Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization

By Sayan Mukherjee, Partha Niyogi, Tomaso A. Poggio, Ryan M. Rifkin. 2006

241 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

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

In Statistics and Probability

Citations in the corpus

Stable and Fair Classification (2019, background): “Stability is a crucial consideration in classiﬁcation [10, 57, 12, 25], and has been investigated in several real-world applications, e.g., advice-giving agents [31, 69], recommendation systems [2, 1, 3], and judicial decision-making [66].”
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).”
Robustness and Regularization of Support Vector Machines (2008, background): “The formulations in Shivaswamy et al. (2006), Lanckriet et al.”
A Bayesian Perspective on Generalization and Stochastic Gradient Descent (2017, background): “They demonstrated that these results cannot be understood within the framework of classical theories of statistical learning like Rademacher complexity (Bartlett & Mendelson, 2002), VC-dimension (Vapnik, 1998) or uniform stability (Mukherjee et al., 2006).”
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.”
Counterfactual Memorization in Neural Language Models (2021, background): “…the test performance for model selection; in learning theory, leave-one-out stability was shown to be deeply connected to generalization [e.g. Mukherjee et al., 2006]; in differential privacy, the worst case performance difference of models trained on two “neighboring” datasets (identical…”
Generalization in Deep Learning (2017, background): “Under certain assumptions, many results in statistical learning theory have been shown to be tight and insightful (e.g., Mukherjee et al. 2006; Mohri et al. 2012).”
Making AI Forget You: Data Deletion in Machine Learning (2019, background): “[60] S.”
Robustness and generalization (2010, background): “Later, McDiarmid’s concentration inequalities (McDiarmid 1989) facilitated new bounds on generalization error (e.g., Bousquet and Elisseeff 2002; Poggio et al. 2004; Mukherjee et al. 2006).”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, background): “…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 stability.”
Estimation Stability With Cross-Validation (ESCV) (2013, background): “This in turn, is exactly choosing the solution whose ES metric has the largest reciprocal, or in our analogy, the most statistically signiﬁcant solution along the path.”
Learning Sparse Neural Networks via Sensitivity-Driven Regularization (2018, unknown): “Letting θ denote the network parameters and λ the regularization factor, the problem minimize L ( θ ) with respect to θ is recasted as minimize L ( θ ) + λR ( θ ) with respect to θ. Stability and generalization are strongly related or even equivalent, as shown by Mukherjee et al. [7].”
Generalization in Adaptive Data Analysis and Holdout Reuse (2015, unknown): “An important line of work [BE02, MNPR06, PRMN04, SSSSS10] establishes connections between the stability of a learning algorithm and its ability to generalize.”
Algorithmic Regularization in Over-parameterized Matrix Recovery (2017, unknown): “Recently, the work of Hardt et al. [16] studies the implicit regularization provided by stochastic gradient descent through uniform stability [3, 19, 25].”
Learnability, Stability and Uniform Convergence (2010, background): “A more recent line of work (Rakhlin et al., 2005; Mukherjee et al., 2006) studied stability as a necessary condition for learnability.”