The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

Guangjian Zhang

cs.LGOct 18, 2026

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

Authors: Guangjian Zhang

Abstract

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension $d\ge1$ , the required number of independent examples is $Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right)$ , uniformly over independent accuracy, failure, and disagreement parameters $α,β,ρ\in(0,1/10)$ . The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: The main upper-bound dependencies. The risk proof also uses the bridge and uniform-validation estimates; the base learner also uses the ensemble guarantee. These secondary arrows are omitted for legibility.

Panel of Figure 2 — Figure 2: Completion of the rate theorem. Rare repair also uses an ordinary proper ERM and independent validation. The confidence lower bound uses one shattered point.

Inherited content	Original v1 locator	Location in this manuscript
Model, countable rounding, self-normalized gate, explicit ERM bounds, and independent-block moments	Definition 2.1 (p. 3); Lemmas 3.1–3.4 (pp. 8, 10, 11, 14); Proposition 3.5 (p. 15)	Definition S2.1 ; Lemma S3.1 – Lemma S3.4 ; Proposition S3.5
Gate-and-round conversion, three ensemble budgets, and additive-confidence rare repair	Theorem 4.1 (p. 15); Proposition 4.2 (p. 17); Lemma 4.3 (p. 20); Theorem 4.4 (p. 21)	Theorem S4.1 , Proposition S4.2 , Lemma S4.3 , Theorem S4.4
Agnostic dimension–replicability and confidence lower bounds, including explicit constants	Theorem 5.1 (p. 22); Lemma 5.2 (p. 25)	Theorem S5.1 , Lemma S5.2 ; also Theorem 5.1 and Appendix G
Countable proper core, ordered quantile coupling, and exact proper learning for every VC-one class	Lemma 6.1 (p. 26); Theorem 6.2 (p. 28)	Lemma S6.1 , Theorem S6.2 ; Theorem 6.1
Exact proper finite-atom learning and the faster realizable bound with stability on all distributions	Theorem 6.3 (p. 30); Corollary 6.4 (p. 31)	Theorem S6.3 , Corollary S6.4 ; Theorems 6.2 and 6.3
Statement qualifications, interface-specific obstructions, SMALL-region variance, and explicit counterexamples	Remarks 6.5 (p. 33), 6.6 (p. 34), and 7.7 (p. 48)	Remark S6.5 , Remark S6.6 , Remark S7.7 ; Section 6

Appendix

Table 1: Results already contained in the Zenodo v1 published on 9 September 2026, DOI 10.5281/zenodo.22658876, and their locations here.

Panel of Figure 3 — Figure 3: Selected dependencies among the retained constructions. The proper and soft branches also use the ERM inputs. The comparison also uses S5.1–S5.2 and the finite-atom case S6.3. Those arrows, and the separate realizable and counterexample branches, are omitted here and are specified in the table and the individual proof introductions.

Symbol	Meaning
$w_{x},y_{x}$	Atom mass and conditional label mean
$e(f),\operatorname{OPT}$	True risk and infimal risk in $H$
$N_{x},C_{x},s_{x}$	Hit count, label sum, $C_{x}/\sqrt{N_{x}}$ , with zero-hit value $0$
$M,\tau,a$	Gate sample count, danger scale, $a=\sqrt{M\tau}$
$u_{x}^{\pm}$	Shared independent gate uniforms on $[1,2]$
$v_{x}$	Shared independent rounding uniforms on $[-1,1]$

Appendix

Table 5

Constant	Verification
Hoeffding $1/8$	Tilted variance $\leq c^{2}/4$ , integrated twice
Hoeffding tail $2$	Optimize $-\lambda t+\lambda^{2}V/8$ at $\lambda=4t/V$
Gate $\sqrt{2}/a$	$\operatorname{Var}(s_{x})\leq 1$ , two-sample difference variance $\leq 2$
Dangerous threshold $9\tau$	Mean magnitude $>3a$ , all thresholds have magnitude $\leq 2a$
Deterministic $25\tau/4$	Mean magnitude $\geq 5a/2$ , deviation $\leq a/2$
VC packing $(5e/\eta)^{2d}$	Collision sample of size $\lceil 2\log N/\eta\rceil$ , $0<\eta\leq 1$

Appendix

Table 6

Factor	Source and treatment
$\log(1/\beta)$ in $L$	Rounding tail budget
$\log(1/\tau)$ in $K$	Simultaneous safety/coverage over atoms
$\log T$ in U	Union bound over base blocks
$\log(1/\alpha)$ in M	Bad-block probability $\alpha\beta/16$
$\log(1/\gamma)/T$ in P	Product of square-exponential moments; total cost is additive
$\ell=\log(256/\rho)$	Running the base construction at failure probability $\rho/64$

Appendix

Table 7

Symbol	Meaning
$\zeta_{x}$	$w_{x}y_{x}/2$ , the signed population histogram
$\widehat{\zeta}_{x}$	Signed empirical histogram, zero at unobserved points
$\mathcal{E}_{D}(p)$	Linear risk of a fractional prediction
$\Pi$	Clipping map onto $[-1,1]$
$\lambda$	Soft-shift strength; not a gate count mean
$U_{x}$	Independent shared rounding uniforms on $[-1,1]$

Appendix

Table 8

Constant or coefficient	Derivation
Clipped-shift $2/3$	Complete the square in $-3z^{2}/2-2z\Delta$
Incorrect-endpoint $1/2$	$2ab\leq(a+b)^{2}/2$
Histogram second moment $1/(4M)$	$\\|V_{i}\\|_{2}=1/2$ and independence
Histogram change $1/M$	$\\|V_{i}-V_{i}^{\prime}\\|_{2}\leq 1$
Histogram tail $e^{-2Mt^{2}}$	Doob increments have range length $1/M$
Average-ERM coefficient $32K_{E}$	Moment exponent $n/(2K_{E})$ , squared threshold $\alpha^{2}/16$

Appendix

Table 9

Factor	Source and treatment
$L$ in the average-ERM term	Product of square-exponential moments; appears as $L/T$ per block and costs $O(L/\alpha^{2})$ in total
No $\log T$ in SOFT-VC	No union bound over the $T$ ERMs
$L$ in $\lambda$	Suppresses the final rounding-seed upper tail
$L^{2}/\rho^{2}$	Current pointwise stability calculation requires $M\geq 32\lambda^{2}/\rho^{2}$
No atom-count logarithm in the histogram	Concentration is for one Hilbert norm, not a union over coordinates
No $\log(1/\alpha)$ in the soft route	No simultaneous atomwise sign-safety requirement

Appendix

Table 10

Agnostic Learning

See all 11 papers

An Optimal Agnostic PAC Algorithm
Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyPAC Learning Statistical Learning Theory
Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley
The Sample Complexity of Replicable Realizable PAC Learning
Feb 23, 2026Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju +1PAC Learning Sample Complexity
Computer Science Department, Aarhus University · Computer Science Department, Stanford University
Replicable Composition
Apr 12, 2026Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari +2Sample Complexity ML Reproducibility
University of Maryland, College Park, MD, USA · Google Research, New York City, NY, USA · Google Research, London, UK

Aug 6, 2026J/K move · Enter open · S save

An Optimal Agnostic PAC Algorithm

Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley

PAC Learning Statistical Learning Theory Generalization Bounds

Open paper AskPDF arXiv

Let

H\subseteq\{-1,+1\}^X

be a class of finite VC dimension

d\ge1

. Writing

L

for the binary risk and

L^*=\min_{h\in H}L(h)

, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size

n

, for every

0<δ\le 1/2

, with probability at least

1-δ

L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right).

This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed

L^*

, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Abstract

Agnostic Learning

Explore similar work

An Optimal Agnostic PAC Algorithm

The Sample Complexity of Replicable Realizable PAC Learning

Replicable Composition