mlsanityData to 14 Oct 2026

Private Selection from Private Candidates

arXiv 1811.07971 ↗First posted 19 Nov 2018cs.DS cs.CR cs.LGcited by 75

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 16; 2022: 15; 2023: 11; 2024: 13; 2025: 15; 2026: 5.

75 papers.

Sort:

By area:

  1. 2021Large Language Models Can Be Strong Differentially Private Learnerscited by 412
  2. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 153
  3. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
  4. 2021Learning with User-Level Privacycited by 72
  5. 2022Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Losscited by 61
  6. 2021Antipodes of Label Differential Privacy: PATE and ALIBIcited by 52
  7. 2022TAN Without a Burn: Scaling Laws of DP-SGDcited by 52
  8. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  9. 2021Enforcing fairness in private federated learning via the modified method of differential multiplierscited by 38
  10. 2022On Privacy and Personalization in Cross-Silo Federated Learningcited by 36
  11. 2024Privacy-Preserving Instructions for Aligning Large Language Modelscited by 35
  12. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
38 more
  1. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  2. 2021The Role of Adaptive Optimizers for Honest Private Hyperparameter Selectioncited by 25
  3. 2021Accuracy, Interpretability, and Differential Privacy via Explainable Boostingcited by 24
  4. 2023Selective Pre-training for Private Fine-tuningcited by 23
  5. 2022Easy Differentially Private Linear Regressioncited by 19
  6. 2023Practical Differentially Private Hyperparameter Tuning with Subsamplingcited by 19
  7. 2023Private GANs, Revisitedcited by 17
  8. 2021Privately Learning Subspacescited by 16
  9. 2021Reducing bias and increasing utility by federated generative modeling of medical images using a centralized adversarycited by 14
  10. 2023Recent Advances of Differential Privacy in Centralized Deep Learning: A Systematic Surveycited by 12
  11. 2023Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learnerscited by 12
  12. 2022A New Linear Scaling Rule for Private Adaptive Hyperparameter Optimizationcited by 11
  13. 2021DPlis: Boosting Utility of Differentially Private Deep Learning via Randomized Smoothingcited by 10
  14. 2021Differentially Private Normalizing Flows for Privacy-Preserving Density Estimationcited by 10
  15. 2021Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Ratescited by 10
  16. 2024DP-DyLoRA: Fine-Tuning Transformer-Based Models On-Device under Differentially Private Federated Learning using Dynamic Low-Rank Adaptationcited by 9
  17. 2022Skellam Mixture Mechanism: a Novel Approach to Federated Learning with Differential Privacycited by 7
  18. 2022On Noisy Evaluation in Federated Hyperparameter Tuningcited by 7
  19. 2025Towards hyperparameter-free optimization with differential privacycited by 7
  20. 2022(Nearly) Optimal Private Linear Regression via Adaptive Clippingcited by 6
  21. 2022Revisiting Hyperparameter Tuning with Differential Privacycited by 6
  22. 2022Generalized PTR: User-Friendly Recipes for Data-Adaptive Algorithms with Differential Privacycited by 6
  23. 2023Improved Differentially Private Regression via Gradient Boostingcited by 6
  24. 2025DC-SGD: Differentially Private SGD with Dynamic Clipping through Gradient Norm Distribution Estimationcited by 6
  25. 2024Revisiting Differentially Private Hyper-parameter Tuningcited by 5
  26. 2024Differentially Private Representation Learning via Image Captioningcited by 5
  27. 2024Differentially Private Post-Processing for Fair Regressioncited by 5
  28. 2021Mitigating Statistical Bias within Differentially Private Synthetic Datacited by 4
  29. 2022Differentially Private Deep Learning with ModelMixcited by 4
  30. 2023DP-HyPO: An Adaptive Private Hyperparameter Optimization Frameworkcited by 4
  31. 2024Differentially Private Clustered Federated Learningcited by 4
  32. 2025An Improved Privacy and Utility Analysis of Differentially Private SGD with Bounded Domain and Smooth Lossescited by 4
  33. 2021Gaussian Processes with Differential Privacycited by 3
  34. 2022Sotto Voce: Federated Speech Recognition with Differential Privacy Guaranteescited by 3
  35. 2022Answering Private Linear Queries Adaptively using the Common Mechanismcited by 2
  36. 2023Online Sensitivity Optimization in Differentially Private Learningcited by 2
  37. 2024Privacy Profiles for Private Selectioncited by 2
  38. 2024Differentially Private Optimization with Sparse Gradientscited by 2

50 most cited of 75 All 75 (JSON)