# A vector-contraction inequality for Rademacher complexities

arXiv: https://arxiv.org/abs/1605.00251 · HTML: https://mlsanity.com/paper/1605.00251/

## Key facts

- Cited by 142 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2016.

## Built on by (most cited first, 30 of 142)

- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Combined Scaling for Zero-shot Transfer Learning](https://mlsanity.com/paper/2111.10050/) (2021)
- [LoRA Training in the NTK Regime has No Spurious Local Minima](https://mlsanity.com/paper/2402.11867/) (2024)
- [Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning](https://mlsanity.com/paper/2103.13883/) (2021)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [Learning with Multiclass AUC: Theory and Algorithms](https://mlsanity.com/paper/2107.13171/) (2021)
- [Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior](https://mlsanity.com/paper/2307.14619/) (2023)
- [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024)
- [Learning from Label Proportions by Learning with Label Noise](https://mlsanity.com/paper/2203.02496/) (2022)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Revisiting Discriminative vs. Generative Classifiers: Theory and Implications](https://mlsanity.com/paper/2302.02334/) (2023)
- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Generalizing Off-Policy Learning under Sample Selection Bias](https://mlsanity.com/paper/2112.01387/) (2021)
- [Bounding the Rademacher Complexity of Fourier neural operators](https://mlsanity.com/paper/2209.05150/) (2022)
- [An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models](https://mlsanity.com/paper/2212.14852/) (2022)
- [Decision-Focused Learning with Directional Gradients](https://mlsanity.com/paper/2402.03256/) (2024)
- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [Towards Understanding How Transformers Learn In-context Through a Representation Learning Lens](https://mlsanity.com/paper/2310.13220/) (2023)
- [Size-invariance Matters: Rethinking Metrics and Losses for Imbalanced Multi-object Salient Object Detection](https://mlsanity.com/paper/2405.09782/) (2024)
- [Representing Random Utility Choice Models with Neural Networks](https://mlsanity.com/paper/2207.12877/) (2022)
- [Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspective](https://mlsanity.com/paper/2403.14917/) (2024)
- [Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification](https://mlsanity.com/paper/2102.00678/) (2021)
- [Deep Learning From Crowdsourced Labels: Coupled Cross-entropy Minimization, Identifiability, and Regularization](https://mlsanity.com/paper/2306.03288/) (2023)
- [Score-based generative models break the curse of dimensionality in learning a family of sub-Gaussian probability distributions](https://mlsanity.com/paper/2402.08082/) (2024)
- [Shallow diffusion networks provably learn hidden low-dimensional structure](https://mlsanity.com/paper/2410.11275/) (2024)
- [Generalization Error Bounds for Iterative Recovery Algorithms Unfolded as Neural Networks](https://mlsanity.com/paper/2112.04364/) (2021)
- [Learning from Aggregated Data: Curated Bags versus Random Bags](https://mlsanity.com/paper/2305.09557/) (2023)
- [Non-Parametric Representation Learning with Kernels](https://mlsanity.com/paper/2309.02028/) (2023)

## Abstract (arXiv)

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.