💻 computer science

$f$ -Differential Privacy Filters: Validity and Approximate Solutions

This paper demonstrates that the natural $f$ -differential privacy filter for fully adaptive composition is fundamentally invalid, establishes the necessary conditions for its validity, and proposes a fully adaptive central limit theorem to construct a closed-form approximate Gaussian filter that outperforms existing RDP-based methods in asymptotic regimes.

Original authors: Long Tran, Antti Koskela, Ossi Räisä, Antti Honkela

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Long Tran, Antti Koskela, Ossi Räisä, Antti Honkela

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 highly sensitive game where players share secret information. Your goal is to let them play as much as possible without anyone being able to figure out who any specific player is. To do this, you have a "Privacy Budget"—a limited amount of "leakage" you can afford before the game must stop to protect everyone.

In the world of Differential Privacy (DP), this is a mathematical way to ensure that even if someone sees the results of your game, they can't tell if a specific person was playing or not.

This paper tackles a specific, tricky problem: What happens when the game changes its rules based on what has already happened?

The Problem: The "Adaptive" Trap

Usually, you might plan your privacy budget in advance. But in modern machine learning (like training AI), the algorithm often decides its next move based on the results of the previous move. This is called fully adaptive composition.

The researchers looked at a popular, sophisticated method for tracking privacy called f-DP (which uses complex curves to measure privacy). They asked: "Can we just keep adding up these privacy curves as the game goes on, and stop the moment we hit our budget limit?"

The Big Discovery: The answer is NO.

The authors proved that this "natural" way of tracking privacy is fundamentally broken when the rules change based on history. It's like trying to navigate a maze by drawing a straight line on a map, only to realize the walls move depending on where you've been. If you just follow the map, you might think you're safe, but you could actually be walking right into a trap.

The Analogy: Imagine you are walking through a forest with a compass that tells you how far you are from the edge.

The Old Way (Non-Adaptive): You plan a straight path. You know exactly how far you can go.
The New Way (Adaptive): Every time you take a step, the forest rearranges itself based on your previous steps.
The Failure: The paper shows that if you just add up your "distance from the edge" calculations as you go, you might think you are still inside the forest, but the forest has actually shifted, and you are already outside. The math you used to track your safety no longer guarantees you are safe.

The Solution: When Does It Work?

The researchers didn't just say "it doesn't work"; they figured out exactly when it does work.

They found that the "natural" tracking method is only safe if the possible future paths of the game are strictly ordered.

The Metaphor: Imagine the game offers you a choice of paths. If every possible path is just a "worse" or "better" version of the others (like a ladder where every rung is clearly above or below the last), then your tracking works.
The Failure: If the paths cross each other (like a tangled knot where one path is better in one spot but worse in another), the tracking breaks. The paper proves that for many common AI tools (like subsampled Gaussian mechanisms), these paths do cross, making the standard tracking method invalid.

The New Approach: The "Central Limit Theorem" Filter

Since the perfect tracking method is broken, the authors proposed a new, approximate way to track privacy that works very well in specific situations.

They used a concept from statistics called the Central Limit Theorem (CLT).

The Analogy: Imagine you are rolling a die many times. Individually, the rolls are random and unpredictable. But if you roll it thousands of times, the average result becomes very predictable and forms a perfect bell curve.
The Application: The authors showed that even though the privacy loss in an adaptive game is chaotic step-by-step, if you look at the total loss after many steps, it settles down into a predictable "bell curve" (a Gaussian distribution).

Using this, they built a new Privacy Filter for a specific type of AI tool (Subsampled Gaussian mechanisms).

How it works: Instead of tracking the complex, tangled curves of the old method, this new filter just tracks the "average" and "spread" of the privacy loss.
The Benefit: In extreme scenarios (where the AI samples data very rarely or very frequently), this new filter is tighter (more accurate) than the current best methods. It allows the game to go longer without breaking privacy rules, whereas the old methods were being overly cautious and stopping the game too early.

Summary of Claims

The "Natural" Filter is Broken: You cannot simply add up privacy curves in an adaptive setting and stop when you hit a limit. It gives a false sense of security.
The Condition for Safety: This method only works if the possible future outcomes are strictly ordered (like a ladder), which is rarely the case in real-world adaptive algorithms.
The New Approximate Filter: By using the "bell curve" behavior of large numbers (Central Limit Theorem), they created a new filter for specific AI tools.
Better Performance: In extreme cases (very low or very high sampling rates), this new filter provides a more precise privacy guarantee than the current standard, allowing for more useful data analysis without compromising safety.

Note: The paper explicitly states that while this new filter is better in extreme cases, it can still be slightly "optimistic" (underestimating risk) at moderate sampling rates, which remains a challenge. It does not claim to solve all privacy problems for all types of AI, only to fix a specific flaw in how we track privacy for certain adaptive mechanisms.

Technical Summary: f-Differential Privacy Filters: Validity and Approximate Solutions

Problem Statement

The paper addresses the challenge of accounting for privacy loss under fully adaptive composition in differential privacy (DP). In fully adaptive settings, the choice of mechanisms and their privacy parameters may depend on the history of prior outputs, a scenario common in iterative algorithms like differentially private stochastic gradient descent (DP-SGD).

While privacy filters (stopping rules) exist for $(\epsilon, \delta)$ -DP and Rényi DP (RDP), the validity of filters based on f-Differential Privacy (f-DP) remains unclear. f-DP characterizes the full extent of adversarial hypothesis testing via trade-off functions and recovers $(\epsilon, \delta)$ -DP through piece-wise linear trade-off functions. It is known that f-DP tensor products provide the tightest composition results for non-adaptive settings. The central question is whether a "natural" f-DP filter—tracking the accumulating tensor product of trade-off functions and stopping when a prescribed curve is crossed—remains valid under full adaptivity.

Methodology and Theoretical Framework

1. Analysis of Natural f-DP Filter Validity

The authors investigate the "natural" f-DP filter, defined as continuing as long as the tensor product of realized trade-off functions $f_1 \otimes \dots \otimes f_t$ remains above a budget curve $f_B$ .

Counterexample Construction: The paper demonstrates that this approach is fundamentally invalid in the fully adaptive setting. Even if individual mechanisms are valid and the composed trade-off function never exceeds the threshold along a specific history, the adaptive composition can violate the budget.
Mechanism of Failure: The failure arises because the adaptive product of trade-off functions depends on the specific realization of outputs, which determines the selection of subsequent mechanisms. If a family of potential future trade-off functions contains a "calibration point" (where functions intersect), the adaptive selection can exploit this to achieve a privacy loss profile that is strictly worse (lower trade-off function) than the lower bound of the tensor product of the individual branches. This phenomenon occurs even for subsampled Gaussian mechanisms, the workhorse of private machine learning.

2. Characterization of Validity Conditions

The authors establish necessary and sufficient conditions for the natural f-DP filter to be valid:

Blackwell Chains: The filter is valid if and only if the family of available trade-off functions (and their tensor products) forms a Blackwell chain. A family is a Blackwell chain if any two functions in the family are totally ordered (one dominates the other point-wise).
Implication: This explains why RDP and Gaussian DP (GDP) admit simple, valid filters: their guarantees are scalar-valued (or form Blackwell chains like Gaussian trade-off functions $G_\mu$ where $\mu$ is a scalar), ensuring comparability. In contrast, general f-DP trade-off functions are not always Blackwell ordered, leading to the failure of the natural filter.

3. Fully Adaptive Central Limit Theorem (CLT)

To circumvent the invalidity of exact f-DP filters, the paper proves a fully adaptive f-DP Central Limit Theorem.

Approach: The authors model the privacy loss as a stochastic process of Privacy Loss Random Variables (PLRVs). Using a martingale variant of the Berry–Esseen bound (Fan, 2019), they prove that under specific regularity conditions (bounded conditional means and variances, and controlled higher-order moments), the cumulative privacy loss converges to a Gaussian distribution.
Result: This convergence allows for the construction of approximate GDP filters. Instead of tracking the full trade-off function, one can track the cumulative conditional means and variances of the PLRVs. The error of this approximation is quantified by the CLT error term $\Delta$ .

4. Approximate GDP Filter for Subsampled Gaussian Mechanisms

As a concrete instantiation, the authors derive closed-form moment approximations for subsampled Gaussian mechanisms in two asymptotic regimes:

Low subsampling ( $q \ll 1$ ): The PLRV mean and variance are approximated using Taylor expansions.
High subsampling ( $q \approx 1$ ): Similar approximations are derived for the limit where the sampling rate approaches 1.
Algorithm: They propose an algorithm that tracks these moment approximations to enforce a budget. This filter avoids tracking the full trade-off function, offering a computationally efficient alternative to numerical FFT-based accounting.

Key Results

Invalidity of Natural Filters: The natural f-DP filter is invalid for fully adaptive compositions of subsampled Gaussian mechanisms. Explicit counterexamples show that the adaptive composition can violate the budget even when all non-adaptive branches satisfy it.
Validity Characterization: The natural filter is valid if and only if the family of trade-off functions forms a Blackwell chain. This provides a sharp theoretical boundary for when trade-off-function-based accounting is possible under full adaptivity.
CLT-Based Approximation: The fully adaptive CLT establishes that cumulative privacy losses converge to Gaussian distributions. This enables the construction of approximate GDP filters that are provably valid in asymptotic regimes.
Performance Comparison:
- In asymptotic regimes ( $q \ll 1$ and $q \approx 1$ ), the proposed approximate GDP filter yields strictly tighter privacy guarantees than fully adaptive RDP accounting (specifically the single-order $(1, B)$ -RDP filter).
- The paper notes that while RDP-based accounting is known to be loose, this slack is shown to stem from the lossy reduction to Rényi divergences rather than a fundamental barrier in adaptive composition.
- However, the CLT-based approximation is known to be optimistic (underestimating privacy loss) at realistic, moderate subsampling rates (e.g., $q=0.1$ ), a limitation shared with non-adaptive CLT approximations.

Significance and Claims

The paper claims to resolve a central open question regarding f-DP filters:

Theoretical Resolution: It definitively shows that the intuitive extension of standard f-DP composition to adaptive filters fails, clarifying why divergence-based notions (RDP) succeed where trade-off-function-based notions (general f-DP) fail without structural constraints.
Constructive Contribution: By proving the fully adaptive CLT, the paper provides a general methodology for constructing approximate GDP filters for any mechanism family where PLRV moments can be approximated analytically.
Practical Implication: For subsampled Gaussian mechanisms, the proposed filter offers a closed-form, efficient alternative to numerical accounting. In extreme subsampling regimes, it provides guarantees that are strictly tighter than the current state-of-the-art RDP-based filters, demonstrating that the "slack" in RDP is an artifact of the representation, not an inherent cost of adaptivity.

The authors remain modest regarding the limitations, acknowledging that the CLT-based approach is optimistic at realistic subsampling rates and that closing the gap at moderate rates remains an open challenge. They also note that the validity of the natural filter is restricted to specific structural conditions (Blackwell chains) that are not generally met by arbitrary f-DP mechanisms.