# List and Certificate Complexities in Replicable Learning

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 5 Apr 2023.

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

- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Reproducibility in Optimization: Theoretical Framework and Limits](https://mlsanity.com/paper/2202.04598/) (2022)
- [ICLR Reproducibility Challenge Report (Padam : Closing The Generalization Gap Of Adaptive Gradient Methods in Training Deep Neural Networks)](https://mlsanity.com/paper/1901.09517/) (2019)
- [Pseudo-deterministic Streaming](https://mlsanity.com/paper/1911.11368/) (2019)
- [Pseudodeterministic Constructions in Subexponential Time](https://mlsanity.com/paper/1612.01817/) (2016)
- [Matching is as Easy as the Decision Problem, in the NC Model](https://mlsanity.com/paper/1901.10387/) (2019)

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

- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Local Borsuk-Ulam, Stability, and Replicability](https://mlsanity.com/paper/2311.01599/) (2023)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [Simplicial covering dimension of extremal concept classes](https://mlsanity.com/paper/2511.11819/) (2025)
- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [Tight list replicability bounds via a novel sphere covering theorem](https://mlsanity.com/paper/2606.06148/) (2026)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)
- [Generalizability of experimental studies](https://mlsanity.com/paper/2406.17374/) (2024)
- [Replicable Conformal Prediction](https://mlsanity.com/paper/2608.23638/) (2026)

## Abstract (arXiv)

We investigate replicable learning algorithms. Ideally, we would like to design algorithms that output the same canonical model over multiple runs, even when different runs observe a different set of samples from the unknown data distribution. In general, such a strong notion of replicability is not achievable. Thus we consider two feasible notions of replicability called list replicability and certificate replicability. Intuitively, these notions capture the degree of (non) replicability. We design algorithms for certain learning problems that are optimal in list and certificate complexity. We establish matching impossibility results.