2
$\begingroup$

Is there any intuition why the ridge regression is strictly convex, while the LASSO is only convex?

Does it have to do with the "corners" of the L1 regularization?

$\endgroup$
  • $\begingroup$ Welcome to CV. The image and the definition on the wiki page for 'strictly convex space' seem to answer the question. Can you elicite what you find problematic on the wiki page? – $\endgroup$ – user603 Apr 14 '14 at 15:44
3
$\begingroup$

Conceptually, a function is convex is for any pair $(x_1, x_2)$, the line segment joining $(x_1,f(x_1))$ and $(x_2,f(x_2))$ lies above the curve $y=f(x)$. It is strictly convex if this line segment strictly lies above the curve (i.e. the only points they have in common are the endpoints $(x_1,f(x_1))$ and $(x_2,f(x_2))$). The LASSO penalty is not strict, because if $x_1$ and $x_2$ have the same sign, then the line segment and the curve are exactly equal, and therefore they have infintely many points in common.

$\endgroup$
  • $\begingroup$ What's the difference between "lie above the line" and "strictly above the line"? How does same sign come into this problem? $\endgroup$ – user13985 Sep 5 '17 at 16:40
  • $\begingroup$ @user13985 The line segment and the curve will always have at least two points in common, namely the two endpoints. "Strictly above the curve" means that there are no other points in common. The "same sign" issue has to do with the definition of the lasso penalty $\endgroup$ – M Turgeon Sep 5 '17 at 16:50
  • $\begingroup$ It's like "less than" vs "less than and equal to"? As for LASSO, I've always struggled how it works, could you point to some simple introduction? $\endgroup$ – user13985 Sep 6 '17 at 21:20
1
$\begingroup$

You need to begin with an understanding of what a "strictly convex" function is. A function f(x) is strictly convex on a convex domain if for every $x_{1}$ and $x_{2}$ in the domain and every $t$, with $0< t < 1$,

$ f((1-t)x_{1}+tx_{2}) < (t-1)f(x_{1})+tf(x_{2})$

In LASSO, you're minimizing $\| \beta \|_{1}$, which is not a strictly convex function.

In ridge regression, you're minimizing $\| X \beta -y \|_{2}^{2}+\lambda \| \beta \|_{2}^{2}$, which is a strictly convex function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.