Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, Tom Waknine · 2026

Read Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale by Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, Tom Waknine (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13684.txt.

Introduction

Shashaank Aiyer and four colleagues study the best scale at which real-valued function classes show uniform convergence and learnability. Their main result extends the fundamental PAC learning theorem to scales. Uniform convergence at scale gamma, agnostic learnability at scale gamma over two, and finite fat-shattering dimension above gamma are equivalent. That answers an Anthony and Bartlett question on precise learnability scales, refuting a Phil Long conjecture that a two-factor gap is unavoidable.

Catalog record

CREATORShashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, Tom Waknine
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92219
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13684

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, Tom Waknine 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 ℱ \mathcal{F} and every γ > 0 \gamma>0 , uniform convergence at scale γ \gamma , agnostic learnability at scale γ / 2 \gamma/2 , and finiteness of the fat-shattering dimension at every scale γ ′ > γ \gamma^{\prime}>\gamma are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press ’99) 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 ’98), which incur such a loss. The key technical ingredient is a direct bound on empirical ℓ ∞ \ell_{\infty} 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 γ \gamma : an O ⁡ ( log 2 ⁡ n ) O(\log^{2}n) bound holds already at scale γ / 2 \gamma/2 , while an O ⁡ ( log ⁡ n ) O(\log n) bound holds at scale 2 ​ γ 2\gamma . We further show that the O ⁡ ( log 2 ⁡ n ) O(\log^{2}n) bound is sometimes tight. These results resolve open questions by Alon et al. (JACM ’97) and Rudelson and Vershynin (Ann. of Math. ’06). 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 c<3 , while 3 3 -weak evaluability always holds, resolving an open question from Aiyer et al. (ICML ’26). We also highlight several open questions on quantitative sample complexity and evaluability. † † Authors are ordered alphabetically. † † Emails: [email protected] , [email protected] , [email protected] , [email protected] , [email protected] 1 Introduction One of the central results in statistical learning theory is the fundamental theorem of PAC learning, which establishes an equivalence between three different notions: agnostic learnability, uniform convergence, and finiteness of the VC dimension. In the binary classification setting, this theorem provides a complete characterization of when a class of functions can be learned from data in a distribution-free manner, and serves as a cornerstone of learning theory 37 ; 10 . A natural extension of this framework considers real-valued function classes \mathcal{F} , where predictions are no longer binary but continuous. In this setting the VC dimension is replaced by a scale-sensitive extension called the fat-shattering dimension (defined below). This notion was introduced in learning theory by Kearns and Schapire 20 , and also appears in approximation theory (see Lorentz 23 , and Tikhomirov 36 who attributes it to earlier work of Kolmogorov). Understanding the relationship between learnability, fat-shattering, and uniform convergence in the real-valued setting has been a long-standing goal. The classical no-free-lunch argument shows that if the \gamma -fat-shattering dimension is unbounded, then the class is not learnable at scale \gamma/2 and does not satisfy uniform convergence at scale \gamma , reflecting a scale-sensitive version of the no-free-lunch principle. In the opposite direction, Alon et al. 2 showed that finite \gamma -fat-shattering dimension implies uniform convergence (and hence learnability) at scale c\gamma for some universal constant c\geq 10 . This was later improved by Bartlett and Long 9 , who established the same implication for any constant c>2 . However, it remained open whether the fat-shattering dimension provides a sharp characterization of learnability and uniform convergence at the optimal scale. This question has been investigated in a sequence of works, and is discussed in detail in the textbook of Anthony and Bartlett 4 (see Section 12.7), where it is noted that the gap between the necessary and sufficient scales may be unavoidable - a conjecture attributed there to Phil Long. For additional background, historical context, and a gentle technical introduction, we refer the reader to Chapters 11 and 12 of that book. Our first main result resolves this question by establishing an exact scale-sensitive analogue of the fundamental theorem of PAC learning in the real-valued setting, thereby refuting the conjecture that the factor- 2 gap is unavoidable. To state the result, we briefly recall the relevant notions. Let \mathcal{X} be a domain, let \mathcal{F}\subset[-R,R]^{\mathcal{X}} be a class of bounded real-valued functions over \mathcal{X} , and let \gamma>0 . We say that \mathcal{F} satisfies \gamma -uniform convergence if for every \varepsilon,\delta>0 there exists m such that for every distribution q over \mathcal{X} , with probability at least 1-\delta over a sample S\sim q^{n} of size n\geq m , \sup_{f\in\mathcal{F}}\left|\mathbb{E}_{x\sim q}[f(x)]-\frac{1}{n}\sum_{x\in S}f(x)\right|\leq\gamma+\varepsilon. We say that \mathcal{F} is \gamma -learnable if there exists a learner \mathcal{A} (that is, a mapping from samples to hypotheses) such that for every \varepsilon,\delta>0 there exists m such that for every distribution q over \mathcal{X}\times[-R,R] , with probability at least 1-\delta over S\sim q^{n} of size n\geq m , \underset{(x,y)\sim q}{\mathbb{E}}\left[\bigl|\mathcal{A}_{S}(x)-y\bigr|\right]\leq\inf_{f\in\mathcal{F}}\underset{(x,y)\sim q}{\mathbb{E}}\left[|f(x)-y|\right]+\gamma+\varepsilon, where \mathcal{A}_{S} denotes the hypothesis output by \mathcal{A} on input sample S . Finally, the \gamma -fat-shattering dimension of \mathcal{F} , denoted \mathrm{fat}_{\gamma}(\mathcal{F}) , is the largest integer d for which there exist points x_{1},\dots,x_{d}\in\mathcal{X} and thresholds r_{1},\dots,r_{d}\in\mathbb{R} such that for every b\in\{\pm 1\}^{d} there exists f\in\mathcal{F} satisfying f(x_{i})\geq r_{i}+\tfrac{\gamma}{2}\ \text{ if }b_{i}=+1,\quad\text{and}\quad f(x_{i})\leq r_{i}-\tfrac{\gamma}{2}\ \text{ if }b_{i}=-1. If for arbitrarily large d there exist points x_{1},\dots,x_{d} and thresholds r_{1},\dots,r_{d} satisfying the above, we say that \mathrm{fat}_{\gamma}(\mathcal{F})=\infty . When \mathcal{F} consists of \{0,1\} -valued functions and the scale \gamma<1 , the fat-shattering dimension coincides with the VC dimension, and these notions reduce to their classical binary counterparts. Thus, the real-valued framework can be viewed as a strict generalization of the binary setting. Theorem 1 . Let \mathcal{F}\subset[-R,R]^{\mathcal{X}} be a bounded function class and let \gamma>0 . Then, the following are equivalent: 1. \mathcal{F} is \frac{\gamma}{2} -learnable; 2. \mathcal{F} satisfies \gamma -uniform convergence; 3. for every \gamma^{\prime}>\gamma , the \gamma^{\prime} -fat-shattering dimension of \mathcal{F} is finite. The proof appears in Section 4.2 . The challenging directions in Theorem 1 are (3)\Rightarrow(1) and (3)\Rightarrow(2) . The converse implications (1)\Rightarrow(3) and (2)\Rightarrow(3) follow from standard no-free-lunch arguments, see, e.g., 4 ; 9 . Covering Numbers. The derivation of uniform convergence from finite combinatorial dimension follows the classical approach of Vapnik and Chervonenkis. The argument proceeds via symmetrization (also known as double sampling), which reduces the problem to controlling the behavior of the class on a finite sample. In the binary case, the behavior of the class is controlled using the Sauer-Shelah Lemma 34 , which bounds the number of distinct labelings induced by the class on a sample of size n . This combinatorial bound allows one to replace an infinite union bound with a finite one. In the real-valued setting, the role of the Sauer–Shelah Lemma is played by covering numbers. Concretely, for \mathcal{F}\subset[-R,R]^{\mathcal{X}} , the empirical \ell_{\infty} covering number N(\mathcal{F},\gamma,n) is the smallest integer N for which for any sequence x_{1},\dots,x_{n} , there exist functions g_{1},\dots,g_{N}:\mathcal{X}\to\mathbb{R} such that for every f\in\mathcal{F} , there exists i\in[N] satisfying \max_{j\in[n]}|f(x_{j})-g_{i}(x_{j})|\leq\gamma. The quantity H(\mathcal{F},\gamma,n):=\log N(\mathcal{F},\gamma,n) is

Read the complete text