Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Andrei Kulunchakov 1 Julien Mairal 1
1 Thoth - Apprentissage de modèles à partir de données massives
LJK - Laboratoire Jean Kuntzmann, Inria Grenoble - Rhône-Alpes
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.
Complete list of metadatas

https://hal.inria.fr/hal-01993531
Contributor : Julien Mairal <>
Submitted on : Monday, April 27, 2020 - 10:08:50 PM
Last modification on : Friday, May 15, 2020 - 11:24:28 AM

Files

lower_bound.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01993531, version 3
  • ARXIV : 1901.08788

Collections

Citation

Andrei Kulunchakov, Julien Mairal. Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise. 2020. ⟨hal-01993531v3⟩

Share

Metrics

Record views

26

Files downloads

259