Source-linked AI summary
Tight Lower Bounds for Differentially Private Selection
Thomas Steinke, Jonathan Ullman
TL;DR
Differentially private selection must identify a small set of high-quality items among d items when their values depend on sensitive data. The paper strengthens previous fingerprinting-based differential-privacy lower bounds by setting β = ω(1), beyond prior results corresponding to β = O(1). The paper proves essentially optimal lower bounds for approximate top-k selection and multiple hypothesis testing, including minimal-accuracy top-k guarantees.
Problem
Differentially private selection must identify a small set of high-quality items among d items when their values depend on sensitive data.
Source: §1 · p. 2Method
The paper strengthens previous fingerprinting-based differential-privacy lower bounds by setting β = ω(1), beyond prior results corresponding to β = O(1).
Source: §1.1 · p. 5Results
The paper proves essentially optimal lower bounds for approximate top-k selection and multiple hypothesis testing, including minimal-accuracy top-k guarantees.
Source: §1 · p. 3, Application to Multiple Hypothesis… · p. 4Takeaways & Limitations
The results show that even simple private selection problems remain sample-intensive when only a small subset of the total coordinates is relevant.
Source: §1 · p. 3, Application to Multiple Hypothesis… · p. 4, §1.1 · p. 5The proof overview is informal and the lower bound's dependence on δ is omitted from the main presentation, though a group-privacy reduction can add a log(1/δ) factor.
Source: Overview of the Analysis · p. 6, §4.1 · p. 16
Abstract
from arXiv · showhide
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(\sqrt{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 = \Omega(\sqrt{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.
1 Introduction
The paper proves tight lower bounds for simple differentially private selection problems, showing that even minimal accuracy requires substantial samples. It extends fingerprinting-based techniques to sparse selection and applies them to approximate top-k selection and multiple hypothesis testing.
1 Introduction
- Differentially private selection identifies a small set of high-mean coordinates from sensitive binary samples, motivated by feature selection and hypothesis testing.The procedure must protect each individual sample while selecting k coordinates whose population means are large.Source: §1 · p. 2
- The approximate top-k lower bound is essentially optimal even for product distributions and applies when the error is at most k/10.This guarantee is only slightly stronger than the trivial error k obtained by selecting the first k coordinates.Source: §1 · p. 3
Empirical Error vs. Population Error
- Population-mean lower bounds differ qualitatively from prior empirical-error lower bounds, which addressed very small error and required n = Ω(k log d).The paper studies larger-error population estimation, whereas prior work could obtain zero population error on uniformly random datasets with fixed population mean.Source: Empirical Error vs. Population Error · p. 3
Application to Multiple Hypothesis Testing
- For multiple hypothesis testing, the task separates coordinates above τ from those below a lower threshold τ′, with non-private algorithms using O_{τ,τ′}(log d) samples.Private algorithms use O(√k log d) samples when k bounds the number of coordinates above τ′.Source: Application to Multiple Hypothesis… · p. 4
- The multiple-hypothesis-testing sample complexity is essentially optimal even for product distributions.Theorem 2 permits a false-positive probability as large as ρk/d, so the expected number of false positives can be Ω(k), a constant fraction of the true positives.Source: Application to Multiple Hypothesis… · p. 4
1.1 Techniques
- The technique strengthens earlier fingerprinting-based lower bounds, which correspond to β = O(1), by using β = ω(1); for the top-k lower bound, β = Θ(log(d/k)).The construction uses Beta(α,β) distributions over [0,1]; in the symmetric case α = β, Beta(1,1) is uniform and becomes more concentrated around 1/2 as β →∞.Source: §1.1 · p. 5
Overview of the Analysis
- The proof compares privacy-based upper bounds and accuracy-based lower bounds on a correlation quantity Z, using fingerprinting-style analysis to force a contradiction.Differential privacy makes the correlation with an individual sample small, while accurate selection makes its expectation large.Source: Overview of the Analysis · pp. 5–6
1.2 Relationship to Previous Lower Bounds and Attacks
- Relative to prior work, the lower bound applies to a simple fixed-value selection problem rather than only to complex adaptive selection or structured query settings.The paper also notes that pure differential privacy has a different top-k complexity, Θ(k log d), while packing arguments do not yield nontrivial bounds for approximate differential privacy.Source: §1.2 · p. 7
2 Preliminaries
The preliminaries establish notation, differential privacy, and beta-distribution facts used in the lower-bound proof. In particular, beta anti-concentration supplies many unusually large coordinates despite a mean of 1/2.
2.1 Notational Conventions
- The notation treats datasets as n×d matrices, with rows indexing individuals and columns indexing items or coordinates.Source: §2.1 · p. 7
2.2 Differential Privacy
- Neighboring datasets differ on at most one row, and differential privacy constrains randomized algorithm outputs on every neighboring pair.Source: §2.2 · p. 7
- The lower bounds apply with ε = 1 and δ nearly 1/n, covering nearly the full parameter range where differential privacy is meaningful.Source: §2.2 · p. 8
2.3 Beta Distributions
- A Beta(α,β) distribution lies on [0,1], with mean α/(α + β) and variance αβ/((α + β)^2(α + β + 1)).Source: §2.3 · p. 8
- Beta(1,1) is uniform, while Beta(β,β) concentrates around 1/2 as β increases.Source: §2.3 · p. 8
- For suitable β, the k largest among d independent Beta(β,β) samples have expected value at least 3/4, using beta anti-concentration.Source: §2.3 · p. 8, §4.1 · p. 16
3 Proof of the Main Lower Bound (Theorem 3)
The proof derives contradictory bounds on a correlation statistic: privacy makes it small, while accuracy and an extended fingerprinting lemma make it large. Combining these bounds yields the main lower bound.
3 Proof of the Main Lower Bound (Theorem 3)
- The proof models each coordinate mean as an independent Beta(β,β) draw and samples an n×d Bernoulli dataset conditioned on those means.Source: §3 · pp. 10–11
- When n is too small, the analysis obtains contradictory upper and lower bounds on the expected statistic E[Z].Source: §3 · p. 11
3.1 Upper Bound via Privacy
- Differential privacy supplies the upper bound on E[Z] by replacing one individual’s row with an independent draw and exploiting output indistinguishability.Source: §3.1 · pp. 11–12
3.2 Lower Bound via Accuracy
- Accuracy supplies the lower bound through a fingerprinting lemma that refines prior fingerprinting arguments by exploiting the distribution of P.Source: §3.2 · p. 12
3.2.2 Using the Fingerprinting Lemma
- Applying the lemma coordinatewise and summing over j produces the lower bound on E[Z], which is then combined with the privacy upper bound to prove Theorem 3.Source: §3.2.1 · p. 14, §3.2.2 · pp. 14–15
3.3 Putting it Together
- The final step combines Lemmas 8 and 11 with the accuracy assumption to complete the main lower-bound proof.Source: §3.3 · p. 15
4 Using our Lower Bound
The lower bound framework yields nearly matching bounds for approximate top-k selection and extends to multiple hypothesis testing, including algorithms with only average-case accuracy guarantees.
4.1 Application to Approximate Top-k Selection
- Theorem 12 gives an upper bound for approximate top-k selection using repeated applications of the exponential mechanism and privacy composition.The same theorem can alternatively provide ρ-concentrated differential privacy with the stated accuracy guarantee.Source: §4.1 · p. 16
- The lower bound for approximate top-k selection is nearly tight, up to a factor of O(log(1/δ)) in most parameter regimes.The lower bound applies even when algorithms provide only average-case accuracy guarantees.Source: §4.1 · p. 16
- Corollary 13 gives the bound k log(d/(16k+208)) for n,d,k ∈ N with d ≥ max{16k,224}.Source: §4.1 · p. 16
4.2 Application to Multiple Hypothesis Testing
- Under the stated assumptions, the analysis says that in expectation there are at least 2k such values P_j, and k plays roughly the same role as in top-k selection.Source: §4.2 · p. 17
A Releasing the Dataset Mean
The paper applies its general lower-bound theorem to releasing the dataset mean, recovering known differentially private mean-release lower bounds.
A Releasing the Dataset Mean
- The framework recovers known lower bounds for releasing the dataset mean [BUV14].The application considers independently drawn coordinate means and a differentially private mechanism for releasing a vector in [0,1]^d.Source: A Releasing the Dataset Mean · p. 22