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

arXiv: https://arxiv.org/abs/1901.08788 · HTML: https://mlsanity.com/paper/1901.08788/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2019.

## Built on by (most cited first, 9 of 9)

- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization](https://mlsanity.com/paper/2102.07148/) (2021)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Stochastic Optimization under Distributional Drift](https://mlsanity.com/paper/2108.07356/) (2021)
- [Demystifying SGD with Doubly Stochastic Gradients](https://mlsanity.com/paper/2406.00920/) (2024)
- [Beyond Tikhonov: Faster Learning with Self-Concordant Losses via Iterative Regularization](https://mlsanity.com/paper/2106.08855/) (2021)
- [Push--Pull with Device Sampling](https://mlsanity.com/paper/2206.04113/) (2022)
- [Unified analysis of SGD-type methods](https://mlsanity.com/paper/2303.16502/) (2023)

## Abstract (arXiv)

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.