Stability and Generalization

By Olivier Bousquet, Andre´ Elisseeﬀ. 2002

2,129 citations recorded by the source corpus.

How researchers see this paper

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

In Statistical Learning Theory

Citations in the corpus

Understanding deep learning requires rethinking generalization (2016, background): “This is commonly done with some notion of stability, such as uniform stability (Bousquet & Elisseeff, 2002).”
On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima (2016, background): “In [6], the authors define notions for stability of learning algorithms and use these definitions to prove generalization bounds.”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “As training time is inevitably limited in practice, our results help to explain the strong generalization performance of stochastic gradient methods observed in practice.”
Sharp Minima Can Generalize For Deep Nets (2017, background): “For example, Duchi et al. (2011); Nesterov & Vial (2008); Hardt et al. (2016); Bottou et al. (2016); Go-nen & Shalev-Shwartz (2017) rely on the concept of stochastic approximation or uniform stability (Bousquet & Elisseeff, 2002).”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “…or flat minima (see, for instance, Srebro et al., 2010; Kakade et al., 2009; Zhou, 2002; Schapire et al., 1998; Koltchinskii et al., 2002; Bousquet and Elisseeff, 2002; Vapnik and Chervonenkis, 1971); the size of the Rashomon set differs from all of these quantities in fundamental ways,…”
Theoretical Guarantees for Model Auditing with Finite Adversaries (2019, background): “More contemporary developments in this topic can be found in [27–32] and references therein.”
On the (Statistical) Detection of Adversarial Examples (2017, background): “They operate in a black-box threat model where they typically can interact with the model only through an interface analog to a cryptographic oracle: it returns the label or probability vector output by the model when presented with an input chosen by the adversary.”
To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, positive): “This property of a learning algorithm to not over-ﬁt the training data (also known as stability ) is known to be both necessary and sufﬁcient for a learning algorithm to generalize Shalev-Shwartz et al. [2009, 2010], Poggio et al. [2011], Bousquet and Elisseeff [2002].”
Analysis of classifiers’ robustness to adversarial perturbations (2015, background): “Finally, the stability of learning algorithms has been defined and extensively studied in (Bousquet & Elisseeff, 2002; Lugosi & Pawlak, 1994).”
Stable and Fair Classification (2019, methodology): “…F that minimizes the expected risk R ( f However, since (cid:61) is often unknown, we usually use the empirical risk to estimate the expected risk [10, 65, 52], i.e., given a training set S = { s i = ( x i , z i , y i ) } i ∈ [ N ] (where ( x i , z i , y i ) ∈ D ), the objective is to learn a…”
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).”
Error asymmetry in causal and anticausal regression (2016, background): “However, the classical learning theories, such as [16,17,18,19,20], are mainly focused on the general nature of statistical algorithms or data dependent properties, but do not consider a connection between the causality in the generation process of data and the corresponding implications for the pre”
Entropy-SGD: biasing gradient descent into wide valleys (2016, methodology): “Stability of the algorithm (Bousquet & Elisseeff, 2002) is then a notion of how much its output differs in loss upon being presented with two datasets, Ξ and Ξ 0 , that differ in at most one sample: (cid:2) (cid:0) (cid:1)(cid”
Smoothness, Low Noise and Fast Rates (2010, methodology): “…similar to Corollary 3: q then for all w ⋆ ∈ W with F ( w ⋆ ) ≤ B 2 and L ( w ⋆ ) ≤ L ∗ , we have that in expectation over sample of size n : To prove Theorem 4 we use stability arguments similar to the ones used by Shalev-Shwartz et al [25], which are in turn based on Bousquet and Elisseeﬀ [7].”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “Stability corresponds to smoothness of the learning map, and the concept is typically used in statistical learning theory to yield tight risk bounds, sometimes when class capacity-based approaches (such as VC dimension-based approaches) do not apply (Devroye and Wagner, 1979; Kearns and Ron, 1999; B”
Robustness and Regularization of Support Vector Machines (2008, background): “It is now well known that a stable algorithm such as SVM has desirable generalization properties, and is statistically consistent under mild technical conditions; see for example Bousquet and Elisseeﬀ (2002); Kutin and Niyogi (2002); Poggio et al. (2004); Mukherjee et al. (2006) for details.”
Preserving Statistical Validity in Adaptive Data Analysis (2014, background): “An important line of work [11, 33, 34, 40] establishes connections between the stability of a learning algorithm and its ability to generalize.”