Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals

# 概要
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…

# 原典
https://arxiv.org/abs/2610.26944

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。