User digdug - MathOverflow

Smoothing L1 norm, Huber vs Conjugate

2013-01-08T04:36:48Z

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.

The two approaches I've seen ( http://www.ee.ucla.edu/~vandenbe/236C/lectures/smoothing.pdf ) 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).

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.

Choice of Lipschitz constant for proximal gradient optimization

2012-11-15T05:02:06Z

I'm trying to use proximal gradient methods (Forward-Backwards Splitting and FISTA) to minimize a function

$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}.$

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.

Now, the basic proximal methods require computing the Lipschitz constant L. I have seen different versions of this, e.g.

$L = ||X^T X||_2^2 \;||H_w \psi||_2^2$

where $||\cdot||_2^2$ is squared spectral norm of the matrix and $H$ is Hessian of the function $f(w) =\psi(Xw)$ (http://www.di.ens.fr/~fbach/bach_jenatton_mairal_obozinski_FOT.pdf, p. 43). I've seen other formulations in other papers, which is confusing.

Is there a "canonical" way to derive a "good" Lipschitz constant for these sort of functions?

Comment by digdug

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?

Comment by digdug

2012-11-15T22:27:31Z

Great! Is there a reference/tutorial that explains this?

Comment by digdug

2012-11-15T11:04:53Z

Thanks again, but my question is simply how do I compute the Lipschitz constant, at least for the above function? I cannot find a derivation in Vandenberghe's notes.

Comment by digdug

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...