# On the Rademacher Complexity of Linear Hypothesis Sets

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2020.

## Built on by (most cited first, 17 of 17)

- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare](https://mlsanity.com/paper/2305.01738/) (2023)
- [Adversarial Rademacher Complexity of Deep Neural Networks](https://mlsanity.com/paper/2211.14966/) (2022)
- [Unifying and Boosting Gradient-Based Training-Free Neural Architecture Search](https://mlsanity.com/paper/2201.09785/) (2022)
- [Bounding the Rademacher Complexity of Fourier neural operators](https://mlsanity.com/paper/2209.05150/) (2022)
- [An Adaptive Algorithm for Learning with Unknown Distribution Drift](https://mlsanity.com/paper/2305.02252/) (2023)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Domain Invariant Adversarial Learning](https://mlsanity.com/paper/2104.00322/) (2021)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [Transfer Learning Through Conditional Quantile Matching](https://mlsanity.com/paper/2602.02358/) (2026)
- [Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attacks](https://mlsanity.com/paper/2402.03576/) (2024)
- [Testing Credibility of Public and Private Surveys through the Lens of Regression](https://mlsanity.com/paper/2410.05458/) (2024)
- [Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel](https://mlsanity.com/paper/2506.11357/) (2025)
- [Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression](https://mlsanity.com/paper/2508.20616/) (2025)
- [Rationality Measurement and Theory for Reinforcement Learning Agents](https://mlsanity.com/paper/2602.04737/) (2026)

## Abstract (arXiv)

Linear predictors form a rich class of hypotheses used in a variety of learning algorithms. We present a tight analysis of the empirical Rademacher complexity of the family of linear hypothesis classes with weight vectors bounded in ℓp-norm for any p ≥ 1. This provides a tight analysis of generalization using these hypothesis sets and helps derive sharp data-dependent learning guarantees. We give both upper and lower bounds on the Rademacher complexity of these families and show that our bounds improve upon or match existing bounds, which are known only for 1 ≤ p ≤ 2.