Approximate Steepest Coordinate Descent
This work addresses optimization efficiency for large-scale problems, but it is incremental as it builds on existing coordinate descent methods.
The paper tackles the problem of coordinate selection in coordinate descent methods for large-scale optimization by proposing a new selection rule that is provably more efficient than random selection and can match steepest coordinate descent, achieving up to an n-fold acceleration. Numerical experiments on Lasso and Ridge regression demonstrate improvements consistent with theoretical results.
We propose a new selection rule for the coordinate selection in coordinate descent methods for huge-scale optimization. The efficiency of this novel scheme is provably better than the efficiency of uniformly random selection, and can reach the efficiency of steepest coordinate descent (SCD), enabling an acceleration of a factor of up to $n$, the number of coordinates. In many practical applications, our scheme can be implemented at no extra cost and computational efficiency very close to the faster uniform selection. Numerical experiments with Lasso and Ridge regression show promising improvements, in line with our theoretical guarantees.