Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals

Guangjian Zhang

Under the quantifier $\exists A\,\forall D$, where the realizable distribution and its marginal are unknown, we determine the finite-class sample-complexity exponent for strict replicability: two independent samples and one shared seed must produce identical functions. For $\varepsilon=δ=ρ=10^{-4}$, the worst case over $|H|\le M$ is $Θ((\log M)^2)$, without iterated logarithms. For $d\ge1$, $0<\varepsilon\le1/16$, and $0<δ,ρ\le10^{-3}$, every randomized, possibly improper learner valid throughout an explicit anchored realizable family requires $Ω(d^2/(\varepsilonρ^2))$ samples. For the full Boolean class $P_d$, $d\ge2$, in the same parameter range, we prove the matching characterization $Θ(d^2/(\varepsilonρ^2)+\varepsilon^{-1}\log(1/δ))$ using a proper Poissonized ball-sampling algorithm. We also give an explicit proper Gibbs upper bound for every finite measurable Boolean class. Our lower bound uses square-root probabilities and volumetric packing; the Gibbs proof builds on established coupling and generalization identities. Finally, we characterize the known-marginal worst case for $P_d$, showing why that interface must be kept distinct.