Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity

Abstract

We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we call ALPHA. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. No coordinate descent methods capable to handle an arbitrary sampling have been studied in the literature before for this problem. ALPHA is a remarkably flexible algorithm: in special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent -- both in nonaccelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.

32 pages, 0 figures

References in corpus (13)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Parallel Coordinate Descent Methods for Big Data Optimization
• Stochastic Optimization with Importance Sampling
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• Accelerated, Parallel and Proximal Coordinate Descent
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Inexact Coordinate Descent: Complexity and Preconditioning
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• On the Complexity Analysis of Randomized Block-Coordinate Descent Methods
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• MixedGrad: An O(1/T) Convergence Rate Algorithm for Stochastic Smooth Optimization

Cited by in corpus (18)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Adding vs. Averaging in Distributed Primal-Dual Optimization
• Stochastic Dual Ascent for Solving Linear Systems
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Distributed Mini-Batch SDCA
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Importance Sampling for Minibatches
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Breaking Locality Accelerates Block Gauss-Seidel
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
• Linear convergence of SDCA in statistical estimation
• Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations
• Importance sampling strategy for non-convex randomized block-coordinate descent
• Accelerated Variance Reduced Block Coordinate Descent
• Faster Convergence of a Randomized Coordinate Descent Method for Linearly Constrained Optimization Problems