f-Differential Privacy Filters: Validity and Approximate Solutions
Pith reviewed 2026-05-16 06:54 UTC · model grok-4.3
The pith
Natural f-DP privacy filters are invalid under full adaptivity
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The natural path-wise f-DP filter that tracks accumulating tensor products of trade-off functions and halts upon crossing a prescribed curve is fundamentally invalid for fully adaptive composition. Necessary and sufficient conditions for validity are given, a fully adaptive central limit theorem establishes Gaussian convergence of cumulative privacy losses, and a closed-form approximate GDP filter for subsampled Gaussians is shown to outperform RDP accounting without maintaining the full trade-off function.
What carries the argument
f-DP trade-off functions whose tensor products accumulate privacy loss under adaptive composition
If this is right
- The natural f-DP filter remains valid only under additional restrictions on the sequence of mechanisms and their adaptivity.
- Cumulative privacy losses converge in distribution to a Gaussian under full adaptivity for sequences obeying the stated conditions.
- The approximate GDP filter yields closed-form accounting that is asymptotically tighter than RDP for subsampled Gaussians when q is either very small or close to 1.
Where Pith is reading between the lines
- Practical implementations of adaptive DP accounting will likely need to adopt approximate methods rather than attempt exact f-DP tracking.
- Validity checks similar to those derived here may be required for other composition methods that were originally analyzed only in non-adaptive settings.
- The gap between asymptotic CLT performance and finite-sample behavior at typical subsampling rates remains an open practical limitation.
Load-bearing premise
The mechanisms and adaptivity satisfy the regularity conditions needed for the fully adaptive central limit theorem to produce Gaussian convergence.
What would settle it
Run an adaptive sequence of subsampled Gaussian mechanisms, apply the natural f-DP stopping rule, and observe whether the realized privacy loss ever exceeds the target trade-off curve.
Figures
read the original abstract
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 $(\varepsilon,\delta)$-DP through piece-wise linear trade-off functions, while enabling tight $(\varepsilon,\delta)$-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\ll 1$ and $q\approx 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that the natural f-DP filter—tracking path-wise accumulating tensor products of trade-off functions and stopping when a prescribed curve is crossed—is fundamentally invalid under full adaptivity. It characterizes this failure by establishing necessary and sufficient conditions for validity of such filters, proves a fully adaptive central limit theorem establishing Gaussian convergence of cumulative privacy losses under arbitrary history-dependent mechanism choice and stopping, and constructs a closed-form approximate GDP filter for subsampled Gaussian mechanisms that provably outperforms RDP-based accounting in the asymptotic regimes q ≪ 1 and q ≈ 1.
Significance. If the results hold, the work is significant for differential privacy accounting: it identifies a previously unrecognized obstruction to direct use of f-DP tensor-product filters in the adaptive setting, supplies a rigorous CLT that justifies efficient Gaussian approximations without RDP slack, and demonstrates concrete improvement for subsampled Gaussians. The explicit separation of adaptivity-induced slack from RDP conservatism is a useful conceptual clarification.
major comments (1)
- [Fully adaptive CLT] The fully adaptive CLT (whose statement appears after the validity characterization): the proof does not supply explicit regularity conditions (adapted Lindeberg or Lyapunov moment bounds on the sequence of trade-off functions, uniform integrability of the stopped martingale, or restrictions on the filtration generated by prior outputs). Without these, it is impossible to confirm applicability to the subsampled Gaussian mechanisms at the q ≪ 1 and q ≈ 1 regimes used for the closed-form filter construction.
minor comments (1)
- [Abstract] The abstract notes that CLT approximations are known to be optimistic at realistic subsampling rates but does not quantify the resulting gap between the proposed filter and exact f-DP accounting for typical q values.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive feedback on our manuscript. We address the major comment below.
read point-by-point responses
-
Referee: [Fully adaptive CLT] The fully adaptive CLT (whose statement appears after the validity characterization): the proof does not supply explicit regularity conditions (adapted Lindeberg or Lyapunov moment bounds on the sequence of trade-off functions, uniform integrability of the stopped martingale, or restrictions on the filtration generated by prior outputs). Without these, it is impossible to confirm applicability to the subsampled Gaussian mechanisms at the q ≪ 1 and q ≈ 1 regimes used for the closed-form filter construction.
Authors: We agree that explicit regularity conditions are required for a fully rigorous statement. In the revised manuscript we will add a dedicated subsection stating the adapted Lindeberg condition on the sequence of trade-off functions together with uniform integrability of the stopped martingale and the necessary restrictions on the history-dependent filtration. We will then verify that these conditions are satisfied by the subsampled Gaussian mechanisms in the regimes q ≪ 1 and q ≈ 1, thereby confirming applicability of the CLT to the closed-form GDP filter. revision: yes
Circularity Check
No significant circularity in derivation chain
full rationale
The paper proves the natural f-DP filter is invalid under full adaptivity, derives necessary and sufficient validity conditions, establishes a new fully adaptive CLT for cumulative privacy losses, and constructs a closed-form approximate GDP filter for subsampled Gaussians. These results are presented as independent mathematical contributions without any reduction to self-definitional inputs, fitted parameters renamed as predictions, or load-bearing self-citations. The CLT is introduced as a convergence theorem rather than a restatement of prior quantities, and no equations or steps in the abstract or described chain collapse by construction to the paper's own assumptions or outputs.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math f-DP trade-off functions compose via tensor products under adaptive mechanisms
- domain assumption Convergence to Gaussian privacy loss under repeated adaptive composition
Reference graph
Works this paper leans on
-
[1]
10 Contents 1 Introduction 1 2 Preliminaries 2 2.1 Differential Privacy
PMLR, 2022. 10 Contents 1 Introduction 1 2 Preliminaries 2 2.1 Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Subsampled Gaussian Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Fully Adaptive Composition . . . . . . . . . . . . . . . . . . ...
work page 2022
-
[2]
(Dong et al., 2022)T[Q, P]is the reflection ofT[P, Q]across the identity line
work page 2022
-
[3]
(Zhu et al., 2022) For allγ >0, Dγ[Q||P] = 1−γ+γD 1 γ [P||Q]. Corollary A.9.Let HM be the privacy profile of a mechanism M, and let fM be the corresponding tightest trade-off function such thatMisf M-DP . Then the following holds
work page 2022
- [4]
-
[5]
For allγ >0,H M(γ) = 1−γ+γH M 1 γ . A privacy profileH − M ofMunder remove adjacency implies that the privacy profileH M is HM(γ) = max H − M(γ),1−γ+γH − M 1 γ . It is therefore sufficient to analyse privacy profiles under remove adjacency. Definition A.10.A privacy profileHis symmetric ifH(γ) = 1−γ+γH 1 γ . For an arbitrary privacy profile H, denote ˆH(γ...
work page 2022
-
[6]
It is commutative and associative
-
[7]
3.H⊗H Id =H Id ⊗H=H, whereH Id(γ) = [1−γ] + is the perfectly private privacy profile
It carries over the Blackwell ordering: IfH 21 ≥H 22, thenH 1 ⊗H 21 ≥H 1 ⊗H 22. 3.H⊗H Id =H Id ⊗H=H, whereH Id(γ) = [1−γ] + is the perfectly private privacy profile
-
[8]
\(H1 ⊗H 2) = ˆH1 ⊗ ˆH2. Proof. Proof for 0. We need to show that the resulting privacy profileH1⊗H2 is independent of the distribution pair(P1, Q1) and (P2, Q2) behind H1 and H2. It is sufficient to show that property 2 holds: By property 2,Dγ[P21, Q21] =D γ[P22, Q22] for allγimplies thatD γ[P1 ×P 21, Q1 ×Q 21] =D γ[P1 ×P 22, Q1 ×Q 22]for allγ. Proof for ...
work page 2021
-
[9]
14 f-Differential Privacy Filters: Validity and Approximate Solutions
It is commutative and associative. 14 f-Differential Privacy Filters: Validity and Approximate Solutions
-
[10]
3.f⊗Id=Id⊗f=f, whereId(α) = [1−α] + is the perfectly private privacy profile
It carries over the Blackwell ordering: Iff 21 ≤f 22, thenf 1 ⊗f 21 ≤f 1 ⊗f 22. 3.f⊗Id=Id⊗f=f, whereId(α) = [1−α] + is the perfectly private privacy profile. 4.(f 1 ⊗f 2)−1 =f −1 1 ⊗f −1 2 . Proof.The proposition is equivalent to Proposition A.13 Theorem A.17(Dong et al., 2022).If M1 is f1-DP , and the adaptively chosenM2 is f2-DP with a fixedf2, then (M1...
work page 2022
-
[11]
Uniform convergencesup γ≥0 |Hn(γ)−H(γ)| n→∞ − − − − →0, which is much stronger than point-wise convergence
-
[12]
Uniform convergence over any compact set: for allγ max >0,sup γ∈[0,γmax] |Hn(γ)−H(γ)| n→∞ − − − − →0
-
[13]
Convergence in the symmetrised∆-divergence introduced by Kaissis et al. (2024): sup γ≥0 |Hn(γ)−H(γ)| 1 +γ n→∞ − − − − →0 Proposition C.4.Uniform convergence implies convergence in∆-divergence. Proof.The∆-divergence is smaller or equal to theL ∞ norm, sup γ≥0 |H(γ)−H n(γ)| 1 +γ ≤sup γ≥0 |H(γ)−H n(γ)|. The following example shows that the implication in Pro...
work page 2024
-
[14]
Convergence in∆-divergence
-
[15]
Point-wise convergence
-
[16]
20 f-Differential Privacy Filters: Validity and Approximate Solutions Proof
Uniform convergence over any compact set. 20 f-Differential Privacy Filters: Validity and Approximate Solutions Proof. 1=⇒2. At any orderγ 0 >0, |Hn(γ0)−H(γ 0)|= (1 +γ 0) |Hn(γ0)−H(γ 0)| 1 +γ 0 ≤(1 +γ 0) sup γ≥0 |Hn(γ)−H(γ)| 1 +γ n→∞ − − − − →0. 2 =⇒3. Since Hn is decreasing for all n and H is continuous, uniform convergence over any compact set follows f...
work page 2022
-
[17]
Convergence in∆-divergence (Kaissis et al., 2024): min{∆≥0 :∀α∈[0,1−∆], f n(α+ ∆)−∆≤f(α)andf(α+ ∆)−∆≤f n(α)} n→∞ − − − − →0
work page 2024
-
[18]
Point-wise convergence over(0,1]
-
[19]
Uniform convergence over[α min,1]for allα min ∈(0,1]. Proof. 1 =⇒2. fn converges to f in ∆-divergence if and only if there exists a decreasing sequence of positive numbers ∆n >0such that∆ n ↘n→∞ 0and for alln, f(α+ ∆ n)−∆ n ≤f n(α)for allα∈[0,1−∆ n], fn(α)≤f(α−∆ n) + ∆n for allα∈[∆ n,1]. Fix α∈(0,1) . Then once n is large enough, say, n > N , ∆n < α <1−∆ ...
work page 2022
-
[20]
Some mechanism at step 1 is notε-DP for anyε, and 2.F ( ⊗)(T−2) fails to be a Blackwell chain, then thef-DP filter is invalid. Proof. Let H be the family of privacy profiles corresponding toF. Let H ∗ 1 , H∗ 2 be the pair of privacy profiles that do not have a Blackwell order. The space of ordersγcan be partioned as [0,∞) ={H ∗ 1 > H ∗ 2 } ⊔ {H ∗ 1 =H ∗ 2...
work page 2019
-
[21]
There existsκ∈ 0, 1 4 such that PT i=1 EP ξ2 i | Gi−1 −1 ≤κalmost surely
-
[22]
PT t=1 Lt(yt)− PT t=1 Ey∼P [Lt(yt)|y 1:t−1]√κ ≤x # −Φ(x) ≤C ρ√v ln ρ√v + r κ v , sup x∈R Q
There existsρ∈ 0, 1 2 such thatE P h |ξi|3 | Gi−1 i ≤ρE P ξ2 i | Gi−1 almost surely for alli. Then the cdf ofPT i=1 ξi satisfies sup x∈R P TX i=1 ξi ≤x ! −Φ(x) ≤C ρ|lnρ|+ √κ , whereΦis the cdf of the standard Gaussian distribution, andCis a universal constant. Note that as T grows, v increases linearly while ρ remains constant, indicating a convergence ra...
work page 2019
-
[23]
Near˜q= 0,T¯q 2 = Θ(1)as¯q→0
-
[24]
Near˜q= 1,T 1 ¯σ2 = Θ(1)andˆq= 1−¯q=O 1 ¯σ2 as¯σ→ ∞. Theorem 4.3.Under the above-mentioned limit conditions, the composition of subsampled Gaussian mechanisms given by Algorithm 2 satisfies the following privacy guarantees:
-
[25]
Near˜q= 0, the composition is∆-approximately √ 2B+O(¯q) -GDP with∆-errorO( √¯q)as¯q→0
-
[26]
Near˜q= 1, the composition is∆-approximately √ 2B+O 1 ¯σ2 -GDP with∆-errorO ln ¯σ ¯σ as¯σ→ ∞. Proof. Fix a remove pair S, S− that differs in some datapoint X. After T steps, the sum of conditional expectations of PLRVs betweenSandS − may remain belowB, because
-
[27]
The filter takes into account an amount of 1 2 q2 t e 1 σ2 t −1 or 1 2 q2 t 1 σ2 t , which upper bounds the actual amount 1 2 q2 t e ∥`gt(X)∥ σ2 −1 or 1 2 q2 t ∥`gt(X)∥ σ2 t spent by theS, S −
-
[28]
AfterTsteps, the total budget accounted for may not have reachedB. In this case, we can artificially create an extra mechanism MT+1 at step T+ 1 , tailored to the pair S, S−, that adaptively consumes the remaining budget, and then apply projection as a post-processing to extract the first T outputs from T+ 1 outputs. Therefore, w.l.o.g. we can assume that...
-
[29]
28 f-Differential Privacy Filters: Validity and Approximate Solutions
In the regime near˜q= 0, as¯q→0, the approximate GDP guarantee is B+B√ 2B +T·O ¯q3 = √ 2B+O(¯q), with∆-error O(¯q)|lnO(¯q)|+ r T·O(¯q 3) 2B =O √¯q . 28 f-Differential Privacy Filters: Validity and Approximate Solutions
-
[30]
In the regime near˜q= 1, as¯σ→ ∞the approximate GDP guarantee is B+B√ 2B +Tˆq·O 1 ¯σ4 +T·O ˆq2 = √ 2B+O 1 ¯σ2 , with∆-error O 1 ¯σ lnO 1 ¯σ + s Tˆq·O 1 ¯σ4 +T·O(ˆq 2) 2B =O ln ¯σ ¯σ . Since the ∆-approximate µ-GDP guarantee is symmetric, the privacy guarantees above apply to both trade-off functions T[M 1:t(S),M 1:t(S−)]andT[M 1:t(S−),M 1:t(S)]. Theorem 4...
work page 2021
-
[31]
Use 1 1+x = 1−x+x 2 +O x3 as x→0 to transform the denominator of the fraction inside the log, and obtain a log of a polynomial
-
[32]
Useln(1 +x) =x− 1 2 x2 +O x3 asx→0to transform the log of a polynomial into a polynomial. Throughout these steps, we neglect terms that would lead to a final contribution of order less than q2. The terms q2 −Pn j=1 naj(y)−na(y) + P n(n+1) 2 k=1 bk(y) and q2 −Pn j=1 naj(y) +P n(n−1) 2 k=1 bk(y) will eventually only con- tribute to the final expression as s...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.