Fast distributed coordinate descent for non-strongly convex losses

By Olivier Fercoq, Zheng Qu, Peter Richtárik, Martin Takác. 2014

59 citations recorded by the source corpus.

We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal O(1/k2) convergence rate, where k is the iteration counter. The core of the work is the theoretical study of stepsize parameters. We have implemented the method on Archer - the largest super-computer in the UK-and show that the method is capable of solving a (synthetic) LASSO optimization problem with 50 billion variables.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

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

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, background): “Works including [2, 8, 3, 9] have established basic theoretical results and developed distributed versions of existing methods, but as this is a relatively new area, many open questions remain.”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “In the convex setting, the problem of distributed optimization and estimation has received significant attention [4, 15, 33], and some algorithms do focus specifically on communication efficiency [45, 34, 40, 27, 43].”
LoAdaBoost: Loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data (2018, methodology): “[5] designed an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions and demonstrated that their method was extendable to a LASSO optimization problem with 50 billion variables.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The first distributed versions of Coordinate Descent algorithms were the Hydra and its accelerated variant, Hydra2, [81, 34], which has been demonstrated to be very efficient on large sparse problems implemented on a computing cluster.”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, background): “For an overview over this currently active research field, we refer the reader to (Balcan et al., 2012; Richtárik & Takáč, 2013; Duchi et al., 2013; Yang, 2013; Liu & Wright, 2014; Fercoq et al., 2014; Jaggi et al., 2014; Shamir & Srebro, 2014; Shamir et al., 2014; Zhang & Lin, 2015; Qu & Richtárik,”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, background): “For sparse data, the work of [20, 21] gives some data dependent choices of βb which are safe.”
Distributed optimization with arbitrary local solvers (2015, background): “…with the massive growth of available datasets, major roadblocks still persist in the distributed setting, where data no longer ﬁts in the memory of a single computer, and computation must be split across multiple machines in a network [3, 7, 12, 18, 22, 28, 32, 34, 37, 46, 50, 58, 60, 62, 76].”
Coordinate descent algorithms (2015, methodology): “This scheme is enhanced with an acceleration step in [15]; the extra computations associated with the acceleration step too are parallelized, using ideas from [23].”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “Two classes of methods address this issue – randomized coordinate descent methods [4], [5], [6] , [7], [8], [9], [10], [11], [12], [13] and stochastic gradien t methods [14], [15], [16], [17], [18].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “The first distributed versions of Coordinate Descent algorithms were the Hydra and its accelerated variant, Hydra(2), [149, 57], which has been demonstrated to be very efficient on large sparse problems implemented on a computing cluster.”
Semi-stochastic coordinate descent (2014, neutral): “Also, efficient accelerated variants with O(1/ √ ) rate were developed [2,4], capable of solving problems with 50 billion variables.”
Stochastic Dual Coordinate Ascent with Adaptive Probabilities (2015, unknown): “Recent advances on mini-batch and distributed variants can be found in (Liu & Wright, 2014), (Zhao et al., 2014b), (Richtárik & Takáč, 2013a), (Fercoq et al., 2014), (Trofimov & Genkin, 2014), (Jaggi et al., 2014), (Mareček et al., 2014) and (Mahajan et al., 2014).”
Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems (2018, background): “primal-dual structure of the problem and [10, 13, 22] which work in the primal alone.”
Efficient Distributed Online Prediction and Stochastic Optimization With Approximate Distributed Averaging (2014, methodology): “Even faster rates (both in theory, and with practical algorithms) have been achieved, using a master-worker architecture, by applying a stochastic coordinate ascent approach [10] to the dual problem under the assumption that the individual loss terms are strongly convex [12], [17].”
Understanding and Controlling User Linkability in Decentralized Learning (2018, background): “3 Decentralized Data Scenarios Distributed learning algorithms [15, 20, 42, 45, 58, 65, 76] typically assume data among the clients are (a) independent and identically distributed (IID) and (b) balanced, as can be seen in Figure 1a.”
Federated Learning of Deep Networks using Model Averaging (2016, background): “In the convex setting, the problem of distributed optimization and estimation has received significant attention (Balcan et al., 2012; Fercoq et al., 2014; Shamir & Srebro, 2014), and some algorithms do focus specifically on communication efficiency (Zhang et al.”
Distributed Mini-Batch SDCA (2015, methodology): “…at each iteration, on each of theC machines,b/C dual variables are selected (as in our distributed sampling), andH iterations of SDCA are performed sequentially on theseb/C points (in parallel on each of theC machines, and while considering all other dual variables, including all variables on…”