The effectiveness of coordinate ascent Why is it so successful for the lasso, though for most other problems standard Quasi-Newton approaches seem to be preferred?  I sort of have this vague geometric idea that it might have to do with the shape of the $L_1$ ball, but haven't really been able to formalize it.  
 A: There are several things to keep in mind here. Lasso for linear regression is optimization of a quadratic function with an $\ell_1$-norm penalty term. The latter is non-smooth, and one can put the problem into the context of quadratic optimization with linear constraints. General purpose solvers turn out to be less than optimal for this particular problem, which has special properties. The coordinate descent algorithm relies on these properties for convergence, see e.g. this paper for the concept of separability. 
Because the optimization is optimization of a non-smooth function the methods that rely on smoothness, such as Quasi-Newton, are not appropriate. For the linear regression problem the coordinate descent algorithm is particularly fast because there are several tricks that save computations. However, there are other fast algorithms like lars aimed directly at the regression problem. In the comparisons I have seen, the implementation of coordinate descent in the R package glmnet is faster than the implementation in the lars package, but the former is also really optimized Fortran code. 
For more general $\ell_1$-penalized optimization problems I have found the following to be important for speed:


*

*Warm starts. For a decreasing sequence of penalty parameter values ($\lambda$'s) we  use the parameter from a previous $\lambda$-value as start guess for the next $\lambda$-value. 

*The coordinate wise update splits into two parts. First we check if the coordinate should stay zero with minimal computations (happens a lot, no extra computations if that is the case). If not, find non-zero update of the coordinate.  

*Sparseness is preserved. The algorithm does not only produce a result with many zeroes but keeps many coordinates at zero for the entire algorithm. Whether this matters for speed depends on the problem, but often sparseness can be exploited in the other computations. 


Whether the non-zero update of one coordinate at a time is best for a particular problem will depend on the problem. It works very well for the linear regression problem and  generalized linear models because each update is the minimization of a simple quadratic function, which is very fast. 
A: Trevor Hastie has some ideas starting on page 19 here.  A big part of the answer has to do with being able to simply ignore large portions of the data during updates, either because things are sparse or because we're only looking at one variable at a time or because solutions from a few steps back can be re-used without worrying too much that they're out of date.
