Rademacher Processes and Bounding the Risk of Function Learning

By Vladimir Koltchinskii, D. Panchenko. 2004

279 citations recorded by the source corpus.

We construct data dependent upper bounds on the risk in function learning problems. The bounds are based on local norms of the Rademacher process indexed by the underlying function class, and they do not require prior knowledge about the distribution of training examples or any specific properties of the function class. Using Talagrand’s type concentration inequalities for empirical and Rademacher processes, we show that the bounds hold with high probability that decreases exponentially fast when the sample size grows. In typical situations that are frequently encountered in the theory of function learning, the bounds give nearly optimal rate of convergence of the risk to zero.

Subfields: Artificial Intelligence, 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 Statistics and Probability

Citations in the corpus

Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, methodology): “The ideas of our localization are rooted in Koltchinskii and Panchenko (2000) and Bartlett, Bousquet, and Mendelson (2005), and related to Koltchinskii (2011).”
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results (2003, background): “Koltchinskii and Panchenko (2000a) proved an analogous error bound in terms of margins .”
Local Rademacher complexities (2005, methodology): “root property. One possible approach is to use classical upper bounds on the Rademacher averages, such as Dudley’s entropy integral. This can give a sub-root upper bound and was used, for example, in [16] and in [22]. However, the second part of Theorem 3.3 indicates a possible choice for ψ, namely,”
Generalization in Deep Learning (2017, background): “…data-dependent bounds with the luckiness framework (Shawe-Taylor et al., 1998; Herbrich and Williamson, 2002) and empirical Rademacher complexity (Koltchinskii and Panchenko, 2000; Bartlett et al., 2002) still depend on a concept of hypothesis spaces (or the sequence of hypothesis spaces), and…”
Empirical margin distributions and bounding the generalization error of combined classifiers (2002, methodology): “The method of proof is similar to the one developed in Koltchinskii and Panchenko (1999) and is based on powerful concentration inequalities of Talagrand (1996) (see also Massart (2000)).”
Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning (2016, background): “3 Previous Related Works An earlier work by Maurer (2006a), which considers linear MTL frameworks for binary classification, investigates the generalization guarantees based on Rademacher averages.”
From Dependence to Causation (2016, background): “(7.7) The following result — in spirit of Koltchinskii and Panchenko (2000); Bartlett and Mendelson (2003) and found in Boucheron et al. (2005, Theorem 4.1) — extends Theorem 2.12 to surrogate risk minimization.”
Theory of classification : a survey of some recent advances (2005, methodology): “For refinements and further development, see Koltchinskii and Panchenko [126], Lozano [29, 142], Bartlett, Bousquet and Mendelson [25], Bousquet, Koltchinskii and Panchenko [50].”
Towards a Learning Theory of Cause-Effect Inference (2015, background): “The following result — in spirit of Koltchinskii & Panchenko (1999); Bartlett & Mendelson (2002) — can be found in Boucheron et al. (2005, Theorem 4.1).”
DEEP NEURAL NETWORKS FOR ESTIMATION AND INFERENCE (2020, methodology): “The ideas of our localization are rooted in Koltchinskii and Panchenko (2000) and Bartlett, Bousquet, and Mendelson (2005), and related to Koltchinskii (2011).”
Oracle inequalities in empirical risk minimization and sparse recovery problems (2011, methodology): “I am especially thankful to Peter Bartlett, Lucien Birgé, Gilles Blanchard, Stephane Boucheron, Olivier Bousquet, Richard Dudley, Sara van de Geer, Evarist Giné, Gabor Lugosi, Pascal Massart, David Mason, Shahar Mendelson, Dmitry Panchenko, Alexandre Tsybakov, Aad van der Vaart, Jon Wellner and Jo”
A Few Notes on Statistical Learning Theory (2002, background): “Koltchinskii and Panchenko [13] have introduced a computable iterative scheme which enabled them to replace the “actual” ball by an empirical one for a random sequence of radii rk = rk(X1, .”
Rademacher Complexity Bounds for Non-I.I.D. Processes (2008, unknown): “The pioneering work of Yu [15] led to VC-dimension bounds for stationaryβ-mixing sequences.”
Moment inequalities for functions of independent random variables (2005, background): “MR1842526 [23] Koltchinskii, V. and Panchenko, D. (2000).”
Relative deviation learning bounds and generalization with unbounded loss functions (2013, methodology): “This includes standard VC-dimension bounds (Vapnik, 1998), Rademacher complexity (Koltchinskii and Panchenko, 2000; Bartlett et al., 2002a; Koltchinskii and Panchenko, 2002; Bartlett and Mendelson, 2002) or local Rademacher complexity bounds (Koltchinskii, 2006; Bartlett et al., 2002b), as well as…”
Introduction to Statistical Learning Theory (2004, methodology): “The use of Rademacher averages in classification was first promoted by Koltchinskii [75] and Bartlett, Boucheron, and Lugosi [76], see also Koltchinskii and Panchenko [77, 78], Bartlett and Mendelson [79], Bartlett, Bousquet, and Mendelson [80], Bousquet, Koltchinskii, and Panchenko [81], Kégl, Lind”
The Dependence of Effective Planning Horizon on Model Accuracy (2015, background): “Furthermore, hypothesis-counting measures of complexity are typically weak, whereas modern data-dependent measures can be significantly tighter and more sensitive [12].”