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. 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 of examples over a dataset, the choice of a good sampling density depends on the trade-off between bias and variance: 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 lead to significant improvements.
Introduction
In large-scale machine learning, Stochastic Gradient Descent (SGD) is a cornerstone due to its computational efficiency. To enhance performance, practitioners often employ "averaging" (Polyak-Ruppert averaging), which theoretically achieves an optimal convergence rate of $O(1/n)$. However, a gap persists between theoretical guarantees and practical performance, especially in high-dimensional settings. This paper bridges this gap by providing a refined asymptotic analysis of Averaged Least-Mean-Squares (LMS) with a constant step size.
The Bias-Variance Decomposition
A central contribution of this work is the explicit decomposition of the generalization error into two distinct components: bias and variance.
- Bias: This term represents the error stemming from the initial starting point. The analysis reveals that bias decays at a rate of $O(1/\gamma^2 n^2)$, where $\gamma$ is the step size. Notably, the quadratic dependence on the step size suggests that larger steps can drastically accelerate the "forgetting" of the initial state.
- Variance: This term accounts for the noise inherent in the data. It decays at a rate of $O(1/n)$, independent of the step size $\gamma$.
As shown in Figure 5, the optimization process typically transitions from a bias-dominated regime (steep decline) to a variance-dominated regime (shallower decline). Understanding this transition is crucial for selecting optimal hyperparameters.
Optimal Sampling and Step-Size Stability
Beyond the decomposition, the authors derive a tighter bound for the maximum allowable step size ($\gamma_{max}$) based on the fourth-order moments of the data. This provides a more precise "speed limit" for the algorithm, preventing divergence in high-dimensional or ill-conditioned scenarios.
Perhaps the most impactful insight concerns importance sampling. While traditional importance sampling aims to reduce the variance term—often yielding only marginal gains—the authors propose sampling proportionally to the squared norm of the input ($X^T X$). This strategy stabilizes the algorithm, allowing for significantly larger step sizes. Because the bias term is inversely proportional to $\gamma^2$, a ten-fold increase in the step size can lead to a hundred-fold reduction in bias-related error.
Experimental Results
The theoretical findings were validated on both synthetic and real-world datasets, including the Yahoo ad-click prediction dataset and the Sido binary classification benchmark.
On the highly unbalanced Yahoo dataset (Figure 1), the "optimal for bias" sampling enabled step sizes up to 20 times larger than uniform sampling. This resulted in error reductions of two orders of magnitude during the initial training phase, demonstrating the practical utility of the proposed sampling distributions.
Conclusion
This work provides a nuanced understanding of ASGD for least-squares regression. By identifying the distinct decay rates of bias and variance, the authors show that the primary benefit of non-uniform sampling lies in its ability to support larger step sizes, thereby rapidly eliminating initial bias. For practitioners, the message is clear: if your model is slow to converge from its initialization, consider a sampling distribution that allows for a bolder step size rather than focusing solely on variance reduction.
Summary updated