# Smoothing L1 norm, Huber vs Conjugate

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.

-
Smoothing the dual will not give you a smooth primal. However, you get a strongly convex primal by dual smoothing (as opposed to merely a strictly convex primal by Huber smoothing). Hence, it depends on what kind of regularity you are aiming at: A smoother primal or a "more convex" primal - both can be helpful algorithmically. Moreover, note that there are numerous methods to treat nonsmooth convex minimization problems efficiently. – Dirk Jan 8 '13 at 7:15
@Dirk: why don't you write an answer about these? What you write here might interest more people. – András Bátkai Jan 8 '13 at 7:18

## 1 Answer

Following the suggestion of András Bátkai I post my comment as an answer:

Smoothing the dual or the primal problem are quite different things: Smoothing the dual will not give you a smooth primal. However, you get a strongly convex primal by dual smoothing (as opposed to merely a strictly convex primal by Huber smoothing). Hence, it depends on what kind of regularity you are aiming at: A smoother primal or a "more convex" primal - both can be helpful algorithmically. A smooth primal allows you to use gradients instead of subgradients and in turn allows you to apply gradient methods with appropriate stopping rules and such. A strongly convex primal leads to a proximal mapping of the primal objective which is not only non-expansive but contractive which is favorable for proximal-splitting methods.

Of course, you can also apply both primal and dual smoothing if you like.

Moreover, note that there are numerous methods to treat nonsmooth convex minimization problems efficiently

-
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? – digdug Jan 8 '13 at 23:04
I don't think so - I even think that a dual solution does not always give you a way to infer a primal solution... (regardless of smoothing). Probably an answer can be found in Nesterov's "Smooth minimization of non-smooth problems". – Dirk Jan 9 '13 at 9:52
Smoothing the dual, we get a strongly convex primal. Then, is it true that the primal is smooth because the primal is strongly convex? – jakeoung Nov 17 '15 at 22:19
@jakeoung No, this is not true in general. – Dirk Nov 18 '15 at 5:25