Pointwise Replicable Agnostic Learning: The Additive Term Is Unnecessary and the Fixed-Confidence Order Is Exact

Abstract

Hopkins, Impagliazzo, and Ye (arXiv:2510.20200) introduced $\rho$-pointwise replicable learning and proved that every class of VC dimension $d$ admits a pointwise replicable agnostic $(\alpha,\beta)$-learner with $\widetilde O(d/(\rho^2\alpha^2)+1/(\rho^2\alpha^4))$ samples, asking whether the additive $\rho^{-2}\alpha^{-O(1)}$ term is necessary. We answer this in the negative for every countable domain and every class of finite VC dimension, with explicit constants: an agnostic $(\alpha,\beta)$-learner that is $\rho$-pointwise replicable exists with $O\big((d+\log(1/\beta)+\min\{\log(1/\rho),\log(1/\alpha)\})/(\rho^2\alpha^2)+\log(1/\beta)\log(\log(1/\beta)/(\alpha^2\beta))/\alpha^2\big)$ samples, and a second construction (SOFT-VC, an averaged proper ERM with a clipped shift by a signed empirical histogram and independent shared rounding) gives, for every fixed confidence $\beta_0$, the exact order $m^*(d,\alpha,\beta_0,\rho)=\Theta_{\beta_0}(d/(\rho^2\alpha^2))$ for all $\alpha,\rho,d$, with no logarithmic factor. A matching lower bound $m\ge\kappa d/(\rho^2\alpha^2)$, $\kappa=1369/(250000\pi^2)$, holds in every dimension $d\ge1$ for all learners, improper and with unlimited shared randomness. Confidence enters additively: $m^*=\widetilde\Theta_{\alpha,\rho}(d/(\rho^2\alpha^2)+\log(1/\beta)/\alpha^2)$, and the exact form $\Theta(d/(\rho^2\alpha^2)+\log(1/\beta)/\alpha^2)$ holds for every VC-one class (with a proper learner) and for the full class on $d$ atoms. Uniformly in $\beta$, the optimal additive form is established on an explicit absorption region; outside it the additive form is not decided here, and no residual logarithm is shown to be necessary. The weaker target of Hopkins, Impagliazzo, and Ye, in which the confidence term may also carry the factor $\rho^{-2}$, is attained on a strictly larger explicit region, but a full-parameter proof of it is not given.