Regularization

Model complexity.

Lasso

minimize $(x - a)^2 + (y - b)^2$ subject to $|x| + |y| = 1$.

image here.

For almost all of $(a, b)$, the optimum occurs at the corner.

Now for the real thing.

minimize $f(x_1, \ldots, x_d)$ subject to $\sum_{i = 1}^d |x_i| =1$. where $f$ is convex.

Let's call $\min f(x_1, \ldots, x_d) + \lambda ||x||_1$ proposition $(P)$. Now call $\min f(x_1, \ldots, x_d)$ s.t. $||x||_1 = \alpha$ proposition $(P_{\alpha})$.

Let $m_{\alpha}$ be its optimal value of $P_{\alpha}$.

Let $\alpha^{*} = \mathrm{argmin}_{\alpha} m_{\alpha}$.

Then $(P)$ is equivalent to $\min f(x_1, \ldots, x_d) + \lambda \alpha^{*}$ s.t. $||x||_1 = \alpha^{*}$.

Thus the solution of $(P)$ is sparse.