Search papers, labs, and topics across Lattice.
This paper generalizes a known optimal $(\varepsilon, \delta)$-DP algorithm for single-partition selection to the $(\alpha, \varepsilon)$-Rényi differential privacy (RDP) setting, enabling tighter privacy analysis under composition. They introduce an optimal algorithm for $L^2$ bounded weighted partition selection, improving upon the Gaussian mechanism and existing partition selection algorithms like PolicyGaussian and MAD2R. The paper also demonstrates a fundamental trade-off between releasing partition frequencies and privacy guarantees, showing that additive noise mechanisms are inherently suboptimal compared to non-additive ones.
Rényi differential privacy unlocks tighter privacy guarantees in partition selection, but releasing partition frequencies comes at a cost.
A common problem in private data analysis is the partition selection problem, where each user holds a set of partitions (e.g. keys in a GROUP BY operation) from a possibly unbounded set. The challenge here is in maximizing the set of released partitions while respecting a differential privacy constraint. Previous work [Desfontaines et al., PoPETS 2022] presented an optimal $(\varepsilon, \delta)$-DP algorithm when each user submits only a single partition. We generalize this approach to find the optimal algorithm under $\delta$-approximate $(\alpha, \varepsilon)$-R\'enyi differential privacy (RDP), which allows much tighter analysis under composition. Motivated by the non-existence of a general optimality result in the case where users submit multiple partitions each, we present an extension of our optimal algorithm tuned for $L^2$ bounded weighted partition selection which can be used as a drop-in improvement over the Gaussian mechanism any time the partition frequency is not also needed. We show that our primitive can be easily plugged into state of the art partition selection algorithms (PolicyGaussian from [Gopi et al., ICML 2020] and MAD2R from [Chen et al., ICML 2025]), improving performance both for parallel and sequential adaptive algorithms. Finally, we show that there is an inherent cost to algorithms which do support releasing the frequency as well as the partitions. Specifically, we formulate a basic notion of optimal approximate RDP algorithm for partition selection using additive noise, and show that there is a numerical separation between additive and non-additive noise mechanisms for this problem.
