Parallel Coordinate Descent Methods for Big Data Optimization

Abstract

In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed to approximately solve the problem with high probability, is a simple expression depending on the number of parallel processors and a natural and easily computable measure of separability of the smooth component of the objective function. In the worst case, when no degree of separability is present, there may be no speedup; in the best case, when the problem is separable, the speedup is equal to the number of processors. Our analysis also works in the mode when the number of blocks being updated at each iteration is random, which allows for modeling situations with busy or unreliable processors. We show that our algorithm is able to solve a LASSO problem involving a matrix with 20 billion nonzeros in 2 hours on a large memory node with 24 cores.

43 pages, 8 tables, 6 figures

References in corpus (5)

• Distributed Coordinate Descent Method for Learning with Big Data
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Inexact Coordinate Descent: Complexity and Preconditioning
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (35)

• Geotagging One Hundred Million Twitter Accounts with Total Variation Minimization
• Parallel Selective Algorithms for Big Data Optimization
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Communication-Efficient Distributed Dual Coordinate Ascent
• Mini-Batch Primal and Dual Methods for SVMs
• Hybrid Random/Deterministic Parallel Algorithms for Nonconvex Big Data Optimization
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• An Asynchronous Parallel Randomized Kaczmarz Algorithm
• Accelerated, Parallel and Proximal Coordinate Descent
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Distributed Mini-Batch SDCA
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Inexact Coordinate Descent: Complexity and Preconditioning
• Least Squares Revisited: Scalable Approaches for Multi-class Prediction
• A Second-Order Method for Strongly Convex L1-Regularization Problems
• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
• A distributed block coordinate descent method for training $l_1$ regularized linear classifiers
• Parallel coordinate descent for the Adaboost problem
• Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Petuum: A New Platform for Distributed Machine Learning on Big Data
• Flexible Parallel Algorithms for Big Data Optimization
• Robust Block Coordinate Descent
• Convex Optimization for Parallel Energy Minimization
• Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
• An efficient distributed learning algorithm based on effective local functional approximations
• Greedy Block Coordinate Descent (GBCD) Method for High Dimensional Quadratic Programs
• Coordinate Descent Algorithms
• Accelerated Parallel Optimization Methods for Large Scale Machine Learning
• Separable Approximations and Decomposition Methods for the Augmented Lagrangian
• Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
• Optimal diagnostic tests for sporadic Creutzfeldt-Jakob disease based on support vector machine classification of RT-QuIC data