Toward Better Generalization Bounds with Locally Elastic Stability

Zhun Deng, Hangfeng He, Weijie J. Su

Abstract

Traditional generalization bounds in machine learning often rely on uniform stability, a metric that considers the worst-case impact of removing a single training point across all possible test points. However, this approach is overly pessimistic for complex models like neural networks, where sensitivity is typically localized to similar data classes. This paper introduces "locally elastic stability," a data-dependent refinement that captures this behavior. By developing new concentration inequalities, the authors derive tighter, exponential generalization bounds that better align with the empirical performance of modern deep learning models.

Introduction: The Generalization Gap

A central question in machine learning is understanding how well a model trained on a specific dataset will perform on unseen data. Algorithmic stability is a key tool for proving generalization: if changing a single training point does not drastically alter the model's predictions, the model is likely to generalize well.

Currently, the gold standard is uniform stability, which evaluates the absolute worst-case change in loss. While it provides strong mathematical guarantees, it is distribution-independent and often too pessimistic. For neural networks, removing a specific image (e.g., a plane) primarily impacts the loss for similar images (other planes) while barely affecting unrelated categories (e.g., cats). Uniform stability ignores this nuance, resulting in theoretical bounds that are too loose to explain the actual success of deep learning.

Methodology: Defining Locally Elastic Stability

To bridge the gap between theory and practice, the authors propose Locally Elastic Stability. Unlike uniform stability, this new parameter $\beta_m(z', z)$ is data-dependent, varying based on both the removed training example ($z'$) and the specific test example ($z$) being evaluated.

Because this stability is data-dependent, standard tools like McDiarmid's inequality cannot be applied due to dependencies among input examples. To overcome this, the authors developed novel concentration inequalities using Doob's martingales. These proofs demonstrate that locally elastic stability still guarantees a vanishing exponential generalization bound. Furthermore, the authors mathematically proved that Stochastic Gradient Descent (SGD) naturally satisfies this stability across convex, strongly convex, and non-convex settings.

Empirical Analysis: The "Elastic" Nature of Neural Networks

Using the CIFAR-10 dataset, the authors estimated model sensitivity for neural networks, random feature models, and linear models. A key finding is that neural networks exhibit a pronounced "diagonal structure" in their sensitivity heatmaps. If a class-specific image is removed from the training set, the model's loss changes almost exclusively for other images in that same class.

Sensitivity heatmaps for (a) neural networks, (b) random feature models, and (c) linear models on CIFAR-10. The diagonal structure in (a) and (b) illustrates local elasticity, which is absent in the linear model (c).

This "local elasticity" explains why the average sensitivity of a model is often orders of magnitude smaller than its worst-case sensitivity. In a ResNet-18 trained on CIFAR-10, the worst-case sensitivity was found to be 3.05, while the expected sensitivity was only 0.02. This indicates that uniform stability overestimates model sensitivity by a factor of approximately 153x.

Key Results and Theoretical Impact

The authors derived a new generalization bound (Theorem 3.1) that scales with expected sensitivity rather than maximum sensitivity. This theoretical advancement makes bounds significantly tighter for algorithms such as bounded Support Vector Machines (SVMs) and regularized least squares.

Empirical validation further showed that sensitivity is even more granular within sub-classes (e.g., removing a "car" affects "trucks" more than "dogs"), confirming the elastic nature of neural network feature spaces. This framework successfully relaxes the worst-case assumption of uniform stability while retaining the highly desirable property of vanishing exponential tail bounds as the dataset grows.

Limitations and Future Work

Despite these advances, the current theoretical proofs require a sufficiently large training sample size ($m$) for the bounds to hold. Investigating whether this requirement can be relaxed is a priority for future research. Additionally, the generalization bound currently relies on a constant ($M_l$) representing the maximum possible loss value. In deep learning, this constant can be quite large, potentially loosening the bound in practical applications. Future work will explore whether this dependence can be improved or bypassed entirely.

Summary updated

BibTeX
@inproceedings{deng2021toward,
  author = {Zhun Deng and Hangfeng He and Weijie J. Su},
  title = {{Toward Better Generalization Bounds with Locally Elastic Stability}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=HzHeNQWDxF},
}
Figure