In machine learning, reproducibility is often a practical concern. A new theoretical result addresses a specific notion called pointwise replicability: if you train a predictor twice with the same random seed, it should output the same label for any fixed query with high probability. This is stronger than typical replicability guarantees that only require the whole model to be similar.
The authors determine the optimal sample complexity for agnostic learning under this constraint. For finite and countable domains, they give a tight bound on how many labeled examples are needed to achieve pointwise replicability while maintaining worst-case accuracy. The bound is optimal, meaning no algorithm can do better and no lower bound can be pushed further.
This settles a question in the theory of replicable learning. It shows that the price of pointwise stability is precisely quantified, and it provides a benchmark for designing algorithms that are both accurate and reproducible. The work also highlights the role of the random seed in ensuring consistent predictions.