# Differentially private partition selection

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2020.

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

- [Sparsity-Preserving Differentially Private Training of Large Embedding Models](https://mlsanity.com/paper/2311.08357/) (2023)
- [Urania: Differentially Private Insights into AI Use](https://mlsanity.com/paper/2506.04681/) (2025)
- [Hot PATE: Private Aggregation of Distributions for Diverse Task](https://mlsanity.com/paper/2312.02132/) (2023)
- [Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale](https://mlsanity.com/paper/2603.22363/) (2026)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Tight End-to-End Accounting for Differentially Private Synthetic Data](https://mlsanity.com/paper/2610.17249/) (2026)

## Abstract (arXiv)

Many data analysis operations can be expressed as a GROUP BY query on an unbounded set of partitions, followed by a per-partition aggregation. To make such a query differentially private, adding noise to each aggregation is not enough: we also need to make sure that the set of partitions released is also differentially private. This problem is not new, and it was recently formally introduced as differentially private set union. In this work, we continue this area of study, and focus on the common setting where each user is associated with a single partition. In this setting, we propose a simple, optimal differentially private mechanism that maximizes the number of released partitions. We discuss implementation considerations, as well as the possible extension of this approach to the setting where each user contributes to a fixed, small number of partitions.