# Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 25 Jun 2022.

## Builds on (most cited first, 9 of 9)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Numerical Composition of Differential Privacy](https://mlsanity.com/paper/2106.02848/) (2021)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [Three Variants of Differential Privacy: Lossless Conversion and Applications](https://mlsanity.com/paper/2008.06529/) (2020)
- [Guidelines for Implementing and Auditing Differentially Private Systems](https://mlsanity.com/paper/2002.04049/) (2020)
- [Optimal Noise-Adding Mechanism in Additive Differential Privacy](https://mlsanity.com/paper/1809.10224/) (2018)

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

- [Beyond Laplace and Gaussian: Exploring the Generalized Gaussian Mechanism for Private Machine Learning](https://mlsanity.com/paper/2506.12553/) (2025)
- [Bayes-Nash Generative Privacy Against Membership Inference Attacks](https://mlsanity.com/paper/2410.07414/) (2024)
- [Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy](https://mlsanity.com/paper/2601.14597/) (2026)
- [On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clustering](https://mlsanity.com/paper/2603.26963/) (2026)

## Abstract (arXiv)

Most differential privacy mechanisms are applied (i.e., composed) numerous times on sensitive data. We study the design of optimal differential privacy mechanisms in the limit of a large number of compositions. As a consequence of the law of large numbers, in this regime the best privacy mechanism is the one that minimizes the Kullback-Leibler divergence between the conditional output distributions of the mechanism given two different inputs. We formulate an optimization problem to minimize this divergence subject to a cost constraint on the noise. We first prove that additive mechanisms are optimal. Since the optimization problem is infinite dimensional, it cannot be solved directly; nevertheless, we quantize the problem to derive near-optimal additive mechanisms that we call "cactus mechanisms" due to their shape. We show that our quantization approach can be arbitrarily close to an optimal mechanism. Surprisingly, for quadratic cost, the Gaussian mechanism is strictly sub-optimal compared to this cactus mechanism. Finally, we provide numerical results which indicate that cactus mechanism outperforms the Gaussian mechanism for a finite number of compositions.