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

Aug 6, 2026

An Optimal Agnostic PAC Algorithm

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].

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

Ask PDF

Feb 23, 2026

The Sample Complexity of Replicable Realizable PAC Learning

In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to

(\log|H|)^{3/2}

dependence on the size of the hypothesis class

H

. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with

H

and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.

Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju +1

Computer Science Department, Aarhus University · Computer Science Department, Stanford University

PAC Learning Sample Complexity

Ask PDF

Apr 12, 2026

Replicable Composition

Replicability requires that algorithmic conclusions remain consistent when rerun on independently drawn data. A central structural question is composition: given

k

problems each admitting a

ρ

-replicable algorithm with sample complexity

n

, how many samples are needed to solve all jointly while preserving replicability? The naive analysis yields

\widetilde{O}(nk^2)

samples, and Bun et al. (STOC'23) observed that reductions through differential privacy give an alternative

\widetilde{O}(n^2k)

bound, leaving open whether the optimal

\widetilde{O}(nk)

scaling is achievable. We resolve this open problem and, more generally, show that problems with sample complexities

n_1,\ldots,n_k

can be jointly solved with

\widetilde{O}(\sum_i n_i)

samples while preserving constant replicability. Our approach converts each replicable algorithm into a perfectly generalizing one, composes them via a privacy-style analysis, and maps back via correlated sampling. This yields the first advanced composition theorem for replicability. En route, we obtain new bounds for the composition of perfectly generalizing algorithms with heterogeneous parameters. As part of our results, we provide a boosting theorem for the success probability of replicable algorithms. For a broad class of problems, the failure probability appears as a separate additive term independent of

ρ

, immediately yielding improved sample complexity bounds for several problems. Finally, we prove an

Ω(nk^2)

lower bound for adaptive composition, establishing a quadratic separation from the non-adaptive setting. The key technique, which we call the phantom run, yields structural results of independent interest.

Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari +2

University of Maryland, College Park, MD, USA · Google Research, New York City, NY, USA · Google Research, London, UK

Sample Complexity ML Reproducibility

Ask PDF

Abstract

Agnostic Learning

Explore similar work

An Optimal Agnostic PAC Algorithm

The Sample Complexity of Replicable Realizable PAC Learning

Replicable Composition