# Adaptive Privacy Composition for Accuracy-first Mechanisms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 24 Jun 2023.

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

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [Fully Adaptive Composition in Differential Privacy](https://mlsanity.com/paper/2203.05481/) (2022)
- [Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM](https://mlsanity.com/paper/1705.10829/) (2017)
- [Concurrent Composition of Differential Privacy](https://mlsanity.com/paper/2105.14427/) (2021)
- [Composition Theorems for Interactive Differential Privacy](https://mlsanity.com/paper/2207.09397/) (2022)
- [Concurrent Composition Theorems for Differential Privacy](https://mlsanity.com/paper/2207.08335/) (2022)
- [Gradual Release of Sensitive Data under Differential Privacy](https://mlsanity.com/paper/1504.00429/) (2015)
- [Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints](https://mlsanity.com/paper/2206.07234/) (2022)

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

- [On the Privacy of Selection Mechanisms with Gaussian Noise](https://mlsanity.com/paper/2402.06137/) (2024)
- [Privacy Without Regret: Differentially Private Inference-Time Alignment](https://mlsanity.com/paper/2608.26324/) (2026)

## Abstract (arXiv)

In many practical applications of differential privacy, practitioners seek to provide the best privacy guarantees subject to a target level of accuracy. A recent line of work by Ligett et al. '17 and Whitehouse et al. '22 has developed such accuracy-first mechanisms by leveraging the idea of noise reduction that adds correlated noise to the sufficient statistic in a private computation and produces a sequence of increasingly accurate answers. A major advantage of noise reduction mechanisms is that the analysts only pay the privacy cost of the least noisy or most accurate answer released. Despite this appealing property in isolation, there has not been a systematic study on how to use them in conjunction with other differentially private mechanisms. A fundamental challenge is that the privacy guarantee for noise reduction mechanisms is (necessarily) formulated as ex-post privacy that bounds the privacy loss as a function of the released outcome. Furthermore, there has yet to be any study on how ex-post private mechanisms compose, which allows us to track the accumulated privacy over several mechanisms. We develop privacy filters [Rogers et al. '16, Feldman and Zrnic '21, and Whitehouse et al. '22'] that allow an analyst to adaptively switch between differentially private and ex-post private mechanisms subject to an overall differential privacy guarantee.