The Sample and Randomness Complexity of Pointwise Replicable Learning

Pointwise replicability requires independent training samples and shared randomness to produce agreeing predictions at each fixed test point with high probability. We close the additive sample-complexity gaps of Hopkins, Impagliazzo, and Ye (2026): binary VC classes admit agnostic learning with $\tilde{O}(d/({\rho }^2{\alpha }^2))$ samples on countable domains and realizable learning with $\tilde{O}(d/({\rho }^2\alpha ))$ samples. At fixed small failure probability, these match known lower bounds up to logarithms, with the realizable comparison for $d\ge 2$. On arbitrary measurable domains, we improve the general agnostic finite-randomness sample bound from $\tilde{O}(d/({\rho }^4{\alpha }^7))$ to $\tilde{O}(d/({\rho }^2{\alpha }^4))$ using $\lceil {\log }_2(1/\rho )\rceil$ additional shared fair bits. With deterministic base learners these are total bits, at most one above the exact minimum $\lfloor {\log }_2(1/\rho )\rfloor$ when improper outputs are allowed. For three point functions, properness costs exactly one extra bit when $\rho \le 1/8$ and $\beta <\rho /2$. One or two shared bits permit a $\Theta ({\beta }^2)$ improvement below disagreement $1/K$, where $K$ is the seed count; for $K\ge 8$, the high-confidence infimum is exactly $1/K$. We determine matching proper sample complexity just above this boundary. We also prove a dimension-dependent sample lower bound near the bit boundary and matching joint tradeoffs, including confidence, for public products of countable VC-one classes, countable tree intervals, and real intervals, and for unions of intervals without a known partition. The agnostic screen estimates normalized label signals; interval scores combine mass and component costs to make confidence additive. The general finite-bit accuracy gap remains open; a statistical lower bound identifies a limitation of the weighted-CDF compiler.