Private selection from private candidates

By Jingcheng Liu, Kunal Talwar. 2018

157 citations recorded by the source corpus.

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.

Subfields: Privacy & Security, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Differentially Private Learning Needs Better Features (or Much More Data) (2020, background): “Private hyper-parameter search is possible at a small cost in the DP budget (Liu & Talwar, 2019), but we argue that fully accounting for this privacy leakage is hard as even our choices of architectures, optimizers, hyper-parameter ranges, etc. are informed by prior analysis of the same data.”
Differentially Private Learning with Adaptive Clipping (2019, neutral): “An approach based on target accuracy was provided in (Gupta et al., 2010), which was further improved in terms of privacy cost and computational efﬁciency in (Liu and Talwar, 2018).”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, background): “We also note that there is an extensive literature on alternative private selection mechanisms, e.g., see Beimel et al. (2013); Chaudhuri et al. (2014); Lantz et al. (2015); Minami et al. (2016); Raskhodnikova & Smith (2016); Liu & Talwar (2019); Awan et al. (2019); McKenna & Sheldon (2020).”
CoinPress: Practical Private Mean and Covariance Estimation (2020, unknown): “The fact that the algorithm’s performance is sensitive to the choice of t, which was not true for mean estimstion, is an interesting phenomenon for further study, although private hyperparameter tuning of this sort can be addressed using [28].”
Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems (2020, unknown): “There has been both theoretical [18, 7, 26, 41, 4] and empirical research [40, 33] providing algorithms which can be used for choosing a “near-optimal” value of the clipping norm.”
EKTELO: A Framework for Defining Differentially-Private Computations (2018, background): “Other recent work [20, 26] considers the problem of data-dependent algorithm selection.”
Differentially Private Set Union (2020, unknown): “Here we will have to account for the loss in privacy budget; see Liu and Talwar [2019] for example.”
Large Language Models Can Be Strong Differentially Private Learners (2021, background): “Model selection from hyperparameter tuning on private training and validation data incurs extra leakage (Liu & Talwar, 2019; Chaudhuri & Vinterbo, 2013; Papernot & Steinke, 2021).”
TAN without a burn: Scaling Laws of DP-SGD (2022, background): “Theoretically, each training run should be charged on the overall budget, but in practice it is commonly assumed that the “bandwidth” of hyper-parameters is too small to incur any observable loss of privacy (see also Liu & Talwar (2019) for a theoretically sound way of handling this problem).”
Automatic Discovery of Privacy–Utility Pareto Fronts (2019, background): “[35] recently provided a way to choose hyperparameters that approximately maximize the utility of a given differentially private model in a way that protects the privacy of both the training and test data sets.”
Differentially Private Learning with Adaptive Clipping (2019, methodology): “An approach based on target accuracy was provided in [11], which was further improved in terms of privacy cost and computational eﬃciency in [16].”