Distribution-free performance bounds for potential function rules

By Luc Devroye, T. Wagner. 1979

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].”
Making AI Forget You: Data Deletion in Machine Learning (2019, neutral): “In statisticalandcomputationallearningtheory, thisideaisknowntoas stability [60,47,50,29,77,68].”
Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization (2006, methodology): “In the classical literature on generalization properties of local classiﬁcation rules [9] hypothesis stability was proven (and used) to imply Eloo err stability.”
Adaptive computation and machine learning (1998, background): “The section on probability theory is based on Feller (1966, Chapter 4) and Kockelkorn (2000). The following section about functional analysis is compiled from Barner and Flohr (1989), Cristianini and Shawe-Taylor (2000) and Debnath and Mikusinski (1998).”
General conditions for predictivity in learning theory (2004, background): “Though specific theoretical results can be derived for some of these algorithm”
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.”
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation (1997, methodology): “This unlimited complexity often makes it difﬁcult to quantify the performance of the learning algorithm except in terms of the asymptotic generalization error (see Devroye, Gy¨orﬁ and Lugosi [1] for a detailed survey of results for nearest-neighbor algorithms).”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “s trained for multiple epochsmatch classic boundsfor stochastic gradient [27,28]. 1.2 Related work There is a venerable line of work on stability and generalization dating back more than thirty years [4,8,18,25,38]. The landmark work by Bousquet and Elisseeﬀ [4] introduced the notion of uniform stab”
Stability and generalization (2002, methodology): “Different notions of stability have already been defined in t he literature to study leave-one-out estimates of the generalization error [ 7 , 10].”