# Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure

1 Thoth - Apprentissage de modèles à partir de données massives
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann
Abstract : Stochastic optimization algorithms with variance reduction have proven successful for minimizing large finite sums of functions. Unfortunately, these techniques are unable to deal with stochastic perturbations of input data, induced for example by data augmentation. In such cases, the objective is no longer a finite sum, and the main candidate for optimization is the stochastic gradient descent method (SGD). In this paper, we introduce a variance reduction approach for these settings when the objective is strongly convex. After an initial linearly convergent phase, the algorithm achieves a $O(1/t)$ convergence rate in expectation like SGD, but with a constant factor that is typically much smaller, depending on the variance of gradient estimates due to perturbations on a single example. We also introduce extensions of the algorithm to composite objectives and non-uniform sampling.
Type de document :
Pré-publication, Document de travail
2017
Domaine :

Littérature citée [31 références]

https://hal.inria.fr/hal-01375816
Contributeur : Alberto Bietti <>
Soumis le : lundi 27 février 2017 - 14:21:42
Dernière modification le : lundi 9 avril 2018 - 12:22:50
Document(s) archivé(s) le : dimanche 28 mai 2017 - 13:05:51

### Fichiers

stoch-miso.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01375816, version 4
• ARXIV : 1610.00970

### Citation

Alberto Bietti, Julien Mairal. Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure. 2017. 〈hal-01375816v4〉

### Métriques

Consultations de la notice

## 673

Téléchargements de fichiers