# Arbitrary Decisions are a Hidden Cost of Differentially Private Training

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 45 references that are in the map.
- First posted on arXiv 28 Feb 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Underspecification Presents Challenges for Credibility in Modern Machine Learning](https://mlsanity.com/paper/2011.03395/) (2020)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously](https://mlsanity.com/paper/1801.01489/) (2018)
- [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [Characterizing Fairness Over the Set of Good Models Under Selective Labels](https://mlsanity.com/paper/2101.00352/) (2021)
- [Diffprivlib: The IBM Differential Privacy Library](https://mlsanity.com/paper/1907.02444/) (2019)
- [Deep Roto-Translation Scattering for Object Classification](https://mlsanity.com/paper/1412.8659/) (2014)
- [SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python](https://mlsanity.com/paper/1907.10121/) (2019)
- [Robin Hood and Matthew Effects: Differential Privacy Has Disparate Impact on Synthetic Data](https://mlsanity.com/paper/2109.11429/) (2021)
- [Predictive Multiplicity in Probabilistic Classification](https://mlsanity.com/paper/2206.01131/) (2022)
- [Selective Ensembles for Consistent Predictions](https://mlsanity.com/paper/2111.08230/) (2021)
- [How unfair is private learning ?](https://mlsanity.com/paper/2206.03985/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)

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

- [Dropout-Based Rashomon Set Exploration for Efficient Predictive Multiplicity Estimation](https://mlsanity.com/paper/2402.00728/) (2024)
- [Systemizing Multiplicity: The Curious Case of Arbitrariness in Machine Learning](https://mlsanity.com/paper/2501.14959/) (2025)
- [Predictive Churn with the Set of Good Models](https://mlsanity.com/paper/2402.07745/) (2024)
- [Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy](https://mlsanity.com/paper/2507.06969/) (2025)
- [The Inadequacy of Similarity-based Privacy Metrics: Privacy Attacks against "Truly Anonymous" Synthetic Datasets](https://mlsanity.com/paper/2312.05114/) (2023)
- [Algorithmic Arbitrariness in Content Moderation](https://mlsanity.com/paper/2402.16979/) (2024)
- [Rashomon Sets for Prototypical-Part Networks: Editing Interpretable Models in Real-Time](https://mlsanity.com/paper/2503.01087/) (2025)
- [Mitigating Unintended Memorization with LoRA in Federated Learning for LLMs](https://mlsanity.com/paper/2502.05087/) (2025)
- [Arbitrariness Lies Beyond the Fairness-Accuracy Frontier](https://mlsanity.com/paper/2306.09425/) (2023)
- [The Cost of Arbitrariness for Individuals: Examining the Legal and Technical Challenges of Model Multiplicity](https://mlsanity.com/paper/2407.13070/) (2024)
- [The Unseen Threat: Residual Knowledge in Machine Unlearning under Perturbed Samples](https://mlsanity.com/paper/2601.22359/) (2026)
- [When Synthetic Data Met Regulation](https://mlsanity.com/paper/2307.00359/) (2023)
- [Using predictive multiplicity to measure individual performance within the AI Act](https://mlsanity.com/paper/2602.11944/) (2026)
- [Regretful Decisions under Label Noise](https://mlsanity.com/paper/2504.09330/) (2025)
- [On Arbitrary Predictions from Equally Valid Models](https://mlsanity.com/paper/2507.19408/) (2025)
- [Rethinking Anonymity Claims in Synthetic Data Generation: A Model-Centric Privacy Attack Perspective](https://mlsanity.com/paper/2601.22434/) (2026)
- [On the Impact of Output Perturbation on Fairness in Binary Linear Classification](https://mlsanity.com/paper/2402.03011/) (2024)
- [The Double-Edged Nature of the Rashomon Set for Trustworthy Machine Learning](https://mlsanity.com/paper/2511.21799/) (2025)
- [Rashomon Sets and Model Multiplicity in Federated Learning](https://mlsanity.com/paper/2602.09520/) (2026)

## Abstract (arXiv)

Mechanisms used in privacy-preserving machine learning often aim to guarantee differential privacy (DP) during model training. Practical DP-ensuring training methods use randomization when fitting model parameters to privacy-sensitive data (e.g., adding Gaussian noise to clipped gradients). We demonstrate that such randomization incurs predictive multiplicity: for a given input example, the output predicted by equally-private models depends on the randomness used in training. Thus, for a given input, the predicted output can vary drastically if a model is re-trained, even if the same training dataset is used. The predictive-multiplicity cost of DP training has not been studied, and is currently neither audited for nor communicated to model designers and stakeholders. We derive a bound on the number of re-trainings required to estimate predictive multiplicity reliably. We analyze--both theoretically and through extensive experiments--the predictive-multiplicity cost of three DP-ensuring algorithms: output perturbation, objective perturbation, and DP-SGD. We demonstrate that the degree of predictive multiplicity rises as the level of privacy increases, and is unevenly distributed across individuals and demographic groups in the data. Because randomness used to ensure DP during training explains predictions for some examples, our results highlight a fundamental challenge to the justifiability of decisions supported by differentially private models in high-stakes settings. We conclude that practitioners should audit the predictive multiplicity of their DP-ensuring algorithms before deploying them in applications of individual-level consequence.