A Vector-Contraction Inequality for Rademacher Complexities
By Andreas Maurer. 2016
308 citations recorded by the source corpus.
The contraction inequality for Rademacher averages is extended to Lipschitz functions with vector-valued domains, and it is also shown that in the bounding expression the Rademacher variables can be replaced by arbitrary iid symmetric and sub-gaussian variables. Example applications are given for multi-category learning, K-means clustering and learning-to-learn.
Subfields: Artificial Intelligence, Statistical Learning Theory, Pure Mathematics
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
- Dacheng Tao
- Yoshua Bengio
- Yuanzhi Li
- Tengyu Ma
- Ruslan Salakhutdinov
- Zeyuan Allen-Zhu
- Sergey Levine
- Percy Liang
In Statistical Learning Theory
- Yuanzhi Li
- Samet Oymak
- Zeyuan Allen-Zhu
- M. Soltanolkotabi
- Behnam Neyshabur
- Mingchen Li
- Kavosh Asadi
- Mehryar Mohri
In Pure Mathematics
- Zeyuan Allen-Zhu
- Dacheng Tao
- Zalan Fabian
- Corinna Cortes
- Zhi-Hua Zhou
- Yann LeCun
- Marc Niethammer
- Nati Srebro
Citations in the corpus
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, methodology): “We begin by stating a vector contraction inequality by Maurer [41].”
- Combined Scaling for Zero-shot Transfer Learning (2021, neutral): “Using a vector-contraction inequality, i.e., Corollary 4 of (Maurer, 2016) with the additional expectation of both sides of the inequality, we have that This proves the first statement.”
- A Theoretical Analysis of Contrastive Unsupervised Representation Learning (2019, background): “[Corollary 4 in (Maurer, 2016)] Let Z be any set, and S = { z j } Mj =1 ∈ Z M .”
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “8]; for the scalar case with absolute value, see [10, Theorem 12]; and for the vector case without absolute value, see [39].”
- Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks (2018, methodology): “We use the following technical result from Maurer [16] in our proof.”
- SIN: Semantic Inference Network for Few-Shot Streaming Label Learning (2022, methodology): “Theorem 1 employs the Rademacher complexity [57], [58] of the hypotheses space H to bound the generalization error of SIN.”
- Can SGD Learn Recurrent Neural Networks with Provable Generalization? (2019, background): “8]; for the scalar case with absolute value, see [6, Theorem 12]; and for the vector case without absolute value, see [22].”
- Rectify Heterogeneous Models with Semantic Mapping (2018, methodology): “generalization error when learning the model W , which is consistent with (Bartlett & Mendelson, 2002; Maurer, 2016).”
- Combating the Compounding-Error Problem with a Multi-step Model (2019, background): “First note that, due to the definition of sup , we clearly have: (cid:13) (cid:13) We define Φ to be the sup in the right hand side of the above bound: (1) Φ( s (cid:13)(cid:13)(cid:13) Due to Corollary 4 of Maurer [2016]: | D | .”
- Structured Prediction Theory Based on Factor Graph Complexity (2016, methodology): “(2)A result similar to Lemma 5 has also been recently proven independently in [Maurer, 2016].”
- Heterogeneous Few-Shot Model Rectification With Semantic Mapping (2020, unknown): “Define where the constant ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi p Theorem 1 provides an Oð 1 ffiffiffi N p Þ convergence rate for the generalization gap when learning the model W , which is consistent with [17], [18].”
- Combined Scaling for Open-Vocabulary Image Classification (2022, unknown): “Using a vector-contraction inequality, i.e., Corollary 4 of (Maurer, 2016) with the additional expectation of both sides of the inequality, we have that This proves the first statement.”
- On Measuring Excess Capacity in Neural Networks (2022, methodology): “…as To derive generalization bounds via classical Rademacher complexity analysis [33], without having to resort to vector-contraction inequalities [32], we consider the hypothesis class (3) Then, defining the empirical Rademacher complexity of any class H of real-valued functions as with iid…”