# Tight Lower Bounds for Locally Differentially Private Selection

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2018.

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

- [Decepticons: Corrupted Transformers Breach Privacy in Federated Learning for Language Models](https://mlsanity.com/paper/2201.12675/) (2022)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Unsupervised Information Obfuscation for Split Inference of Neural Networks](https://mlsanity.com/paper/2104.11413/) (2021)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [When approximate design for fast homomorphic computation provides differential privacy guarantees](https://mlsanity.com/paper/2304.02959/) (2023)

## Abstract (arXiv)

We prove a tight lower bound (up to constant factors) on the sample complexity of any non-interactive local differentially private protocol for optimizing a linear function over the simplex. This lower bound also implies a tight lower bound (again, up to constant factors) on the sample complexity of any non-interactive local differentially private protocol implementing the exponential mechanism. These results reveal that any local protocol for these problems has exponentially worse dependence on the dimension than corresponding algorithms in the central model. Previously, Kasiviswanathan et al. (FOCS 2008) proved an exponential separation between local and central model algorithms for PAC learning the class of parity functions. In contrast, our lower bound are quantitatively tight, apply to a simple and natural class of linear optimization problems, and our techniques are arguably simpler.