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.

本文提出一种基于局部弹性的弱稳定性概念，用以提供具有指数通用性限制条件的机器学习算法算法稳定性，比常见的分布无关的最坏损失情况敏感性更具参考价值，该概念在支持向量机、最小二乘回归和随机梯度下降等模型中具有受限制的情况下比统一稳定性提供更紧的泛化限制条件。