pith. sign in

arxiv: 2602.06756 · v2 · submitted 2026-02-06 · 💻 cs.CR

f-Differential Privacy Filters: Validity and Approximate Solutions

Pith reviewed 2026-05-16 06:54 UTC · model grok-4.3

classification 💻 cs.CR
keywords differential privacyf-DPprivacy filtersadaptive compositioncentral limit theoremGaussian differential privacysubsampled mechanisms
0
0 comments X

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.

The paper establishes that the intuitive f-DP filter, which accumulates tensor products of trade-off functions along each path and stops when a target curve is crossed, fails to enforce the promised global privacy budget when mechanism choices and parameters can depend on previous outputs. It characterizes exactly when this natural construction remains valid and proves a central limit theorem showing that cumulative privacy losses still converge to a Gaussian limit even with full adaptivity. As a concrete demonstration it supplies a closed-form approximate Gaussian DP filter for subsampled Gaussian mechanisms that improves on RDP-based accounting in both the small-q and large-q asymptotic regimes.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2602.06756 by Antti Honkela, Antti Koskela, Long Tran, Ossi R\"ais\"a.

Figure 1
Figure 1. Figure 1: A counterexample to the validity of the f-DP filter, constructed using subsampled Gaussian mechanisms. The first row a), b) showcases the calibration point phenomenon between tensor products of future trade-off functions. The second row c), d) reveals the failure of fB,tight-DP, indicating filter invalidity. The left column a), c) considers remove adjacency, while the right column b), d) symmetrises into a… view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of fully adaptive RDP accounting and ap￾proximate fully adaptive GDP accounting for the Poisson subsam￾pled Gaussian mechanism with adaptive σ-parameter values when the subsampling ratio q = 0.01. The resulting filtering algorithm is approximately µ-GDP for µ = √ 2B ≈ 0.314. 5. Discussion and Conclusions This work resolves a central open question about fully adap￾tive privacy accounting for trad… view at source ↗
Figure 3
Figure 3. Figure 3: Tensor products of future privacy profiles of a single pair ((X), ∅), with a calibration point at γ0 ≈ 1.363. These privacy profiles are equivalent to the trade-off functions in Figure 1a. Denote H2×3,1 = H − SG,0.5,2.25 ⊗ H − SG,0.5,2.25 and H2×3,2 = H − SG,0.5,0.1 ⊗ H − SG,0.5,10 the privacy profiles illustrated in [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Left: Hadapt exceeds HB,tight in the region surrounding γ0 ≈ 1.363. Right: Symmetrising these privacy profiles does not erase the phenomenon. These privacy profiles are equivalent to the trade-off functions in Figures 1c and 1d. Why the f-DP filter failure occurs in Example 3.3. The tensor products underlying HB,tight,  H − SG,0.5,1.3 ⊗ H2×3,1  (γ) = Z R H2×3,1  γ q1(y1) p1(y1)  p1(y1) dy1,  H − SG,0.… view at source ↗
Figure 5
Figure 5. Figure 5: Comparing H1 ⊗ H ↑ 2×3 to Hadapt and HB,tight, as described in Corollary B.4. We verify the inequality  H1 ⊗ H ↑ 2×3  (γ0) > HB(γ0) in Example 3.3, where H ↑ 2×3 = max(H2×3,1, H2×3,2). In Figure 5a, Hadapt approaches H1 ⊗ H ↑ 2×3 at γ0 ≈ 1.363 but not everywhere, since the selection rule in Example 3.3 coincides with that in the proof of Theorem B.1 when γ = γ0. C. Convergence of Privacy Profiles/Trade-o… view at source ↗
Figure 6
Figure 6. Figure 6: Relative error of EP [ln(P/Q)] versus the approximation 1 2 q 2 (exp(µ 2 /σ2 ) − 1) as q → 0, illustrating the approximation of (1a) in Theorem 4.1. 0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200 q 10 8 10 7 10 6 10 5 10 4 10 3 10 2 A bsolute relativ e error |(accurate a p pro x)/a p pro x| Relative error for VarP[log(P/Q)] vs. q = 2 = 4 = 6 = 8 = 10 [PITH_FULL_IMAGE:figures/full_fig_p030_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Relative error of VarP [ln(P/Q)] versus the approximation q 2 (exp(µ 2 /σ2 ) − 1) as q → 0, illustrating the approximation (1c) in Theorem 4.1. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Relative error of EP [ln(P/Q)] versus the approximation 1 2 q 2µ 2 /σ2 for q ≈ 1, illustrating the approximation (2a) in Theorem 4.1. 0.800 0.825 0.850 0.875 0.900 0.925 0.950 0.975 1.000 q 10 4 10 3 10 2 A bsolute relativ e error |(accurate a p pro x)/a p pro x| Relative error for VarP[log(P/Q)] vs. q = 2 = 4 = 6 = 8 = 10 [PITH_FULL_IMAGE:figures/full_fig_p031_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Relative error of VarP [log(P/Q)] versus the approximation q 2µ 2 /σ2 for q ≈ 1, illustrating the approximation (2c) in Theorem 4.1. 31 [PITH_FULL_IMAGE:figures/full_fig_p031_9.png] view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

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)
  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)
  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

1 responses · 0 unresolved

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
  1. 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

0 steps flagged

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

0 free parameters · 2 axioms · 0 invented entities

Central claims rest on the tensor-product composition rule for f-DP trade-off functions and standard regularity conditions for central-limit behavior; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • standard math f-DP trade-off functions compose via tensor products under adaptive mechanisms
    Invoked when defining the natural filter and its path-wise accumulation.
  • domain assumption Convergence to Gaussian privacy loss under repeated adaptive composition
    Required for the fully adaptive CLT and the approximate GDP filter.

pith-pipeline@v0.9.0 · 5585 in / 1457 out tokens · 47891 ms · 2026-05-16T06:54:13.169061+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [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 . . . . . . . . . . . . . . . . . . ...

  2. [2]

    (Dong et al., 2022)T[Q, P]is the reflection ofT[P, Q]across the identity line

  3. [3]

    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

    (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

  4. [4]

    the identity line

    The graph off M(α)is symmetric w.r.t. the identity line

  5. [5]

    A privacy profileH − M ofMunder remove adjacency implies that the privacy profileH M is HM(γ) = max H − M(γ),1−γ+γH − M 1 γ

    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(γ...

  6. [6]

    It is commutative and associative

  7. [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. [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 ...

  9. [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. [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...

  11. [11]

    Uniform convergencesup γ≥0 |Hn(γ)−H(γ)| n→∞ − − − − →0, which is much stronger than point-wise convergence

  12. [12]

    Uniform convergence over any compact set: for allγ max >0,sup γ∈[0,γmax] |Hn(γ)−H(γ)| n→∞ − − − − →0

  13. [13]

    (2024): sup γ≥0 |Hn(γ)−H(γ)| 1 +γ n→∞ − − − − →0 Proposition C.4.Uniform convergence implies convergence in∆-divergence

    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...

  14. [14]

    Convergence in∆-divergence

  15. [15]

    Point-wise convergence

  16. [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...

  17. [17]

    Convergence in∆-divergence (Kaissis et al., 2024): min{∆≥0 :∀α∈[0,1−∆], f n(α+ ∆)−∆≤f(α)andf(α+ ∆)−∆≤f n(α)} n→∞ − − − − →0

  18. [18]

    Point-wise convergence over(0,1]

  19. [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−∆ ...

  20. [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...

  21. [21]

    There existsκ∈ 0, 1 4 such that PT i=1 EP ξ2 i | Gi−1 −1 ≤κalmost surely

  22. [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...

  23. [23]

    Near˜q= 0,T¯q 2 = Θ(1)as¯q→0

  24. [24]

    Theorem 4.3.Under the above-mentioned limit conditions, the composition of subsampled Gaussian mechanisms given by Algorithm 2 satisfies the following privacy guarantees:

    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. [25]

    Near˜q= 0, the composition is∆-approximately √ 2B+O(¯q) -GDP with∆-errorO( √¯q)as¯q→0

  26. [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. [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. [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. [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. [30]

    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)]

    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...

  31. [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. [32]

    ln P Q 2# − EP ln P Q 2 =E P

    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...