Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection

Abstract

There has been significant recent work on the theory and application of randomized coordinate descent algorithms, beginning with the work of Nesterov [SIAM J. Optim., 22(2), 2012], who showed that a random-coordinate selection rule achieves the same convergence rate as the Gauss-Southwell selection rule. This result suggests that we should never use the Gauss-Southwell rule, as it is typically much more expensive than random selection. However, the empirical behaviours of these algorithms contradict this theoretical result: in applications where the computational costs of the selection rules are comparable, the Gauss-Southwell selection rule tends to perform substantially better than random coordinate selection. We give a simple analysis of the Gauss-Southwell rule showing that---except in extreme cases---its convergence rate is faster than choosing random coordinates. Further, in this work we (i) show that exact coordinate optimization improves the convergence rate for certain sparse problems, (ii) propose a Gauss-Southwell-Lipschitz rule that gives an even faster convergence rate given knowledge of the Lipschitz constants of the partial derivatives, (iii) analyze the effect of approximate Gauss-Southwell rules, and (iv) analyze proximal-gradient variants of the Gauss-Southwell rule.

ICML 2015. v2: Updated the Gauss-Southwell-q result in Section 8 and Appendix H, to remove the part depending on mu_1 (the proof had an error). Added Section 8.1, which discusses conditions under which a rate depending on mu_1 does hold

References in corpus (1)

• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

Cited by in corpus (28)

• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Coordinate Friendly Structures, Algorithms and Applications
• Forming intracluster gas in a galaxy protocluster at a redshift of 2.16
• A Primer on Coordinate Descent Algorithms
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank
• Accelerating Greedy Coordinate Descent Methods
• Breaking Locality Accelerates Block Gauss-Seidel
• From safe screening rules to working sets for faster Lasso-type solvers
• FIRE: An Optimization Approach for Fast Interpretable Rule Extraction
• Accelerated Coordinate Descent with Arbitrary Sampling and Best Rates for Minibatches
• Safe Screening for the Generalized Conditional Gradient Method
• TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods
• On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization
• On the Minimization of Convex Functionals of Probability Distributions Under Band Constraints
• Variable selection for Gaussian process regression through a sparse projection
• Stochastic Spectral and Conjugate Descent Methods
• A better convergence analysis of the block coordinate descent method for large scale machine learning
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• Markov Chain Block Coordinate Descent
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Global linear convergent algorithm to compute the minimum volume enclosing ellipsoid
• High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent
• Accelerated Block Coordinate Proximal Gradients with Applications in High Dimensional Statistics
• Distributed Convolutional Dictionary Learning (DiCoDiLe): Pattern Discovery in Large Images and Signals
• Stochastic Primal Dual Coordinate Method with Non-Uniform Sampling Based on Optimality Violations
• Safe Adaptive Importance Sampling