mlsanityData to 7 Oct 2026

Fully Adaptive Composition in Differential Privacy

arXiv 2203.05481 ↗First posted 10 Mar 2022cs.LG cs.CR cs.DScited by 22

Not on the map. Why?

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.

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

Builds on

14 of 44 references.

References · 14

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2017Renyi Differential Privacycited by 643
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  4. 2013The Composition Theorem for Differential Privacycited by 290
  5. 2018Subsampled R'enyi Differential Privacy and Analytical Moments Accountantcited by 234
  6. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  7. 2016Concentrated Differential Privacycited by 139
  8. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
  9. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  10. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  11. 2020Individual Privacy Accounting via a Renyi Filtercited by 57
  12. 2016Privacy Odometers and Filters: Pay-as-you-Go Compositioncited by 32
2 more
  1. 2017Accuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained ERMcited by 20
  2. 2021Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learningcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 3; 2024: 8; 2025: 2; 2026: 6.

22 papers.

Sort:

By area:

  1. 2024Privacy-Preserving Retrieval-Augmented Generation with Differential Privacycited by 38
  2. 2022Individual Privacy Accounting for Differentially Private Stochastic Gradient Descentcited by 20
  3. 2022Individual Privacy Accounting with Gaussian Differential Privacycited by 19
  4. 2024Adaptive Randomized Smoothing: Certified Adversarial Robustness for Multi-Step Defencescited by 9
  5. 2024Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Datacited by 8
  6. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  7. 2024Federated Learning on Riemannian Manifolds with Differential Privacycited by 5
  8. 2023Adaptive Principal Component Regression with Applications to Panel Datacited by 4
  9. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  10. 2022Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraintscited by 3
  11. 2023Adaptive Privacy Composition for Accuracy-first Mechanismscited by 2
  12. 2024On the Privacy of Selection Mechanisms with Gaussian Noisecited by 2
10 more
  1. 2024Differentially Private Optimization with Sparse Gradientscited by 2
  2. 2025Private-RAG: Answering Multiple Queries with LLMs while Keeping Your Data Privatecited by 2
  3. 2024Adaptive Data Analysis for Growing Datacited by 1
  4. 2025Differentially Private In-Context Learning with Nearest Neighbor Searchcited by 1
  5. 2026Your Privacy Depends on Others: Collusion Vulnerabilities in Individual Differential Privacycited by 1
  6. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 0
  7. 2026Private Adaptive Covariance Estimation via Gaussian Graphical Modelscited by 0
  8. 2026Private Anytime Selective-Risk Certification for Federated Retrieval-Augmented Generation: Guarantees and Empirical Limitscited by 0
  9. 2026Privacy Without Regret: Differentially Private Inference-Time Alignmentcited by 0
  10. 2026Pushing the (Decision) Boundaries: Dynamically Calibrating Differentially Private Noise to Explainability in Federated Learningcited by 0