Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions

Alexandre Défossez 1, 2 Francis Bach 1, 2
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider the least-squares regression problem and provide a detailed asymptotic analysis of the performance of averaged constant-step-size stochastic gradient descent (a.k.a. least-mean-squares). In the strongly-convex case, we provide an asymptotic expansion up to explicit exponentially decaying terms. Our analysis leads to new insights into stochastic approximation algorithms: (a) it gives a tighter bound on the allowed step-size; (b) the generalization error may be divided into a variance term which is decaying as O(1/n), independently of the step-size γ, and a bias term that decays as O(1/γ 2 n 2); (c) when allowing non-uniform sampling, the choice of a good sampling density depends on whether the variance or bias terms dominate. In particular, when the variance term dominates, optimal sampling densities do not lead to much gain, while when the bias term dominates, we can choose larger step-sizes that leads to significant improvements.
Type de document :
Communication dans un congrès
International Conference on Artificial Intelligence and Statistics (AISTATS),, 2015, San Diego, United States. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2015
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01081578
Contributeur : Francis Bach <>
Soumis le : dimanche 9 novembre 2014 - 21:21:06
Dernière modification le : jeudi 11 janvier 2018 - 06:23:26
Document(s) archivé(s) le : lundi 16 février 2015 - 16:20:37

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Domaine public

Identifiants

  • HAL Id : hal-01081578, version 1
  • ARXIV : 1412.0156

Collections

Citation

Alexandre Défossez, Francis Bach. Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions. International Conference on Artificial Intelligence and Statistics (AISTATS),, 2015, San Diego, United States. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2015. 〈hal-01081578〉

Partager

Métriques

Consultations de la notice

201

Téléchargements de fichiers

269