Abstract
The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. Existing works based on stability have studied nonconvex loss functions, but only considered the generalization error of the SGD in expectation. In this paper, we establish various generalization error bounds with probabilistic guarantee for the SGD. Specifically, for both general nonconvex loss functions and gradient dominant loss functions, we characterize the on-average stability of the iterates generated by SGD in terms of the on-average variance of the stochastic gradients. Such characterization leads to improved bounds for the generalization error for SGD. We then study the regularized risk minimization problem with strongly convex regularizers, and obtain improved generalization error bounds for proximal SGD. With strongly convex regularizers, we further establish the generalization error bounds for nonconvex loss functions under proximal SGD with high-probability guarantee, i.e., exponential concentration in probability.
Introduction
In machine learning, the "generalization gap"—the difference between a model's performance on training data versus unseen data—is a critical metric for evaluating algorithmic success. While algorithmic stability has long been used to bound this gap, traditional stability-based theories for Stochastic Gradient Descent (SGD) often suffer from being "data-blind." They typically fail to account for the underlying data distribution or the specific optimization path, making them unable to explain why deep networks can perfectly memorize random labels while failing to generalize to new data. This paper addresses these shortcomings by establishing new generalization error bounds with probabilistic guarantees for SGD in nonconvex settings.
Theoretical Framework: On-Average Stability
The core of this work is a novel analysis of on-average stability. Rather than focusing on worst-case changes in model output, the authors characterize stability through the optimization path of SGD.
Key Technical Components
- On-Average Variance: The analysis incorporates the variance of stochastic gradients ($\nu_S^2$) into the generalization bound. This metric captures the "noise" level of the optimization process relative to the specific dataset, providing a data-dependent measure of stability.
- Optimization Path Analysis: By tracking how iterates ($w_t$) diverge when the algorithm is run on datasets differing by only one sample, the authors provide a more granular view of stability.
- Gradient Dominance (PL Condition): The framework extends to functions satisfying the Polyak-Łojasiewicz condition, allowing for faster convergence and significantly tighter generalization bounds compared to general nonconvex cases.
- Proximal SGD and Regularization: For regularized problems, the authors show that strongly convex regularizers (like $L_2$ regularization) fundamentally stabilize the algorithm, shifting the generalization bound from a sub-linear decay to an exponential concentration in probability.
Experimental Validation
The authors validated their theoretical insights using three distinct setups: Logistic Regression on the a9a dataset, a three-layer ReLU neural network on MNIST, and a ResNet-18 architecture on CIFAR-10.
As illustrated in Figure 4, the measured on-average variance of SGD increases consistently as the fraction of random labels increases from 0 to 1. This empirical evidence supports the "Variance-Generalization Link": when labels are randomized, gradients become more erratic, the optimization path becomes less stable, and the generalization error increases. This successfully explains the "memorization" phenomenon observed in deep learning.
The Role of Regularization as a Stabilizer
A key finding of the research is that regularization does more than prevent large weights; it fundamentally improves the generalization bound. For regularized nonconvex problems, the authors proved that the generalization error does not have to grow with the number of iterations ($T$), effectively removing the $\log T$ dependence found in previous literature and achieving an $O(1/n)$ bound.
Figure 6 demonstrates this stabilizing effect. As the regularization weight increases, the generalization error (red) decreases significantly across both logistic regression and neural network models, even as training error (blue) increases. This highlights the trade-off between fitting the training data and maintaining the stability required for generalization.
Conclusion
This paper provides a robust theoretical framework for understanding SGD's generalization in nonconvex optimization. By linking generalization error to the on-average variance of stochastic gradients and providing high-probability guarantees, the authors bridge the gap between theoretical stability bounds and the practical behavior of deep learning models on structured and randomized data. Future work may explore these bounds under even more diverse geometric conditions of the objective function.
Summary updated