Generalization Bounds for Uniformly Stable Algorithms

By Vitaly Feldman, Jan Vondr'ak. 2018

105 citations recorded by the source corpus.

Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002). Specifically, for a loss function with range bounded in $[0,1]$, the generalization error of $\gamma$-uniformly stable learning algorithm on $n$ samples is known to be at most $O((\gamma +1/n) \sqrt{n \log(1/\delta)})$ with probability at least $1-\delta$. Unfortunately, this bound does not lead to meaningful generalization bounds in many common settings where $\gamma \geq 1/\sqrt{n}$. At the same time the bound is known to be tight only when $\gamma = O(1/n)$. Here we prove substantially stronger generalization bounds for uniformly stable algorithms without any additional assumptions. First, we show that the generalization error in this setting is at most $O(\sqrt{(\gamma + 1/n) \log(1/\delta)})$ with probability at least $1-\delta$. In addition, we prove a tight bound of $O(\gamma^2 + 1/n)$ on the second moment of the generalization error. The best previous bound on the second moment of the generalization error is $O(\gamma + 1/n)$. Our proofs are based on new analysis techniques and our results imply substantially stronger generalization guarantees for several well-studied algorithms.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Stable and Fair Classification (2019, background): “Existing literature [10, 29] claimed that uniform stability implies a generalization bound.”
Generalization in anti-causal learning (2018, background): “Interestingly, a certain form of leave-one-out stability of the learning algorithm provides necessary and sufﬁcient conditions for generalization in an even more general class of learning problems than ERM (Mukherjee et al., 2006; Bousquet and Elisseeff, 2002; Feldman and Vondrak, 2018).”
Uniform convergence may be unable to explain generalization in deep learning (2019, background): “Or perhaps, algorithmic stability (Feldman & Vondrák, 2018; Hardt et al., 2016; Bousquet & Elisseeff, 2002; ShalevShwartz et al., 2010) which has not been as extensively studied for deep networks, might hold more promise in explaining generalization (although there are challenges specific to using…”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, background): “These bounds have been signiﬁcantly improved in a recent sequence of works (Feldman and Vondrák, 2018, 2019; Bousquet et al., 2019).”
AUC Maximization in the Era of Big Data and AI: A Survey (2022, methodology): “The work [95] uses the the concept of uniform stability [15] and the corresponding high probability generalization bounds [16, 44] to derive the excess risk bound O (logn/ √ n) in the convex case.”