On Linear Stability of SGD and Input-Smoothness of Neural Networks

Chao Ma, Lexing Ying

TL;DR

This paper provides a theoretical bridge between the "flatness" of a neural network's loss landscape and its ability to generalize to new data. By analyzing the linear stability of Stochastic Gradient Descent (SGD), the authors demonstrate that SGD implicitly regularizes the Sobolev norms (smoothness) of the model function relative to its inputs. This mathematical connection helps explain why SGD produces models that are both high-performing and adversarially robust.

The Problem: Why Does Flatness Matter?

Deep learning researchers have long observed that SGD tends to find "flat minima"—regions of the parameter space where the loss remains relatively stable even if the weights are perturbed. Empirically, these flat minima generalize better than "sharp" ones. However, two fundamental questions have remained largely unanswered:

  1. Why does SGD prefer flat minima in the first place?
  2. Why exactly does parameter flatness lead to better generalization on unseen data?

Existing theories often model SGD as a continuous process using Stochastic Differential Equations (SDEs). Unfortunately, this approximation breaks down when learning rates are large. Furthermore, the link between parameter flatness and a model's performance on new data has often relied more on intuition than rigorous mathematical proof. This paper bridges these gaps by examining the discrete dynamics of SGD and the specific mathematical structure of neural network layers.

Methods: Connecting Parameters to Inputs

To build this bridge, the authors employ two primary theoretical tools:

  • Linear Stability Analysis: Instead of relying on SDEs, the researchers analyze the discrete-time stability of SGD around a global minimum. They extend previous work to include "high-order moments," demonstrating that for SGD to remain stable (i.e., for the loss not to explode), the gradients of the loss must satisfy specific, strict constraints.
  • Multiplicative Structure Analysis: The authors exploit a fundamental property of neural networks: in the first layer, weights ($W_1$) and input data ($x$) are multiplied together. This simple structural observation allows them to mathematically link the gradient of the model with respect to its parameters to its gradient with respect to the input data.

By combining these two approaches, they prove that the stability requirements of SGD act as an implicit Sobolev regularization. In practical terms, SGD forces the neural network to be "smooth" in the input space, preventing it from making wild, erratic predictions between known training points.

Key Insights

  • Flatness Equals Input Smoothness: The paper's core breakthrough is proving that flatness in the weight landscape directly translates to smoothness in the input landscape due to the multiplicative nature of the first layer. If the loss is flat with respect to $W_1$, the model's output must be smooth with respect to $x$.
  • Beyond Continuous Approximations: By utilizing linear stability, the authors accurately capture the behavior of SGD at moderate-to-large learning rates. This succeeds where traditional "diffusion" theories—which incorrectly suggest it takes exponentially long to escape sharp minima—fail to match empirical reality.
  • Implicit Sobolev Regularization: SGD does more than just minimize training error; it acts as a hidden regularizer that penalizes high-frequency oscillations in the model function. This inherent smoothness explains why SGD-trained models are naturally more robust to adversarial attacks, which typically exploit such oscillations.
  • Manifold Generalization: The authors derive generalization bounds that are particularly tight when the input data lies on a low-dimensional manifold, a common and realistic assumption for complex real-world data like images.

Empirical Validation and Key Results

The authors validated their theoretical insights using standard benchmarks, including FashionMNIST (with a fully-connected network) and CIFAR10 (with a VGG-11 convolutional network). These experiments were specifically designed to test the correlation between parameter-space flatness and input-space smoothness.

The results demonstrate a strong empirical correlation between the norm of the parameter gradient ($g_W$) and the norm of the input gradient ($g_x$).

Correlation between parameter gradient norm ($g_W$) and input gradient norm ($g_x$)

As illustrated in the figure above, solutions found with larger learning rates and smaller batch sizes (indicated by the yellow/green points) consistently exhibit smaller gradient norms in both parameter and input spaces. This confirms the theoretical prediction that "noisier" SGD configurations lead to smoother, more heavily regularized models.

Quantitatively, the paper introduces a new generalization error bound that scales with the number of data points and the "coverage" of the training data. They show that as the order of stability increases, the model becomes increasingly smooth, yielding stronger theoretical guarantees for both generalization and adversarial robustness.

Limitations and Future Work

  • Weight Norm Dependency: The current theoretical bounds depend on the norm of the first-layer weights ($\|W_1\|$). While the authors show empirically that this norm remains stable during training, in certain architectures (such as those using ReLU without batch normalization), weights can grow significantly, which could loosen the bounds.
  • Data Coverage Assumption: The generalization results rely on a "covered condition"—the assumption that test data is generally close to some training data point. While this holds true for low-dimensional manifolds, it may be difficult to satisfy in extremely high-dimensional, sparse feature spaces.
  • Extension to Deeper Layers: The current analysis focuses heavily on the input (first) layer. The authors suggest that the multiplicative structure also exists in intermediate layers, making the extension of this "Sobolev effect" throughout the entire depth of the network a highly promising direction for future research.

Summary updated

Abstract

The multiplicative structure of parameters and input data in the first layer of neural networks is explored to build connection between the landscape of the loss function with respect to parameters and the landscape of the model function with respect to input data. By this connection, it is shown that flat minima regularize the gradient of the model function, which explains the good generalization performance of flat minima. Then, we go beyond the flatness and consider high-order moments of the gradient noise, and show that Stochastic Gradient Dascent (SGD) tends to impose constraints on these moments by a linear stability analysis of SGD around global minima. Together with the multiplicative structure, we identify the Sobolev regularization effect of SGD, i.e. SGD regularizes the Sobolev seminorms of the model function with respect to the input data. Finally, bounds for generalization error and adversarial robustness are provided for solutions found by SGD under assumptions of the data distribution.
BibTeX
@inproceedings{ma2021linear,
  author = {Chao Ma and Lexing Ying},
  title = {{On Linear Stability of SGD and Input-Smoothness of Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=yAvCV6NwWQ},
}
Figure