Technical Summary: Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

Problem Statement

This paper addresses fundamental questions in statistical learning theory regarding real-valued function classes. Specifically, it investigates the precise relationship between three core concepts: agnostic learnability, uniform convergence, and the fat-shattering dimension (a scale-sensitive generalization of the VC dimension).

While the "Fundamental Theorem of PAC Learning" establishes the equivalence of these notions for binary classification, the real-valued setting has historically exhibited a gap. Prior work (e.g., Bartlett and Long, 1998) demonstrated that a finite $\gamma$-fat-shattering dimension implies uniform convergence and learnability, but only at a scale of $2\gamma$ (or $c\gamma$ for $c>2$). This left open the question of whether a multiplicative factor of 2 in the scale is unavoidable, a conjecture attributed to Phil Long in the textbook by Anthony and Bartlett (1999).

Furthermore, the paper addresses the behavior of metric entropy (logarithm of covering numbers) in relation to the fat-shattering dimension. Previous results (Alon et al., 1997; Rudelson and Vershynin, 2006) provided bounds on metric entropy but left open whether the dependence on the sample size $n$ could be improved from $O(\log^2 n)$ to $O(\log n)$ at optimal scales, and whether the scale factors in these bounds could be tightened.

Finally, the paper applies these theoretical insights to the evaluability and estimability of generative models using Integral Probability Metrics (IPMs). A recent dichotomy for binary test functions (Aiyer et al., 2026) suggested that such metrics are either estimable or weakly evaluable with an optimal scale of $c=3$. Extending this to real-valued functions was hindered by the aforementioned scale-gap in uniform convergence results.

Methodology

The authors' primary technical innovation is a direct bound on empirical $\ell_\infty$ covering numbers, bypassing the standard detour through packing numbers.

1. Direct Covering via Partial Concept Classes:
   Instead of relating covering numbers to packing numbers (which inherently incurs a scale loss), the authors utilize the theory of partial concept classes (Lon01; AHHM22). They map real-valued functions to partial binary functions based on thresholds relative to the scale $\gamma$. By bounding the VC dimension of these induced partial classes, they construct explicit covers of sub-exponential size. This allows them to derive covering number bounds directly at the optimal scale $\gamma/2$ rather than $2\gamma$.

2. Iterative Refinement:
   To achieve bounds at scales arbitrarily close to $\gamma/2$, the authors employ an iterative construction. Starting from a coarse cover, they recursively refine the boxes, reducing the radius geometrically while controlling the growth of the cover size. This yields a bound on the metric entropy $H(F, \gamma/2 + \epsilon, n)$ that is sublinear in $n$.

3. Sample Compression and Dual Classes:
   For the regime where the scale is large ($\gamma > 2\gamma^*$), the authors utilize sample compression schemes. They leverage the fact that the dual class of a function class with finite fat-shattering dimension also satisfies uniform convergence (a result derived from their main theorem) to sparsify distributions and construct constant-size compression schemes. This leads to $O(\log n)$ entropy bounds.

4. Reduction to Total Variation:
   In the application to evaluability, the authors construct a reduction from general IPMs with infinite fat-shattering dimension to the Total Variation (TV) distance setting. They carefully construct mixtures of distributions over shattered sets to show that the IPM behaves asymptotically like the TV distance, preserving the optimal scale constants.

Key Contributions and Results

1. Resolution of the Scale Gap (Theorem 1)

The paper establishes an exact analogue of the Fundamental Theorem of PAC learning for real-valued classes. For a bounded function class $F$ and scale $\gamma > 0$, the following are equivalent:

1. $F$ is $\gamma/2$-learnable.
2. $F$ satisfies $\gamma$-uniform convergence.
3. For every $\gamma' > \gamma$, the $\gamma'$-fat-shattering dimension of $F$ is finite.

Significance: This result refutes the conjecture that a factor-2 gap is unavoidable. It proves that learnability and uniform convergence hold at the optimal scale $\gamma/2$ (for learnability) and $\gamma$ (for convergence), provided the fat-shattering dimension is finite at any scale strictly larger than $\gamma$.

2. Sharp Metric Entropy Bounds (Theorem 2)

The paper provides a complete characterization of the growth of metric entropy $H(F, \gamma, n)$ based on the critical scale $\gamma^* = \inf\{\gamma : \text{fat}_\gamma(F) < \infty\}$:

• Linear Regime ($\gamma < \gamma^*/2$): $H(F, \gamma, n) = \Theta(n)$.
• Intermediate Regime ($\gamma^*/2 < \gamma \le 2\gamma^*$): $H(F, \gamma, n) = O(\log^2 n)$. The paper shows this bound is tight (up to lower-order terms) for $\gamma \in (\gamma^*/2, \gamma^*)$, resolving a question by Alon et al. (1997) regarding the necessity of the $\log^2 n$ factor.
• Large Scale Regime ($\gamma > 2\gamma^*$): $H(F, \gamma, n) = O(\log n)$. This confirms that the exponent can be reduced to 1 at sufficiently large scales, resolving a question by Rudelson and Vershynin (2006).

3. Dichotomy for Evaluability of Generative Models (Theorem 3 & Proposition 1)

Applying the sharp scale-sensitive results, the paper establishes a dichotomy for bounded Integral Probability Metrics (IPMs):

• If the fat-shattering dimension is finite for all $\gamma > 0$, the IPM is estimable (and thus strongly evaluable with $c=1$).
• If the fat-shattering dimension is infinite for some $\gamma \in (0, 1/2)$, the IPM is weakly evaluable with optimal scale $c=3$, but not for any $c < 3$.

Significance: This extends the binary dichotomy from Aiyer et al. (2026) to real-valued functions. The proof critically relies on the authors' ability to establish uniform convergence at scale $\gamma$ without the factor-2 loss; without this, the argument for the optimal scale $c=3$ would fail.

4. Closure Properties

The paper demonstrates that the properties of $\gamma$-learnability and $\gamma$-uniform convergence are invariant under:

• Duality: The dual class of a uniformly convergent class is also uniformly convergent.
• Aggregation: Aggregating classes via 1-Lipschitz functions preserves uniform convergence at the same scale.

Significance and Claims

The authors claim that their work resolves several long-standing open questions in learning theory:

1. Refutation of the Factor-2 Conjecture: By proving that learnability and uniform convergence hold at the optimal scales, the paper definitively answers the question posed by Anthony and Bartlett (1999), showing the factor-2 gap is not inherent.
2. Sharp Entropy Bounds: The paper settles the precise dependence of metric entropy on the sample size $n$ and the scale $\gamma$, clarifying exactly when $O(\log n)$ bounds are achievable versus when $O(\log^2 n)$ is necessary.
3. Qualitative Characterization of Evaluability: The paper argues that the quantitative improvement from a factor of 2 to 1 in the scale of uniform convergence unlocks a qualitative characterization of generative model evaluation, establishing a sharp dichotomy between estimability and weak evaluability with $c=3$.

The authors note that while they resolve the asymptotic behavior and the existence of the dichotomy, the precise behavior of entropy in the intermediate range $\gamma^* < \gamma \le 2\gamma^*$ and sharp sample complexity bounds for learning at the optimal scale remain open problems. Additionally, the relationship between fat-shattering dimension and covering numbers under other $\ell_p$ metrics is left for future investigation.