arXiv CSopen access

Near-Optimal Generalized Private Testing

NEAR-OPTIMAL GENERALIZED PRIVATE TESTING

arXiv:2605.21601v1 [cs.DS] 20 May 2026

ANAMAY CHATURVEDI1 , MONIKA HENZINGER1 , AND JALAJ UPADHYAY2 A BSTRACT. One of the most well-studied problems in differential privacy (DP) is private threshold testing, in which there is a sequence of real values (vt )t≥1 , and the goal is to identify the first value which exceeds a given threshold τ. The sparse vector technique is a privacy accounting technique that addresses this problem under the promise that the values have bounded Lipschitz sensitivity, and it is ubiquitous in the DP literature. In this paper, we introduce new algorithms, lower bounds and applications for the generalized version of this problem. The generalized private testing problem was introduced by Liu and Talwar (STOC 2019). There is a private dataset X, and a sequence of black-box ε t -DP mechanisms Mt taking values in {+1, −1}. The goal is to identify the first mechanism whose success probability pt = Pr[Mt ( X ) = +1] exceeds a given acceptance threshold p∗ ∈ (0, 1), while achieving an ε-DP guarantee. In other words, the Lipschitz requirement on real-valued inputs in the standard setting is replaced by a stability guarantee in terms of DP itself. The accuracy of a solution for this problem can be characterized by the gap between the acceptance threshold p∗ , and a corresponding rejection threshold p̄, such that with probability 1 − β for all t ≥ 1, if pt ≤ p̄, then the mechanism Mt is rejected, and if pt ≥ p∗ , it is accepted. In this paper, we introduce a new DP mechanism called the Generalized Thresholding Mechanism (GTM). For any ε > 0 and any sequence of approximate (ε t , δt )-DP input mechanisms Mt , the GTM achieves a pure ε-DP guarantee. For any θ > 0, γ ∈ (1, 2], and β ∈ (0, 1), it achieves a rejection threshold of max( p∗ /γΛt , 1 − γΛt (1 − p∗ )) − δt /ε t for Λt = (5t ln3 (t + 2))(2+θ )ε t /ε (4/β)(3+θ +2/θ )ε t /ε . With probability

1 − β, the number of evaluations of Mt is at most O (ln(t/β)/(γ − 1)2 ) · max Λt /p∗ , (1 − p∗ )−1 for all t ≥ 1. We also prove lower bounds which show near-optimality of our accuracy and sample complexity guarantees. We illustrate the power of the GTM by giving a black-box reduction for private optimization from the continual observation (CO) setting to the batch setting. This gives us the first algorithms for a large class of maximization problems in the CO setting. Our mechanism permits an adaptive choice of acceptance thresholds ( p∗t )t≥1 (replacing a uniform choice of p∗ with an adaptive choice of p∗t ). This functionality addresses in part a challenge mentioned in prior work on using generalized private testing for hyperparameter optimization (Papernot and Steinke (ICLR 2022)).

1 Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria.

{anamay.chaturvedi, monika.henzinger}@ist.ac.at. 2 Rutgers University, USA. [email protected].

i

1. I NTRODUCTION Two fundamental problems in the study of differential privacy (DP) are private selection and private testing. The private selection problem asks the analyst to pick the best item from a given ground set based on a score function. The private testing problem asks the analyst to pick the first item from a given stream whose score exceeds a given target score. These problems are well understood when the function is known to have bounded Lipschitz sensitivity, and their algorithmic solutions, the exponential mechanism [MT07] and the above threshold mechanism [DNR+ 09], are some of the most widely used mechanisms in the design of DP mechanisms. A fundamental limitation to what can be achieved for private selection and testing for worstcase inputs is the requirement that the score functions have known bounded global Lipschitz sensitivity over the dataset space. In seminal work, Liu and Talwar [LT19] consider a generalized formulation of these problems: a sequence of ε 1 -DP mechanisms, (Mt )1≤t≤T , is given as input (in black-box manner), such that each mechanism’s outputs are items in the ground set along with associated scores (in selection), or a score for the mechanism itself (in testing). The analyst generates an output which is an item in the selection problem and accept/reject in the testing problem. This generalization relaxes the Lipschitz requirement on the score function to distributional stability for a randomized mechanism in the sense of DP itself. Liu and Talwar proposed mechanisms that evaluate every mechanism Mt multiple times and output a value computed from the aggregate of evaluations, but incur privacy loss that is invariant in the number of evaluations. This approach offers significantly better privacy-utility trade-offs than using composition theorems [DR14], especially for tasks like private hyperparameter optimization. Mechanisms for generalized private selection have been studied and applied extensively in the literature. Following the work of Liu and Talwar [LT19], Papernot and Steinke [PS21], and Cohen, Lyu, Nelson, Sarlós, and Stemmer [CLN+ 23] gave improved mechanisms that for ε 1 -DP inputs, (Mt )1≤t≤T , achieved privacy loss of (2 + θ )ε 1 for any fixed θ > 0. A lower bound argument in [LT19, Appendix D] indicates that under a reasonable notion of accuracy, this is the best privacy guarantee achievable. In this paper, we study generalized private testing. Formally, we are given a private dataset X drawn from a dataset universe X equipped with an arbitrary symmetric notion of adjacency, a target success probability p∗ ∈ (0, 1), and a public sequence of black-box ε t -DP mechanisms (Mt )t≥1 with range {−1, +1} such that pt = Pr[Mt ( X ) = +1]. The goal of generalized private testing is that the mechanism should correctly halt and output the first mechanism Mt for which pt ≥ p∗ , while achieving an ε-DP guarantee. The accuracy of a mechanism for generalized private testing is described in terms of a rejection threshold p̄ < p∗ , such that, with high probability for all t ≥ 1, if pt ≤ p̄ then the mechanism does not halt, and if for some t ≥ 1, pt ≥ p∗ , it halts. For pt ∈ ( p̄, p∗ ), the mechanism may halt or continue arbitrarily. Ideally, we would like p̄ to be as close to p∗ as possible. [LT19] gave a (ε, δ)-DP mechanism that achieves p̄ ≈ p∗ ( β2 /T )12ε 1 /ε , where ε and δ are the privacy loss parameters of the testing mechanism, β is a given failure probability, and T is the number of input mechanisms. [CLN+ 23] showed how to unify the generalized private selection and testing problems into one framework by introducing correlated random dropping. Ghazi, Kamath, Knop, Kumar, Manurangsi and Zhang [GKK+ 25] gave similar algorithms for generalized private selection and testing but with new accuracy guarantees for selection in the ex-post setting [WRL+ 19]. In contrast with [LT19], both of these works provide a pure DP mechanism when the input mechanisms are also pure DP, and an approximate DP mechanism for approximate DP input mechanisms. However, while the testing mechanism in [LT19] can achieve any output privacy loss parameter ε regardless of the input privacy loss parameter ε 1 , [CLN+ 23, GKK+ 25] require that ε > 2ε 1 and do not state an accuracy guarantee along the lines of [LT19] for generalized testing. 1

We show in Section 9.3 that approaches based on correlated random dropping cannot achieve a rejection threshold better than p̄ ≈ p∗ ( β/T ); this is asymptotically worse than [LT19]. To be more precise, regardless of the choice of privacy parameters, p∗ / p̄ increases with T/β. In contrast, for the mechanism of [LT19], p∗ / p̄ can be reduced to ( T/β)c for any arbitrarily small constant c. To summarize, existing mechanisms for generalized private testing have (1) either a large constant factor coefficient in the exponent of β/T in p̄ (i.e, p̄ ≈ p∗ ( β2 /T )12ε 1 /ε ), restrictive privacy analyses (i.e., achieving only approximate privacy and only for pure DP inputs), and a large number of evaluations of each mechanism Mt [LT19]; or (2) tight privacy guarantees, but with an accuracy that scales poorly with T/β, regardless of the choice of ε [CLN+ 23]. Further, while mechanisms for generalized private selection are used extensively, mechanisms for generalized private testing have not seen many applications. In this paper, we address these gaps by introducing new algorithms, lower bounds, and applications for generalized private testing. The rest of this section is organized as follows. We give a formal problem statement in Section 1.1 followed by our contributions in Section 1.2, applications in Section 1.3, a high-level technical overview of our proof in Section 1.4, and practical implications of our mechanism in Section 1.5. 1.1. Problem description. Let X denote the dataset universe, equipped with a fixed symmetric adjacency relation; we call X, X ′ ∈ X neighboring if they are adjacent. All results hold for any choice of adjacency relation. We consider a sequence of binary mechanisms Mt : X → {−1, +1} for t = 1, 2, . . ., where each Mt satisfies (ε t , δt )-differential privacy, i.e. for all neighboring X, X ′ and all v ∈ {−1, +1}, Pr[Mt ( X ) = v] ≤ eε t Pr[Mt ( X ′ ) = v] + δt . We also consider a sequence of datasets ( Xt )t≥1 and privacy parameters (ε t , δt )t≥1 , which, along with the mechanisms (Mt )t≥1 , may be chosen adaptively based on prior public outputs, subject only to the constraint that Mt is (ε t , δt )-DP. We write pt := Pr[Mt ( Xt ) = +1] for the success probability at step t. A direction st ∈ {−1, +1} and a target threshold p∗t ∈ (0, 1) are associated with each step. The target regime at step t is { pt : st pt ≥ st p∗t }. In other words, when st = +1, then we want a tester to halt when pt ≥ p∗t , and when st = −1, we want the tester to halt when pt ≤ p∗t . Definition 1 (Generalized private tester). Fix a global privacy budget ε > 0. A generalized private tester is a randomized procedure that, at each step t, interacts with the dataset Xt only through i.i.d. samples from Mt ( Xt ). It draws a (potentially random) number of independent evaluations, observes their outcomes, and outputs at ∈ {−st , st }, where at = st denotes halting and at = −st denotes continuation. The transcript is ( a1 , . . . , a T ) where T is the halting step (a T = s T , at = −st for t < T), or the infinite sequence (−s1 , −s2 , . . .) if the tester never halts. The tester must be ε-DP, i.e. for every t ≥ 1, every pair of dataset sequences ( X j ) j≥1 , ( X j′ ) j≥1 with X j , X j′ neighboring for all j, and every measurable E ⊆ {−1, +1}t ,     Pr ( a1 , · · · , at ) ∈ E ≤ eε Pr ( a1′ , · · · , a′t ) ∈ E . Definition 2 (Accuracy and sample complexity). We say that a generalized private tester when run with a failure probability of β and target thresholds ( p∗t )t≥1 achieves rejection thresholds ( p̄t )t≥1 if with probability 1 − β for all t ≥ 1, st pt ≤ st p̄t ⇒ at = −st (no false positives), and st pt ≥ st p∗t ⇒ at = st (no false negatives). The sample complexity of a generalized private tester is the number of times it evaluates Mt on the dataset Xt . 2

This problem setting is a mild reformulation of the version introduced by [LT19]. In prior work, the notion of β-global accuracy was considered only by [LT19], and all work implicitly set st = +1 for all t ≥ 1, i.e. the Above Threshold formulation. 1.2. Our contributions. Our main contribution is a new mechanism for generalized private testing. Theorem 3 (Upper Bound, Informal version of Theorem 21 and Corollary 25). Given a sequence of target thresholds ( p∗t )t≥1 , a privacy parameter ε > 0, a tuning parameter θ > 0, a failure probability β, a ratio parameter γ ∈ (1, 2], and a stream of mechanisms and dataset pairs (Mt , Xt ) where Mt is (ε t , δt )DP, there is an ε-DP mechanism called the Generalized Thresholding Mechanism (GTM, Algorithm 1). For all t ≥ 1, define Λt = (5t ln3 (t + 2))(2+θ )ε t /ε (4/β)(3+θ +2/θ )ε t /ε and the rejection thresholds   ∗ pt ∗ , 1 − γ Λ t (1 − p t ) . p̄t := max γ Λt Then, with probability 1 − β over the randomness of the GTM, for all t ≥ 1, the following statements hold: (1) If pt ≥ p∗t + δt /ε t , then the mechanism halts. (2) If pt ≤ p̄t − δt /ε t , then the mechanism continues. (3) The number of evaluations of the mechanism Mt at step t is Nt drawn from a Poisson distribution Po(λt ) for λt ≤ Ãt · wt , where !! (4/β)(1+2/θ )ε t /ε 1 ln(t/β) Ãt := O · max , ( γ − 1)2 p∗t 1 − p∗t and wt := eε t η2,t . wt is distributed as a Pareto distribution Par(σt ) with σt := ε/(ε t (θ + 2)), independently across steps. We see that for a generic value of p∗t , Theorem 3 achieves the rejection threshold p̄t ≥ p∗t · Θ̃(t−(2+θ )ε t /ε β(3+θ +2/θ )ε t /ε ). Our sample complexity is randomized,  but in Lemma 22 we show that with probability 1 − β, for 

all t ≥ 1, Nt ≤ (γ−1)2 max Λp∗t , 1−1p∗ . Further, in the setting where ε t = ε 1 < ε/(2 + θ ) for all t t t ≥ 1, the amortized sample complexity obeys the bound: " !!# 1 T ε (4/β)(1+2/θ )ε 1 /ε 1 Pr , Nt ≥ Õ · max < β. T t∑ ε − (2 + θ ) ε 1 p∗ 1 − p∗ =1 ln(t/β)

Comparison with [LT19]. The exponent of t can be driven down to (2 + θ )ε t /ε for any θ > 0 at the cost of a reciprocally larger exponent of β, but the coefficients of both t and β are simultaneously smaller than those achieved in [LT19], for which Λt = ( T/β2 )12ε t /ε . The ratio between the thresholds is large but finite for any choice of ε, and on studying the max expression for p̄t in Theorem 3 we see that the gap between the thresholds | p∗ − p̄t | reduces to 0 as the success threshold p∗ approaches 0 or 1; this is the case for both our work and [LT19], but more rapidly in our case since our value of Λt is smaller. Apart from the improvement in the exponent, the more significant points of comparison between our works are the privacy guarantees and sample complexities. Our mechanism guarantees pure DP regardless of whether (Mt )t≥1 are pure or approx-DP, while [LT19] requires (Mt )t≥1 to be pure DP and their mechanism achieves only approximate DP guarantees. ( T/β)12ε 1 /ε ln( T/δ)

[LT19] have a per-round sample complexity of ≈ min{ p∗ ,1− p∗ } . As described above, our sample complexity obeys a high probability bound with a smaller exponent, and when ε > (2 + θ )ε t , the amortized sample complexity scales only logarithmically with the time-step index, and incurs a (4/β)(1+2/θ )ε 1 /ε dependence on the failure probability β. 3

TABLE 1. Comparison of accuracy and sample complexity for generalized private testing. Expressions suppress lower-order terms. For our results, θ > 0 and γ ∈ (1, 2] are free parameters. For [LT19], ε 0 ∈ (0, 1) is an auxiliary parameter. † [LT19]’s guarantee is conditional on halting at step t and does not guarantee halting at pt = p∗ , but at a value somewhat larger than p∗ .

Privacy Guarantee Requirement Noise penalty, Λt Rejection threshold, p̄t

Sample complexity, Nt

Our results

Cohen et al. [CLN+ 23]

Liu–Talwar [LT19]

(Theorem 21)

(Proposition 48)

(Theorem 46)

pure ε-DP

pure ε-DP

(ε, δ)-DP

ε>0  (1+2/θ )ε 1 /ε (2+θ )ε 1 /ε 1 t β β  ∗  pt max , 1 − γΛt (1 − p∗t ) γΛt

ε > 2ε 1 β1+ε 1 /(ε−2ε 1 )

ε > 0, finite T  12(ε 1 +ε 0 )/ε t † β2

p∗ Λt

p∗ † Λ t (1 − p ∗ ) + p ∗

ln(1/β) p∗ βε 1 /(ε−2ε 1 )

( T/β)12(ε 1 +ε 0 )/ε ln( T/δ) ε20 min{ p∗ , 1 − p∗ }

ln(t/β) max ( γ − 1)2



1 Λt , p∗t 1 − p∗t



t

Comparison with [CLN+ 23]. [CLN+ 23] do not state their accuracy bound along the lines of [LT19] (and the one used in this work). Therefore, to make a fair comparison, in Proposition 48, we derive an accuracy guarantee for their mechanism. It has a similar multiplicative relationship between p∗ and p̄ but with two caveats: (1) the rejection threshold is at best p̄t = βp∗ /t, regardless of the choice of ε t and ε; and (2) the gap between the thresholds vanishes when p∗ approaches 0, but not when it approaches 1. Further, they require that ε > 2ε 1 . Although our analysis does not preclude a more refined analysis, we prove a lower bound (Corollary 51) showing that the factor of β/t is unavoidable for their algorithm. The work of [GKK+ 25] uses similar algorithmic techniques for generalized private testing and selection, and when applied to this problem, suffers the same β/t slack (see Section 9.4). For ease of comparison, we tabulate accuracy and sample complexity bounds in Table 1. We compare the rejection thresholds described in terms of the noise penalty (which captures the impact of privatizing perturbations), the rejection threshold achieved, and the sample complexity. For a fair comparison we mention only our high-probability sample complexity bound above, but as mentioned before, our amortized scaling is significantly better. We complement our upper bound on the generalized private testing with the following lower bound on the accuracy of any generalized private tester. Theorem 4 (Lower Bound, Informal version of Corollary 30 and Theorem 31). Given a target threshold p∗ , a stream length T, an input privacy parameter ε 1 > 0, output privacy parameters ε > 0 and δ ∈ [0, 1) and a failure probability β, define δ′ := δ/(eε − 1), and suppose β + δ′ < 1/2. Define ε /ε Λ T = e−2ε 1 · ( T/(4( β + Tδ′ )( β + δ′ ))) 1 . Suppose A is any generalized private tester that achieves the rejection threshold p̄. Then: (1) If p∗ , p̄ ≤ 1/2, then p̄ ≤ p∗ /Λ T . (2) If p∗ , p̄ ≥ 1/2, then p̄ ≤ 1 − Λ T (1 − p∗ ). (3) If p̄ < 1/2 < p∗ , then p̄ ≤ 1/(4(1 − p∗ )Λ T ). 4

Further, we show that any generalized private tester for a given target threshold p∗ < 1/2 with failure probability at most β must satisfy: E[ Nt ] = Ω(1/( p∗ · βε 1 /ε )). When p∗ approaches 0 or 1, the functional form of our upper and lower bounds is identical: (i) p̄t = p∗t /(γΛt ) when p∗ is close to 0 compared with p̄ ≤ p∗t /Λ T in the lower bound and (ii) p̄t = 1 − γΛt (1 − p∗t ) compared with 1 − Λ T (1 − p∗t ) in the lower bound. In these domains, the comparison reduces to the gap between γΛt and Λ T ; we note that γ ≤ 2 so this factor has limited impact. The lower bound for pure DP inputs and approximate DP outputs still requires that Λt ≈ ( T/(( β + Tδ)( β + δ)))ε 1 /ε ≈ ( T/β2 )ε 1 /ε as δ ≪ β. If we have ε t = ε 1 , our upper bound achieves a noisy penalty term Λt = t(2+θ )ε t /ε β−(3+θ +2/θ )ε t /ε . The gap between the upper and lower bounds is thus reduced to small constants in the exponents of tε t /ε and βε t /ε in all privacy settings. We can reduce the gap in the exponent of t to a near-2 factor at the cost of a larger exponent on βε t√/ε ; conversely, when we minimize the exponent of βε t /ε , then we have that √ Λt ≈ β−(3+2 2)ε t /ε t(2+ 2)ε t /ε . Our upper and lower bounds show that solving generalized private testing necessitates a loss in accuracy captured by a Λ T factor, that scales essentially as ( T/β)cε t /ε , for some constant c, and ′ an average sample complexity that scales as (1/p∗ ) βc ε 1 /ε for some constant c′ . The lower bounds show that it is impossible to get rid of these polynomial in t and β factors, but that the impact of this factor in terms of the absolute gap between the acceptance and rejection thresholds p∗ and p̄ vanishes as p∗ approaches 0 or 1. Our upper bound suggests another way of mitigating the Λt -factor in the gap between p∗ and p̄, which is to let the ratio between the privacy parameters ε/ε t scale as ln(t/β). We formalize this as an ex-post guarantee. Definition 5 (Ex-post privacy [WRL+ 19]). Given a randomized algorithm A : X → Y , define the ex-post privacy loss of A on o ∈ Y to be a function ε̃ : Y → R≥0 if for all neighboring X, X ′ ∈ X , Pr[A( X ) = o ] ≤ eε̃(o) Pr[A( X ′ ) = o ]. Theorem 6 (Ex-post setting, Informal statement of Theorem 23). In the setting of Theorem 3, define Λ0 = e2 (4/β)ε 1 /ε . For all t ≥ 1, Algorithm 1 suffers ex-post privacy loss at most ( ε + ε t ln(t/β) if at = st ε̃(( a1 , . . . , at )) = ε if at = −st . The accuracy and high-probability sample complexity guarantees are identical to that of Theorem 3, with Λt replaced by Λ0 . 1.3. Applications. We have seen that in Algorithm 1, one can reduce this loss in accuracy Λt to any arbitrarily small constant CΛ > 1 in two ways: (i) by allowing the output privacy loss to scale logarithmically with t/β, i.e. setting ε = ε t ln(t/β), or (ii) by forcing the input privacy guarantees to become more restrictive, setting ε t = ε · 1/ ln(t/β). The former guarantee serves as a way to solve the testing problem with a constant gap between the rejection threshold and incurring privacy loss scaling logarithmically with the length of the stream. In comparison, a fixed choice of ε and desired constant rejection threshold of p̄ would eventually cause false positives to occur at a constant rate; the privacy loss incurred by each false positive √ must be accounted for via basic or advanced composition, leading to a net privacy loss of ≈ tε t for long streams with an approximate DP guarantee. In contrast, by committing to a logarithmically scaling privacy loss, we are guaranteed to not incur any false positives with high probability and solve the same testing problem with a pure DP guarantee with privacy loss 5

= ε 1 ln t. The benefits of the latter guarantee, i.e. when ε t = Θ(ε/ ln(t/β)), are best illustrated by our next contribution that we discuss now. Reduction from Optimization in the Continual Observation setting to the Batch setting. Over the past few years, the continual observation (CO) model of differential privacy [DNPR10] has received a lot of interest. Unlike the standard batch setting, where the entire dataset X is known a priori, in the CO setting, the data is constantly modified by a stream of updates, with the dataset after the t-th update denoted by Xt . In the CO setting a solution Yt must be output after every update, and the privacy requirement is that the entire output stream (Yt )t≥1 is differentially private with respect to sequence of datasets seen in the input ( Xt )t≥1 . Dwork, Naor, Pitassi, and Rothblum in their seminal work [DNPR10] posed a question whether the existence of a DP algorithm for a problem in the batch setting implies the existence of a DP algorithm in the continual observation setting. They [DNPR10, Section 6] proposed an approach in which a mechanism in the CO setting maintains and repeatedly outputs a fixed solution. It modifies the output only when it no longer serves as a good solution for the updated dataset. Detecting when the prior solution is no longer of adequate quality is a threshold monitoring problem: at each time step, recomputation is triggered when the test passes and indicates that the function has changed significantly. By trading off some accuracy on average, over the length of the entire stream, one can achieve superior trade-offs between accuracy and privacy. In the standard private testing setting, the sparse vector technique (SVT) is used to solve threshold monitoring efficiently when monitored function has bounded Lipschitz sensitivity. Unfortunately, the quality of the solutions tested by the CO scheme described above admits no tractable Lipschitz bound in general, and none of these privacy accounting techniques apply. This limits the scope of the general technique introduced by [DNPR10]. We give a brief overview of how our mechanism for generalized testing allows us to extend this reduction for a broad class of problems, and we refer the readers to Section 7 for more detail. When a mechanism for an optimization problem exists in the batch setting, we can circumvent the bounded Lipschitz requirement of [DNPR10] as follows. Rather than attempting to directly monitor the optimal utility OPTt at time t, we use a black-box batch DP algorithm A(·). At each time step, we give the GTM query access to A( Xt ) to test whether the quality of solutions generated by A( Xt ) is significantly better compared to the quality of the previous most recently generated output. More precisely, let f : X × Y → R be a maximization problem, which for a given dataset X asks for argmaxY ∈Y f ( X, Y ); with this notation OPTt = maxY ∈Y f ( Xt , Y ). Let A be an algorithm that is ε 1 -DP for any ε 1 > 0, and such that for Y ← A( X ), with probability 1 − β A , f ( X, Y ) ≥ αOPTt − E A (ε 1 ) for some multiplicative approximation α ∈ (0, 1) and additive error E A (ε 1 ) ≥ 0. Our reduction gives an algorithm in the continual observation setting that for any ε < 1, with probability 1 − O( β), for all t ≥ 1, generates a sequence of outputs (Yt )t≥1 such that !  ! κε 1 ln3 (t/β) αOPTt − EA −O 1 + ln . f ( Xt , Yt ) ≥ 1+κ κε 1 − βA ln2 (t/β) Further, the total number of evaluations of A at time-step t is only O(ln(t/β)). The fact that we only need the batch algorithms to be differentially private, and not fulfill some more restrictive Lipschitz bound constraint, gives us significantly more flexibility in using algorithms that apply in the batch setting for constructing new ones in the CO setting. Another key feature of our generalized threshold mechanism that makes this reduction effective is that, when we use the batch DP algorithm with ε t < ε/ ln(t/β) (we set ε t < ε/ ln2 (t/β) for technical reasons), the ex-post accuracy guarantee ensures that the noise penalty Λ0 is bounded by a universal constant independent of t, so the per-step accuracy of each threshold test does 6

TABLE 2. Application of Theorem 42 to batch DP submodular maximization algorithms. OPT: batch optimum; OPTt : CO optimum at time t; k: cardinality or matroid rank constraint; κ, η > 0: user-defined parameters; β: failure probability. Monotone/non-monotone refers to argument-monotonicity; our framework additionally requires data-monotonicity. For in-expectation batch guarantees, Corollary 44 is applied with small constant c > 0. Work, Setting

Batch Guarantee

CO Guarantee (Ours)

[MBKK17] Monotone, (ε, δ)-DP, k-Card.

(1− 1e )OPT − Õ k ε ln m ln 1δ

[RY20] Monotone, (ε, δ)-DP, k-Card.

(1− 1e )OPT − Õ kε3 m ln m

[CNZ21] Decomp. non-mon. (ε, δ)-DP, k-Card.

k ln m ln 1δ ( 1e −η )OPT − Õ ηε

1/e−η 3 t k 1 1+κ OPTt − Õ ηκε ln β ln m ln δ

Decomp. non-mon. (ε, δ)-DP, k-Matroid

k ( 1e −η )OPT − Õ ηε ln m ln 1δ

1/e−η 3 t k 1 1+κ OPTt − Õ ηκε ln β ln m ln δ

[GKK+ 24] Decomp. monotone ε-DP, k-Card., η ∈(0, 1)

(1− 1e −η )OPT − O

k ln m/β
ε

1−1/e−η k OPTt − Õ κε ln3 βt ln m 1+κ β

Decomp. monotone ε-DP, k-Matroid, η ∈(0, 1)

(1− 1e −η )OPT − O

k ln m/ηβ
ε

1−1/e−η k m ln3 βt ln ηβ OPTt − Õ κε 1+κ

3/2

7

3 1−1/e k3/2 1 1+κ OPTt − Õ κε ln t ln m ln δ

6 1−1/e k7 1+κ OPTt − Õ κε3 m ln m ln t

not degrade over time. This implies that we can invoke the batch algorithm at each step with a constant failure probability β A , rather than one that decays with the stream length. This timeindependent failure probability requirement even allows us to adapt batch algorithms that provide only in-expectation accuracy guarantees, rather than high-probability bounds on accuracy. As an in-expectation accuracy bound of the form E[ f ( X, A( X ))] ≥ α · OPT( X ) − E A implies a bounded constant failure probability (see Lemma 33), such algorithms can be plugged directly into the reduction. In other words, there is no accumulation of the failure probabilities of the invocations of the batch algorithm. Our reduction applies to any bounded-sensitivity, data-monotone maximization problem, and yields the first DP algorithms under continual observation for several fundamental problems, including submodular maximization under cardinality and matroid constraints, weighted densest subgraph, and Max-Cut. Crucially, the invocations of the batch algorithm in the t-th time-step 2 occur with √ multiplicative privacy parameter set to equal ε t = ε/ ln (t/β); this is in stark contrast with the t scaling needed via a direct application of advanced composition. In Table 2, we cover some examples to illustrate the benefits of these flexibilities, and direct the reader to Section 8 for a more complete treatment. 1.4. Technical Overview of the Generalized Thresholding Mechanism. The starting point of our approach is that any mechanism for generalized private testing needs to evaluate Mt ( Xt ) a (potentially randomized) Nt number of times to gain information about pt , where pt = Pr[Mt ( Xt ) = +1]. The number Kt of +1 outputs of these evaluations should be a sufficient statistic to reason 7

about whether Mt ( Xt ) should be accepted or rejected. The problem then reduces to defining (i) how to pick Nt ; and (ii) for what values of Kt should one accept Mt ( Xt ), while ensuring a tight privacy-accuracy trade-off. Achieving Privacy, Step 1: Poissonized sampling. Our first key technical insight is that if we pick Nt ∼ Po(λt ) for mean parameter λt , then Kt ∼ Po(λt pt ) as a consequence of Poisson thinning. Achieving Privacy, Step 2: Randomizing λt . Next, we perturb λt just enough to obfuscate pt and e−ε t pt , which in turn allows us to use a coupling argument for the privacy proof similar to the proof of the SVT. To perturb λt , let it be a function of a random variable Z. Then Kt ∼ Po(λt (z) pt ), where z is the value assumed by Z, and the algorithm decides to stop if Kt > ct for a suitably chosen threshold ct . For all t ≥ 1, p′t = Pr[Mt ( Xt′ )] where Xt′ is some dataset neighboring Xt . As we are guaranteed that pt ≥ e−ε t p′t , we pick λt (z) such that λt (z) pt ≥ λt (z − 1) p′t . Specifically we choose λt (z) = ρt eε t z , where ρt is a parameter that is needed for the accuracy bound and discussed further below. This is useful as the CDF of the Poisson random variable Kt is non-increasing in λt (z) pt . Thus, for any z, F (ct , λt (z) pt ) ≤ F (ct , λt (z − 1) p′t ), where F (c, ℓ) := Pr A∼Po(ℓ) [ A ≤ c] is the probability that a Poisson random variable with parameter ℓ returns a value less than c. Let at (a′t , resp.) denote the output of the mechanism at time t with input Xt (Xt′ , resp.). We show here the privacy argument for only the first time step, the detailed proof is given in Section 3.1. The probability that the mechanism when started on Xt does not stop in the first time step is Pr( a1 = −1) =

Z ∞ −∞

F (c, λ(z) pt ) f Z (z)dz ≤

Z ∞ −∞

F (c, λ(z − 1) p′t ) f Z (z)dz.

Shifting the variable to u = z − 1 and assuming that f Z (u + 1) ≤ eε f Z (u) upper bounds the previous expression by Z ∞ −∞

F (c, λ(u) p′t ) f Z (u + 1)du ≤ eε

Z ∞ −∞

F (c, λ(u) p′t ) f Z (u)du = eε Pr( a1′ = −1)

( u + 1) ≤ e ε f

To guarantee f Z Z ( u ), we sample a random variable η1 using an exponential distribution with scale 1/ε and could set Z = −η1 . However, for the privacy proof of the halting case and for the accuracy analysis, we need to choose Z in a more refined way, without destroying the crucial property of f Z : Setting λt in this manner allows us to bound the privacy loss by ε for an arbitrarily long sequence of failures, i.e., a1 = · · · = at = −1; however, we need to introduce an appropriately scaled noise at every input, η2,t , to bound the privacy loss to account for at = +1 at some indeterminate time-step t (similar to the coupling argument in the standard private testing setting). We sample η2,t using an exponential distribution with scale 2/ε, i.e., η2,t ∼ Exp(2/ε) and for the coupling argument to work we could set Z = −η1 + η2,t . However, for the purposes of the accuracy analysis, it will be convenient to introduce a constant offset µ1 to have Z be positive with high probability. Formally, let µ1 = (1/ε) ln(3/β) be a high-probability bound on the magnitude of η1 . Then we define Zt := µ1 − η1 + η2,t . Using the tail bound on exponential distribution, we can show that Zt ≥ 0 for all t ≥ 1 with probability 1 − β/3 over η1 ∼ Exp(1/ε). For point (ii) mentioned above, we test Kt ≥ ct for an appropriately chosen ct (see eq. (1)). Since threshold tests Kt ≥ ct are monotonic in the value of Kt , by post-processing, the outcomes of the tests will also be ε-DP. Achieving Tight Accuracy, Step 1: Choosing Base Rate, ρt . Recall that we define λt to equal ρt exp(ε t Zt ) with ρt > 0 and Zt := µ1 − η1 + η2,t and that there are so far no further restrictions on ρt . By the choice of µ1 and since η2,t ≥ 0 unconditionally, we have that with probability 1 − β/3 over the draw of η1 , we have λt ≥ ρt . For the accuracy analysis we also need an upper bound on η2,t for all t. We define a sequence of failure probabilities β t = Θ( β/(t ln3 t)) such that ∑t≥1 β t = 8

β/6. Thus, with probability at least 1 − β/2, it holds that for all t, η2,t ≤ (2/ε) ln(1/β t ) and ρt ≤ λt ≤ Λt ρt with Λt = exp((ε t /ε)(ln(3/β) + ln(1/β t ))). We now reason about how to conduct threshold tests where Nt ∼ Po(λt ) is the number of such tests and Kt ∼ Po(λt pt ) is the number p of +1 outcomes. At a high level, the distribution of Kt has left and right tails roughly λt pt ± 6λt pt ln(1/β t ) with probability at least 1 − 2β t ; both grow monotonically with λt pt . We set ρt := ρ†t /p∗t for appropriately chosen ρ†t . Thus with probability at least 1 − β/2 − β/3 = 1 − 5β/6 for all t it holds that s q † Λ p̄ 6ρ†t Λt p̄t ρ t t † ∗ t Kt ≥ ρt − 6ρ†t ln(1/β t ) for pt ≥ pt and Kt ≤ + ln(1/β t ) for pt ≤ p̄t . p∗t p∗t At a high level, we need to set pt so as to compensate for the magnitude Λt of the privatizing noise exp(ε t Zt ). Setting pt = p∗t /(γΛt ), for some fixed constant γ > 1, allows us to offset the Λt factor and gives the following bound when pt ≤ p̄t : s † 6ρ†t ρ Kt ≤ t + ln(1/β t ). γ γ To summarize, we require as threshold for our test a value of ct such that q q ρ†t /γ + 6(ρ†t /γ) ln (1/β t ) ≤ ct ≤ ρ†t − 6ρ†t ln (1/β t ). (1) Note that, as ρ†t increases, the leading term of both bounds dominates, and for any γ > 1, these bounds become simultaneously satisfiable. Working out the details we get that there is a value ln(1/β )
ρ†t = Θ (γ−1)t2 that suffices. Combining everything together, we arrive at the expression     Λt ln(1/β t ) Λt ln(t/β) ρt = Θ (2) =Θ . p ∗ ( γ − 1)2 p ∗ ( γ − 1)2 The Flipped variant. In the above discussion, we have generalized private testing with the rejection threshold pt = p∗ /γΛt . When p∗ approaches 0, the gap p∗ − pt in absolute terms vanishes, even though p∗ /pt remains γΛt . This is desirable because it means there are few values for pt where we do not have a guarantee on the performance of the mechanism. However, when p∗ is close to 1, then p∗ − pt is large, which is undesirable for the same reason. This suggests the following modification when p∗ is close to 1: instead of running the mechanism as is, we flip each test by running a threshold test on the evaluations of −Mt ( Xt ) with the target threshold 1 − p∗ . Since Pr[M( Xt ) = −1] = 1 − pt , this is the same test as 1 − pt < 1 − p∗ iff pt > p∗ . Now, this is the Below Threshold variant of the Thresholding Mechanism, i.e., the mechanism halts when Kt ≤ ct . Recall that the noise added to ensure privacy is one-sided with different scale (i.e., η1 ∼ Exp(1/ε) and η2,t ∼ Exp(2/ε)). Therefore, to account for the difference in the problem (i.e., Below threshold vs Above threshold), we also need to flip the noise variable: let st denote whether we want the mechanism to halt on acceptance or on rejection, then we define Zt = st (µ1 − η1 + η2,t ). Clearly, this is equivalent to the description above when st = +1. Subtle adjustments are required, but otherwise the mechanism is identical, with the caveat that it must halt when it rejects some stream element. On implementing this modification, the analyst is free to pick whichever variant offers us less error, and, thus, we are able to show that the rejection threshold equals  ∗  pt ∗ p̄t := max , 1 − γ Λ t (1 − p t ) . γ Λt Furthermore, since the variable Zt is negative with high probability for st = −1, this implies that the Poisson mean parameter is deflated by up to a factor of Λt , instead of being inflated. 9

  ln(t/β) In other words, ρt = Θ p∗ (γ−1)2 leading (with a failure probability of at most β/6) to a high probability sample complexity bound of   Λt 1 ln(t/β) max , . Nt = ( γ − 1)2 p∗t 1 − p∗t The first term of the max expression occurs on the direct variant, and the latter occurs on the flipped variant. There is no inflation in the sample complexity via the noise penalty term Λt in the flipped variant. Purification via randomized response. Thus far we have only reasoned about pure DP inputs. To deal with mechanisms Mt ( Xt ) that only fulfill a weaker (ε t , δt )-DP guarantee, we appeal to a black box modification based on randomized response. Each evaluation of Mt ( Xt ) is flipped with probability ϕ = δt /(eε t − 1 + 2δt ) ≤ δt /ε t . We denote this “ϕ−smoothed” mechanism by ft , and its success probability by pet . It is not hard to see that | pt − pet | ≤ δt /ε t ; in other words, M the perturbation to the success probabilities is vanishingly small. The advantage of this ϕ-smoothed mechanism is that it is pure ε t -DP. The key idea here is that if a mechanism with co-domain {+1, −1} is (ε t , δt )-DP, then in some sense the worst privacy loss occurs when for v ∈ {+1, −1}, Pr[Mt ( Xt ) = v] = δt , but Pr[Mt ( Xt′ ) = v] = 0. Clearly such a mechanism cannot be ε-DP for any value of ε. However, if we increase the probability of both outputs by δt , then the ratio of these two outputs changes from being undefined to 2, and the effective privacy loss as measured by the multiplicative privacy parameter changes from ∞ to ln 2. Refining this outline, we get the stated claim. ft ( Xt ), and the bound on | pt − pet | implies that essentially the We can now run Algorithm 1 on M same acceptance and rejection thresholds hold, perturbed by at most a value of δt /ε t . This technique of using randomized response as post-processing to purify approximate-DP mechanisms with finite co-domains is attributed to folklore by [HC22]. The term purification was coined by [LWMW25] to describe the generation of pure DP outputs via randomized post-processing, and they give further generalizations and applications of this approach. 1.5. Discussion on Private Testing vs Selection. A major motivation behind the introduction of generalized private selection and testing in [LT19] was private training of machine learning models. In this section, we discuss potential benefits of mechanisms like GTM for generalized private testing in this context. Implication I: Hyperparameter Optimization. Hyperparameter optimization (HPO) in private learning is the process of selecting parameters (like noise level, clipping norm, batch size, and learning rate) that balance model accuracy with privacy guarantees. Since finding these parameters itself can leak information, it must be done via privacy-preserving methods. Solving HPO was one of the motivations for generalized private selection and testing in [LT19]. While subsequent works [PS21, GKK+ 25] used generalized private selection instead of testing for this problem, they mention that algorithms for generalized private testing have potential advantages over selection, but point out that if the acceptance threshold were set too high, one could evaluate large sets of hyperparameter choices without identifying a useful candidate, and conversely if we set it too low, then we would get poor quality outputs (see [PS21, Appendix C]). Algorithm 1 addresses this challenge in part by allowing the analyst to set the acceptance threshold p∗t adaptively in every step. This suggests a way to deal with the challenge mentioned by [PS21]: initialize p∗t with a restrictive value at the beginning of the stream and make it gradually more permissive as t increases. Further, in the ex-post setting, if we commit to an ex-post privacy loss guarantee that scales logarithmically in the index of hyperparameter value output by the GTM, then we are guaranteed a rejection threshold p̄t = p∗t /γΛ0 in the notation of theorem 6 10

and theorem 3, where 1/γΛ0 does not depend on the number of hyperparameter values tested. Further, the privacy loss incurred is pure and constant if no hyperparameter value is accepted even when testing on approximate DP mechanisms Mt . Implication II: Reproducibility in Private Machine Learning. [GKK+ 25] suggested the following approach to use generalized private selection in practical private training: instead of trying to find the best hyperparameter directly, one privately trains models using all possible choices of hyperparameters and selects the output model that has the best generalization error (on a given set of test data). They prove that with sufficiently many repetitions per hyperparameter, one is guaranteed to output a model that is competitive with the best model generated (see Section 9.4 for a complete discussion). However, this does not imply that the selection identified the best set of hyperparameters. Typically, there are a large number of hyperparameters with a small probability of generating a good trained model, and a few set of hyperparameters with a high probability of generating a good model. For reproducibility in learning (and considering intrinsic stochasticity of all learning algorithms), one would ideally like to use the hyperparameters of the latter type. The guarantee of [GKK+ 25] (theorem 52) cannot circumvent the hardness of generalized private testing and identifying a good model; we formalize this via an idealized toy example in Corollary 53. We find that regardless of the choice of privacy parameters, when we measure the quality of their private selection algorithm for testing, their approach incurs a ≈ β/T loss in accuracy over a set of T hyperparameter values. At a high level, although correlated random dropping works well for generalized private selection, it seems to always incur a T/β factor in the ratio between acceptance and rejection thresholds when used for generalized private testing. 2. P RELIMINARIES We collect some common notational choices here for reference throughout this paper. Definition 7 (Notation). We make the following definitions of convenience. (1) We define ∞ 1 1 , ζ = . ωt = ∑ 3 3 ζ · t · ln (t + 2) j=1 j ln ( j + 2) With this definition, ∑∞ t=1 ωt = 1. One can check that ζ ∈ (1, 5/4), and that therefore 1/ωt ∈ (t ln3 (t + 2), 2t ln3 (t + 2)). β . These expressions (2) We define β t := ωt β, whence we have that ∑∞ 3 t=1 β t = β, and β t ≥ ζt ln (t+2)

will be used heavily in all failure probability accounting. We recall the definitions and some properties of the distributions used in the sequel. Definition 8 (Distributions). We use the following standard distributions. (1) Bernoulli. For p ∈ [0, 1], a random variable B ∼ Ber( p) takes values in {0, 1} with Pr[ B = 1] = p and Pr[ B = 0] = 1 − p. (2) Exponential. For τ > 0, a random variable η ∼ Exp(τ ) has support [0, ∞) and density f (z) = 1 −z/τ for z ≥ 0. τ e 1 −|z|/(τ ) (3) Laplace. For τ > 0, a random variable ν ∼ Lap(τ ) has support R and density f (z) = 2τ e for z ∈ R. (4) Poisson. For λ ≥ 0, a random variable M ∼ Po(λ) takes values in Z≥0 with mass function k Pr[ M = k ] = e−λ λk! for k ∈ Z≥0 . (5) Pareto. For σ > 0, a random variable w ∼ Par(σ ) has support [1, ∞) with Pr[w > u] = u−σ for u ≥ 1 and density f (u) = σ u−σ−1 for u ≥ 1. 11

Definition 9 (Differential Privacy fundamentals). (1) We define the sensitivity of a function f : X → R by ∆ f := maxd(X,X ′ )=1 | f ( X ) − f ( X ′ )|, where d( X, X ′ ) = 1 is shorthand for X and X ′ are neighboring. (2) Given a sensitivity-1 query f : X → R, the Laplace mechanism ([DMNS06]) releases f ( X ) + ν for ν ∼ Lap(1/ε). The Laplace mechanism is ε-DP. Poisson mean thresholds. For x ≥ 0 and α ∈ (0, 1), define the left and right mean thresholds q (3) λℓ ( x, α) := x + ln(1/α) + 2x ln(1/α) + ln2 (1/α), q (4) λr ( x, α) := x + 1 − 2( x + 1) ln(1/α). These thresholds are derived from Poisson Chernoff bounds (Lemma 54) and provide sufficient conditions for tail control: if M ∼ Po(λ), then λ ≥ λℓ ( x, α) guarantees Pr[ M ≤ x ] ≤ α, and λ ≤ λr ( x, α) guarantees Pr[ M ≥ x + 1] ≤ α (under a mild validity condition that x not be too small). The thresholds may not be tight with respect to the exact Poisson tail probabilities (see Lemma 10, item 3). We define the mean thresholds for real valued x as opposed to just integer valued so as to be able to exploit the algebraic inversion property. See Lemma 10, item 4. Lemma 10 (Poisson and exponential facts). The following properties are used throughout. (1) Additivity. If M1 ∼ Po(λ1 ) and M2 ∼ Po(λ2 ) are independent, then M1 + M2 ∼ Po(λ1 + λ2 ). (2) Thinning. Let M ∼ Po(λ), and conditional on M, let B1 , . . . , BM be i.i.d. Ber( p) random variables, independent of M. Then K := ∑iM =1 Bi ∼ Po( λp ). (3) Tail bounds. Let M ∼ Po(λ) and fix α ∈ (0, 1) and c ∈ Z≥0 . (a) (Left tail.) If λ ≥ λℓ (c, α), then Pr[ M ≤ c] ≤ α. (b) (Right tail.) If c + 1 ≥ 2 ln(1/α) and λ ≤ λr (c, α), then Pr[ M ≥ c + 1] ≤ α. (4) Algebraic inversion. Fix α ∈ (0, 1) and let L = ln(1/α). For λ ≥ 0 and x ≥ 0 with x + 1 > 2L, λ ≤ λr ( x, α)

⇐⇒

x + 1 ≥ λℓ (λ, α).

(5) Exponential density shift. Let η ∼ Exp(τ ) with density f (z) = τ1 e−z/τ for z ≥ 0. For any z ≥ 0 and ∆ ∈ R with z + ∆ ≥ 0, f (z + ∆) = e−∆/τ f (z). Proof. Items 1–2. Standard; see, e.g., [MU05]. Item 3. Write L = ln(1/α). Left tail. We apply Lemma 54 (lower tail) with shift u = λ − c. The assumption λ ≥ λℓ (c, α) ≥ c ensures u ≥ 0, so the bound gives   ( λ − c )2 . Pr[ M ≤ c] = Pr[ M ≤ λ − u] ≤ exp − 2λ We require this to be at most α, i.e., (λ − c)2 ≥ 2λL. Expanding the left side and rearranging by powers of λ yields the quadratic inequality λ2 − 2(c + L)λ + c2 ≥ 0. The roots of the corresponding equation are q p λ = c + L ± (c + L)2 − c2 = c + L ± 2cL + L2 . Since u ≥ 0 requires λ ≥ c, we need λ at or above the larger root. Recognizing the larger root as λℓ (c, α), the bound Pr[ M ≤ c] ≤ α holds for all λ ≥ λℓ (c, α). 12

Right tail. We apply Lemma 54 (upper tail) with shift u = c + 1 − λ for u ≥ 0. Note that the denominator in the Chernoff exponent becomes 2(λ + u) = 2(c + 1), giving   ( c + 1 − λ )2 . Pr[ M ≥ c + 1] = Pr[ M ≥ λ + u] ≤ exp − 2( c + 1) We require this to be at most α, i.e., (c + 1 − λ)2 ≥ 2(c + 1) L as L = ln(1/α). We first show that this implies c + 1 ≥ 2L. The Chernoff upper tail bound requires the shift u = c + 1 − λ to be nonnegative, so we must have λ ≤ c + 1. If c + 1 < 2L, then for every λ ∈ [0, c + 1] we have (c + 1 − λ)2 ≤ (c + 1)2 < 2(c + 1) L, so the required inequality (c + 1 − λ)2 ≥ 2(c + 1) L cannot hold. The condition c + 1 ≥ 2L is therefore necessary. Under this condition, we take the square root of both sides. Since the shift u = c + 1 − λ must be nonnegative, the left side c + 1 − λ is nonnegative, and we obtain q c + 1 − λ ≥ 2(c + 1) L. p Isolating λ yields λ ≤ c + 1 − 2(c + 1) L = λr (c, α). Note that this automatically enforces λ ≤ c + 1, so the nonnegative shift requirement u ≥ 0 is satisfied. Item 4. Let L = ln(1/α) and set y = x + 1, so the validity condition is y > 2L. Starting from λ ≤ λr ( x, α): p p ⇐⇒ y − λ ≥ 2yL. λ ≤ y − 2yL p p Since 2yL ≥ 0, this implies y ≥ λ. So squaring y − λ ≥ 2yL gives (y − λ)2 ≥ 2yL, i.e., y2 − 2(λ + L)y + λ2 ≥ 0. Because y ≥ λ, the variable y lies at or above the larger root: p y ≥ λ + L + 2λL + L2 = λℓ (λ, α). Substituting y = x +p 1 yields x + 1 ≥ λℓ (λ, α). All steps are reversible (the implication y ≥ λ is enforced by y − λ ≥ 2yL ≥ 0), establishing the equivalence. Item 5. Direct computation: f (z + ∆) = τ1 e−(z+∆)/τ = e−∆/τ · τ1 e−z/τ = e−∆/τ f (z).

□

Lemma 11 (Poisson overhead control). Fix error parameters α, β ∈ (0, 1) and a target ratio γ ∈ (1, 2]. Let A = ln(1/α), B = ln(1/β) and c = max(⌊2 max( A, B)⌋, ⌈r2 ⌉), where q √ √ √ √ 2A + γ 2B + ( 2A + γ 2B)2 + 8(γ − 1) A r= . 2( γ − 1) Then, the following statements hold: (1) λℓ (c, α) ≤ γ λr (c, β),
(2) c + 1 > 2 max ln(1/α), ln(1/β) ,
(3) c = O (ln(1/α) + ln(1/β))/(γ − 1)2 . √ Proof. Setting m = c + 1, the right threshold expands as q √ λr (c, β) = c + 1 − 2(c + 1) B = m2 − m 2B. √ √ √ For the left threshold, bounding c < m2 and applying 2cA + A2 < 2m2 A + A2 ≤ m 2A + A gives p √ λℓ (c, α) = c + A + 2cA + A2 < m2 + 2A + m 2A. The condition λℓ (c, α) ≤ γ λr (c, β) is therefore implied by  √ √  m2 + 2A + m 2A ≤ γ m2 − m 2B , 13

which rearranges to

( γ − 1) m2 −

(5)

√

√
2A + γ 2B m − 2A ≥ 0.

Since γ > 1, this quadratic inequality holds for all m at or above its larger positive root q √ √ √ √
2 2A + γ 2B + 2A + γ 2B + 8(γ − 1) A r := . 2( γ − 1) Define c := max Item 1. Since c ≥ ⌈r2 ⌉ ≥ r2 , we have m =



√

   2 max( A, B) , r2 .

c + 1 > r, so (5) holds and the gap condition follows.

Item 2. Since ⌊y⌋ + 1 > y for all y, we have c + 1 ≥ ⌊2 max( A, B)⌋ + 1 > 2 max( A, B). √ √ √ √ Item 3. Write a = 2A + γ 2B for the linear coefficient in (5). Using a2 + b ≤ a + b for a ≥ 0, the numerator of r satisfies q q a + a2 + 8(γ − 1) A ≤ 2a + 8(γ − 1) A. √ √ √ p 2A + 2 2B and 8 ( γ − 1 ) A ≤ 8A, so the numerator is Since γ ≤ 2, we have a ≤ √ √ √ √ O( A + B). Therefore r = O(( A + B)/(γ − 1)) and r2 = O(( A + B)/(γ − 1)2 ). Since ⌊2 max( A, B)⌋ ≤ 2( A + B), the conclusion c = O(( A + B)/(γ − 1)2 ) follows. □ Lemma 12 (Pareto facts). The following properties are used throughout. (1) Exponential to Pareto transformation. If η ∼ Exp(τ ), then eη/(στ ) ∼ Par(σ). (2) Moments. Let w ∼ Par(σ ). For any k > 0, E[w−k ] = σ/(σ + k ). For any 0 < k < σ, E[wk ] = σ/(σ − k). If k ≥ σ, then E[wk ] = ∞. (3) Truncated moments. Let w ∼ Par(σ ) with σ > 1, and define w̃ := min(w, W ) for W ≥ 1. Then: W 1− σ σ σ − ≤ . (a) E[w̃] = σ− 1 σ−1 σ−1 2 − σ  −σ 2 W if σ ̸= 2, 2 2−σ (b) E[w̃ ] =  2 ln W + 1 if σ = 2. In particular: when 1 < σ < 2, E[w̃2 ] ≤ 2−2 σ W 2−σ ; when σ = 2, E[w̃2 ] = 2 ln W + 1; σ when σ > 2, E[w̃2 ] ≤ σ− 2. Proof. Item 1. For u ≥ 1, Pr[eη/(στ ) > u] = Pr[η > στ ln u] = e−σ ln u = u−σ . R∞ Item 2. By direct integration, E[wk ] = σ 1 uk−σ−1 du = σ/(σ − k ) when k < σ, and the integral R∞ diverges when k ≥ σ. Similarly, E[w−k ] = σ 1 u−k−σ−1 du = σ/(σ + k ) for all k > 0. RW Item 3(a). E[w̃] = 1 u · σu−σ−1 du + W · W −σ . The integral equals 1−σ σ (W 1−σ − 1) for σ > 1. 1− σ

σ W Adding W 1−σ and simplifying gives E[w̃] = σ− 1 − σ −1 . Since W ≥ 1 and σ > 1, the subtracted term is nonnegative. RW Item 3(b). E[w̃2 ] = σ 1 u1−σ du + W 2−σ . For σ ̸= 2, the integral equals 2−σ σ (W 2−σ − 1), and 2− σ

adding W 2−σ gives 2 W2−σ−σ . For σ = 2, the integral equals 2 ln W, and adding 1 gives 2 ln W + 1. 2− σ

2− σ

For the bounds: when 1 < σ < 2, 2 − σ > 0, so 2W2−σ−σ ≤ 2W 2−σ . When σ > 2, rewrite

2− σ 2W 2−σ −σ σ 2−σ ≥ 0. = σ−σ2W ≤ σ− 2− σ −2 2 since W

□ 14

We will find it convenient to reason about the accuracy of generalized private testers in terms of their per-step type I and type II errors. Definition 13 (Accuracy). Consider a generalized private tester that for some given failure probability β and target thresholds ( p∗t )t≥1 achieves rejection thresholds ( p̄t )t≥1 . A Type I error (false halt) at step t is the event that the tester halts and st pt ≤ st p̄t . A Type II error (missed halt) at step t is the event that the tester continues and st pt ≥ st p∗t . Then we define the following notions of accuracy. (1) Global accuracy. The tester is β-globally accurate if, with probability at least 1 − β, no Type I or Type II error occurs at any step. (2) Per-step accuracy. The tester has ( βIt , βIIt ) per-step accuracy at step t if the Type I and Type II error probabilities at step t are at most βIt and βIIt , respectively. For the given choice of thresholds, the generalized private tester considered in this definition is β-globally accurate. 3. T HE G ENERALIZED T HRESHOLDING M ECHANISM In this section, we introduce the Generalized Thresholding Mechanism (Algorithm 1). The algorithm monitors a sequence of mechanisms Mt : X → {−1, +1}, each evaluated on a dataset Xt with an input privacy promise ε t ≥ 0, and halts when it believes that the success probability pt := Pr[Mt ( Xt ) = +1] lies in the target regime. The sequence is provided by an adaptive analyst. At the beginning of the stream, the analyst fixes (a) a value τ1 that determines the scale parameter of a privatizing noise value η1 ∼ Exp(τ1 ) that is shared across the stream, and (b) a calibration parameter µ1 which will be a high probability upper bound on the magnitude of η1 . At each step t, after observing the prior outputs a1 , . . . , at−1 , the analyst selects (c) the mechanism Mt , (d) dataset Xt , (e) privacy parameter ε t , subject only to the constraint that Mt is ε t -differentially private, and (f) a noise scale τ2,t . The mechanism will choose various per-step tuning parameters, namely (1) a threshold ct , (2) a base rate ρt , and (3) a direction st . The privacy guarantee (Lemma 17) holds against all such adaptive choices; it is parameterized by τ1 and by the per-step noise scales τ2,t (which directly determines the privacy cost at halting time, regardless of the values of ε 1 , . . . , ε t ). However, different values of st , ρt , and ct yield qualitatively different accuracy guarantees in terms of the rejection threshold p̄ and we give below values that minimize accuracy loss. The algorithm uses two sources of randomness for privacy. A shared noise value η1 ∼ Exp(τ1 ) is drawn once at initialization and reused at every step. At each step t, a fresh noise value η2,t ∼ Exp(τ2,t ) is drawn independently. They are combined with the calibration offset µ1 > 0 and the direction st ∈ {−1, +1} as follows to form the noise term Zt = st · (µ1 − η1 + η2,t ). The noise Zt controls the number of mechanism evaluations at step t. The algorithm makes Nt i.i.d. evaluations of Mt ( Xt ), where Nt ∼ Po(ρt exp(ε t Zt )). The exponential scaling exp(ε t Zt ) scales the perturbation with the input privacy parameter ε t ; when ε t = 0, the mechanism already satisfies 0-DP and no perturbation is needed, so Nt reduces to the base rate ρt . The algorithm counts the number Kt of +1 outcomes among the Nt -many evaluations of Mt ( Xt ). The direction parameter st determines two modes of operation. (1) When st = +1 (above threshold), the algorithm halts if Kt ≥ ct + 1, indicating that pt is large. (2) When st = −1 (below threshold), the algorithm halts if Kt ≤ ct , indicating that pt is small. 15

procedure GTM.Init(τ1 , µ1 ): Input: Shared noise scale τ1 > 0; calibration offset µ1 > 0. Draw η1 ∼ Exp(τ1 ); Store η1 and µ1 ; procedure GTM.Step(Mt , Xt , ε t , τ2,t , ct , ρt , st ): Input: privacy parameter ε t ≥ 0; Mechanism Mt : X → {−1, +1} (ε t -DP); dataset Xt ∈ X ; per-step noise scale τ2,t > 0; threshold ct ∈ Z≥0 ; base rate ρt > 0; direction st ∈ {−1, +1}. Output: at ∈ {−st , st }, where at = st denotes halting and at = −st denotes continuation. Draw η2,t ∼ Exp(τ2,t );
Zt ← st µ1 − η1 + η2,t ; λt ← ρt · exp(ε t Zt ); Draw Nt ∼ Po(λt ); Kt ← 0; for i = 1, . . . , Nt do Draw yt,i ∼ Mt ( Xt ); if yt,i = +1 then Kt ← Kt + 1; end if st · (Kt − ct − 21 ) > 0 then Output at ← st and halt; else Output at ← −st ; Algorithm 1: Generalized Thresholding Mechanism Conditioned on η1 ≤ µ1 , the signed quantity st Zt = µ1 − η1 + η2,t is nonnegative. Therefore, Zt is positive when st = +1 and negative when st = −1. This means that above threshold (st = +1) never deflates Nt below ρt , while the below threshold (st = −1) never inflates it above ρt . Definition 14 (Execution variables and continuation probability). Fix a step t ≥ 1. Let the parameters up to step t be as specified in Algorithm 1. Write pt := Pr[Mt ( Xt ) = +1]. Algorithm 1 induces the following random variables at step t:

• Aggregated noise and conditional Poisson mean. Define Zt := st (µ1 − η1 + η2,t ),

λt (z) := ρt exp(ε t z)

for z ∈ R,

and write λt := λt ( Zt ) = ρt exp(ε t Zt ) for the realized Poisson mean. The algorithm draws Nt ∼ Po(λt ) evaluations of Mt ( Xt ). • Count and thinning. Let Kt := ∑iN=t 1 1{yt,i = +1} denote the number of +1 outcomes. By Poisson thinning (Lemma 10), conditional on λt , Kt ∼ Po(λt pt ).

• Continuation probability. Define gt (z) to be the probability that step t produces the non-halting output at = −st , given Zt = z:   gt (z) := Pr at = −st Zt = z . For a neighboring dataset Xt′ , write p′t := Pr[Mt ( Xt′ ) = +1], and let gt′ (z) denote the corresponding continuation probability when Mt is evaluated on Xt′ . 16

3.1. Privacy analysis. Lemma 15 (Poisson representation and pointwise shifts). Fix a step t ≥ 1 and neighboring datasets Xt , Xt′ . Let gt (·) and gt′ (·) be the continuation probabilities from Definition 14, and define the Poisson cumulative distribution function F (c; λ) := Pr[ M ≤ c] where M ∼ Po(λ). Then for every z ∈ R, the following hold: (1) (Poisson representation.) gt ( z ) =


 F ct ; λt (z) pt ,

if st = +1,

1 − F c t ; λ t ( z ) p t ,

if st = −1,

and an identical representation holds for gt′ (z) with p′t in place of pt . (2) (Shift identities for the conditional mean.) λ t ( z − s t ) = e −st ε t λ t ( z )

and

λ t ( z + s t ) = e s t ε t λ t ( z ).

(3) (Shift inequalities for continuation probability.) gt (z) ≤ gt′ (z − st )

1 − gt (z) ≤ 1 − gt′ (z + st ).

and

Proof. Fix z ∈ R. Part (1). Condition on the event { Zt = z}. Under this conditioning, the algorithm draws Nt ∼ Po(λt (z)) evaluations of Mt ( Xt ), and counts Kt = ∑iN=t 1 1{yt,i = +1}. By Poisson thinning (Lemma 10),
Kt ∼ Po λt (z) pt . The step outputs −st exactly when st · (Kt − ct − 12 ) ≤ 0. For st = +1, this condition is Kt ≤ ct as ct is an integer, yielding gt (z) = F (ct ; λt (z) pt ). For st = −1, this condition is Kt ≥ ct + 1, yielding gt (z) = 1 − F (ct ; λt (z) pt ). The derivation for gt′ (z) is identical with p′t replacing pt . Part (2). This follows directly from the definition of λt (·):
λt (z ± st ) = ρt exp ε t (z ± st ) = e±st ε t λt (z). Part (3). We establish the shift inequalities by considering the two cases of st .

Case st = +1: By part (1), gt (z) = F ct ; λt (z) pt and gt′ (z − 1) = F ct ; λt (z − 1) p′t . By ε t differential privacy, pt ≥ e−ε t p′t . By part (2), λt (z) = eε t λt (z − 1). Multiplying these yields λt (z) pt ≥ λt (z − 1) p′t . Because the Poisson CDF λ 7→ F (c; λ) is non-increasing in λ, it follows that

gt (z) = F ct ; λt (z) pt ≤ F ct ; λt (z − 1) p′t = gt′ (z − 1). For the second inequality, we evaluate the halting probability 1 − gt (z) = Pr[Po(λt (z) pt ) ≥ ct + 1]. By differential privacy, pt ≤ eε t p′t , and by part (2), λt (z + 1) = eε t λt (z), yielding λt (z) pt ≤ λt (z + 1) p′t . Since 1 − F (c; λ) is non-decreasing in λ, we obtain 1 − gt (z) ≤ 1 − gt′ (z + 1).

Case st = −1: By part (1), gt (z) = 1 − F ct ; λt (z) pt and gt′ (z + 1) = 1 − F ct ; λt (z + 1) p′t . By differential privacy, pt ≤ eε t p′t , and by part (2), λt (z + 1) = eε t λt (z), yielding λt (z) pt ≤ λt (z + 1) p′t . Because F (ct ; λ) is non-increasing in λ, the complement 1 − F (ct ; λ) is non-decreasing. Thus gt (z) ≤ gt′ (z + 1) = gt′ (z − st ). 17

For the second inequality, note that 1 − gt (z) = F (ct ; λt (z) pt ) and 1 − gt′ (z − 1) = F (ct ; λt (z − 1) p′t ). Using pt ≥ e−ε t p′t and λt (z) = eε t λt (z − 1), we find λt (z) pt ≥ λt (z − 1) p′t . Applying the non-increasing property of F (ct ; λ) gives 1 − gt (z) ≤ 1 − gt′ (z − 1) = 1 − gt′ (z + st ).

□ Remark 16 (Asymmetric use of input privacy). The shift inequalities in Part (3) depend on the input privacy guarantee only through bounds on the ratio pt /p′t of the +1 output probabilities. In all four subcases, the Poisson thinning mean is λt (z) pt , and the comparison is with λt (z ± 1) p′t ; the ratio (1 − pt )/(1 − p′t ) of the −1 output probabilities never appears. When the algorithm operates on the negated mechanism (flipped variant, st = −1), the role of pt and 1 − pt is exchanged, and the relevant ratio becomes (1 − pt )/(1 − p′t ) in terms of the original mechanism. Lemma 17 (Privacy of the generalized thresholding mechanism). Let ( Xt )t≥1 and ( Xt′ )t≥1 be dataset sequences with Xt neighboring Xt′ for every t. Run Algorithm 1 on ( Xt )t≥1 and on ( Xt′ )t≥1 with the same sequences (ε t ), (ct ), (ρt ), (τ2,t ), and (st ). Let ( at )t≥1 and ( a′t )t≥1 denote the resulting output sequences. Then for every t ≥ 1,     Pr a[t] = (−s1 , . . . , −st ) ≤ e1/τ1 Pr a′[t] = (−s1 , . . . , −st ) , (6) (7)

    Pr a[t] = (−s1 , . . . , −st−1 , st ) ≤ e1/τ1 +2/τ2,t Pr a′[t] = (−s1 , . . . , −st−1 , st ) .

In particular, if τ2,t = τ2 for all t, the algorithm satisfies pure ε-differential privacy with ε = 1/τ1 + 2/τ2 . Proof. Write f 1 for the pdf of η1 ∼ Exp(τ1 ) and f 2,t for the density of η2,t ∼ Exp(τ2,t ). By the exponential density shift (Lemma 10, item 5), (8)

f 1 ( x + 1) = e−1/τ1 f 1 ( x )

f 2,t (y + 2) = e−2/τ2,t f 2,t (y)

for x ≥ 0,

for y ≥ 0,

or equivalently, f 1 (u − 1) = e1/τ1 f 1 (u) for u ≥ 1 and f 2,t (v − 2) = e2/τ2,t f 2,t (v) for v ≥ 2. Conditional factorization. Conditional on η1 and η2,1 , . . . , η2,t , each Zi is deterministic, and the Poisson draw and mechanism evaluations at distinct time steps are mutually independent. By the chain rule, t    Pr a[t] = (−s1 , . . . , −st ) η1 , η2,[t] = ∏ Pr ai = −si

 a[i−1] = (−s1 , . . . , −si−1 ), η1 , η2,[t] .

i =1

The prefix (−s1 , . . . , −si−1 ) determines the mechanism, dataset, and parameters that the analyst selects at step i. Given these, the conditional probability Pr[ ai = −si | a[i−1] = (−s1 , . . . , −si−1 ), η1 , η2,[t] ] depends only on Zi , where the probability is taken over the random variables Ni and yi,j , and equals gi ( Zi ) by Definition 14. Therefore, t   Pr a[t] = (−s1 , . . . , −st ) η1 , η2,[t] = ∏ gi ( Zi ).

(9)

i =1

Similarly, the halt-at-t probability factors as t −1

(10)





Pr a[t] = (−s1 , . . . , −st−1 , st ) η1 , η2,[t] =

∏ gi (Zi )

!

(1 − gt ( Zt )).

i =1

The shift inequality gi (z) ≤ gi′ (z − si ) from Lemma 15 holds for every ε i -DP mechanism, regardless of how the analyst selected it. 18

All-continuation transcript. We bound the probability that the algorithm continues through all t steps. Integrating over η1 and taking the expectation over the independent per-step noises η2,[t] := (η2,1 , . . . , η2,t ):   (11)

 t   Z ∞
   Pr a[t] = (−s1 , . . . , −st ) = E ∏ gi si (µ1 − x + η2,i )  f 1 ( x ) dx.  0 η2,[t]  i =1 {z } |

S ′ By Lemma 15 (item 3), gi (z) ≤ gi (z − si ) for all z ∈ R. Evaluating at z = si (µ1 − x + η2,i ) gives z − si = si (µ1 − ( x + 1) + η2,i ), so the term in the integrand in (11) is bounded above by t
S ≤ ∏ gi′ si (µ1 − ( x + 1) + η2,i ) . i =1

That is, 



Pr a[t] = (−s1 , . . . , −st ) ≤

Z ∞ 0

" E

η2,[t]

#

t

∏ gi′ si (µ1 − (x + 1) + η2,i )

f 1 ( x ) dx

i =1

Let u = x + 1. Then the integration domain { x ≥ 0} maps to {u ≥ 1}, and we obtain " # t
  Z ∞ Pr a[t] = (−s1 , . . . , −st ) ≤ E ∏ gi′ si (µ1 − u + η2,i ) f 1 (u − 1) du. 1

η2,[t]

i =1

In the region {u ≥ 1}, the density shift (8) gives f 1 (u − 1) = e1/τ1 f 1 (u). Since the integrand is non-negative, enlarging the domain from {u ≥ 1} back to {u ≥ 0} only increases the value of integration, i.e., " # Z ∞ t
  E ∏ gi′ si (µ1 − u + η2,i ) f 1 (u) du Pr a[t] = (−s1 , . . . , −st ) ≤ e1/τ1 0

η2,[t]

i =1

  = e1/τ1 Pr a′[t] = (−s1 , . . . , −st ) . Halt-at-t transcript. We bound the probability that the algorithm continues through steps 1, . . . , t − 1 and halts at step t. Writing x for the integration variable of η1 and y for that of η2,t , and taking the expectation over the remaining per-step noises η2,[t−1] := (η2,1 , . . . , η2,t−1 ):   Pr a[t] = (−s1 , . . . , −st−1 , st ) "Z Z ! # ∞ ∞ t −1


(12) = E ∏ gi si (µ1 − x + η2,i ) 1 − gt st (µ1 − x + y) f1 (x) f2,t (y) dy dx . η2,[t−1]

0

0

i =1

The proof idea remains the same as above except that we have to treat the halting step differently. In particular, as in the previous case, we first apply the shift inequalities from Lemma 15 (item 3): for each continuation step i ≤ t − 1, we use gi (z) ≤ gi′ (z − si ), and for the halting step, 1 − gt (z) ≤ 1 − gt′ (z + st ). Evaluating the shifted arguments:
si (µ1 − x + η2,i ) − si = si µ1 − ( x + 1) + η2,i , s t ( µ1 − x + y ) + s t = s t ( µ1 − x + y + 1). We perform a simultaneous change of variables: u = x + 1 and v = y + 2, where the variable v deals with the halting step. Then x = u − 1 and y = v − 2, and the arguments become
si µ1 − ( x + 1) + η2,i = si (µ1 − u + η2,i ), 19

s t ( µ1 − x + y + 1) = s t µ1 − ( u − 1) + ( v − 2) + 1 = s t ( µ1 − u + v ). The integration domain { x ≥ 0, y ≥ 0} maps to {u ≥ 1, v ≥ 2}. Substituting into (12) and applying the shift inequalities:   Pr a[t] = (−s1 , . . . , −st−1 , st ) "Z Z ! # ∞ ∞ t −1


≤ E ∏ gi′ si (µ1 − u + η2,i ) 1 − gt′ st (µ1 − u + v) f1 (u − 1) f2,t (v − 2) dv du . η2,[t−1]

1

2

i =1

In the restricted region {u ≥ 1, v ≥ 2}, we apply the density shifts (8): f 1 (u − 1) = e1/τ1 f 1 (u) and f 2,t (v − 2) = e2/τ2,t f 2,t (v). Enlarging the integration region back to {u ≥ 0, v ≥ 0} yields   Pr a[t] = (−s1 , . . . , −st−1 , st ) "Z Z ! # ∞ ∞ t −1


1/τ1 +2/τ2,t ′ ′ ≤e E ∏ gi si (µ1 − u + η2,i ) 1 − gt st (µ1 − u + v) f1 (u) f2,t (v) dv du η2,[t−1]

0

0

i =1

  = e1/τ1 +2/τ2,t Pr a′[t] = (−s1 , . . . , −st−1 , st ) . Overall privacy. When τ2,t = τ2 for all t, the multiplicative factor in both equations (6) and (7) is at most e1/τ1 +2/τ2 . Every reachable transcript of the algorithm is either an all-continuation prefix or a halt-at-t transcript for some t ≥ 1. Summing the per-transcript bounds over all t yields Pr[output ∈ F ] ≤ e1/τ1 +2/τ2 Pr[output′ ∈ F ] for every measurable event F, establishing pure ε-differential privacy with ε = 1/τ1 + 2/τ2 . □ Remark 18 (Sample complexity). Run Algorithm 1 for t steps. At each step i ≤ t, the algorithm draws Ni ∼ Po(λi ) evaluations of Mi ( Xi ), where λi = ρi exp(ε i Zi ). The total number of evaluations through step t is N≤t := ∑it=1 Ni . Conditional on the shared noise η1 and the per-step noises η2,1 , . . . , η2,t , each Zi = si (µ1 − η1 + η2,i ) is deterministic, so the counts N1 , . . . , Nt are conditionally independent with Ni | η1 , η2,i ∼ Po(λi ). By Poisson additivity (Lemma 10), ! t

N≤t | η1 , η2,[t] ∼ Po

∑ λi

.

i =1

Since Zi depends on η1 and η2,i but not on η2,j for j ̸= i, the conditional total mean ∑it=1 λi depends on η1 through every term, and on each η2,i only through the i-th term. 4. A CCURACY G UARANTEES The privacy guarantee of the GTM holds for adaptive choices of threshold parameter ct and base rate ρt . We now show how to set these parameters to achieve concrete accuracy guarantees. In Theorem 21, we derive a uniform high probability accuracy guarantee, and in Theorem 23 we derive a similar accuracy guarantee, but under an ex-post privacy guarantee. Both of these results follow from a technical lemma, Lemma 20. To motivate Lemma 20, consider a step with st = +1 (above threshold). If pt ≥ p∗t , we want the algorithm to halt. The algorithm generates a count Kt ∼ Po(λt pt ) and halts if Kt > ct . Since λt = ρt exp(ε t Zt ), there is inherent uncertainty in the value of λt due to the privatizing noise Zt = st (µ1 − η1 + η2,t ). We call the event G the event that certain high-probability bounds hold on the value of η1 and η2,t , see Lemma 19. Now, conditioned on G , there is a value Λt > 1 such that λt ∈ [ρt , ρt Λt ]. To ensure that the probability of a Type II error (missed halt) is at most βII , we need that even under a worst-case draw of λt , the thinned Poisson mean λt p∗t is large enough so that Pr[Kt ≤ ct ] is small; by the left 20

tail bound of Poisson distribution (i.e., item 3a in Lemma 10), this requires λt p∗t ≥ λℓ (ct , βII ). If pt ≥ p∗t , then conditioned on G , since λt ≥ ρt , it suffices that ρt ≥ λℓ (ct , βII )/p∗t for Kt > ct with probability 1 − βII . In particular, combining pt ≥ p∗t and λt ≥ ρt , if ρt ≥ λℓ (ct , βII )/p∗t , then we get the inequality: λℓ (ct , βII ) λℓ (ct , βII ) λt ≥ ρt ≥ ≥ . ∗ pt pt Conversely, to ensure that the probability of a Type I error (i.e., false halt) is at most βI when pt ≤ p̄t for some p̄t < p∗t , we need that for any value of λt ∈ [ρt , ρt Λt ], the mean λt p̄t is small enough that Pr[Kt > ct ] is small. By item 3b in Lemma 10, this requires λt p̄t ≤ λr (ct , βI ). Again, conditioned on G , this implies that for continuation, it suffices that p̄t ≤

λr ( c t , βI ) . ρt Λt

We now have two requirements: the halting condition ρt ≥ λℓ (ct , βII )/p∗t , and the continuation condition p̄t ≤ λr (ct , βI )/(ρt Λt ). Since larger ρt means higher sample complexity (the Poisson mean λt = ρt exp(ε t Zt ) scales linearly with ρt ), we set ρt as small as possible, namely ρt = λℓ (ct , βII )/p∗t . Substituting into the continuation condition, the rejection threshold below which the test is guaranteed to continue becomes p̄t =

λr ( c t , βI ) λr (ct , βI ) p∗t = ℓ · . ρt Λt λ (ct , βII ) Λt

This factorization isolates the two sources of accuracy loss. The factor p∗t /Λt is the cost of privacy: it reflects the worst-case multiplicative perturbation of λt by the noise exp(ε t Zt ), and we show in Section 6 that it is unavoidable up to constant factors in the exponent. The ratio λr (ct , βI )/λℓ (ct , βII ) ≤ 1 is the cost of finite-sample Poisson testing: both thresholds grow linearly in ct , but their gap grows sublinearly, so the ratio approaches 1 as ct → ∞. Lemma 20 makes this precise: for any target ratio γ ∈ (1, 2], it constructs a value of ct such that λℓ (ct , βII ) ≤ γ · λr (ct , βI ), giving p̄t ≥ p∗t /(γΛt ). The required base rate scales as ρt = O((ln(1/βI ) + ln(1/βII ))/((γ − 1)2 p∗t )). The case st = −1 (below threshold) is analogous, with λt ∈ [ρt /Λt , ρt ] (conditioned on high probability bounds on η1 and η2,t ), and with the roles of the left and right tails exchanged: halting uses the right tail (with parameter βII ) and continuation uses the left tail (with parameter βI ). In this description, we have described the above threshold variant of Algorithm 1, where for every step t, st = +1; the below threshold analysis is entirely analogous. However, there is another consequence of this functionality. The choice of direction parameter st gives us two ways of running the algorithm to solve the standard above threshold formulation of the generalized private testing problem, where we are required to halt for pt ≥ p∗t . (1) Direct variant: We set st = +1 for all t ≥ 1, and run the mechanism as is (2) Flipped variant: We set st = −1 for all t ≥ 1, and feed the GTM the ‘flipped’ input mechanisms −Mt with success probabilities qt = 1 − pt , a flipped target success threshold q∗t = 1 − p∗t . For the second formulation, we see that the GTM halts when st = −1, indicating that qt ≤ q∗t ⇔ pt ≥ p∗t , so clearly both variants solve the same problem. We find that the flipped variant offers better accuracy when p∗t is close to 1. From the description above, we see that the direct variant with st = +1 for all t ≥ 1 achieves a rejection threshold of p̄t = p∗t /(γ Λt ), for some γ, Λt > 1. It follows that p∗t − p̄t = p∗t (1 − 1/γΛt ), i.e the gap between the thresholds is large when p∗t approaches 1, but small when p∗t approaches 0. Similarly, for the 21

flipped variant, we get that q̄t = q∗t /γΛt , and the gap between the thresholds is large when q∗t approaches 1 and small when q∗t approaches 0. However, since q∗t = 1 − p∗t , this implies that the flipped variant has a smaller threshold gap when the given value of p∗t approaches 1. By choosing the variant adaptively that maximizes our accuracy, we can achieve a tight accuracy for both regimes, i.e. when p∗t approaches 0 and when p∗t approaches 1. Lemma 19 (Bounding λt ). Run Algorithm 1 with parameters τ1 > 0 and µ1 > 0, per-step noise scales τ2,t > 0, and per-step privacy parameters ε t ≥ 0. Fix a constant cG ≤ 1, and define the good noise event \  η2,t ≤ τ2,t ln(1/cG β t ) . G : = η1 ≤ µ 1 ∩ t ≥1

Then the following hold. (1) Failure probability. Pr[G c ] ≤ e−µ1 /τ1 + cG ∑∞ t =1 β t .
(2) Noise range conditioned on G . Define Λt := exp ε t (µ1 + τ2,t ln(1/(cG β t ))) . Conditioned on G , the signed noise satisfies st Zt ∈ [0, µ1 + τ2,t ln(1/(cG β t ))], and the Poisson mean satisfies st = +1 =⇒ λt ∈ [ρt , ρt Λt ], st = −1 =⇒ λt ∈ [ρt /Λt , ρt ]. (3) Halting range on {η1 ≤ µ1 }. Conditioned on the event {η1 ≤ µ1 } alone (and not on all of G ), st Zt ≥ 0 for all t, and therefore λt ≥ ρt when st = +1 and λt ≤ ρt when st = −1. Proof. By the tail bound of the exponential distribution, Pr[η1 > µ1 ] = e−µ1 /τ1 and Pr[η2,t > τ2,t ln(1/cG β t )] = cG β t for each t. A union bound gives item 1. For Items 2 and 3, recall that Zt = st (µ1 − η1 + η2,t ) and st ∈ {−1, 1}. Therefore, st Zt = µ1 − η1 + η2,t . When η1 ≤ µ1 , the lower bound st Zt ≥ η2,t ≥ 0 holds since η2,t has nonnegative support and the rest of Item 3 holds by the definition of λt . On G , the upper bound st Zt ≤ µ1 + τ2,t ln(1/(cG β t )) holds by the per-step noise constraint. Exponentiating and recalling λt = ρt exp(ε t Zt ) gives the stated ranges. □ Lemma 20 (Parameter selection). Fix a target threshold p∗t ∈ (0, 1), per-step error parameters βI , βII ∈ (0, 1), a parameter Λ ≥ 1, and a target ratio γ ∈ (1, 2]. Let p ∈ (0, 1),

λ > 0,

and

K ∼ Po(λ p).

For α, β ∈ (0, 1), let cα,β be defined as in lemma 11, i.e. for A = ln(1/α) and B = ln(1/β), cα,β = max(⌊2 max( A, B)⌋, ⌈r2 ⌉), where q √ √ √ √ 2A + γ 2B + ( 2A + γ 2B)2 + 8(γ − 1) A r= . 2( γ − 1) (1) Above threshold (s = +1). Let (α, β) = ( βII , βI ), and let c = cα,β . Let ρ = λℓ (c, βII )/p∗t . Then the following statements hold: (a) Halting: If λ ≥ ρ and p ≥ p∗t , then Pr[K ≤ c] ≤ βII . (b) Continuation: If λ ≤ ρΛ and p ≤ p∗t /(γΛ), then Pr[K ≥ c + 1] ≤ βI . (2) Below threshold (s = −1). Let (α, β) = ( βI , βII ) and let c = cα,β . Set ρ = λr (c, βII )/p∗t . (a) Halting: If λ ≤ ρ and p ≤ p∗t , then Pr[K ≥ c + 1] ≤ βII . (b) Continuation: If λ ≥ ρ/Λ and p ≥ γΛp∗t , then Pr[K ≤ c] ≤ βI . ln(1/βI )+ln(1/βII )
Further, in both cases (i.e., s ∈ {+1, −1}), we have the base rate upper bound ρ = O , (γ−1)2 p∗t  1 I II I II and the base rate lower bound that if β , β ≤ 1/e, then ρ ≥ p∗ max ln(1/β ), ln(1/β ) . t

22

Proof. We prove each of the parts separately. Above threshold. Since c is defined via Lemma 11 with (α, β) = ( βII , βI ), it follows from Lemma 11 that λℓ (c, βII ) ≤ γ λr (c, βI ) and c + 1 > 2 max( LI , LII ), where LI = ln(1/βI ) and LII = ln(1/βII ). Since we set ρ = λℓ (c, βII )/p∗t , rearranging, ρ p∗t = λℓ (c, βII ). Halting. If p ≥ p∗t and λ ≥ ρ, then λ p ≥ ρ p∗t = λℓ (c, βII ). By Lemma 10(3a), Pr[K ≤ c] ≤ βII . Continuation. If p ≤ p∗t /(γΛ), and λ ≤ ρΛ, then λ p ≤ ρ p∗t /γ = λℓ (c, βII )/γ ≤ λr (c, βI ). The hypothesis c + 1 > 2 ln(1/βI ) ensures the domain condition of Lemma 10(3b), giving Pr[K ≥ c + 1] ≤ βI . Below threshold. Since c is defined via Lemma 11 with (α, β) = ( βI , βII ), it follows from lemma 11 that λℓ (c, βI ) ≤ γ λr (c, βII ) and c + 1 > 2 max( LI , LII ) where LI = ln(1/βI ) and LII = ln(1/βII ). Since we set ρ = λr (c, βII )/p∗t , rearranging, ρ p∗t = λr (c, βII ). Halting. If p ≤ p∗t and λ ≤ ρ, then λ p ≤ ρ p∗t = λr (c, βII ). Since c + 1 > 2 ln(1/βII ) the domain condition of Lemma 10(3b) is fulfilled, and so Pr[K ≥ c + 1] ≤ βII . Continuation. If p ≥ γΛp∗t and λ ≥ ρ/Λ, then λ p ≥ γ ρ p∗t = γλr (c, βII ) ≥ λℓ (c, βI ). By item 3a in Lemma 10, Pr[K ≤ c] ≤ βI . Base rate bounds √ Upper bound. In the above-threshold setting, ρ = λℓ (c, βII )/p∗t and λℓ (c, βII ) = O(c + c LII + LII ). In the below-threshold setting, ρ = λr (c, βII )/p∗t and λr (c, βII ) ≤ c + 1. In both cases, c = O(( LI + LII )/(γ − 1)2 ) by Lemma 11(3), and dividing by p∗t gives the stated bounds. Lower bound. Write LI = ln(1/βI ) q ≥ 1 and LII = ln(1/βII ) ≥ 1. From (3), λℓ (c, α) ≥ c + 2 ln(1/α)

for all c ≥ 0 and α ∈ (0, 1), since 2c ln(1/α) + ln2 (1/α) ≥ ln(1/α). From Lemma 11(2) and integrality of c, c ≥ 2 max( LI , LII ) − 1. In the above threshold setting, ρ p∗t = λℓ (c, βII ) ≥ c + 2LII ≥ (2LI − 1) + 2LII . Since LI ≥ 1, this gives ρ p∗t ≥ LI + 2LII ≥ max( LI , LII ). In the below threshold setting, by Lemma 11(1), γ ρ p∗t = γ λr (c, βII ) ≥ λℓ (c, βI ) ≥ c + 2LI ≥ (2LII − 1) + 2LI . Dividing by γ ≤ 2 gives ρ p∗t ≥ LI + LII − 12 ≥ max( LI , LII ), since min( LI , LII ) ≥ 1 > 12 . □ 4.1. Global accuracy guarantee. Theorem 21 instantiates Lemma 17, Lemma 19, and Lemma 20 with specific choices of γ, βI , βII , and Λt determined by the privacy budget and failure probability allocation, and establishes a worst-case accuracy bound for Algorithm 1. Theorem 21 (Global utility). Fix ε > 0, θ > 0, a gap parameter γ ∈ (1, 2], and a failure probability β ∈ (0, 1). Define  (ε t /ε)(1+2/θ )  (ε t /ε)(2+θ ) 4 4 Λt := . β βt For any choice of p∗t , st , ρt and ct , Algorithm 1 is ε-differentially private. Further, there exists a choice of parameter settings for st , ρt and ct such that, with probability at least 1 − β, the following hold simultaneously for all t ≥ 1: 23

(1) Halting. At every step t where pt ≥ p∗t , the algorithm halts. (2) Continuation. The algorithm continues past every step t satisfying pt ≤ p̄t , where the rejection threshold   ∗ pt ∗ , 1 − γ Λ t (1 − p t ) . p̄t := max γ Λt (3) Sample complexity. The number of evaluations of the mechanism Mt at step t is Nt ∼ Po(λt ) for λt ≤ Ãt · wt , where ! (4/β)(1+2/θ )ε t /ε C A · ln(t/β) 1 Ãt := · max , ( γ − 1)2 p∗t 1 − p∗t for some universal constant C A and wt := eε t η2,t ∼ Par(σt ) with σt := ε/(ε t (θ + 2)), independently across steps. Proof of Theorem 21. We run Algorithm 1 with the following parameter setting. For θ > 0, define
1 θε 2 2ε = = , , ∀t τ2,t = τ2 µ1 = τ1 ln β4 . τ1 θ+2 τ2 θ+2 Privacy. Since 1/τ1 + 2/τ2 = ε and τ2,t = τ2 for all t, Lemma 17 gives pure ε-differential privacy. Bounding λt . Applying Lemma 19 with cG = 1/4, since e−µ1 /τ1 = β/4 and cG ∑t β t = β/4, we can write β β β Pr[G c ] ≤ + = . 4 4 2 From the definition of Λt in lemma 19 and using that µ1 = τ1 ln(4/β), we can write  τ1 ε t  τ2,t ε t
4 4 Λt = exp ε t (µ1 + τ2,t ln(4/β t )) = β βt From the definition of τ1 and τ2,t , we have that   εt εt 2 +1 τ2,t ε t = (2 + θ ) τ1 ε t = ε θ ε

 (ε t /ε)(1+2/θ )  (ε t /ε)(2+θ ) 4 4 ⇒ Λt = . β βt

Now, Lemma 19 shows that conditioning on G , λt ∈ [ρt , ρt Λt ] when st = +1 and λt ∈ [ρt /Λt , ρt ] when st = −1. When η1 ≤ µ1 , then λt ≥ ρt when st = +1 and λt ≤ ρt when st = −1. Accuracy. Conditioned on G , we know that for all time-steps t, for any choice of ρt , if st = +1 then λt ∈ [ρt , ρt Λt ], and if st = −1 then λt ∈ [ρt /Λt , ρt ]. If st = +1: applying item 1 of Lemma 20 with target p∗t , error parameters ( β t /4, β t /4), gap γ, and parameter Λ = Λt gives us that there exists an integer ct such that for ρt = λℓ (ct , β t /4)/p∗t , we have (1) Halting: if λt ≥ ρt and pt ≥ p∗t , then Pr[Kt ≤ ct ] ≤ β t /4. (2) Continuation: if λt ≤ ρt Λt and pt ≤ p∗t /(γΛt ), then Pr[Kt ≥ ct + 1] ≤ β t /4. (3) Base rate upper bound ρt = O(ln(1/β t )/((γ − 1)2 p∗t )), and lower bound ρt ≥ (1/p∗t ) ln(4/β t ) . Similarly, if st = −1: item 2 of Lemma 20 applied to the negated mechanism with target 1 − p∗t , error parameters ( β t /4, β t /4), gap γ, parameter Λ = Λt gives us that there exists an integer ct such that for ρt = λr (ct , β t /4)/(1 − p∗t ), we have (1) Halting: if λt ≤ ρt and 1 − pt ≤ 1 − p∗t ⇔ pt ≥ p∗t , then Pr[Kt ≥ ct + 1] ≤ β t /4. (2) Continuation: if λt ≥ ρt /Λt and 1 − pt ≥ γΛt (1 − p∗t ) ⇔ pt ≤ 1 − γΛt (1 − p∗t ), then Pr[Kt ≤ ct ] ≤ β t /4. 24

(3) Base rate: ρt = O(ln(1/β t )/((γ − 1)2 (1 − p∗t ))), and lower bound ρt ≥ (1/(1 − p∗t )) ln(4/β t ). Flipping rule. The direct execution guarantees continuation at Mt ( Xt ) for pt ≤ p∗t /(γΛt ) and the flipped execution for pt ≤ 1 − γΛt (1 − p∗t ). The analyst may select whichever threshold is larger for a better test. Writing x = γΛt ≥ 1,
p∗t (1 − p∗t )( x − 1)( x − p∗t /(1 − p∗t )) − 1 − x (1 − p∗t ) = . x x Since x ≥ 1, the sign is determined by x − p∗t /(1 − p∗t ). It follows that the direct path has a higher rejection threshold when γΛt ≥ p∗t /(1 − p∗t ), equivalently γΛt (1 − p∗t ) ≥ p∗t , and the flipped path is better otherwise. Therefore, to achieve the stated accuracy bound, the analyst can therefore set ( +1 where γΛt (1 − p∗t ) > p∗t st = −1 otherwise, achieving continuation at pt ≤ max( p∗t /(γΛt ), 1 − γΛt (1 − p∗t )) = p̄t . Sample complexity. Condition on G0 := {η1 ≤ µ1 } ⊃ G , which holds with probability at least 1 − β/4. On G0 , µ1 − η1 ≥ 0 and eε t (µ1 −η1 ) ≤ eε t µ1 = (4/β)(1+2/θ )ε t /ε . Write wt := eε t η2,t ∼ Par(σt ) with σt = 1/(ε t τ2 ) = ε/(ε t (θ + 2)), independently across steps by Lemma 12 (1). We show that λt ≤ Ãt · wt on G0 for all t, where Ãt is defined below. On the direct path (st = +1): λt = ρt eε t (µ1 −η1 ) wt ≤ ρt eε t µ1 wt . By the base rate upper bound (Lemma 20), ρt eε t µ1 = O(eε t µ1 ln(t/β)/( p∗t (γ − 1)2 )). On the flipped path (st = −1): on G0 , λt = ρt e−ε t (µ1 −η1 +η2,t ) ≤ ρt since µ1 − η1 ≥ 0 and η2,t ≥ 0. By the base rate upper bound, ρt = O(ln(t/β)/((1 − p∗t )(γ − 1)2 )). Since wt ≥ 1, we have λt ≤ ρt ≤ ρt wt . Define  εtµ  e 1 ln(t/β) 1 · max Ãt := C A · , . ( γ − 1)2 p∗t 1 − p∗t eε t µ1 ln(t/β)

ln(t/β)

On the direct path, ρt eε t µ1 = O( p∗ (γ−1)2 ), and on the flipped path, ρt = O( (1− p∗ )(γ−1)2 ). Let C ′ t t be the constant for which both of these big-Oh expressions are explicit upper bounds. It follows that for C A = max(γ C ′ , 2), λt ≤ Ãt wt . Substituting eε t µ1 = (4/β)(1+2/θ )ε t /ε gives the stated expression for Ãt ; since this bound holds conditioned on G0 , it holds on G . Failure probability accounting. We apply a union bound across all points of failure - the probability of the event G not holding, and the probability of a type I or type II error at any time-step. ∞

∞

Pr[G c ] + ∑ Pr[Type I Error at t | G] + ∑ Pr[Type II Error at t | G] ≤ β. | {z } t =1 t =1 | {z } | {z } ≤ β/2 ≤ β/4

≤ β/4

The bound on the first term comes from the application of lemma 19 at the beginning of this proof, and the bounds on the second and third terms come from the application of lemma 20 with type I and type II failure probabilities β t /4. □ Lemma 22 (Sample complexity). Under the hypotheses and parameter settings of Theorem 21, assume β ≤ 1/e, and let N≤T := ∑tT=1 Nt denote the total number of evaluations through step T. The following hold. 25

(1) Per-step bound. Conditioned on G , for all t ≥ 1, the Poisson mean satisfies λt ≤ λ̄t , where     C A ln(t/β) Λt 1 λ̄t := max · max ∗ , , ln(4/β t ) . ( γ − 1)2 pt 1 − p∗t In particular, Pr[ Nt > e λ̄t | G] ≤ β t /4. (2) Amortized bound. Assume additionally that ε t = ε 1 and p∗t = p∗ are constant across steps, that σ := ε/(ε 1 (θ + 2)) > 1, and that T ≥ 2 ln(16/β). Define Λ0 := (4/β)(1+2/θ )ε 1 /ε and   C A ln( T/β) Λ0 1 R := · max ∗ , . ( γ − 1)2 p 1 − p∗ Then with probability at least 1 − β/2,   2σ N≤T ≤ R + O R · T 1/σ−1 β−1/σ . T σ−1 Proof. Throughout, C A = max(γ C ′ , 2) is the constant defined in the proof of Theorem 21, where C ′ is the base rate upper bound constant from Lemma 20. In particular, C A ≥ γ C ′ and C A ≥ 2. C ln(t/β)

Item 1. We show λt ≤ A(γ−1)2 max(Λt /p∗t , 1/(1 − p∗t )) on G , which implies λt ≤ λ̄t since λ̄t is defined as the maximum of this expression and ln(4/β t ). From the proof of Theorem 21, conditioned on G , λt ≤ ρt Λt when st = +1 and λt ≤ ρt when st = −1. By the base rate upper bound from Lemma 20, ρt ≤ C ′ ln(t/β)/((γ − 1)2 p∗t ) when st = +1 and ρt ≤ C ′ ln(t/β)/((γ − 1)2 (1 − p∗t )) when st = −1. Case st = +1. The bound on λt is: λt ≤ ρt Λt ≤

C ′ Λt ln(t/β) . p∗t (γ − 1)2

The flipping rule selects st = +1 only when γΛt (1 − p∗t ) > p∗t , which rearranges to 1/(1 − p∗t ) < γΛt /p∗t . Therefore the max is controlled by the first term:   Λt 1 Λt max , ≤ γ· ∗. ∗ ∗ pt 1 − pt pt Since C A ≥ γ C ′ , we conclude λt ≤ p∗t )). Case st = −1. The bound on λt is:

C ′ Λt ln(t/β) p∗t (γ−1)2

λt ≤ ρt ≤

) ) Λt ≤ CA(γln−(1t/β · p∗ ≤ CA(γln−(1t/β max(Λt /p∗t , 1/(1 − )2 )2 t

C ′ ln(t/β) . (1 − p∗t ) (γ − 1)2

The flipping rule selects st = −1 when γΛt (1 − p∗t ) ≤ p∗t , which rearranges to Λt /p∗t ≤ 1/(γ(1 − p∗t )) ≤ 1/(1 − p∗t ). Therefore the max equals the second term:   1 1 Λt max , = . ∗ ∗ pt 1 − pt 1 − p∗t C ′ ln(t/β)

C ln(t/β)

C ln(t/β)

Since C A ≥ C ′ , we conclude λt ≤ (1− p∗ )(γ−1)2 ≤ A(γ−1)2 · 1−1p∗ = A(γ−1)2 max(Λt /p∗t , 1/(1 − t t p∗t )). Tail bound. Since λ̄t ≥ ln(4/β t ) by definition, and Nt ∼ Po(λt ) with λt ≤ λ̄t on G , by stochastic dominance Nt ⪯ Po(λ̄t ) on G . By Lemma 55 (upper tail), Pr[Po(λ̄t ) > e λ̄t ] ≤ e−λ̄t . Since λ̄t ≥ ln(4/β t ), e−λ̄t ≤ β t /4. Therefore Pr[ Nt > e λ̄t | G] ≤ β t /4. 26

Item 2. The proof proceeds in four stages: we use the Pareto decomposition from Theorem 21 to write ∑t λt as a weighted sum of i.i.d. Pareto random variables, then apply truncation, Chebyshev, and Poisson concentration. Setup. By Item 3 of Theorem 21, on the event G0 = {η1 ≤ µ1 } (which holds with probability at least 1 − β/4), we have λt ≤ Ãt wt for all t, where wt ∼ Par(σt ) independently across steps. Since ε t = ε 1 is constant, σt = ε/(ε 1 (θ + 2)) = σ for all t, so the wt are i.i.d. Par(σ ). Since p∗t = p∗ is constant and (4/β)(1+2/θ )ε t /ε = (4/β)(1+2/θ )ε 1 /ε = Λ0 for all t, the expression for Ãt from Theorem 21 specializes to   Λ0 1 C A ln(t/β) · max ∗ , Ãt = . ( γ − 1)2 p 1 − p∗ We bound Ãt from above and below. First, since ln(t/β) ≤ ln( T/β) for t ≤ T,   C A ln( T/β) Λ0 1 Ãt ≤ · max ∗ , = R. ( γ − 1)2 p 1 − p∗ Second, since C A ≥ 2, (γ − 1)2 ≤ 1 (as γ ∈ (1, 2]), max(Λ0 /p∗ , 1/(1 − p∗ )) ≥ 1 (as Λ0 ≥ 1 and p∗ ≤ 1), and ln(t/β) ≥ ln(1/β) ≥ 1 (as β ≤ 1/e), we have Ãt ≥ C A · 1 · 1 · 1 ≥ 2. Define B := ∑tT=1 Ãt and Amax := maxt≤T Ãt . By the two properties above, Amax ≤ R and B ≤ T R. Truncation. Define W := (16T/β)1/σ and w̃t := min(wt , W ). Since Pr[wt > W ] = W −σ = β/(16T ) for each t, a union bound gives Pr[∃ t ≤ T : wt > W ] ≤ T · β/(16T ) = β/16. On the complementary event, wt = w̃t for all t ≤ T, so ∑tT=1 λt ≤ ∑tT=1 Ãt wt = ∑tT=1 Ãt w̃t . Chebyshev. Since the w̃t are i.i.d. and the Ãt are deterministic on G0 : " # T T σ B, E ∑ Ãt w̃t = ∑ Ãt E[w̃t ] ≤ σ − 1 t =1 t =1 where we used E[w̃t ] ≤ σ/(σ − 1) from Lemma 12 (3a). For the variance, since the w̃t are independent: ! T

Var

∑ Ãt w̃t

t =1

T

T

t =1

t =1

= ∑ Ã2t Var(w̃t ) ≤ Var(w̃) · Amax · ∑ Ãt = Var(w̃) · Amax · B,

where Var(w̃) := Var(w̃1 ) is bounded by Lemma 12 (3b). By Chebyshev’s inequality, # " T Var(w̃) · Amax · B σ B+u ≤ . Pr ∑ Ãt w̃t > σ−1 u2 t =1 p Setting the right-hand side equal to β/16 and solving: u := 4 Var(w̃) · Amax · B/β. Since Amax ≤ R and B ≤ T R, u2 ≤ 16 Var(w̃) T R2 /β. By Lemma 12 (3b), Var(w̃) ≤ 2−2 σ W 2−σ when 1 < σ < 2, Var(w̃) ≤ 2 ln W + 1 when σ = 2, and Var(w̃) ≤ σ/(σ − 2) when σ > 2. Substituting W = (16T/β)1/σ and dividing by T: u/T = O( R · T 1/σ−1 β−1/σ ) when 1 < σ < 2 (and strictly smaller when σ ≥ 2). σ Poisson concentration. Recall B := ∑tT=1 Ãt and define M := σ− 1 B + u. On the event that T ∑t=1 λt ≤ M (which holds with probability at least 1 − β/16 − β/16 by the truncation and Chebyshev bounds), the total sample count N≤T = ∑tT=1 Nt ∼ Po(∑tT=1 λt ) ⪯ Po( M ) by Poisson additivity and stochastic dominance. Since T ≥ 2 ln(16/β), we have M/4 ≥ T/2 ≥ ln(16/β), so 27

e− M/4 ≤ e−T/2 ≤ β/16. Therefore Pr[Po( M ) > 2M ] ≤ e− M/4 ≤ β/16, where the first inequality is by Lemma 54 (upper tail) with u = M. On the complementary event:   2M 2σ B 2u 2σ N≤T ≤ = · + ≤ R + O R · T 1/σ−1 β−1/σ . T T σ−1 T T σ−1 Failure probability. The total failure probability is the sum of four terms: Pr[G0c ] ≤ β/4, Pr[truncation fails] ≤ β/16, Pr[Chebyshev fails] ≤ β/16, and Pr[Po( M ) > 2M ] ≤ β/16. The total is at most β/4 + 3β/16 < β/2. □ 4.2. GTM with Ex-post privacy guarantee. The drawback of the choice of parameters τ1 , τ2,t , and µ1 in Theorem 21 is the worst-case polynomial decay in accuracy forced by the Λt factor, which equals essentially (t/β)Θ(ε t /ε) (see Theorem 21). In this subsection, we present a different choice of parameters leading to different tradeoffs. More specifically, Theorem 23 below circumvents this poor scaling with the length of the stream by allowing the ratio of the output privacy parameter ε to the input privacy parameter ε t to scale as ln(t/β). With this scaling, the Λt slack factor is bounded from above by a constant. We describe Theorem 23 as an ex-post privacy loss guarantee, but it can be achieved in two ways: either (a) the input privacy parameter is forced to decay logarithmically or (b) the output privacy parameter is allowed to grow logarithmically. Both these settings have natural applications. The setting in (a) is most reasonable for our application in reducing optimization under continual observation to the batch setting, as described later in Section 7, and gives us a standard uniform privacy loss bound. The setting in (b) is the standard setting for ex-post privacy loss guarantees, and is well suited for potential applications in hyperparameter optimization. It allows Algorithm 1 to achieve a privacy loss bound that scales only logarithmically with the length of the stream. Further, if the whole stream is processed without halting at any step, then the privacy loss is constant instead of growing with the input length. Theorem 23 (Ex-post privacy guarantee). Fix a gap parameter γ ∈ (1, 2], a failure probability β ∈ (0, 1), privacy parameters ε C and a constant CH > 0. Define  ε t /ε C 4 Λt := · e2/CH . β Define the rejection threshold  p∗t ∗ p̄t := max , 1 − γΛt (1 − pt ) . γΛt 

There exists a parameter setting for Algorithm 1 for which we achieve an ex-post privacy guarantee with privacy loss function ( ε C + CH ε t ln(4/β t ) if at = st ε̃(( a1 , . . . , at )) = . εC if at = −st Further, with probability 1 − β, for all t ≥ 1, (1) Halting. At every step t where pt ≥ p∗t , the algorithm halts. (2) Continuation. The algorithm continues past every step t satisfying pt ≤ p̄t . (3) Sample complexity. The number of evaluations of the mechanism Mt at each step satisfies    Λ ln ( t/β ) t   if γΛt (1 − p∗t ) > p∗t , O ∗ 2 p ( γ − 1 )  t  Nt ≤ ln(t/β)   if γΛt (1 − p∗t ) ≤ p∗t . O (1 − p∗t ) (γ − 1)2 28

Note that, as in the case of Theorem 21, the gap parameter γ controls the trade-off between the rejection threshold and the per-step sample complexity. The sample complexity grows as ln(t/β) per step, identical to Theorem 21; what improves is the gap between the thresholds p∗t and p̄t . Proof of Theorem 23. The proof follows the same structure as Theorem 21, with the following parameter changes. In the initialization of Algorithm 1, set 1/τ1 = ε C and µ1 = ln(4/β)/ε C = τ1 ln(4/β), so that Pr[η1 > µ1 ] = β/4. At each step t, set τ2,t = 2/(CH ε t ln(4/β t )). Privacy. The result follows using Lemma 17 and observing that 1/τ1 = ε C and 1/τ1 + 2/τ2,t = ε C + CH ε t ln(4/β t ) for any t ≥ 1. Bounding λt . Apply Lemma 19 with cG = 1/4. Since e−µ1 /τ1 = β/4 and cG ∑t β t = β/4, we have Pr[G c ] ≤ β/2. The choice of τ2,t ensures exact cancellation:  ε t /ε C
4 2 ε t τ2,t ln(4/β t ) = , Λt = exp ε t (µ1 + τ2,t ln(1/(cG β t ))) = · e2/CH . CH β Lemma 19 (part (2)) shows that conditioned on G , for all time-steps t and any choice of ρt , if st = +1 then λt ∈ [ρt , ρt Λt ], and if st = −1 then λt ∈ [ρt /Λt , ρt ]. Further, part (3) in Lemma 19 shows that, when η1 ≤ µ1 , then λt ≥ ρt when st = +1 and λt ≤ ρt when st = −1. Accuracy. We analyze the case depending on st = −1 or st = +1 separately. When st = +1, then applying Lemma 20 (case (1)) with target p∗t , error parameters ( β t /6, β t /6), gap γ, parameter Λt gives us that there exists an integer ct such that for ρt = λℓ (ct , β t /6)/p∗t , we have (1) Halting: if λt ≥ ρt and pt ≥ p∗t , then Pr[Kt ≤ ct ] ≤ β t /6. (2) Continuation: if λt ≤ ρt Λt and pt ≤ p∗t /(γΛt ), then Pr[Kt ≥ ct + 1] ≤ β t /6. (3) Base rate: ρt = O(ln(6/β t )/((γ − 1)2 p∗t )). Similarly, if st = −1, then Lemma 20 (case (2)) applied to the negated mechanism with target 1 − p∗t , error parameters ( β t /6, β t /6), gap γ, parameter Λt gives us that there exists an integer ct such that for ρt = λr (ct , β t /6)/(1 − p∗t ), we have (1) Halting: if λt ≤ ρt and 1 − pt ≤ 1 − p∗t , then Pr[Kt ≥ ct + 1] ≤ β t /6. (2) Continuation: if λt ≥ ρt /Λt and 1 − pt ≥ γΛt (1 − p∗t ), then Pr[Kt ≤ ct ] ≤ β t /6. (3) Base rate: ρt = O(ln(6/β t )/((γ − 1)2 (1 − p∗t ))). Flipping rule. The direct path guarantees continuation at pt ≤ p∗t /(γΛt ) and the flipped path at pt ≤ 1 − γΛt (1 − p∗t ). When ε t and p∗t are constant, Λt is time-independent, the flipping rule is the same at every step. Writing x = γΛt ≥ 1,  
p∗t (1 − p∗t )( x − 1)( x − p∗t /(1 − p∗t )) (1 − p∗t )( x − 1) p∗t ∗ − 1 − x (1 − p t ) = = x− . x x x (1 − p∗t ) Since x ≥ 1, the sign is determined by x − p∗t /(1 − p∗t ) = γΛt − p∗t /(1 − p∗t ). It follows that the direct path has a higher rejection threshold when γΛt (1 − p∗t ) ≥ p∗t , and the flipped path is better otherwise. The analyst sets st = +1 when γΛt (1 − p∗t ) > p∗t and st = −1 otherwise, achieving continuation at pt ≤ max( p∗t /(γΛt ), 1 − γΛt (1 − p∗t )) = p̄t . Sample complexity. Conditioned on G , Nt ∼ Po(λt ) with λt ≤ λ̄t , where ( ρ t Λ t s t = +1 λ̄t = ρt st = −1. We claim that λ̄t ≥ ln(6/β t ) in both cases. On the direct path, λ̄t ≥ λℓ (ct , β t /6)/p∗t ≥ λℓ (ct , β t /6) ≥ ct + ln(6/β t ) ≥ ln(6/β t ), where the third inequality is from (3) and the fourth uses ct + 1 > 2 ln(6/β t ) from Lemma 11(2). 29

On the flipped path (selected only when p∗t ≥ 1/2), the gap condition of Lemma 11(1) gives r λ (ct , β t /6) ≥ λℓ (ct , β t /6)/γ, and since λℓ (ct , β t /6) ≥ 2 ln(6/β t ) and γ ≤ 2, we have λ̄t = λr (ct , β t /6)/(1 − p∗t ) ≥ ln(6/β t )/(1 − p∗t ) ≥ ln(6/β t ). Conditioned on G , λt ≤ λ̄t , so by stochastic dominance of Po(λt ) by Po(λ̄t ), and the upper tail of the multiplicative Poisson Chernoff bound (Lemma 55), Pr[ Nt ≥ e λ̄t | G] ≤ e−λ̄t ≤ β t /6. Substituting the base rates, we get    Λt ln(t/β)   s t = +1 O(ρt Λt ) = O 2 p∗t (γ −   1) Nt = ln(t/β)   st = −1. O (1 − p∗t )(γ − 1)2 Failure probability accounting. We apply a union bound across all points of failure - the probability of the event G not holding, the probability of a type I or type II error at any time-step, and the probability of the sample complexity bound failing. ∞

∞

∞

Pr[G c ] + ∑ Pr[Type I Error at t | G] + ∑ Pr[Type II Error at t | G] + ∑ Pr[ Nt ≥ e λ̄t | G] ≤ β. | {z } t =1 t =1 t =1 {z } {z } {z } | | | ≤ β/2 ≤ β/6

≤ β/6

≤ β/6

□ 5. P URIFICATION In this section, we formally prove a simple purification lemma that allows us to convert approximate DP mechanisms to pure ones with minimal perturbation to their accuracy. As mentioned in the introduction, this technique of using randomized response as post-processing to purify approximate-DP mechanisms with finite co-domains is attributed to folklore by [HC22]. We give complete proofs for ease of reference. Lemma 24 (Purification). Let M : X → {+1, −1} be an (ε 1 , δ1 )-DP mechanism, X, X ′ ∈ X a pair of neighboring data sets, and p′ = Pr[M( X ′ ) = +1].

p = Pr[M( X ) = +1]

f : X → {+1, −1} that for any input dataset X ′′ evaluates a ← Define the ϕ-smoothed mechanism M ′′ M( X ) and passes a through a binary symmetric channel with crossover probability ϕ. That is, we draw an independent bit b ∼ Ber(ϕ) and output − a if b = 1, and a if b = 0. Let f X ′ ) = +1]. pe′ = Pr[M(

f X ) = +1] pe = Pr[M(

. The following statements are true: (1) pe = p + ϕ(1 − 2p), and if ϕ ≤ 1/2, then pe ≥ pe′ ⇔ p ≥ p′ . (2) Assuming ϕ ≤ 1/2, if for some c ≥ 1, ϕ≥

δ1 ecε 1 − 1 + 2δ1

f is (c · ε 1 , 0)-DP. then the ϕ-smoothed mechanism M (3) In particular, setting δ1 ϕ= ε e 1 − 1 + 2δ1 f is ε 1 -DP and that | pe − p| ≤ δ1 /ε 1 . we have that M 30

Proof.

f, the output probabilities are convex combinations: (1) By the definition of M

(13)

pe = (1 − ϕ) p + ϕ(1 − p) = (1 − 2ϕ) p + ϕ.

The mapping p 7→ pe is affine. If ϕ ≤ 1/2, then the coefficient of p is non-negative, and this mapping is order preserving, so pe ≥ pe′ ⇔ p ≥ p′ . (2) Since M is (ε 1 , δ1 )-DP, p ≤ eε 1 p′ + δ1 . Since ϕ ≤ 1/2, we are guaranteed that 1 − 2ϕ ≥ 0, and it follows that pe ≤ (1 − 2ϕ)(eε 1 p′ + δ1 ) + ϕ
= eε 1 (1 − 2ϕ) p′ + δ1 (1 − 2ϕ) + ϕ. Using the relation (1 − 2ϕ) p′ = pe′ − ϕ, we rewrite this entirely in terms of the smoothed probabilities: pe ≤ eε 1 ( pe′ − ϕ) + δ1 (1 − 2ϕ) + ϕ

= eε 1 pe′ + δ1 (1 − 2ϕ) − ϕ(eε 1 − 1). To ensure strict cε 1 -indistinguishability for any c ≥ 1, we require pe ≤ ecε 1 pe′ . Thus, it is sufficient that the residual terms satisfy δ1 (1 − 2ϕ) − ϕ(eε 1 − 1) ≤ (ecε 1 − eε 1 ) pe′ . Since c ≥ 1, the right-hand side is non-negative and monotonically increasing with respect to pe′ . Therefore, it suffices for the inequality to hold at the minimum possible valid value, which is pe′ = ϕ. δ1 (1 − 2ϕ) − ϕ(eε 1 − 1) ≤ (ecε 1 − eε 1 )ϕ

⇔ δ1 − 2ϕδ1 − ϕeε 1 + ϕ ≤ ϕecε 1 − ϕeε 1 ⇔ δ1 ≤ ϕ(ecε 1 − 1 + 2δ1 ). Rearranging for ϕ yields the generalized bound. (3) Substituting c = 1 gives us the relevant expression for ϕ. The bound on the perturbation follows from a direct calculation: δ1 ≤ δ1 /ε 1 . | p̃ − p| = |ϕ(1 − 2p)| ≤ ε e 1 − 1 + 2δ1 □ Corollary 25 (Approximate DP inputs). Suppose each mechanism Mt is (ε t , δt )-DP with δt ≥ 0. For each t, apply Lemma 24 with c = 1 and crossover ϕt = δt /(eε t − 1 + 2δt ) to obtain a pure ε t -DP ft . Run Algorithm 1 on the purified stream with targets ( p∗ )t≥1 . Then Theorems 21 and 23 mechanism M t apply to the purified stream, and their guarantees transfer to the original success probabilities pt as follows. Write ϕt < δt /ε t for the purification slack at step t. (1) Halting (Theorems 21 and 23). The algorithm halts at every step t where pt ≥ p∗t + ϕt . (2) Continuation (Theorems 21 and 23). The algorithm continues past every step t where pt ≤ p̄t − ϕt , where p̄t is the rejection threshold from the relevant theorem. (3) Privacy and sample complexity are unchanged. Since ϕt ≤ δt /ε t , the perturbation to the acceptance and rejection thresholds p∗t and p̄t is asymptotically negligible and all bounds match their pure-DP counterparts up to lower-order terms. Proof. By Lemma 24(3), the purified success probability satisfies | pet − pt | ≤ ϕt ≤ δt /ε t . Items 1 and 2 follow from the triangle inequality: pt ≥ p∗t + ϕt implies pet ≥ pt − ϕt ≥ p∗t , and pt ≤ p̄t − ϕt implies pet ≤ pt + ϕt ≤ p̄t . Sample complexity is unchanged since each purified evaluation requires exactly one evaluation of Mt plus one independent coin flip. □ 31

6. L OWER B OUNDS We establish lower bounds for the generalized private tester by reduction from the classical Above Threshold problem [DR14, Chapter 3]. We first prove a per-step lower bound for Above Threshold, then lift it to a multi-step bound by an averaging argument. We finally transfer it to the generalized testing problem via the Laplace mechanism. Standard threshold test. Let ε > 0, δ ≥ 0 and let X denote the data universe with a fixed symmetric adjacency relation. Let X ∈ X be the private input of the testing mechanism. A (standard) threshold test receives a sensitivity-1 query f : X → R, a public threshold τ ∈ R, and outputs a ∈ {−1, +1}. We consider a sequence of such queries f 1 , f 2 , . . . presented in an online fashion, where at = +1 denotes halting and at = −1 denotes continuation. We say an ε-differentially private threshold test has global accuracy (α+ , α− , β) if, with probability at least 1 − β over the algorithm’s randomness, for all t ≥ 1: f t ( X ) ≥ τ + α+ =⇒ at = +1,

f t ( X ) ≤ τ − α− =⇒ at = −1.

We first show that for two datasets X0 and X1 such that the probability of M ( X0 ) = 1 is clearly less than 1/2 and the probability of M ( X1 ) = 1 is clearly above 1/2, then X0 and X1 must have “large enough” distance d in the adjacency relation. Definition 26. (1) Let M : X → {−1, +1} be an (ε, δ)-differentially private mechanism. (2) Let X0 = Y0 , Y1 , . . . , Yd = X1 be a chain of neighboring datasets with Yj and Yj+1 neighboring for each j. (3) Define h j := Pr[ M (Yj ) = +1], δ′ := δ/(eε − 1), u j := h j + δ′ , and v j := (1 − h j ) + δ′ . Note u j + v j = 1 + 2δ′ for all j, and δ + δ′ = eε δ′ . Lemma 27 (Acceptance probability propagation). For all j ∈ {0, . . . , d − 1}: (1) e−ε u j ≤ u j+1 ≤ eε u j . (2) e−ε v j ≤ v j+1 ≤ eε v j . Proof. Item 1. Since Yj and Yj+1 are neighboring, and M is (ε, δ)-DP, h j+1 ≤ eε h j + δ, so u j+1 = h j+1 + δ′ ≤ eε h j + δ + δ′ = eε (h j + δ′ ) = eε u j . The other bound follows by flipping the role of Yj and Yj+1 . Item 2. Similarly, by reasoning about the −1 output, we have that (1 − h j ) ≤ eε (1 − h j+1 ) + δ, so v j = (1 − h j ) + δ′ ≤ eε (1 − h j+1 ) + δ + δ′ = eε ((1 − h j+1 ) + δ′ ) = eε v j+1 . As before, the other bound follows by flipping the role of Yj and Yj+1 . □ Lemma 28. If Pr[ M( X0 ) = +1] ≤ βI and Pr[ M( X1 ) = +1] ≥ 1 − βII for some βI , βII ≥ 0 with βI + δ′ < 1/2 and βII + δ′ < 1/2, then   1 1 1 (14) log + log − 1. d ≥ ε 2( βI + δ ′ ) 2( βII + δ′ ) In particular, when δ = 0 this reduces to d ≥ 1ε (log 2β1 I + log 2β1II ) − 1. Proof. By assumption, u0 ≤ βI + δ′ < 1/2. Since βII + δ′ < 1/2, we have ud = hd + δ′ ≥ (1 − βII ) + δ′ > 1/2. Since u j+1 ≤ eε u j , there exists k ∈ {0, . . . , d − 1} with uk ≤ 1/2 ≤ uk+1 . From uk + vk = 1 + 2δ′ , it follows that vk ≥ 1/2 + 2δ′ ≥ 1/2. Applying u j+1 ≤ eε u j from j = 0 to j = k gives 1 ≤ u k +1 ≤ e ( k +1) ε u 0 ≤ e ( k +1) ε ( β I + δ ′ ), 2 so k + 1 ≥ 1ε ln 2( βI1+δ′ ) . 32

By assumption, vd ≤ βII + δ′ . Applying v j ≤ eε v j+1 from j = k to j = d − 1 gives 1 ≤ vk ≤ e(d−k)ε vd ≤ e(d−k)ε ( βII + δ′ ), 2 so d − k ≥ 1ε ln 2( βII1+δ′ ) . Adding the two gives d + 1 = (k + 1) + (d − k ) ≥ 1ε (log 2( βI1+δ′ ) + log 2( βII1+δ′ ) ).

□

We next show a lower bound on any (ε, δ)-differentially private standard threshold test Theorem 29 (Lower bound for standard private threshold testers). Let A be an (ε, δ)-differentially private standard threshold test with global accuracy (α+ , α− , β) over T steps. Define δ′ := δ/(eε − 1). If β + δ′ < 1/2, then   T 1 1 (15) log + log − 2. α+ + α− ≥ ε 2( β + Tδ′ ) 2( β + δ ′ ) Proof. Fix queries f 1 , . . . , f T of sensitivity 1 with disjoint support in the dataset, i.e. the entries of X that affect f t are disjoint from those affecting f t′ for t ̸= t′ . Recall that τ is the public threshold. Let X0 be a dataset with f t ( X0 ) = τ − α− for all t. For each t ∈ [ T ], write Ht ( X ) for the event that the algorithm when run on a dataset X ∈ X reaches step t and halts there, i.e., a[t] = (−1, . . . , −1, +1). When A is run on X0 , global accuracy gives ∑tT=1 Pr[ Ht ( X0 )] ≤ β, so by averaging there exists ∗ t ∈ [ T ] with Pr[ Ht∗ ( X0 )] ≤ β/T. Let X1 be the dataset obtained from X0 by modifying only the entries in the support of f t∗ so that f t∗ ( X1 ) = τ + α+ . Since f t∗ has sensitivity 1, the datasets X0 and X1 are at distance ⌈α+ + α− ⌉ in the adjacency relation. By the disjointness of the support, f t ( X1 ) = τ − α− for all t ̸= t∗ . When A is run on X1 , global accuracy requires that no error occurs at any step with probability at least 1 − β; since the only step with f t ≥ τ + α+ is t = t∗ , this implies Pr[ Ht∗ ( X1 )] ≥ 1 − β. Define the mechanism M ( X ) := +1 if Ht∗ ( X ) occurs when A is run with dataset X on the query sequence f 1 , . . . , f T , and M ( X ) := −1 otherwise. This mechanism is (ε, δ)-DP by post-processing. Applying Lemma 28 to M with βI = β/T, βII = β, and d = ⌈α+ + α− ⌉ ≤ α+ + α− + 1 gives   1 T 1 log + log − 2. □ α+ + α− ≥ ε 2( β + Tδ′ ) 2( β + δ ′ ) Corollary 30 (Lower bound for generalized private testers). Fix a target threshold p∗ ∈ (0, 1), a constant input privacy parameter ε 1 > 0, and an output privacy guarantee (ε, δ). Let A be a generalized private tester (Definition 1) for ε 1 -DP input mechanisms with global accuracy β ≤ 1/2 over T steps. Define δ′ := δ/(eε − 1), suppose β + δ′ < 1/2, and let p̄ denote the background threshold of the tester. Define ε 1 /ε  1 T −2ε 1 · . Λ0 : = e · 2( β + Tδ′ ) 2( β + δ′ ) Then: (1) If p∗ , p̄ ≤ 1/2, then p∗ / p̄ ≥ Λ0 . (2) If p∗ , p̄ ≥ 1/2, then (1 − p̄)/(1 − p∗ ) ≥ Λ0 . (3) If p̄ < 1/2 < p∗ , then 1/(4 p̄(1 − p∗ )) ≥ Λ0 . These bounds imply a simplified unified description in terms of the odds ratios of p∗ and p̄ unconditionally. p ∗ / (1 − p ∗ ) ≥ Λ0 . p̄/(1 − p̄) 33

Proof. Fix sensitivity-1 queries f 1 , . . . , f T with disjoint support, a dataset X, and a parameter τL ∈ R. For each t, define Mt by the mechanism that when given input X, evaluates f t ( X ), draws ν ∼ Lap(1/ε 1 ), and outputs +1 if f t ( X ) + ν ≥ τL , and −1 otherwise. Each Mt is ε 1 -DP, and disjoint support ensures that changing the entries affecting f t∗ does not alter Mt for t ̸= t∗ . The success probability pt = Pr[Mt ( X ) = +1] satisfies ( 1 −ε (τ − f (X )) t 1 L if f t ( X ) ≤ τL , 2e pt = 1 −ε 1 ( f t ( X )−τL ) 1− 2 e if f t ( X ) > τL . Note that pt ≤ 1/2 iff f t ( X ) ≤ τL . For p ∈ (0, 1), define the quantile function Q( p) := τL + q( p) where   1 log(2p) if p ≤ 1/2, ε1 q( p) :=  1 log 1 if p > 1/2. ε1 2(1− p ) It follows that pt = p exactly when f t ( X ) = Q( p). Note that q( p) is continuous, strictly increasing, and satisfies q(1/2) = 0. Note that f t ( X ) = Q( p∗ ) gives pt = p∗ and f t ( X ) = Q( p̄) gives pt = p̄. With α+ = 0 and α− = Q( p∗ ) − Q( p̄) = q( p∗ ) − q( p̄), feeding the mechanisms Mt into the generalized tester A yields an (ε, δ)-DP (standard) threshold test with global accuracy β over T steps. Applying Theorem 29:   1 T 1 ∗ (16) log + log − 2. q( p ) − q( p̄) = α+ + α− ≥ ε1 2( β + Tδ′ ) 2( β + δ ′ ) Multiplying both sides by ε 1 and exponentiating, the right-hand side becomes Λ0 . We now evaluate ε 1 (q( p∗ ) − q( p̄)) in each case. Note that by the definition of the generalized private testing the case p∗ < p̄ cannot happen. Case 1: p∗ , p̄ ≤ 1/2. ε 1 (q( p∗ ) − q( p̄)) = log(2p∗ ) − log(2 p̄) = log

p∗ . p̄

Therefore p∗ / p̄ ≥ Λ0 . Case 2: p∗ , p̄ ≥ 1/2. ε 1 (q( p∗ ) − q( p̄)) = log

1 1 1 − p̄ − log = log . 2(1 − p ∗ ) 2(1 − p̄) 1 − p∗

Therefore (1 − p̄)/(1 − p∗ ) ≥ Λ0 . Case 3: p̄ < 1/2 < p∗ . ε 1 (q( p∗ ) − q( p̄)) = log

1 1 − log(2 p̄) = log . ∗ 2(1 − p ) 4 p̄(1 − p∗ )

Therefore 1/(4 p̄(1 − p∗ )) ≥ Λ0 . Unified bound via the odds ratio. In all three cases, the per-case bound implies a lower bound on the p ∗ / (1− p ∗ ) 1− p̄ odds ratio p̄/(1− p̄) . In Case 1, since p∗ ≥ p̄ and both are at most 1/2, we have 1− p∗ ≥ 1, so p ∗ / (1 − p ∗ ) p∗ 1 − p̄ p∗ = · ≥ ≥ Λ0 . p̄/(1 − p̄) p̄ 1 − p∗ p̄ 34

p∗

In Case 2, since p∗ ≥ p̄ and both are at least 1/2, we have p̄ ≥ 1, so p ∗ / (1 − p ∗ ) p∗ 1 − p̄ 1 − p̄ = · ≥ ≥ Λ0 . ∗ p̄/(1 − p̄) p̄ 1 − p 1 − p∗ In Case 3, since p∗ > 1/2 and p̄ < 1/2, we have p∗ (1 − p̄) > 1/4, so p ∗ / (1 − p ∗ ) p∗ (1 − p̄) 1 = > ≥ Λ0 . ∗ p̄/(1 − p̄) p̄(1 − p ) 4 p̄(1 − p∗ ) Therefore, in all cases, (17)

p ∗ / (1 − p ∗ ) ≥ Λ0 . p̄/(1 − p̄)

□ 6.1. Sample complexity lower bounds. We now turn to lower bounds on the number of evaluations that any generalized private tester must perform. Theorem 31 (Expected sample complexity lower bound). Fix p∗ ∈ (0, 1/2], a constant input privacy parameter ε 1 > 0, and output privacy parameters (ε, δ) with δ′ := δ/(eε − 1). Let A be a generalized private tester (Definition 1) with per-step Type I and Type II error probabilities βIt and βIIt at step t, with βIt ≤ 1/4 and βIIt + δ′ < 1/2. Then there exists an input instance on which the expected number of evaluations of Mt at step t satisfies e−ε 1 . 4 p∗ (2( βIIt + δ′ ))ε 1 /ε

E[ Nt ] ≥ −ε

When δ = 0, this simplifies to E[ Nt ] ≥ 4 p∗ (e2βII1 )ε 1 /ε . t

Proof. We use the Laplace mechanism construction from the proof of Corollary 30. Fix sensitivity1 queries f 1 , . . . , f T with disjoint support and a threshold τL , and define Mt ( X ) = sgn( f t ( X ) + Lap(1/ε 1 ) − τL ). As in that proof, construct a chain of datasets X (0) , X (1) , . . . , X (k) differing only in the support of f t , with X ( j) and X ( j+1) neighboring, f t ( X ( j) ) = f t ( X (0) ) − j, and f t′ ( X ( j) ) = f t′ ( X (0) ) ( j) for all t′ ̸= t. Choosing f t ( X (0) ) = τL + ε11 ln(2p∗ ) gives pt = p∗ e− jε 1 ≤ 1/2 for all j ≥ 0. Write h j := Pr[ at = st | Xt = X ( j) ] and v j := (1 − h j ) + δ′ .

Step 1: propagation of acceptance probability. The mapping Xt 7→ at is (ε, δ)-DP by the definition of a generalized private tester (Definition 1), and post-processing. The Type II accuracy guarantee gives h0 ≥ 1 − βIIt , so v0 ≤ βIIt + δ′ . Set k = ⌊ 1ε ln 2( βII1+δ′ ) ⌋, so that ekε ≤ 2( βII1+δ′ ) . Iterating Item 2 of t

t

Lemma 27 gives vk ≤ ekε v0 ≤ ekε ( βIIt + δ′ ) ≤ 1/2. It follows that hk = 1 + δ′ − vk ≥ 1 + δ′ − 1/2 ≥ 1/2. Step 2: bounding the joint probability of halting with no positive evaluations. Let Kt := N ∑i=t 1 1[yt,i = +1] denote the number of +1 outcomes among the Nt evaluations. Let R denote all internal randomness of the algorithm at step t. Conditioned on R = r and the event that all evaluation outcomes are −1, the algorithm follows a deterministic execution path: it performs some number of evaluations n⊥ (r ) and produces an output a⊥ (r ) ∈ {−st , st }, both determined by r alone. We can write Pr[ at = st , Kt = 0 | pt , R = r ] = Pr[Kt = 0 | pt , R = r ] · Pr[ at = st | pt , R = r, Kt = 0] 35

Since Pr[Kt = 0 | pt , R = r ] = (1 − pt )n⊥ (r) and Pr[ at = st | pt , R = r, Kt = 0] = 1[ a⊥ (r ) = st ], by the law of total probability over R, h i Pr[ at = st , Kt = 0 | pt ] = E (1 − pt )n⊥ ( R) 1[ a⊥ ( R) = st ] . R

Since (1 − pt )n⊥ ( R) is non-increasing in pt for each R, the joint probability is non-increasing in pt . In the Laplace construction, p′ can be made arbitrarily small (and in particular smaller than p̄t ) by taking f t ( X ) sufficiently small. For any such p′ ≤ p̄t , the Type I accuracy guarantee gives Pr[ at = st | p′ ] ≤ βIt . Therefore: (18)

Pr[ at = st , Kt = 0 | pk ] ≤ Pr[ at = st , Kt = 0 | p′ ] ≤ Pr[ at = st | p′ ] ≤ βIt .

Step 3: lower bound on E[Kt | pk ]. Decomposing the acceptance probability at pt = pk : 1 ≤ hk = Pr[ at = st , Kt = 0 | pk ] + Pr[ at = st , Kt ≥ 1 | pk ] 2 ≤ βIt + Pr[Kt ≥ 1 | pk ]. Therefore Pr[Kt ≥ 1 | pk ] ≥ 1/2 − βIt ≥ 1/4, and since Kt is a non-negative integer-valued random variable: 1 E[Kt | pk ] ≥ Pr[Kt ≥ 1 | pk ] ≥ . 4 Step 4: from E[Kt ] to E[ Nt ]. Conditioned on the algorithm’s internal randomness R = r, the evaluations of Mt ( Xt ) are i.i.d. Ber( pk ), and Nt is a stopping time with respect to the filtration generated by the evaluation outcomes. By Wald’s equation (see, e.g., [MU05, Theorem 12.3]), E[Kt | pk , R = r ] = pk · E[ Nt | pk , R = r ]. Taking expectations over R: E[Kt | pk ] = pk · E[ Nt | pk ]. Combining with Step 3: E[ Nt | pk ] =

E[ Kt | p k ] 1 ≥ . pk 4 pk

Since k ≥ 1ε ln 2( βII1+δ′ ) − 1: t

pk = p∗ e−kε 1 ≤ p∗ eε 1 (2( βIIt + δ′ ))ε 1 /ε ,

□

and the result follows.

Remark 32 (Comparison with the amortized upper bound). With δ = 0 and global accuracy β, the Type II error satisfies βIIt ≤ β at every step, so Theorem 31 gives E[ Nt ] = Ω(1/( p∗ βε 1 /ε )) per step. The amortized sample complexity upper bound (Lemma 22), for σ ≥ 2) gives N≤T /T = (1/β)ε 1 /(θε) ln( T/β)

σ O( σ− ). Both scale as (1/β)Θ(ε 1 /ε) /p∗ , matching up to the ln( T/β)/(γ − 1)2 fac1 · p ∗ ( γ −1)2 tor and constants in the exponent on 1/β. 36

7. R EDUCTION FROM O PTIMIZATION UNDER C ONTINUAL O BSERVATION TO THE B ATCH S ETTING In this section we present the meta-algorithm B ATCH T O CO that converts any batch differentially private optimization algorithm into one that operates under continual observation. We recall the problem setting formally in Section 7.1, some technical preliminaries in Section 7.2, and the algorithm B ATCH T O CO in Section 7.3. We prove its privacy and accuracy guarantee in Section 7.4 and Section 7.5, and then show in Section 8 how to construct various CO algorithms for problems of interest using B ATCH T O CO. 7.1. Problem Setup. Maximization problems. Let X denote the data universe. An (insertiononly) data stream is a sequence of datasets X1 , X2 , . . . ∈ X such that Xt+1 is obtained from Xt by inserting a single data element at time t + 1. Let Y denote a set of candidate solutions. A maximization problem is specified by a function f : X × Y → R≥0 . We write OPT( X ) := maxY ∈Y f ( X, Y ). We consider problems f that have bounded sensitivity, i.e. for all neighboring datasets X, X ′ (differing in one element) and all Y ∈ Y ,

| f ( X, Y ) − f ( X ′ , Y )| ≤ 1. Private maximization under continual observation. We study optimization in the continual observation setting for bounded sensitivity maximization problems f that in addition satisfy data monotonicity, i.e. for all Y ∈ Y and all t ≥ 1, f ( Xt , Y ) ≤ f ( Xt+1 , Y ). We write OPTt := maxY ∈Y f ( Xt , Y ) for the optimum at time t. Data monotonicity implies that OPTt is non-decreasing. By bounded sensitivity, OPTt+1 ≤ OPTt + 1. The goal is to produce, at every time t, a solution Yt ∈ Y such that, with probability at least 1 − β simultaneously for all t ≥ 1, f ( Xt , Yt ) ≥ Φ · OPTt − Etotal (t), where Φ ∈ (0, 1] is a constant multiplicative approximation factor and Etotal (t) ≥ 0 is additive error incurred at time t. The output sequence (Yt ) must satisfy (ε, δ)-differential privacy, where ε and δ are prescribed global budgets. Here two streams ( Xt )t≥1 and ( Xt′ )t≥1 are considered neighboring if for all t, Xt ∼ Xt′ . A multiplicative approximation is a standard relaxation introduced for dealing with optimization problems f that are NP-hard, and additive error is a consequence of working in the private setting. Prior work [GLM+ 10, CNN23] proves lower bounds showing that for problems like submodular maximization additive error is unavoidable. Batch DP algorithm guarantee. We will construct algorithms for private maximization under continual observation by starting with a DP algorithm that works in the static i.e. batch setting. A batch DP algorithm A takes as input a dataset X ∈ X , a privacy parameter ε > 0, an approximateDP parameter δ ≥ 0, and a failure probability β A ∈ (0, 1), and returns a solution Ŷ ∈ Y . The algorithm A is (ε, δ)-DP. We consider two kinds of accuracy guarantees: • High-probability: There exists some α ∈ (0, 1] and some function E A such that with probability at least 1 − β A , f ( X, A( X )) ≥ α · OPT( X ) − E A ( X, ε, δ, β A ). • In-expectation: E[ f ( X, A( X ))] ≥ α · OPT( X ) − E A ( X, ε, δ). We write E A (t) as shorthand for E A evaluated at the parameters in effect at time t. 7.2. Preliminaries. 1. Converting in-expectation guarantees to bounded error probability guarantees. We use the following lemma to reduce reasoning about algorithms with in-expectation guarantees, to reasoning about algorithms with constant bounded error probabilities. 37

Lemma 33 (In-expectation to bounded-error conversion). Let f : X × Y → R≥0 and let A be a randomized algorithm satisfying E[ f ( X, A( X ))] ≥ α · OPT( X ) − E for some α ∈ (0, 1] and E ≥ 0. Then for any c ∈ (0, 1), writing α′ := (1 − c)α and β c := 1 − cα,   Pr f ( X, A( X )) ≥ α′ · OPT( X ) − E ≥ 1 − β c . Proof. Set τ := α′ · OPT( X ) − E. If τ ≤ 0, the bound holds since f ≥ 0. For τ > 0, we can write α · OPT( X ) − E ≤ E[ f ( X, A( X ))]

≤ τ Pr[ f ( X, A( X )) < τ ] + OPT( X ) Pr[ f ( X, A( X )) ≥ τ ] = τ + (OPT( X ) − τ ) Pr[ f ( X, A( X )) ≥ τ ]. In the above, we use that f ( X, A( X )) ∈ [0, OPT( X )] unconditionally. Rearranging: α · OPT( X ) − E − τ OPT( X ) − τ α · OPT( X ) − E − α′ · OPT( X ) + E = OPT( X ) − α′ · OPT( X ) + E cα · OPT( X ) . = (1 − α′ ) · OPT( X ) + E

Pr[ f ( X, A( X )) ≥ τ ] ≥

Since τ > 0 implies E < α′ · OPT( X ), cα · OPT( X ) ≥ cα = 1 − β c . (1 − α′ ) · OPT( X ) + E

□

2. Generalized Private Selection via Random Stopping [LT19]. We recall one of the variants of the algorithm introduced by [LT19] for Generalized Private Selection, that we refer to as T HRESH OLD S ELECT for convenience. We refer the reader to the arxiv version of their paper [LT18] for the statements and proofs that we refer to here. T HRESHOLD S ELECT takes as input query access to an (ε 1 , δ1 )-DP mechanism Q that for datasets X ∈ X outputs pairs of elements and scores (Y, v) ∈ Y × R. It is also given a threshold τ ∈ R, and parameters ξ ∈ (0, 1] and ε 0 ∈ [0, 1]. It computes a number of iterations T that is the maximum number of times it will query A. It then proceeds to iterate over a counter j ∈ [ T ], and draw values (Yj , v j ) ← Q( Xt ). It checks whether v j ≥ τ, i.e. whether the score beats the given threshold, and outputs (Yj , v j ) if so. If this check fails, then it performs a randomized check by drawing b ∼ Ber(ξ ). If b = +1, then this check is considered to have failed, and T HRESHOLD S ELECT halts immediately, outputting −1 indicating failure. If b = −1, then this check has passed and the algorithm continues to iterate over j. If all T iterations result in no successful threshold test, then the algorithm outputs −1. T HRESHOLD S ELECT can be used as a success probability amplification algorithm. When it is known that the probability of Q outputting a value (Y, v) such that v beats τ with probability at least p1 , then by setting ξ to scale roughly as βp1 , we are guaranteed that Q will output a value that beats the threshold τ with probability 1 − β. Further, the privacy cost of this procedure is roughly (O(ε 1 ), O(δ1 /ξ )), in other words the privacy cost of success probability amplification is borne almost entirely by the additive privacy loss parameter in the approximate DP setting, and just the constant factor overhead in the multiplicative privacy loss parameter in the pure DP setting. Further, the sample complexity can in fact be bounded in terms of a Geometric distribution with stopping probability at least p1 . Lemma 34 (Thresholded Private Selection [LT18, Theorem 3.1]). Let Q : X → Y × R be an (ε 1 , δ1 ) DP mechanism. Fix ξ ∈ (0, 1], ε 0 ∈ (0, 1], and T ≥ max 1ξ ln ε20 , 1 + eξ1 . 38

Input: Dataset X ∈ X , Mechanism Q : X → Y × R; threshold τ ∈ R; ξ ∈ (0, 1], parameter ε 0 ∈ [0, 1]. Output: A sample (Y, v) ∈ Y × R, or −1. T ← ⌈max{(1/ξ ) ln(2/ε 0 ), 1 + 1/(eξ )}⌉; for j = 1, . . . , T do (Yj , v j ) ← Q( X ); if v j ≥ τ then return (Yj , v j ); Draw b ∼ Ber(ξ ), if b = +1, return −1; end return −1; Algorithm 2: T HRESHOLD S ELECT (Algorithm 1, Thresholding with a known threshold τ in the arXiv version of [LT18])
(1) Privacy. The output of Algorithm 2 is 2ε 1 + ε 0 , 3e2ε 1 +ε 0 · δ1 /ξ -differentially private. When δ1 = 0, this simplifies to (2ε 1 + ε 0 , 0)-DP. (2) Failure probability. Let p1 := Pr(Y,v)∼Q(X ) [v ≥ τ ]. Then Pr[output = −1] ≤

(1 − p1 )(1 + ε 0 /2) ξ. p1

(3) Sample complexity. The number of draws from Q is at most T. Let p1 := Pr(Y,v)∼Q(X ) [v ≥ τ ]. The number of draws is stochastically dominated by a Geo( p1 (1 − ξ ) + ξ )-distributed random variable. Proof. Items 1 and 2 are parts (b), (c), and (e) of [LT18, Theorem 3.1] respectively. Item 3 follows directly from the proof of part (d) of [LT18, Theorem 3.1]; in each iteration, the algorithm makes an evaluation of Q that succeeds with probability at least p1 . If this evaluation fails, then the algorithm halts with probability ξ. These two Bernoulli draws are independent of each other. Therefore, the probability of halting in any one iteration is exactly p1 (1 − ξ ) + ξ. It follows that the total number of evaluations is dominated by Geo( p1 (1 − ξ ) + ξ ). □ 3. Simplified GTM. We briefly recall a simplified version of Theorem 23 that we will refer to in our reduction from optimization in the CO setting to the batch setting. Corollary 35 (GTM with ExPost parameters). Fix a threshold probability p∗ ∈ (0, 1), a gap parameter γ ∈ (1, 2], and suppose β GTM ≤ 1/e and C1 , CH > 0. There exists a GTM instance (Algorithm 1) such that if ε t ≤ ε/(C1 ln(4/(ωt β GTM ))) for all t ≥ 1, then the following hold with p̄ := p∗ /(γΛ), where Λ := e1/C1 +2/CH is a universal constant (independent of t and β GTM ). (1) Privacy. The GTM transcript is (1 + CH /C1 )ε-differentially private. (2) Accuracy. With probability at least 1 − β GTM , simultaneously for all t ≥ 1: (a) the algorithm halts at every step t where pt ≥ p∗ + δt /ε t , and (b) the algorithm continues past every step t where pt ≤ p̄ − δt /ε t . When δt = 0, the thresholds simplify to p∗ and p̄. (3) Sample complexity. With probability at least
1 − β GTM , the number of evaluations of Mt at step t is at most O ln(t/β GTM )/( p∗ (γ − 1)2 ) . Proof. Apply Theorem 23 with ε C = ε, β = β GTM , and st = +1 for all t. The hypothesis on ε t gives Λt = (4/β GTM )ε t /ε C · e2/CH ≤ (4/β GTM )1/(C1 ln(4/(ωt β GTM ))) · e2/CH ≤ e1/C1 +2/CH . It follows that 39

p̄t = p∗ /(γΛt ) ≥ p∗ /(γΛ) so it follows that p̄ := p∗ /(γΛ) suffices for the rejection threshold. Items 1 and 3 follow directly from Theorem 23; the sample complexity uses Λt ≤ Λ = O(1). The δt /ε t perturbation in Item 2 follows from Corollary 25. □ 7.3. Algorithm description. We can now introduce B ATCH T O CO (Algorithm 3) that takes as input black-box access to a mechanism A that solves a maximization problem f : X × Y → R≥0 in the batch DP setting, and constructs a mechanism that solves the same problem in the CO setting. We will show in Theorem 42 that B ATCH T O CO fulfills the same sort privacy guarantee as A, i.e. pure or approximate. Further, it fulfills an error bound for the dataset Xt that scales with the error incurred by A on Xt when initialized with privacy parameters ε t = Ω(ε/ ln2 (t/β)), δt = Ω̃(δ/ ln2 t), plus some slow scaling polylogarithmic error terms. Additionally, with probability 1 − β, for all t ≥ 1, the per-round sample complexity, i.e. evaluations of A, is at most Õ(ln(t/β)). Inputs and Outputs. A run of B ATCH T O CO proceeds as follows. It is given as input black-box access to a batch DP mechanism A : X → Y to which it can feed the input dataset Xt at any point t in the input data stream, and privacy parameters ε t and δt . Every time it evaluates A, it is guaranteed that the evaluation is (ε t , δt )-DP. It will output a sequence of values (Yt )t≥1 ∈ Y ∗ . Checkpoints. Algorithm 3 defines a sequence of increasing time-steps called checkpoints, denoted (t(ℓ))ℓ≥1 ∈ N∗ over the course of the stream. Checkpoints are time-steps at which Algorithm 3 will update its output solution; at time-steps which are not checkpoints, the solution output will be the solution output at the previous checkpoint. t(1) := 1, i.e. the first time-step is always the first checkpoint, and at the very beginning of the stream, with the dataset X1 , we make a call to the batch algorithm A to generate the very first output Y1 . All subsequent outputs will be determined as explained below. Calls to GTM. After having identified the (ℓ − 1)-th checkpoint, Algorithm 3 identifies the ℓth checkpoint via an invocation of GTM (Algorithm 1), with the parameter setting indicated by Corollary 35. We refer to this instance as GTM ℓ . It defines a threshold hℓ = (1 + κ )ℓ , and conducts the threshold test: 1( f ( Xt , Ŷ ) + Lap(2/ε t ) − hℓ ≥ 0),

Ŷ ← A( Xt , ε t /2, δt ).

In other words, it checks whether the utility obtained from a value Ŷ drawn from the batch algorithm A for the dataset Xt beats the ℓ-th threshold hℓ . Since A is randomized, this is a probabilistic check, and by adding a draw from the Laplace distribution Lap(2/ε t ), we will have the promise that f ( Xt , Ŷ ) + Lap(2/ε t ) is (ε t , δt )-DP. It follows that we can define a single evaluation of this probabilistic test as the t-th input Mt ( Xt ) to GTM ℓ . Since neighboring data streams ( Xt )t≥1 and ( Xt′ )t≥1 fulfill the promise that there is at most one time-step t such that the new elements xt and xt′ inserted at that time-step are unequal, it follows that Xt and Xt′ are neighboring at all time-steps. It follows from the privacy guarantee of GTM ℓ that this invocation fulfills a pure privacy guarantee. We set the output privacy parameter to be a value ε ℓ such that ∑∞ ℓ=2 ε ℓ < ε, and the acceptance threshold p∗ = Θ(1), i.e. some constant to be determined later. It follows from Corollary 35, that by setting ε t = Θ(ε ℓ(t) / ln(t/β)), we are guaranteed that all invocations ( GTM ℓ )ℓ≥2 are ∑ℓ≥2 ε(ℓ)-DP, and it will suffice to set ε(ℓ) = Θ(ε/ℓ ln2 ℓ). This holds even for approximate DP A because of the internal purification by GTM (see Corollary 35); the additive privacy loss parameters affect only the accuracy of the threshold tests. With high probability, GTM ℓ will halt if the test passes with probability at least p∗ + δt /ε t , and it will not halt if pt ≤ p̄ − δt /ε t = p∗ /γΛ − δt /ε t , for some user-defined constants γ and Λ. Here 40

pt is the probability of the t-th threshold test passing, i.e. pt := Pr[ f ( Xt , A( Xt , ε t /2, δt )) + Lap(2/ε t ) ≥ (1 + κ )ℓ ]. To absorb the δt /ε t terms, we introduce a constraint on δt to be at most ε t · p̄/2. Modulo the additive error introduced by the Laplace noise, this implies that if GTM ℓ outputs at = −1, then f ( Xt , Ŷ ) + Lap(2/ε t ) cannot be greater than (1 + κ )ℓ with probability greater than p∗ + δt /ε t . Similarly, if at = +1, then f ( Xt , Ŷ ) + Lap(2/ε t ) cannot be smaller than (1 + κ )ℓ with probability greater than 1 − p̄ + δt /ε t . Since the δt /ε t terms are negligible, this guarantee promises that if GTM ℓ indicates continuation, then it is safe to repeat the previous checkpoint’s solution whilst ensuring accuracy competitive with what the batch algorithm A would achieve on the dataset Xt with privacy parameter (ε t , δt ). Further, since at = +1 only when pt ≥ p̄ − δt /ε t , and since the thresholds (1 + κ )ℓ increase exponentially with ℓ whereas f ( Xt , ·) can only increase at most linearly with t (due to 1-sensitivity), it will follow that with high probability, only some O(ln(t/β))-many checkpoints are defined by time-step t. Since checkpoints are declared at a low rate, the privacy parameters passed to the active instance of GTM ℓ scale slowly, and the invocations of the batch algorithm also get slowly-decaying privacy-loss parameters (ε t , δt ) as t increases. Putting everything together, we are guaranteed high accuracy in the threshold tests. Calls to T HRESHOLD S ELECT. When a new checkpoint is declared, we know that the previous checkpoint’s solution is no longer competitive with (1 + κ )ℓ , and a new solution must be generated. If we make a single invocation to A and set Yt to equal its output, we are only guaranteed that it beats (1 + κ )ℓ with probability p̄ − δt /ε t . To amplify the success probability, we make a call to the generalized private selection algorithm T HRESHOLD S ELECT (Algorithm 2) to generate a new solution for release, with threshold set equal to (1 + κ )ℓ . We will refer to this invocation of T HRESHOLD S ELECT as T HRESHOLD S ELECT ℓ . It will follow that as long as T HRESHOLD S ELECT ℓ makes at least ≈ 1/ p̄ many evaluations, at least one draw will exceed the updated threshold (1 + κ )ℓ , and this solution is selected and output by Algorithm 2. Again, there is some error introduced by Laplace noise added to privatize the score of each draw, but this again turns out to give us a lower order error term. B ATCH T O CO guarantees. To sum up, the privacy guarantee of B ATCH T O CO follows by basic composition over the very first call to the batch algorithm A, and the subsequent invocations of ( GTM ℓ )ℓ≥2 and ( T HRESHOLD S ELECT ℓ )ℓ≥2 . The accuracy guarantee of B ATCH T O CO follows from the accuracy of the tests conducted by the invocations of GTM, and the quality of the solutions generated by the invocations of T HRESHOLD S ELECT. The total sample complexity of B ATCH T O CO turns out to be essentially O(ln(t/β)), due to the sample complexity of the ex-post parameter setting with which GTM is used, and the relatively mild stopping probability ξ = Θ̃( p̄) with which T HRESHOLD S ELECT is invoked; since p̄ = Ω(1), this implies a relatively small number of calls until the threshold check passes and a solution may be output. The outline of the rest of this section is as follows. In Definition 36 and Lemma 37 we define the mechanisms constructed from A that we pass to the instances of GTM and T HRESHOLD S E LECT , and prove accuracy and privacy guarantees for them. Lemma 38 proves that B ATCH T O CO is (ε, δ)-DP. Lemma 39 shows that when GTM ℓ outputs at = −1, then the quality of values generated by A cannot be much more than (1 + κ )ℓ , and that if at = +1, then OPTt cannot be much less than (1 + κ )ℓ . Lemma 40 uses the latter guarantee to show that the number of checkpoints scales logarithmically in the length of the stream. Lemma 41 shows that when a checkpoint is reached, and a value is generated via T HRESHOLD S ELECT ℓ , then its quality is not too much less than (1 + κ )ℓ . Finally, theorem 42 puts everything together to formally prove the privacy, accuracy, and sample complexity guarantees of B ATCH T O CO, and Corollary 43 and Corollary 44 show 41

how to derive concrete accuracy bounds when the batch algorithm A is known to satisfy an accuracy guarantee with bounded error probability β A , or just an in-expectation accuracy guarantee, respectively. We collect the parameters and derived quantities used in B ATCH T O CO and its analysis. The pseudocode appears in Algorithm 3; the quantities below are referenced throughout Sections 7.4 and 7.5. Input parameters.

• ε < 1, δ ∈ [0, 1): global privacy budget. • A: batch DP algorithm, (ε, δ)-DP for any given (ε, δ). • p∗ ∈ (0, 1/2]: target halting threshold for the GTM. In the high-probability setting, p∗ = (1 − β A )/2 where β A is the failure probability of A; in the in-expectation setting with slack c, p∗ = cα/2. • κ > 0: parameterizes the scaling of the geometric sequence of thresholds hi = (1 + κ )i . • γ ∈ (1, 2]: parameter in calls to GTM that controls the trade-off between the rejection threshold and per-step sample complexity. • β ∈ (0, 1/e): global failure probability. Weight sequence. We fix a sequence (ωi )i≥1 with ∑i∞=1 ωi ≤ 1. We use ωk = Cω /(k ln2 (k + 1)), for an appropriate normalization constant Cω . Constants. The following constants are set to satisfy the privacy and accuracy constraints established in Lemma 38 and Lemma 41:

• C1 > 0, CH > 0: control the ex-post privacy decay rate in Corollary 35.The per-step privacy parameter within GTM instance ℓ is ε t = ε(ℓ)/(C1 ln(4/(ωt β))). • Cε = C1 /(C1 + CH + 3) < 1: scaling parameter for the per-checkpoint privacy budget, so that ε(ℓ) = Cε · ωℓ · ε (see per-checkpoint quantities below). Chosen so that the combined privacy cost of the ℓ-th GTM instance and the corresponding T HRESHOLD S ELECT call is at most ωℓ ε (see Lemma 38). • Cβ ≤ 1/3: scaling parameter for the per-instance failure probability, so that β ℓ = Cβ · ωℓ · β (see per-checkpoint quantities below). The constraint Cβ ≤ 1/3 ensures that T HRESHOLD S ELECT succeeds with sufficiently high probability at each checkpoint (see Lemma 41). • Cδ = 1 + 3e3 /Cβ : scaling parameter for the per-instance δ budget, ensuring that the total additive privacy loss across all checkpoints is at most δ (see Lemma 38). Derived quantities from the GTM. From Corollary 35:

• Λ = e1/C1 +2/CH . Depends only on C1 and CH ; independent of t, β, and the data. • p̄ = p∗ /(γΛ): the rejection threshold. The GTM continues past step t whenever pt ≤ p̄ − δt /ε t . Since p∗ ≤ 1/2 and γΛ > 1, we have p̄ < 1/2. Per-checkpoint quantities. For each GTM instance ℓ ≥ 2:

• ε(ℓ) = Cε · ωℓ · ε: the privacy budget allocated to instance ℓ. • β ℓ = Cβ · ωℓ · β: the failure probability allocated to instance ℓ. By definition of ωℓ , ∑ℓ≥2 β ℓ ≤ Cβ β. • ξ ℓ = p̄ · β ℓ : the stopping probability parameter for T HRESHOLD S ELECT at checkpoint ℓ. Per-step quantities. For GTM instance ℓ at time t:

• ε(ℓ, t) = ε(ℓ)/(C1 · ln(4/(ωt β))): the privacy parameter for evaluations of the test and scored mechanisms at time t. The decay in t is required by Corollary 35 to keep Λt ≤ Λ. 42

Input: Output privacy parameters ε < 1, δ ∈ [0, 1); batch-DP algorithm A; target threshold p∗ ∈ (0, 1/2]; parameters κ > 0, γ ∈ (1, 2]; failure probability β ∈ (0, 1/e). Output: At each time t, a solution Yt ∈ Y . Define for all i, t ≥ 1:; h i : = (1 + κ ) i ; ε(i ) := Cε · ωi · ε; β i := Cβ · ωi · β; ξ i := p̄ · β i ;
ε(i, t) := ε(i ) / C1 · ln(4/(ωt β)) ; δ(i, t) := min( p̄ · ωi2 · β · δ/Cδ , ( p̄/2) · ε(i, t)); ε 1 ← ε(1, 1); δ1 ← δ(1, 1); Ycur ← A( X1 , ε 1 , δ1 ); Y1 ← Ycur ; ℓ ← 2; GTM ℓ .Init(ε(ℓ), p∗ , β ℓ ); for t = 2, 3, . . . do ε t ← ε(ℓ, t); δt ← δ(ℓ, t); at ← GTM ℓ .Step(Mthℓ , Xt , ε t , δt ); if at = −1 then Yt ← Ycur ; else Ŷ ← T HRESHOLD S ELECT (Qt , hℓ , ξ ℓ , min(ε t , 1)); if Ŷ ̸= −1 then Ycur ← Ŷ; Yt ← Ycur ; ℓ ← ℓ + 1; GTM ℓ .Init(ε(ℓ), p∗ , β ℓ ); end end Algorithm 3: Batch-to-Continual-Observation Meta-Algorithm

• δ(ℓ, t) = min( p̄ ωℓ2 β δ/Cδ , ( p̄/2) · ε(ℓ, t)): the approximate-DP parameter at time t. The first term in the min-expression ensures the total additive privacy loss across checkpoints is at most δ; the second ensures δt /ε t ≤ p̄/2, which absorbs the δt /ε t perturbation in the GTM accuracy guarantee. Batch algorithm parameters at time t. Suppose there are ℓ − 1 checkpoints before time-step t. The batch algorithm A is called with privacy parameters ε t /2 = ε(ℓ, t)/2 and δt = δ(ℓ, t). Substituting, the effective batch privacy parameter is ε batch (t) =

Cε ωℓ ε , 2C1 ln(4/(ωt β))

and δbatch (t) = δ(ℓ, t) ≤ p̄ ωℓ2 β δ/Cδ = Θ(ωℓ2 β δ). E A ( Xt , ε batch (t), δbatch (t)).

We write E A (t) as shorthand for

Definition 36 (Test and scored mechanisms). Given a batch DP algorithm A, privacy parameters ε t > 0, δt ∈ [0, 1), and a threshold h > 0, define: 43

(1) The test mechanism Mth : X → {−1, +1}: on input Xt , draw Ŷ ← A( Xt , ε t /2, δt ) and return
Mth ( Xt ) := sgn f ( Xt , Ŷ ) + Lap(2/ε t ) − h . (2) The scored mechanism Qt : X → Y × R: on input Xt , draw Ŷ ← A( Xt , ε t /2, δt ) and return
Qt ( Xt ) := Ŷ, f ( Xt , Ŷ ) + Lap(2/ε t ) . Lemma 37 (Properties of the test and scored mechanisms). Let Mth and Qt be as in Definition 36. The following statements hold: (1) Privacy. Both Mth and Qt are (ε t , δt )-differentially private. (2) Test success probability. Let pt := Pr[Mth ( Xt ) = +1]. (a) For any v ≥ h and β A ∈ (0, 1) such that Pr[ f ( Xt , Ŷ ) ≥ v] ≥ 1 − β A for Ŷ ← A( Xt , ε t /2, δt ),

pt ≥ (1 − β A ) 1 − 21 exp − ε2t (v − h) . (b) If h ≥ OPTt , then
pt ≤ 21 exp − ε2t (h − OPTt ) . (3) Score accuracy. Let (Ŷ, v) ∼ Qt ( Xt ). Then for any β′ ∈ (0, 1),   2 1 Pr v − f ( Xt , Ŷ ) > ln ′ = β′ . εt β Proof. Item 1. Each mechanism composes two operations on Xt : (i) A( Xt , ε t /2, δt ), which is (ε t /2, δt )-DP; and (ii) f ( Xt , Ŷ ) + Lap(2/ε t ), which for fixed Ŷ is ε t /2-DP since Xt 7→ f ( Xt , Ŷ ) has sensitivity 1. By basic composition, both mechanisms are (ε t , δt )-DP. Item 2. Write V := f ( Xt , Ŷ ) and L ∼ Lap(2/ε t ) independent of Ŷ. The test returns +1 if and only if V + L ≥ h. For part (a): with probability at least 1 − β A , V ≥ v ≥ h. Conditioned on this event, fixing a draw of V, Pr[V + L ≥ h|V ] = 1 − 21 exp(−ε t (V − h)/2) ≥ 1 − 12 exp(−ε t (v − h)/2). Taking expectation over V, and dropping the conditioning on the event of probability ≥ 1 − β A , the stated bound follows. For part (b): since f ( Xt , Ŷ ) ≤ OPTt unconditionally, V ≤ OPTt ≤ h. For any draw of V, Pr[V + L ≥ h|V ] = 12 exp(−ε t (h − V )/2) ≤ 12 exp(−ε t (h − OPTt )/2). Taking expectation over V gives the stated bound. Item 3. The score is v = f ( Xt , Ŷ ) + L where L ∼ Lap(2/ε t ) is independent of Ŷ. The claim follows from the Laplace tail bound: Pr[| L| > s] = exp(−ε t s/2) for all s ≥ 0. □ 7.4. Privacy. Lemma 38. If β < 1/e, ε < 1, Cε ≤ C1 /(C1 + CH + 3), and Cδ ≥ 1 + 3e3 /Cβ , then Algorithm 3 satisfies (ε, δ)-differential privacy. When δ = 0, the algorithm is ε-DP. Proof. The observable output is determined by: (a) the initialization call to A at time-step t = 1; (b) the GTM transcript within each instance; (c) the T HRESHOLD S ELECT output at each checkpoint; and (d) continuation outputs Yt = Ycur , which are post-processing of (a) and (c). By basic composition, the total privacy cost is the sum of the costs of (a)–(c). 44

Privacy loss per GTM Instance. By Corollary 35, the GTM transcript for instance ℓ is (1 + CH /C1 )ε(ℓ)-DP with δ = 0, since purification is handled internally. Substituting ε(ℓ) = Cε ωℓ ε, we get that each invocation is pure DP with privacy parameter

(1 + CH /C1 ) Cε ωℓ ε.

(19)

Privacy loss per T HRESHOLD S ELECT instance. At checkpoint ℓ, for t = t(ℓ), T HRESHOLD S ELECT (Algorithm 2) draws from Qt , which is (ε t , δt )-DP by Lemma 37. By Lemma 34(1) with ε 1 = ε t , ε 0 = min(ε t , 1), δ1 = δt , and coin-flip probability ξ ℓ , the output is
2ε t + ε 0 , 3e2ε t +ε 0 · δt /ξ ℓ -DP. Since ε t ≤ 1, we have 2ε t + ε 0 ≤ 3ε t and 3e2ε t +ε 0 ≤ 3e3 . For the ε-term, we note the checkpoint occurs at the halting time t = t(ℓ), where ε t(ℓ) = ε(ℓ, t) = ε(ℓ)/(C1 ln(4/(ωt(ℓ) β))). Since ln(4/(ωt(ℓ) β)) ≥ ln(1/β) ≥ 1 (assuming β ≤ 1/e), we get that the ε-term is at most 3 Cε ωℓ ε 3ε(ℓ) = . C1 C1

(20)

For the δ-term, we have that by definition δt ≤ p̄ ωℓ2 β δ/Cδ , and ξ ℓ = p̄ Cβ ωℓ β. It follows that the δ-term is at most (21)

3e3 ·

p̄ ωℓ2 β δ/Cδ δt 3e3 = 3e3 · ω δ. = ξℓ Cβ Cδ ℓ p̄ Cβ ωℓ β

Privacy loss for first checkpoint. The call A( X1 , ε 1 , δ1 ) costs (ε 1 , δ1 ), where ε 1 = ε(1, 1) is at most (22)

Cε ω1 ε/(C1 ln(4/(ω1 β))) ≤ Cε ω1 ε/C1 .

Similarly δ1 = δ(1, 1) which is at most (23)

p̄ ω12 β δ/Cδ ≤ ω1 δ/Cδ ,

using p̄ ω1 β ≤ 1. If A is pure DP and δ has been set equal to 0, then this equals 0. Total multiplicative privacy loss parameter. Summing (19), (20) over ℓ ≥ 2, and adding (22), the net multiplicative privacy loss parameter is at most     ∞ Cε ω1 ε C 3 C 3 + ∑ Cε ωℓ ε 1 + H + ≤ Cε ε 1 + H + . C1 C1 C1 C1 C1 ℓ=2 This is at most ε when Cε ≤ C1 /(C1 + CH + 3). Total additive privacy loss parameter. GTM instances are pure DP, so by summing (21) over ℓ ≥ 2 and adding (23), we have that the additive privacy loss parameter is at most   ∞ ω1 δ 3e3 δ 3e3 +∑ ω δ ≤ 1+ . Cδ C C ℓ Cδ Cβ ℓ=2 β δ This is at most δ when Cδ ≥ 1 + 3e3 /Cβ , and this is true even when δ = 0, as mentioned above. □ 45

7.5. Accuracy. We establish the accuracy of Algorithm 3. The following lemma translates the outcome of the GTM at each step into bounds on OPTt relative to the threshold h. Lemma 39 (Threshold test accuracy). Let p∗ ∈ (0, 1/2] and let p̄ := p∗ /(γΛ) as in Corollary 35. With probability at least 1 − β ℓ over the randomness of the ℓ-th invocation of Algorithm 1: (1) If at = −1 (continuation), then for any v satisfying Pr[ f ( Xt , Ŷ ) ≥ v] ≥ 1 − β A for some β A ≤ 1 − 2p∗ , 1 2 v < h + ln . εt p̄ (2) If at = +1 (halting), then OPTt +

1 2 ln > h. εt p̄

Proof. By Corollary 35, with β GTM = β ℓ , with probability at least 1 − β ℓ the halting and continuation guarantees hold simultaneously for all t. We condition on this event. By the definition of δ(i, t) in Algorithm 3, δt /ε t ≤ p̄/2. Item 1. If at = −1, then by Corollary 35(2a) and δt /ε t ≤ p̄/2, we have pt < p∗ + p̄/2. On the other hand, if v ≥ h, Lemma 37(2a) gives

pt ≥ (1 − β A ) 1 − 12 exp − ε2t (v − h) . For both bounds to hold simultaneously, since (1 − β A ) ≥ 2p∗ and 1 − 21 e−x is increasing in x, setting x ′ := v − h it must be the case that   1 −ε t x′ /2 ∗ < p∗ + p̄/2 2p 1 − e 2 ′ 1 1 p̄ ⇔ 1 − e−ε t x /2 < + ∗ 2 2 4p ′ p̄ ⇔ e−ε t x /2 > 1 − ∗ ≥ p̄, 2p where in the above we use that p̄ ≤ p∗ ≤ 1/2. Taking logarithms, x ′ < (2/ε t ) ln(1/ p̄). If v < h, the bound holds trivially. Item 2. By the contrapositive of Corollary 35(2b): if at = +1, then pt > p̄ − δt /ε t ≥ p̄/2. If h < OPTt , the conclusion holds trivially since (2/ε t ) ln(1/ p̄) > 0. If h ≥ OPTt , then by Lemma 37(2b), pt ≤ 21 exp(− ε2t (h − OPTt )). Combining with pt > p̄/2 and taking logarithms: h − OPTt <

2 1 ln . εt p̄

□

Lemma 40 (Checkpoint count). Under the hypotheses of Lemma 39, with probability at least 1 − ∑ℓ β ℓ ≥ 1 − β (by a union bound over the accuracy guarantees of Corollary 35 across all instances), the number of checkpoints ℓ(t) declared by time t satisfies    1 t 1 1 ℓ(t) = O ln + ln ln + ln ln . ln(1 + κ ) ε β p̄ Proof. Suppose instance ℓ halts at step t(ℓ). By Lemma 39 Item 2, hℓ < OPTt(ℓ) + 46

2 1 ln . ε t(ℓ) p̄

By bounded sensitivity, OPTt(ℓ) ≤ t(ℓ). Substituting ε t(ℓ) = Cε ωℓ ε/(C1 ln(4/(ωt(ℓ) β))), 2 ε t(ℓ)

ln

1 4 1 2C1 · ln · ln . = Cε ωℓ ε ωt(ℓ) β p̄ p̄

We can write ωℓ = Cω /(ℓ ln2 (ℓ + 1)), ℓ ln2 (ℓ + 1) ≤ ℓ3 for ℓ ≥ 1, and t(ℓ) ≤ t. It follows that

(1 + κ )ℓ = hℓ < t + C3 ·

1 ℓ3 ln(t/β) · ln ε p̄

for an absolute constant C3 > 0. Taking logarithms:   1 ℓ3 ln(t/β) · ln ℓ ln(1 + κ ) < ln t + C3 · . ε p̄ Since 3 ln ℓ is eventually dominated by the linear growth of ℓ ln(1 + κ ),    1 1 1 t ln + ln ln + ln ln . ℓ = O ln(1 + κ ) ε β p̄

□

Lemma 41 (Checkpoint quality). Under the hypotheses of Lemma 39, suppose instance ℓ halts at step t(ℓ) and T HRESHOLD S ELECT (Algorithm 2) is run with the scored mechanism Qt(ℓ) (Definition 36), stopping probability parameter ξ ℓ , and threshold hℓ . Then with probability at least 1 − 3ωℓ β, f ( Xt(ℓ) , Ycur ) ≥ hℓ −

4C1 ln(4/(ωt(ℓ) β)) 2C1 ln(4/(ωt(ℓ) β)) 4 1 ln − ln . p̄ Cε ωℓ ε ωℓ β Cε ωℓ ε

Proof. Write t = t(ℓ) throughout. We show that three events each hold with probability at least 1 − ωℓ β. Bound on K Since instance ℓ halted, by Corollary 35(2b) and δt /ε t ≤ p̄/2, the success probability of each draw satisfies pt > p̄ − δt /ε t ≥ p̄/2. By Lemma 34(3), the number of draws K is stochastically dominated by Geo(( p̄/2)(1 − ξ ℓ ) + ξ ℓ ). Since ( p̄/2)(1 − ξ ℓ ) + ξ ℓ ≥ p̄/2, it follows that it is also stochastically dominated by Geo( p̄/2). Setting kmax = ⌈(2/ p̄) ln(1/(ωℓ β))⌉: Pr[K > kmax ] ≤ (1 − p̄/2)kmax ≤ e−( p̄/2)kmax ≤ ωℓ β. Success of T HRESHOLD S ELECT. By Lemma 34(2) with coin-flip probability ξ ℓ = p̄ Cβ ωℓ β, using 1/pt ≤ 2/ p̄, (1 − pt ) ≤ 1, and (1 + ε 0 /2) ≤ 3/2: Pr[output = −1] ≤

3ξ ℓ = 3Cβ ωℓ β ≤ ωℓ β, p̄

where the last inequality holds for Cβ ≤ 1/3. When T HRESHOLD S ELECT succeeds, it returns (Ŷ, v) with v ≥ hℓ . Uniform bound on Laplace noise terms. By Lemma 37(3) applied to each of the first kmax draws with β′ = ωℓ β/kmax , a union bound gives:   2 kmax Pr ∃ j ∈ [kmax ] : |v j − f ( Xt , Ŷj )| > ln ≤ ωℓ β. εt ωℓ β Combining. By a union bound, all three events hold simultaneously with probability at least 1 − 3ωℓ β. On this event: K ≤ kmax (Step 1), so the returned draw has index j ≤ kmax ; its score satisfies v ≥ hℓ (Step 2); and its Laplace noise satisfies |v − f ( Xt , Ŷ )| ≤ (2/ε t ) ln(kmax /(ωℓ β)) (Step 3). Therefore: f ( Xt , Ycur ) ≥ v − |v − f ( Xt , Ŷ )| ≥ hℓ − 47

2 kmax ln . εt ωℓ β

We simplify the additive loss. Since kmax ≤ 1 + (2/ p̄) ln(1/(ωℓ β)) ≤ (4/ p̄) ln(1/(ωℓ β)) for ωℓ β ≤ 1/e: 4 1 1 1 4 kmax ≤ ln + ln ln + ln ≤ 2 ln + ln . ln ωℓ β p̄ ωℓ β ωℓ β ωℓ β p̄ Substituting ε t = Cε ωℓ ε/(C1 ln(4/(ωt β))): f ( Xt , Ycur ) ≥ hℓ −

4C1 ln(4/(ωt β)) 1 2C ln(4/(ωt β)) 4 ln − 1 ln . Cε ωℓ ε ωℓ β Cε ωℓ ε p̄

□

Theorem 42 (Batch-to-Continual-Observation reduction). Let f be a bounded-sensitivity, datamonotone maximization problem, and let A be a batch (ε, δ)-DP algorithm. Fix geometric spacing κ > 0, gap parameter γ ∈ (1, 2], threshold p∗ ∈ (0, 1/2], failure probability β ∈ (0, 1/e), and ε < 1. Run Algorithm 3. For each time t, define VA ( Xt ) := sup{v : Pr[ f ( Xt , A( Xt , ε t /2, δt )) ≥ v] ≥ 2p∗ } , where ε t and δt are the privacy parameters in effect at time t. Then: (1) Privacy. The output sequence (Yt )t≥1 is (ε, δ)-DP. When δ = 0, the output is ε-DP. (2) Accuracy. With probability at least 1 − O( β), simultaneously for all t ≥ 1: !! ln(t/β) 1 1 VA ( Xt ) −O · ln + ln f ( Xt , Yt ) ≥ , 1+κ ωℓ(t) ε ωℓ(t) β p̄ where p̄ = p∗ /(γΛ) and ℓ(t) = O((ln(t/ε) + ln ln(1/β) + ln ln(1/ p̄))/ ln(1 + κ )). (3) Sample complexity. At each step t, the GTM makes O(ln(t/β)/( p∗ (γ − 1)2 )) calls to A. At each checkpoint ℓ, T HRESHOLD S ELECT makes at most O(ln(1/(ωℓ β))/ p̄) calls with probability at least 1 − ωℓ β. Proof. Item 1 is Lemma 38. Probability accounting (Item 2). We condition on the intersection of the following events: • The accuracy guarantee of Corollary 35 holds for every instance. By a union bound: probability ≥ 1 − ∑i β i ≥ 1 − Cβ β. • The checkpoint quality guarantee of Lemma 41 holds at every checkpoint. By a union bound: probability ≥ 1 − 3 ∑i ωi β ≥ 1 − 3β. Total failure ≤ (Cβ + 3) β = O( β). Between-checkpoint argument. Fix t ≥ 2. Let ℓ(t) denote the index of the most recent checkpoint at or before time t, with ℓ(t) = 1 if no checkpoint has been declared (corresponding to the initialization at t = 1). The currently active GTM instance is ℓ(t) + 1. Case ℓ(t) = 1 (no checkpoint declared). Instance 2 has not halted at step t. By Lemma 39 Item 1 with v = VA ( Xt ) and threshold h2 = (1 + κ )2 : VA ( Xt ) < (1 + κ )2 +

1 2 ln . p̄ εt

Since f ( Xt , Yt ) ≥ 0 by non-negativity: f ( Xt , Yt ) ≥

VA ( Xt ) 2 1 − (1 + κ ) − ln . 1+κ (1 + κ )ε t p̄

Substituting ε t = Cε ω2 ε/(C1 ln(4/(ωt β))), the additive loss is O(ln(t/β) ln(1/ p̄)/(ω2 ε) + 1), which is dominated by the general bound. Case ℓ(t) ≥ 2. 48

Step 1: lower bound on hℓ(t) . Instance ℓ(t) + 1 has not halted at step t. By Lemma 39 Item 1 with v = VA ( Xt ) and threshold hℓ(t)+1 = (1 + κ )hℓ(t) : VA ( Xt ) < (1 + κ ) hℓ(t) +

1 2 ln , εt p̄

so hℓ(t) >

(24)

1 2 VA ( Xt ) ln . − 1+κ (1 + κ )ε t p̄

Step 2: checkpoint quality. By Lemma 41 at checkpoint ℓ(t): f ( Xt(ℓ(t)) , Ycur ) ≥ hℓ(t) −

2C1 ln(4/(ωt(ℓ(t)) β)) 4 4C1 ln(4/(ωt(ℓ(t)) β)) 1 ln − ln . Cε ωℓ(t) ε ωℓ(t) β Cε ωℓ(t) ε p̄

Step 3: monotonicity. Data monotonicity gives f ( Xt , Yt ) ≥ f ( Xt(ℓ(t)) , Ycur ). Since t(ℓ(t)) ≤ t, ln(4/(ωt(ℓ(t)) β)) = O(ln(t/β)). Combining. Substituting (24) into Step 2 and applying Step 3. The continuation correction (2/((1 + κ )ε t )) ln(1/ p̄) uses ε t = Cε ωℓ(t)+1 ε/(C1 ln(4/(ωt β))), giving O(ln(t/β) ln(1/ p̄)/(ωℓ(t)+1 ε)), which is absorbed since ωℓ(t)+1 = Θ(ωℓ(t) ). The total additive loss is !! ln(t/β) 1 1 O · ln + ln . ωℓ(t) ε ωℓ(t) β p̄ Checkpoint count. By Lemma 40, ℓ(t) = O((ln(t/ε) + ln ln(1/β) + ln ln(1/ p̄))/ ln(1 + κ )). Sample complexity (Item 3). The per-step GTM cost is Corollary 35(3): O(ln(t/β)/( p∗ (γ − 1)2 )) calls per step. At each checkpoint, by Lemma 41, T HRESHOLD S ELECT makes at most kmax = O(ln(1/(ωℓ β))/ p̄) calls with probability at least 1 − ωℓ β. □ Corollary 43 (High-probability batch guarantee). Under the hypotheses of Theorem 42, suppose additionally that A satisfies f ( X, A( X )) ≥ α · OPT( X ) − E A with probability at least 1 − β A for some β A < 1. Set p∗ = (1 − β A )/2. Then with probability at least 1 − O( β), simultaneously for all t ≥ 1: !! ln(t/β) 1 1 α · OPTt − E A (t) −O · ln + ln , f ( Xt , Yt ) ≥ 1+κ ωℓ(t) ε ωℓ(t) β p̄ 2 βδ ), and p̄ = (1 − where E A (t) is evaluated at ε batch = Θ(ωℓ(t) ε/ ln(t/β)) and δbatch = Θ(ωℓ( t) β A )/(2γΛ).

Proof. Since Pr[ f ( Xt , A( Xt )) ≥ αOPTt − E A (t)] ≥ 1 − β A = 2p∗ , we have VA ( Xt ) ≥ αOPTt − E A (t). The result follows from Theorem 42(2). □ Corollary 44 (In-expectation batch guarantee). Under the hypotheses of Theorem 42, suppose additionally that E[ f ( X, A( X ))] ≥ α · OPT( X ) − E A . Fix a slack c ∈ (0, 1) and set p∗ = cα/2. Then with probability at least 1 − O( β), simultaneously for all t ≥ 1: !! ln(t/β) 1 1 (1 − c)α · OPTt − E A (t) −O · ln + ln , f ( Xt , Yt ) ≥ 1+κ ωℓ(t) ε ωℓ(t) β p̄ 2 βδ ). where p̄ = cα/(2γΛ) and E A (t) is evaluated at ε batch = Θ(ωℓ(t) ε/ ln(t/β)) and δbatch = Θ(ωℓ( t)

Proof. By Lemma 33 with slack c, Pr[ f ( Xt , A( Xt )) ≥ (1 − c)αOPTt − E A (t)] ≥ cα = 2p∗ . Thus VA ( Xt ) ≥ (1 − c)αOPTt − E A (t). The result follows from Theorem 42(2). □ 49

TABLE 3. Application of Theorem 42 to batch DP submodular maximization algorithms. OPT: batch optimum; OPTt : CO optimum at time t; k: cardinality or matroid rank constraint; κ, η > 0: user-defined parameters; β: failure probability. Monotone/non-monotone refers to argument-monotonicity; our framework additionally requires data-monotonicity. For in-expectation batch guarantees, Corollary 44 is applied with small constant c > 0. Work, Setting

Batch Guarantee

CO Guarantee (Ours)

[MBKK17] Monotone, (ε, δ)-DP, k-Card.

(1− 1e )OPT − Õ k ε ln m ln 1δ

[RY20] Monotone, (ε, δ)-DP, k-Card.

(1− 1e )OPT − Õ kε3 m ln m

[CNZ21] Decomp. non-mon. (ε, δ)-DP, k-Card.

k ln m ln 1δ ( 1e −η )OPT − Õ ηε

1/e−η 3 t k 1 1+κ OPTt − Õ ηκε ln β ln m ln δ

Decomp. non-mon. (ε, δ)-DP, k-Matroid

k ( 1e −η )OPT − Õ ηε ln m ln 1δ

1/e−η 3 t k 1 1+κ OPTt − Õ ηκε ln β ln m ln δ

[GKK+ 24] Decomp. monotone ε-DP, k-Card., η ∈(0, 1)

(1− 1e −η )OPT − O

k ln m/β
ε

1−1/e−η k OPTt − Õ κε ln3 βt ln m 1+κ β

Decomp. monotone ε-DP, k-Matroid, η ∈(0, 1)

(1− 1e −η )OPT − O

k ln m/ηβ
ε

1−1/e−η k m ln3 βt ln ηβ OPTt − Õ κε 1+κ

3/2

7

3 1−1/e k3/2 1 1+κ OPTt − Õ κε ln t ln m ln δ

6 1−1/e k7 1+κ OPTt − Õ κε3 m ln m ln t

8. A PPLICATIONS Our batch-to-continual-observation reduction (Theorem 42) has many applications. In this section, we cover some of them in detail. 8.1. Submodular maximization. For a natural number m ∈ N, we let U = {1, 2, · · · , m} be the universe. A set function f : 2U 7→ R is submodular if

∀S ⊆ T ⊆ U

and

v ∈ U \ T,

f (S ∪ {v}) − f (S) ≥ f ( T ∪ {v}) − f ( T ).

In the problem of submodular maximization, we are given query access to a submodular set function f : 2U 7→ R. The goal is to find a subset T ⊆ U that maximizes f ( T ) under certain constraints, such as:

• Cardinality constraints. The goal is to find T that maximizes f ( T ) under the constraint that | T | ≤ c. • Matroid constraints. Given a rank-c matroid (U , I), we want T to be an independent set of the matroid (i.e., T ∈ I ) • Knapsack constraints. There is a cost cu ∈ R>0 associated with each element u ∈ U , and one is only allowed to pick sets S such that ∑u∈S cu ≤ 1. • p-extendible system constraints. If I is a collection of subsets of U , the pair (U , I) is a p-extendible system if for all S ⊂ T ∈ I , and u ∈ U such that S ∪ {u} ∈ I , there is some set V ⊂ T \S of at most p elements such that ( T \V ) ∪ {u} ∈ I . 50

Submodular maximization is also studied under various restrictions on the objective function itself, such as: • Monotone, or argument-monotone. A submodular function f is monotone if whenever S ⊆ T, then f (S) ≤ f ( T ). Note that this is distinct from the data monotonicity used in this paper to construct our black-box reduction, which is why we call this condition argument monotonicity to avoid any ambiguity. • Decomposable. Also known as the combinatorial public projects problem, here the function f can be written as m

f (·) = ∑ f i (·) i =1

for some f i : U → [0, 1]. Note that here since the co-domain is non-negative, decomposability unconditionally implies data-monotonicity. • Bounded curvature. For a monotone submodular function f , its total curvature κ f is given by the expression f (U ) − f (U \{u}) . f (u) − f (∅) u∈U

κ f = 1 − min

For objective functions with known curvature, we can typically give a better approximation guarantee than in the general case. Private submodular maximization in the batch setting. Motivated by the problem of private feature selection, [MBKK17] were the first to initiate a systematic study of the optimization of submodular functions under the constraint of differential privacy, introducing privacy-preserving algorithms for both monotone and non-monotone objectives, under cardinality, matroid, and p-extendible systems constraints. Previously the work [GLM+ 10] had considered a special instance of private submodular maximization under k-cardinality constraints for decomposable objectives, achieving a (1 − 1/e)-approximation and an additive error which is O((k/ε) log m) under approximate DP. This approximation factor is known to be optimal in the non-private setting under standard hardness assumptions and [GLM+ 10] showed that a Ω(k/ε) factor is indeed necessary under the constraints of pure-DP. A similar linear dependence of the additive error on k was shown also to hold in the approximate DP setting by [CNN23]. All of these works require a bounded sensitivity of the objective function in terms of the input data set. Formally, the private submodular maximization problem is stated as follows: Definition 45 (Private submodular maximization). We are given a correspondence X → f X (·) between datasets X ∈ NX and submodular functions f X , with the property of bounded sensitivity; i.e. there is some public value ∆ f such that given the set of admissible inputs C ⊂ 2Y , it is the case that max

X ∼ X ′ ,Y ∈C

| f X (Y ) − f X ′ (Y )| ≤ ∆ f .

The private submodular maximization problem asks for a solution to the submodular maximization problem defined by the objective f X for a given data set X, and the constraint set C . The mapping from the data set X to the output solution Y ∗ must be differentially private for the given choice of privacy parameters. There has since been a long line of work in the DP algorithms literature studying variants of private submodular maximization. We see that since the bounded sensitivity constraint is inherent to this problem, our result Theorem 42 is applicable to each work where the data-monotone condition is also fulfilled. In some cases, like non-negative decomposable objectives in both monotone and non-monotone cases, the data-monotone condition is always fulfilled — note that even if a submodular function f X is non-monotone, the data monotone condition requires only that for all X ⊂ X ′ , f X ≤ f X ′ . In the decomposable setting we have f X = ∑ x∈X f { x} , and as long as 51

f { x} ≥ 0, data-monotonicity is immediate. In other cases where we only have ∆ f -sensitivity, data monotonicity is an extrinsic condition not necessarily true of all objectives. To the best of our knowledge, there are no prior works for private submodular maximization in the continual observation setting. With our framework, we are able to apply each work in the batch setting to give the first guarantee in the same setting in the continual observation setting, with the additional potentially extrinsic constraint of the objective being data-monotone. We construct Table 3 by applying Theorem 42 to each prior work. The batch approximation factor α is preserved up to the geometric spacing factor (1 + κ ). For algorithms with inexpectation guarantees, Corollary 44 converts the in-expectation guarantee to a high-probability one via Lemma 33, incurring only a (1 − c) factor in the multiplicative guarantee for an arbitrarily small user-chosen c > 0, at the cost of an O(ln(1/c)) additive term. In the table, we absorb this loss into the existing slack parameter η or suppress it as a lower-order term. 8.2. Densest subgraph. Given a graph G = (V, E) and a node weight function, c : V 7→ R+ , a subset S ⊆ V, let | E(S)| , ρ(S) = ∑v∈S c ( v ) where E(S) is the set of edges induced by S ⊆ V, i.e., with both end points in S. The goal of the densest subgraph problem is to find S∗ := argmaxS⊆V ρ(S). The above definition is the general form of densest subgraph problem (known as weighted densest subgraph). The unweighted densest subgraph has all node weights O(1), in which case, ∑v∈S c(v) = O(|S|) and the objective becomes S∗ := argmaxS⊆V

| E(S)| . |S|

It is easy to see that in both cases, under edge-insertions the objective is monotonically increasing for every candidate solution S, and so Theorem 42 applies as is. Further, in the weighted setting, the only works considered assume that c(v) ≥ 1, so we also immediately have that the objective of interest is 1-sensitive. For graph problems, differential privacy is usually formulated in terms of node-neighboring and edge-neighboring graphs, which is to say that neighboring input graphs G = (V, E) and G ′ = (V ′ , E′ ) can vary in the presence or absence of at most 1 node in the node-neighboring setting, and in the presence or absence of 1 edge in the edge-neighboring setting. The latter is a weaker notion of privacy but is in practice much easier to work with — we will consider only this notion of privacy. In the CO setting, we consider two streams to consist of edges of the graphs. Two streams are considered to be neighboring if they differ in one time epoch, where an edge is present or absent. Prior work in the batch setting. The work [DLR+ 22] solves the unweighted densest subgraph problem for any given constant η > 0 with multiplicative approximation 1/(1 + η ) and additive error O( 1ε log4 n) in the batch setting in an ε-DP manner. This algorithm succeeds with high probability, which they specify to mean with probability 1 − 1/nc for any given constant c. The work [DKLV25] solves the weighted densest subgraph problem  q in the approximate-DP

 setting with no multiplicative loss at all (α = 1) and additive error O 1ε log nδ log (n) . This bound holds with high probability, which tracking the proof of the relevant result can be set to be 1 − 1/nc for any constant c > 0. They assume that c(v) ≥ 1, a standard assumption from the non-privacy literature. 52

Implications for CO. In the unweighted setting, we apply Theorem 42 Item 2 to the highprobability guarantee of [DLR+ 22]. Since the batch algorithm achieves a 1/(1 + η )-approximation, our reduction gives a 1/((1 + η )(1 + κ ))-approximation under CO. For any desired constant multiplicative loss, we can set η and κ to be small constants. The additive error is       1 1 1 2 4 3 6+ a log t · log t + Õ log t = Õ log t . Õ κε κε κε In the above, the Õ notation hides log 1/ε terms and a is an arbitrarily small constant. In this unweighted setting, the state of the art result is not the one achieved by our framework, but rather by [ELMZ24], who give an ε-DP algorithm that achieves a 1+1 κ multiplicative approximation with additive error O( κ14 ε log5 n) with high probability for all time-steps. The gap between our log6+a t and their log5 n reflects the cost of the black-box approach. In the weighted setting, to the best of our knowledge, there is no prior work in the CO setting. Here, on applying Theorem 42 Item 2 to the batch DP result of [DKLV25] (which has α = 1), we get that there is an (ε, δ)-DP algorithm that with high probability achieves a 1+1 κ -approximation and additive error ! r     q 1 1 1 1 Õ log2 t log δt log t + Õ log3 t = Õ log3 t log . εκ εκ εκ δ 8.3. Densest k-subgraph. We also note the recent work of Khayatian, Vullikanti and Konar [KVK25] who give the first (ε, δ)-edge DP algorithms for DkS. Given an unweighted undirected graph G = (V, E) with |V | = n and | E| = m, and a target size k ∈ [n], the Densest-k-Subgraph (DkS) problem seeks a subset S ⊆ V of exactly k vertices maximizing the induced edge density d(S) := |ES |/(2k ), where ES = {(u, v) ∈ E : u, v ∈ S}. We write d∗k := max|S|=k d(S) for the optimum. As in the densest subgraph setting, the induced edge count has sensitivity 1 under edge-DP and satisfies data monotonicity under edge insertions, so Theorem 42 applies. c DkS is computationally intractable: achieving an O(n1/(log log n) )-approximation is hard under standard complexity-theoretic assumptions [Man17]. As a result, no worst-case multiplicative approximation ratio α is available, and Corollary 43 and Corollary 44 do not apply. However, Theorem 42 and its data-dependent guarantee via VA ( Xt ) imply that the performance of the CO construction based on their algorithm ought to inherit a performance similar to the performance of their algorithm executed at time step t with privacy parameter ε/ ln2 (t/β), and some additional additive polylogarithmic overhead scaled by 1/κ. As the performance of their algorithm is measured entirely empirically, there is no corresponding theoretical result that we can state. We conclude this section by observing that our reduction applies in this problem setting, that our analysis indicates non-trivial performance guarantees, but leave it as an open question for future work to test whether this actually pans out in practice. 8.4. Max-Cut. Given a graph G = (V, E) and an edge weight function w : E → R+ , the MAXCUT problem asks for a subset S ⊆ V that maximizes the cut value: max S ⊆V

∑

w ( e ).

e=(u,v)∈ E u∈S, v∈V \S

It is easy to see that for every candidate solution S, the objective is monotonically increasing for insertion-only edge streams. The sensitivity of this problem is maxe∈E w(e), so when a bound on this expression is known the objective function can be rescaled and Theorem 42 can be applied. 53

Chandra et al. [CDFZ24] gave an ε-differentially private algorithm A that (1, β, E A )-solves MAX-CUT, where     1 1 E A ( Xt , ε, 0, β) := O n log n + log . ε β Note that the algorithm of Chandra et al. [CDFZ24] is not efficient: the time and space consumption depend on the complexity of finding the exact max-cut on a noisy graph with non-negative edge weights. However, since our framework applies to this problem, our reduction implies that if there exists an efficient algorithm for DP MAX-CUT in the batch setting, then we would immediately have an efficient algorithm in the CO setting as well, with an accuracy guarantee derived from Theorem 42. 9. A CCURACY GUARANTEES IN PRIOR WORK In this section we recall the formal accuracy guarantees in prior work, and compare them at a technical level with the guarantees we derive for the Generalized Thresholding Mechanism. 9.1. Prior work. We first give a brief review of the above threshold mechanism in the standard setting, and the techniques of two works most related to our works, i.e., [LT19] and [CLN+ 23]. Review of problem description. Recall that in standard private testing there is a sequence of private real numbered values (vt )t≥1 and a threshold τ ∈ R+ . A tester processes the stream in an online fashion and outputs at = −1 until it receives vt ≥ τ; at this point it outputs at = +1 and halts. However, the output of the tester should be ε-DP where v and v′ are considered neighboring streams if ∀t, |vt − v′t | ≤ 1. The Above Threshold mechanism [DR14] solves this problem with the accuracy guarantee that with probability 1 − β for all t ≥ 1, at = +1 ⇒ vt ≥ τ − O((1/ε)(log(t/β))), and at = −1 ⇒ vt ≤ τ + O((1/ε)(log(t/β))). For the ease of the readers, we recall the problem of generalized private testing. In the generalized private testing, the values (vt )t≥1 are replaced with a sequence of mechanisms, datasets and privacy parameters Mt : X → {+1, −1}, Xt ∈ X , and ε t ≥ 0, and the threshold τ is replaced by a target success probability p∗ ∈ (0, 1). For simplicity, we assume here ε t = ε 1 for all t. We define pt = Pr[Mt ( Xt ) = +1] and p′t = Pr[Mt ( Xt′ ) = +1], where Xt′ is a dataset neighboring Xt . Two streams of mechanism and dataset pairs (Mt , Xt ) and (Mt , Xt′ ) are considered neighboring if pt ∈ (e−ε t p′t , eε t p′t ) and (1 − pt ) ∈ (e−ε t (1 − p′t ), eε t (1 − p′t ). We call this the stability guarantee of pt . The analyst should process the stream and stop at the first (Mt , Xt ) for which pt ≥ p∗ . Just as in the standard setting, the goal is to suffer a small loss in accuracy of these threshold tests, which is to say that if the test fails, then pt should not be more than p∗ , and if it passes, then pt should not be much less than p∗ . Technical overview of [LT19]. Liu and Talwar approached this problem by initially assuming access to an oracle which gives the analyst the exact value of pt . Then, they observed that the logodds ratio of the input probability, i.e. Φ( pt ) = log( pt /(1 − pt )) is 2ε-Lipschitz. In this simplified setting, they can reduce the generalized private testing problem to the standard setting, and they show essentially that with this reduction, with probability 1 − β for t ≥ 1, if pt ≤ p̄t then at = −1, where p̄t = ( β2 /t)12ε 1 /ε p∗ ; for pt ∈ ( p̄t , p∗ ), there is no guarantee. We see that the logarithmic additive error in accuracy in the standard setting gets amplified to a multiplicative polynomial gap between p∗ and p̄ in the generalized setting. However, in generalized private testing, the analyst does not have access to pt . To circumvent this issue, the generalized Above Threshold mechanism of [LT19] draws Nt many samples from Mt ( Xt ), and use a coupling argument to show that the estimates pbt of pt fulfill a weak Lipschitz property. As discussed in the introduction, the downsides of this approach are that (a) we can only 54

guarantee approximate DP outputs while requiring the inputs to be pure DP, (b) the exponent of β2 /T is 12 and (c) the sample complexity has a large ( T/β)12ε 1 /ε factor. Technical overview of [CLN+ 23] Cohen, Lyu, Nelson, Sarlós and Stemmer revisited this problem, and gave a unified framework for generalized private selection and generalized private testing. Their Test procedure for generalized private testing draws a value p† , with cumulative density function, Pr[ p† ≤ x ] ≤ x θC for all x ∈ [0, 1] and some fixed θC ≥ 0 chosen by the analyst. Then, for every mechanism and dataset Mt and Xt , they draw a value bt ∼ Ber( p† ). If bt = −1, then they output −1 without evaluating Mt ( Xt ). If b1 = +1, then they output whatever they get from the evaluation of Mt ( Xt ). They showed that, if for all t ≥ 1, Mt is (ε 1 , δt )-DP, then their mechanism achieves ((2 + θC )ε 1 , ∑i δi )-DP. In particular, for a target output probability of ε > 2ε 1 , this implies that picking θC = ε/ε 1 − 2 suffices for (ε, ∑t δt )-DP. [CLN+ 23] introduce two new key technical insights which make this possible: (1) a coupling argument along the lines of the sparse vector technique that only requires an injective mapping, not a bijective one, and (2) the observation that one can lean on the inherent privacy guarantee of each mechanism evaluation to avoid adding more noise for each test. The significance of the first insight is that a one-sided perturbation that only systematically reduces the probability of a test passing suffices for proving the uniform privacy loss bound; this means that less noise is needed for achieving privacy, and this improves the accuracy of tests. Along with the second insight, this implies much less additional is being added to achieve a similar privacy loss guarantee, compared to [LT19]. At a high level, the θC ε 1 term in the privacy loss is incurred by the coupling argument, and the 2ε 1 term is incurred by the last mechanism evaluation that leads to a halt. [CLN+ 23] do not give accuracy guarantee along the line of [LT19]. In this section, we analyse the accuracy of their mechanism along the lines of [LT19]. We also derive a lower bound demonstrating that with this algorithm, one cannot achieve a rejection threshold greater than p∗ β/T. The highlight is that the coefficient of ε 1 /ε is significantly better, but an additional β/T factor is incurred in the rejection threshold. 9.2. The accuracy guarantee of [LT19]. We recall the algorithm and formal guarantee for the reader’s reference. We start with main steps in the ExtendedAboveThreshold mechanism presented in [LT18] (the arxiv version of [LT19]). The mechanism gets target threshold p∗ ∈ (0, 1), a failure probability β ∈ (0, 1), a privacy parameter δ ∈ (0, 1), an auxiliary parameter ε 0 ∈ (0, 1), a stream length T > 1, and input privacy parameter ε 1 > 0. Let ε > 0 denote the output privacy parameter (ε 3 in the notation of [LT19]). The ExtendedAboveThreshold algorithm ([LT19, Algorithm 4]) proceeds as follows. (1) At initialization, it draws shared noise ν ∼ Lap(4(ε 1 + ε 0 )/ε). (2) Let σLT := 12(ε 1 + ε 0 )/ε for the exponent that governs the accuracy–privacy tradeoff. Define   1 T C ln(8T/δ) ε 0 +ε 1 ε 0 /2 = O 2 ln , C : = 2( e + 1 + e ) < 21, ∆ := ε 0 ( e ε 0 + ε 1 − 1) δ ε0 (25)   eε 0 ∆ T + 1 σLT Nx + ∆ N := · , Φ∆ ( x ) := . ∗ ∗ min{ p , 1 − p } β N (1 − x ) + ∆ (3) At each step t = 1, . . . , T, (a) draws N i.i.d. evaluations of Mt ( Xt ); (b) computes the empirical success probability pbt := N1 ∑ N j=1 1 { yt,j = +1}; (c) draws per-step noise ξ t ∼ Lap(8(ε 1 + ε 0 )/ε) 55

(d) if eξ t · Φ∆ ( pbt ) ≥ eν · Φ∆ ( p∗ ). then output at = +1 and halt. Otherwise output at = −1 and continues. We now restate their result in our notation: Theorem 46 (Theorem 4.4 in [LT19] restated in our notation). Fix a target threshold p∗ ∈ (0, 1), a failure probability β ∈ (0, 1), a privacy parameter δ ∈ (0, 1), an auxiliary parameter ε 0 ∈ (0, 1), a stream length T > 1, and input privacy parameter ε 1 > 0. Let ε > 0 denote the output privacy parameter (ε 3 in the notation of [LT19]). Let σLT , C, ∆, N, and Φ∆ ( x ) be as defined in eq. (25). Suppose that each Mt is ε 1 -DP. Then the following hold: (1) Privacy. The mechanism is (ε, δ)-DP. (2) Not stopping too early. Conditional on the algorithm halting at step R, with probability at least 1 − β − δ/2: σLT  1 β p R ≥ e−ε 0 p∗ . 2 R+1 (3) Not stopping too late. Conditional on the algorithm halting at step R, with probability at least 1 − β − δ/2: no earlier step i < R satisfies   R + 1 σLT Φ ∆ ( p ∗ ). Φ ∆ ( pi ) ≥ e ε 0 β Further, ([LT19, Theorem 4.2(c), “moreover”]), with probability 1 − β − δ/2, p R is bounded from below:    −1 eε 0 R + 1 σLT pR ≥ 1 − 1 + . 2(1 − p ∗ ) β (4) Halting. If at some step t (conditional on not having halted earlier) the success probability satisfies  σLT 1 ε0 Φ ∆ ( p ∗ ), Φ∆ ( pt ) ≥ e β then the algorithm halts at step t with probability at least 1 − β − δ/(4T ). Typographical note: The statement of [LT19, Theorem 4.2(d)] writes Pr[ at = +1| . . .] ≤ β + δ/(4T ), but the proof establishes the complementary bound Pr[ at ̸= +1| . . .] ≤ β + δ/(4T ), as stated above. (5) Sample complexity. The number of evaluations of Mt at each step is   σLT  1 T T N = O 2 · · ln . β δ ε 0 min{ p∗ , 1 − p∗ } Note that the halting guarantee is not a guarantee that the algorithm halts whenever pt ≥ p∗ ; the condition requires pt to be substantially above p∗ . For large N, Φ∆ ( x ) → x/(1 − x ), so the condition is approximately  σLT pt 1 p∗ ε0 ≥ e · . 1 − pt β 1 − p∗ 9.3. Accuracy guarantee for the Test procedure of Cohen et al. [CLN+ 23]. [CLN+ 23] introduce an elegant and lightweight procedure for achieving an SVT-style privacy loss for generalized private testing. They are able to apply this framework to improve the standard SVT, as well as error bounds for the private multiplicative weight update method [HR10] and bounds for adaptive data analysis [DFH+ 15]. They introduce the Test subroutine in Algorithm 4, and show the following result: 56

Input: Stream of ε 1 -DP mechanisms (Mt )t≥1 with pt := Pr[Mt ( Xt ) = +1]; target p∗ ∈ (0, 1); failure probability β ∈ (0, 1); parameter θC = ε/ε 1 − 2 > 0. Draw p† from [0, 1] with Pr[ p† ≤ x ] = x θC ; Function T EST (Mt ): Draw r ∼ Ber( p† ); if r = 0 then return −1; return Mt ( Xt ); for t ≥ 1 do Nt ← ⌈ln(2/β)/(( β/2)1/θC p∗ )⌉; halted ← false; for j = 1, . . . , Nt do if T EST (Mt ) = +1 then Output at = +1; halted ← true; break; end end if halted then halt; else output at = −1 and continue to step t + 1; end Algorithm 4: Generalized Private Testing via [CLN+ 23] Theorem 47. [CLN+ 23, Theorem 2]. Let there be a stream of (ε 1 , δt )-DP mechanisms (Mt )t≥1 , and parameter θC = ε/ε 1 − 2 > 0. The T EST procedure of [CLN+ 23, Algorithm 1] (reproduced here as the T EST procedure in Algorithm 4) takes as input the given stream and halts when it has output +1 c ≥ 1 √ T − c times . The collection of outputs satisfies ((2c + θC )ε 1 , ∑i=1 δt )-DP for all δ ∈ (0, 2 ). This theorem provides an adaptive privacy guarantee: it applies to any adaptive sequence of calls to T EST, where the choice of mechanism at each call may depend on prior outputs, as long as the sequence terminates after receiving c positive responses. In their work, Cohen et al. [CLN+ 23] do not give an accuracy guarantee as introduced by [LT19] for the generalized private testing problem. We derive an accuracy guarantee for their Test procedure along the lines of the notion of accuracy introduced by [LT19]. At initialization, the mechanism draws a shared pass probability p† from [0, 1] with Pr[ p† ≤ x ] = x θC for all x ∈ [0, 1]. At each step t, the mechanism makes up to Nt independent calls to T EST (Mt ), where each call draws r ∼ Ber( p† ) and returns Mt ( Xt ) if r = 1 and −1 if r = 0. The mechanism halts at step t if any call returns +1, and continues to the next step if all Nt calls return −1. We see that with probability p† , the T EST procedure does not evaluate the mechanism Mt at all. To avoid the possibility of a missed halt, we test every mechanism some Nt -many times to ensure that if pt ≥ p∗ , then we would encounter a +1 with probability 1 − β. We formalize this guarantee in Algorithm 4 and the following result. Proposition 48 (Accuracy of the mechanism of [CLN+ 23] for generalized private testing). Fix a target threshold p∗ ∈ (0, 1), a failure probability β ∈ (0, 1), an input privacy parameter ε 1 > 0, and a private dataset X. Suppose ε > 2ε 1 , and define θC := ε/ε 1 − 2 > 0. When Algorithm 4 is run on an input sequence of mechanisms Mt ( X ), the following properties hold. 57

(1) Privacy. The mechanism is ε-differentially private. (2) Accuracy. With probability at least 1 − 2β, simultaneously for all t ≥ 1: (a) Halting: If pt ≥ p∗ , then at = +1. (b) Continuation: If pt ≤ p̄t , then at = −1, where  1/θC β p∗ β t −β . p̄t = 2 ln(2/β) 2 (3) Sample complexity.   O

ln(2/β) p∗ ( β/2)1/θC

The number of evaluations of Mt at each step is at most Nt =

.

Proof. Each call to T EST (Mt ) returns +1 with probability p† · pt , where p† ∈ [0, 1] with Pr[ p† ≤ x ] = x θC : the Bernoulli trial passes with probability p† , and conditioned on passing, Mt ( Xt ) returns +1 with probability pt . At step t, the mechanism makes calls sequentially and halts globally on the first +1 response, or outputs at = −1 after Nt consecutive −1 responses. Since the calls are independent, the probability of observing at least one +1 among Nt calls is 1 − (1 − p† pt ) Nt , regardless of whether we stop at the first +1 or run all Nt calls. Privacy. Algorithm 4 produces an adaptive sequence of T EST calls (the choice of Mt at each step may depend on prior outputs a1 , . . . , at−1 ) that terminates after at most c = 1 positive response. Therefore, by Theorem 47, the full transcript is ε-DP for ε = (2 + θC )ε 1 . Noise control. Define the event G := { p† ∈ (( β/2)1/θC , (1 − β/2)1/θC )}. Since Pr[ p† ≤ x ] = x θC , we have Pr[G c ] = β. Halting. Conditioned on G , suppose pt ≥ p∗ at some step t. Each of the Nt independent calls returns +1 with probability p† · pt ≥ ( β/2)1/θC p∗ . The probability that all Nt calls return −1 is β , 2 where the last inequality uses Nt ≥ ln(2/β)/(( β/2)1/θC p∗ ). Since we only need to detect the first instance of pt ≥ p∗ , the probability of a Type II error at any step is at most β/2, conditioned on G .

(1 − p† · pt ) Nt ≤ (1 − ( β/2)1/θC p∗ ) Nt ≤ exp(− Nt ( β/2)1/θC p∗ ) ≤

Continuation. Suppose pt ≤ p̄t at step t. Since x 7→ 1 − (1 − x ) Nt is non-decreasing on [0, 1] and p† ≤ (1 − β/2)1/θC , the probability that at least one of the Nt calls returns +1 satisfies, 1 − (1 − p† · pt ) Nt ≤ p† Nt pt ≤ (1 − β/2)1/θC Nt p̄t , where the first inequality uses 1 − (1 − x ) N ≤ Nx for x ∈ [0, 1]. Summing over all t ≥ 1, we require   β β 1/θC Nt p̄t ≤ . ∑ 1− 2 2 t ≥1 t Defining p̄t = 2N (1− β/2 , since ∑t≥1 β t /2 = β/2, this bound holds. Setting the value of Nt , )1/θC

β

t

p̄t = 2

l

ln(2/β)

βt m

( p∗ ( β/2)1/θC )

β

1− 2

1/θC

≤

p∗ β t ( β/2)1/θC . 2 ln(2/β)(1 − β/2)1/θC

Failure probability. The total failure probability is at most Pr[G c ] + Pr[Type II error | G] + Pr[Type I error | G] ≤ 2β. | {z } | {z } | {z } ≤β

≤ β/2

≤ β/2

□

This completes the proof of Proposition 48. 58

Remark 49 (Approximate DP inputs). Proposition 48 assumes pure ε 1 -DP input mechanisms. When the input mechanisms are (ε 1 , δ)-DP, [CLN+ 23, Theorem 2] gives ((2 + θC )ε 1 , ∑i δi )-DP, where the sum is over all calls to T EST. Since Algorithm 4 makes as many as ∑tT=1 Nt calls over T inputs, this yields a total δ-cost of up to ∑tT=1 Nt δt , which scales linearly in both the number of trials per step and the stream length. [CLN+ 23] also provide a Rényi DP analysis [CLN+ 23, Theorem 2] to obtain tighter approximate DP guarantees via conversion, at the cost of a more involved privacy accounting. Both the linear δ-accumulation and the need for Rényi DP analysis can be avoided by applying the purification technique of Lemma 24. Given (ε 1 , δ)-DP mechanisms, each evaluation is passed through a binary symmetric channel with crossover probability ϕ = δ/(eε 1 − 1 + 2δ) ≤ δ/ε 1 , producing a pure ε 1 DP mechanism. The acceptance and rejection thresholds are then perturbed by at most δ/ε 1 . This approach applies to the mechanism of Cohen et al. [CLN+ 23] as well as to our Algorithm 1, and yields pure DP guarantees for the output in both cases, with no δ-accumulation across calls. Lemma 50 (False positive accumulation under shared randomness). Let M ≥ 1, q0 ∈ (0, 1], and q > 0. Let Ω be a probability space and E ⊆ Ω an event with Pr[ E] ≥ q0 . Suppose that for every outcome ω ∈ E, conditioned on ω, at least M conditionally independent trials are observed, each succeeding with conditional probability at least q. Then the probability that at least one trial succeeds is at least   q0 1 − e− Mq . In particular, if this probability is at most β for some β < q0 , then q ≤

1 1 . ln M 1 − β/q0

For β ≤ q0 /2, this gives q ≤ 2β/( Mq0 ). Proof. For every ω ∈ E, the probability that all M trials fail is at most (1 − q) M ≤ e− Mq . Averaging over E, Pr[all fail | E] ≤ e− Mq , so Pr[at least one succeeds | E] ≥ 1 − e− Mq . Marginalizing, the unconditional probability of at least one success is at least q0 (1 − e− Mq ). Setting this at most β and rearranging, β 1 1 − e− Mq ≤ ⇒ Mq ≤ log . q0 1 − β/q0 Dividing both sides by M in the latter inequality yields the stated bound. For β ≤ q0 /2, we have β/q0 ≤ 1/2, and the standard inequality ln(1/(1 − x )) ≤ 2x for x ∈ [0, 1/2] gives q ≤ 2β/( Mq0 ). □ Corollary 51 (Error lower bound of algorithm 4). Fix β ∈ (0, 1/4), T ≥ 1, ε 1 > 0, and ε > 2ε 1 . Write θC = ε/ε 1 − 2 > 0 for the parameter of the mechanism of [CLN+ 23]. Consider their testing mechanism applied to T mechanisms, each ε 1 -DP with range {−1, +1}, success probabilities pt , and evaluated Nt times at step t. If there exists p̄ > 0 such that for every instance with pt ≤ p̄ for all t ∈ [ T ], the probability that the algorithm halts is at most β, then 4β · 21/θC p̄ ≤ . ∑tT=1 Nt   In particular, for any fixed θC > 0, p̄ = O β/ ∑tT=1 Nt . Proof. The mechanism draws p† ∈ [0, 1] with Pr[ p† ≤ x ] = x θC . Define E = { p† ≥ (1/2)1/θC }, which has probability q0 = 1 − ((1/2)1/θC )θC = 1/2. At each step t, each of the Nt calls to T EST independently draws r ∼ Ber( p† ) and evaluates Mt ( X ) if r = 1. For any fixed p† ∈ E, the T EST calls are conditionally independent of each other, each producing +1 with conditional probability 59

p† · pt ≥ (1/2)1/θC · p̄. The algorithm halts on any +1. Apply Lemma 50 with M = ∑tT=1 Nt , q = (1/2)1/θC p̄, and q0 = 1/2. Since β < 1/4 = q0 /2,

(1/2)1/θC p̄ ≤

4β , M

giving the claimed bound on p̄.

□

9.4. Technical Overview of [GKK+ 25]. Ghazi, Kamath, Knop, Kumar, Manurangsi, and Zhang [GKK+ 25] introduce two mechanisms which are relevant to our setting. They work in the generalized private selection setting and consider a stream of mechanisms generating outputs with scores in some arbitrary domain, and their objective is to find an output which achieves a user-defined threshold. Their first mechanism is their generalized AboveThreshold mechanism with random dropping [GKK+ 25, Algorithm 2]. It is similar to the T EST procedure of [CLN+ 23], with a dropping proba′ bility p†G = e−ε i ·k , where k ∼ Geo(e−ε ). For every mechanism in the input stream they first draw a value y ∼ Ber( p†G ), and only query the mechanism if this check passes. Then, if the score of the item output by the mechanism beats the given threshold, they output this item, along with the index of the mechanism that generated this output, in the clear. They show that this mechanism fulfills an (2ε i + ε′ )-ex post privacy guarantee. Their guarantee is more general than that of [CLN+ 23] by allowing for varying input privacy parameter ε i , and they also show that one can output the element that achieves the score which passes the threshold test. However, the core idea is similar - each access to Mt is mediated by a dropping probability, and in fact the distribution from which this probability is drawn is very similar (we explain this next). Further, the privacy loss guarantee is similar; for ε t = ε 1 , their guarantee is exactly the 2ε i + ε guarantee achieved by [CLN+ 23]. ′ To reason about the dropping probability distribution, we see that for k ∼ Geo(e−ε ) and any ′ j ∈ N, Pr[k ≥ j] = e−ε j . It follows that the 1 − β-probability upper bound on k is ≈ ε1′ log 1/β. It follows that the (1 − x ) probability lower bound on the dropping probability p†G equals exp(−ε i · 1 ε i /ε′ . In other words, Pr[ p† < x ] ≈ x ε i /ε′ . This is essentially the same distribution ε′ log 1/x ) ≈ β from which the dropping probability p† of [CLN+ 23] is drawn, and it follows that similar upper and lower bounds in terms of accuracy for generalized private testing follow. [GKK+ 25] introduce another algorithm called the Hyperparameter Tuning Mechanism with Random Dropping (Algorithm 3 in their paper); we recall it here for reference in our notation for ease of comprehension. The algorithm incurs output privacy loss ε = 2ε i + ε′ ; we write θG = ε − 2ε 1 = ε′ > 0 to match notation with our discussion. They prove that their algorithm achieves the following accuracy guarantee: Theorem 52 ([GKK+ 25], restated). Let α, β ∈ (0, 1), ε′ > 0, and let M1 , . . . , Md be mechanisms where Mi is ε i -DP with range O . Define &   ′  ' 2 1 2 ε i /ε ln . Ti := α β β ′

Run Algorithm 5 with E = Geo(e−ε ), repeating each Mi for Ti times in the input sequence. Then: (1) Privacy. The mechanism is ex-post ε̃-DP with ε̃(o, i ) = 2ε i + ε′ and ε̃(⊥) = 0. (2) Accuracy. If there exists o ∗ ∈ O and i∗ ∈ [d] such that Pr[Mi∗ ( D ) ≥ o ∗ ] ≥ α, then the algorithm outputs an element at least as large as (o ∗ , 0) with probability at least 1 −  β.  ε /ε′   1 2 i (3) Sample complexity. The number of evaluations of Mi is at most Ti = O α β ln β2 . 60

Input: Mechanisms Mt : X → {−1, +1}, each ε 1 -DP, for t ∈ [ T ]; dataset X. Output: (o, t) ∈ {−1, +1} × [ T ] or ⊥. S ← {⊥}; Draw k ∼ Geo(e−θG ); for t = 1, . . . , T do Draw yt ∼ Ber(e−ε 1 ·k ); // random drop if yt = 1 then o ← M t ( X ); S ← S ∪ {(o, t)}; end end return element of S selected by a data-independent rule; Algorithm 5: Maximum Selection with Random Dropping [GKK+ 25] This guarantee is very compelling, because unlike our upper and lower bounds for generalized private testing, it does not incur poor scaling with the length of the stream. However, we find that when we analyse their mechanism in terms of testing, as opposed to for selection, it incurs a similar accuracy loss of β/T. We formalize this via a toy example. Consider a setting where there are some T mechanisms; G of them are good, and have a probability p∗ of generating good +1 outputs, and the remaining T − G of them are bad, and only generate good +1 outputs with probability p̄t . If we want a 1 − β probability guarantee that the mechanism whose index is output by the selection mechanism is not bad, then for any fixed choice of θG , we will require p̄ ≈ Θ( β/T ) if G = o ( T ). Corollary 53 (Error lower bound for Algorithm 5 when used for testing). Fix β ∈ (0, 1/2), T ≥ 2, p∗ ∈ (0, 1), ε 1 > 0, and ε > 2ε 1 . Write θG = ε − 2ε 1 and suppose β ≤ (1 − e−θG )/2. Consider Algorithm 5 applied to T mechanisms with range {−1, +1}, of which G ∈ [ T − 2] have success probability pt ≥ p∗ and the remaining T − G have success probability pt ≤ p̄. Suppose the selection rule is uniform random among all (+1, t) in S. If the probability that the algorithm returns (+1, t) with pt ≤ p̄ is at most β, then p̄ ≤

2β(1 + Gp∗ ) . ( T − G )(1 − e−θG )

In particular, for any fixed ε > 2ε 1 , p̄ = O( β(1 + Gp∗ )/( T − G )). Proof. The algorithm draws k ∼ Geo(e−θG ). Conditioned on k = 0, which has probability 1 − e−θG , every Bernoulli gate passes, so all T mechanisms are evaluated independently. Fix a bad configuration t0 with pt0 ≤ p̄. Under uniform random selection among all (+1, t) in S,   1 Pr[t0 selected | k = 0] = p̄ · E , 1 + N−t0 where N−t0 is the number of +1’s from the remaining T − 1 configurations, independent of t0 ’s output. Since x 7→ 1/(1 + x ) is convex, Jensen’s inequality gives   1 1 1 E ≥ = . 1 + N−t0 1 + E[ N−t0 ] 1 + ( T − G − 1) p̄ + Gp∗ The events {t0 selected} are disjoint over distinct bad configurations t0 , so summing over all T − G bad configurations, Pr[bad selected | k = 0] ≥ 61

( T − G ) p̄ . 1 + ( T − G − 1) p̄ + Gp∗

Incorporating Pr[k = 0] = 1 − e−θG and setting the result at most β:

(1 − e − θ G ) ·

( T − G ) p̄ ≤ β. 1 + ( T − G − 1) p̄ + Gp∗

Rearranging: (1 − e−θG )( T − G ) p̄ ≤ β(1 + ( T − G − 1) p̄ + Gp∗ ) = β + β( T − G ) p̄ − β p̄ + βGp∗ . Moving the β( T − G ) p̄ term to the left:

(1 − e−θG − β)( T − G ) p̄ ≤ β(1 + Gp∗ − p̄) ≤ β(1 + Gp∗ ). Since β ≤ (1 − e−θG )/2, the factor 1 − e−θG − β ≥ (1 − e−θG )/2 > 0, giving p̄ ≤

2β(1 + Gp∗ ) . ( T − G )(1 − e−θG )

Since 1 − e−θG is a positive constant depending only on the privacy parameters, p̄ = O( β(1 + Gp∗ )/( T − G )) for any fixed ε > 2ε 1 . □ A CKNOWLEDGEMENTS This research was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564), and the Austrian Science Fund (FWF) under grant DOI 10.55776/Z422. For open access purposes, the authors have applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Anamay Chaturvedi was supported by an ISTA-Fellowship. Jalaj Upadhyay was supported by NSF CNS 2433628, Google Seed Fund grant, Google Research Scholar Award, Dean Research Seed Fund, and Decanal Research Grant. A part of the work was done while Jalaj was visiting ISTA. R EFERENCES [CDFZ24] Rishi Chandra, Michael Dinitz, Chenglin Fan, and Zongrui Zou. Differentially private algorithms for graph cuts: A shifting mechanism approach and more. arXiv preprint arXiv:2407.06911, 2024. [CLN+ 23] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Generalized private selection and testing with high confidence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), pages 39–1. Schloss Dagstuhl–LeibnizZentrum für Informatik, 2023. [CNN23] Anamay Chaturvedi, Huy L. Nguyen, and Thy Dinh Nguyen. Streaming submodular maximization with differential privacy. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 4116–4143. PMLR, 2023. 62

[CNZ21] Anamay Chaturvedi, Huy Le Nguyen, and Lydia Zakynthinou. Differentially private decomposable submodular maximization. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pages 6984–6992. AAAI Press, 2021. [DFH+ 15] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toni Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. Advances in Neural Information Processing Systems, 28, 2015. [DKLV25] Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. Almost tight bounds for differentially private densest subgraph. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2908–2950. SIAM, 2025. [DLR+ 22] Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 754–765. IEEE, 2022. [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pages 265–284, 2006. [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proc. of the Forty-Second ACM Symp. on Theory of Computing (STOC’10), pages 715–724, 2010. [DNR+ 09] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 381–390. ACM, 2009. [DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014. [ELMZ24] Alessandro Epasto, Quanquan C Liu, Tamalika Mukherjee, and Felix Zhou. Sublinear space graph algorithms in the continual release model. arXiv preprint arXiv:2407.17619, 2024. [GKK+ 24] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Adam Sealfon. Individualized privacy accounting via subsampling with applications in combinatorial optimization. arXiv preprint arXiv:2405.18534, 2024. [GKK+ 25] Badih Ghazi, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Private hyperparameter tuning with ex-post guarantee. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [GLM+ 10] Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1106–1125. Society for Industrial and Applied Mathematics, 2010. [HC22] Yiyang Huang and Clément L. Canonne. Lemmas of differential privacy. CoRR, abs/2211.11189, 2022. [HR10] Moritz Hardt and Guy N Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 61–70. IEEE, 2010. [KVK25] Alireza Khayatian, Anil Vullikanti, and Aritra Konar. Differentially private and scalable estimation of the network principal component. arXiv preprint arXiv:2505.03858, 2025. 63

[LT18] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. arXiv preprint arXiv:1811.07971, 2018. [LT19] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 298–309. ACM, 2019. [LWMW25] Yingyu Lin, Erchi Wang, Yi-An Ma, and Yu-Xiang Wang. Purifying approximate differential privacy with randomized post-processing. CoRR, abs/2503.21071, 2025. [Man17] Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 954–961. ACM, 2017. [MBKK17] Marko Mitrovic, Mark Bun, Andreas Krause, and Amin Karbasi. Differentially private submodular maximization: Data summarization in disguise. In International Conference on Machine Learning, pages 2478–2487. PMLR, 2017. [MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007. [MU05] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. [PS21] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. arXiv preprint arXiv:2110.03620, 2021. [RY20] Akbar Rafiey and Yuichi Yoshida. Fast and private submodular and k-submodular functions maximization with matroid constraints. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7887–7897. PMLR, 2020. [WRL+ 19] Zhiwei Steven Wu, Aaron Roth, Katrina Ligett, Bo Waggoner, and Seth Neel. Accuracy first: Selecting a differential privacy level for accuracy-constrained ERM. J. Priv. Confidentiality, 9(2), 2019. A PPENDIX A. C ONCENTRATION I NEQUALITIES Lemma 54 (Poisson Chernoff bounds). Let M ∼ Po(λ) with λ > 0. For any u ≥ 0, the following tail bounds hold:   2

(1) Upper tail: Pr[ M ≥ λ + u] ≤ exp − 2(λu+u)  2 u (2) Lower tail: Pr[ M ≤ λ − u] ≤ exp − 2λ

Proof. Let M ∼ Po(λ). We first derive the moment generating function (MGF). Using the probak bility mass function Pr[ M = k ] = e−λ λk! , for any t ∈ R: ∞

E[etM ] = ∑ etk e−λ k =0

∞
t λk (λet )k = e−λ ∑ = e−λ eλe = exp λ(et − 1) . k! k! k =0

Upper tail. For any t > 0, we apply Markov’s inequality to the monotonically increasing function etM :
E[etM ] Pr[ M ≥ λ + u] = Pr[etM ≥ et(λ+u) ] ≤ t(λ+u) = exp λ(et − 1) − t(λ + u) . e To minimize the right-hand side, we differentiate the exponent with respect to t and set it to zero, which yields t = ln(1 + u/λ). Note that t > 0. Substituting this optimal t back into the exponent 64

gives:

 u  u  u  Pr[ M ≥ λ + u] ≤ exp λ − 1+ ln 1 + . λ λ λ 2 Let x = u/λ ≥ 0, and define h( x ) = (1 + x ) ln(1 + x ) − x. We claim that h( x ) ≥ 2(1x+ x) . Let 2

2

2x f ( x ) = h( x ) − 2(1x+ x) . We have f (0) = 0. The first derivative is f ′ ( x ) = ln(1 + x ) − 2x(1+ , with + x )2

(1+ x )2 −1

2

f ′ (0) = 0. The second derivative simplifies to f ′′ ( x ) = 1+1 x − (1+1x)3 = (1+ x)3 = (x1++x2x)3 . Since f ′′ ( x ) ≥ 0 for all x ≥ 0, f ′ ( x ) is non-decreasing, implying f ′ ( x ) ≥ 0 for all x ≥ 0, which in turn 2 implies f ( x ) ≥ 0 for all x ≥ 0. Thus, the inequality h( x ) ≥ 2(1x+ x) holds for all x ≥ 0. Substituting x = u/λ into this bound yields: u  u2 u  u (u/λ)2 − 1+ =− . ln 1 + ≤− λ λ λ 2(1 + u/λ) 2λ(λ + u) Multiplying by λ and exponentiating gives the desired upper bound:   u2 Pr[ M ≥ λ + u] ≤ exp − . 2( λ + u ) Lower tail. For the lower tail, let 0 ≤ u ≤ λ. (For u > λ, the probability is exactly 0 and the bound trivially holds). For any t < 0, we apply Markov’s inequality, which yields:
E[etM ] = exp λ(et − 1) − t(λ − u) . t ( λ − u ) e Minimizing this over t < 0 yields the optimal choice t = ln(1 − u/λ). Substituting this into the exponent gives:   u  u  u  Pr[ M ≤ λ − u] ≤ exp λ − − 1 − ln 1 − . λ λ λ Let y = u/λ ∈ [0, 1), and define g(y) = −y − (1 − y) ln(1 − y). Using the Taylor series expansion Pr[ M ≤ λ − u] = Pr[etM ≥ et(λ−u) ] ≤

yk

for ln(1 − y) = − ∑∞ k =1 k , we have: ∞

∞ ∞ ∞ yk yk y k +1 g ( y ) = − y + (1 − y ) ∑ = −y + ∑ −∑ = −y + y + ∑ yk k k k =1 k k =1 k =1 k =2



1 1 − k k−1



∞

−yk . k ( k − 1) k =2

=∑

Since every term in the series is strictly negative, we can bound the sum by taking just the first y2

term (k = 2), yielding g(y) ≤ − 2 . Substituting y = u/λ gives: u  u  u u2 − − 1− ln 1 − ≤ − 2. λ λ λ 2λ Multiplying by λ and exponentiating gives the desired lower bound:   u2 Pr[ M ≤ λ − u] ≤ exp − . 2λ

□

This completes the proof.

Lemma 55 (Poisson Chernoff bounds – Multiplicative Form). Let M ∼ Po(λ) with λ > 0. For any c > 0, the following tail bounds hold: e−λ (eλ)c . cc e−λ (eλ)c (2) Lower tail: If c < λ, Pr[ M ≤ c] ≤ . cc

(1) Upper tail: If c > λ, Pr[ M ≥ c] ≤

Proof. We use
the moment generating function of the Poisson distribution, which is E[etM ] = exp λ(et − 1) for any t ∈ R. 65

Upper tail. Assume c > λ. By Markov’s inequality, for any t > 0, we have:
E[etM ] = exp λ(et − 1) − tc . tc e We minimize the right-hand side by differentiating the exponent with respect to t and setting it to zero: c λet − c = 0 =⇒ et = . λ Since we assumed c > λ, the optimal parameter is t = ln(c/λ) > 0, making it valid for the right-tail Markov application. Substituting et = c/λ and t = ln(c/λ) into the bound yields:  c   c    c  Pr[ M ≥ c] ≤ exp λ − 1 − c ln = exp c − λ − c ln . λ λ λ Using the properties of exponents, we can rewrite this exactly as:  c e−λ (eλ)c λ = . Pr[ M ≥ c] ≤ e−λ ec c cc Lower tail. Assume c < λ. For any t < 0, Markov’s inequality yields: Pr[ M ≥ c] = Pr[etM ≥ etc ] ≤

E[etM ] = exp λ(et − 1) − tc . tc e Minimizing this over t < 0 yields t = ln(c/λ) and optimal value et = c/λ. Because c < λ, the parameter t = ln(c/λ) < 0, which is valid for the left-tail application. Substituting this t into the bound yields the exact same algebraic sequence:   c  e−λ (eλ)c = . Pr[ M ≤ c] ≤ exp c − λ − c ln λ cc This completes the proof. □ Pr[ M ≤ c] = Pr[etM ≥ etc ] ≤

66