Accelerated, Parallel and Proximal Coordinate Descent

Abstract

We propose a new stochastic coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel and PROXimal; this is the first time such a method is proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate $2\bar{\omega }\bar{L}{R}^2/(k+1{)}^2$, where $k$ is the iteration counter, $\bar{\omega }$ is an average degree of separability of the loss function, $\bar{L}$ is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and $R$ is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of existing accelerated coordinate descent methods. The fact that the method depends on the average degree of separability, and not on the maximum degree of separability, can be attributed to the use of new safe large stepsizes, leading to improved expected separable overapproximation (ESO). These are of independent interest and can be utilized in all existing parallel stochastic coordinate descent algorithms based on the concept of ESO.

25 pages, 2 algorithms, 6 tables, 3 figures

References in corpus (1)

• Parallel Coordinate Descent for L1-Regularized Loss Minimization

Cited by in corpus (22)

• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Kalman-based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Distributed Mini-Batch SDCA
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Block-proximal methods with spatially adapted acceleration
• Strategies and Principles of Distributed Machine Learning on Big Data
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Robust Block Coordinate Descent
• Faster Parallel Solver for Positive Linear Programs via Dynamically-Bucketed Selective Coordinate Descent
• Coordinate Descent Algorithms
• Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations
• Accelerated Parallel Optimization Methods for Large Scale Machine Learning
• A stochastic coordinate descent primal-dual algorithm with dynamic stepsize for large-scale composite optimization
• A stochastic coordinate descent inertial primal-dual algorithm for large-scale composite optimization
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
• An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming
• A stochastic coordinate descent splitting primal-dual fixed point algorithm and applications to large-scale composite optimization