Uniform convergence at optimal rate and scale

Noga Alon; Steve Hanneke; Shay Moran; Tom Waknine

cs.LGOct 17, 2026

Uniform convergence at optimal rate and scale

Authors: Noga Alon, Steve Hanneke, Shay Moran, Tom Waknine

Organizations: Department of Mathematics, Princeton University, Princeton, NJ, USA. · Department of Computer Science, Purdue University, West Lafayette, IN, USA. · Departments of Mathematics, Computer Science, and Data and Decision Sciences, Technion–Israel Institute of Technology; Google Research. · Department of Mathematics, Technion–Israel Institute of Technology, Haifa, Israel.

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 $\varepsilon$ is of order $d/\varepsilon^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 $γ+\varepsilon$ with order $d/\varepsilon^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 $\varepsilon$ -nets with margin. A classical $\varepsilon$ -net intersects every set of mass at least $\varepsilon$ 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 $\ell_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.

Figures & tables

Reference	Metric	Covering radius	Entropy bound	$n$ -free
Alon et al. Alon et al. (1997)	$\ell_{\infty}$	$2\gamma$	$\log N_{\infty}(V,2\gamma)=O\left(d\log\frac{en}{\gamma}\log\frac{en}{d\gamma}\right)$	No
Bartlett, Kulkarni, and Posner Bartlett et al. (1997)	$\ell_{1}$	$C\gamma$	$\log N_{1}(V,C\gamma)=O\left(d\log^{2}\frac{e}{\gamma}\right)$	Yes
Bartlett and Long Bartlett and Long (1998)	$\ell_{1}$	$\gamma+\varepsilon$	$\log N_{1}(V,\gamma+\varepsilon)=O\left(d\log\frac{1}{\varepsilon}\log^{2}(en)\right)$	No
Mendelson and Vershynin Mendelson and Vershynin (2003)	$\ell_{2}$	$C\gamma$	$\log N_{2}(V,C\gamma)=O\left(d\log\frac{e}{\gamma}\right)$	Yes
Rudelson and Vershynin Rudelson and Vershynin (2006)	$\ell_{\infty}$	$C\gamma/\rho$	$\log N_{\infty}\left(V,\frac{C\gamma}{\rho}\right)=O\left(d\log\frac{en}{d\gamma}\log^{\rho}\frac{en}{d}\right)$	No
Aiyer et al. Aiyer et al. (2026)	$\ell_{\infty}$	$\gamma/2+\varepsilon$	$\log N_{\infty}\left(V,\frac{\gamma}{2}+\varepsilon\right)=O\left(d\log\frac{1}{\varepsilon}\log^{2}(en)\right)$	No

Table 1: Comparison of covering-number bounds for bounded real-valued function classes. Throughout,

d=\mathtt{fat}_{\gamma}(V)

\varepsilon,\rho\in(0,1)

, and

C>0

denotes a universal constant. The family

V\subseteq[-1,+1]^{n}

is fixed, and

N_{p}(V,r)

denotes its covering number in the indicated normalized metric.

Panel of Figure 1 — Figure 1: Moving the center while preserving the approximation. The shaded intersection $A=B_{R}(y)\cap B_{r}(x)$ remains covered when we replace $B_{r}(x)$ by $B_{r}(z)$ . The radius stays $r$ , while the new center satisfies $\|z-y\|_{2}\leq\sqrt{R^{2}-r^{2}}$ .

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 154 papers

May 13, 2026

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

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.

Shashaank Aiyer, Yishay Mansour, Shay Moran +2

University of Maryland · Tel Aviv University and Google Research · Technion and Google Research +1

Agnostic Learning Statistical Learning Theory Integral Probability Metrics Generalization Bounds

Ask PDF

May 7, 2026

A Fine-Grained Understanding of Uniform Convergence for Halfspaces

We study the fine-grained uniform convergence behavior of halfspaces beyond worst-case VC bounds. For inhomogeneous halfspaces in

\mathbb{R}^d

with

d\ge 2

, we show that standard first-order VC bounds are essentially tight: even consistent hypotheses can incur population error

Θ(d\ln(n/d)/n)

, and in the agnostic setting the deviation scales as

\sqrt{τ\ln(1/τ)}

at true error

τ

. In contrast, homogeneous halfspaces in

\mathbb{R}^2

exhibit a markedly different behavior. In the realizable case, every hypothesis consistent with the sample has error

O(1/n)

. In the agnostic case, we prove a bandwise, log-free deviation bound on each dyadic risk band via a critical-wedge localization argument. Unioning over bands incurs only a

\ln\ln n

overhead, and we establish a matching lower bound showing this overhead is unavoidable. Together, these results give a fine-grained and nearly complete picture of uniform convergence for halfspaces, revealing sharp dimensional and structural thresholds.

Aryeh Kontorovich, Kasper Green Larsen

Ben-Gurion University · Aarhus University

Halfspace Learning Statistical Learning Theory Generalization Bounds

Ask PDF

Mar 25, 2026

Uniform Laws of Large Numbers in Product Spaces

Uniform laws of large numbers form a cornerstone of Vapnik--Chervonenkis theory, where they are characterized by the finiteness of the VC dimension. In this work, we study uniform convergence phenomena in cartesian product spaces, under assumptions on the underlying distribution that are compatible with the product structure. Specifically, we assume that the distribution is absolutely continuous with respect to the product of its marginals, a condition that captures many natural settings, including product distributions, sparse mixtures of product distributions, distributions with low mutual information, and more. We show that, under this assumption, a uniform law of large numbers holds for a family of events if and only if the linear VC dimension of the family is finite. The linear VC dimension is defined as the maximum size of a shattered set that lies on an axis-parallel line, namely, a set of vectors that agree on all but at most one coordinate. This dimension is always at most the classical VC dimension, yet it can be arbitrarily smaller. For instance, the family of convex sets in

\mathbb{R}^d

has linear VC dimension

2

, while its VC dimension is infinite already for

d\ge 2

. Our proofs rely on estimator that departs substantially from the standard empirical mean estimator and exhibits more intricate structure. We show that such deviations from the standard empirical mean estimator are unavoidable in this setting. Throughout the paper, we propose several open questions, with a particular focus on quantitative sample complexity bounds.

Ron Holzman, Shay Moran, Alexander Shlimovich

Department of Mathematics, Technion · Departments of Mathematics, Computer Science, and Data and Decision Sciences, Technion and Google Research

VC Dimension Statistical Learning Theory Generalization Bounds

Ask PDF

Abstract

Generalization Bounds

Explore similar work

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

A Fine-Grained Understanding of Uniform Convergence for Halfspaces

Uniform Laws of Large Numbers in Product Spaces