Any optimal solution w∗w^* can be expressed as:

w∗=∑j=1Nα(j)x(j)w^* = \sum^N_{j = 1} \alpha^{(j)}x^{(j)}

for some coefficients α(i),…,α(N)∈R\alpha^{(i)}, \dots, \alpha^{(N)} \in \R

considering the regularized empirical risk minimization problem:

min⁡w∈RdJ(w)=∑i=1NL(y(i),w⊺x(i))+λ∣∣w∣∣2\min_{w \in \R^d} \mathcal{J}(w) = \sum^N_{i = 1} L(y^{(i)}, w^\intercal x^{(i)}) + \lambda \mid\mid w\mid\mid^2

where

  • L:L: a loss function
  • {x(i),y(i)}i=1N:\{x^{(i)}, y^{(i)}\}_{i = 1}^{N}: the training examples
  • λ>0:\lambda > 0: a regularization parameter
  • w∈Rd:w \in \R^d: the weight vector

Proof

1. Decompose w

Any vector w∈Rdw \in \R^d can be uniquely decomposed into two orthogonal components:

w=w∣∣+w⊥w = w_{||} + w_{\perp}

where

  • w∣∣∈span{x(i),…,x(N)}w_{||} \in span\{x^{(i)}, \dots, x^{(N)}\} (parallel component)
  • w⊥⊥span{x(i),…,x(N)}w_{\perp} \perp span\{x^{(i)}, \dots, x^{(N)}\} (parallel component)

2. Rewrite w∣∣w_{||}

w∣∣=∑j=1Nα(j)x(j)w_{||} = \sum^N_{j = 1} \alpha^{(j)}x^{(j)}

for some coefficient α(1),…,α(N)\alpha^{(1)}, \dots, \alpha^{(N)}

Tip

Full proof can be found in Orthogonal Decomposition Theorem

3. Analyze predictions on training data

w⊺x(i)=(w∣∣+w⊥)⊺x(i)w^\intercal x^{(i)} = (w_{||} + w_{\perp})^\intercal x^{(i)}

Given that w⊥⊥x(i)w_\perp\perp x^{(i)}

w⊺x(i)=w∣∣⊺x(i)+w⊥⊺x(i)=w∣∣⊺x(i)\begin{align*} w^\intercal x^{(i)} &= w_{||}^\intercal x^{(i)} + w_\perp^\intercal x^{(i)} \\ &= w_{||}^\intercal x^{(i)} \end{align*}

4. Compare ERM functions

Given that w∣∣⊥w⊥w_{||} \perp w_{\perp}

∣∣w∣∣2=∣∣w∣∣+w⊥∣∣2=∣∣w∣∣∣∣2+∣∣w⊥∣∣2||w||^2 = ||w_{||} + w_\perp ||^2 = ||w_{||}||^2 + ||w_\perp||^2

Then, plug them back to risk minimization functions

J(w)=∑i=1NL(y(i),w∣∣⊺x(i))+λ∣∣w∣∣∣∣2+λ∣∣w⊥∣∣2J(w∣∣)=∑i=1NL(y(i),w∣∣⊺x(i))+λ∣∣w∣∣∣∣2∵λ∣∣w⊥∣∣2≥0 and J(w)=J(w∣∣)+λ∣∣w⊥∣∣2∴J(w)≥J(w∣∣)  ⟹  w∗=∑j=1Nα(j)x(j)\begin{align*} &\mathcal{J}(w) = \sum^N_{i = 1} L(y^{(i)}, w_{||}^\intercal x^{(i)}) + \lambda||w_{||}||^2 + \lambda||w_{\perp}||^2\\ \\ &\mathcal{J}(w_{||}) = \sum^N_{i = 1} L(y^{(i)}, w_{||}^\intercal x^{(i)}) + \lambda||w_{||}||^2 \\ \\ &\because \lambda ||w_{\perp}||^2 \ge 0 \text{ and } \mathcal{J}(w) = \mathcal{J}(w_{||}) + \lambda ||w_{\perp} ||^2\\ \\ &\therefore \mathcal{J}(w) \ge \mathcal{J}(w_{||}) \\ \\ &\implies w^* = \sum^N_{j = 1} \alpha^{(j)}x^{(j)} \end{align*}