Parallel Coordinate Descent for L1-Regularized Loss Minimization

By Joseph K. Bradley, Aapo Kyrola, Danny Bickson, Carlos Guestrin. 2011

311 citations recorded by the source corpus.

We propose Shotgun, a parallel coordinate descent algorithm for minimizing L1-regularized losses. Though coordinate descent seems inherently sequential, we prove convergence bounds for Shotgun which predict linear speedups, up to a problem-dependent limit. We present a comprehensive empirical study of Shotgun for Lasso and sparse logistic regression. Our theoretical predictions on the potential for parallelism closely match behavior on real data. Shotgun outperforms other published solvers on a range of large problems, proving to be one of the most scalable algorithms for L1.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, 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

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “Our framework reduces to Shotgun as a special case when the internal solver is a single-coordinate update on the subproblem (10), γ = 1 , and for a suitable σ (cid:48) .”
Distributed Coordinate Descent Method for Learning with Big Data (2013, methodology): “For instance, in the case of the three losses ` in Table 1, assumption (2) holds with M = ATA for SL and HL, and M = 1 4A TA for LL (Bradley et al., 2011).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Numerous follow-up works extended the concept to proximal setting [79], single processor parallelism [15, 80] and develop efficiently implementable acceleration [51].”
TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning (2017, methodology): “Researches such as sparse logistic regression and Lasso optimization problems [4][12][26] took advantage of the sparsity inherent in models and achieved”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, methodology): “First, we note that there is a clear correlation between the wall-time spent processing each dataset and the number of vectors communicated, indicating that communication has a significant effect on convergence speed.”
More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server (2013, methodology): “Note that SSP is not limited to stochastic gradient matrix algorithms: it can also be applied to parallel collapsed sampling on topic models [2] (by storing the word-topic and document-topic tables in x), parallel coordinate descent on Lasso regression [5] (by storing the regression coefficients β i”
Mini-Batch Primal and Dual Methods for SVMs (2013, methodology): “Bradley et al. (2011) presented and analyzed SHOTGUN, a parallel coordinate descent method for l1regularized problems, showing linear speedups for mini-batch sizes bounded in terms of the spectral norm of the data.”
Coordinate descent algorithms (2015, background): “[9] consider a bound-constrained problem that is a reformulation of the problem (2) with specific choices of f and with Ω(x) = ‖x‖1.”
Petuum: A New Platform for Distributed Machine Learning on Big Data (2013, methodology): “, DML implemented on single machine, and Shotgun [10]); (2) Petuum ML implementations can run faster than other programmable platforms (e.”
Fast distributed coordinate descent for non-strongly convex losses (2014, background): “For examples of regularizersR and loss functions f satisfying the above assumptions, relevant to machine learning applications, we refer the reader to [1, 2, 3].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Numerous follow-up works extended the concept to proximal setting [148], single processor parallelism [24, 151] and develop efficiently implementable acceleration [96].”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, background): “Paper Proximal Parallel Accelerated Notable feature Leventhal & Lewis, 2008 [5] × × × quadratic f S-Shwartz & Tewari, 2009 [18] `1 × × 1st `1-regularized Nesterov, 2010 [12] × × YES 1st block, 1st accelerated Richtárik & Takáč, 2011 [17] YES × × 1st general proximal Bradley et al, 2012 [2] `1 YES × ”
Parallel coordinate descent methods for big data optimization (2012, methodology): “Lastly, the theoretical speedups obtained in [1], when compared to the serial CDM method, depend on a quantity that is hard to compute in big data settings (it involves the computation of an eigenvalue of a huge-scale matrix).”
Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling (2015, methodology): “These methods were then generalized to the τ -nice sampling in SHOTGUN [2], further generalized to arbitrary uniform samplings in PCDM [23], SPCDM [7], APPROX [6] (which is an accelerated method) and to arbitrary (even nonuniform) samplings in NSync [22].”
A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing (2014, methodology): “The Shotgun algorithm proposed by [4] is among the ﬁrst to parallelize coordinate descent for Lasso.”
Distributed Mini-Batch SDCA (2015, methodology): “In this Section we will make use of the Expected Separable Overapproximation (ESO) theory introduced in [20] and further extended e.g. in [16, 19, 18].”