Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.