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

Alexandre Défossez, Francis R. Bach

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 $\gamma$, and a bias term that decays as $O(1/\gamma^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.

Introduction

Stochastic Gradient Descent (SGD) is the foundational algorithm for large-scale machine learning. While traditional convergence theory focuses on the asymptotic regime where error decays at a rate of $O(1/n)$, practitioners often observe that this regime is not reached quickly, particularly in high-dimensional settings. This paper addresses the gap between theoretical optimal rates and practical performance by investigating how step size and sampling distributions influence the two primary components of generalization error: bias and variance.

Analytical Framework: Averaged Least-Mean-Squares

The study focuses on Averaged Least-Mean-Squares (LMS), a variant of SGD for least-squares regression where a constant step size $\gamma$ is used and the final output is the average of all previous iterates. Unlike previous works that rely on upper bounds, this research derives a detailed asymptotic expansion of the error's covariance matrix. This granular approach allows for a precise decomposition of how the algorithm "forgets" its initial conditions (bias) and how it incorporates inherent data noise (variance).

Tighter Step-Size Bounds

A significant contribution of this work is the derivation of a new supremum for the step size, $\gamma_{max}$, required to ensure stability. The authors prove that for stochastic problems, this limit is strictly smaller than the deterministic limit. Specifically, stability is maintained as long as $\gamma < 2/Tr(H)$, where $Tr(H)$ is the trace of the Hessian (the sum of the eigenvalues of the data's second-order moment matrix).

The Bias-Variance Trade-off

The analysis reveals a critical split in the error decay rates:

  • Variance: Decays at a rate of $O(1/n)$, largely independent of the step size $\gamma$.
  • Bias: Decays at a rate of $O(1/\gamma^2 n^2)$.

While the bias term decays faster asymptotically, it is highly sensitive to the step size. If $\gamma$ is too small, the bias term can dominate the total error for a significant number of iterations, effectively slowing down the early stages of learning. This suggests that the "optimal" step size in practice must balance the need to reduce bias quickly without inducing instability in the variance.

Optimal Sampling Strategies

The paper explores how non-uniform sampling (importance sampling) can be leveraged to optimize these terms. The effectiveness of a sampling distribution $q$ depends entirely on which regime the algorithm is currently in:

  1. Variance-Dominated Regime: In the long-term limit, optimal sampling provides marginal gains (typically less than a factor of 2).
  2. Bias-Dominated Regime: In the early stages of training, optimal sampling is transformative. By sampling data points proportionally to their squared norm ($\|X\|^2$), practitioners can utilize much larger stable step sizes. This strategy can lead to performance improvements of 100x to 400x.

Interestingly, the authors note that this "bias-optimal" sampling strategy results in an update rule remarkably similar to Normalized Least Mean Squares (NLMS), providing a theoretical foundation for that algorithm's empirical success.

Empirical Validation

The theoretical findings were validated across synthetic and real-world datasets:

  • Synthetic Data: Used to observe the precise $1/n$ and $1/n^2$ decay slopes in a controlled environment.
  • Yahoo Dataset: A massive, unbalanced dataset for ad click prediction (millions of rows, 136 features). The results showed that resampling proportionally to $\|X\|^2$ allowed the algorithm to recover the large step sizes typically reserved for well-balanced data.
  • Sido Dataset: A high-dimensional binary classification dataset (12,678 points, 4,932 features) used to confirm the stability and acceleration benefits of the proposed sampling schemes.

Conclusion and Limitations

This research provides a rigorous justification for why bias often acts as the primary bottleneck in early iterations of SGD. While the analysis is currently limited to least-squares regression, it offers a roadmap for understanding smooth losses like logistic regression.

One practical limitation is that variance-optimal sampling requires prior knowledge of the noise $\epsilon$ and the Hessian $H$, which is often unavailable. However, bias-optimal sampling only requires the norm of the input vector $X$, making it a highly practical and implementable strategy for accelerating stochastic approximation in real-world streaming applications.

Summary updated

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 $\gamma$, and a bias term that decays as O(1/$\gamma$ 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.
BibTeX
@inproceedings{defossez2015constant,
  author = {Alexandre Défossez and Francis R. Bach},
  title = {{Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions}},
  booktitle = {HAL},
  year = {2015},
}
Figure