Stability and generalization

By Olivier Bousquet, Andre´ Elisseeﬀ. 2002

94 citations recorded by the source corpus.

We define notions of stability for learning algorithms and show how to use these notions to derive generalization error bounds based on the empirical error and the leave-one-out error. The methods we use can be applied in the regression framework as well as in the classification one when the classifier is obtained by thresholding a real-valued function. We study the stability properties of large classes of learning algorithms such as regularization based algorithms. In particular we focus on Hilbert space regularization and Kullback-Leibler regularization. We demonstrate how to apply the results to SVM for regression and classification.

Subfields: General Health Professions, Philosophy

How researchers see this paper

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

In General Health Professions

In Philosophy

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].”
Domain Adaptation: Learning Bounds and Algorithms (2009, methodology): “This family of algorithms includes support vector machines (SVM) (Cortes & Vapnik, 1995), support vector regression (SVR) (Vapnik, 1998), kernel ridge regression (Saunders et al., 1998), and other algorithms such as those based on the relative entropy regularization (Bousquet & Elisseeff, 2002).”
Does learning require memorization? a short tale about a long tail (2019, background): “Algorithmic stability [13, 25, 28, 46] is essentially the only general approach that is known to imply generalization bounds beyond those achievable via uniform convergence [23, 46].”
Fairness in Machine Learning: A Survey (2020, methodology): “Whilst a number of approaches exist to determine model stability [44, 228, 175, 246, 39, 160], it has rarely been applied to ML research beyond notions of model convergence and traditional performance measures with similar objectives to cross-validation.”
Understanding How Feature Structure Transfers in Transfer Learning (2017, methodology): “To theoretically justify feature structure transfer learning, we introduce the stability framework proposed by [Bousquet and Elisseeff, 2002].”
Generalization Bounds for Transfer Learning under Model Shift (2015, background): “(Bousquet & Elisseeff (2002), Theorem 12 and Example 3) Consider a training set S = { z 1 = ( x 1 , y 1 ) , ..., z m = ( x m , y m ) } drawn i.i.d. from an unknown distribution D .”
Conformal prediction with conditional guarantees (2023, unknown): “For this reason, in our real data examples, we will prefer to use RKHS functions for which we have much faster convergence rates.”
Chromatic PAC-Bayes Bounds for Non-IID Data (2009, background): “ss in the ﬁeld of generalization bounds for classiﬁers, themost noticeable of which areRademacher-complexity-based bounds(Bartlett and Mendelson, 2002; Bartlett et al., 2005), stability-based bounds (Bousquet and Elisseeﬀ, 2002) and PacBayes bounds (McAllester, 1999). Pac-Bayes bounds, introduced by”