# On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

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

## Key facts

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

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

- [A Central Limit Theorem for Differentially Private Query Answering](https://mlsanity.com/paper/2103.08721/) (2021)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)
- [Predicting adaptively chosen observables in quantum systems](https://mlsanity.com/paper/2410.15501/) (2024)
- [Fixed-Parameter Tractability of Private Synthetic Data Generation](https://mlsanity.com/paper/2606.11283/) (2026)

## Abstract (arXiv)

In this work, we study the problem of answering k queries with (ε, δ)-differential privacy, where each query has sensitivity one. We give an algorithm for this task that achieves an expected ℓ_∞ error bound of O(frac1ε√k log frac1δ), which is known to be tight (Steinke and Ullman, 2016). A very recent work by Dagan and Kur (2020) provides a similar result, albeit via a completely different approach. One difference between our work and theirs is that our guarantee holds even when δ < 2-Omega(k/(log k)8) whereas theirs does not apply in this case. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the ℓ∞ error bound of O(frac1ε√k log frac1δ) holds not only in expectation but always (i.e., with probability one) while we can only get a high probability (or expected) guarantee on the error.