Distribution-free inequalities for the deleted and holdout error estimates

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, background): “ery high probability, and(b)the guarantee holds simultaneously over all queries in a sequence. The proof of the basic guarantee follows the lines of existing proofs using algorithmic stability (e.g., [DW79a]), while the monitor technique and the resulting ampliﬁcation statements are new. The ampliﬁc”
Robustness and generalization (2010, background): “The first results that relate stability to generalizability track back to Devroye and Wagner (1979a, 1979b).”
Predictive inference with the jackknife+ (2019, methodology): “This work builds on earlier results by Bousquet and Elisseeff [2], which study generalization bounds for risk minimization through the framework of stability conditions; an earlier work in this line is that of Devroye and Wagner [7], which give analogous results for classification risk.”
A high-dimensional Wilks phenomenon (2011, background): “A similar connection between the so-called L1-stability E h P |bhn − bhn−1|i and the bias of the leave-one-out estimate of the risk had been pointed out by Devroye and Wagner (1977) and further investigated by Kearns and Ron (1999) and Rakhlin et al. (2005) (see Theorem 4.1 there).”
Theory of classification : a survey of some recent advances (2005, methodology): “The idea of using stability of a learning algorithm to obtain error bounds was first exploited by Rogers and Wagner [186], Devroye and Wagner [74,75].”
Stability and Generalization (2002, background): “It will turn out to be the case.”
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation (1997, methodology): “On the other hand, among the strongest bounds (in the sense of the quality of the estimate) are those given for the leave-one-out estimate by the work of Rogers and Wagner [15], and Devroye and Wagner [2, 3].”
Early stopping for non-parametric regression: An optimal data-dependent stopping rule (2011, methodology): “ computed in practice). Hold-out method: First, we consider a simple hold-out method: it performs gradient descent using 50% of the data, and uses the other 50% of the data to estimate the risk (e.g. [14]). Assuming that the sample size is even for simplicity, we split the full data set {xi}n i=1 in”
SIRUS: making random forests interpretable (2019, background): “In particular, Rogers and Wagner (1978), Devroye and Wagner (1979), and Bousquet and Elisseeﬀ (2002) show that stability and predictive accuracy are closely connected.”
Generalization Bounds for Uniformly Stable Algorithms (2018, background): “variance (a notable exception is [8] where high probability bounds on the generalization error of k-NN are proved).”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, methodology): “Stability is a classical approach to proving generalization bounds pioneered by Rogers and Wagner (1978); Devroye and Wagner (1979a,b).”