# Private Selection from Private Candidates

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

## Key facts

- Cited by 75 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2018.

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

- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Antipodes of Label Differential Privacy: PATE and ALIBI](https://mlsanity.com/paper/2106.03408/) (2021)
- [TAN Without a Burn: Scaling Laws of DP-SGD](https://mlsanity.com/paper/2210.03403/) (2022)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Enforcing fairness in private federated learning via the modified method of differential multipliers](https://mlsanity.com/paper/2109.08604/) (2021)
- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection](https://mlsanity.com/paper/2111.04906/) (2021)
- [Accuracy, Interpretability, and Differential Privacy via Explainable Boosting](https://mlsanity.com/paper/2106.09680/) (2021)
- [Selective Pre-training for Private Fine-tuning](https://mlsanity.com/paper/2305.13865/) (2023)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [Practical Differentially Private Hyperparameter Tuning with Subsampling](https://mlsanity.com/paper/2301.11989/) (2023)
- [Private GANs, Revisited](https://mlsanity.com/paper/2302.02936/) (2023)
- [Privately Learning Subspaces](https://mlsanity.com/paper/2106.00001/) (2021)
- [Reducing bias and increasing utility by federated generative modeling of medical images using a centralized adversary](https://mlsanity.com/paper/2101.07235/) (2021)
- [Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic Survey](https://mlsanity.com/paper/2309.16398/) (2023)
- [Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners](https://mlsanity.com/paper/2401.00583/) (2023)
- [A New Linear Scaling Rule for Private Adaptive Hyperparameter Optimization](https://mlsanity.com/paper/2212.04486/) (2022)
- [DPlis: Boosting Utility of Differentially Private Deep Learning via Randomized Smoothing](https://mlsanity.com/paper/2103.01496/) (2021)
- [Differentially Private Normalizing Flows for Privacy-Preserving Density Estimation](https://mlsanity.com/paper/2103.14068/) (2021)
- [Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates](https://mlsanity.com/paper/2107.09802/) (2021)
- [DP-DyLoRA: Fine-Tuning Transformer-Based Models On-Device under Differentially Private Federated Learning using Dynamic Low-Rank Adaptation](https://mlsanity.com/paper/2405.06368/) (2024)
- [Skellam Mixture Mechanism: a Novel Approach to Federated Learning with Differential Privacy](https://mlsanity.com/paper/2212.04371/) (2022)
- [On Noisy Evaluation in Federated Hyperparameter Tuning](https://mlsanity.com/paper/2212.08930/) (2022)

## Abstract (arXiv)

Differentially Private algorithms often need to select the best amongst many candidate options. Classical works on this selection problem require that the candidates' goodness, measured as a real-valued score function, does not change by much when one person's data changes. In many applications such as hyperparameter optimization, this stability assumption is much too strong. In this work, we consider the selection problem under a much weaker stability assumption on the candidates, namely that the score functions are differentially private. Under this assumption, we present algorithms that are near-optimal along the three relevant dimensions: privacy, utility and computational efficiency. Our result can be seen as a generalization of the exponential mechanism and its existing generalizations. We also develop an online version of our algorithm, that can be seen as a generalization of the sparse vector technique to this weaker stability assumption. We show how our results imply better algorithms for hyperparameter selection in differentially private machine learning, as well as for adaptive data analysis.