Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise

Abstract

In this paper, we propose a unified view of gradient-based algorithms for stochastic convex composite optimization by extending the concept of estimate sequence introduced by Nesterov. More precisely, we interpret a large class of stochastic optimization methods as procedures that iteratively minimize a surrogate of the objective, which covers the stochastic gradient descent method and variants of the incremental approaches SAGA, SVRG, and MISO/Finito/SDCA. This point of view has several advantages: (i) we provide a simple generic proof of convergence for all of the aforementioned methods; (ii) we naturally obtain new algorithms with the same guarantees; (iii) we derive generic strategies to make these algorithms robust to stochastic noise, which is useful when data is corrupted by small random perturbations. Finally, we propose a new accelerated stochastic gradient descent algorithm and an accelerated SVRG algorithm with optimal complexity that is robust to stochastic noise.

Journal of Machine Learning Research, Microtome Publishing, In press

References in corpus (8)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
• On Acceleration with Noise-Corrupted Gradients
• Direct Acceleration of SAGA using Sampled Negative Momentum
• Estimate Sequences for Variance-Reduced Stochastic Composite Optimization
• Cyanure: An Open-Source Toolbox for Empirical Risk Minimization for Python, C++, and soon more

Cited by in corpus (8)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• A unified variance-reduced accelerated gradient method for convex optimization
• Recent theoretical advances in decentralized distributed convex optimization
• A Generic Acceleration Framework for Stochastic Composite Optimization
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• From low probability to high confidence in stochastic convex optimization
• Cyanure: An Open-Source Toolbox for Empirical Risk Minimization for Python, C++, and soon more
• StoMADS: Stochastic blackbox optimization using probabilistic estimates