# The Price of Selection in Differential Privacy

arXiv: https://arxiv.org/abs/1702.02970 · HTML: https://mlsanity.com/paper/1702.02970/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Feb 2017.

## Built on by (most cited first, 8 of 8)

- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees](https://mlsanity.com/paper/2104.00245/) (2021)
- [The Correlated Gaussian Sparse Histogram Mechanism](https://mlsanity.com/paper/2412.10357/) (2024)
- [Majority Vote for Distributed Differentially Private Sign Selection](https://mlsanity.com/paper/2209.04419/) (2022)
- [Smooth Partial Lotteries for Stable Randomized Selection](https://mlsanity.com/paper/2605.20069/) (2026)
- [CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplaces](https://mlsanity.com/paper/2605.23887/) (2026)

## Abstract (arXiv)

In the differentially private top-k selection problem, we are given a dataset X ∈ ± 1n × d, in which each row belongs to an individual and each column corresponds to some binary attribute, and our goal is to find a set of k ll d columns whose means are approximately as large as possible. Differential privacy requires that our choice of these k columns does not depend too much on any on individual's dataset. This problem can be solved using the well known exponential mechanism and composition properties of differential privacy. In the high-accuracy regime, where we require the error of the selection procedure to be to be smaller than the so-called sampling error α ≈ √ln(d)/n, this procedure succeeds given a dataset of size n gtrsim k ln(d). We prove a matching lower bound, showing that a dataset of size n gtrsim k ln(d) is necessary for private top-k selection in this high-accuracy regime. Our lower bound is the first to show that selecting the k largest columns requires more data than simply estimating the value of those k columns, which can be done using a dataset of size just n gtrsim k.