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 de l'École normale supérieure, 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

https://hal.inria.fr/hal-01081578
Contributor : Francis Bach <>
Submitted on : Sunday, November 9, 2014 - 9:21:06 PM
Last modification on : Friday, February 12, 2021 - 9:22:04 AM
Long-term archiving on: : Monday, February 16, 2015 - 4:20:37 PM

Files

paper.pdf
Files produced by the author(s)

Licence


Public Domain

Identifiers

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

Share

Metrics

Record views

406

Files downloads

301