# Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 37 references that are in the map.
- First posted on arXiv 13 May 2026.

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

- [MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers](https://mlsanity.com/paper/2102.01454/) (2021)
- [What is Wrong with Perplexity for Long-context Language Modeling?](https://mlsanity.com/paper/2410.23771/) (2024)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Can Perplexity Reflect Large Language Model's Ability in Long Text Understanding?](https://mlsanity.com/paper/2405.06105/) (2024)
- [Sparse Text Generation](https://mlsanity.com/paper/2004.02644/) (2020)
- [Sample Compression for Real-Valued Learners](https://mlsanity.com/paper/1805.08254/) (2018)
- [The Optimal Approximation Factor in Density Estimation](https://mlsanity.com/paper/1902.05876/) (2019)
- [Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions](https://mlsanity.com/paper/2304.11059/) (2023)
- [Agnostic Sample Compression Schemes for Regression](https://mlsanity.com/paper/1810.01864/) (2018)
- [Primal and Dual Combinatorial Dimensions](https://mlsanity.com/paper/2108.10037/) (2021)
- [Fat-Shattering Dimension of k-fold Aggregations](https://mlsanity.com/paper/2110.04763/) (2021)
- [An Improved Uniform Convergence Bound with Fat-Shattering Dimension](https://mlsanity.com/paper/2307.06644/) (2023)
- [A Theoretical Framework for Statistical Evaluability of Generative Models](https://mlsanity.com/paper/2604.05324/) (2026)

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

- [An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension](https://mlsanity.com/paper/2609.29696/) (2026)

## Abstract (arXiv)

We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class and every γ>0, uniform convergence at scale γ, agnostic learnability at scale γ/2, and finiteness of the fat-shattering dimension at every scale γ'>γ are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press 1999) on the precise scales governing learnability, refuting a conjecture attributed there to Phil Long that a multiplicative 2-factor gap is unavoidable, and improves the upper bounds of Bartlett and Long (JCSS 1998), which incur such a loss. The key technical ingredient is a direct bound on empirical ℓ_∞ covering numbers, avoiding the standard detour through packing numbers. As a consequence, we obtain sharp asymptotic metric-entropy bounds in terms of the fat-shattering scale γ: an O(log2 n) bound holds already at scale γ/2, while an O(log n) bound holds at scale 2γ. We further show that the O(log2 n) bound is sometimes tight. These results resolve open questions by Alon et al. (JACM 1997) and Rudelson and Vershynin (Ann. of Math. 2006). As an application, we establish a sharp dichotomy for bounded integral probability metrics: every such IPM is either estimable or cannot be weakly evaluated within any multiplicative factor c<3, while 3-weak evaluability always holds, resolving an open question from Aiyer et al. (ICML 2026). We also highlight several open questions on quantitative sample complexity and evaluability.