Private selection from private candidates
Open accessThe DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000042 · Cited by 5,557
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
The Statistical Crisis in Science
Gelman, A., & Loken, E. (2014) · American Scientist · doi:10.1511/2014.111.460 · Cited by 963
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898 · cited 1×
“tially Private Selection problem, often known as dierentially private maximization, is a very general algorithmic problem that arises in many applications. Some examples include private PAC learning [21], private frequent itemset mining [4], private PCA [8,20] and private multiple hypothesis testing [15,34]. The Spars…”
BackgroundSemi-supervised Knowledge Transfer for Deep Learning from Private Training Data
Papernot, N., Abadi, M., Erlingsson, Ú., Goodfellow, I., & Talwar, K. (2016) · arXiv · doi:10.48550/arxiv.1610.05755 · Cited by 492
Self-citationPrivate Learning and Sanitization: Pure vs. Approximate Differential Privacy
Beimel, A., Nissim, K., & Stemmer, U. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40328-6_26 · Cited by 72
Cited by
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z., Denison, C., McMahan, H. B., Vassilvitskii, S., Chien, S., & Thakurta, A. G. (2023) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.14649 · Cited by 166
“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).”
BackgroundTraining Production Language Models without Memorizing User Data
Ramaswamy, S., Thakkar, O., Mathews, R., Andrew, G., McMahan, H. B., & Beaufays, F. (2020) · arXiv · doi:10.48550/arxiv.2009.10031 · Cited by 37
Rajotte, J.-F., Mukherjee, S., Robinson, C., Ortiz, A., West, C., Ferres, J. M. L., & Ng, R. T. (2021) · Proceedings of the Conference on Information Technology for Social Good · doi:10.1145/3462203.3475875 · Cited by 34
Automatic Discovery of Privacy–Utility Pareto Fronts
Avent, B., González, J., Diethe, T., Paleyes, A., & Balle, B. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2020-0060 · Cited by 3
Metadata
- Authors
- Liu, J., & Talwar, K.
- Venue
- Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
- Publisher
- ACM
- Published
- 2019-06-23
- Pages
- 298-309
- OpenAlex
- W2964296660
- Cited by
- 64
- References
- 7
- FWCI
- 3.31
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Private selection from private candidates. https://app.cochat.ai/papers/10.1145/3313276.3316377
- The paper
- Liu, J., & Talwar, K. (2019). Private selection from private candidates. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. https://doi.org/10.1145/3313276.3316377
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.