# Privacy Odometers and Filters: Pay-as-you-Go Composition

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2016.

## Built on by (most cited first, 30 of 33)

- [Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions](https://mlsanity.com/paper/2207.04380/) (2022)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [Privacy-Preserving Retrieval-Augmented Generation with Differential Privacy](https://mlsanity.com/paper/2412.04697/) (2024)
- [Fully Adaptive Composition in Differential Privacy](https://mlsanity.com/paper/2203.05481/) (2022)
- [Individual Privacy Accounting with Gaussian Differential Privacy](https://mlsanity.com/paper/2209.15596/) (2022)
- [Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learning](https://mlsanity.com/paper/2103.01379/) (2021)
- [A Randomized Approach for Tight Privacy Accounting](https://mlsanity.com/paper/2304.07927/) (2023)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [Cross-silo Federated Learning with Record-level Personalized Differential Privacy](https://mlsanity.com/paper/2401.16251/) (2024)
- [Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences](https://mlsanity.com/paper/2406.10427/) (2024)
- [Generalization in the Face of Adaptivity: A Bayesian Perspective](https://mlsanity.com/paper/2106.10761/) (2021)
- [Fully Adaptive Composition for Gaussian Differential Privacy](https://mlsanity.com/paper/2210.17520/) (2022)
- ["Private Prediction Strikes Back!'' Private Kernelized Nearest Neighbors with Individual Renyi Filter](https://mlsanity.com/paper/2306.07381/) (2023)
- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [A Neighbourhood-Aware Differential Privacy Mechanism for Static Word Embeddings](https://mlsanity.com/paper/2309.10551/) (2023)
- [Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints](https://mlsanity.com/paper/2206.07234/) (2022)
- [On the Privacy of Selection Mechanisms with Gaussian Noise](https://mlsanity.com/paper/2402.06137/) (2024)
- [Private-RAG: Answering Multiple Queries with LLMs while Keeping Your Data Private](https://mlsanity.com/paper/2511.07637/) (2025)
- [Adaptive Privacy Composition for Accuracy-first Mechanisms](https://mlsanity.com/paper/2306.13824/) (2023)
- [DPack: Efficiency-Oriented Privacy Budget Scheduling](https://mlsanity.com/paper/2212.13228/) (2022)
- [On Using Secure Aggregation in Differentially Private Federated Learning with Multiple Local Steps](https://mlsanity.com/paper/2407.19286/) (2024)
- [PROPS: Progressively Private Self-alignment of Large Language Models](https://mlsanity.com/paper/2508.06783/) (2025)
- [AVEC: Bootstrapping Privacy for Local LLMs](https://mlsanity.com/paper/2509.10561/) (2025)
- [Your Privacy Depends on Others: Collusion Vulnerabilities in Individual Differential Privacy](https://mlsanity.com/paper/2601.12922/) (2026)
- [Differentially Private Block-wise Gradient Shuffle for Deep Learning](https://mlsanity.com/paper/2407.21347/) (2024)
- [CURATE: Scaling-up Differentially Private Causal Graph Discovery](https://mlsanity.com/paper/2409.19060/) (2024)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Adaptive Diffusion Denoised Smoothing : Certified Robustness via Randomized Smoothing with Differentially Private Guided Denoising Diffusion](https://mlsanity.com/paper/2507.08163/) (2025)
- [Beyond One-Size-Fits-All: Neural Networks for Differentially Private Tabular Data Synthesis](https://mlsanity.com/paper/2511.13893/) (2025)
- [DPSR: Differentially Private Sparse Reconstruction via Multi-Stage Denoising for Recommender Systems](https://mlsanity.com/paper/2512.18932/) (2025)

## Abstract (arXiv)

In this paper we initiate the study of adaptive composition in differential privacy when the length of the composition, and the privacy parameters themselves can be chosen adaptively, as a function of the outcome of previously run analyses. This case is much more delicate than the setting covered by existing composition theorems, in which the algorithms themselves can be chosen adaptively, but the privacy parameters must be fixed up front. Indeed, it isn't even clear how to define differential privacy in the adaptive parameter setting. We proceed by defining two objects which cover the two main use cases of composition theorems. A privacy filter is a stopping time rule that allows an analyst to halt a computation before his pre-specified privacy budget is exceeded. A privacy odometer allows the analyst to track realized privacy loss as he goes, without needing to pre-specify a privacy budget. We show that unlike the case in which privacy parameters are fixed, in the adaptive parameter setting, these two use cases are distinct. We show that there exist privacy filters with bounds comparable (up to constants) with existing privacy composition theorems. We also give a privacy odometer that nearly matches non-adaptive private composition theorems, but is sometimes worse by a small asymptotic factor. Moreover, we show that this is inherent, and that any valid privacy odometer in the adaptive parameter setting must lose this factor, which shows a formal separation between the filter and odometer use-cases.