A new arXiv paper by Guangjian Zhang settles the sample-complexity exponent for strict replicability in realizable learning when the data-generating marginal is unknown. Strict replicability requires that two independent samples plus one shared seed produce identical functions. The paper analyzes this under the quantifier "exists A for all D," where both the realizable distribution and its marginal are unknown.
For finite hypothesis classes, the worst-case complexity over |H| <= M is Theta((log M)^2) when epsilon, delta, and rho are all 10^-4. More generally, for an explicit anchored realizable family, every randomized, possibly improper learner needs Omega(d^2/(epsilon rho^2)) samples. For the full Boolean class P_d, the paper proves the matching characterization Theta(d^2/(epsilon rho^2) + epsilon^-1 log(1/delta)) using a proper Poissonized ball-sampling algorithm.
The paper also gives an explicit proper Gibbs upper bound for every finite measurable Boolean class and characterizes the known-marginal worst case for P_d, showing why that setting must be treated separately. As the sole source, the abstract presents these results as a unified contribution rather than a comparison of competing claims.