# Approximate Replicability in Learning

arXiv: https://arxiv.org/abs/2510.20200 · HTML: https://mlsanity.com/paper/2510.20200/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2025.

## Built on by (most cited first, 3 of 3)

- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [Model Agreement via Anchoring](https://mlsanity.com/paper/2602.23360/) (2026)
- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)

## Abstract (arXiv)

Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness). While a strong and interesting notion of stability, the cost of replicability can be prohibitive: there is no replicable algorithm, for instance, for tasks as simple as threshold learning (Bun et al. STOC '23). Given such strong impossibility results we ask: under what approximate notions of replicability is learning possible? In this work, we propose three natural relaxations of replicability in the context of PAC learning: (1) Pointwise: the learner must be consistent on any fixed input, but not across all inputs simultaneously, (2) Approximate: the learner must output hypotheses that classify most of the distribution consistently, (3) Semi: the algorithm is fully replicable, but may additionally use shared unlabeled samples. In all three cases, for constant replicability we obtain close to sample-optimal agnostic PAC learners: 1) and 2) are achievable using O(d/α2 + 1/α4) samples, while 3) requires Theta(d2/α2) labeled samples.