# Reproducibility in Optimization: Theoretical Framework and Limits

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 9 Feb 2022.

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

- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [Deep Ensembles: A Loss Landscape Perspective](https://mlsanity.com/paper/1912.02757/) (2019)
- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning](https://mlsanity.com/paper/2012.09816/) (2020)
- [Measuring the Effects of Data Parallelism on Neural Network Training](https://mlsanity.com/paper/1811.03600/) (2018)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Large scale distributed neural network training through online distillation](https://mlsanity.com/paper/1804.03235/) (2018)
- [Critical Learning Periods in Deep Neural Networks](https://mlsanity.com/paper/1711.08856/) (2017)
- [Randomness In Neural Network Training: Characterizing The Impact of Tooling](https://mlsanity.com/paper/2106.11872/) (2021)
- [Nondeterminism and Instability in Neural Network Optimization](https://mlsanity.com/paper/2103.04514/) (2021)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Analyzing the Role of Model Uncertainty for Electronic Health Records](https://mlsanity.com/paper/1906.03842/) (2019)
- [On the Sample Complexity of Stability Constrained Imitation Learning](https://mlsanity.com/paper/2102.09161/) (2021)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [On the Reproducibility of Neural Network Predictions](https://mlsanity.com/paper/2102.03349/) (2021)
- [On Acceleration with Noise-Corrupted Gradients](https://mlsanity.com/paper/1805.12591/) (2018)
- [Smooth activations and reproducibility in deep networks](https://mlsanity.com/paper/2010.09931/) (2020)
- [Algorithmic Instabilities of Accelerated Gradient Descent](https://mlsanity.com/paper/2102.02167/) (2021)
- [Anti-Distillation: Improving reproducibility of deep networks](https://mlsanity.com/paper/2010.09923/) (2020)
- [Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions](https://mlsanity.com/paper/1805.10579/) (2018)
- [Synthesizing Irreproducibility in Deep Networks](https://mlsanity.com/paper/2102.10696/) (2021)
- [Beyond Point Estimate: Inferring Ensemble Prediction Variation from Neuron Activation Strength in Recommender Systems](https://mlsanity.com/paper/2008.07032/) (2020)

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

- [On the Factory Floor: ML Engineering for Industrial-Scale Ads Recommendation Models](https://mlsanity.com/paper/2209.05310/) (2022)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [Reproducibility in Multiple Instance Learning: A Case For Algorithmic Unit Tests](https://mlsanity.com/paper/2310.17867/) (2023)
- [What Do Machine Learning Researchers Mean by "Reproducible"?](https://mlsanity.com/paper/2412.03854/) (2024)
- [A Siren Song of Open Source Reproducibility](https://mlsanity.com/paper/2204.04372/) (2022)
- [Replicability and stability in learning](https://mlsanity.com/paper/2304.03757/) (2023)
- [Replicable Online Learning](https://mlsanity.com/paper/2411.13730/) (2024)
- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [On Corruption-Robustness in Performative Reinforcement Learning](https://mlsanity.com/paper/2505.05609/) (2025)
- [Towards Inferential Reproducibility of Machine Learning Research](https://mlsanity.com/paper/2302.04054/) (2023)
- [Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization](https://mlsanity.com/paper/2310.17759/) (2023)
- [Real World Large Scale Recommendation Systems Reproducibility and Smooth Activations](https://mlsanity.com/paper/2202.06499/) (2022)
- [Replicable Constrained Bandits](https://mlsanity.com/paper/2602.14580/) (2026)
- [Generalizability of experimental studies](https://mlsanity.com/paper/2406.17374/) (2024)
- [Fractal basin geometry and the limits to predictability and reproducibility in deep learning](https://mlsanity.com/paper/2510.05606/) (2025)
- [Calibrating Adaptive Smoothing Methods for Freeway Traffic Reconstruction](https://mlsanity.com/paper/2602.02072/) (2026)
- [Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity](https://mlsanity.com/paper/2606.11431/) (2026)

## Abstract (arXiv)

We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.