Efficient Greedy Coordinate Descent for Composite Problems
This work addresses the optimization of large-scale non-smooth problems like SVMs, offering potential speed improvements for machine learning applications, though it is incremental as it extends known greedy methods from smooth to non-smooth cases.
The paper tackles the problem of greedy coordinate selection for non-smooth composite optimization, such as L1-regularized problems and SVMs, by providing the first linear convergence rates independent of dimension n and showing speedups similar to smooth cases, with up to n times fewer iterations. It also maps the selection rule to maximum inner product search to enable efficient implementation using nearest neighbor algorithms.
Coordinate descent with random coordinate selection is the current state of the art for many large scale optimization problems. However, greedy selection of the steepest coordinate on smooth problems can yield convergence rates independent of the dimension $n$, and requiring upto $n$ times fewer iterations. In this paper, we consider greedy updates that are based on subgradients for a class of non-smooth composite problems, which includes $L1$-regularized problems, SVMs and related applications. For these problems we provide (i) the first linear rates of convergence independent of $n$, and show that our greedy update rule provides speedups similar to those obtained in the smooth case. This was previously conjectured to be true for a stronger greedy coordinate selection strategy. Furthermore, we show that (ii) our new selection rule can be mapped to instances of maximum inner product search, allowing to leverage standard nearest neighbor algorithms to speed up the implementation. We demonstrate the validity of the approach through extensive numerical experiments.