On Optimal Probabilities in Stochastic Coordinate Descent Methods
arXiv:1310.3438
Abstract
We propose and analyze a new parallel coordinate descent method---`NSync---in which at each iteration a random subset of coordinates is updated, in parallel, allowing for the subsets to be chosen non-uniformly. We derive convergence rates under a strong convexity assumption, and comment on how to assign probabilities to the sets to optimize the bound. The complexity and practical performance of the method can outperform its uniform variant by an order of magnitude. Surprisingly, the strategy of updating a single randomly selected coordinate per iteration---with optimal probabilities---may require less iterations, both in theory and practice, than the strategy of updating all coordinates at every iteration.
5 pages, 1 algorithm (`NSync), 2 theorems, 2 figures
References in corpus (9)
- Parallel Coordinate Descent for L1-Regularized Loss Minimization
- Distributed Coordinate Descent Method for Learning with Big Data
- Proximal Stochastic Dual Coordinate Ascent
- Smooth minimization of nonsmooth functions with parallel coordinate descent methods
- Inexact Coordinate Descent: Complexity and Preconditioning
- On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
- Parallel coordinate descent for the Adaboost problem
- A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming
- Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
Cited by in corpus (14)
- Not All Samples Are Created Equal: Deep Learning with Importance Sampling
- Parallel Coordinate Descent Methods for Big Data Optimization
- Adding vs. Averaging in Distributed Primal-Dual Optimization
- Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
- Randomized Dual Coordinate Ascent with Arbitrary Sampling
- Accelerated, Parallel and Proximal Coordinate Descent
- Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
- Stochastic Dual Coordinate Ascent with Adaptive Probabilities
- Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
- Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
- SGD with Coordinate Sampling: Theory and Practice
- Coordinate Descent with Online Adaptation of Coordinate Frequencies
- A generic coordinate descent solver for nonsmooth convex optimization
- Faster Convergence of a Randomized Coordinate Descent Method for Linearly Constrained Optimization Problems