1
$\begingroup$

I would like to know if some variables in design matrix are correlated then LASSO is convex or not. If you give me a proof for convexity of LASSO and ADAPTIVE lasso, I will be thankful. LASSO is defined by minimizing penalized likelihood function. Then in the context of regression with Gaussian errors we have $$ L_n=||Y-X'\beta||_2^2 +\lambda_n||B||_1 ,\quad \lambda_n \geq 0 $$ So my question is, if some columns of $X$ are correlated, then how can I prove that $L_n$ is convex(if it is convex). It is obvious that my goal is minimizing $L_n$ with respect to $\beta$. Thank you.

$\endgroup$
3
$\begingroup$

If $XX'$ is positive semi-definite, then $L_n$ is convex.

Expand $\left \|Y-X'\beta \right \|_2^2$, we get $F(\beta)=Y'Y-2Y'X'\beta+\beta'XX'\beta$. $F(\beta)$ is convex with respect to $\beta$ when $XX'$ is positive semi-definite. As you know $\| \beta \|_1$ is convex, therefore $L_n$ is the sum of two convex function, it's convex.

$\endgroup$
11
  • $\begingroup$ Thanks, Could you please give me a proof? $\endgroup$ – TPArrow Apr 27 '14 at 17:57
  • $\begingroup$ Thank you. So as I understand, positive-semi-define means $det(XX')\geq 0$ then it means even if there exists correlation between variables in $X$ (as a result $det(XX')=0$), LASSO stays convex. Is that true? $\endgroup$ – TPArrow Apr 27 '14 at 18:49
  • $\begingroup$ @HAMEDHASELI positive-semi-define means all its eigenvalues should be larger or equal to 0. $\endgroup$ – E.J. Apr 27 '14 at 19:28
  • $\begingroup$ Thanks you. So based based on your definition of positive-semi-defined matrix, LASSO is always convex either there exist correlation among variables or not. Could you please confirm this? $\endgroup$ – TPArrow Apr 27 '14 at 19:37
  • $\begingroup$ I found this in wikipedia : For any matrix A, the matrix AA is positive semidefinite, and rank(A) = rank(AA). The question arise in my mind is, if a function is convex, it means there exists a unique minimum. Then, why in high-dimensional cases (I mean when the number of variables is more than the number of observations) there are infinite possibilities for the solution of (LASSO)convex function? $\endgroup$ – TPArrow Apr 27 '14 at 19:40

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.