Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
By Peter L. Bartlett, Shahar Mendelson. 2003
3,284 citations recorded by the source corpus.
We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities. In a decision theoretic setting, we prove general risk bounds in terms of these complexities. We consider function classes that can be expressed as combinations of functions from basis classes and show how the Rademacher and Gaussian complexities of such a function class can be bounded in terms of the complexity of the basis classes. We give examples of the application of these techniques in finding data-dependent risk bounds for decision trees, neural networks and support vector machines.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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
- Yoshua Bengio
- Sergey Levine
- Percy Liang
- Quoc V. Le
- Mohit Bansal
- Ruslan Salakhutdinov
- Dacheng Tao
- Jianfeng Gao
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Xiaogang Wang
- Jitendra Malik
- Andrew Zisserman
- Yi Yang
In Statistical Learning Theory
- Francis R. Bach
- Bernhard Schölkopf
- Arthur Gretton
- Kenji Fukumizu
- Bharath K. Sriperumbudur
- Alex Smola
- Michael I. Jordan
- Jason D. Lee
Citations in the corpus
- Deep Learning Scaling is Predictable, Empirically (2017, methodology): “Follow-on work uses data complexity measures to estimate the structure of model families that might fit the data (Bartlett and Mendelson (2002)).”
- The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, neutral): “Bartlett and Mendelson [2002]), we can bound the empirical Rademacher complexity of the function class F : R̂X(F) := 1 n E ε1,.”
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, positive): “Proof Based on [9], E[L(f, `)] ≤ L(f, `) + 2RS(`,F) + √ 5 log(2/δ) n holds with 1 − δ probability.”
- Combined Scaling for Zero-shot Transfer Learning (2021, background): “Lemma 4 is a direct application of previous results (Bartlett and Mendelson, 2002; Mohri et al., 2012; Shalev-Shwartz and Ben-David, 2014) to our problem.”
- Designing and Interpreting Probes with Control Tasks (2019, background): “(2017) defined completely random tasks related to Rademacher complexity (Bartlett and Mendelson, 2001) to understand the capacity”
- A theory of learning from different domains (2010, background): “We do not yet know whether our divergence measure admits tighter data-dependent bounds (McAllester 2003; Bartlett and Mendelson 2002), or if there are other, more appropriate divergence measures which do.”
- Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, background): “V.7 Proof of Theorem 10 The Rademacher complexity is a fundamental notion in learning [Bartlett and Mendelson, 2002].”
- Certifying Some Distributional Robustness with Principled Adversarial Training (2017, methodology): “Thus, the functional θ 7→ F n ( θ ) satisfies bounded differences [14, Thm. 6.2], and applying standard results on Rademacher complexity [1] and entropy integrals [64, Ch. 2.2] gives the result.”
- Robust Large Margin Deep Neural Networks (2016, methodology): “Various measures such as the VC-dimension [29], [30], the Rademacher or Gaussian complexities [31] and algorithmic robustness [32] have been used to bound the GE in the context of DNNs.”
- Fair Regression: Quantitative Definitions and Reduction-based Algorithms (2019, methodology): “For a fixed tuple ( s 1 , u 1 ) , . . . , ( s n , u n ) , we have where the first inequality follows from Theorem 12(5) of Bartlett & Mendelson (2002) and the last inequality follows from the contraction principle of Ledoux & Talagrand (1991), specifically their Theorem 4.12.”
- Smoothness, Low Noise and Fast Rates (2010, methodology): “Table 1 summarizes the bounds on the excess risk of the ERM implied by Theorem 1 as well previous bounds for Lipschitz loss on finite-dimensional [22] and scale-sensitive [2] classes, and a bound for squared-loss on finite-dimensional classes [9, Theorem 11.”
- Balanced Policy Evaluation and Learning (2017, methodology): “We quantify that using Rademacher complexity [3] and later extend our results to VC dimension.”
- On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “Following standard results for Rademacher complexities of ℓ 2 -balls (Bartlett and Mendelson, 2003, Lemma 22), the first term is less than Because of the G -Lipschitz-continuity of the loss, we have dρ ) , and thus the second term is less than √ 8 λGF 3 GF √ λ .”
- Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent (2020, positive): “…E[ sup ‖wt‖2≤Bt,t∈[T ] T∑ t=1 〈wt, 2 nt nt∑ i=1 iφt(x t i)〉Ht |(Xt)] = T∑ t=1 E[ sup ‖wt‖2≤Bt 〈wt, 2 nt nt∑ i=1 iφt(x t i)〉Ht |(Xt)] ≤ T∑ t=1 2Bt nt (Tr(kt(Xt,Xt))) 1/2 The last inequality is obtained by applying the upper bound from Lemma 22 in (Bartlett & Mendelson, 2003), on each function…”
- Minimax Weight and Q-Function Learning for Off-Policy Evaluation (2019, background): “Here we show that in the tabular setting, which is a special case of the linear setting, MWL and MQL can achieve the semiparametric lower bound of OPE (Kallus and Uehara, 2019a), because they coincide 10See Bartlett and Mendelson (2003) for the definition.”