Estimate Sequences for Variance-Reduced Stochastic Composite Optimization

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. This point of view covers the stochastic gradient descent method, variants of the approaches SAGA, SVRG, and has several advantages: (i) we provide a generic proof of convergence for the aforementioned methods; (ii) we show that this SVRG variant is adaptive to strong convexity; (iii) we naturally obtain new algorithms with the same guarantees; (iv) 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 show that this viewpoint is useful to obtain new accelerated algorithms in the sense of Nesterov.

short version of preprint arXiv:1901.08788

Cited by in corpus (12)

• Recent theoretical advances in decentralized distributed convex optimization
• 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
• On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
• Towards closing the gap between the theory and practice of SVRG
• Adaptive Step Sizes in Variance Reduction via Regularization
• On the Convergence of SARAH and Beyond
• How Does Momentum Help Frank Wolfe?
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization
• Parallel and Distributed algorithms for ML problems
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters