Realisation-Level Privacy Filtering
arXiv:2604.08630v1 [cs.CR] 9 Apr 2026
Sophie Taylor, Praneeth Kumar Vippathalla, and Justin P. Coon
Abstract—We study differentially private data release, where a database is accessed through successive, possibly adaptive queries and mechanisms. Existing composition theorems and privacy filters combine worst case per-round privacy parameters, leaving room for more refined accounting based on realised leakage, which we term realisation-level accounting. We propose a realisation-level filtering approach to determine stopping times for data releases, and design one such filter. Despite technical challenges arising from conditioning on realisations and stopping time, we prove that the filter guarantees (ϵ, δ)-differential privacy, with ϵ and δ chosen by the data handler. Through numerical evidence, we demonstrate that realisation-level filtering provides a path to better utility beyond mechanism-level methods. Furthermore, our proposed filter applies to arbitrary mechanisms, including those that are badly behaved under Rényi differential privacy.
I. I NTRODUCTION In most privacy preserving applications, a database is subject to successive queries, and is therefore accessed more than once. In modern settings, queries and mechanisms are often adaptive, meaning they depend on previously released outputs. A key example is federated learning, where model training involves repeated access to data. In such systems, the sequence of queries and mechanisms may be generated by an adaptive training procedure. Moreover, each data access incurs a privacy loss, making adaptive privacy accounting essential. Hence, it is crucial that a system designer can quantify how privacy guarantees compose under multiple adaptive mechanism uses. Throughout this work, we take differential privacy (DP) as the privacy notion. Existing approaches to privacy composition provide powerful guarantees in many contexts, but can be overly conservative in certain settings. Classical composition theorems bound the cumulative privacy loss without knowledge of mechanism outputs, commonly by combining known per-mechanism parameters [1]–[3]. Notably, Rényi differential privacy (RDP) provides strong composition guarantees by leveraging the distribution of the privacy leakage [4] and more recent FFT [5], [6] and saddle-point based [7] approaches refine this by directly targeting the tail probability of the privacy loss, the The authors are with the Department of Engineering Science, University of Oxford, Oxford, U.K (e-mail: [email protected]; [email protected]; [email protected]). This research was funded in whole or in part by the Engineering and Physical Sciences Research Council under grant number EP/W524311/1, and the U. S. Army Research Laboratory and the U. S. Army Research Office under grant number W911NF-22-1-0070. For the purpose of Open Access, the authors have applied a CC BY public copyright license to any Author Accepted Manuscript (AAM) version arising from this submission.
quantity that governs DP.1 In practice, RDP is used as an accounting tool, with privacy guarantees converted back to DP for reporting. Classical guarantees must be computed in advance and are independent of the realised mechanism outputs. Given a privacy budget, the number of allowable releases must be determined uniformly over all possible mechanism choices, rather than tailored to the specific sequence used. This can lead to very conservative stopping rules in adaptive scenarios. To tackle the adaptive setting, researchers have proposed the use of privacy filters, which may be DP based [8], [9] or RDP based [9], [10], and keep a running total of privacy loss to adaptively decide when to stop releases to stay within a privacy budget. Existing privacy filters track the privacy loss of the sequence of realised mechanisms by combining their per round parameters. This contrasts classical composition, which operates without knowledge of the particular realisations of adaptively chosen mechanisms. We call this mechanism-level accounting. Despite its advantages, mechanism-level accounting relies on worst case privacy parameters, and does not exploit the fact that the realised leakage may be significantly smaller. In this work, we propose a filtering approach that tracks leakage pointwise, operating at the realisation-level. While this may appear natural, doing so poses significant technical challenges, as differential privacy can be violated through conditioning on realised outputs. In particular, designing a stopping rule to ensure a privacy guarantee requires accounting for the privacy loss from halting the filter. In this work, we propose a privacy filtering approach based on realisation-level accounting. We design one such filter and prove that it satisfies (ϵ, δ)-DP. The filter is generally applicable, and does not assume a particular class of mechanism. Finally, we discuss its utility implications in terms of the allowed number of data releases. II. P RIVACY F ILTERING Consider the adaptive data privacy problem setup in Figure 1. An analyst sends a data request R1 from the set of allowable requests R1 to a database X. This is input to a privacy mechanism M1 , which produces a random output Y1 = M1 (R1 , X). Given this response, the analyst can make a second request R2 ∈ R2 . Importantly, requests can be chosen adaptively, depending on previous outputs. The second data release Y2 is the output of M2 (R1 , R2 , Y1 , X). The process continues so that the ith data release Yi is generated by 1 As typically presented, saddle-point approaches use asymptotic approximations rather than explicit upper bounds, making them more naturally suited to evaluating privacy loss than to guaranteeing strict DP bounds. FFT-based convolution methods rely on discretisation and incur non-constant runtime.
A. Mechanism-Level Privacy Accounting
Fig. 1. Adaptive data privacy problem
Mi (R1 , . . . , Ri , Y1 , . . . , Yi−1 , X). We assume a fixed series of allowable sets R1 , R2 . . . , and a fixed family of conditional distributions PX (Y1 |R1 ), PX (Y1 |R1 , R2 , Y2 ), . . . defining the mechanisms M1 , M2 , . . . a priori; the mechanisms are adaptive in the standard sense that, at each round, the distribution of the output is conditioned on all previous requests and outputs. We use superscript indexing to denote the first i requests Ri := (R1 , . . . , Ri ) and the first i − 1 outputs Y i−1 := (Y1 , . . . , Yi−1 ). For i ≥ 1, we refer to (Ri , Y i−1 ) as the partial transcript and (Ri , Y i ) as the full transcript at step i. Conditioned on a realised partial transcript (Ri , Y i−1 ) = (ri , y i−1 ) and database X = x, the output Yi is distributed according to Px (yi |ri , y i−1 ). Throughout, the subscript x indicates that the probabilities are conditioned on the database X = x. To safely carry out this process, the data handler must control the privacy loss incurred by the sequence of released outputs. Privacy preservation can be achieved through the use of a privacy filter. A privacy filter [11] is a sequential algorithm that, after every request, decides whether to halt the data release process or proceed with accepting a new request. In other words, it tracks leakage to inform a stopping rule. Let T denote the filter’s stopping time which is defined as the index of the last released output when the algorithm halts, and is a random variable. In order for the filter to guarantee (ϵ, δ)-DP, we need to consider the following definition.
The classical additive composition result of [1] enables a simple privacy filter. Let (ϵ, δ) be the privacy budget. Suppose (M1 , M2 , . . . , Mt−1 ) are the adaptive mechanisms applied so far, and at step t a request rt is made with Mt being the corresponding mechanism. Then, the data handler might employ privacy filter [8] that checks Pt the so-calledPadditive t if i=1 ϵi ≤ ϵ and i=1 δi ≤ δ, where (ϵi , δi ) are the DP parameters of mechanism Mi (ri , y i−1 , X). If either condition is violated, the data handler will not apply Mt to X and stops accepting new requests. Otherwise, she applies the mechanism, releases the corresponding data, and accepts a new request. Using an advanced composition result for adaptive mechanisms, [8, Thm 5.1] gave an improved privacy filter (in certain Pt i regimes) that checks if δ ′ + i=1 ϵ2δ ϵi ≤ δ and ϵ exceeds e i v u t u X + t2 ϵ2i +
Definition 1 ((ϵ, δ)-DP Privacy Filter). Given a sequence of mechanisms and allowable requests, a privacy filter is said to be (ϵ, δ)-DP if, for every adversary employing a random and adaptive strategy to choose requests, the following holds: T T T T Px R , Y ∈ S ≤ eϵ Px′ R , Y ∈ S + δ, (1)
! ϵ2 2 28.04 log( δ1′ ) i=1 i=1 v !! u Pt 1 2 u 28.04 log( ) ϵ 1 2 ′ i=1 i δ t 1 + log × +1 log . 2 ϵ2 δ′ (2) This will be referred to as an advanced privacy filter. Privacy filters based on RDP parameters have also been proposed [9], [10]. These track privacy loss in terms of Rényi divergence of fixed order α > 1. Let ρi (α) denote the adaptive RDP parameter of the mechanism Mi (ri , y i−1 , X), which may depend on previous requests and outputs. By known composition properties ofPRDP [4], the cumulative t RDP parameter after t steps is i=1 ρi (α). To employ an adaptive RDPP privacy filter, the data handler checks at each t step whether i=1 ρi (α) ≤ ϵα . If the condition is violated, the filter stops and Mt is not applied. From [4], this yields log 1 an (ϵ, δ)-DP guarantee, where ϵ = ϵα + α−1δ . Importantly, α must in general be fixed before running the filter and cannot be optimised during its execution. In the mechanism-level setting, the quantities ρi (α) are transcript-dependent and do not hold uniformly over all adaptive executions. In contrast, under classical RDP composition, the composed RDP parameter does not depend on the execution, and an optimisation over α > 1 can safely be performed. As these filters use mechanism parameters to track privacy loss, we call them mechanism-level privacy filters. All are designed to guarantee (ϵ, δ)-DP.
for all neighbouring databases x ∼ x′ and all measurable sets S of full transcripts.
B. Realisation-Level Privacy Accounting
Note that we use the full transcript in our DP definition, despite the fact that requests are chosen by the adversary. This is because all random variables can be jointly used by the adversary to infer about the database. By requiring privacy to hold for all measurable sets of full transcripts, we ensure that no adversary can distinguish neighbouring databases beyond the (ϵ, δ)-DP bound, however they select their requests.
Mechanism-level privacy accounting relies on worst case parameters for each mechanism, regardless of realised outputs. As a result, these filters may halt in executions where the realised leakage is significantly less than the budget. Therefore, we propose another paradigm for a privacy filter design based on realisation-level privacy accounting. Here, the idea is to track the accumulated privacy loss of the full transcript (ri , y i )
t X ϵi (eϵi − 1)
at the ith step. The privacy loss incurred in releasing the output yi at ith step given the partial transcript (ri , y i−1 ) is li (x, x′ ) := log
Px (yi | ri , y i−1 ) . Px′ (yi | ri , y i−1 )
The cumulative privacy loss at step i corresponding to the full transcript (ri , y i ) is given by l(i) (x, x′ ) := l1 (x, x′ ) + · · · + li (x, x′ ). The associated random variables are denoted by Li (x, x′ ) and L(i) (x, x′ ). For brevity, we will sometimes drop the explicit dependency on x ∼ x′ , so Li := Li (x, x′ ). We refer to these quantities as leakage. A filter tracking the leakage this way has the potential to be less conservative by adapting to favourable outcomes, thereby allowing more data releases without compromising privacy. This intuition is formalised by our proposed privacy filter in Sec. III and the rest of the paper. Before presenting ours, we consider design aspects of a general realisation-level privacy filter. Upon stopping, the fulltranscript leakage to an adversary is given by the random variable, log
Px (RT , Y T ) , Px′ (RT , Y T )
where T is the stopping time of the algorithm, and (RT , Y T ) is the full transcript the adversary has. By noting that Ri cannot depend on X given (Ri−1 , Y i−1 ), we can write T
log
T
Px (R , Y ) Px′ (RT , Y T ) QT Px (Ri |Ri−1 , Y i−1 )Px (Yi |Ri , Y i−1 ) = log QTi=1 i−1 , Y i−1 )P ′ (Y |Ri , Y i−1 ) ′ x i i=1 Px (Ri |R QT i i−1 Px (Yi |R , Y ) = log QTi=1 i i−1 ′ ) i=1 Px (Yi |R , Y Px (YT |RT , Y T −1 ) Px (Y1 |R1 ) + · · · + log = log Px′ (Y1 |R1 ) Px′ (YT |RT , Y T −1 ) (T ) ′ = L (x, x ).
Therefore, the filter bounds the leakage to an adversary at the stopping time by tracking and limiting the cumulative leakage. Central to the filter is the design of a stopping rule that preserves the desired privacy guarantee. In an attempt to achieve (ϵ, δ)-DP, one might construct the following naive realisationlevel privacy filter. At each step i, upon receiving request ri , it considers the accumulated leakage l(i−1) (x, x′ ) from the realised full transcript (ri−1 , y i−1 ), and analyses the mechanism Mi (ri , y i−1 , X). If the worst-case (over databases) probability that releasing Yi would cause the accumulated privacy loss to exceed ϵ is greater than δ, i.e., Px Li (x, x′ ) > ϵ − l(i−1) (x, x′ ) | ri , y i−1 > δ, for any x ∼ x′ , the filter halts and the mechanism is not executed; otherwise, the mechanism is applied and the output yi is released. This construction ensures the stopping time leaks no information about X beyond that jointly revealed by requests and outputs.
Despite its intuitive nature and handling of stopping decisions, (ϵ, δ)-DP is not guaranteed. To see this, consider repeated application of an identical non-adaptive binary erasure mechanism, where an adversary makes the same fixed request at each step, and observes the output of the mechanism. Here, Y = X with probability p ≤ δ and Y = ∆ otherwise. These events correspond to infinite and zero leakages respectively. The filter halts at step i iff l(i−2) (x, x′ ) = 0 and l(i−1) (x, x′ ) = ∞ for one ordering of the neighbouring pair. In other words, the naive filter continues as long as only ∆’s are observed. Therefore, with probability one, the infinite leakage event occurs, and by Def. 1, guarantee is no better than (ϵ, 1)DP. Owing to the difficulty in ensuring (ϵ, δ)-DP guarantee, a realisation-level privacy filter must be carefully designed. III. A R EALISATION -L EVEL P RIVACY F ILTER We introduce a privacy filter that tracks cumulative leakage, and bounds it with a valid stopping rule. In step i, the request ri is received. What follows is subtle but essential. Rather than deciding whether to release yi , the algorithm decides whether it will receive the following request ri+1 , using knowledge of ri and y i−1 . Specifically, it uses a step-wise parameter δ̂i+1 to assess the risk of releasing yi+1 under the worst case request ri+1 and database x. Formally, δ̂i+1 is given by n o inf z ∈ [0, 1] : inf ′ Px Yi ∈ Ỹi (z) | ri , y i−1 ≥ 1 − θ , x∼x ri+1 ∈Ri+1
(3) where Ỹi (z) is a function of x, x′ and ri+1 and is defined as n o yi : Px Li+1 (x, x′ ) > ϵ − l(i) (x, x′ ) | ri+1 , y i ≤ z . Note that the algorithm requires checking the condition δ̂i+1 ≤ δ̃. This is most easily done by confirming whether inf ′ Px Yi ∈ Ỹi (δ̃) | ri , y i−1 ≥ 1 − θ, (4) x∼x ri+1 ∈Ri+1
as (4) is true if and only if δ̂i+1 ≤ δ̃. Whatever the outcome of this check, the algorithm then executes mechanism i and releases yi . The privacy filter is outlined in Algorithm 1, where r0 and y0 are taken to be fixed (r0 = y0 =⊥), and l0 = 0. The look-ahead design of the stopping rule makes the filter (ϵ, δ)-DP, which is proved in Sec. IV. Formally, it ensures that the stopping event {T = i} does not depend on the realised output yi , which allows the stopping time to be decoupled from the leakage in the proof of Theorem 1. Finally, we remark that the algorithm requires a choice of parameters (δ̃, θ, N ). Any decision satisfying the condition δ̃ + θ(1 − δ̃)N ≤ δ preserves (ϵ, δ)-DP, but may yield substantially different stopping times. Here, N is the maximum stopping time. The parameter θ introduces a relaxation in (4), allowing the condition to hold with high probability rather than with probability 1. If θ = 0, the leakage induced by yi+1 is analysed for the worst possible realisation of yi . Increasing θ softens this condition. In turn δ̃ must be reduced from δ to accommodate positive θ. We also see a trade off between θ and
1Ai (x,x′ ) = Ex Ex 1{T =i} Ri , Y i−1 1 − δ̂i 1 = Ex 1{T =i} Px Ai (x, x′ ) | Ri , Y i−1 1 − δ̂i = Ex Ex 1{T =i} Z | Ri , Y i−2 ,
Algorithm 1: Realisation-level privacy filter Input: x, ϵ, δ, M1 , M2 , . . . , R1 , R2 , . . . Choose δ̃ ∈ [0, δ], θ ∈ [0, 1], and N ∈ Z+ such that δ̃ + θ(1 − δ̃)N ≤ δ (−1) 3 Initialize i = 0, l =0 4 while i ≤ N do 5 Receive ri 6 Execute Mi (ri , y i−1 , x) to obtain and release yi . 7 if δ̂i+1 > δ̃ (if (4) is false) then 8 break 9 end 10 l(i) (x, x′ ) ← l(i−1) (x, x′ ) + li (x, x′ ), ∀x ∼ x′ 11 i←i+1 12 end 1 2
IV. P RIVACY G UARANTEE In this section, we establish the privacy guarantee of our privacy filter. For brevity, we use Px (S) to mean Px ((RT , Y T ) ∈ S), and Ex to denote an expectation with respect to Px . Theorem 1. The privacy filter described in Algorithm 1 is (ϵ, δ)-DP. Proof. Let A(x, x′ ) := {L(T ) (x, x′ ) ≤ ϵ}. To prove the (ϵ, δ)DP guarantee, it is enough to show that ∀x ∼ x′ ,
(5)
because of the following argument. If (RT , Y T ) ∈ A(x, x′ ) then Px (RT , Y T ) ≤ eϵ Px′ (RT , Y T ). Hence, for any measurable set S, we have Px (S ∩ A(x, x′ )) ≤ eϵ Px′ (S ∩ A(x, x′ )). This combined with (5) yields Px (S) = Px (S ∩ A(x, x′ )) + Px (S ∩ Ac (x, x′ ))
′
= Px (T = i) − θ,
(10)
for all x ∼ x′ . For an upper bound on the expression on the left-hand side of (10), note that if T = i, then 1 − δ̂i ≥ 1 − δ̃. Thus, 1Ai (x,x′ )∩{T =i} ′ Ex Fi (x, x )1{T =i} = Ex 1 − δ̂i 1 Px (Ai (x, x′ ), T = i). (11) ≤ 1 − δ̃ Combining (10) and (11) yields Px (Ai (x, x′ ), T = i) ≥ (1 − δ̃)(Px (T = i) − θ),
(12)
for all x ∼ x′ . We can finally return to Px (Ac (x, x′ )). Following from (12) yields Px (Ac (x, x′ )) = 1 − Px (A(x, x′ )) =1−
N X
Px (Ai (x, x′ ), T = i)
i=0 N X ≤1− (1 − δ̃)(Px (T = i) − θ)
= 1 − (1 − δ̃) + N θ(1 − δ̃) (6)
for all neighbours x ∼ x , proving the (ϵ, δ)-DP guarantee. Now we show (5). To achieve this, define the event Ai (x, x′ ) := L(i) (x, x′ ) ≤ ϵ and the random variable Fi (x, x′ ) := 1Ai (x,x′ ) /(1 − δ̂i ) for i ≥ 1. Note that the stopping event T = i can be written as o n {T = i} = δ̂1 ≤ δ̃, . . . , δ̂i ≤ δ̃, δ̂i+1 > δ̃ . Now consider the expectation Ex Fi (x, x′ )1{T =i}
where (9) follows from the definition of δ̂i (3) that given (Ri−1 , Y i−2 ), Z ≥ 1 with probability at least 1 − θ for all Ri . By combining (8), and (9), we finally get Ex Fi (x, x′ )1{T =i} ≥ Ex Px T = i | Ri , Y i−2 − θ
i=1
≤ eϵ Px′ (S ∩ A(x, x′ )) + Px (Ac (x, x′ )) ≤ eϵ Px′ (S) + Px (Ac (x, x′ )) ≤ eϵ Px′ (S) + δ,
(8)
where (7) uses that fact that δ̂i is a function of Ri−1 , Y i−2 and 1{T =i} is a function of Ri , Y i−1 , and for brevity, in (8) we use Z := Px (Ai |Ri , Y i−2 , Yi−1 )/(1− δ̂i ). Since Z ≥ 1{Z≥1} , Ex 1{T =i} Z|Ri , Y i−2 ≥ Px T = i, Z ≥ 1 | Ri , Y i−2 ≥ Px T = i | Ri , Y i−2 + Px {Z ≥ 1} | Ri , Y i−2 − 1 ≥ Px T = i | Ri , Y i−2 − θ, (9)
N . The maximum stopping time is allowed to be very large if θ is very small. The best parameter choice may vary according to the sequence of mechanisms input to the algorithm. In Sec. V-B, we discuss parameter selection for a series of i.i.d Gaussian mechanisms, and find that the (δ̃, θ) pair can be chosen optimally given N . In fact, the idea may be extended to any set of i.i.d. mechanisms.
Px (Ac (x, x′ )) ≤ δ
(7)
≤ δ̃ + θ(1 − δ̃)N ≤ δ, where we note that Px (A0 (x, x′ ), T = 0) = 0, and the final inequality is true by construction, proving the theorem. V. U TILITY OF THE R EALISATION -L EVEL F ILTER Beyond ensuring differential privacy, a privacy filter is more useful if it can run for a longer, enabling many data releases without privacy compromise. Utility is thus naturally characterised by the stopping time T , the number of database queries before access is cut off. We focus on survival probabilities
Px (T ≥ t). In this section, we contrast the utility of classical composition, mechanism-level filters, and our realisation-level filter. A. Pure Differential Privacy We first consider (ϵ, 0)-DP approaches, comparing their utility by formalising the release conditions. Assume that the filters operate on fixed sequences of pure DP mechanisms M1 , M2 , ... and allowable sets R1 , R2 , .... Among mechanism-level approaches, we adopt the additive privacy filter described in Sec. II-A since additive composition is tight for pure DP while advanced composition and RDPbased composition rely on δ > 0. For step i, classical composition concerns the ϵ parameter of the full mechanism Mi (Ri , Y i−1 , X), whilst the additive filter tracks that of the realised mechanism Mi (ri , y i−1 , X). Let ϵtC , ϵtM , and ϵtR denote privacy loss at step t under classical composition, mechanism-level accounting and realisationi i−1 level accounting respectively. If Mi (R , X) is ϵi -DP, P,tY classical composition yields an overall i=1 ϵi -DP guarantee. Writing ϵtC =
t X
ϵi =
t X
li (x, x′ ),
sup
(13)
i i ′ i=1 r ,y ,x∼x
i=1
yt is released if ϵtC ≤ ϵ. The additive filter on the other hand considers the realised mechanism Mi (ri , y i−1 , X), which is pure ϵ′i -DP. With ϵtM =
t X
ϵ′i =
i=1
t X
sup li (x, x′ ),
(14)
′ i=1 yi ,x∼x
yt is released if ϵtM ≤ ϵ. Finally, consider realisation-level filtering as in Algorithm 1. When δ = 0, θ = δ̃ = 0, and the continuation criteria for output t becomes ϵtR ≤ ϵ, where ( t−2 ) X t ′ ′ ′ ϵR = sup li (x, x ) + sup (lt−1 (x, x ) + lt (x, x )) . x∼x′
rt ,yt−1 ,yt
i=1
(15) The tth output is released if ϵiR ≤ ϵ for all i ≤ t. Combining (13), (14) and (15) reveals that, for all t, ϵtC ≥ ϵtM and ϵtC ≥ ϵtR . Thus, for any adversary, classical composition admits the fewest data releases, highlighting the benefit of privacy filtering. No strict ordering exists between ϵtM and ϵtR , but a sufficient condition for ϵtM ≥ ϵtR is A(x, x′ ) + B(x, x′ ) + C(x, x′ ) ≥ 0, ∀x ∼ x′ , where A(x, x′ ) :=
t−2 X
sup li (x̂, x̂′ ) − li (x, x′ ),
′ i=1 yi ,x̂∼x̂
B(x, x′ ) :=
sup yt−1 ,x̂∼x̂′
′
lt−1 (x̂, x̂′ ) − sup lt−1 (x, x′ ), yt−1 ′
C(x, x ) := sup lt (x̂, x̂ ) − yt ,x̂∼x̂′
′
sup
lt (x, x′ ).
rt ,yt−1 ,yt ′
Both A(x, x ) and B(x, x ) are non-negative, whilst the sign of C(x, x′ ) is not known in general. Thus, the condition A+B + C ≥ 0 weighs an accumulation of non-negative contributions
from earlier steps against a single term of uncertain sign at step t. While it is not impossible for C to dominate the sum for small t, the term A + B grows with t. Once the filters pass early stopping thresholds, the condition increasingly favours the realisation-level filter. A similar effect appears numerically in Sec. V-B in the approximate DP setting. B. Approximate Differential Privacy In this section, we numerically compare the utility of existing mechanism-level filters [8]–[10] with our realisationlevel privacy filter, described by Algorithm 1. We simulate the additive, advanced and RDP privacy filters outlined in Sec. II-A, alongside our realisation-level filter, for a sequence of i.i.d. Gaussian mechanisms. Suppose x = (x1 , . . . , xn ) and x′ = (x′1 , . . . , x′n ) with xj , x′j ∈ {0, 1} are two neighbouring datasets that differ only in one Pn entry. We consider counting queries of the form r(x) = j=1 xj , and i.i.d. Gaussian mechanisms with Yi = r(X) + Zi , where Zi ∼ N (0, σ 2 ), and σ = 2. We note a practical consideration when implementing mechanism-level privacy filters. For the additive and adaptive DP-based filters, a given mechanism Mi (ri , yi−1 , X) may admit multiple valid (ϵi , δi ) pairs, requiring a choice of parameters at each round. Similarly, a constant Rényi divergence order α > 1 must be chosen for the RDP filter. In the current setting, mechanisms are i.i.d. and are therefore all known in advance. This allows us to select parameter values optimally across all rounds. Accordingly, all mechanism-level simulations use parameter choices that maximise the stopping time. This process, and hence the computation of mechanismlevel stopping times, is outlined in Appendix B. Notably, in the i.i.d. setting, mechanism-level filtering reduces to classical composition. In contrast, realisation-level filters retain their adaptive nature. Recall that we must fix (N, δ̃, θ) before running the realisation-level filter. We start by specifying the maximum stopping time N , which determines the maximum number of outputs that may be released. Unlike the other parameters, N has a direct operational interpretation, and can therefore be chosen based on the intended use of the filter. It should be set to a reasonable upper bound on the number of outputs one expects to consider. For i.i.d. Gaussian mechanisms, we can then choose (δ̃, θ) optimally to maximise the stopping time. Proposition 1. In the i.i.d. Gaussian setting described above with unit sensitivity, i.e., |r(x) − r(x′ )| = 1 ∀x ∼ x′ , the condition (4) for releasing yi+1 is equivalent to l(i−1) (x, x′ ) ≤ κ, ∀x ∼ x′ , where 1 −1 1 Φ (1 − δ̃) + Φ−1 (1 − θ) , κ := ϵ − 2 − σ σ and Φ is the cumulative density function of the standard normal distribution. The proof of Proposition 1 can be found in Appendix A. Recall that there are only two neighbouring datasets within
our setting, and that li (x, x′ ) = −li (x′ , x). Therefore, from Proposition 1, we can say Px (T ≥ t) = Px |L(1) (x, x′ )| ≤ κ, . . . , |L(t−2) (x, x′ )| ≤ κ . Clearly, maximising κ maximises the stopping time. Taking δ̃ , the optimal (δ̃, θ) pair can be found by numeriθ = N δ− (1−δ̃) cally minimising Φ−1 (1 − δ̃) + Φ−1 (1 − θ). Following this procedure, we set (N, δ̃, θ) as (48, 4.797 × 10−6 , 2.073 × 10−5 ), which yields the result in Fig. 2. We remark that, due to symmetry in our setting, Px (T ≥ t) = Px′ (T ≥ t). Therefore, we simply plot P (T ≥ t) against t. The primary observation is that the realisation-level filter generally dominates the mechanism-level filters, particularly for larger t. The realisation-level filter admits a marginally lower survival probability than the RDP filter for a small number of early t values. This is consistent with its reliance on realised leakage values, which may be unusually high, occasionally triggering early stopping. The effect is strongly outweighed in the long term. We also remark the poor performance of the advanced filter, which is down to the particular mechanisms simulated. The advanced composition theorem significantly outperforms additive composition in the small ϵi regime, which is not where this simulation operates. Overall, the results highlight the potential for utility gains from privacy accounting at the realisation level. VI. D ISCUSSION AND F UTURE D IRECTION In this work, we propose privacy filtering at realisation level, design one such privacy filter, and prove that it guarantees (ϵ, δ)-differential privacy. Contrasting prior approaches, the filter tracks realised leakage, rather than composing worst case per mechanism parameters. It can be applied to arbitrary mechanisms, whether they be independent or adaptive, with discrete or continuous outputs that may have differing supports. This extends beyond settings where Rényi divergence is well behaved, as required by RDP filters. This work demonstrates that realisation-level accounting provides a previously unexplored axis for utility improvement, by exploiting knowledge of the realised leakage. The main implementation challenge of the filter is in checking the condition δ̂i+1 > δ̃. Whilst analytical computation is perfectly feasible in simple settings, efficient approximations or bounds may be required for more elaborate mechanisms. Recall the definition (3) of δ̂i+1 and the equivalent check (4). Given a triple (x, x′ , ri+1 ), let M denote the number of basic operations required to determine whether Px Yi ∈ Ỹi (δ̃) | ri , y i−1 ≥ 1 − θ. Then, the number of basic P operations required to check δ̂i+1 > δ̃ is at most C = x∈X N (x)|Ri+1 |M , where N (x) counts the number of neighbours of database x. In the i.i.d. Gaussian example of Sec. V-B, M = 1 and C = 2. In general however, this bound can be much larger. For complex, non-Gaussian mechanisms, the probability calculations may require Monte Carlo simulation with large sample sizes, which can substantially increase M . For the RDP filter, the main source of computational
complexity lies in evaluating ρi (α) for each mechanism, where ρi (α) must bound the Rényi divergence of order α for all pairs of neighbouring datasets. This is fundamentally hard when the divergence itself admits no closed-form expression. Existing filters face a similar scaling issue to ours, as their bounds must hold over all neighbouring datasets. This can become costly as the domain grows, especially for complex mechanisms. Our filter additionally requires bounds to hold for all requests in Ri+1 . Unlike datasets, this set may be controlled by the data handler, who can reject other requests and safely continue. The effect of this strategy on utility warrants further study, particularly in adaptive learning settings where requests may be difficult to predict. Another challenge in implementing our realisation-level filter is parameter selection. The filter requires prior specification of (δ̃, θ, N ). Proposition 1 reveals that, in the i.i.d. Gaussian setting, the stopping condition is equivalent to the accumulated leakage exceeding a threshold κ. In fact, this extends to general i.i.d. mechanisms for suitable κ. Thus, for fixed N , maximising κ over (δ̃, θ) yields the maximum stopping time for any transcript. General optimal selection of filter parameters remains open. One possible approach is to approximate the sequence of mechanisms by an i.i.d. model, and select parameters accordingly. This may offer useful intuition and a principled alternative to arbitrary parameter selection. However, for mechanisms exhibiting strong dependence, an i.i.d. model may be inaccurate. Exploring filters that combine realisation-level accounting with Rényi-based composition is a promising direction for future work. Rényi differential privacy is known to provide very strong composition guarantees for light-tailed mechanisms, such as those based on Gaussian noise, and existing RDP filters leverage this property to achieve high utility for some common mechanisms. The simulation results in this work illustrate that realisation-level accounting can yield significantly improved stopping time behaviour, even over RDP-based methods, by exploiting knowledge of realised privacy loss. In summary, our work provides evidence that realisation-level accounting provides a complementary path to higher utility. A PPENDIX A P ROOF OF P ROPOSITION 1 For i.i.d. Gaussian mechanisms with unit sensitivity, the leakage variables are themselves i.i.d. and Gaussian. In particular, since Yi = r(X) + Zi with Zi ∼ N (0, σ 2 ), it follows that for any neighbouring inputs (x, x′ ), 1 1 ′ , , Li (x, x ) ∼ N 2σ 2 σ 2 under the distribution Px of Yi . Recall from (4) that at step i, Algorithm 1 decides to release yi+1 if inf ′ Px Yi ∈ Ỹi (δ̃) | ri , y i−1 ≥ 1 − θ, x∼x ri+1 ∈Ri+1
where Yi (δ̃) is defined as n o yi : Px Li+1 (x, x′ ) > ϵ − l(i) (x, x′ ) | ri+1 , y i ≤ δ̃ . (16)
Fig. 2. Stopping time survival P (T ≥ t) of mechanism-level privacy filters compared with our realisation-level privacy filter.
Let us first examine Ỹi (δ̃), dropping the explicit dependencies on x ∼ x′ for brevity. The inner probability in (16) is 2 (i) (i−1) (i) Px Li+1 > ϵ − l | l =1−Φ σ ϵ−l − , σ (17) where we have used the fact that mechanisms are i.i.d. to drop the conditional dependence on ri+1 and y i . Using (17), we find that the condition yi ∈ Ỹi (δ̃) is equivalent to 1 1 l(i) ≤ ϵ − 2 − Φ−1 (1 − δ̃). 2σ σ Substituting this back into the stopping rule (4) yields the following condition for the release of yi+1 : 1 −1 1 (i−1) (i) inf Px L ≤ ϵ − 2 − Φ (1 − z) | l ≥ 1 − θ. x 2σ σ (18) Expanding the Gaussian probability on the left hand side and using L(i) = l(i−1) + Li yields 1 1 −1 Φ (1 − δ̃) + Φ−1 (1 − θ) , l(i−1) ≤ ϵ − 2 − σ σ ∀x ∼ x′ , which gives Proposition 1. A PPENDIX B S TOPPING T IME C OMPUTATION FOR M ECHANISM -L EVEL F ILTERS Let Ta , Tav and TRDP represent the stopping times for the additive, advanced, and RDP filters respectively, as outlined in Sec. II-A. Recall that each mechanism Mi is i.i.d. Throughout this section, we use ϵi as shorthand for ϵi (δi ), which is the smallest ϵi for which Mi is (ϵi , δi )-DP. Then, the stopping time for the additive filter is ) ( ϵ Ta = max t ∈ N0 : min ϵi ≤ . t δi ≤ δt
Similarly, the stopping time for the advanced filter is f (δi , ϵi , δ ′ ) ≤ ϵ , Tav = max t ∈ N0 : min 2tδi δi ,δ ′ :δ ′ + ϵ ≤δ ϵi e i
where we use f (δi , ϵi , δ ′ ) to denote the expression in (2). Finally, for the RDP filter applied to Gaussian mechanisms, the parameter ρi (α) admits a closed form expression [4]. In particular, our example with unit sensitivity yields ρi (α) = 2σα2 . Therefore, the stopping time for the RDP filter is log 1δ tα TRDP = max t ∈ N0 : min + ≤ϵ . α>1 2σ 2 α−1 In the implementation of the simulation in Sec. V-B, Ta , Tav and TRDP were computed numerically. R EFERENCES [1] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” in Advances in Cryptology - EUROCRYPT 2006, S. Vaudenay, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 486–503. [2] C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and differential privacy,” in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 51–60. [3] C. Dwork and A. Roth, The Algorithmic Foundations of Differential Privacy, ser. Foundations and Trends in Theoretical Computer Science. Now Publishers Inc., 2014, vol. 9, no. 3–4. [4] I. Mironov, “Rényi differential privacy,” in 2017 IEEE 30th Computer Security Foundations Symposium (CSF), 2017, pp. 263–275. [5] A. Koskela, J. Jälkö, and A. Honkela, “Computing tight differential privacy guarantees using FFT,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2020, pp. 2560–2569. [6] A. Koskela, J. Jälkö, L. Prediger, and A. Honkela, “Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using FFT,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 3358–3366. [7] W. Alghamdi, J. F. Gomez, S. Asoodeh, F. Calmon, O. Kosut, and L. Sankar, “The saddle-point method in differential privacy,” in International Conference on Machine Learning. PMLR, 2023, pp. 508–528.
[8] R. Rogers, A. Roth, J. Ullman, and S. Vadhan, “Privacy odometers and filters: Pay-as-you-go composition,” 2021. [Online]. Available: https://arxiv.org/abs/1605.08294 [9] V. Feldman and T. Zrnic, “Individual privacy accounting via a renyi filter,” Advances in Neural Information Processing Systems, vol. 34, pp. 28 080–28 091, 2021. [10] M. Lécuyer, “Practical privacy filters and odometers with rényi differential privacy and applications to differentially private deep learning,” arXiv preprint arXiv:2103.01379v2, 2021. [11] R. Rogers, A. Roth, J. Ullman, and S. Vadhan, “Privacy odometers and filters: pay-as-you-go composition,” in Proceedings of the 30th International Conference on Neural Information Processing Systems, ser. NIPS’16. Red Hook, NY, USA: Curran Associates Inc., 2016, p. 1929–1937.