Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

Abstract

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(log² n) bound holds already at scale γ/2, while an O(log n) bound holds at scale 2γ. We further show that the O(log² 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.

Risk-Sensitive Stochastic Optimal Control on Positive Cones
Mohamad Al Ahdab, John-Josef Leth
arXiv4 Nov 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
List coloring uncrowded hypergraphs at the shattering threshold
Abhishek Dhawan, Abhishek Methuku, Minh-Quan Vo
arXiv24 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Combinatorial Characterizations of the Learnability of Conditional Distributions
Mihir Dhanakshirur, Ambuj Tewari
arXiv22 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
A Spectral Boundary for Independence Learnability
Senhan Yao, Yuxin Zhou
arXiv28 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Optimal Initialization Scale for Neural Networks with Locally Quadratic Loss Landscapes: An SGD Dynamics Perspective
Hiroshi Horii, Sothea Has
IEEE Transactions on Neural Networks and Learning Systems17 Aug 2026Peer-reviewedPublisher termsFull textStatisticsHAL

Cite

BibTeX RIS

BibTeX

@misc{aiyer2026scalesensitive,
  title = {{Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale}},
  author = {Shashaank Aiyer and Yishay Mansour and Shay Moran and Han Shao and Tom Waknine},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.13684},
  eprint = {2605.13684},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.13684},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
AU  - Shashaank Aiyer
AU  - Yishay Mansour
AU  - Shay Moran
AU  - Han Shao
AU  - Tom Waknine
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2605.13684
UR  - https://arxiv.org/abs/2605.13684
AB  - 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(log^2 n) bound holds already at scale γ/2, while an O(log n) bound holds at scale 2γ. We further show that the O(log^2 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.
ER  -

Abstract

Related

Cite