Local Rademacher complexities

By Peter L. Bartlett, Olivier Bousquet, Shahar Mendelson. 2005

945 citations recorded by the source corpus.

We propose new bounds on the error of learning algorithms in terms of a data-dependent notion of complexity. The estimates we establish give optimal rates and are based on a local and empirical version of Rademacher averages, in the sense that the Rademacher averages are computed from the data, on a subset of functions with small empirical error. We present some applications to classification and prediction with convex function classes, and with kernel classes in particular.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Management Science and Operations Research

In Statistical Learning Theory

Citations in the corpus

A Closer Look at Memorization in Deep Networks (2017, background): “Zhang et al. (2017) show that DNNs can perfectly ﬁt noise and thus that their generalization ability cannot be explained through traditional statistical learning theory (e.g., see (Vapnik & Vapnik, 1998; Bartlett et al., 2005)).”
Smoothness, Low Noise and Fast Rates (2010, methodology): “For example, Steinwart [29] used Local Rademacher Complexity to provide fast rate on the 0/1 loss of Support Vector Machines (SVMs) ( ℓ 2 -regularized hinge-loss minimization) based on the so called “geometric margin condition” and Tsybakov’s margin condition.”
Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, methodology): “Of particular relevance to us are Yarotsky (2017, 2018) and Bartlett et al. (2017); a recent textbook treatment, containing numerous other references, is given by Goodfellow et al.”
On the optimal estimation of probability measures in weak and strong topologies (2013, methodology): “(i) Note that instead of using McDiarmid’s inequality in the above proof, one can directly obtain a version of (58) by applying Talagrand’s inequality through Theorem 2.1 in [3], albeit with worse constants and similar dependency on n .”
On the empirical estimation of integral probability metrics (2012, neutral): “4 in [4].”
Variance-based Regularization with Convex Objectives (2016, background): “Although the below result is in terms of covering numbers for ease of exposition, a variant holds depending on localized Rademacher averages [2] of the class F , which can yield tighter guarantees (we omit such results for lack of space).”
Robustness and Regularization of Support Vector Machines (2008, background): “Indeed, research on classifier regularization mainly considers its effect on bounding the complexity of the function class (e.g., Smola et al., 1998; Evgeniou et al., 2000; Bartlett and Mendelson, 2002; Koltchinskii and Panchenko, 2002; Bartlett et al., 2005).”
Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes (2019, methodology): “sumptions in Theorem 6 are standard ﬁnite-sample estimation guarantees. For example, if estimators for nuisancesare obtained byempirical riskminimization methods based on L2-loss, then the results of Bartlett et al. (2005) apply. In this cases, the rates α1 and α2 would be determined by the local Ra”
Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, background): “This type of fixed point equation is familiar from work on oracle inequalities and local complexity measures in empirical process theory [2, 17, 31, 36], and when λ is chosen so that the fixed point equation (9) holds this (typically) yields minimax optimal convergence rates [2, 17, 36, 8].”
Self-Distillation Amplifies Regularization in Hilbert Space (2020, background): “7 of [3] which provides a generalization bound that is affine in the form”
Robustness and generalization (2010, background): “…Vapnik-Chervonenkis (VC) dimension (Vapnik and Chervonenkis 1991; Evgeniou et al. 2000), the fat-shattering dimension (Kearns and Schapire 1994; Alon et al. 1997; Bartlett 1998), and the Rademacher complexity (Koltchinskii 2002; Bartlett and Mendelson 2002; Bartlett et al. 2005).”
On the Spectral Bias of Neural Networks (2018, background): “dom perturbation directions). Higher frequency functions are more sensitive to parameter perturbations. Traditional statistical learning theory (Eg. VC-dimensions Vapnik (2013), Rademacher complexity Bartlett et al. (2005)) cannot explain the behavior of deep networks because their generalization bo”
Efficient Policy Learning (2017, methodology): “, Bartlett et al. (2005) and Giné and Koltchinskii (2006). The reason we might expect slicing to work in our case is that, as discussed earlier, the efficient variance for evaluating any given policy π is V (π) = V (n) max −Q(2)n (π).”
Data-Dependent Stability of Stochastic Gradient Descent (2017, background): “PAC literature approached such bounds through relative VC bounds [37], local Rademacher complexity [2], and Rademacher bounds for smooth loss classes [35].”
Active and passive learning of linear separators under log-concave distributions (2012, background): “, 2007; Koltchinskii, 2010; Hanneke, 2011); this includes the random classification noise commonly studied in computational learning theory (Kearns and Vazirani, 1994), and the more general bounded (or Massart) noise (Bartlett et al., 2005; Massart and Nedelec, 2006; Giné and Koltchinskii, 2006; Kol”
Regularization in kernel learning (2010, background): “Such a function is called an empirical minimizer and its properties have been widely studied (see, for example, [2, 3, 8, 16, 19] and references therein).”
Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning (2016, methodology): “In what follows, we demonstrate the power of Theorem 8 by applying it to derive the LRC bounds for some popular MTL models, including group norm, Schatten norm and graph regularized MTL models extensively studied in the literature of MTL [46, 23, 6, 4, 38, 3].”