Learnability, Stability and Uniform Convergence

By Shai Shalev-Shwartz, Ohad Shamir, Nati Srebro, Karthik Sridharan. 2010

370 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Control and Systems Engineering, Statistical Learning Theory

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 Control and Systems Engineering

In Statistical Learning Theory

Citations in the corpus

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.”
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].”
Stable and Fair Classification (2019, methodology): “In this paper, we focus on the following stability measure introduced by (Bousquet & Elisseeff, 2002), which was also used by (Shalev-Shwartz et al., 2010; Maurer, 2017; Meng et al., 2017).”
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, neutral): “In statisticalandcomputationallearningtheory, thisideaisknowntoas stability [60,47,50,29,77,68].”
Generalization Error Bounds for Noisy, Iterative Algorithms (2018, background): “Rather than minimizing the risk directly, ERM proceeds by minimizing the empirical average of the loss function evaluated on the finite sample of data points contained in the training set [3].”
Is Out-of-Distribution Detection Learnable? (2022, methodology): “(3)Similar to [30], in this paper, we regard an algorithm as a mapping from ∪+∞ n=1(X × Y) to H.”
Steps Toward Deep Kernel Methods from Infinite Neural Networks (2015, methodology): “Although the technical details are obscured in some of these results, we rely on their derivations (speciﬁcally [3] Theorem 22 and [22] Theorem 2).”
Understanding deep learning requires rethinking generalization (2016, background): “It is possible to deﬁne weaker notions of stability (Mukherjee et al., 2002; Poggio et al., 2004; Shalev-Shwartz et al., 2010).”
How Much Does Your Data Exploration Overfit? Controlling Bias via Information Usage (2015, background): “A powerful line of work in computer science and learning theory [12]–[14] has explored the role of algorithmic stability in preventing overfitting.”
Decentralized Online Learning With Kernels (2017, neutral): “This loss is averaged over all possible training examples to define the statistical loss L̃(f̃) := Ex,y [ (f̃(x), y)], which we combine with a Tikhonov regularizer to construct the regularized loss R̃(f̃) := argminf̃∈H L̃(f̃) + (λ/2)‖f̃‖(2)H [39], [40].”
Information-theoretic analysis of generalization capability of learning algorithms (2017, background): “[8] and the notion of uniform stability defined in Bousquet and Elisseeff [9].”
Gradient Diversity Empowers Distributed Learning (2017, background): “(5)This concept of stability is called the average-RO (replacing one) stability in [37].”
Data-Dependent Stability of Stochastic Gradient Descent (2017, background): “Since our bounds are data-dependent, it is likely that by following a similar analysis one could develop improved optimistic bounds (Srebro et al., 2010), that exhibit fast convergence rates subject to vanishing empirical risk of the output.”