Anderson acceleration of coordinate descent

Abstract

Acceleration of first order methods is mainly obtained via inertial techniques à la Nesterov, or via nonlinear extrapolation. The latter has known a recent surge of interest, with successful applications to gradient and proximal gradient techniques. On multiple Machine Learning problems, coordinate descent achieves performance significantly superior to full-gradient methods. Speeding up coordinate descent in practice is not easy: inertially accelerated versions of coordinate descent are theoretically accelerated, but might not always lead to practical speed-ups. We propose an accelerated version of coordinate descent using extrapolation, showing considerable speed up in practice, compared to inertial accelerated coordinate descent and extrapolated (proximal) gradient descent. Experiments on least squares, Lasso, elastic net and logistic regression validate the approach.

References in corpus (10)

• Anderson Accelerated Douglas-Rachford Splitting
• A Primer on Coordinate Descent Algorithms
• Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations
• Implicit differentiation of Lasso-type models for hyperparameter optimization
• OpenML-Python: an extensible Python API for OpenML
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• Anderson Acceleration of Proximal Gradient Methods
• Geometry of First-Order Methods and Adaptive Acceleration
• Model identification and local linear convergence of coordinate descent
• Generalized Framework for Nonlinear Acceleration

Cited by in corpus (1)

• The folded concave Laplacian spectral penalty learns block diagonal sparsity patterns with the strong oracle property