Toward Better Generalization Bounds with Locally Elastic Stability

Zhun Deng, Hangfeng He, Weijie J. Su

Introduction: The Limits of Uniform Stability

A fundamental question in machine learning is: Why does a model trained on a specific dataset work on new, unseen data? To answer this, researchers often rely on algorithmic stability. The underlying intuition is straightforward: if removing a single data point from the training set does not significantly alter the model's predictions, the model is considered "stable" and is therefore likely to generalize well.

Historically, the gold standard for measuring this has been uniform stability, which evaluates the absolute worst-case change in loss across all possible data points. However, uniform stability is often too pessimistic for modern deep learning. In a neural network, removing an image of a "plane" might significantly change the prediction for other "planes," but it has almost zero impact on how the model evaluates a "cat." Uniform stability ignores this localized behavior and focuses entirely on the worst-case "plane-to-plane" impact. This leads to theoretical generalization bounds that, while mathematically valid, are often practically vacuous.

Proposed Method: Locally Elastic Stability (LES)

To address the distribution-independent shortcomings of uniform stability, this paper introduces Locally Elastic Stability (LES).

Instead of relying on a single constant to represent worst-case sensitivity, LES utilizes a function $\beta_m(z_i, z)$ that depends on both the specific training point being removed ($z_i$) and the test point being evaluated ($z$). Because LES is data-dependent, standard mathematical tools like McDiarmid’s inequality (which are traditionally used for uniform stability) cannot be applied. To overcome this, the authors developed a novel, fine-grained analysis of empirical risk to maintain "exponential" bounds—meaning the probability of a large generalization error drops off exponentially as the dataset grows.

To empirically validate their theory on real neural networks without the computationally prohibitive task of retraining models thousands of times, the authors employed influence functions. These functions approximate how much a specific training point affects a specific test prediction.

Key Insights and Empirical Evidence

The authors demonstrate empirically that for architectures like ResNets and random feature models, sensitivity to a data point is highly class-dependent.

Sensitivity heatmaps demonstrating local elasticity across different model architectures on CIFAR-10.

When evaluated on datasets like CIFAR-10, models exhibit a distinct "diagonal" sensitivity structure. For instance, in a ResNet, the "plane-to-plane" sensitivity is approximately seven times higher than the "plane-to-cat" sensitivity.

This reveals that uniform stability is often overkill. For neural networks, the ratio between the worst-case sensitivity (captured by uniform stability) and the average sensitivity (captured by LES) can be as high as 153x. Generalization is not merely a property of the algorithm itself; it is a property of the algorithm interacting with a specific data distribution. LES successfully captures this interaction. Furthermore, unlike some weaker stability notions, the bounds derived from LES shrink to zero as the training sample size ($m$) approaches infinity, making them statistically consistent.

Theoretical Results

The paper's main theoretical contribution (Theorem 3.1) is a new generalization bound that depends on the expectation of the stability function over the population, rather than its maximum.

The authors revisited classic algorithms to demonstrate the superiority of LES:

  • Classic Algorithms: For Support Vector Machines (SVM) and Regularized Least Squares, they proved that if the data is even slightly concentrated (i.e., not perfectly uniform), the LES bound is strictly tighter than the bound provided by uniform stability.
  • Stochastic Gradient Descent (SGD): The theory was also extended to SGD, showing that it naturally satisfies locally elastic stability. This provides a much sharper theoretical explanation for why SGD generalizes so well in practice compared to what previous worst-case stability theories suggested.

Limitations and Future Work

While LES provides a significant step forward, the framework has a few limitations:

  1. Sample Size Requirements: The current theoretical proofs require the training sample size $m$ to be "sufficiently large" for the bounds to hold. Future work is needed to determine if this requirement can be relaxed.
  2. Dependence on Maximum Loss: The bounds still depend on the maximum possible loss ($M_l$). In deep learning, where losses can technically grow very large, this constant can still make the bounds feel loose, even if the stability component is much tighter.
  3. Practical Computation: While influence functions mitigate some computational burden, calculating these bounds for massive, production-scale models remains expensive. Finding more efficient ways to estimate local elasticity is a promising direction for future research.

Summary updated

Abstract

Algorithmic stability is a key characteristic to ensure the generalization ability of a learning algorithm. Among different notions of stability, \emph{uniform stability} is arguably the most popular one, which yields exponential generalization bounds. However, uniform stability only considers the worst-case loss change (or so-called sensitivity) by removing a single data point, which is distribution-independent and therefore undesirable. There are many cases that the worst-case sensitivity of the loss is much larger than the average sensitivity taken over the single data point that is removed, especially in some advanced models such as random feature models or neural networks. Many previous works try to mitigate the distribution independent issue by proposing weaker notions of stability, however, they either only yield polynomial bounds or the bounds derived do not vanish as sample size goes to infinity. Given that, we propose \emph{locally elastic stability} as a weaker and distribution-dependent stability notion, which still yields exponential generalization bounds. We further demonstrate that locally elastic stability implies tighter generalization bounds than those derived based on uniform stability in many situations by revisiting the examples of bounded support vector machines, regularized least square regressions, and stochastic gradient descent.
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