Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
Introduces scale-sensitive shattering, proving equivalence between uniform convergence, learnability, and fat-shattering dimension at optimal scales.
Key Findings
Methodology
The paper employs a novel approach by directly bounding empirical ℓ∞ covering numbers, avoiding traditional packing number methods. Using partial concept classes and geometric recursive constructions, it derives sharp bounds at the optimal scale. The core algorithm involves discretizing function classes via disambiguation of partial functions, leading to precise estimates of covering numbers at scales γ/2 and 2γ. This method overcomes previous limitations, establishing tight asymptotic bounds of O(log^2 n) and O(log n) respectively, and confirming their tightness through constructed examples. The approach fundamentally advances the understanding of scale-sensitive uniform convergence and learnability, providing a unified framework that refutes prior conjectures about unavoidable scale gaps.
Key Results
- At scale γ/2, the empirical ℓ∞ covering number's log complexity is bounded by O(log^2 n), which is sometimes tight, improving previous results by a factor of two. For scales above 2γ, the bound reduces to O(log n), and this is shown to be optimal via explicit function class constructions. These results resolve longstanding open questions posed by Alon et al. and Rudelson and Vershynin, establishing the precise relationship between fat-shattering dimension and uniform convergence at the optimal scale.
- The paper proves that for any bounded real-valued function class, γ-fat-shattering dimension being finite is equivalent to γ-uniform convergence and γ-agnostic learnability. This completes the scale-sensitive generalization of the classical PAC theorem, providing a rigorous foundation for understanding learnability in the real-valued setting. The results also extend to the evaluation of integral probability metrics (IPMs), where a dichotomy is established: such metrics are either estimable or cannot be weakly evaluated within any c<3 factor, with 3-weak evaluability always holding.
- The theoretical advancements have practical implications for model evaluation, especially in generative modeling. The sharp bounds enable precise assessment of whether models truly generalize or merely memorize training data, with the dichotomy clarifying the limits of evaluation procedures based on finite samples. These insights are crucial for developing robust, scalable evaluation frameworks in machine learning applications.
Significance
This work marks a significant breakthrough by establishing an exact scale-sensitive equivalence between fat-shattering dimension, uniform convergence, and learnability, effectively refuting the long-standing conjecture that a factor-2 gap is unavoidable. The results provide a refined understanding of the fundamental limits of learning real-valued functions, with implications spanning theoretical foundations and practical model evaluation. By delivering tight bounds at the optimal scale, the paper enhances the precision of sample complexity estimates and guides the design of scalable learning algorithms. Its extension to integral probability metrics offers a rigorous basis for evaluating generative models, addressing critical challenges in AI safety and reliability. Overall, this research significantly advances the theoretical landscape of statistical learning, opening new avenues for multi-scale analysis and application in complex, high-dimensional settings.
Technical Contribution
The primary technical innovation is the direct bounding of empirical ℓ∞ covering numbers through a novel partial concept class disambiguation technique, bypassing the traditional reliance on packing number bounds. This approach enables the derivation of sharp asymptotic bounds at the optimal scales, specifically achieving O(log^2 n) at γ/2 and O(log n) at 2γ. The method involves geometric recursive refinement of covers, leveraging the finite fat-shattering dimension to control the complexity at each scale. It also establishes the equivalence between finite fat-shattering dimension and uniform convergence/learnability at the same scale, completing the scale-sensitive generalization of the classical PAC theorem. Additionally, the paper extends these insights to integral probability metrics, proving a dichotomy between estimability and weak evaluability, with precise bounds on the evaluation factor c.
Novelty
This research is the first to establish the exact equivalence between finite fat-shattering dimension and uniform convergence at the optimal scale, refuting the conjecture that a factor-2 gap is unavoidable. The direct bounding of empirical ℓ∞ covering numbers, without passing through packing bounds, represents a significant methodological advance. The results provide the tightest possible asymptotic bounds, resolving open questions by Alon et al. and Rudelson and Vershynin, and extending the theory to evaluation of integral probability metrics. This work fundamentally shifts the understanding of scale-dependent learnability and evaluation in real-valued function classes.
Limitations
- The current results focus on infinite, continuous domains; their extension to finite or high-dimensional settings remains to be explored. Practical computation of the bounds may be challenging due to the complexity of the geometric recursive constructions.
- While the bounds are tight in theory, real-world functions may not reach these limits, and the assumptions of boundedness and finite fat-shattering dimension may restrict applicability. Further work is needed to adapt these results to noisy or unbounded scenarios.
- The extension to other norms (beyond ℓ∞) and more general function classes is not fully addressed, leaving open questions about broader applicability and the impact of different metric choices.
Future Work
Future research will aim to develop practical algorithms based on the theoretical bounds, enabling scalable model evaluation and learning in high-dimensional and real-world data. Extending the framework to other norms and more complex function classes, such as deep neural networks, is a key direction. Additionally, exploring the finite domain setting, refining sample complexity bounds, and integrating these insights into robust evaluation protocols for generative models will be crucial. The potential for multi-scale analysis in transfer learning and domain adaptation also presents promising avenues for further investigation.
AI Executive Summary
This paper advances the theoretical understanding of real-valued function classes by establishing a scale-sensitive framework linking uniform convergence, learnability, and fat-shattering dimension. Unlike traditional binary classification results, the authors focus on the continuous setting, where the scale of approximation critically influences learnability. They introduce a novel approach to directly bound empirical ℓ∞ covering numbers, bypassing the limitations of packing number methods. This innovation yields sharp asymptotic bounds: an O(log^2 n) complexity at scale γ/2 and an O(log n) complexity at scale 2γ, with proofs of tightness, thus resolving longstanding open questions.
The core theoretical contribution is the proof that finite fat-shattering dimension at scale γ is equivalent to γ-uniform convergence and γ-agnostic learnability, completing the scale-sensitive generalization of the classical PAC theorem. This result refutes the conjecture that a factor-2 gap in scales is unavoidable, providing a precise characterization of the learnability boundary. The work also extends to integral probability metrics (IPMs), establishing a dichotomy: such metrics are either estimable or cannot be weakly evaluated within any c<3 factor, with 3-weak evaluability always achievable.
These insights have profound implications for machine learning, especially in evaluating generative models. The sharp bounds enable reliable assessment of whether models truly generalize or merely memorize data, addressing critical issues in AI safety and robustness. The theoretical framework opens new avenues for multi-scale analysis, with potential applications in deep learning, transfer learning, and domain adaptation. Future work will focus on practical algorithms, broader function classes, and finite domain extensions, aiming to translate these fundamental insights into scalable, real-world solutions.
Deep Dive
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 $\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 $γ$: 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.