Optimal sample size needed for stable and accurate binary prediction
The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning
Machine Learning
Summary
This paper solves a problem about training two separate prediction models so that they give the same answer on any question with high probability. The authors find the best possible number of examples needed to ensure this stable agreement when learning on binary data with some errors allowed. Their method combines multiple trained predictors and carefully picks the final one to guarantee stability even on rare cases. They also prove that their sample size is as small as possible for these conditions. The work extends previous results by covering more cases and removing earlier limitations.
What this means in practice
- •For machine learning engineers: Determine the minimal training data needed to reliably produce consistent binary classifiers using fixed random seeds.
- •For data platform teams: Guarantee stable model outputs when retraining classifiers on the same dataset and random initialization, preventing unpredictable changes.
A theory result. No direct application yet.
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.