-1
$\begingroup$

Wondering if there is an established result for the convergence rate when solving L1 regularized optimization via coordinate descent with tiny step? By "tiny step" I mean the step is always set to a very small positive constant, involving none of those step selection technique.

$\endgroup$
  • 1
    $\begingroup$ you posted the same question on math.sx (math.stackexchange.com/questions/358379/…). I think this one should be closed. You can check results by Boyd and Vandenbergh (non technical) or more technical results by Nesterov and Nemirovsky. You can also look up ISTA and FISTA methods which should give you an idea. If I remember well you can't hope for anything better than quadratic. $\endgroup$ – tibL Apr 11 '13 at 16:04
  • 1
    $\begingroup$ I've flagged your post on math.se and I'm waiting for moderators decision there. In any case, there should be only one copy of this question on SE sites. $\endgroup$ – chl Apr 11 '13 at 17:31
  • $\begingroup$ Sorry, I didn't realize that duplicate question is not allowed. My apology. Shall I delete the same question on math.se? The best answer for this question so far seems to be still from stats.se... $\endgroup$ – pengsun.thu Apr 15 '13 at 14:19
2
$\begingroup$

Quite slow.

Convergence rate in LASSO-type estimators are always hard to get; mostly because you don't have a good a priori knowledge of the smoothness of $f$, thanks to the $\ell_1$ objective function being non-differentiable(Ref. 1, Sec. 5, Ref. 3, Sec. 3). There are some results on the convergence of the coordinate descent method for convex differentiable minimization that state that : "for a strictly convex function which is twice differentiable in its effective domain the convergence is at least linear" (Ref. 2); but you can not use that for $\ell_1$ directly. (Actually that is the caveat missing from answer you got in math.stackexchange)

Assuming you are interested in some actual application, this thread might be of interest to you: Stochastic coordinate descent for $\ell_1$ regularization; even in the case of Stochastic CD the authors present the step size is modified though.

If you are determined to use a fixed step-size you might as well try steepest descent; given you use only gradient information you might as well try to utilize it to the max. Check how a Line Search works and what Wolfe Conditions are; step-selection (in simple cases) is not that hard to include in an optimization algorithm. :)

$\endgroup$
  • $\begingroup$ Thanks for your detailed and patient answer. I just find I actually haven't figured out such a question: if we solve $min \quad \phi(x)$ using coordinate descent with tiny step size, do we get the $\ell$-1 regularization path for $min \quad \left(\phi(x) + \lambda||x||_1 \right)$, where $\phi(x)$ is smoothly convex function? $\endgroup$ – pengsun.thu Apr 15 '13 at 14:28

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