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

By Julie Nutini, Mark W. Schmidt, Issam Hadj Laradji, Michael P. Friedlander, Hoyt A. Koepke. 2015

249 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, background): “ng distributions [57, 58, 60, 6] . Accelerated variants of RCD were studied in [34, 16, 1]. For other non-randomized coordinate descent variants and their convergence analysis, we refer the reader to [74, 48, 8]. To the best of our knowledge, mRCD and smRCD have never been analyzed before in any set”
Approximate Steepest Coordinate Descent (2017, methodology): “For smooth functions this strategy yields always better progress than UCD, and the speedup can reach a factor of the dimension (Nutini et al., 2015).”
Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence (2017, background): “We previously showed that this property is also satisfied for the GS rule in the case of logistic regression, provided that the data is sufficiently sparse [61].”
Efficient Use of Limited-Memory Accelerators for Linear Learning on Heterogeneous Systems (2017, background): “Both this line of research as well as steepest coordinate descent [8] are still limited to single coordinate updates, and cannot be readily extended to arbitrary accuracy updates on a larger subset of coordinates (performed per communication round) as required in our heterogeneous setting.”
Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain (2017, methodology): “Theorem 1 and 2 are based on the analysis framework of [22] for the Augmented Lagrangian Method, as well as the recent results on the linear convergence of Frank-Wolfe variants [23] and Greedy Coordinate Descent for non-strongly convex functions of the form (13) [24, 25].”
Optimization Methods for Large-Scale Machine Learning (2016, result): “Using this approach, one obtains a similar result in which c is replaced by ĉ, the strong convexity parameter as measured by the `1-norm [115].”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “For other nonrandomized coordinate descent variants and their convergence analysis, we refer the reader to [199, 143, 27].”
A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing (2015, methodology): “Theoretically, the BCD algorithm and its variants have been signiﬁcantly generalized to accommodate various coordinate update rules [5], [13], [14], and have been made suitable for implementation on modern parallel processing architecture [15]–[19].”
The Cyclic Block Conditional Gradient Method for Convex Optimization Problems (2015, background): “A question related to the discussion of the previous paragraph is to give a theoretical justiﬁcation to this observation or eventually provide iteration dependent block update rules that comply with it (see for example [27] for an illustration in the context of gradient descent).”
Safe Adaptive Importance Sampling (2017, methodology): “Deterministic strategies are seldom used for the data selection—examples are steepest coordinate descent [4, 34, 20] or screening algorithms [14, 15].”