Private Selection from Private Candidates

Understand

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.