pipette
ENEnglish

Quadratic Sample Complexity for Strictly Replicable Realizable Learning with Unknown Marginals

Guangjian Zhang

Preprint

En palabras de los autores

Under the quantifier , 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 , the worst case over is , without iterated logarithms. For , , and , every randomized, possibly improper learner valid throughout an explicit anchored realizable family requires samples. For the full Boolean class , , in the same parameter range, we prove the matching characterization 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 , showing why that interface must be kept distinct.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 34 pages