# Do we really need the Rademacher complexities?

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 27 references that are in the map.
- First posted on arXiv 21 Feb 2025.

## Builds on (most cited first, 4 of 4)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails](https://mlsanity.com/paper/2205.08494/) (2022)
- [`local' vs. `global' parameters -- breaking the gaussian complexity barrier](https://mlsanity.com/paper/1504.02191/) (2015)

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

- [Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits](https://mlsanity.com/paper/2602.03970/) (2026)
- [A Closed-Form Formula for Consistent Lipschitz Regression on Metric Spaces with Sparse Neural Network Realizations](https://mlsanity.com/paper/2609.03129/) (2026)

## Abstract (arXiv)

We study the fundamental problem of learning with respect to the squared loss in a convex class. The state-of-the-art sample complexity estimates in this setting rely on Rademacher complexities, which are generally difficult to control. We prove that, contrary to prevailing belief and under minimal assumptions, the sample complexity is not governed by the Rademacher complexities but rather by the behaviour of the limiting gaussian process. In particular, all such learning problems that have the same L2-structure -- even those with heavy-tailed distributions -- share the same sample complexity. This constitutes the first universality result for general convex learning problems. The proof is based on a novel learning procedure, and its performance is studied by combining optimal mean estimation techniques for real-valued random variables with Talagrand's generic chaining method.