A Generic Acceleration Framework for Stochastic Composite Optimization
arXiv:1906.01164
Abstract
In this paper, we introduce various mechanisms to obtain accelerated first-order stochastic optimization algorithms when the objective function is convex or strongly convex. Specifically, we extend the Catalyst approach originally designed for deterministic objectives to the stochastic setting. Given an optimization method with mild convergence guarantees for strongly convex problems, the challenge is to accelerate convergence to a noise-dominated region, and then achieve convergence with an optimal worst-case complexity depending on the noise variance of the gradients. A side contribution of our work is also a generic analysis that can handle inexact proximal operators, providing new insights about the robustness of stochastic algorithms when the proximal operator cannot be exactly computed.
References in corpus (16)
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- A Universal Catalyst for First-Order Optimization
- SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
- Primal-dual subgradient methods for minimizing uniformly convex functions
- On Acceleration with Noise-Corrupted Gradients
- Direct Acceleration of SAGA using Sampled Negative Momentum
- Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
- Catalyst Acceleration for Gradient-Based Non-Convex Optimization
- Altitude Training: Strong Bounds for Single-Layer Dropout
- A Universally Optimal Multistage Accelerated Stochastic Gradient Method
- Nonlinear Acceleration of Stochastic Algorithms
- Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
Cited by in corpus (4)
- The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
- Recent theoretical advances in decentralized distributed convex optimization
- From low probability to high confidence in stochastic convex optimization
- Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression