HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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 - ENS 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.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

Contributor : Francis Bach Connect in order to contact the contributor
Submitted on : Sunday, November 9, 2014 - 9:21:06 PM
Last modification on : Thursday, March 17, 2022 - 10:08:44 AM
Long-term archiving on: : Monday, February 16, 2015 - 4:20:37 PM


Files produced by the author(s)


Public Domain


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



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. ⟨hal-01081578⟩



Record views


Files downloads