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 (4)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction

Cited by in corpus (6)

• Adding vs. Averaging in Distributed Primal-Dual Optimization
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Importance sampling strategy for non-convex randomized block-coordinate descent
• Accelerated Variance Reduced Block Coordinate Descent