# Reproducibility in Learning

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 61 references that are in the map.
- First posted on arXiv 20 Jan 2022.

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

- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [Are GANs Created Equal? A Large-Scale Study](https://mlsanity.com/paper/1711.10337/) (2017)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Reproducibility of Benchmarked Deep Reinforcement Learning Tasks for Continuous Control](https://mlsanity.com/paper/1708.04133/) (2017)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Privately Learning Thresholds: Closing the Exponential Gap](https://mlsanity.com/paper/1911.10137/) (2019)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Characterizing the Sample Complexity of Private Learners](https://mlsanity.com/paper/1402.2224/) (2014)
- [Property Testing for Differential Privacy](https://mlsanity.com/paper/1806.06427/) (2018)
- [Efficient, Noise-Tolerant, and Private Learning via Boosting](https://mlsanity.com/paper/2002.01100/) (2020)
- [LightDP: Towards Automating Differential Privacy Proofs](https://mlsanity.com/paper/1607.08228/) (2016)
- [Synthesizing Coupling Proofs of Differential Privacy](https://mlsanity.com/paper/1709.05361/) (2017)
- [Higher-Order Approximate Relational Refinement Types for Mechanism Design and Differential Privacy](https://mlsanity.com/paper/1407.6845/) (2014)
- [Deciding Accuracy of Differential Privacy Schemes](https://mlsanity.com/paper/2011.06404/) (2020)
- [Pseudo-deterministic Streaming](https://mlsanity.com/paper/1911.11368/) (2019)

## Built on by (most cited first, 30 of 44)

- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Reproducibility in Optimization: Theoretical Framework and Limits](https://mlsanity.com/paper/2202.04598/) (2022)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Local Borsuk-Ulam, Stability, and Replicability](https://mlsanity.com/paper/2311.01599/) (2023)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [User-Level Differential Privacy With Few Examples Per User](https://mlsanity.com/paper/2309.12500/) (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)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Replicable Online Learning](https://mlsanity.com/paper/2411.13730/) (2024)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [A Unified Characterization of Private Learnability via Graph Theory](https://mlsanity.com/paper/2304.03996/) (2023)
- [Simple online learning with consistent oracle](https://mlsanity.com/paper/2308.08055/) (2023)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Stability and List-Replicability for Agnostic Learners](https://mlsanity.com/paper/2501.05333/) (2025)
- [Spherical dimension](https://mlsanity.com/paper/2503.10240/) (2025)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [The Unseen Threat: Residual Knowledge in Machine Unlearning under Perturbed Samples](https://mlsanity.com/paper/2601.22359/) (2026)
- [Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization](https://mlsanity.com/paper/2310.17759/) (2023)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem](https://mlsanity.com/paper/2409.11597/) (2024)
- [The Cost of Replicability in Active Learning](https://mlsanity.com/paper/2412.09686/) (2024)

## Abstract (arXiv)

We introduce the notion of a reproducible algorithm in the context of learning. A reproducible learning algorithm is resilient to variations in its samples -- with high probability, it returns the exact same output when run on two samples from the same underlying distribution. We begin by unpacking the definition, clarifying how randomness is instrumental in balancing accuracy and reproducibility. We initiate a theory of reproducible algorithms, showing how reproducibility implies desirable properties such as data reuse and efficient testability. Despite the exceedingly strong demand of reproducibility, there are efficient reproducible algorithms for several fundamental problems in statistics and learning. First, we show that any statistical query algorithm can be made reproducible with a modest increase in sample complexity, and we use this to construct reproducible algorithms for finding approximate heavy-hitters and medians. Using these ideas, we give the first reproducible algorithm for learning halfspaces via a reproducible weak learner and a reproducible boosting algorithm. Finally, we initiate the study of lower bounds and inherent tradeoffs for reproducible algorithms, giving nearly tight sample complexity upper and lower bounds for reproducible versus nonreproducible SQ algorithms.