The LASSO problem is well-known problem in ML community given by: \begin{equation} f(x) = \frac{1}{n}\|Ax-b\|^2_2 + \frac{\lambda}{n}\|x\|_1 \end{equation}

This equation appears in paper1 on page 9 (S2GD algorithm). Now, there are two ways to calculate lipschitz constant of the above problem.

  1. $L=\frac{2}{n}\|A^TA\|_2$ which is by going through Hessian way.This can be approximated by $L=\frac{2}{n}\|A^T\|\|A\|$ since former one is costly to compute(from memory perspective).

  2. $L=2*max(sum(X^2,2))$ (in MATLAB, $X^2$ is X.^2). This is basically computing row square; summing and taking max. This is how author in the above paper and their another paper2 has calculated lipschitz constant (however for logistic regression on page 18 of paper2).

My concern is the two ways of calculating L should give the same result but it's NOT!. Specifically, S2GD algorithm is taking long time to converge on different data sets with L set as above. Can somebody tell me the right way to calculate the lipschitz constant for the lasso problem applicable to S2GD algorithm?

  • 2
    $\begingroup$ Your problem (which formula works in matlab, why slow, etc.) is more of "computational science" than mathematics. Standard form of objective: $f(x) = \frac{1}{2}\|Ax-b\|_2^2 + \lambda\|x\|_1$. To compute Lipschitz constant for the smooth part, in Python do: L = scipy.linalg.svdvals(A)[0] ** 2 $\endgroup$ – dohmatob Jan 8 '16 at 12:34
  • $\begingroup$ The right thing to do is to adapt L over the course of the algorithm. A fixed L is necessarily over conservative. $\endgroup$ – Michael Grant Jan 8 '16 at 13:12
  • $\begingroup$ Agreed that it's more of "computational science". However, the author in the above paper uses a technique to calculate L which is to take the max of sum of each feature vector $a_i$. Can you tell me if this approach will yield the same L as calculated from method using Hessian way? $\endgroup$ – chandresh Jan 8 '16 at 13:12
  • $\begingroup$ @MichaelGrant. Can you point out some papers to choose L adaptively? $\endgroup$ – chandresh Jan 8 '16 at 13:15
  • 1
    $\begingroup$ Your problem is believing that algorithms described in papers are actually meant to be used in practice. :-) Seriously, go check out TFOCS. Sure, we wrote a paper, but after we had software we liked. And one of the first things we had to tackle was figuring out a way to select $L$ intelligently and adaptively. $\endgroup$ – Michael Grant Jan 8 '16 at 14:43

Your Answer

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

Browse other questions tagged or ask your own question.