14
$\begingroup$

I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ has the property that restricted to any single variable, it is easy to optimize. So coordinate descent proceeds by cycling through the coordinates, fixing all but the chosen one and minimizing along that coordinate. Eventually, improvements slow to a halt, and you terminate.

My question is: is there any theoretical study of coordinate descent methods that talks about convergence rates, and properties of $f$ that make the method work well, and so on ? Obviously, I'm not expecting fully general answers, but answers that illuminate cases where the heuristic does well would be helpful.

Aside: the alternating optimization technique used for $k$-means can be seen as an example of coordinate descent, and the Frank-Wolfe algorithm seems related (but is not a direct example of the framework)

$\endgroup$
  • $\begingroup$ At least as described in Ken Clakrson's paper kenclarkson.org/sga/p.pdf, Frank-Wolfe is very very similar. The only difference seems to be that in FW you pick the best coordinate to descend on. It has the same sparsity property that matus mentions. $\endgroup$ – Sasho Nikolov Jul 25 '14 at 16:21
  • 2
    $\begingroup$ Sebastien Bubeck has a recent monograph on convex optimization and iteration complexity for various methods. May be a useful place to look. blogs.princeton.edu/imabandit/2014/05/16/… $\endgroup$ – Chandra Chekuri Jul 26 '14 at 2:14
24
$\begingroup$

(Edit notes: I reorganized this after freaking out at its length.)

Literature on coordinate descent can be a little hard to track down. Here are some reasons for this.

  1. Many of the known properties of coordinate methods are captured in umbrella theorems for more general descent methods. Two examples of this, given below, are the fast convergence under strong convexity (hold for any $l^p$ steepest descent), and the general convergence of these methods (usually attributed to Zoutendijk).

  2. Naming is not standard. Even the term "steepest descent" is not standard. You may have success googling any of the terms "cyclic coordinate descent", "coordinate descent", "Gauss-Seidel", "Gauss-Southwell". usage is not consistent.

  3. The cyclic variant rarely receives special mention. Instead, usually only the best single choice of coordinate is discussed. But this almost always gives the cyclic guarantee, albeit with an extra factor $n$ (number of variables): this is because most convergence analyses proceed by lower bounding the improvement of a single step,and you can ignore the extra coordinates. It also seems difficult to say anything general about what cyclic buys you, so people just do the best coordinate and the $n$ factor can usually be verified.

Rate under strong convexity. The simplest case is that your objective function is strongly convex. Here, all gradient descent variants have the rate $\mathcal O(\ln (1/\epsilon))$. This is proved in Boyd & Vandenberghe's book. The proof first gives the result for gradient descent, and then uses norm equivalence to give the result for general $l^p$ steepest descent.

Constraints. Without strong convexity, you have to start being a little bit careful. You didn't say anything about constraints, and thus in general, the infimum may not be attainable. I'll say briefly on the topic of constraints that the standard approach (with descent methods) is to project onto your constraint set each iteration to maintain feasibility, or to use barriers to roll the constraints into your objective function. In the case of the former, I don't know how it plays with coordinate descent; in the case of the latter, it works fine with coordinate descent, and these barriers can be strongly convex.

More specifically to coordinates methods, rather than projecting, many people simply make the coordinate update maintain feasibility: this for instance is exactly the case with the Frank-Wolfe algorithm and its variants (i.e., using it to solve SDPs).

I'll also note briefly that the SMO algorithm for SVMs can be viewed as a coordinate descent method, where you are updating two variables at once, and maintaining a feasibility constraint while you do so. The choice of variables is heuristic in this method, and so the guarantees are really just the cyclic guarantees. I'm not sure if this connection appears in standard literature; I learned about the SMO method from Andrew Ng's course notes, and found them to be quite clean.

General convergence guarantee. What I know in this more general setting (for coordinate descent) is much weaker. First, there is an ancient result, due to Zoutendijk, that all these gradient variants have guaranteed convergence; you can find this in the book by Nocedal & Wright, and it also appears in some of Bertsekas's books (at the very least, "nonlinear programming" has it). These results are again for something more general than coordinate descent, but you can specialize them to coordinate descent, and then get the cyclic part by multiplying by $n$.

More specifically to cyclic coordinate descent, there's a paper by Luo & Tseng titled "On the convergence of the coordinate descent method for convex differentiable minimization". These results require the infimum to be attainable. There are no rates here, only convergence guarantees, but these results have been applied to some more specialized settings to get rates; for instance, in boosting (in the special case that the infimum is attainable), Warmuth, Mika, Raetsch, and Warmuth ("on the convergence of leveraging") were able to show rates of $\mathcal O(\ln(1/\epsilon))$.

There are some more recent results on coordinate descent, I've seen stuff on arXiv. Also, luo&tseng have some newer papers. but this is the main stuff.

More convergence rates in the special case of boosting. Due to its importance, there has been other specialization in the case of boosting. This is a pretty severe special case because your objective can be written $\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$ where $g$ is a (convex) univariate function and the $(a_i)_1^m$ are fixed vectors ($\lambda$ is the optimization variable). Bickel, Ritov, and Zakai ("some theory for generalized boosting algorithms") showed you can get $\exp(1/\epsilon^2)$ in general, and there are more recent results by other people showing $\mathcal O(1/\epsilon)$. The difficulty in these is that the infimum is not assumed attainable.

The issue with exact updates. Also, it is very often the case that you do not have a closed form single coordinate update. Or the exact solution may simply not exist. But fortunately, there are lots and lots of line search methods that get basically the same guarantees as an exact solution. This material can be found in standard nonlinear programming texts, for instance in the Bertsekas or Nocedal&Wright books mentioned above.

Vis a vis your second paragraph: when these work well. First, many of the above mentioned analyses for gradient work for coordinate descent. So why not always use coordinate descent? The answer is that for many problems where gradient descent is applicable, you can also use Newton methods, for which superior convergence can be proved. I don't know of a way to get the Newton advantage with coordinate descent. Also, the high cost of Newton methods can be mitigated with Quasinewton updates (see for instance LBFGS).

Second, the place where these methods shine is where the presumed solution is sparse (in the $l^0$ sense). Of course, there are NP-hardness issues with this kind of sparsity, but the point is that if you run $k$ iterations, you have $k$ nonzero entries. These facts generalize to, say, using coordinate methods with SDP solvers, where each iteration you throw in a rank 1 matrix, thus with $k$ iterations you have a rank $k$ iterate. There is a great paper on this topic, by Shalev-Shwartz, Srebro, and Zhang, titled "trading accuracy for sparsity in optimization problems with sparsity constraints". Most specifically to the second paragraph of your question, this paper gives further properties on $f$ that allow fast convergence and good sparsity (true to its title).

$\endgroup$
  • 2
    $\begingroup$ wow. that's a really comprehensive answer. Thanks ! $\endgroup$ – Suresh Venkat Aug 12 '11 at 23:18
2
$\begingroup$

I suggest looking here, we've done some work in this area:

http://arxiv.org/abs/1107.2848

Cheers

Peter

$\endgroup$
2
$\begingroup$

We've just put up a paper on arXiv (http://arxiv.org/abs/1201.1214) that proves generic lower bounds for "statistical algorithms" for optimization problems, with each "problem" having its own lower bound depending on its various properties.

Coordinate descent (and pretty much anything else we can think of) can be seen as a statistical algorithm in our framework, so hopefully this paper has some results that will be of interest to you.

$\endgroup$
  • $\begingroup$ Cool. Will look into it. $\endgroup$ – Suresh Venkat Jan 6 '12 at 19:47
2
$\begingroup$

Note that in optimization, "convergence rate" usually means asymptotic behavior. That is, the rate only applies to the neighborhood of optimal solutions. In that sense, Luo & Tseng did prove linear convergence rates for some non-strongly convex objective functions in the paper "On the convergence of the coordinate descent method for convex differentiable minimization".

The non-asymptotic convergence rate, aka "iteration complexity", is generally more useful in bounding the iteration numbers of minization algorithms. For strongly convex objective functions, the iteration complexity of cyclic coordinate descent methods is already shown in Luo & Tseng's Error bounds and convergence analysis of feasible descent methods: a general approach if a global error bound is used. For non-strongly convex problems, we have some new results in Iteration Complexity of Feasible Descent Methods for Convex Optimization. To be specific, we've shown the iteration complexity for cyclic coordinate descent methods on problems such as the dual form of SVMs and Gauss-Seidel methods. Further, the results also cover other feasible descent methods including gradient descent and friends.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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