Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals

Abstract

Under the quantifier "there exists A for all 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 epsilon = delta = rho = 10^-4, the worst case over |H| <= M is Theta((log M)^2), without iterated logarithms. For d >= 1, 0 < epsilon <= 1/16, and 0 < delta, rho <= 10^-3, every randomized, possibly improper learner valid throughout an explicit anchored realizable family requires Omega(d^2/(epsilon rho^2)) samples. For the full Boolean class P_d, d >= 2, in the same parameter range, we prove the matching characterization Theta(d^2/(epsilon rho^2) + epsilon^-1 log(1/delta)) 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.