📊 statistics

Edgeworth Accountant: An Analytical Approach to Differential Privacy Composition

This paper introduces the Edgeworth Accountant, an analytical method that leverages the Edgeworth expansion and $f$ -differential privacy to efficiently compute non-asymptotic, tight $(\epsilon, \delta)$ -differential privacy bounds for composed mechanisms with constant computational cost, making it particularly effective for deep learning and federated analytics.

Original authors: Hua Wang, Sheng Gao, Huanyu Zhang, Milan Shen, Weijie J. Su, Jiayuan Wu

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hua Wang, Sheng Gao, Huanyu Zhang, Milan Shen, Weijie J. Su, Jiayuan Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a secret club where you want to learn things about your members (like their favorite ice cream flavor) without ever revealing who said what. This is the world of Differential Privacy (DP). It's like a magic shield that adds a little bit of "static" or "noise" to the data so that if someone tries to peek, they can't tell if a specific person was in the group or not.

But here's the tricky part: You don't just ask one question. You ask thousands of questions over time, or you combine data from many different sources. Every time you ask a question, the "static" gets a little weaker, and the risk of someone figuring out a secret gets a little higher. This is called Composition.

The big question is: How much privacy have we lost after asking 1,000 questions?

The Problem with Old Tools

Before this paper, people had two main ways to answer this:

The "Rough Estimate" (Moments Accountant): This is like guessing how much money you've spent by looking at your bank balance and saying, "I think I'm under budget." It's fast, but it's often too scary. It tells you, "You might have spent $1,000!" when you actually only spent $100. It's too loose, so you end up being overly cautious and not learning enough from your data.
The "Exact Calculator" (FFT Method): This is like counting every single penny you spent. It's very accurate, but it's incredibly slow. If you have 1,000 transactions, it takes a long time to crunch the numbers. If you have a million transactions (like in modern AI training), this method crashes or takes forever. It's like trying to count grains of sand on a beach one by one.

The New Solution: The Edgeworth Accountant

The authors of this paper introduce a new tool called the Edgeworth Accountant. Think of it as a smart, high-speed GPS for privacy.

Here is how it works, using a simple analogy:

1. The "Privacy Loss" is a Sound Wave

Imagine every time you ask a question, it creates a tiny "ripple" of privacy loss. If you ask 1,000 questions, you have 1,000 ripples.

Old methods tried to add these ripples up by either guessing the total height (too loose) or measuring every single drop of water (too slow).
The Edgeworth Accountant looks at the shape of the ripples. It knows that when you add up many small, random ripples, they tend to form a specific, predictable wave pattern (a bell curve).

2. The "Edgeworth Expansion" is a Super-Refined Telescope

The standard way to predict these waves is the "Central Limit Theorem" (the basic bell curve). But that's like looking at the moon with the naked eye; it's okay, but blurry.
The Edgeworth Expansion is like putting a high-powered telescope on that view. It doesn't just see the moon; it sees the craters and the mountains. It corrects the "blur" of the basic math.

Why this matters: It allows the accountants to calculate the exact privacy loss with incredible precision, but it does it using a simple formula (like a calculator) rather than counting every grain of sand.

3. The Two Modes: The "Estimator" and the "Safety Net"

The paper offers two versions of this tool:

The Approximate Edgeworth Accountant (AEA): This is your Speedy Estimator. It gives you a very accurate answer almost instantly. It's perfect for when you are designing your experiment and need to know, "Is this safe?"
The Exact Edgeworth Accountant Interval (EEAI): This is your Safety Net. It doesn't just give you a number; it gives you a range (a "confidence interval"). It says, "The privacy loss is definitely between X and Y." This is crucial for legal and safety reasons, ensuring you never accidentally break the privacy rules.

Why is this a Big Deal?

Imagine you are training a super-smart AI to diagnose diseases. You need to ask it millions of questions about patient data.

Old Way: You either have to be so scared of privacy leaks that you stop the AI from learning anything useful, OR you wait weeks for a computer to calculate if it's safe.
New Way (Edgeworth): You can calculate the privacy cost in a split second. You get a tight, accurate number that tells you exactly how much privacy you have left. This means you can train better AI models faster, without accidentally exposing patient secrets.

The Bottom Line

The Edgeworth Accountant is a new, mathematical "super-tool" that lets data scientists track privacy loss with speed (like a calculator) and precision (like a microscope). It solves the age-old problem of "How do I use a lot of data without losing everyone's secrets?" by using advanced math to predict the future of privacy loss before it even happens.

It's the difference between guessing how far you can drive on a tank of gas, and having a dashboard that tells you exactly how many miles you have left, down to the inch, no matter how bumpy the road gets.

1. Problem Statement

In privacy-preserving data analysis (e.g., Deep Learning, Federated Analytics), algorithms are often constructed as compositions of multiple private building blocks. A critical challenge is privacy accounting: accurately computing the overall privacy loss (specifically the $(\epsilon, \delta)$ -differential privacy parameters) after $m$ compositions.

Existing methods face a trade-off between accuracy and computational efficiency:

Moments Accountant (Rényi DP): Computationally efficient ( $O(1)$ or $O(m)$ ) but provides loose, often impractical upper bounds because the conversion from Rényi DP to $(\epsilon, \delta)$ -DP is lossy.
FFT-based Numerical Methods: Provide tight, exact finite-sample bounds but suffer from high computational complexity (polynomial in $m$ , e.g., $O(m^{2.5})$ ) and numerical instability when $m$ is large (common in deep learning).
Gaussian DP (GDP) / CLT Approximation: Offers a closed-form solution but is only asymptotically accurate, lacking rigorous finite-sample guarantees.

The paper aims to develop a method that offers tight, finite-sample $(\epsilon, \delta)$ -DP bounds with linear or constant time complexity and high numerical stability.

2. Methodology

The proposed Edgeworth Accountant leverages the $f$ -Differential Privacy ( $f$ -DP) framework and the Edgeworth expansion to approximate the distribution of privacy loss.

Core Concepts

$f$ -DP Framework: The authors utilize $f$ -DP, which characterizes privacy via a trade-off function between Type I and Type II errors in a hypothesis testing framework. This allows for a "lossless" representation of privacy guarantees compared to $(\epsilon, \delta)$ -DP.
Privacy-Loss Log-Likelihood Ratios (PLLRs): The composition of mechanisms is modeled as the sum of independent random variables representing the log-likelihood ratios of the output distributions under neighboring datasets.
- Let $X_i$ and $Y_i$ be the PLLRs for the $i$ -th mechanism.
- The total privacy loss is determined by the cumulative distribution functions (CDFs) of the sums $S_X = \sum X_i$ and $S_Y = \sum Y_i$ .
Edgeworth Expansion: Instead of using the standard Central Limit Theorem (CLT) (which is the 0-th order approximation), the authors apply the Edgeworth expansion. This is a series expansion that refines the normal approximation by incorporating higher-order moments (cumulants), providing a faster convergence rate ( $O(m^{-(p+1)/2})$ for order $p$ ).

Two Variants

The paper introduces two specific tools:

Approximate Edgeworth Accountant (AEA):
- Uses the Edgeworth expansion to approximate the CDFs of PLLR sums.
- Provides a closed-form expression relating $\epsilon$ and $\delta$ .
- Computationally efficient ( $O(1)$ for identical mechanisms, $O(m)$ for heterogeneous).
- Asymptotically consistent and highly accurate for practical $m$ .
Exact Edgeworth Accountant Interval (EEAI):
- Derives rigorous finite-sample upper and lower bounds for the privacy loss.
- Uses a Berry–Esseen type bound adapted for the Edgeworth expansion to quantify the approximation error ( $\Delta_{m,k}$ ).
- Provides an interval $[\delta^-, \delta^+]$ (or $[\epsilon^-, \epsilon^+]$ ) that strictly contains the true privacy guarantee.

Handling Subsampling

For mechanisms involving subsampling (e.g., NoisySGD), the authors address the complexity of the trade-off function (which involves a double conjugate of an infimum). They utilize Lemma 3.3 to decompose the problem into analyzing multiple sequences of PLLRs corresponding to different components of the trade-off function, then taking the supremum of the resulting bounds.

3. Key Contributions

Novel Analytical Accountant: Introduction of the Edgeworth Accountant, which achieves constant time $O(1)$ for identical mechanisms and linear time $O(m)$ for general compositions, significantly outperforming FFT-based methods ( $O(m^{2.5})$ ).
Finite-Sample Guarantees: The first DP accountant to provide explicit, non-asymptotic error bounds using Edgeworth expansions. This bridges the gap between asymptotic approximations (like GDP) and exact numerical methods (like FFT).
Tightness and Accuracy: The method provides significantly tighter bounds than the Moments Accountant (Rényi DP) and more accurate estimates than the standard CLT/GDP approximation, especially for moderate to large $m$ .
Numerical Stability: Unlike FFT methods, which suffer from numerical instability and potential failure (e.g., negative $\epsilon$ bounds) when $m$ is large or mechanisms are heterogeneous, the Edgeworth Accountant remains analytically stable.
Generalizability: The framework is applicable to any noise-addition mechanism (Gaussian, Laplace, etc.) provided the PLLRs have bounded moments.

4. Results

The authors validate their approach through extensive numerical experiments:

Accuracy Comparison: In experiments involving the composition of 1,500 Gaussian mechanisms, the AEA estimates were nearly identical to the "Exact" ground truth (computed via FFT for small $m$ or theoretical limits), whereas the Moments Accountant (RDP) and standard GDP provided loose or inaccurate bounds.
Large-Scale Stability: In scenarios with $m$ up to $10^6$ (simulating deep learning training), the FFT method failed to produce valid results (yielding negative $\epsilon$ bounds due to numerical errors). In contrast, the EEAI provided stable, tight, and valid bounds.
Federated Learning: The method successfully handled complex subsampled Gaussian mechanisms typical in Federated Analytics, offering precise privacy tracking for 10 epochs of training where $m$ is large.

5. Significance

The Edgeworth Accountant represents a major advancement in the toolkit for Differential Privacy:

Practical Impact: It enables the rigorous privacy accounting of large-scale deep learning and federated learning models, where the number of composition steps is often in the millions. Previous methods were either too slow (FFT) or too loose (Moments) to be useful in these settings.
Theoretical Contribution: It establishes the first finite-sample error bounds for Edgeworth expansions in the context of DP, a result of independent mathematical interest.
Efficiency: By reducing the complexity to linear or constant time, it allows practitioners to rapidly evaluate privacy budgets during hyperparameter tuning, a task that was previously computationally prohibitive with exact methods.

In summary, the Edgeworth Accountant offers the "best of both worlds": the computational efficiency of analytical methods and the accuracy and rigor of numerical methods, making it the state-of-the-art solution for privacy accounting in modern machine learning applications.