Coordinate descent algorithms
By Stephen J. Wright. 2015
1,641 citations recorded by the source corpus.
Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate descent approach, together with variants and extensions and their convergence properties, mostly with reference to convex objectives. We pay particular attention to a certain problem structure that arises frequently in machine learning applications, showing that efficient implementations of accelerated coordinate descent algorithms are possible for problems of this type. We also present some parallel variants and discuss their convergence properties under several models of parallel execution.
Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Algorithms & Complexity
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
- Peter Richtárik
- Martin Jaggi
- Nicolas Loizou
- Jakub Konecný
- Sebastian U. Stich
- Michael I. Jordan
- Percy Liang
- Mohit Bansal
In Computational Mechanics
- Peter Richtárik
- Nicolas Loizou
- Jakub Konecný
- Martin Takác
- Martin Jaggi
- Sebastian U. Stich
- Michael I. Jordan
- Francis R. Bach
In Optimization & Training
- Peter Richtárik
- Jakub Konecný
- Nicolas Loizou
- Martin Jaggi
- Sebastian U. Stich
- Martin Takác
- Simon Lacoste-Julien
- Francis R. Bach
In Algorithms & Complexity
- Nicolas Loizou
- Aurélien Bellet
- Martin Jaggi
- Sebastian U. Stich
- Peter Richtárik
- Marc Tommasi
- Rachid Guerraoui
- Stephen P. Boyd
Citations in the corpus
- Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, methodology): “It is important to note that the linear dependency of L k, K in the block size κ , which is the worst possible dependency for block Lipschitz constants (Wright, 2015), is tight for our objective function.”
- Personalized and Private Peer-to-Peer Machine Learning (2017, background): “This follows from a slight adaptation of the proof of Wright (2015) (Theorem 1 therein) to the block coordinate descent case.”
- Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, neutral): “In order to derive a convergence rate for the above algorithm under the SGC, we first observe that a form of the SGC is satisfied in the case of coordinate descent [39].”
- CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “This algorithm and its variants are increasingly used in practice (Wright, 2015), and extensions such as accelerated and parallel versions can directly be applied (Shalev-Shwartz and Zhang, 2014; Fan et al., 2008) in our framework.”
- Group Knowledge Transfer: Collaborative Training of Large CNNs on the Edge (2020, background): “The essence of GKT is that it reformulates FL as an alternating minimization (AM) approach [14, 15, 16, 17, 18, 19], which optimizes two random variables (the edge model and the server model) by alternatively fixing one and optimizing another.”
- Factorized Q-learning for large-scale multi-agent systems (2018, background): “, solving much simpler univariate optimization problems in a loop [32].”
- Distributed optimization with arbitrary local solvers (2015, methodology): “This algorithm and its variants are increasingly used in practice [57, 68].”
- Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “This algorithm and its variants are increasingly used in practice [186, 164].”
- Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, background): “Note that the dual problem of (5) takes the form of a quadratic minimization problem [14], and randomized methods such as coordinate descent [23, 36], random pursuit [31, 32] or stochastic dual ascent [14] can thus also be captured as special instances of this method.”
- Language2Pose: Natural Language Grounded Pose Forecasting (2019, background): “As L j is a mutivariate function in X 1: N and Y 1: T , co-ordinate descent [33] for optimizing the loss function is a natural choice and is described in Algorithm 1.”
- Linear convergence of first order methods for non-strongly convex optimization (2015, background): “Algorithms based on gradient information have proved to be effective in these settings, such as projected gradient and its fast variants [3], stochastic gradient descent [4] or coordinate gradient descent [5].”
- Hessian-CoCoA : a general parallel and distributed framework for non-strongly convex regularizers (2017, background): “5 Coordinate Descent The growing interest towards Coordinate Descent (CD) algorithms (see [14]) is motivated by their competitive performance when applied to large scale machine learning problems.”
- Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, methodology): “Coordinate methods have been widely successful not just due to their faster convergence, but also because they are less resource intensive and provide faster update times [35].”
- Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization (2014, background): “which corresponds to the batch complexity Oe(1 +κ/n). For more general convex optimization problems, there is a vast literature on coordinate descent methods; see, e.g., the recent overview by Wright [47]. In particular, Nesterov’s work on randomized coordinate descent [27] sparked a lot of recent a”
- A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps (2016, neutral): “It is then natural to consider the coordinate descent algorithm (for an introduction and overview see Wright 2015): Algorithm 3.6.”
- Fast dynamic routing based on weighted kernel density estimation (2018, methodology): “Note that the proposed routing method maximizes f̂(v, r) by following a framework of coordinate descent [13].”