7
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Dirk
    Commented Jan 8, 2013 at 7:15
  • $\begingroup$ @Dirk: why don't you write an answer about these? What you write here might interest more people. $\endgroup$
    – András Bátkai
    Commented Jan 8, 2013 at 7:18

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – digdug
    Commented Jan 8, 2013 at 23:04
  • $\begingroup$ 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". $\endgroup$
    – Dirk
    Commented Jan 9, 2013 at 9:52
  • $\begingroup$ Smoothing the dual, we get a strongly convex primal. Then, is it true that the primal is smooth because the primal is strongly convex? $\endgroup$
    – jakeoung
    Commented Nov 17, 2015 at 22:19
  • $\begingroup$ @jakeoung No, this is not true in general. $\endgroup$
    – Dirk
    Commented Nov 18, 2015 at 5:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .