f-Differential Privacy Filters: Validity and Approximate Solutions
summary
The gist
Accounting for privacy loss under fully adaptive composition—where mechanism choice and privacy parameters may depend on the history of prior outputs—is a central challenge in differential…
In short
The paper investigates privacy filters for fully adaptive differential privacy, focusing on f-DP. It shows that the natural filter tracking trade-off functions fails under full adaptivity, blocking efficient numerical accounting. However, it establishes conditions for validity and proves a central limit theorem showing cumulative losses converge to Gaussian distributions. This leads to constructing approximate filters that outperform Rényi DP accounting.
Key concepts
- f-DP
- f-Differential Privacy characterizes the full extent of adversarial hypothesis testing in privacy analysis. It is a stronger notion than standard $(\epsilon, \delta)$-DP and helps define the complete set of privacy bounds achievable under adaptive mechanisms.
- Natural f-DP Filter Failure
- The intuitive filter that tracks path-wise accumulating tensor products fails in fully adaptive settings. This means simply stopping when a prescribed curve is crossed does not guarantee the resulting privacy loss satisfies the f-DP bound, even if individual steps are valid.
- Fully Adaptive CLT
- This theorem proves that cumulative privacy losses under full adaptivity converge to a Gaussian distribution. This convergence provides a general method for building approximate GDP filters by using mechanism-specific moment approximations.
- Blackwell Chain Condition
- A structural condition where the family of trade-off functions forms a Blackwell chain determines if the natural f-DP filter is valid. If this condition fails, it proves the filter is invalid, characterizing when such accounting methods are possible.
Terminology used across episodes
This episode discusses
- f-Differential Privacy Filters: Validity and Approximate Solutions · Paper Radio
- Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learning
- Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity · Paper Radio
The paper
f-Differential Privacy Filters: Validity and Approximate Solutions · Read on arXiv
Department of Computer Science, University of Helsinki · Nokia Bell Labs · CISPA Helmholtz Center for Information Security
Accounting for privacy loss under fully adaptive composition---where mechanism choice and privacy parameters may depend on the history of prior outputs---is a central challenge in differential privacy (DP). Here, privacy filters are stopping rules ensuring a prescribed global budget is not exceeded. A leading candidate for optimal filter design is f-DP, which characterizes the full extent of adversarial hypothesis testing and recovers (epsilon,δ) -DP through piece-wise linear trade-off functions, while enabling tight (epsilon,δ) -DP accounting in standard compositions via tensor products. Yet whether such filters can be correctly defined under f-DP remains unclear. We show that the natural f-DP filter---tracking path-wise accumulating tensor products and stopping when the prescribed curve is crossed---is fundamentally invalid, precluding the direct use of standard efficient numerical Fast-Fourier-Transform accounting in the fully adaptive setting. We characterize this failure, establishing necessary and sufficient conditions for the natural filter's validity. Furthermore, we prove a fully adaptive central limit theorem for f-DP, establishing Gaussian convergence of cumulative privacy losses under full adaptivity. As a demonstration, we construct a closed-form approximate GDP filter for subsampled Gaussian mechanisms that provably outperforms RDP-based accounting in asymptotic regimes (q much less than 1 and q about 1) without tracking the full trade-off function, demonstrating that the slack in RDP is not intrinsic to adaptive composition---though CLT-based approximations are known to be optimistic at realistic subsampling rates, a limitation that remains an open challenge.
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: I'm Nadia.
Elias: And I'm Elias, here with Priya.
Nadia: We're looking at the paper: "f-Differential Privacy Filters".
Elias: Here's the gist of the paper. Accounting for privacy loss under fully adaptive composition—where mechanism choice and privacy parameters may depend on the history of prior outputs—is a central challenge in differential privacy (DP) Here, privacy filters are stopping rules ensuring a prescribed global budget is not exceeded A leading candidate for optimal filter design is f-DP, which characterizes the full extent of adversarial hypothesis testing and recovers (ε, δ)-DP through piece-wise linear trade-off functions, while enabling tight (ε, δ)-DP accounting in standard compositions via tensor products Yet whether such filters can be correctly defined under f-DP remains unclear We show that the natural f-DP filter—tracking path-wise accumulating tensor products and stopping when the prescribed curve is crossed—is fundamentally invalid, precluding the direct use of standard efficient numerical Fast-Fourier-Transform (FFT) accounting in the fully adaptive setting.
Nadia: Failure of Natural Filters The natural f-DP filter fails because composing trade-off functions and stopping at a threshold does not generally guarantee that the resulting stopped interaction satisfies the same f-DP bound.
Elias: This failure occurs even when each individual mechanism is validly f-DP and even when the composed trade-off function never exceeds the threshold along the realized history of outcomes.
Nadia: This phenomenon occurs for fully adaptive compositions of subsampled Gaussian mechanisms, which are the main workhorse of private machine learning.
Title and authors: Nadia: So we're diving into this paper now called "f-Differential Privacy Filters: Validity and Approximate Solutions". It’s about this really tricky problem in differential privacy where the mechanism you choose and your privacy settings can actually change based on what you’ve seen before, which is called fully adaptive composition.
Elias: Exactly. The authors are looking at how we can have these stopping rules that keep us under a global budget without breaking the privacy guarantee when things adapt over time. They introduce this concept called f-DP, which they say describes the whole picture of adversarial testing and allows you to get tight epsilon delta differential privacy through piece-wise linear trade-off functions while still letting you handle standard compositions with tensor products.
Priya: So it sounds like they're trying to figure out if these f-DP filters actually work when we make choices based on history, because that seems like the main sticking point in making these things practical for real systems.
Nadia: Right, and what they show is that the natural way of doing this—tracking the accumulating tensor products of those trade-off functions and stopping when you hit a certain curve—is actually fundamentally invalid under fully adaptive composition. That means if you just do that, it doesn't guarantee you’re staying within the f-DP bound, even if every single mechanism is individually valid and your composed function never crosses that threshold along the history of outcomes.
Elias: That failure happens even when each individual mechanism is validly f-DP and the composed trade-off function never exceeds the threshold along the realized history of outcomes. They give explicit negative examples to show why this approach doesn't work in general, which rules out using standard efficient numerical fast Fourier transform accounting in this fully adaptive setting for getting accurate epsilon delta bounds.
Priya: So that’s a big hurdle because we rely on those efficient methods for computation, and if the natural filter isn't valid, it means our go-to way of tracking privacy loss is broken in the most complex scenarios.
Nadia: It opens up some new avenues then. The paper points out that while the natural f-DP filter fails generally, it actually becomes valid under specific structural conditions on those trade-off functions. They establish necessary and sufficient conditions for when stopping based on composed trade-off curves yields a correct f-DP guarantee, and they also prove a fully adaptive f-DP central limit theorem.
Elias: That central limit theorem is significant because it suggests that cumulative privacy losses actually converge to Gaussian distributions under full adaptivity, which points toward a general methodology for building approximate GDP filters by using mechanism specific piece wise linear trade off function moment approximations. This implies you might not need the exact function anymore if you can use these approximations.
Title and authors: Priya: If the losses converge to a Gaussian distribution, that gives us a statistical way to bound what happens, which is helpful because it moves us away from needing the perfect tracking of every single interaction history. But what about those approximate solutions?
Nadia: The paper constructs a closed form approximate GDP filter specifically for subsampled gaussian mechanisms that they prove provably outperforms Rényi DP based accounting in asymptotic regimes when the sampling rate q is less than one or when q is approximately equal to one, and it does this without needing to track the full trade-off function.
Elias: That’s a strong claim because it shows that the slack you see in rényi dp isn't just about the adaptive composition itself, which is what we thought before. But you have to be careful with that, because they admit that the error in these central limit theorem based approximations depends on how good those piece wise linear trade off function moment approximations are.
Priya: So it sounds like for practical applications, especially with subsampled gaussian mechanisms—which are pretty common in private machine learning—we can get a filter that is better than standard rényi dp accounting without having to track the entire history of trade-off functions. But they admit that the approximation quality depends on those moment approximations.
Nadia: Exactly. They also characterize when the natural f-DP filter actually works by checking if the family F of trade off functions is a Blackwell chain, which is a structural assumption that ensures the greatest lower bound of the options satisfies necessary conditions for validity, generalizing some older results from rdp and gdp accounting.
Elias: That Blackwell chain condition acts as a test for when you can use this type of trade-off function based accounting under full adaptivity, giving us a concrete way to check if the filter you’re using is theoretically sound or not. It's a condition on the family of functions themselves.
Priya: So we have the general theory showing why the natural method fails, and then we have specific conditions under which it works, plus statistical tools that suggest how to build approximations when the exact tracking is too much work. It’s a lot of machinery to digest at once.
Nadia: It's heavy machinery because it ties together analysis of adversarial testing, the structure of trade-off functions, and then uses a central limit theorem to justify an approximate solution for practical use cases like subsampled gaussian mechanisms. The implication is that we have a path forward for building filters in fully adaptive settings.
Elias: And they show Monte Carlo simulations back up these asymptotic guarantees, confirming the empirical privacy loss distribution matches the theoretical Gaussian approximation predicted by theorem four point two, and they found that the filter halts with high probability after an average of eleven to twelve active epochs, which backs up using that Gaussian approximation of the privacy loss distribution.
Title and authors: Priya: That empirical validation is important because it shows that in practice, after a certain number of steps—about eleven or twelve epochs—the system actually stops as predicted by their theoretical model, which gives us confidence in using the Gaussian approximation for bounding our privacy loss.
Nadia: And honestly, they confirm that rényi dp accounting is highly suboptimal compared to their proposed filter in all settings, even when comparing it to the more complex f-DP framework. The paper "f-Differential Privacy Filters: Validity and Approximate Solutions" shows us that while the simple natural filter fails, there are solid ways to construct approximate solutions when we rely on those statistical convergence properties.
Elias: It’s a big statement because it moves us away from needing to track the full trade-off function for every interaction. The focus shifts toward these approximate filters built from Gaussian structure and moment approximations, which is a more computationally feasible route for many applications.
Priya: For someone just listening, it means that if you're using private machine learning on data that's been sampled down—like subsampled gaussian mechanisms—you might be able to use a filter that gives you tighter bounds than what standard rényi dp accounting provides, even without tracking the entire history of all the trade-off curves.
Nadia: Exactly. We’re not just getting a theoretical result here; they are giving us a concrete construction and proving its performance against another standard method in specific regimes, which is really useful for anyone building these kinds of systems in practice.
Elias: So we have the failure of the natural filter, the conditions for validity based on Blackwell chains, and then the CLT that suggests Gaussian convergence to build approximate filters via moment approximations. It’s a comprehensive look at what’s possible under fully adaptive composition.
Priya: I just want to say that while these results are powerful for building approximate filters, they do have limitations—specifically, the authors admit that the error in those central limit theorem based approximations depends on how good those piece wise linear trade off function moment approximations are. That’s a caveat we have to keep in mind when relying on those statistical bounds.
Nadia: True. It’s not a perfect solution, it’s an approximate one, and that approximation quality is tied directly to the underlying moment approximations they use for the subsampled gaussian mechanisms. That's where the real work for implementation lies.
Elias: So when we look at this paper, we see a clear progression from identifying why a simple approach fails to developing sophisticated statistical tools—the central limit theorem—to then constructing a practical, closed form approximate filter that beats rényi accounting in certain limits.
Priya: It's about moving from needing the perfect tracking of every single interaction history to using statistical convergence properties, like the Gaussian distribution they prove, to build something usable. That’s what this paper is really trying to achieve with "f-Differential Privacy Filters: Validity and Approximate Solutions".
The paper's summary: Nadia: So we're looking at this paper "f-Differential Privacy Filters: Validity and Approximate Solutions". It really boils down to a problem in fully adaptive differential privacy where you can change your privacy settings based on what you've seen before.
Elias: Exactly, it tackles the challenge of having stopping rules for a global budget that work even when the mechanism choices are history-dependent. They introduce this f-DP framework, which they say gives a complete picture of how adversarial testing works.
Priya: So what they find is that the standard way we try to track this privacy loss—that natural filter tracking those accumulated tensor products—it’s actually fundamentally invalid in the fully adaptive setting.
Nadia: That means even if every single mechanism you pick is individually safe, and you never cross that threshold during your history of outcomes, the composed filter might not actually guarantee the f-DP bound.
Elias: They show this failure happens even when each individual mechanism is already validly f-DP and the composed trade-off function never exceeds that boundary along the history of outcomes.
Priya: So that invalidity rules out using standard, efficient numerical methods for fast Fourier transform accounting when things are fully adaptive.
Nadia: That’s a big deal because those efficient methods are how we usually try to get accurate epsilon delta bounds in practice.
Elias: But the paper doesn't stop there, though. They find specific structural conditions on those trade-off functions under which that natural filter actually works correctly.
Priya: And they also prove a fully adaptive f-DP central limit theorem, which suggests that cumulative privacy losses actually behave like a Gaussian distribution when you have full adaptivity.
Nadia: That statistical convergence is interesting because it points toward a general way to build approximate filters by using those piece wise linear trade off function moment approximations.
Elias: They build a closed form approximate GDP filter for subsampled gaussian mechanisms, and they prove that this construction provably beats Rényi DP based accounting in specific asymptotic regimes.
Priya: So for practical applications with things like subsampled gaussian mechanisms, you can get tighter privacy guarantees than what standard rényi DP gives you without tracking the entire history of trade-off functions.
Nadia: But they have to be careful because the error in those central limit theorem based approximations depends on how accurate those piece wise linear trade off function moment approximations are.
Elias: They also characterize when that natural filter is valid by checking if the family of trade off functions behaves like a Blackwell chain, which gives us a test for whether this type of accounting is even possible under full adaptivity.
Priya: So they’re giving us a tool to check validity based on the structure of the functions themselves, rather than just running simulations on every possible history.
Nadia: It’s like they’ve given us a mathematical way to decide if we should trust a certain type of privacy filter under complex, adaptive scenarios.
Elias: And they do validate these asymptotic results with Monte Carlo simulations, showing that the empirical loss distribution matches the theoretical Gaussian approximation predicted by their theorem.
Priya: The simulations also show the filter halts after about eleven to twelve active epochs in most experiments, which backs up using that Gaussian approximation of privacy loss distribution.
Nadia: It’s a lot of machinery put together, tying adversarial testing structure to statistical convergence, and it points toward a more robust way to handle adaptive privacy spending.
The paper's improvements: Tom: So we're looking at how the authors suggest ways to improve these f-DP filters they discussed earlier. It’s about moving from just theoretical ideas to actually building something that works better in the real world.
Nadia: They focus on constructing those approximate Gaussian DP filters for subsampled gaussian mechanisms, which they claim provably outperform Rényi DP accounting when the sampling rate q is less than one or close to one.
Elias: That’s a big claim because it suggests you can get tighter privacy bounds without needing to track the entire history of every single trade-off curve.
Priya: So they rely on closed form piece wise linear trade off function moment approximations for subsampled gaussian mechanisms to build these filters.
Nadia: But they also mention that this construction only works if those moment approximations are actually pretty good, which is a key caveat we need to watch out for when implementing it.
Elias: They also highlight using Algorithm three, which lets you manage privacy spending by choosing per datapoint budgets for each individual, dynamically adjusting clipping thresholds based on the history of what you've seen.
Priya: That sounds like a way to make the clipping more granular and responsive to the actual data stream rather than just a fixed global budget.
Nadia: It builds on earlier work from Feldman and Zrnic, but they’re extending that individual accounting to cover both asymptotic regimes now.
Elias: And they also give us this methodology for building approximate GDP filters based on mechanism specific piece wise linear trade off function moment approximations, using the central limit theorem we discussed.
Priya: That convergence to a Gaussian distribution under full adaptivity gives us a statistical tool to construct these filters even when the exact tracking is too much work.
Nadia: The paper also shows that you can check if that natural filter is valid by looking at whether the family of trade off functions forms a Blackwell chain, which tells you if you can use this kind of accounting under full adaptivity.
Elias: So the improvements focus on giving us specific construction methods and structural tests to determine when these complex adaptive filters are actually mathematically sound.
Priya: It’s a shift from just saying the natural way fails, to giving us a statistical framework and concrete constructions for what *can* work under certain conditions.
Nadia: It’s about moving from needing perfect tracking to using statistical convergence properties and structural assumptions to build something usable in practice.
Conclusion: Nadia: So to wrap up "f-Differential Privacy Filters: Validity and Approximate Solutions", we've seen that the natural filter approach for adaptive privacy is generally not valid under fully adaptive composition.
Elias: Right, and we established that while it fails in general, there are specific conditions on those trade off functions where stopping based on the composed curve actually yields a correct f-DP guarantee.
Priya: And they gave us a way to approximate these filters using a Gaussian convergence theorem, which suggests cumulative privacy losses behave like Gaussian distributions under full adaptivity.
Nadia: So it means we can construct approximate filters for subsampled gaussian mechanisms that provably beat Rényi DP accounting in certain settings, even without tracking the entire history of every interaction.
Elias: That approximation depends on how well those piece wise linear trade off function moment approximations are, which is a caveat we have to remember when implementing it.
Priya: It’s about using that statistical convergence to build something usable when exact tracking would otherwise be computationally impossible or too much work.
Nadia: The paper also gives us a structural check—the Blackwell chain condition—to determine if the natural filter is valid in the first place.
Elias: So they've given us both a failure case and a set of conditions under which we can trust specific filtering methods for adaptive privacy spending.
Priya: It changes how we think about what privacy loss actually looks like when mechanisms are being chosen adaptively over time.
Nadia: Exactly. We’re moving toward using these statistical properties to build filters that are better than the standard accounting methods in certain regimes.
Elias: So, the implication is that for many adaptive scenarios, we can rely on these approximate solutions instead of needing perfect tracking of every possible history.
More episodes
- 2608.27496-ROPE: Routed Origin Policy Enforcement against Indirect Prompt Injection
- Daily Summary for 2026-11-19
- 2607.07085-Is Randomness Necessary for Adaptive Data Analysis?
- The day in conversation for 2026-11-19
- Daily Summary for 2026-11-19
- 2609.10601-Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows
- 2610.38786-Adversarial Process Disturbances at a Deployable Alarm Budget: Detector Evaluation on a Simulator and a Real Plant
- 2511.08660-Binary and Multiclass Cyberattack Classification on GeNIS Dataset
- 2604.27302-Static Attribution of Android Residential Proxy Malware Using Graph Kernels
- Daily Summary for 2026-11-18