Uniform convergence at optimal rate and scale
Abstract
Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension d, the sharp worst-case sample complexity for additive error ε is of order d/ε2. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale γ. The challenge is to achieve error γ+ε with order d/ε2 samples, matching the sample bound for binary classes, where d is now the fat-shattering dimension at scale γ. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns ε-nets with margin. A classical ε-net intersects every set of mass at least ε in a prescribed family; we allow the net to intersect a slightly enlarged version of each such set. Remarkably, this relaxation permits bounds independent of the ambient dimension in natural geometric settings. Second, we derive improved covering bounds in both discrete and real-valued settings: we extend Haussler's covering lemma to partial concept classes and use this extension to obtain ℓ2 covers at the optimal scale for real-valued function classes. Third, we obtain a chaining bound at the optimal scale by aligning the covers so that successive approximations become increasingly close to one another.
Related
- Uniform transport processes and the Brownian sheet:the one-parameter rate of convergence is preserved
- Optimal rates of uniform convergence for weighted Birkhoff averages via almost all rotations
- Incompressible Navier-Stokes Limit of the Relativistic Boltzmann Equation with the Optimal Convergence Rate
- Optimal Design of Distributed Inexact Gradient Tracking: Exact Worst-case Convergence Rate and Explicit Parameters
- Joint Uniform Continuity of Reduced Free Products for strong convergence
BibTeX
@misc{alon2026uniform,
title = {{Uniform convergence at optimal rate and scale}},
author = {Noga Alon and Steve Hanneke and Shay Moran and Tom Waknine},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24336},
eprint = {2610.24336},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24336},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Uniform convergence at optimal rate and scale
AU - Noga Alon
AU - Steve Hanneke
AU - Shay Moran
AU - Tom Waknine
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24336
UR - https://arxiv.org/abs/2610.24336
AB - Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension d, the sharp worst-case sample complexity for additive error ε is of order d/ε^2. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale γ. The challenge is to achieve error γ+ε with order d/ε^2 samples, matching the sample bound for binary classes, where d is now the fat-shattering dimension at scale γ. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns ε-nets with margin. A classical ε-net intersects every set of mass at least ε in a prescribed family; we allow the net to intersect a slightly enlarged version of each such set. Remarkably, this relaxation permits bounds independent of the ambient dimension in natural geometric settings. Second, we derive improved covering bounds in both discrete and real-valued settings: we extend Haussler's covering lemma to partial concept classes and use this extension to obtain ℓ_2 covers at the optimal scale for real-valued function classes. Third, we obtain a chaining bound at the optimal scale by aligning the covers so that successive approximations become increasingly close to one another.
ER -