Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation

By Michael Kearns, Dana Ron. 1997

How researchers see this paper

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

Citations in the corpus

Algorithmic stability for adaptive data analysis (2015, methodology): “Traditionally, stability was measured via the change in the generalization error of an algorithm’s output, and algorithms stable according to such a criterion have long been known to ensure statistical validity in nonadaptive analysis [DW79a, DW79b, KR99, BE02, SSSS10].”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “Several notions of stability are known to lead to good generalization error bounds (Devroye and Wagner, 1979; Kearns and Ron, 1999; Bousquet and Elissee , 2002; Kutin and Niyogi, 2002), sometimes in cases where class capacity-based approaches such as VC theory do not apply.”
Stronger generalization bounds for deep nets via a compression approach (2018, background): “Finally, note that the terms compression and stability are traditionally used in a different sense in generalization theory (Littlestone and Warmuth, 1986; Kearns and Ron, 1999; Shalev-Shwartz et al., 2010).”
Making AI Forget You: Data Deletion in Machine Learning (2019, background): “In statistical and computational learning theory, this idea is known to as stability [60, 47, 50, 29, 77, 68].”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “Since we will not deal with other variants of algorithmic stability in this paper (e.g., hypothesis stability (Kearns & Ron, 1999), uniform stability (Bousquet & Elisseeff, 2002) and leave-one-out (LOO) stability in Mukherjee et al. (2006)), we simply call Definition 6 stability or uniform…”
Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization (2006, methodology): “A deﬁnition which turns out to be equivalent was introduced in [5] (see also [14]) under the name of pointwise hypothesis ( PH ) stability .”
Beating the hold-out: bounds for K-fold and progressive cross-validation (1999, background): “It would also be interesting to explore the connection between hypothesis instabili y, which Breiman discusses for the purposes of reducing generalization error, to hypothesis stability, which Kearns and Ron [8] trace back to Devroye and Wagner [5] for the purposes of accurate error estimation.”
Sample Selection Bias Correction Theory (2008, methodology): “Our analysis is based on the novel concept of distributional stability which generalizes the point-based stability introduced and analyzed by previous authors (Devroye & Wagner, 1979; Kearns & Ron, 1997; Bousquet & Elisseeff, 2002).”
Estimating the Generalization Performance of an SVM Efficiently (2000, methodology): “Bounds on the variability of the leave-oneout estimator presented by Kearns and Ron 1997 are independent of the learning task.”
Stability and Generalization (2002, background): “2 Definition of stability Different notions of stability have already been defined in t he literature to study leave-one-out estimates of the generalization error [7, 10].”
Theory of classification : a survey of some recent advances (2005, background): “Kearns and Ron [116] investigated it further and introduced formally several measures of stability.”
A high-dimensional Wilks phenomenon (2011, background): “pointed out by Devroye and Wagner [14] and further investigated by Kearns and Ron [ 22 ] and Rakhlin et al. [37] (see Theorem 4.1 there).”
Fairness in Machine Learning: A Survey (2020, unknown): “…research operates quite often in simulation and not using “standard” datasets (Reference [215] is a notable exception) and thus there is a need to produce or identify meaningful datasets for these approaches to be evaluated with and to compare to other approaches discussed throughout this article.”
Automated detection of brain atrophy patterns based on MRI for the prediction of Alzheimer's disease (2010, methodology): “Cross-validation is an established validation scheme in the case of few training examples with respect to the dimensionality of the data (Kearns and Ron, 1997).”