When training machine learning models on sensitive data, we rarely look at the dataset just once. In iterative algorithms like Differentially Private Stochastic Gradient Descent (DP-SGD), we compute gradients on random mini-batches thousands of times, injecting noise at every single step to protect individual privacy.
The fundamental challenge is composition: how do we track the total privacy leakage across an entire training run?
Traditional differential privacy (DP) composition theorems treat each step as a worst-case event and add up the privacy parameters $(\epsilon, \delta)$ loosely. This creates a massive "privacy tax." To guarantee a reasonable overall privacy budget, practitioners are forced to inject so much noise at each step that the final model becomes virtually useless.
The breakthrough that makes modern private deep learning viable is a shift in perspective: treating privacy loss not as a static, worst-case scalar, but as a random variable that concentrates over time. By tracking the full distribution of this variable, advanced privacy accountants allow us to train models with orders of magnitude less noise.
The Intuition: The Law of Large Flukes
To understand why traditional accounting fails, imagine flipping a biased coin 1,000 times. Standard DP composition bounds the total privacy loss by assuming you will flip "heads" every single time. While technically possible, the probability of hitting the absolute worst-case leakage at every single step of a long training run is astronomically small.
In reality, privacy loss is a random variable. When a randomized mechanism outputs a result, the privacy loss is the log-likelihood ratio of producing that output under a dataset $X$ versus a neighboring dataset $Y$. Because the noise added at each step is independent, the total privacy loss after many steps is simply the sum of these independent random variables.
Just like the Central Limit Theorem tells us that the sum of independent random variables concentrates into a predictable Gaussian bell curve, the cumulative privacy loss of an iterative algorithm concentrates tightly around its expected value. Advanced accounting frameworks are designed to measure this concentration precisely.
Analytical Relaxations: Moments and Concentrated DP
The first major wave of tight accounting bypassed tracking $(\epsilon, \delta)$ directly by focusing on the moments of the privacy loss distribution.
In their seminal paper, Abadi et al. introduced the Moments Accountant. Instead of tracking the tail bounds of the privacy loss distribution at a single point, the Moments Accountant tracks the log-moments of the privacy loss optimization. Because these log-moments (related to Rényi divergence) compose linearly across iterations, the authors could compute a much tighter final $(\epsilon, \delta)$ bound after thousands of iterations of DP-SGD.
This mathematical machinery evolved into formal, generalized frameworks like Rényi Differential Privacy (RDP) and Zero-Concentrated Differential Privacy (zCDP). By bounding the moment-generating function of the privacy loss, zCDP provides a clean, linear accumulation of privacy costs. This framework has become the standard for analyzing complex, multi-step private algorithms, including:
- Variational Inference: Jälkö et al. utilized tight iterative accounting to make private Bayesian inference practical for non-conjugate models.
- Expectation Maximization: Park et al. combined moment perturbation with zCDP to drastically reduce the noise required for private clustering algorithms.
- Distributed Optimization: Frameworks like PP-ADMM, analyzed by Ding et al., leverage zCDP to track privacy depletion across decentralized networks without overestimating leakage.
Numerical Accounting: Tracking the Exact Distribution
While moment-based methods are vastly superior to basic composition, they still lose information by compressing an entire probability distribution into a few scalar moments. If we can track the exact shape of the Privacy Loss Distribution (PLD), we can get even tighter bounds.
Because the total privacy loss is the sum of independent random variables, the distribution of the total privacy loss is the convolution of the individual steps' PLDs. In the density domain, convolution is computationally expensive. However, by moving to the frequency domain via the Fast Fourier Transform (FFT), convolution turns into simple multiplication.
This is the core mechanism behind the Fourier Accountant, introduced by Koskela et al. and expanded in Koskela et al.. By discretizing the PLD and using the FFT to compute the exact convolution across thousands of steps, the authors achieved nearly exact privacy bounds.
[Step 1: PLD] --FFT--> [Characteristic Function 1] \
--> [Multiply] --IFFT--> [Exact Total PLD]
[Step 2: PLD] --FFT--> [Characteristic Function 2] /
This numerical approach preserves the fine-grained characteristics of the privacy loss. To prevent numerical errors from making the privacy guarantees unsafe, Doroshenko et al. developed "pessimistic" piecewise-linear approximations that guarantee the numerical accountant remains strictly conservative while running up to 300x faster.
The Finite-Sample Regime: Beyond Asymptotics
The Central Limit Theorem is an asymptotic guarantee—it works beautifully when an algorithm runs for thousands of steps. But what happens when we only run an algorithm for a few iterations, such as when fine-tuning a Large Language Model?
In these short-duration regimes, standard asymptotic assumptions fail, causing accountants to overestimate privacy loss. To fix this, researchers have introduced higher-order statistical corrections to refine the shape of the distribution:
- Edgeworth Expansions: Zheng et al. and Wang et al. proposed using Edgeworth expansions to incorporate skewness and kurtosis into the privacy loss distribution. This reduces the theoretical error from $O(n^{-1/2})$ to $O(n^{-3/2})$, providing ultra-tight bounds for low-iteration counts. Behnia et al. demonstrated that this "Edgeworth Accountant" allows practitioners to reclaim model utility during short LLM fine-tuning cycles by safely reducing added noise.
- Saddle-Point Approximations: Alghamdi et al. introduced the Saddle-Point Accountant, borrowing the method of steepest descent from mathematical physics. This method achieves relative errors below 0.1% compared to exact ground truth, but operates with constant computational complexity—completely decoupling the accountant's runtime from the number of training steps.
Expanding the Frontier
Precise privacy accounting has unlocked the ability to move beyond standard Gaussian noise and uniform data sampling. For instance, Jang et al. extended moment accounting to Logistic noise distributions to privatize sign-based gradient descent (signSGD), while Yang et al. optimized custom noise distributions by directly manipulating the privacy loss random variable.
Furthermore, accounting is no longer confined to static, worst-case offline calculations. In graph algorithms, Rongzhe Wei demonstrated that tracking privacy via infinity-Wasserstein distances between iterative steps yields significantly tighter bounds than global state-space analysis. In generative AI, Flemings et al. showed that privacy loss can be calculated dynamically during inference by numerically evaluating the divergence between full and leave-one-out ensembles in real time.
Ultimately, why does concentrated and numerical privacy accounting work? It works because it respects the true, probabilistic nature of privacy leakage. By replacing loose, pessimistic algebraic upper bounds with exact distributions and statistical expansions, we stop wasting our privacy budget on statistical flukes that will never happen.
Key Foundational Work
Deep Learning with Differential Privacy (2016) — contributed 2 concept elements to this direction.
Deep Learning with Differential Privacy (2016) — contributed 4 concept elements to this direction.
Differentially Private Dropout (2017) — contributed 2 concept elements to this direction.