Tight Privacy Accounting for Differential Privacy Composition

32 concepts30 papers1 proposal

When deploying Differential Privacy (DP) in real-world systems, we rarely run just a single private query. Instead, we execute complex, iterative workflows. For instance, training a deep neural network via DP-SGD requires computing gradients over thousands of mini-batches, while running a multi-round federated learning protocol involves continuous communication between clients and a server.

Every time an algorithm interacts with a sensitive dataset, a small amount of privacy leaks. To guarantee a global privacy bound $(\epsilon, \delta)$, we must compute the cumulative privacy loss across all operations—a process known as privacy composition.

The fundamental challenge is that standard, naive composition theorems assume a absolute worst-case scenario at every single step. This pessimistic accounting overestimates the actual privacy leakage, creating a massive gap between the calculated privacy budget and reality. To satisfy a target privacy guarantee under these loose bounds, practitioners are forced to inject excessive noise, which severely degrades model utility and accuracy.

To solve this, modern privacy accounting shifts the paradigm: instead of tracking worst-case scalar bounds, we track the exact probability distribution of the privacy loss.

The Core Intuition: Privacy Loss as a Random Variable

To understand why tight composition works, we must look at how privacy loss behaves under independent noise.

Suppose an adversary is trying to determine whether a specific individual's data is present in a dataset. They observe the output of a private mechanism and compute the log-likelihood ratio of that output under two scenarios: dataset $X$ (with the individual) versus dataset $X'$ (without the individual). This log-likelihood ratio is the privacy loss.

Because the mechanism injects random noise (such as Gaussian or Laplace noise) to mask individual contributions, the privacy loss itself is not a fixed number—it is a random variable.

When we compose multiple independent private mechanisms, the total privacy loss is simply the sum of these independent random variables. Basic composition theorems merely add up the maximum possible values of these variables. However, from elementary probability, we know that the sum of independent random variables tends to concentrate around its mean. The probability that the random noise consistently aligns in the absolute worst-case direction across thousands of iterations is astronomically small.

By tracking the actual distribution of the privacy loss rather than its worst-case upper bound, we can exploit this concentration of measure to get significantly tighter privacy guarantees.

Tracking Moments: Rényi and Concentrated DP

The first major breakthrough in tight privacy accounting came from tracking the higher moments of the privacy loss distribution.

In their seminal paper on DP-SGD, Martı́n Abadi et al. introduced the Moments Accountant in Deep Learning with Differential Privacy. Instead of bounding $(\epsilon, \delta)$ directly, the Moments Accountant bounds the log of the moment-generating function of the privacy loss variable. Because the moments of independent random variables add up linearly, tracking these moments across thousands of iterations is mathematically clean and yields vastly tighter bounds than traditional advanced composition.

This approach was generalized into a distinct privacy framework called Zero-Concentrated Differential Privacy (zCDP) by Mark Bun et al. in Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. By utilizing Rényi divergence to bound privacy loss, zCDP provides an elegant, analytical framework that is particularly well-suited for the Gaussian mechanism.

Practitioners have leveraged these tight bounds to make iterative algorithms viable. For example, Mijung Park et al. applied zCDP and the Moments Accountant to iterative expectation-maximization in DP-EM: Differentially Private Expectation Maximization, drastically reducing the noise required for learning complex mixture models. Similarly, Peter Kairouz et al. utilized concentrated DP bounds in The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation to maintain high model utility across multiple training rounds without exceeding strict privacy budgets.

The Central Limit Theorem for Privacy

If composing independent privacy loss variables is analogous to summing independent random variables, can we apply the Central Limit Theorem (CLT)?

Yes. As the number of composed mechanisms grows, the cumulative privacy loss distribution converges to a Gaussian distribution. This insight underpins the $f$-Differential Privacy framework, specifically Gaussian Differential Privacy (GDP), introduced by Zhiqi Bu et al. in Deep Learning with Gaussian Differential Privacy.

[Privacy Loss 1] + [Privacy Loss 2] + ...

+ [Privacy Loss N] 
                       │
                       ▼ (By Privacy CLT)
         [Normal/Gaussian Distribution]

GDP frames privacy not through abstract parameters, but operationally as a hypothesis testing problem: how effectively can an adversary distinguish between dataset $X$ and $X'$? The trade-off between the adversary's Type I error (false alarm) and Type II error (missed detection) defines the privacy profile. Under GDP, the composition of many steps is completely characterized by a single parameter $\mu$, which denotes the distance between two normal distributions. This provides an analytically exact and tight bound for algorithms like NoisySGD. To expand the utility of this framework, Yi Liu developed tools in Identification, Amplification and Measurement: A bridge to Gaussian Differential Privacy to seamlessly convert traditional DP mechanisms into the tighter GDP representation.

Exact Numerical Composition via FFT

While analytical frameworks like zCDP and GDP offer excellent approximations, they can still introduce mathematical slack for certain noise distributions or small numbers of compositions. To achieve the absolute tightest bounds possible, we can compute the exact distribution of the total privacy loss numerically.

Because the sum of independent random variables corresponds mathematically to the convolution of their individual probability density functions, calculating the composed privacy loss requires computing repeated convolutions. Doing this naively is computationally prohibitive.

To bypass this bottleneck, Antti Koskela et al. introduced the Fourier Accountant in Computing Exact Guarantees for Differential Privacy and Computing Tight Differential Privacy Guarantees Using FFT. By leveraging the Fast Fourier Transform (FFT), the Fourier Accountant transforms the complex operation of convolution into simple pointwise multiplication in the frequency domain.

[Privacy Loss Distributions] ──► [ FFT ] ──► [ Pointwise Multiplication ] ──► [ IFFT ] ──► [ Exact Total Privacy Loss ]

This numerical approach allows practitioners to calculate nearly exact $(\epsilon, \delta)$ guarantees in a fraction of a second. The efficiency of this method was pushed even further by Lukas Wutschitz et al. in Numerical Composition of Differential Privacy, achieving near-optimal runtimes that make exact numerical accounting practical for massive, industrial-scale machine learning models.

Dynamic and Adaptive Accounting

In many real-world exploratory data analysis scenarios, we do not know the sequence of queries in advance. An analyst might decide which query to run next based on the answers to previous queries. Standard composition theorems struggle here because they assume a static, predetermined sequence of operations.

To handle this adaptively without falling back on pessimistic worst-case assumptions, Ryan M. Rogers et al. introduced the concepts of privacy filters and privacy odometers in Privacy Odometers and Filters: Pay-as-you-Go Composition.

  • A privacy odometer acts like a real-time dashboard, tracking the cumulative privacy loss dynamically as the analyst runs queries.
  • A privacy filter acts as a safety switch, allowing the analyst to choose privacy parameters on the fly and automatically halting further computation the moment the total budget is threatened.

This dynamic tracking is especially powerful when dealing with "accuracy-first" mechanisms, where noise is added adaptively until a target accuracy is reached. In Adaptive Privacy Composition for Accuracy-first Mechanisms, the authors developed specialized privacy filters that seamlessly compose standard DP queries with accuracy-first queries, ensuring that adaptive exploration does not prematurely exhaust the global privacy budget.

Key Foundational Work

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds (2016) — contributed 1 concept elements to this direction.
Deep Learning with Differential Privacy (2016) — contributed 1 concept elements to this direction.
DP-EM: Differentially Private Expectation Maximization (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_loose_privacy_composition_ceef2492,
  title = {loose privacy composition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/loose-privacy-composition/rdr_ceef2492344f42a5ae169963951c3aa1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_loose_privacy_composition_ceef2492_v1,
  title = {loose privacy composition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/loose-privacy-composition/rdr_ceef2492344f42a5ae169963951c3aa1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake