Pathwise coordinate optimization

TLDR

Coordinate‑wise descent algorithms have been proposed for L1‑penalized regression (lasso) but are rarely used in convex optimization. The study considers one‑at‑a‑time coordinate‑wise descent algorithms for a class of convex optimization problems. The authors develop coordinate‑wise descent methods, extend them to a generalized algorithm for the fused lasso, and further generalize to two‑dimensional fused lasso, applying them to image smoothing tasks. The proposed coordinate‑wise descent algorithm outperforms LARS in large lasso problems, extends to garotte and elastic net, and the generalized fused lasso algorithm solves problems faster than standard convex optimizers and performs well on two‑dimensional image smoothing.

Abstract

We consider “one-at-a-time” coordinate-wise descent algorithms for a class of convex optimization problems. An algorithm of this kind has been proposed for the L1-penalized regression (lasso) in the literature, but it seems to have been largely ignored. Indeed, it seems that coordinate-wise algorithms are not often used in convex optimization. We show that this algorithm is very competitive with the well-known LARS (or homotopy) procedure in large lasso problems, and that it can be applied to related methods such as the garotte and elastic net. It turns out that coordinate-wise descent does not work in the “fused lasso,” however, so we derive a generalized algorithm that yields the solution in much less time that a standard convex optimizer. Finally, we generalize the procedure to the two-dimensional fused lasso, and demonstrate its performance on some image smoothing problems.