Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness
Abstract
Strict replicability requires two independent training samples, processed with the same random seed, to produce exactly the same hypothesis. We study realizable Boolean learning under unknown and known instance marginals. For unknown marginals, we obtain the worst-case sample complexity Θ(((log M)2/ρ2+log(1/δ))/ε) for classes of cardinality at most M, throughout a fixed small-parameter range. This resolves the distribution-free finite-class sample-complexity question up to universal constants and rules out a general ρ−1 dependence. The upper bound uses a truncated-power distribution with a hard empirical-error budget. For known marginals, a control-variate learner uses O(((1+log M)3/2/ρ+log(1/δ))/ε) samples, and explicit uniform-marginal instances establish the matching class-size exponent. On a product of d finite threshold chains of length k, we determine the exact rate Θ((dklog(1+√d/(kρ))+log(1/δ))/ε). We also characterize deterministic learning, the very-small-ρ regime for arbitrary finite classes, and every cardinality-replicability regime for finite classes of VC dimension one. A VC-covering-number bound yields the fixed-accuracy exponent 3/2 independently of cardinality. Finally, we separate statistical complexity from implementation costs: we prove a sharp fixed-block trade-off, short-seed existence bounds, and a shared rejection-filter reduction from optimal learning of the full Boolean class to efficient public sampling of ordinary Bernoulli product distributions. Detailed proofs include the geometric lower bounds, the discrete posterior-kernel comparison, and the finite-bit constructions.
Related
- Replication Descent and J-Finality of Replicable Functions
- Generalized Spectral Closedness and the Nonexistence of Walk-Realizable Supporters for Split Graphs
- Realizable Cohomology Classes of Dihedral and Generalized Quaternion Groups
- Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
- Revisiting the Bobkov-Chistyakov-Götze theorem on approximately Gaussian marginals
BibTeX
@misc{zhang2026strictly,
title = {{Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness}},
author = {Guangjian Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26944},
eprint = {2610.26944},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26944},
}
RIS
TY - UNPB
TI - Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness
AU - Guangjian Zhang
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.26944
UR - https://arxiv.org/abs/2610.26944
AB - Strict replicability requires two independent training samples, processed with the same random seed, to produce exactly the same hypothesis. We study realizable Boolean learning under unknown and known instance marginals. For unknown marginals, we obtain the worst-case sample complexity Θ(((log M)^2/ρ^2+log(1/δ))/ε) for classes of cardinality at most M, throughout a fixed small-parameter range. This resolves the distribution-free finite-class sample-complexity question up to universal constants and rules out a general ρ^−1 dependence. The upper bound uses a truncated-power distribution with a hard empirical-error budget. For known marginals, a control-variate learner uses O(((1+log M)^3/2/ρ+log(1/δ))/ε) samples, and explicit uniform-marginal instances establish the matching class-size exponent. On a product of d finite threshold chains of length k, we determine the exact rate Θ((dklog(1+√d/(kρ))+log(1/δ))/ε). We also characterize deterministic learning, the very-small-ρ regime for arbitrary finite classes, and every cardinality-replicability regime for finite classes of VC dimension one. A VC-covering-number bound yields the fixed-accuracy exponent 3/2 independently of cardinality. Finally, we separate statistical complexity from implementation costs: we prove a sharp fixed-block trade-off, short-seed existence bounds, and a shared rejection-filter reduction from optimal learning of the full Boolean class to efficient public sampling of ordinary Bernoulli product distributions. Detailed proofs include the geometric lower bounds, the discrete posterior-kernel comparison, and the finite-bit constructions.
ER -