Approximate Steepest Coordinate Descent

Abstract

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.

appearing at ICML 2017

Cited by in corpus (8)

• Decentralized Deep Learning with Arbitrary Communication Compression
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches
• A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems
• High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent
• Randomized Gradient Boosting Machine
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Safe Adaptive Importance Sampling