On generalization bounds for deep networks based on loss surface implicit regularization

Masaaki Imaizumi, Johannes Schmidt-Hieber

Abstract

Deep neural networks often possess far more parameters than training examples, yet they generalize remarkably well—a phenomenon known as the "overparameterization paradox." This paper proposes a theoretical framework to resolve this mystery through the lens of loss surface geometry. The authors argue that "stagnation sets" around local minima act as a form of implicit regularization, forcing Stochastic Gradient Descent (SGD) to remain within low-dimensional regions of the parameter space. By deriving generalization bounds based on the complexity of these sets rather than the total parameter count, the study provides a more accurate theoretical account of deep learning performance.

Introduction: The Overparameterization Paradox

Classical statistical learning theory suggests that models with millions of parameters should overfit training data, leading to poor generalization. However, empirical evidence shows that deep networks often improve in performance as they grow larger. While previous work has focused on the implicit bias of optimizers toward minimum-norm solutions, this research investigates how the physical geometry of the loss landscape itself constrains the learning process. The authors hypothesize that the optimizer becomes "trapped" in specific regions near minima, effectively reducing the functional complexity of the model.

Methodology: Stagnation and Local Convexity

The authors model the optimization process using Gaussian SGD, a continuous-time approximation of standard minibatch SGD. Central to their theory is the concept of stagnation sets—neighborhoods around the local minima of the population risk where the optimizer is likely to reside during the later stages of training.

To analyze these sets, the paper introduces Local Essential Convexity. Unlike standard convexity, which is rarely found in neural networks, this relaxed assumption requires the loss surface to be convex only along the path between a parameter point and its projection onto the local minimum manifold. This accounts for the connected manifolds of minima typically found in ReLU networks due to scaling symmetries.

Visualization of local essential convexity on a loss surface.

By calculating the metric entropy and covering numbers of these stagnation sets, the authors measure the complexity of the space actually visited by the optimizer. This approach shifts the focus from the entire parameter space $\mathbb{R}^D$ to the much smaller volume of the stagnation regions.

Key Results: Independence from Parameter Count

The primary theoretical contribution is a new generalization bound that scales with the dimension of the minima manifold ($d$) and the radius of the stagnation neighborhood ($\delta$), but notably excludes the total number of parameters ($D$):

$$\mathcal{O}\left( \frac{\sqrt{d \log K} + S L \delta \log^{1/2}(\bar{h})}{\sqrt{n}} \right)$$

Here, $K$ represents the number of minima, $S$ the product of spectral norms, $L$ the network depth, and $n$ the number of training samples.

Generalization gap as a function of parameter count D for various stagnation radii delta.

Empirical simulations on synthetic ReLU networks support this finding. As shown in the figure above, once the model reaches a sufficient size, further increasing $D$ has negligible impact on the generalization gap. Instead, the gap is primarily determined by the radius $\delta$ of the local neighborhood where the model stagnates.

Discussion and Limitations

This work reinforces a "two-regime" view of training: an initial global search phase followed by a local stagnation phase. Generalization is determined not by the capacity of the entire network, but by the properties of the specific basin where the model eventually settles.

However, several challenges remain. The reliance on a Gaussian approximation for SGD noise may not capture the "heavy-tailed" escape behaviors observed in real-world training. Additionally, while "Local Essential Convexity" is a powerful theoretical tool, verifying this property for complex architectures like Transformers remains difficult. Future research may also explore how the total parameter count $D$ might implicitly influence other variables, such as the number of minima $K$ or the achievable radius $\delta$.

Summary updated

BibTeX
@article{imaizumi2022generalization,
  author = {Masaaki Imaizumi and Johannes Schmidt-Hieber},
  title = {{On generalization bounds for deep networks based on loss surface implicit regularization}},
  journal = {IEEE Transactions on Information Theory},
  year = {2022},
  doi = {10.1109/tit.2022.3215088},
}
Figure