The Sample Complexity of Replicable Realizable PAC Learning

Kasper Green Larsen; Markus Engelund Mathiasen; Chirag Pabbaraju; Clement Svendsen

cs.LGFeb 23, 2026

The Sample Complexity of Replicable Realizable PAC Learning

Authors: Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, Clement Svendsen

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

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Example with $k=7$ for hypothesis $h_{i}$ for $i=(0,5,2)$ . Each interval shows which values of $b$ will make $h_{i}((a,b))=1$ . For instance, if $a=1$ then $h_{i}((a,b))=1$ for $b\in\{0,5,6\}$ .

PAC Learning

Probably approximately correct (PAC) learning studies when finite samples can yield predictors that generalize with bounded error and confidence.

See all 40 papers

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
Oct 18, 2026Guangjian ZhangAgnostic Learning Sample Complexity
PAC Learning with Query Feedback
Oct 16, 2026Chase Hutton, Adam Melrod, Han ShaoPAC Learning Multiclass Classification
University of Maryland · Harvard University
Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum
Aug 31, 2026Guangjian Zhang, Zhengyi Yang, Xiaoyang WangPAC Learning Statistical Learning Theory

Oct 18, 2026J/K move · Enter open · S save

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

Guangjian Zhang

Agnostic Learning Sample Complexity Statistical Learning Theory

Open paper AskPDF arXiv

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.

Abstract

PAC Learning

Explore similar work

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

PAC Learning with Query Feedback

Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum