Parallel Coordinate Descent for L1-Regularized Loss Minimization

Abstract

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.

References in corpus (10)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al

Cited by in corpus (78)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Challenges of Big Data Analysis
• Distributed Coordinate Descent Method for Learning with Big Data
• Geotagging One Hundred Million Twitter Accounts with Total Variation Minimization
• Parallel Selective Algorithms for Big Data Optimization
• Communication-Efficient Distributed Dual Coordinate Ascent
• Optimization with First-Order Surrogate Functions
• Mini-Batch Primal and Dual Methods for SVMs
• Coordinate Friendly Structures, Algorithms and Applications
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
• A Primer on Coordinate Descent Algorithms
• Stochastic Dual Ascent for Solving Linear Systems
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• Feature Clustering for Accelerating Parallel Coordinate Descent
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Accelerated, Parallel and Proximal Coordinate Descent
• Distributed Mini-Batch SDCA
• Stochastic, Distributed and Federated Optimization for Machine Learning
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Randomized Block Coordinate Descent for Online and Stochastic Optimization
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• LOCO: Distributing Ridge Regression with Random Projections
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• Median Selection Subset Aggregation for Parallel Inference
• Scaling Up Coordinate Descent Algorithms for Large ${\ell }_1$ Regularization Problems
• Penalized Maximum Likelihood Estimation of Multi-layered Gaussian Graphical Models
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
• A distributed block coordinate descent method for training $l_1$ regularized linear classifiers
• Primitives for Dynamic Big Model Parallelism
• Block Coordinate Descent for Sparse NMF
• DimmWitted: A Study of Main-Memory Statistical Analytics
• Orchestrating the Development Lifecycle of Machine Learning-Based IoT Applications: A Taxonomy and Survey
• L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework
• Strategies and Principles of Distributed Machine Learning on Big Data
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Parallel coordinate descent methods for composite minimization: convergence analysis and error bounds
• Petuum: A New Platform for Distributed Machine Learning on Big Data
• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
• Asynchronous Stochastic Block Coordinate Descent with Variance Reduction
• On Data Dependence in Distributed Stochastic Optimization
• Flexible Parallel Algorithms for Big Data Optimization
• Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
• Distributed Stochastic Optimization of the Regularized Risk
• Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
• Fast, Accurate, and Scalable Method for Sparse Coupled Matrix-Tensor Factorization
• A machine-compiled macroevolutionary history of Phanerozoic life
• Analog Sparse Approximation with Applications to Compressed Sensing
• TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods
• Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
• ParMAC: distributed optimisation of nested functions, with application to learning binary autoencoders
• Stochastic Distributed Optimization for Machine Learning from Decentralized Features
• An Accelerated Communication-Efficient Primal-Dual Optimization Framework for Structured Machine Learning
• A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Accelerated Parallel Optimization Methods for Large Scale Machine Learning
• Revisiting Random Binning Features: Fast Convergence and Strong Parallelizability
• Separable Approximations and Decomposition Methods for the Augmented Lagrangian
• A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing
• Parallel Coordinate Descent Newton Method for Efficient ${\ell }_1$-Regularized Minimization
• Massively-Parallel Feature Selection for Big Data
• An Analysis of Asynchronous Stochastic Accelerated Coordinate Descent
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization
• Carathéodory Sampling for Stochastic Gradient Descent
• GPU-Accelerated Primal Learning for Extremely Fast Large-Scale Classification
• ${\ell }_1$ Adaptive Trend Filter via Fast Coordinate Descent
• Proximal SCOPE for Distributed Sparse Learning: Better Data Partition Implies Faster Convergence Rate
• A Parallel and Efficient Algorithm for Learning to Match
• Distributed Optimization via Adaptive Regularization for Large Problems with Separable Constraints
• An efficient parallel block coordinate descent algorithm for large-scale precision matrix estimation using graphics processing units
• An efficient projection neural network for ${\ell }_1$-regularized logistic regression
• A generic coordinate descent solver for nonsmooth convex optimization
• Structure-Aware Dynamic Scheduler for Parallel Machine Learning
• On the Performance and Convergence of Distributed Stream Processing via Approximate Fault Tolerance
• Data Dependent Convergence for Distributed Stochastic Optimization