Toward Better Generalization Bounds with Locally Elastic Stability

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.

Published in ICML 2021

References in corpus (10)

• Understanding deep learning requires rethinking generalization
• Prevalence of Neural Collapse during the terminal phase of deep learning training
• What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation
• Learning Diverse and Discriminative Representations via the Principle of Maximal Coding Rate Reduction
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Deep Networks from the Principle of Rate Reduction
• The Local Elasticity of Neural Networks
• Traces of Class/Cross-Class Structure Pervade Deep Learning Spectra
• Label-Aware Neural Tangent Kernel: Toward Better Generalization and Local Elasticity
• An Exponential Efron-Stein Inequality for Lq Stable Learning Rules

Cited by in corpus (5)

• Recent advances in deep learning theory
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• Practical Assessment of Generalization Performance Robustness for Deep Networks via Contrastive Examples
• Towards Sharper Utility Bounds for Differentially Private Pairwise Learning
• Characterization of Excess Risk for Locally Strongly Convex Population Risk