# The Sample Complexity of Replicable Realizable PAC Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 33 references that are in the map.
- First posted on arXiv 23 Feb 2026.

## Builds on (most cited first, 17 of 17)

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Replicability and stability in learning](https://mlsanity.com/paper/2304.03757/) (2023)
- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [Replicable Online Learning](https://mlsanity.com/paper/2411.13730/) (2024)
- [Efficient Optimal PAC Learning](https://mlsanity.com/paper/2502.03620/) (2025)
- [The Role of Randomness in Stability](https://mlsanity.com/paper/2502.08007/) (2025)
- [Approximate Replicability in Learning](https://mlsanity.com/paper/2510.20200/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)

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

- [Replicable Composition](https://mlsanity.com/paper/2604.10423/) (2026)
- [Optimal Unambiguous DNFs and Alon-Saks-Seymour](https://mlsanity.com/paper/2608.02533/) (2026)

## Abstract (arXiv)

In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to (log|H|)3/2 dependence on the size of the hypothesis class H. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with H and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.