mlsanityData to 7 Oct 2026

On the Rademacher Complexity of Linear Hypothesis Sets

arXiv 2007.11045 ↗First posted 21 Jul 2020cs.LG stat.MLcited by 17

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 3; 2023: 4; 2024: 3; 2025: 3; 2026: 2.

17 papers.

Sort:

By area:

  1. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 76
  2. 2023Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcarecited by 41
  3. 2022Adversarial Rademacher Complexity of Deep Neural Networkscited by 18
  4. 2022Unifying and Boosting Gradient-Based Training-Free Neural Architecture Searchcited by 17
  5. 2022Bounding the Rademacher Complexity of Fourier neural operatorscited by 16
  6. 2023An Adaptive Algorithm for Learning with Unknown Distribution Driftcited by 14
  7. 2023PILLAR: How to make semi-private learning more effectivecited by 10
  8. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  9. 2021Domain Invariant Adversarial Learningcited by 7
  10. 2021Local and Global Uniform Convexity Conditionscited by 4
  11. 2025Learning Laplacian Positional Encodings for Heterophilous Graphscited by 4
  12. 2026Transfer Learning Through Conditional Quantile Matchingcited by 1
5 more
  1. 2024Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attackscited by 0
  2. 2024Testing Credibility of Public and Private Surveys through the Lens of Regressioncited by 0
  3. 2025Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernelcited by 0
  4. 2025Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regressioncited by 0
  5. 2026Rationality Measurement and Theory for Reinforcement Learning Agentscited by 0