CoChat

Tight Lower Bounds for Differentially Private Selection

Steinke, Thomas, Ullman, Jonathan · 2017 · 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
Cited by 48

The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.

Abstract

A pervasive task in the differential privacy literature is to select the k items of “highest quality” out of a set of d items, where the quality of each item depends on a sensitive dataset that must be protected. Variants of this task arise naturally in fundamental problems like feature selection and hypothesis testing, and also as subroutines for many sophisticated differentially private algorithms. The standard approaches to these tasks-repeated use of the exponential mechanism or the sparse vector technique-approximately solve this problem given a dataset of n = O(√k log d) samples. We provide a tight lower bound for some very simple variants of the private selection problem. Our lower bound shows that a sample of size n = Ω(√k log d) is required even to achieve a very minimal accuracy guarantee. Our results are based on an extension of the fingerprinting method to sparse selection problems. Previously, the fingerprinting method has been used to provide tight lower bounds for answering an entire set of d queries, but often only some much smaller set of k queries are relevant. Our extension allows us to prove lower bounds that depend on both the number of relevant queries and the total number of queries.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/focs.2017.57

Cites

6 of 6 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 6 references

Research works printed but not linked: 38

  1. 10.1007/978-3-642-11799-2_26 · DOI
  2. 10.1145/1536414.1536465 · DOI
  3. 10.1007/978-3-540-85174-5_26 · DOI
  4. 10.1145/1250790.1250804 · DOI · Paper page
  5. 10.1038/ng.436 · DOI · Paper page
  6. 10.1145/2488608.2488652 · DOI
  7. 10.1145/2213977.2214090 · DOI · Paper page
  8. 10.1137/1.9781611973105.102 · DOI
  9. 10.1145/1806689.1806795 · DOI · Paper page
  10. 10.1137/1.9781611973075.90 · DOI
  11. 10.1145/1806689.1806786 · DOI · Paper page
  12. 10.1145/2897518.2897566 · DOI · Paper page
  13. 10.1007/11681878_14 · DOI · Paper page
  14. 10.1145/773153.773173 · DOI · Paper page
  15. 10.1007/978-3-540-28628-8_32 · DOI · Paper page
  16. 10.1145/1065167.1065184 · DOI · Paper page
  17. 10.1145/2591796.2591877 · DOI
  18. steinke, 2017, Between pure and approximate differential privacy, Journal of Privacy and Confidentiality, 7, 10.29012/jpc.v7i2.648 · DOI
  19. 10.1109/FOCS.2015.46 · DOI · Paper page
  20. 10.1109/FOCS.2007.66 · DOI · Paper page
  21. 10.1145/2591796.2591883 · DOI · Paper page
  22. 10.1145/1835804.1835869 · DOI · Paper page
  23. 10.1109/FOCS.2014.56 · DOI · Paper page
  24. talwar, 2015, Nearly optimal private lasso, Advances in neural information processing systems, 3025
  25. 10.1145/1806689.1806794 · DOI · Paper page
  26. 10.1145/2450142.2450148 · DOI · Paper page
  27. 10.1007/978-3-642-28914-9_19 · DOI · Paper page
  28. 10.1109/FOCS.2010.85 · DOI · Paper page
  29. smith, 2013, Differentially private model selection via stability arguments and the robustness of the lasso, Journal of Machine Learning Research-Proc Track, 30, 819
  30. 10.1145/2745754.2745755 · DOI
  31. dwork, 2015, Private false discovery rate control
  32. 10.1145/1536414.1536467 · DOI · Paper page
  33. bafna, 2017, The price of selection in differential privacy
  34. 10.1109/FOCS.2014.55 · DOI · Paper page
  35. kasiviswanathan, 2014, On the “semantics” of differential privacy: A bayesian formulation, Journal of Privacy and Confidentiality, 6, 10.29012/jpc.v6i1.634 · DOI
  36. 10.1137/1.9781611974782.85 · DOI
  37. 10.1007/978-3-662-53641-4_24 · DOI · Paper page
  38. steinke, 2015, Interactive fingerprinting codes and the hardness of preventing false discovery, Proceedings of The 28th Conference on Learning Theory COLT 2015, 1588

Cited by

See all 48

Metadata

Authors
Steinke, T., & Ullman, J.
Venue
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
Publisher
IEEE
Published
2017-10
Pages
552-563
ISSN
0272-5428 (ISSN-L)
OpenAlex
W2608195534
Cited by
48
References
6
FWCI
2.41
Type
conference paper
Language
en
Open access
closed

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: Tight Lower Bounds for Differentially Private Selection. https://app.cochat.ai/papers/10.1109/focs.2017.57
The paper
Steinke, T., & Ullman, J. (2017). Tight Lower Bounds for Differentially Private Selection. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). https://doi.org/10.1109/focs.2017.57

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.