Randomized Dual Coordinate Ascent with Arbitrary Sampling

Abstract

We study the problem of minimizing the average of a large number of smooth convex functions penalized with a strongly convex regularizer. We propose and analyze a novel primal-dual method (Quartz) which at every iteration samples and updates a random subset of the dual variables, chosen according to an arbitrary distribution. In contrast to typical analysis, we directly bound the decrease of the primal-dual error (in expectation), without the need to first analyze the dual error. Depending on the choice of the sampling, we obtain efficient serial, parallel and distributed variants of the method. In the serial case, our bounds match the best known bounds for SDCA (both with uniform and importance sampling). With standard mini-batching, our bounds predict initial data-independent speedup as well as additional data-driven speedup which depends on spectral and sparsity properties of the data. We calculate theoretical speedup factors and find that they are excellent predictors of actual speedup in practice. Moreover, we illustrate that it is possible to design an efficient mini-batch importance sampling. The distributed variant of Quartz is the first distributed SDCA-like method with an analysis for non-separable data.

References in corpus (13)

• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Proximal Stochastic Dual Coordinate Ascent
• Parallel Coordinate Descent Methods for Big Data Optimization
• Stochastic Optimization with Importance Sampling
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Smooth minimization of nonsmooth functions with parallel coordinate descent methods
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Accelerated, Parallel and Proximal Coordinate Descent
• Inexact Coordinate Descent: Complexity and Preconditioning
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• Analysis of Distributed Stochastic Dual Coordinate Ascent

Cited by in corpus (22)

• 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
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Block-proximal methods with spatially adapted acceleration
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
• Stochastic gradient methods with inexact oracle
• Primal-Dual Rates and Certificates
• Breaking Locality Accelerates Block Gauss-Seidel
• Faster Learning by Reduction of Data Access Time
• About accelerated randomized methods
• Parallel Stochastic Newton Method
• Efficient numerical algorithms for regularized regression problem with applications to traffic matrix estimations
• Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks
• Reducing Runtime by Recycling Samples
• Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity
• Non accelerated efficient numerical methods for sparse quadratic optimization problems and its generalizations