One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods

Abstract

We propose a remarkably general variance-reduced method suitable for solving regularized empirical risk minimization problems with either a large number of training examples, or a large model dimension, or both. In special cases, our method reduces to several known and previously thought to be unrelated methods, such as {\tt SAGA}, {\tt LSVRG}, {\tt JacSketch}, {\tt SEGA} and {\tt ISEGA}, and their arbitrary sampling and proximal generalizations. However, we also highlight a large number of new specific algorithms with interesting properties. We provide a single theorem establishing linear convergence of the method under smoothness and quasi strong convexity assumptions. With this theorem we recover best-known and sometimes improved rates for known methods arising in special cases. As a by-product, we provide the first unified method and theory for stochastic gradient and stochastic coordinate descent type methods.

arXiv comment61 pages, 6 figures, 3 tables

References in corpus (11)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Optimization with First-Order Surrogate Functions
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• SEGA: Variance Reduction via Gradient Sketching
• SGD: General Analysis and Improved Rates
• Direct Acceleration of SAGA using Sampled Negative Momentum
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Optimal mini-batch and step sizes for SAGA
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
• SAGA with Arbitrary Sampling

Cited by in corpus (9)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Federated Learning of a Mixture of Global and Local Models
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Local SGD: Unified Theory and New Efficient Methods
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters