Algorithmic Stability and Generalization Performance

By Olivier Bousquet, Andre´ Elisseeﬀ. 2000

153 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.

Citations in the corpus

Stability and Generalization (2002, methodology): “In previous work (see [4]), we focused on a specific type of lea rning algorithm in the regression case.”
Stability Bounds for Stationary φ-mixing and β-mixing Processes (2008, methodology): “It has been later used successfully by Bousquet and Elisseeff (2001, 2002) to show algorithm-speciﬁc stability bounds for i.i.d. samples.”
Extensions to McDiarmid's inequality when dierences are bounded with high probability (2002, methodology): “Such a result would have significant implications for the theory of algorithmic stability [5, 13].”
SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training (2025, unknown): “…RL are both widely used for foundation model training (OpenAI, 2023b; Google, 2023; Jaech et al., 2024; DeepSeekAI et al., 2025), their distinct effects on generalization (Bousquet & Elisseeff, 2000; Zhang et al., 2021) remain unclear, making it challenging to build reliable and robust AI systems.”
Updates in Human-AI Teams: Understanding and Addressing the Performance/Compatibility Tradeoff (2019, background): “Stability expresses the ability of a model to not significantly change its predictions given small changes in the training set (Bousquet and Elisseeff 2001).”
Algorithms for Learning Kernels Based on Centered Alignment (2012, methodology): “A version of this result was presented by Cristianini, Shawe-Taylor, E isseeff, and Kandola (2001) and Cristianini, Kandola, Elisseeff, and Shawe-Taylor (2002) for the so-called Parz en window solution and non-centered kernels.”
Stability and generalization (2002, methodology): “It is based on earlier results presented in Bousquet and Elisseeff (2001). We consider both the leaveone-out error and the empirical error as possible estimates of the generalization error.”
Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization (2006, background): “For instance, the results of [4] imply that regularization and SVMs are LOO stable; a version of bagging with the number k of regressors increasing with n (with (k/n) → 0) is CV loo stable and has hypothesis stability (because of [9]) and thus LOO stable; similarly k -NN with k → ∞ and (k/n) → 0…”
Regularization and Semi-supervised Learning on Large Graphs (2004, methodology): “We use the notion of algorithmic stability, flrst introduced by Devroye and Wagner in [6] and later used by Bousquet and Elisseefi in [ 3 ] to prove generalization bounds for regularization networks.”
A Generalized Representer Theorem (2001, background): “More sophisticated functions based on other bounds on the test error are conceivable, as well as variants for regression estimation (e.g., [3, 6 ]).”
Feature Selection with Ensembles, Artificial Variables, and Redundancy Elimination (2009, background): “More recently, a series of theoretical developments (Bousquet and Elisseeff, 2001; Poggio et al., 2002; Mukherjee et al., 2006; Poggio et al., 2004) also confirmed the fundamental role of stability for the generalization of a learning algorithm.”