Abstract
The classical statistical learning theory implies that fitting too many parameters leads to overfitting and poor performance. That modern deep neural networks generalize well despite a large number of parameters contradicts this finding and constitutes a major unsolved problem towards explaining the success of deep learning. While previous work focuses on the implicit regularization induced by stochastic gradient descent (SGD), we study here how the local geometry of the energy landscape around local minima affects the statistical properties of SGD with Gaussian gradient noise. We argue that under reasonable assumptions, the local geometry forces SGD to stay close to a low dimensional subspace and that this induces another form of implicit regularization and results in tighter bounds on the generalization error for deep neural networks. To derive generalization error bounds for neural networks, we first introduce a notion of stagnation sets around the local minima and impose a local essential convexity property of the population risk. Under these conditions, lower bounds for SGD to remain in these stagnation sets are derived. If stagnation occurs, we derive a bound on the generalization error of deep neural networks involving the spectral norms of the weight matrices but not the number of network parameters. Technically, our proofs are based on controlling the change of parameter values in the SGD iterates and local uniform convergence of the empirical loss functions based on the entropy of suitable neighborhoods around local minima.
Introduction
A central paradox in modern deep learning is the "generalization puzzle": why do models with millions of parameters generalize effectively instead of overfitting to training noise? Classical statistical learning theory suggests that models with more parameters than data points should suffer from poor out-of-sample performance. However, deep neural networks (DNNs) frequently operate in the overparameterized regime while maintaining high accuracy.
While existing literature often credits the implicit regularization of the Stochastic Gradient Descent (SGD) optimizer, this work proposes that the shape of the loss surface itself is a critical factor. The authors argue that the local geometry of the energy landscape acts as a filter, trapping SGD in low-dimensional "stagnation sets" around local minima. This restriction effectively reduces the model's complexity, leading to generalization bounds that are independent of the total parameter count.
Theoretical Framework
The authors develop a mathematical framework to analyze SGD with Gaussian noise, focusing on the interaction between the optimizer and the loss landscape geometry.
Stagnation Sets and Local Geometry
The core of the theory relies on the concept of stagnation sets—neighborhoods around the local minima of the population risk. Once the optimization process enters these regions, the local geometry makes it highly probable that the iterates will remain within a small radius as the learning rate decays.
To formalize this, the authors introduce Local Essential Convexity. Unlike global convexity, which is absent in DNN loss surfaces, this property assumes the surface is convex along paths between a parameter point and its projection onto the set of local minima.
Metric Entropy Analysis
By calculating the "covering numbers" (metric entropy) of these stagnation sets, the authors bound the generalization gap. This approach measures the effective complexity of the regions where SGD actually spends its time, rather than the complexity of the entire high-dimensional parameter space.
Key Results
The theoretical analysis yields two primary results:
- Stagnation Probability (Theorem 4): The probability of SGD remaining within a "good" neighborhood increases toward 1 as training time $T$ grows and the learning rate is appropriately scheduled.
- Parameter-Independent Generalization Bound (Theorem 6): The derived bound for the generalization gap is: $$\text{Gap} \lesssim \frac{\sqrt{d \log K} + SL\delta \log^{1/2}(\bar{h})}{\sqrt{n}}$$ Notably, the total number of parameters $D$ is absent from the numerator. Instead, the bound depends on the dimension of the minima set ($d$), the number of minima ($K$), the product of spectral norms ($S$), the network depth ($L$), and the neighborhood radius ($\delta$).
Empirical simulations on synthetic regression tasks validate these findings, showing that the generalization gap saturates as parameter count increases but scales linearly with the neighborhood radius $\delta$.
Discussion and Limitations
While providing a novel perspective on generalization, several challenges remain. The theory assumes Gaussian gradient noise, which may not fully capture the "heavy-tailed" nature of real-world minibatch noise. Furthermore, verifying "Local Essential Convexity" for complex architectures like Transformers or ResNets is an open problem. Finally, while this work explains behavior after reaching a stagnation set, the "global search" phase—how SGD finds these high-quality minima initially—requires further investigation.
Summary updated