# Fully Adaptive Composition in Differential Privacy

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 10 Mar 2022.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [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)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Privacy Odometers and Filters: Pay-as-you-Go Composition](https://mlsanity.com/paper/1605.08294/) (2016)
- [Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERM](https://mlsanity.com/paper/1705.10829/) (2017)
- [Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learning](https://mlsanity.com/paper/2103.01379/) (2021)

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

- [Privacy-Preserving Retrieval-Augmented Generation with Differential Privacy](https://mlsanity.com/paper/2412.04697/) (2024)
- [Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent](https://mlsanity.com/paper/2206.02617/) (2022)
- [Individual Privacy Accounting with Gaussian Differential Privacy](https://mlsanity.com/paper/2209.15596/) (2022)
- [Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defences](https://mlsanity.com/paper/2406.10427/) (2024)
- [Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Data](https://mlsanity.com/paper/2403.07797/) (2024)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [Adaptive Principal Component Regression with Applications to Panel Data](https://mlsanity.com/paper/2307.01357/) (2023)
- [Federated Learning on Riemannian Manifolds with Differential Privacy](https://mlsanity.com/paper/2404.10029/) (2024)
- [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (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)
- [Differentially Private Optimization with Sparse Gradients](https://mlsanity.com/paper/2404.10881/) (2024)
- [Adaptive Data Analysis for Growing Data](https://mlsanity.com/paper/2405.13375/) (2024)
- [Differentially Private In-Context Learning with Nearest Neighbor Search](https://mlsanity.com/paper/2511.04332/) (2025)
- [Your Privacy Depends on Others: Collusion Vulnerabilities in Individual Differential Privacy](https://mlsanity.com/paper/2601.12922/) (2026)
- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)
- [Private Adaptive Covariance Estimation via Gaussian Graphical Models](https://mlsanity.com/paper/2605.24295/) (2026)
- [Private Anytime Selective-Risk Certification for Federated Retrieval-Augmented Generation: Guarantees and Empirical Limits](https://mlsanity.com/paper/2608.07913/) (2026)
- [Privacy Without Regret: Differentially Private Inference-Time Alignment](https://mlsanity.com/paper/2608.26324/) (2026)
- [Pushing the (Decision) Boundaries: Dynamically Calibrating Differentially Private Noise to Explainability in Federated Learning](https://mlsanity.com/paper/2609.03851/) (2026)

## Abstract (arXiv)

Composition is a key feature of differential privacy. Well-known advanced composition theorems allow one to query a private database quadratically more times than basic privacy composition would permit. However, these results require that the privacy parameters of all algorithms be fixed before interacting with the data. To address this, Rogers et al. introduced fully adaptive composition, wherein both algorithms and their privacy parameters can be selected adaptively. They defined two probabilistic objects to measure privacy in adaptive composition: privacy filters, which provide differential privacy guarantees for composed interactions, and privacy odometers, time-uniform bounds on privacy loss. There are substantial gaps between advanced composition and existing filters and odometers. First, existing filters place stronger assumptions on the algorithms being composed. Second, these odometers and filters suffer from large constants, making them impractical. We construct filters that match the rates of advanced composition, including constants, despite allowing for adaptively chosen privacy parameters. En route we also derive a privacy filter for approximate zCDP. We also construct several general families of odometers. These odometers match the tightness of advanced composition at an arbitrary, preselected point in time, or at all points in time simultaneously, up to a doubly-logarithmic factor. We obtain our results by leveraging advances in martingale concentration. In sum, we show that fully adaptive privacy is obtainable at almost no loss.