User digdug - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T09:23:00Z http://mathoverflow.net/feeds/user/28115 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/118333/smoothing-l1-norm-huber-vs-conjugate Smoothing L1 norm, Huber vs Conjugate digdug 2013-01-08T04:36:48Z 2013-01-08T09:51:34Z <p>I'm trying to minimize a convex (not necessarily strictly convex) function involving an L1 norm (similar to lasso), which makes it non-differentiable at some points. So I'd like to smooth it and treat it as an L2 norm problem.</p> <p>The two approaches I've seen ( <a href="http://www.ee.ucla.edu/~vandenbe/236C/lectures/smoothing.pdf" rel="nofollow">http://www.ee.ucla.edu/~vandenbe/236C/lectures/smoothing.pdf</a> ) are directly smoothing the L1 norm using the Huber function, and smoothing the conjugate (i.e, derive the dual norm, here it's L-infinity, which is still non-differentiable, then smooth that).</p> <p>The Huber approach is much simpler, is there any advantage in the conjugate method over Huber? I can't see the point of smoothing the dual instead of just smoothing the primal.</p> http://mathoverflow.net/questions/112450/choice-of-lipschitz-constant-for-proximal-gradient-optimization Choice of Lipschitz constant for proximal gradient optimization digdug 2012-11-15T05:02:06Z 2013-01-08T02:20:01Z <p>I'm trying to use proximal gradient methods (Forward-Backwards Splitting and FISTA) to minimize a function</p> <p>$f(B) = \frac{1}{2}|| XB - Y||_F^2 + \frac{\gamma}{2}||B C^T||_F^2$, where $X \in \mathbb{R}^{N \times p}, Y \in \mathbb{R}^{N \times K}, B \in \mathbb{R}^{p \times K}, C \in \mathbb{R}^{E \times K}.$</p> <p>I know this can be done with gradient descent but I'd like to use proximal methods anyway for didactic purposes. Since the entire function is twice differentiable, I don't care about the actual prox operator at the moment.</p> <p>Now, the basic proximal methods require computing the Lipschitz constant L. I have seen different versions of this, e.g.</p> <p>$L = ||X^T X||_2^2 \;||H_w \psi||_2^2$ </p> <p>where $||\cdot||_2^2$ is squared spectral norm of the matrix and $H$ is Hessian of the function $f(w) =\psi(Xw)$ (<a href="http://www.di.ens.fr/~fbach/bach_jenatton_mairal_obozinski_FOT.pdf" rel="nofollow">http://www.di.ens.fr/~fbach/bach_jenatton_mairal_obozinski_FOT.pdf</a>, p. 43). I've seen other formulations in other papers, which is confusing.</p> <p>Is there a "canonical" way to derive a "good" Lipschitz constant for these sort of functions?</p> http://mathoverflow.net/questions/118333/smoothing-l1-norm-huber-vs-conjugate/118346#118346 Comment by digdug digdug 2013-01-08T23:04:22Z 2013-01-08T23:04:22Z Great answer, thanks. One more clarification: are there any guarantees that minimizing the smoothed dual will actually produce good (optimal?) solutions to the original primal? http://mathoverflow.net/questions/112450/choice-of-lipschitz-constant-for-proximal-gradient-optimization/112453#112453 Comment by digdug digdug 2012-11-15T22:27:31Z 2012-11-15T22:27:31Z Great! Is there a reference/tutorial that explains this? http://mathoverflow.net/questions/112450/choice-of-lipschitz-constant-for-proximal-gradient-optimization/112453#112453 Comment by digdug digdug 2012-11-15T11:04:53Z 2012-11-15T11:04:53Z Thanks again, but my question is simply <i>how</i> do I compute the Lipschitz constant, at least for the above function? I cannot find a derivation in Vandenberghe's notes. http://mathoverflow.net/questions/112450/choice-of-lipschitz-constant-for-proximal-gradient-optimization/112453#112453 Comment by digdug digdug 2012-11-15T05:39:59Z 2012-11-15T05:39:59Z Thanks, but in simple cases like above where the Lipschitz constant can be derived beforehand, wouldn't that be more computationally efficient than line search? Plus I'd like to understand the basics first...