The Target-Charging Technique for Privacy Analysis across Interactive Computations
Authors: Edith Cohen
Xin Lyu
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy; Adaptive Composition; Sparse Vector Technique
TL;DR: We propose a privacy analysis method that significantly generalizes the applicability of the Sparse Vector Technique (SVT)

Abstract: We propose the \emph{Target Charging Technique} (TCT), a unified privacy analysis framework for interactive settings where a sensitive dataset is accessed multiple times using differentially private algorithms. Unlike traditional composition, where privacy guarantees deteriorate quickly with the number of accesses, TCT allows computations that don't hit a specified \emph{target}, often the vast majority, to be essentially free (while incurring instead a small overhead on those that do hit their targets). TCT generalizes tools such as the sparse vector technique and top-k selection from private candidates and extends their remarkable privacy enhancement benefits from noisy Lipschitz functions to general private algorithms.

The Target-Charging Technique for Privacy Analysis across Interactive Computations
Edith Cohen
Xin Lyu UC Berkeley 1yuxin19990gmai1. com
Google Research and Tel Aviv University edith@cohenwang.com
Abstract
We propose the Target Charging Technique (TCT), unified privacy analysis framework for interactive settings where a sensitive dataset is accessed multi- ple times using differentially private algorithms. Unlike traditional composition, where privacy guarantees deteriorate quickly with the number of accesses, TCT allows computations that don't 't hit specified target, often the vast majority, be essentially free (while incurring instead a small overhead on those that do hit their targets). TCT generalizes tools such the sparse vector technique and top-k se- lection from private candidates and extends their remarkable privacy enhancement benefits from noisy Lipschitz functions general private algorithms.
Introduction
In many practical settings of data analysis and optimization, the dataset D is accessed multiple times interactively via different algorithms (A:),, so that A, depends on the transcript of prior responses (A, (D)) When each A; is analysis. We consider the standard statistical framework of differential privacy introduced in [11]. Composition theorems [14] are a generic way to do that and achieve overall privacy cost that scales linearly or (via "advanced" composition) with square-root dependence in the number of private computations. We aim for broad understanding of scenarios where the overall privacy bounds can be lowered significantly via the following paradigm: Each computation is specified by a private algorithm A, together with target T,, that is subset of its potential outputs. The total privacy cost depends only on computations where the output hits its target, that is A,)) suitable and can be highly beneficial when (i) the specified targets are good proxy for the actual privacy exposure and (ii) expect the majority of computations to not hit their target, and thus essentially be "free" in terms of privacy cost.
we are interested tight end-to-end privacy
T,. This paradigm
The Sparse Vector Technique (SVT) [12, 30, 18, 34] is a classic special case. SVT is designed for computations that have the form of approximate threshold tests applied Lipschitz functions. Concretely, each such AboveThreshold d test is specified by 1-Lipschitz functioon f and a threshold value 1 and we wish to test whether ((D) Z l. The textbook SVT algorithm compares noisy value with noisy threshold (independent Laplace noise for the values and threshold noise that can updated only after positive responses). Remarkably, the overall privacy cost depends only positive responses: Roughly, composition is applied to twice the number of positive responses instead of to the total number of computations. In our terminology, the target of each test a positive response. SVT privacy analysis benefits when the majority of Above Threshold test results are negative (and hence "free"). This makes SVT a key ingredient in a range methods [13]: private multiplicative weights [18], Propose-Test-Rete stability [33]. model-agnostic private learning [1] [.nd designing streaming algorithms that are robust adaptive inputs [19, 6).
[10], fine privacy analysis via distance-to-
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We aim to extend such target-hits privacy analysis to interactive applications of general private al- gorithms (that is, algorithms that provide privacy guarantees but have no other assumptions); private tests, where we would hope to incur privacy cost only for positive responses, and private algo- rithms that return more complex outputs, e.g., vector average, cluster centers, a sanitized dataset, or trained ML model, where the goal is to incur privacy cost only when the output satisfies some criteria. Textbook SVT, however, is less amenable to such extensions: First, SVT departs from the natural paradigm of applying private algorithms to the dataset and reporting the output. A nat- ural implementation of private AboveThreshold tests would add Laplace noise to the value and compare with the threshold. Instead, SVT takes input the Lipschitz output of the non-private al- gorithms with threshold value and the privacy treatment is integrated (added noise both to values and threshold). The overall utility and privacy of the complete interaction are analyzed with respect to the non-private values, which is not suitable when the algorithms are already private. Moreover, the technique of using hidden shared threshold noise across multiple AboveThresher cific for Lipschitz functions, introduces dependencies between responses, and more critically, results in separate privacy costs for reporting noisy values (that is often required by analyties tasks [22]).
tests is spe-
Consider private tests. The natural paradigm is to sequentially choose a test, apply it, and report the result. The hope is to incur privacy loss only on positive responses. Private testing was considered in prior works [21, 7] but in ways that departed from this paradigm: [21] processed the private tests so that positive answer is returned only when the probability p of a positive response by the private test is very close to 1. This seems unsatisfactory: If the design goal of the private testing algorithm was to report only very high probabilities, then this could have been more efficiently integrated into the design, and if otherwise, then we miss out on acceptable positive responses with moderately high probabilities (e.g. 95%)
Consider now Top-k selection, which is a basic subroutine in data analysis, where input algorithms (A:) (aka candidates) that return results with quality scores are provided in a batch (i.e., non interactively). The selection returns the k candidates with highest quality scores on our dataset. The respective private construct, where the data is sensitive and the algorithms are private, had been intensely studied [23, 17, 32]. The top-k candidates can be viewed as target-hits and we might hope for privacy cost that is close
composition over k private computations, instead of over m >> k. The natural approach for top-k is one-shot (Algorithm 3), where each algorithm is applied once and the responses with top-k scores are reported. Prior works on private selection that achieve this analysis goal include those [9, 29] that use the natural one-shot selection but are tailored to Lipschitz. functions (apply the Exponential Mechanism [24] the Report-Noise-Man paradigm [13)) and works [21, 28, 7] that do apply with general private algorithms but significantly depart from the natural one-shot approach: They make a randomized number of computations that is generally much larger than m., with each A; invoked multiple times or none. The interpretation of the selection deviates from top-1 and does not naturally extend to top-k. We seek privacy analysis that applies to one-shot top-k selection with candidates that are general private algorithms.
The natural interactive paradigm and one-shot selection are simple, interpretable, and general. The departures made in prior works were made for a reason: Simple arguments (that apply with both 1 one-shot private selection [21] and AboveThreshold tests) seem to preclude efficient target- charging privacy analysis: With pure-DP, if we perform m computations that are c-DP (that is, m candidates or m tests), then the privacy parameter value for pure DP bound is R(m)s. With approximate-DP, and even a single "hit," the parameter values are (Ats log(1/5)), 0). The latter suggests a daunting overhead of (log((/5) instead of O(1) per "hit." We circumvent the men- tioned limitations by taking approximate DP to be a reasonable relaxation and additionally, aim for application regimes where many private computations are performed on the same dataset and we expect multiple, say ((log((//o), "target hits" (c.g. positive tests and sum of the k-values of selections). With these relaxations in place, we seek a unified target-charging analysis (c.g. privacy charge that corresponds to (11) calls per "target hit") that applies with the natural paradigm across interactive calls and top-k selections.
2 Overview of Contributions
We overview our contributions (proofs and details are provided in the Appendix). We introduce the Chargging Technique (TCT) for privacy analysis over interactive private computations (see Al Algorithm 1). Each computation performed on the sensitive dataset D) is specified by pair of
2

---

private algorithm A, and target T₁. The interaction is halted after a pre-specified number of computations satisfy (D) E T, We define targets as follows:
Definition 2.1 (q-Target), Let M: X + + be a randomized algorithm. For q E (0, 1] and e > 0, we say that a subset T S y of outcomes is 9- g-Target of M, if the following holds: For any pair D and D² of neighboring data sels, there exist p E [0, 1]. and three distributions C, B and B² such that
1. The distributions M(D") and M(D can be written as the following mixtures:
M(D*) = C+ (1 (1- p) B
) C+
2. B", B¹ are (e, (i:D-iindistinnnnhhablee
3. min(Pr[BB* E Tr, E TJ) 2 q-
The effectiveness of a target as a proxy of the actual privacy cost is measured by its g-value where q E (0, 11. We interpret 1/q as the overhead factor of the actual privacy exposure per target hit, that is, the number of private accesses that correspond to a single target hit. Note that an algorithm with q-target for 3 > 0 must be (s, O)-DP and that any (e, 0)-DP algorithm has a 1-target, as the set of all outcomes T = y is a 1-target (and hence also a q-target for any q S 1). More helpful targets are "smaller" (so that is smaller). We establish the following privacy bounds.
are less likely to be charged) with larger q (so that the overhead per charge
Lemma 2.2 (simplified meta privacy cost of target-charging). The privacy parameters of Algo- rithm / are (s', 5) where e' x 7e and 5 = el()))
Alteraatiely, we obtain parameter values (s',8)) = (fe(r,)), fs(r, + -D(r) where r R 7/g and ((( are privacy parameter values for advanced composition [14] of s-DP com- putations.
Proof details for a more general statement that also applies with approximate DP algorithms are provided in Section B (in which case the d parameters of all calls simply add up). The idea is simple: We compare the execution of Algorithm 4 on two neighboring data sets D D Given a request (A, T). let p, C, B, B", B² be the decomposition of A w.r.t. 1 D given by Definition 2.1. Then, running A on D _ can be implemented in the following equivalent way: we flip a p-bbasedd coin. With probability p. the algorithm samples from C and returns the result, without accessing Do, D at all (!). Otherwise, the algorithm needs to sample from Bddh or B depending on whether the private data is D or D' However, by Property in Definition 2.1, there is a probability of at least q that Algorithm I will "notice" the privacy-leaking computation by observing a result in the target set T. If this indeed happens, the algorithm increments the counter. On average, each counter increment corresponds to i accesses to the private data. Therefore we use the number of
target hits (multiplied by 1/g) as proxy for the actual privacy leak. Finally, we apply concentration inequalities to obtain high confidence bounds on the probability that the actual number of accesses significantly exceeds its expectation of r/q. The multiplicative error decreases when the number 7 of target hits is larger. In the regime - > In( 1 we amortize the mentioned (log(1/8)) overhead of the natural paradigm so that each target hit results in privacy cost equivalent O(L/g) calls. In the regime of very few target hits (e.g., few private tests or private selections), we still have to effectively "pay" for the larger 7 = (1In(1 ((In(1/5)), but TCT still has some advantages over alternative approaches, due to its use of the natural paradigm and its applicability with general private algorithms.
TCT is simple but turns out to be surprisingly powerful due natural targets with low overhead. We present an expansive toolkit that is built on top of TCT and describe application scenarios.
2.1 NotPrior targets
A NotPrior target of an c-DP algorithm is specified by any outcome of our choice (the "prior") that we denote by 1. The NotPrior target the set of all outcomes except 1. Surprisingly perhaps, this is effective target (See Section C for the proof that applies also with approximate-DP):
Lemma 2.3 (Property of a NotPrior target). Let A X - YuUPU [1], where 1 $ V, be an c-DP algorithm. Then the set of outcomes y constitutes an क target for A.
3

---

Algorithm 1: Target Charging
Input: Dataset D {ar,...... :. X". Integer 7 2 (Upper limit the numher of target hits).
Fraction g E 1].
C+0 while C' < do
// Initialize target hit counter
// Main loop
Receive (A, T) where A is E-DP mechanism, and T is
a g-target for A
r A(D)
Publish r
r E T then - C+1
// outcoma is target hit
Note that for small E, we have q approaching 1/2 and thus the overhead factor is close to The TCT privacy analysis is beneficial over plain composition when the majority of all outcomes in interaction match their prior I.. We describe application scenarios for NotPrior targets. For most of aware of that provides the stated privacy guarantees
these scenarios, TCT is the only method in the general context.
Private testing A private test is a private algorithm with a Boolean output. By specifying our prior to be negative response, obtain (for small s) an overhead of 2 for positive responses, which matches SVT. TCT is the only method we are aware that provides SVT-like guarantees with general private tests.
When we have prior on the result of each computation and expect the results of most computations agree with their respective prior, we set 1 to be our prior. We report all results but pay only for those that disagree with the prior. We describe some use cases where paying only for change can be very beneficial (i) the priors are results of the same computations on an older dataset, so they are likely remain the same (ii) In streaming dynamic graph algorithms, the input is sequence of updates where typically the number of changes to the output is much smaller than the number of updates. Differential privacy was used to obtain algorithms that are robust to adaptive inputs [19, 2] by private aggregation non-robust copies. The may-only-for-change allows for number of changes to output (instead of the much larger number of updates) that is quadratic in the number copies. Our result enables such gain with any private aggregation algorithm (that is not necessarily in the form of AboveThreshold tests).
seyy-onl--fo--haanee
2.2 Conditional Release
We have a private algorithm :: X + y but are interested in the output A(D) only when a certain condition holds (i.e., when the output is T T y). The condition may depend on the interaction transcript thus far (depend on prior computations and outputs). We expect most computations not to meet their release conditions and want to "charged" only for the ones that do. Recall that with differential privacy, not reporting a result also leaks information on the dataset, so this is not straightforward. We define AT Condi tww.alleleaaeeeee T) as the operation that inputs dataset D, computes + A(D). If y T, then publish and otherwise publish L. We show that this operation can be analysed in TCT as a call with the algorithm and NotPrior target pair (AT, T), that is, target hit occurs if and only if T:
Lemma 2.4 ConditionalRell and a NotPrior target AT.
privacy analysis). AT satisfies the privacy parameters of A
Proof. AT processes the output of the private algorithm A and thus from post processing property also private with the same privacy parameter values. Now note that T is NotPrior target of A, with respect to prior 1.
We describe some example use-cases:
(i) Private learning of models from the data (clustering, regression, average, ML model) but we are interested in the result only when quality is sufficient, say above a specified threshold, or when some other conditions hold.

---

(ii) Greedy coverage or representative selection type applications, where we incur privacy cost only for selected items. To do so, we condition the release on the "coverage" of past responses. For example, when greedily selecting a subset of features that are most relevant or a subset of centers that bring most value.
(iii) Approximate AboveThreshold tests on Lipschitz functions, with release of above-threshold noisy values: As mentioned, SVT incurs additional privacy cost for the reporting whereas TCT (using ConditionalReleasee does not, so TCT benefits in the regime of sufficiently many target hits.
(iv) AboveThreshold tests with sketch-based approximate distinct counts: Distinct counting sketches [16, 15, 5] meet the privacy requirement by the built-in sketch randomness [31]. We apply ConditionalRelease and set T to be above threshold values. In comparison, despite the function (distinct count) being I-Lipschitz, the use of SVT for this task incurs higher overheads in utility (approximation quality) and privacy: Even for the goal of just testing, a direct use of SVT treats the approximate value as the non- non-private input, which reduces accuracy due to the additional added noise. Treating the reported value as noisy Lipschitz still incurs accuracy loss due to the threshold noise, threshold noise introduces bias, and analysis is complicated by the response not following a particular noise distribution. For releasing values, SVT as a separate distinct-count sketch is needed to obtain an independent noisy value [22]. which increases both storage and privacy costs.
2.3
Conditional Release with Revisions
We present extension of Conditional Release that allows for followup revisions of the target. The initial Condi ti tionalRel ease and the followup ReviseCR calls are described in Algorithm 2. The Conditi oealoelelalelleeee call specifies computation identifier h for later reference, an algorithm and a target pair (A, T). It draws тΛ A(D) and internally stores тa and a current target Tr <- T. When Th. E T then гy is published and a charge is made. Otherwise, 1 published. Each (followup) ReviseCR call specifies an identifier / and disjoint extension T' to its current target т₁ If Th TV, then гι published and a charge is made. Otherwise, 1 is published. The stored current target for computation h is augmented to include T'. Note that a target hit occurs at most once in a sequence of (initial and followup revise) calls and and only if the result of the initial computation Th is in the final target Th.
cnase
Algorithm 2: Conditional Release and Revise Calls
// Initial Conditional Rolease call: Analyned in TCT as a (c, 6)-DP algorithn Ar and NotPrior target
T
Function Conditiomalleeecsss(...4 T): // unique identifier h, (e. 8)-DP slgorithm A A V,
T CCY
T +-1
Curreat target computation
TCT Charge for
0, sea Section B // Result for compatation h // publish and charge only 1f outcone is in Tk
rh
f A(D)
if Fr Tí then
Publish r's
TCT Charge for NotPrior target hit of e-DP algorithm
else
Publish
// Revise call: Analysed in TCT 2e-DP Algoritha (4 -T))) and NotPrior target T
Function ReviseCR (h, T'):
Revise target include T Input: An identifier a prior ConditionalRelease call, target extension T' where T' T =
Th E T' then
// Reault is in current target, publish and charge
Publish ra
TCT Charge for NotPrior target hit of 2s-DP algorithm
clse
L
Publish
TA
TA TT
1/ Updata target include extension
We show the following (Proof provided in Section D):
5

---

Lemma 2.5 (Privacy analysis for Algorithm 2). Each ReviseCR call can be analysed in TCT as call to a 22-DP algorithm with a NotPrior target T/.
Thus, the privacy cost of conditional release followed by sequence of revise calls is within factor of 2 (due to the doubled privacy parameter on revise calls) of a single ConditionalRed call made with the final target. The revisions extension of conditional release facilitates our results for private selection, which are highlighted next.
2.4 Private Top-k Selection
Consider the nature one-shot top-k selection procedure shown in Algorithm 3: We call each al- gorithm once and report the k responses with the highest quality scores. We establish the following:
Lemma 2.6 (Privacy of One-Shot Top-k Selection). Consider one-shot top-k selection (Algo- rithm 3) on a dataset D where {Ai] are 6e) This selection can be simulated exactly in TCT by a sequence of calls to (2e, 6)-P algorithms with NotPrior targets that has k target hits.
As a corollary. assuming e < 1, Algorithm 3 is (O(E//log(1/// 2 -0(()) +8+ Σ, DP) for every 8 > O.
To the best of our knowledge, our result is the first such bound for one-shot selection from general private candidates. For the case when the only computation performed on D is single top-1 lection, we match the "bad example" in [21] (see Theorem J.1). In the regime where & > log(1/6) our bounds generalize those specific to Lipschitz functions [9. 29] (see Section J). Moreover, Lemma 2.6 allows for a unified privacy analysis of interactive computations that are interleaved with ohe-shot selections. We obtain (1)) overhead per target hit when there are (2loog(16)) hits in total.
Algorithm 3: One-Shot Top-k Selection
Input: A dataset D. Candidate algorithms A1,... Am. Parameter S S 0
for i = 1,... m do
(yi, 8:) +- A:(D) <- S U {(i, Wis s:)}
return L the tap-k from S, by decreasing
The proofs of Lemma 2.6 and implications to selection tasks are provided in Section J. The proof utilizes Conditional Release with revisions (Section 2.3).
2.4.1 Selection using Conditional Release
We analyze private selection procedures using conditional release (see Section for details). First note that ionddtionnaRooe Rase calls (without revising) suffice for one-shot above-threshold selec- tion (release all results with quality score that exceeds pre-specified threshold t), with target hits only on what was released: We simply specify the release condition to be s; > t. What is missing in order to implement one-shot top-k selection is an ability to find the "right" threshold (a value so that exactly h candidates have quality scores above (), while incurring only & target hits. The revise calls provide the functionality of lowering the threshold of previous conditional release calls (lowering the threshold amounts to augmenting the target). This functionality allows us to simulate sweep of the m results of the batch in the order of decreasing quality scores. We can stop the sweep when a certain condition is met (the condition must be based on the prefix of the ordered sequence that we viewed so far) and we incur target hits only for the prefix. To simulate a sweep, we run a high threshold conditional release of all m candidates and then incrementally lower the threshold using sets of m revise calls (one call per candidate). The released results are in decreasing order of quality scores. To prove Lemma 2.6 observe that the one-shot top-k selection (Algorithm 3) is simulated exactly by such a sweep that halts after scores are released (the sweep is only used for analysis).
As mentioned, with this approach we can apply any stopping condition that depends on the prefix. This allows us use data-dependent selection criteria. One natural such criteria (instead of using

---

rigid value of k) is to choose k when there is a large gap in the quality scores, that the (k + 1 1)st quality score is much lower than the kth score [35]. This criterion can be implemented using a one- shot algorithm and analyzed in the same way using equivalent sweep. Data-dependent criteria are also commonly used in applications such as clustering (choose "the right" number of clusters according to gap in clustering cost) and greedy selection of representatives.
2.5 Best of multiple targets
Multi-targer charging is simple but useful extension of Algorithm 1 (that is "single target"). With k-TCT, queries have the form (A, (T (T))e())) where T; for E [k] are q-targets (we allow targets to overlap). The algorithm maintains ls counters (Ci) For each query, for each i, we increment C,
if E T₁. We halt when min; C = т.
The multi-target extension allows us to flexibly reduce the total privacy cost to that of the "best" among k target indices in retrospect (the one that is hit the least number of times). Interestingly, this extension is almost free in terms of privacy cost: The number of targets & only multiplies the privacy parameter (see Section B.1 for details).
2.6 BetweenThreehoolds in TCT
The BetweenThresholdd classifier refines the AboveThreshold test: The goal is to report if the noisy Lipschitz value is below, between, above thresholds & < fr. We aim for privacy loss that only depends on between outcomes. An SVT-based BetweenThresholdd was proposed by [3] (with noisy value and thresholds). Their analysis required the gap size to satisfy t, 2 (12/s)(oog(0/// + log(1/8) + 1).
We consider the "natural" Between Theeeennnheesold classifier that compares the Lipschitz value with added (1/( noise to the two threshold values and reports the result. This is D-DP and we show (see Section G) that the between outcome is a target with q 2 (1- (1-e-(4,-41e)) (t,-t))5) - This q value is at most that of NotPrior target (544) and degrades smoothly as the gap decreases. Importantly, there is almost no degradation for fairly small gaps: When t, t 2 2/a (resp. 3/c) the g-value is 0.87 (resp 0.95
e++1 )
e+41
One benefit of TCT BetweenThreeholld is that it applies with much smaller gaps 4, 1..-4, 4 compared with [3]. also asymptotically. Another benefit that holds even for large gaps (where the SVT variant applicable) is that the natural algorithm requires lower privacy noise for given accuracy. In Section H we demonstrate this improvement numerically in that we can answer x6-x95 fold more queries for the same accuracy requirements compared to [3]. This bring BetweenThreehoolds into the practical regime.
We compare an AboveThreshold test with a threshold with a Between/hresholds classifier with 4 = L - 1/e and 1, = L + 1/e. Surprisingly perhaps, despite Between/hreeholdd being more informative than AboveThreshold. privacy cost is lower, and is much lower when values are either well above or well below the thresh- olds. Somehow, the addition of the third between outcome to the test tightened the privacy analysis! A natural question is whether we can extend this benefit more generally inject a "boundary out- come" as target when our private algorithm does not have one, then tighten the privacy analysis when queries are "far" from the boundary. We introduce next a method that achieves this goal.
provides more granular information on the value, its
2.7 The Boundary Wrapper Method
When the algorithm is tester or a classifier, the result is most meaningful when one outcome dominates the distribution A(D). Moreover, when performing sequence of tests or classification tasks we might expect most queries to have high confidence labels (e.g., [27, 1]). Our hope then to incur privacy cost that depends only on the "uncertainty." captured by the probability of non- dominant outcomes. When we have for each computation good prior on which outcome is most likely, this goal can be achieved via NotPrior targets (Section 2.1). When we expect the whole sequence to be dominated by one type of outcome, even when we don't know which one it is, this goal can be achieved via NotPrior with multiple targets (Section 2.5). But these approaches do not apply when a dominant outcome exists in most computations but we have no handle on it.
7

---

For private test A, can we choose a moving target per computation to be the value with the smaller probability arg min (0.1) Pr[A[D)= = b|? More generally. with a private classifier, can we some- how choose the target to be all outcomes except for the most likely one? Our boundary wrapper, described in Algorithm 4, achieves that goal. The privacy wrapper W takes any private algorithm A. such as tester or classifier, and wraps it to obtain algorithm W(A). The wrapped algorithm has its outcome set augmented to include one boundary outcome T that is designed to be a q-target. The wrapper returns T with some probability that depends on the distribution of A(D) and otherwise returns a sample from A(D) (that is, the output we would get when directly applying A to D). We then analyse the wrapped algorithm in TCT.
Note that the probability of the wrapper A returning T is most 1/3 and roughly proportional to the probability of sampling an outcome other than the most likely from A(D). When there is no dominant outcome the T probability tops at 1/3. Also note that a dominant outcome (has probability E [1/2, 1] in A(D)) has probability p/(2 p) to be reported. This is at least 1/3 when p 1/2 and is close to when p close to For the special case of A being a private test, there always dominant outcome.
A wrapped AboveThreshold test provides the benefit of Between/hreeholdde discussed in Sec- tion 2.6 where we do not pay privacy cost for values that are far from the threshold (on either side). This is achieved mechanically without the need explicitly introduce two thresholds around the given one and defining a different algorithm.
Algorithm 4: Boundary Wrapper
Input:
Dataset D = f
Fnf X", private algorithm A
f arg max, Pr) r]
The noat likely outcone of A(D) I/ Frobability that A doea not return the moat likely outcone
TD)) - 1 - Pr(A(D)= r
Ber(min { 3:
[1
// Coin for boundary // return boundary or value
1 then Return else Return A(D)
We show (proofs provided in Section E) that the wrapped algorithm is nearly as private as its base- line:
Lemma 2.7 (Privacy of a wrapped algorithm). If D-DP then Algorithm 4 applied to A is t(E)- DP where t(E) S f.c.
Lemma 2.8 (g-value of the boundary target). The outcome T of a boundary wrapper (Algorithm 4)
--11-1 of an s-DP algorithm is a T(e teerao-1y-target -target.
For small we obtain q ((E)/(((s (())). Substituting t(e) f we obtain q ~ 3. Since the target T has probability at most 1 /3, this is a small loss of efficiency (1/6 factor overhead) compared with composition in the worst case when there are no dominant outcomes.
The boundary wrapper yields weight privacy analysis that pays only for the "uncertainty" of the response distribution A(D) and can be alternative to more complex approaches based smooth sensitivity (the stability of A(D) to changes in D) [25, 10, 33). Note that the houndary-wrapper method assumes availability of the probability of the most dominant outcome in the distribution A(D), when it is large enough. The probability can always be computed without incurring pri- vacy costs (only computation cost) and is readily available with the Exponential Mechanism [24] or when applying known noise distributions for AboveThreshold, RetweenThresholle and Report- Noise-Max [9]. In Section F we propose Moundary-wrappee that only uses sampling access to A(D).
2.7.1 Applications Private Learning using Non-prrvacy--peserving Models
Methods that achieve private learning through training non non-private models include Private Aggre- gation of Teacher Ensembles (PATE) [26, 27] and Model-Agnostic private learning [1]. The private dataset D is partitioned into parts D = D, L... L D2 and model is trained (non-privately) on each part. For multi-class classification with e labels, the trained models can be viewed as functions (Ji X >> he]]. Note that changing one sample in can only change the training set of one of the models. To privately label an example drawn from public distribution, we compute the
8

---

predictions of all the models (z)( heejs] and consider the counts n, = EiEl 1ff(z)) = } (the number of models that gave label j to example a) for [c). We then privately aggregate obtain a private label, for example using the Exponential Mechanism [24] or Report-Noisy- MMxx [9, 29]. This setup is used to process queries (label examples) until the privacy budget is exceeded. In PATE, the new privately-labeled examples are used to train a new studen/ model (and {Li} are called teacher models). In these applications we seek tight privacy analysis. Composition over all queries for ((1) privacy, only allows for O(k²) queries. We aim to replace this with ((22) "target hits." " These works used combination of methods including SVT, smooth sensitivity, distance-to-instabile io-instabilityy and popose-test-relcat [10, 33J. The TCT toolkit can streamline the analysis:
(i) It was noted in [1, 27] that when the teacher models are sufficiently accurate, we can expect that Rj > k/2 on the ground truth label j on most queries. High-agreement examples are also more useful for training the student model. Moreover, agreement implies stability and lower privacy cost (when accounted through the mentioned methods) is lower. Instead, to gain from this stability, we can apply the boundary wrapper (Algorithm 4) on top of the Exponential Mechanism. Then use T as our target. Agreement queries, where max, n; > k/2 (or more finely, when h = arg max, n2 and n4 > max n1)) are very unlikely to be target hits.
(ii) If we expect most queries to be either high agreement max; n2 >> k/2 or no agreement max; n2 < k/2 and would like to avoid privacy charges also with no agreement, we can apply AboveThreshold test to max, n,. If above, we apply the exponential mechanism. Otherwise, we report "Low." The wrapper applied to the combined algorithm returns label in [c]. "Low," or T. Note that "Low" is a dominant outcome with no-agreement queries (where the actual label is not useful anyway) and class label in [c] is dominant outcome with high agreement. We therefore incur privacy loss only on weak agreements.
2.8
SVT with individual privacy charging
Our TCT privacy analysis simplifies and improves the analysis of SVT with individual privacy charg- ing, introduced by Kaplan al [20]. The input is dataset D E X and an online sequence of linear queries that are specified by predicate and threshold value pairs (fi, T:). For each query, the algo- rithms reports noisy AboveThreshold test results Exep f((x) Z T. Compared with the standard SVT, which halts after reporting T positive responses, SVT with individual charging maintains a separate budget counter Cg for each item æ. For each query with a positive response. the algorithm only charges items that contribute to this query (namely, all the Ir's such that fi(z) 1). Once an item x contributes charging improves utility with the same privacy budget, as demonstrated by several recent works [20, 6]. We establish the following:
7 hits (that is, C₂ 7), it is removed from the data set. This finer privacy
Theorem 2.9 (Privacy of Algorithm 5). Assume e < 1. Algorithm 5 is DP for every d e (0,
((T) +
Compared with prior work [20]: Algorithm 5 simply adds Laplace noise obtain f (EzED f((z)) + Lap(1/E) and then tests whether f. T, whereas [20] adds two independent Laplace noises and publishes the approximate sum f, for "Ahove-Threshold" without incurring ad- ditional privacy loss. Our analysis much simpler (few lines instead of several pages) and sig- nificantly tighter, also asymptotically: For the privacy bound in the statement of Theorem 5, our additive error is lower by a / /lo()))))ool/// 1og(1/8) factor. Importantly, our improvement aligns the bounds of SVT with individual privacy charging with those of standard SVT, bringing the former into the practical regime. See Section I for details.
Conclusion We introduced the Target Charging Technique (TCT), a versatile unified privacy anal- ysis framework that is particularly suitable when a sensitive dataset is accessed multiple times via differentially private algorithms. We provide an expansive toolkit and demonstrate significant im- provement over prior work for basic tasks such as private testing and one-shot selection, describe use cases, and list challenges for followup works. TCT is simple with low overhead and we hope will be adopted in practice.

---

Algorithm 5: SVT with Individual Privacy Charging
Input: Private data set X"; privacy budget 0: Privacy parameter 0. Ieitialize counter for isen
foreach E D C₂ for = 1, 1,2,.... do
// Receive queries
Receive a predicate fi X + [0, 1] and threshold 7: E R fi - CERED fi(()) - Lap(1/e)
11 Add Laplace noise to
if f 2 T; then
// Compare with threshold
Publish
foreach r E D such that [(x) > do
C₂ C2 +
if then Remove x from D
else Publish
Acknowledgement 1156/23)
Edith Cohen is partially supported by Israel Science Foundation (grant no.
References
[1] Raef Bassily, Om Thakkar, and Abhradeep Guha Thakurta. Model-agnostic private learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[2] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. CoRR, abs/211 1.03980, 2021.
[3] Mark Bun, Thomas Steinke, and Jonathan Ullman. Make Up Your Mind: The Price of Online Queries Differential Privacy, pages 1306-1325. 2017.
[4] H. Chernoff. A measure of the asymptotic efficiency for test of a hypothesis based on the sum of observations. Annals of Math. Statistics, 23:493-509 -099 1952.
[5] E. Cohen. Hyperloglog hyper extended: Sketches for concave sublinear frequency statistics. wtt.://wwwww///////...oo.
In KDD, ACM, 2017. full version: https: httpaa///axxvv.vrr//ae abr61677 06517.
[6] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
[7] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Generalized Private Selection and Testing with High Confidence. In 14th Innovations Theoretical Computer Sci- ence Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informaties (LIPles), Dagstuhl, Germany, 2023. Schloss Dagstuhl Leibniz Leibniz-Zentrum Zentrum für Informatik.
[8] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differentially private learning of thresholds and quasi-concave optimization. In Proceedings of the 55th Annual ACM Symposium on Theory Computing. STOC 2023, page 472 482, New York, NY, USA, 2023, Association for Computing Machinery.
[9] David Durfee and Ryan M. Rogers. Practical differentially private top-k selection with pay- what-you-get composition. In Hanna Wallach, Hugo Larochelle, Alina Beygelzimer, Flo- rence d' Alché Buc, Emily B. Fox, and Roman Gamett, editors, Advances in Neural Informa- tion Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver BC, Canada, pages 3527-3537 2019.
[10] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. STOC '09, New York, NY, USA, 2009. Association for Computing Machinery.
10

---

[11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensi- tivity in private data analysis. In TCC. 2006.
[12] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. STOC '09, page 381-390, New York, NY, USA, 2009. Association for Computing Machinery.
[13] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., ():211 1 407, aug 2014.
[14] Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51-60. IEEE Computer Society, 2010.
[15] Flajolet, E. Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The analysis of near-optimal cardinality estimation algorithm. In Analysis of Algorithms (AofA). DMTCS, 2007.
[16] P. Flajolet and G. N. Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31:182 109, 1985.
[17] Arik Friedman and Assaf Schuster. Data mining with differential privacy. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 10, page 193-502, New York, NY, USA, 2010. Association for Computing Machinery.
[18] Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy- preserving data analysis. In 51th Annual IEFE Symposium on Foundations of Computer Sci- ence, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 61-70. IEEE Com- puter Society, 2010.
[19] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversar- ially robust streaming algorithms via differential privacy. In Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2020.
[20] Haim Kaplan, Yishay Mansour, and Uri Stemmer. The sparse vector technique, revisited. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2747-2776. PMLR, 2021.
[21] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phwenix, AZ, USA, June 23-26, 2019, pages 298-309. ACM, 2019.
[22] Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proc. VLDB Endow., 1066)63776448 2017.
[23] Frank McSherry and llya Mironov. Differentially private recommender systems: Building pri- vacy into the netflix prize contenders. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09, page 627-636, New York, NY, USA, 2009, Association for Computing Machinery.
[24] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 94-103. IEEE Computer Society, 2007.
[25] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, page 75-84, New York, NY, USA, 2007. Association for Computing Machinery.
[26) Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian J. Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. In 5th International Conference on Laaning Representations, ICLR 2017, Toudon, France, April 24-26, 2017, Con- ference Track Proceedings. OpenReview.net, 2017.
11

---

[27] Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Ülfar Erlingsson. Scalable private learning with PATE. 6th International Conference on Learning Representations, ICIR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[28] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with Rényi differential privacy. In The Tenth International Conference Learning Representations. ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[29] Gang Qiao, Weijie J. Su, and Li Zhang. Oneshot differentially private top-k selection. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8672-8681 PMLR, 2021.
[30] Aaron Roth and Tim Roughgarden. Interactive privacy via the median mechanism. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposiun on Theory of Com- puting, STOC 2010, Cambridge, Massachusetls, USA, 5-8 June 2010, pages 765-774. ACM, 2010.
[31] Adam Smith, Shuang Song, and Abhradeep Thakurta. The flajolet-martin sketch itself pre- serves differential privacy: Private counting with minimal space. In Proceedings of the 34th International Conference Neural Information Processing Systems, NIPS' 20, 2020.
[32] Thomas Steinke and Jonathan R. Ullman. Tight lower bounds for differentially private lection. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 552-563. IEEE Com- puter Society, 2017.
[33] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via sta- bility arguments, and the robustness of the lasso. In Shai Shalev-Shwarz and Ingo Steinwart, editors, Proceedings of the 26th Anmual Conference on Learning Theory, volume 30 of Pro- ceedings of Machine Learning Research, pages 819-850, Princeton, NJ, USA, 12-14 Jun 2013. PMLR.
[34] Salil P. Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials the Foundations of Cryptography, pages 347-450. Springer International Publishing. 2017.
[35] Yuqing Zhu and Yu-Xiang Wang. Adaptive multi-label pate. In Gustau Camps-Vall Francisco R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, vol- ume 151 of Proceedings of Machine Learning Research, pages 5622-5635. PMLR, 28-30 Mar 2022.
with adaptive k and application
12

---

A Preliminaries
Notation. We say that function f over datasets is t-Lipschitz if for any two neighboring datasest D D', it holds that [fD)) - f(D)) I e= b.
For two reals a, and O, we write a ~ b
For random variables X X1, say that they e-indistinguishable, denoted X R X1, their max-divergence and symmetric counterpart are both at most e. That is, for E {0, 1), Es[ maxscsupp(X*) In Pr[X 'ES] E.
We similarly say that for d 0, the random variables are ( -indistinnguihaable denoted X 2,,6 X if for E {0
Pr[X E E 0 Pr[XI-be E.
max In SCsupp( X
For two probability distributions, BD, B' We extend the same notation and write B =e B and Bd Re, B² when this holds for random variables drawn from the respective distributions.
The following relates (e, 0) and (e, -iniiiiiiisinuuihabbiittt with 5 = 0 and 6 > 0.
Lemma A.1. Let B B² be two distributions. Then Bddh Re,8 B if and only if we can express them as mixtures
B = =1-1100 N E.
where No Re N
We treat random variables interchangeably distributions, and in particular, for randomized al- gorithms A and input we use A(D) to denote both the random variable and the distribution.
For space of datasets equipped with symmetric neighboring relation, we say an algorithm A s- DP (pure differential privacy). ). for any two neighboring datasets D and D' A(D) Re A(D'). Sim- ilarly, we say A is (c, 8DP (approximate differential privacy) if for any two neighboring datasets D, D', it holds that A(D) Re.6 A(D") [11]. We refer to c, 8 as the privacy parameters.
A private test is differentially private algorithm with Boolean output (say in (0.
Remark A.2. The literature in differential privacy uses different definitions of neighboring datasets. TCT, and properties these preliminaries, apply with any symmetric relation over the space of possible input datusets.
The following is immediate from Lemma A.I:
Corollary A.3 (Decomposition of an approximate DP Algorithm). An algorithum A is (E if and only for any two neighboring datasets D and D we can represent each distribution A(D*)
(b E {0, 13) as a mixture
A(D*) = (1 (1- - 5) No +5.E
where No me N
Differential privacy satisfies the post-pree post-processing property (post-processing of the output of a private algorithm remains private with the same parameter values) and also has nice composition theorems:
Lemma A.4 (DP composition [11, 14]). An interactive sequence ofr executions of sDD algorithms satisfies (e', O)DP for
e' = re and 8 = 0 by basic composition [11], or
for any 5 > 0.
e' -ra² Eev 2r log(1/5).
by advanced composition [14].
13

---

A.1 Simulation-based privacy analysis
Privacy analysis of an algorithm via simulations performed by simulating the original algorithm A on two neighboring datasets D D The simulator does not know which of the datasets is the actual input (but knows everything about the datasets). Another entity called the "data holder" has the 1 1-bit information b E (0, on which dataset it is. We perform privacy analysis with respect to what the holder discloses to the simulator regarding the private bit b (taking the maximum over all choices of D D )D)). The privacy analysis is worst case over the choices of two neighboring datasets. This is equivalent to performing privacy analysis for A.
Lemma A.5 (Simulation-Nan based privacy analysis). [8] Let be an algorithm whose input dataset. If there exist a pair of interactive algorithms S and H satisfying the following 2 prop- erties, then algorithm A (e, (D.P.
D and for every bit b {0, 1) it holds that 1. For every two neighboring datasets D
(S(D", ,D) + H(D",'', DD,b)) A(D*).
Here (S(DO, D H(D", D', .)) denotes the outcome of S after interacting with H.
2. Algorithm is (e, ().B) w.r.t. the input bit b.
A.2 Privacy Analysis with Failure Events
Privacy analysis of randomized algorithm A using designated failure events is as follows:
1. Designate some runs of the algorithm as failure events.
2. Compute an upper bound on the maximum probability, over datasets D, of a transcript with failure designation.
3. Analyse the privacy of the interaction transcript conditioned on no failure designation.
Note that the failure designation is only used for the purpose of analysis. The output on failure runs restricted (e.g., could be the dataset D)
Lemma A.6 (Privacy analysis with privacy failure events). Consider privacy analysis of A with failure events. If the probability of failure event is bounded by 8 E [0. and the transcript conditioned on non-failure is (ED then the algorithm is (e, 8 -
Proof. Let D and D be neighboring datasets. From our assumptions, for b {0, 1}. we can represent A(D*) as the mixture A(D*) (1 5t). ZZ + - - Fb, where Z Re Z and 8(b) S 8*.
From Lemma A.1, we have Z (1 81- No + 8' E., where No Reg N
Then
A(D*) = (1 (1-86% 8(h)) z + 80h) (bt)
= =(1 - 8*) 2 + (8- 5(6)) - 5(6) Fb.
(1 8*): z 8" (1 {(b) /8*) Z + 5(4) F²)
(1 8* 8*)(1 8') No (1 8* 8*)8'' 3). Eb + 8' (11 zz + 8 Fb)
(1 8* - 8') No 8'5- N (1 5'' E² 5 (11 5(0) 15)) 1-))0) z + 5(0) pb)
The claim follows from Corollary A.3.
Using simulation- based privacy analysis algorithms (optionally with designated failure events) as a respective interactive sequence of pure- DP algorithms where the å parameters anlaysed through failure events. This simplifies analysis:
treat an interactive sequence of approximate-DD
We can relate the privacy of composition of approximate-DD algorithms to that of a composition of corresponding pure-DP algorithms:
14

---

Corollary A.7 (Composition of approximate-DD algorithms). An interactive sequence of (Ei, 6.)-
DP algorithms (i [k)) has privacy parameter values (c', + +x 6z), where (e',8') are privacy parameter values of a composition of pure (si, D--D algorithms E [k]
Proof. We perform simulation-based analysis. Fix Uwo neighboring datasets D D For an (ss. &:)- DP algorithm, we can consider the mixtures as in Corollary A.3. We draw Ber( 6 and if designate the output as failure and return r E(b), Otherwise, we return r ( The overall failure probability is bounded by 1 1- I[; (1 6:) S E; 6, The output conditioned on non-failure is a composition of (e;, O)-DP algorithms (i [K:)). The claim follows using Lemma A.6.
B The Target-Charging Technique
We extend the definition of g-targets (Definition 2.1) so that it applies with approximate DP algo- rithms:
Definition B.1 (q-target with (e.d) of pair of distributions), Let A + y be a randomized algo- rithm. Let Z and Z be two distributions with support V. We say that T S y is q-target of (Z), Z with (e, where > 0 and 8 E [0, 1), if there exist p E [0, 1] and five distributions C, Bd, and Eb (for b E (0,1)) such that Z and Z can be written as the mixtures
z = (1 (1- (p C (1 (1-p) p)- -B) -55- E
z' = (1 6) C+ p) . BB) +
where B me Bd, and min (Pr(B" E T], TT) 24
Definition B.2 (q-target with (8 of a randomized algorithm). Let A + y be a randomized algorithm. We say that T E y is a q-targel of A with (e, 5), where e >> 0 and ō E [0,1), 1), for pair D D of neighboring datasets, T is q-target with (E, of A(D") and A(D").
any any
We can relate privacy of an algorithms or indistinguishabiiiyy of two distributions to existence of q-targets:
Lemma B.3. (f Z have a q-target with (e, then Z =e,8 Z Conversely, if Re,8 Z then (Z", 3 have 1-target with (e, 6) (the full support is 1-target).
(ii) If an algorithm has a q-target with (E, then A is (e, DD.. Conversely, an algorithm A (e, 8)-P then it has I-target (the set Y) with (E,
Proof. If two distributions Bd, B' have a g-target with (c, 5) than from Definition B.1 they can be represented as mixtures. Now observe the Bd me BA then the mixtures also satisfy p. C + (1
p) BB ~ C + (1 p) B Using Lemma A.1, we get Z 25,6 Z'
For (ii) consider A and two neighboring datasets D and D Using Definition B.2 and applying the argument above obtain A(D*) Re.5 A(D'). The claim follows using Corollary A.3.
Now for the converse. If 0 R5,5 Z then consider the decomposition as in Lemma A.1. Now we set p- = and B¹ < No to obtain the claim with and the target being the full support.
For (ii), if A - ) is 0)DP then consider neighboring (D*, D2}. We have A(D*) Re A(D*). We proceed as with the distributions.
Algorithm is an extension of Algorithm that permits calls to approximate DP algorithms. The extension also inputs bound on the number of target hits and a bound Ta on the cummulative d parameter values of the algorithms that were called. We apply adaptively a sequence of (c. (DP algorithms with specified q- gatargets to the input data set D and publish the results. We halt when the first of the following happens (1) the respective target sets are hit for a specified number of times (2) the accumulated d-values exceed the specified limit 78-
The privacy cost of Thrget-Charging as follows (This a precise and more general statement of Lemma 2.2):
15

---

Algorithm 6: Target Charging with Approximate DP
Input: Dataset D {.1,...> ;.n] X". Integer 7 (Upper limit the numher of target hits). T4 2 (upper limit on cumulative parameter). Fraction & [0, 1].
C 0, Cs +
// Initialize target hit and failure counters // Main loop Receive (A., T() where A, is (DD mechanism, and T3 is q-target with (e, for A
for i = 1.... do
-.
ifCs + 6 T5 then Halt
C3 < +
1/ tCT charge for &
Publish r
if T then
// Charge q-targat
f- C+1
C r then Halt
Algorithm 7: Simulation of Target Charging
Input: Two neighboring datasets Dº, D', private E (0, 1]. 7 E N, va E 122. y E [0, 11, > C' - 0, Cs +- 0, / <- 0 Initialize; h is counter the number nen-fail calls to data holder Main loop
io 1.... do
Receive (A,, T() where A, 6.DD, mechanism, and is g-target with (e, 6,) for
Cs + 6, > Ts then Halt
Cs < Cs 4 5
Let E 00. 1]. C. B
and E (for E (0, (0, such that (p C p) Bd +-E
me Bd. and
A(D")
// By Dafinition 8.2 11 Non-private Data Holder call with Failure
Ber(() = then
Fail
Publish
else
if Ber(p) = then Publish C
No access to data holder
else
Publish
B
// e-DP Holder Call counter of e-private data holder calls
h
+1 h (1 a)7/9 then
// Nunber of Holder calls exceeded linit
L Fail
if E T then
I/ putcona target hit
C < C+1
if C 7 then Halt
Theorem B.4 (Privacy of Harget-Charging), Algorithm 6 satisfies the following approximate DP privacy bounds:
(1 (1+a) a.o
for any a > 0:
1 (( q
E + (1+ a) log(116), +G ( Co
for any 8 0, a
- where (T( se शीम and Cs S TB is as computed by the algorithm.
Proof. We apply the simulation-based privacy analysis in Lemma A.5 and privacy analysis with failure events (Lemma A.6).
The simulation is described in Algorithm 7. Fix two neighboring data sets D and D The simulator initializes the target hit counter C' <- and the cumulative 8-values tracker Cs +- 0. For proceeds as follows. It receives (Ag, Ti) where A; is (e, JDP. If Cs + 8, > it halts. Since T;
g-target for AG, there are p. C. B B E and E as Definition B.2. The simulator flips biased coin c' ~ Ber()). If c' it outputs E and the execution is designated as Fail. In this
16

---

case there is an interaction with the data holder but also failure designation. The simulator flips a biased coin Ber(p). c 1, then the simulator publishes a sample require an interaction with the data holder). Otherwise, the data holder is called. The data holder publishes r' B We track the number of calls to the data holder. If h exceeds (1 + a)) /g. we designate the execution as Fail. Ifr E T, then C' is incremented. If C = т, the algorithm halts.
C (this does not
The correctness of the simulation (Taithfully simulating Algorithm 1 on the dataset D$) is straight- forward. We analyse the privacy cost. We will show that
(i) the simulation designated failure with probability at most C3 8 aT,
(ii) Conditioned on no failure designation, the simulation performed at most r = (1 + + adaptive calls to (e, 0)-DP algorithms
Observe that (ii) is immediate from the simulation declaring failure when h > r. We will establish (i) below.
The statement of the Theorem follows from Lemma A.6 and when applying the DP composition bounds (Lemma A.4). The first bounds follow using basic composition and the second follow using advanced composition [14].
This analysis yields the claimed privacy bounds with respect to the private bit b. From Lemma A.5 this is the privacy cost of the algorithm.
remains to show bound the failure probability. There are two ways which a failure can occur. The first on each call, with probability 6,. This probability is bounded by 1 1-II. 6, S Σ, 6, S Cs- The second is when the number / of private accesses to the data holder exceeds the limit. We show that the probability that the algorithm halts with failure due to that is most 8*.
We consider a process that continues until r charges are made. The privacy cost of the simulation (with respect to the private bit b) depends on the number of times that the data holder is called. Let X be the random variable that is the number of calls the data holder. Each call E-DP with respect to the private b. In each call, there is probability at least for a "charge" (increment of C).
A failure is the event that the number of calls to data holder exceeds (1 o/)7/g before charges are made. We show that this occurs with probability at most 8* (T,,a)):
Pr x
_ s (T,
(1)
To establish (1), we first observe that the distribution of the random variable X is dominated by a random variable X' that corresponds a process of drawing i.i.d. Ber(y) until we get successes (Domination means that for all m. Pr[X' > m] 2 Pr(X > ml). Therefore, it suffices to establish that
Pr x' x1+
s (T,
Let Y be the random variable that is sum of m 1+ (1 + a i..dd Ber(g) random variables. Note that
Pr x' > (1 (1+) = PPrYY <r)
We bound Pr(Y < r] using multiplicative Chernoff bounds [4]². The expectation is μ mg and we bound the probability that the sum of Bernoulli random variables is below I4al = (1- - Ita ).
a
Using the simpler form of the bounds we get using μ mg 2 (1 + a)r
2
Pr|y < = Pr(y < (1 I+a
)m] Se " S -
Bounn can be tightened when using precise tail probability values.
17

---

Remark B.5 (Number of target hits). The TCT privacy analysis has a tradeoff between the final "E" and "8" privacy parameters. There is multiplicative factor of of (1+ + a) (v1+ a with advanced composition) on the "e" privacy parameter. But when use a smaller a need larger value of т to keep the "8" privacy parameter small. For a given a, 8* > we can calculate a bound on the smallest value of r that works. We get
2 2 a =2 (1+a) in (ca((taa (1 a) -1/(+ta))))))))))))))))))))))))) -In(1/8*)
-I((1/8)
(simplified Chernoff)
a
1
(raw Chernoff)
For a = 0.5 we get > 10.6 In(1/6*). For a we get T > 3.26 Im(1/6*). For a we get 0.31 In(1//*).
Remark B.6 (Mix-and-match TCT). TCT analysis can be extended to the case where gorithms with varied privacy guarantees & and varied qi values? In this case the privacy cost depends (D)A( 5., The analysis relies tail bounds on the sum of random variables, is q," more complex. Varied values means the random variables have different size supports. A simple coarse bound is according to the largest support, which allows to use a simple counter for target hits, but may be lossy with respect to precise bounds. The discussion concerns the (analytical or mamerical) derivation of tail bounds is non-specific to TCT and is tangential to our contribution.
al-
B.1 Multi-Target TCT
Multi-target charging is described in Algorithm 8. We show the following
Lemma B.7 (Privacy of multi-TCT),, Algorithm 8 satisfies (E', k.6' >-aproxximate D)P bounds, where (e', (²) are privacy bounds for single-target charging (Algorithm f).
Specifically, when we expect that one (index) of multiple outcomes Li...., will dominate our interaction but can not specify which one it is in advance, we can use k-TCT with NotPrior targets with priors -...... -A. From Lemma B.7, the overall privacy cost depends on the number of times that the reported output is different than the most dominant outcome. More specifically, for private testing, when we expect that one type of outcome would dominate the sequence but we do know if it is 0 or 1, we can apply 2-TCT. The total number of target hits corresponds to the less dominant outcome. The total number of privacy charges (on average) is at most (approximately for small s) double that, and therefore is always comparable or better to composition (can be vastly lower when there dominant outcome).
Algorithm 8: Multi- Charging
Input: Dataset D = { [n) E X". Integer 7 2 1 (charging limit). Fraction 9 E [0, 1]. k 1 (number of targets).
for i E [k] do C <- 0
// Initializa charge countars // Main loop
while min C2 < do
Receive (A,, (T<))e)4) where A is an e-DP mechanism, and T; is g-target for A
r r- *+)(D)
Publish
for i E [k] do
if e T, then C₁ - C. +1
// outcone is in g-target T
Proof of Lemma B.7 (Privacy of mulliiiTaaaee TCT). 'Let (c, be the privacy bounds for M2 that is single-target TCT with (A,, T4). Let M the k-target algorithm. Let T be the ith target in step
"One of applications of revise calls conditional release (see Section D applies TCT with both e-DP 2D-DP algorithms even base eDD algorithm) We note that the claim generally holds for online privacy analysis with the best of multiple methods. We provide proof specific multi-target charging below.
18

---

We say that an outcome sequence R = (r,)}=1 E is valid for i E [k] if and only if M; would halt with this output sequence, that is, Σー [ E T = T and Th E T. We define G(R) C [R] to be all i E [k] for which R is valid.
Consider set of sequences H. Partition H into k + 1 sets H, so that Ho {R H G(R) = 0} and H, may only include R E for which i E G(R). That is, Hu contains all sequences that are not valid for any and H; may contain only sequences that are valid for
k
Σ Pr(M(D) E H.) = Σ Pr[M((D) E H.l
Pr(M(D) E HJ
(C(.P(()))) E H. = Σ Pr(M.(D') H.] + 8-8
e Pr(M(D)) H| k.
C Properties of NotPrior targets
Recall that a NotPrior target of an (E, 6D- algorithm is specified by any potential outcome (of choice) that denote by I. The NotPrior target is the set of all outcomes except I. In this Section we prove (a more general statement of) Lemma 2.3:
Lemma C.1 (Property of a NotPrior target). Let M X - p (U( where 1 & y. be an (e, 8)-D algorithm. Then the set of outcomes y constitutes e1+1 -target with (c, 5) for M.
We will use the following lemma:
Lemma C.2. two distributionss Z Z with support yU satisfy Z me Z then constitutes an targett with (c,0) for (Z) Z
Proof of Lemma 2.3. From Definition B.2, it suffices show that for any two neighboring datasets, D and D., the set y is an 5 target with (c,5) for (M(D"), M(DD)) (as in Definition B.1).
Consider two neighboring datasets. We have M(Do) = M(D'). Using Lemma A.1, for b e {0, 1) we can have
M(D') = (1 6) No + + E..
(2)
where No Re N From Lemma C.2, y a 1 ---4-targer with (c, 0) for (No, (NO.N)). From Defini- tion B. and (2), this means that y is
1 c+41 -target with (E for (M(D"),M(D'))
C.1 Proof of Lemma C.2
We first prove Lemma C.2 for the special case of private testing (when the support is (0, 1)): Lemma C.3 (target for private testing). Let Zo and Zt with support (0, satisfy Z mg Zt Then T = (1) (or T = {0}) is an e-41 -target with (c, 0) for (Z ).
Proof. We show that Definition B.1 satisfied with = {1}, q c1 and (e, 0), and Z Z
1
म = Pr E T] T' = Pr E T]
be the probabilities of T outcome Z and Z respectively. Assume without loss of generality (otherwise we switch the roles of Z and Z that T'' 2 If I the choice of 0 and Bd Z (and any C) trivially satisfies the conditions of Definition 2.1. Generally, (also for all
19

---

Let
x'C= π
p= 1
e
Note that since Z 2₂ Zt it follows that x' Re and (1 11-7 x') Re (1 r) and therefore
p E [o, 1] for any applicable S π S n'
1.
Let be the distribution with point mass on {0).
Let B Ber(1
-- Ber --e-r-
Let B
Ber(1
5' =xx-x)) Ber efal-a)
1 We show that this choice satisfies Definition 2.1 with q = 2-41
We show that for both E 1). Z' p C + (1 p) Bd: It suffices to show that the probability of I. is the same for the distributions both sides. For b 0, the probability I. in the right hand side distribution
7-C - π
n π
e-
6
-
6 1
For b = 1, the probability is
T'E k
n'E²
π.'
p+ (1 p)
e π
π
E
6 1
e π
9'6 π
n' π
1
1
6
e T
T'C π
π
π
7
6
e
We show that for E {0, 11. Pr[B E T
1
-- -T
Pr[BO T =
n' ह-
π e E
e - 1
1
e غ
2
+1
n' 7'f - 1)
Pr(B TT]
a ee π
(e 1)
6
2e π
c -
e +1
Note that the inequalities are tight when n' = (and are tighter when n' is closer to œ). This means that our selected is the largest possible that satisfies the conditions for the target being T.
We show that B and B' are i-idistinguishable, that is
Ber(1 T' e ह ~ Ber(1 n/
e -
Recall that Ber(a) Re Ber(b) if and only if Re b and (1 a) me (1 b). First note that
x'
n' e 2 π
e n
Hence
π
n π
e
It also holds that
n
1 15
c
7
x -
20

---

Proof of Lemma C.2. The proof is very similar to that Lemma C.3, with a few additional details since T = y can have more than one element (recall that - is single element).
Assume (otherwise we switch roles) that Pr[Z 11 Pr(Z 1]. Let
π = Pr|Z y n' PriZ V/.
Note that n 2
We choose p. C. B B² as follows. Note that when क 2 e+4 then the choice of p and B Z satisfies the conditions. Generally,
Let
N'e π
p=
e
Let C be the distribution with point mass 1.
Let B be 1 with probability x'-x and otherwise (with probability M- conditioned on the outcome being in V
be Z
Let B² be 1 with probability s'-m and otherwise (with probability e' ditioned on the outcome being in y
of e'n'=x' 6-x--
be Z con-
It remains to show that these choices satisfy Definition 2.1:
The argument for Pr(B* E E
- ef is identical to Lemma C.3 (with y = T).
We next verify that for b E 10: Z = C+ (1 - The argument for the probability of I is identical to Lemma C.3. The argument for y follows from the probability of being y being the same and that proportions are maintained.
For the probability of in the right hand side distribution is
(1 - p) - me Pr y)
Pr = v) Zr <
Pr|z y).
- Pr|Zo E y = π.
For = 1, the probability of y E y in the right hand side distribution is
(1-p) ह - n²'
Pr = =/ Pr(Z y]
e Pr E Pr yl
Pr y).
Finally, we verify that 8 and are e-indistinguishable. Let W C y. We have
T(1 - - -² 2m
Pr|Z E W]
e- - e'E Pr|z E W]
Pr[B E w]
T'e 1)
Pr[Z W
e 1
Pr/B E W
Pr W
e'
n'
N'e=
Therefore
Br E W]
Zr E W] Pr E W
Pr W
and we use z Re Zt, The case W identical to the proof of Lemma C.3. The case 1. E W follows.
21

---

D Conditional Release with Revisions
In this section we analyze an extension to conditional release that allows for revision calls to be made with respect previous computations. This extension presented in Section 2.3 and described in Algorithm 2. conditional release applies a private algorithm A + y with respect to subset of outcomes T V. It draws y A(D) and returns y if y T and I otherwise. Each revise calls effectively expands the target to Tn U U', when T₁, is the prior target and T' a disjoint extension. If the (previously) computed result hits the expanded target (y T'), the value y is reported and charged. Otherwise, additional revise calls can be performed. The revise calls can be interleaved with other TCT computations any point in the interaction.
D.1 Preliminaries
For distribution Z with support y/ and W y denote by Zw the distribution with support W U {1) where outcomes not in W are "replaced" by I. That is, for E W, Pr(Zw y Pr[Z and Pr[Zw = 1| == Pr[Z & W).
For a distribution with support y and C we denote by Z W the conditional distribution of Z on W. That is, for W, Pr[(Z W) = y] :- PriZ v Pr[Z e W).
Lemma D.1. B8 R8.5 B² then Byy Re.5 BW
Lemma D.2. Let Bº, B' be probability distributions with support y such that B me B Let W C ). Then B" W #32 B I..
We extend these definitions to a randomized algorithm A, where Aw (D) has distribution A(D)w and (A (DD has distribution A(D) W. The claims in Lemma D.1 and Lemma D.2 then transfer to privacy of the algorithms.
D.2 Analysis
To establish correctness, remains to show that each LanditionnaReleaan call with an (e. 8DDD algorithm A can be casted in TCT call to an (e, d)DP algorithm with NotPrior target and each ReviseCR call cap be casted as a call to an 2c-DP algorithm with a No NotPrior target.
Proof of Lemma 2.5. The claim for Condit t onalRelease was established in Lemma 2.4: Con- ditional release Conditional SondittonalReeesee (A,, T) calls the algorithm AT with target T. From Lemma D.I, AA is (c, 6)D when is (e, DP. constitutes NotPrior target for AT with respect to prior 1.
We next consider revision calls deseribed in Algorithm 2. We first consider the case of a pure-DP A (8 = 0).
When intiitionnnReelesse publishes L. the internally stored value тh conditioned published is sample from the conditional distribution A(D) -T.
We will show by induction that this remains true after ReviseCR calls, that is the distribution of Th conditioned on being returned in all previous calls is A(D) -TA where Ty is the current expanded target.
An ReviseCR call with respect current target Tn h and extension T' can be equivalently framed as drawing r ~ A(D) -Tu. From Lemma D.2, AA is s-DP then A -Tx is 2e-DP. If E T we publish and otherwise we publish 1. This conditional release computation with respect to the 2a-DP algorithm A -T,, and the target T'. Equivalently, it is call to the 2s-DP algorithm (A -T,)T with NotPrior target T'.
Following the ReviseCR call, the conditional distribution rh conditioned on 1 returned in the previous calls is A(D) -(T U T') claimed. We then update T +- T TT.
remains to handle the case 5 > 0. We consider ReviseCR calls for the case where A is (c, 8)- DP (approximate DP). In this case, we want to show that we charge for the å value once, only on the original Conditi onalRelease call. We apply the simulation- Theorem B.4 with two fixed neighhoring datasets. Note that this can be viewed as each call being
analysis in the proof of
22

---

with a pair of distributions with an appropriate g-target (that in our case is always a NotPrior target).
The first ManditionalRleaaan call uses the distributions A(D)) and A(D"). From Lemma A, they can be expressed as respective mixtures of pure No ~ N part (with probability 1 - 6) and non-private parts. The non non-private draw is designated failure with probability 6. Effectively, the call in the simulation is then applied to the pair (Nę, N with target T.
A followup ReviseCR call with respect to the previous target Tx, and target extension T', The call is with the distributions (No TTA)T> that using Lemma D.1 and Lemma D.2 satisfy (No T Siz (N' TT)
E Boundary Wrapper Analysis
In this section we provide details for the boundary wrapper method including proofs Lemma 2.7 and Lemma 2.8. For instructive reasons, first consider the special case of private testing and then outline the extensions to private classification.
Algorithm 4 when specialized for tests first computes π rDD) min -, = 0.). returns T with probability 17(1+ + т) and otherwise (with probability 1/(1 - T)) return A(D).
Overall, we return the less likely outcome with probability 7/(1 + x), and the more likely one with probability (1 - /1 T).
Lemma E.1 (Privacy of wrapped test). If the test e-DP then the wrapper test is ((e)-DP where (() < ge.
Proof. Working directly with the definitions, ((E) is the maximum of
1 π
max
S
(3)
E0, 1/2)
+ _ - π
3
e F
1 π
max (0,1/2)
8
(4)
1 5
π
- π
max #E( 2 11tee)
In
8
(5)
1
1 -
2 - TT
max
In
5 3
(6)
TE( (= THee
1
65
max
ln
8
1 1
e
Inequality (3) bounds the ratio change the probably of the larger probability outcome when remains the same and (4) the ratio change in the probability of the smaller probability outcome when remains the same between the neighboring datasets. When the less probable outcome changes between the neighboring datasets it suffices to consider the case where the probability of the initially less likely outcome changes to e > 1/2 so that e π < т, that the change is from и to e where (%2 1+te)) ). Inequalities and correspond to this case. The wrapped probabilities of the T outcome are the same as the less probably outcome in the case that it is the same in the two databases. Inequality 7 corresponds to the case when there is change.
We now show that T is a target for the wrapped test.
Lemma E.2 (g-value of the boundary target). The outcome of a boundary wrapper of an s-DP e(e)) test is 21 -target.
Proof. Consider two neighboring datasets where the same outcome is less likely for both and æ S n'. Suppose without loss of generality that 0 is the less likely outcome.
The common distribution (C) has point mass on 1.
23

---

The distribution B is a scaled part of M(D") that includes all 0 and T outcomes (probability <e /1 + œ) each) and probability of A e of the 1 outcomes, where A I+*
I+
The distribution B' is a scaled part of M(D*) that includes all 0 and T outcomes (probability x' r11(1 x') each) and probability of A ألoー of the 1 outcomes.
easy to verify that B (s)) B and that
2T
2m
el(e)
1 -
A
1 + n
(((6)
-
1
(6)
2T'
((c)
2T
+ n' el(E)
-1
+ e
ed(s) - (e((e)
2
n²
π
1 1 n²
1+
Using 14
S
H' 1+x
and
の we obtain
I+
q
((())
-1
2
ed(E)
r¹
1-x
It
(s)
-
2
et(=)++ -
Extension to Private Classification To extension from Lemma E.1 Lemma 2.7 follows by noting that the same arguments also hold respectively for sets of outcomes and also cover the case when there is no dominant outcome and when there is transition between neighboring datasets from no dominant outcome to a dominant outcome. The extension from Lemma E. to Lemma 2.7 also straightforward by also noting the cases above (that only make the respective A smaller), and allowing C to be empty when there is no dominant outcome.
F Boundary wrapping without a probability oracle
We present borpdigg method that does assume probability oracle. This method accesses the distribution A(D) in a blackbox fashion.
At very high level, show that outcomes. Then, denote by y the range of the algorithm A. We can show that = {(y, s/) y o v'} S Y' ) is an -taa-tt of this procedure. That is, if the analyst observes the same outcome twice, she learns the outcome "for free". the two outcomes are different, the analyst pays O(e) of privacy budget, but she will be able to access both outcomes, which is potentially more informative than single execution of the algorithm.
can an (s, O)-DP algorithm A twice and observe both
X > y is an (e, DD algorithm where | < Co. Denote by A c A the following algorithm: on input D, independently run A twice and publish both outcomes. Define E = {3, 1') # v/} C x y. Then, A a (2s, DDP algorithm, and a f(E)-target for A o A, where
Lemma F.1. Suppose
f(e) 1 e (2
Proof. Ao is (2e, DD by the basic composition theorem. Next, we verify the second claim. | Let D, D' be two adjacent data sets. For each E [m]. p. Pr(A(D) i]. P Pr(A(D') i).
Identify elements of 3' as 1, 2,
let
24

---

We define a distribution C. For each i E [m²] define to be the largest real such that
- qi E le (v,² q.), e (r, - -:1l-
Then, we define C to be a distribution over {(t, i) : [m]] where Pr(C = (i, i)] Σ
We can then write (Ao (DD =a C (1- a) No and A) =a a. C+ (1--a)) N', where a Σ; q. and N and N' are 2 i--inisstinguihable.
Next, we consider lower-bounding Pr[N" = 3/) : y + vl) The lower bound of Pr(N (u. 3/) : y A y'] will follow from the same argument. Indeed, we have
Pr[No (v.D') :9: 5/1 E p:) Pr Pr (v.
E.P² 96
We claim that
p qi S p.. The inequality is trivially true if p2 < 1-pp
2 Otherwise, we can observe that for q == 2;²pp;²
12 -1
O, have p,2 - q 1 p²² and p/.2 q p.2. Since 1 - pf [e 20 p?) ) e²c -p;)] this implics that g can only be larger than
Since we also trivially have that pł
S p:?. we conclude that
Pr[No = (y. 3') y ン
E.p(1 pi) Σ. min(y, v!.)
P.pi(1- - -p;)
Pr[No y v)]
E, mimmi( (pt 62e pp
Next, is straightforward to show that, for every p E [0, 1]. one has
p(1-p) p) min(p?, 22 (1-
1 1--P
p
1 e2 /(1 + (2))
min
(<((pt)))
2
e2
V
Consequently,
Pr[No (v.5')
Pr(N" (v. :
Pr[No (3.0)) y v + Pr = (y.v)) 21 2
as desired.
Remark F22 For a rypical use case where c = 0.1, we have f(e) so 0.258. Then, by applying Theorem B.4, on average we pay = 8 privacy cost for each target hit. Improving the constant of is a natural question for future research. We also note that while the overhead is more significant compared to the boundary wrapper of Algorithm the output more informative it includes two independent responses of the core algorithm whereas Algorithm 4 returns one or none (when T is returned). We expect that is possible to design less-informative boundary wrappers for the case of blackbox access (no probability oracle) that have a lower overhead. We leave this as an interestion question for followup work.
G q value for BetreenThreehoods
We provide details for the BetweenThreeshldds classifier (see Section 2.6). The BetweenThresholds classifier is a refinement of AboveThreshold. Lipschitz function f. two thresholds te < tr, and a privacy parameter E. We compute f(D) f(D) + Lap()/=), where Lap is the Laplace distribution. If f(D) < te we return L. If f(D) > tr return H. Otherwise, return T.
is specified by 1-
Lemma G.1 (Efffectiveness of the "hetween" target). The T outcome is an (1 - (() target BetweenThreshol.s
Proof. Without loss of generality we assume that l. 0 and = I/e for parameter 1.
Consider two neighboring data sets D and D and the respective S(D)) and S(D*). Since f is 1-Lipschitz, can assume without loss of generality (otherwise we switch the roles of the two data
25

---

sets) that f(D")= S f(D") S f(D" + Consider the case f(D)) I O. The case f(D") 2 t/s is
symmetric and the cases where one or both of f(D") are in (0,1/e) make 1 a more effective target.
m Pr[f(D*) Lap - 2
0
[S(D")|s
T = Pr(f(D") + Lap 1//))> t/s] (If(D")l-t
2
1
->((D"") / - - - - (1-1500)e(11-00
7 = P Lap (0,1/e)] = 2
Note that Th ~e z and H ~3 म. L5 2 म and H 2 TO "
We set
ef - 1 +2 mB)) + ( ef (TH TH))
-= (
and the distribution C to be L with probability (+ ( TL))/p and H otherwise.
We specify p and the distributions Bh and C as we did for NotPrior (Lemma 2.3) with respect to "prior" L. (We can do that and cover also the case where f(Do) > t/E where the symmetric prior would be H because the target does not depend on the values being below or above the threshold).
The only difference is that our target is smaller, and includes only T rather than and H. Because of that, the calculated y value is reduced by factor of
Je -e-1/(D Ne (1-E
= = =1---))
2 Ge-1s(1))
H Numerical Comparison of Betweenfhreesoldds
We demonstrate numerically the benefits of our TCT-based Between/hrrehoolds (Section 2.6) compared with the SVT-based prior work of [3].
Consider a sensitive dataset D {xI...., Φn of size and thresholds t; < ty. We process sequence of queries where each is specified by a function f X [0, 1]. We aim to process each query by performing noisy comparison of - to f and f, with the goal of having a error of at most a on our responses to queries with confidence least 3 =
1/n. That is, for below responses it holds that 1 > f(z;) I t + a, for above responses it holds that +Σ=,
x fx,,) 2 a, and for between responses it holds that
Σ fx;) S + a. We then consider how many (that is, between) responses we can incur under the requirement that the whole sequence is (c, dDDP with < and ō = 1/n.
log(n) with the thresholds lt, fr and report below, between (T), or above accordingly. To achieve the desired accuracy and confidence of a and B = 1 - 1/n, we set the Laplace noise parameter to log(n) This ensures that with confidence at least (1 ), the noisy count is within relative error a of the true count. The sensitivity is 1/n and each call is DD with g log n
TCT: For query f. we compare the noisy count n Ei-, f(;;) Lap( a
Itee We can then compute the overall privacy cost for number of target hits using basic or advanced composition according to Theorem B. using the appropriate q values and 6. We solve for the number of target hits that keeps the overall privacy parameter values below (1, 1/m).
For t, - t4 2 2. each call has a q-target with q == 1-e
SVT-based [3]: Through the analysis in [3], we obtain that we need 5 > 16-log(n) An "optimistic"
analysis that we performed implied that we can not get better than e' >
4-login)
Figure shows the dependence of the number of between responses (y axis) on the number of data points n (ar axis) for TCT and for the provided and optimistic bounds for [3]. TCT has factor of 95 gain with respect the provided bound and factor of 6 gain over the optimistic bound.
26

---

Comparison for BetweenThresholdd
BSU Ootimeeicc
10a
1.2
100000 202030
300000
400000
500020
600010
Number of Data Pilntt
Figure I: Number of BetweenThreehollds target hits for data set size. 6= B= = 1/n, a 0.01
Finally, the gains reported in the figure assume that both algorithms use the same gap that is large enough to satisfy the requirement of [3] that |t, 41 >= / But in situations where we are interested narrow gap around single threshold, TCT with the smaller effective gap also benefits from much fewer target hits.
I Analysis of SVT with individual privacy charging
Our improved SVT with individual charging described in Algorithm 5 (see Section 2.8).
We establish the privacy guarantee:
Proof of Theorem 2.9. We apply simulation- based privacy analysis (see Section A.S). Consider two neighboring datasets D and D' Du(). The only queries where potentially f(D) # f(D) and may need to call the data holder are those with f(x) * O. Note that for every x' E D, the counter Cz' is the same during the execution of Algorithm 5 on either D or D'. This is because the update of C depends only the published results and f((x'), both of which public information. Hence, we can think of the processing of Cz'' as post-processing when we analyze the privacy property between D and D'
After 2 is removed, the response on D and D' the same, and the data holder does not need to be called. Before is removed from D', need to consider the queries such that f(x) * 0 while C2 < T. Note that this equivalent to a sequence AboveThresholk tests to linear queries, we apply TCT analysis with Condi tiomalRelease applied with above threshold responses. The claim follows from Theorem B.4.
We also add that Algorithm 5 can be implemented with BetweenThreshold, test (see Section 2.6), the extension straightforward with the respective privacy bounds following from Lemma G.I (g value for target hit).
J Private Selection
In this section we provide proofs and additional details for private selection in TCT (Sections 2.4 and 2)..1). Let AI...., Am be of private algorithms that return results with quality scores. The private selection task asks us to select the best algorithm from the m candidates. The one-shot selection described in Algorithm (with & 1) runs each algorithm once and returns the response with highest quality.
It is shown in [21] that if each A; is (s, D) then the one-shot selection algorithm degrades the privacy bound (me, 0)-DP However, we relax the requirement to approximate DP, we can show that one-shot selection is (O(log(1 (1)))), 8)-DP, which is independent of m (the number of candidates). Moreover, in light of lower-bound example by [21], Theorem J.I tight up to constant factors.
27

---

Formally, our theorem can be stated as
Theorem J.1. Suppose E < 1. Let AI..... Am x" - y x be a list of (e, 6.). al- gorithms, where the output of A, consists of solution y Be..,A, the following algorithm (Algorithm 3 with l = 1): run each AI...., once, get results (y1, 81) 81)g-..; (ym: 8m), and ouipud (y++,8 where 8" arg max; 8;-
and score E R. Denote by
Then, for every (0,1). Best(AI,..... Am. satisfies (c', 8D) where e' O log(1 (1))))), 6 L, 84.
Proof. Discrete scores. We start by considering the case that the output scores from AI..... Am always lie in a finite set X _ R. The case with continuous scores can be analyzed by discretization argument.
Fix DO, D to be pair of adjacent data sets. We consider the following implementation of the vanilla private selection.
Algorithm 9: Private Selection: A Simulation
Input: Private data set D. The set X defined above.
for i = 1,..., m do
(Wi, 84) < AD)
for & X in the decreasing order do
for i 1..... m do
if á then return (y:, 8;)
Assuming the score of AD(D) always lies in the set X, is easy to see that Algorithm 9 simulates the top-1 one-shot selection algorithm (Algorithm with k 1) perfectly. Namely, Algorithm first runs each A, (D) once and collects m results. Then, the algorithm searches for the lowest & E X such that there pair (yt, 8,) with score of at least s; 2 S. The algorithm then publishes this score.
On the other hand, note that Algorithm 9 can be implemented by the conditional release with revisions framework (Algorithm 2). Namely, Algorithm 9 first runs each private algorithm once and stores all the outcomes. Then the algorithm gradually extends the target set (namely, when the algorithm is searching for the threshold s, the target set is {8),)) outcome in the target. Therefore, follows from Lemma 2.5 and Theorem B.4 that Algorithm is (o) Σ, DDP
2 8}), and tries to find an
Continuous scores. We then consider the case that the distributions of the scores of Ai (D).... Ax(D) are continuous over TR. We additionally assume that the distribution has no "point mass". This is to say, for every E [m] and E R. it holds that
Pr [ - A < S S $] A (..)s))AA.)))
This assumption is without loss of generality because we always add tiny perturbation the original output score of (D).
Fix D, D' two neighboring data sets. We show that the vanilla selection algorithm preserves differential privacy between D and D'.
Let > 0 be an arbitrarily small real number. Set M 10 For each E [1, let E R be the unique real such that
f
Pr [s qel M+1 (...m)).....) (.(
Similarly we define of with respect A, (D)). Let X (gr, d/)-
Now, consider running Algorithm 9 with the set X and candidate algorithms AI,..., Ar on or
D'. Sort elements of X in the increasing order, which denote as X {â) S ). After
28

---

sampling (.( for each i E [m=] Algorithm 9 fails to return the best outcome only if one of the following events happens.
The best outcome (v" satisfies that s* < q1-
There are two outcomes (yi, 8t) and (y) 85) such that 8,, 8j E [āe, (6+1) for some & [r]]
If Item happens, Algorithm 9 does not output anything. If Item 2 happens, then it might be possible that j, 8; 8j, but Algorithm outputs 8,.
is easy to see that Event happens with probability at most m M S v by the construction of X. Event 2 happens with probability most M m= v). Therefore, the output distribution of Algorithm 9 differs from the true best outcome by at most O(1) in the statistical distance. Taking the limit 1) completes the proof.
Remark J.2. Theorem J.I shows that there is a factor of of /6) overhead when we run top-1 one- shot private selection (Algorithm 9) only once. Nevertheless, we observe that if we compose top-1 one-shot selection with other algorithms under the TCT framework (e.g., compose multiple top-1 one-shot selections, generalized private testing, or any other upplications mentioned in this paper)), then on-average only puy 4g privacy cost (one NotPrior larget hit with 2e-DP algorithm) per top-1 selection (assuming & is sufficiently small so that ef 1). In particular, adaptively performing a. executions of top-1 selection is (E',8)- 6 where e' = 1...A44/log (Avcloo(L//)) + o(vc)).
Liu and Talwar [21] established a lower bound 25 on the privacy of a more relaxed top-1 selection task. Hence, there a factor of 2 gap between this lower bound and our privacy analysis. Note that for the simpler task of one-shot above threshold score (discussed in Section 1, where the goal to return a response that is above the threshold if there is one, can be implemented using a single target hit on Conditional Release call (without revise) and this matches the lower bound of 22. We therefore suspect that might be possible tighten the privacy analysis of top-1 one-shot selection. We leave it as interesting question for followup work.
J.1 One-Shot Top-k Selection
In this section, we prove our results for top-k selection.
We consider the natural one-sho shot algorithm for top-k selection described in Algorithm 3, which (as mentioned in the introduction) generalizes the results presented in [9, 29], which were tailored for selecting from 1-L.iscchizz functions, using the Exponential Mechanism or the Report-Noise-Max paradigm.
We prove the following privacy theorem for Algorithm 3. Theorem J.3. Suppose < 1. Assume that each Ar is (s,0)-DP. Then, for every E (0, Algorithm: 3 is (e (e.(( O((/log(())) log(t) Remark J.4. The constant hidden in the big-Oh depends on For the setting that is close to zero so that e" se and ê 2 20(k), the privacy bound is roughly (E' (E',8)-DP where e' E (4 k +(VT)).
+ l)g({))) 8)DP.
Remark J.S. We can take A; the Laplace mechanism applied to a 1-Lipschisz quality function fü (namely, A:(D) outputs a pair (i. f((D) + Lap(1/))) where i denotes the ID of the i-th candidate, and (D) + Lap(1/e) is the noisy quality score of Candidate with respect the data D). In this way, Theoerem J.3 recovers the main result of [29].
Moreover, Theorem J.3 improves over [29] from three aspects: Firstly, Theorem J.3 allows to report the noisy quality scores of selected candidates for free, while [29] needs to run one addi- tional round of Laplace mechanism to publish the quality scores. Second, our privacy bound has no dependence on while the bound in the prior work [29] was (O / (og(m//)) 8D-DP. Lastly, Theorem J.3 applies more generally to any preseri-g algorithms, instead of the classic Laplace mechanism.
Proof. The proof similar to that of Theorem J.1. Namely, we run each (D) once and store all results. Then maintain threshold T, which starts with T = We gradually decrease T,
29

---

and use Algorithm 2 (Conditional Release with Revised Calls) to find outcomes with quality score larger than T. We keep this process until we identify & largest outcomes. The claimed privacy bound now follows from Lemma 2.5 and Theorem B.4.
30


Reviews:
[{"review_id": "tycTCV4S2l", "reviewer": "Reviewer_ot2S", "summary": "The submission studies a privacy analysis framework for interactive computations. The main contribution is extending the conventional differential privacy analysis framework, namely the sparse vector technique, which counts the privacy cost only for the positive response. Particularly, the proposed framework, namely the target charging technique, generalizes from the specific constraints (e.g., threshold) of positive response to general expressions that are not necessarily threshold. The overall analyses are regarding the $(\\epsilon,\\delta)$-DP. ", "questions": "1) As written in the weaknesses part, I cannot see how the q value is attained from the target setting in practice. Could you provide a (toy) example for the q-target? \n\n2) What happens if the $\\epsilon$ is not too small (e.g. $\\epsilon=10$ in Lemma 2.3)? It seems the resulting $\\epsilon$ would be very large, which is not acceptable in general. Is there any way to compensate for it?\n\n", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-organized. I think the problem of privacy analysis for interactive computing is an essential topic and the extension/generalization made in this work is significant. \nI think that the privacy analysis shown in Lemma 2.2 for a general system is important in DP literature. \nThe list of application scenarios of the proposed framework is well-categorized and shows the applicability of the proposed technique in practice.", "weaknesses": "I think the results and definitions are hard to read. In particular, it is hard to see how one can distinguish the q value of a q-target. It is also not straightforward to understand the notPrior target.\nI know this paper is a theory paper, but it would be good to show some experimental results of the application of the main results, which makes the paper more sound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nAnswers:\nAs for experimental results, see our general response!\n\nQuestion 1:  $q$-targets:  We list examples of useful q-targets.  For private testing, the $q$-target can be (selected one of) true/false responses.  For Top-$k$ selection, the $q$-targets are mapped to being in the top-$k$.  For “between thresholds” tests,  the $q$-target is simply a between outcome.  The only place where the $q$- target is “manufactured” is in our “boundary wrapper” method.  \n$q$-values are derived for each of the cases.  Nearly all of our use cases directly map to the “not prior” q-value that (for small $\\varepsilon$) is close to $1/2$.  The “between thresholds” application includes an exact calculation of $q$ as a function of the  “gap” between the thresholds.\n  \nQuestion 2:  Note that the value of $\\varepsilon$ in the context of Lemma 2.3 is that of a single call to a DP algorithm on our dataset.  This value is typically very small $\\varepsilon \\ll 1$ and therefore $q\\approx ½$.   In the TCT setting, we assume that there are multiple applications of private algorithms to our dataset, and tens (or hundreds) of them are “target hits.”  The overall privacy cost is a composition over target hits.  We can set out overall privacy budget to have $\\varepsilon=1$ or if one wishes $\\varepsilon=10$.  But regardless, the privacy parameter values of each call are small. \n"}, {"review_id": "Y1o4oBsh0J", "reviewer": "Reviewer_xrUp", "summary": "This paper presents a new privacy analysis framework called Target Charging Technique (TCT). Designed for interactive scenarios where sensitive datasets are frequently accessed using differentially private algorithms, TCT offers a unique perspective. Unlike traditional composition schemes where privacy assurances degrade with multiple data accesses, TCT provides an alternative approach. It allows computations that avoid hitting a specified target to occur without significant cost but imposes a minor overhead on computations that do meet their targets. Furthermore, TCT generalizes tools such as the sparse vector technique and top-k selection from private candidates and extends their remarkable privacy enhancement benefits from noisy Lipschitz functions to general private algorithms.\n", "questions": "It seems that this work is very promising in theory. Have you tested it on some real-world scenarios? Will it become open-source?", "limitations": "See weakness.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well written. The details of movtivation, methodology, proofs are described clearly.\n2. The insight of this paper is quite reasonable and the proposed approach looks novel.", "weaknesses": "1. The related work section is missing.\n2. The effectiveness of this approach is not clear to me. What are the main improvements offered by this method? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nResponse to Question: Please see our general response regarding numerical comparisons and a demonstration of the practicality of TCT and improvement over prior work.  As for open-source: TCT privacy analysis is simple to add and we hope it will be  incorporated in DP libraries.\n\nResponse to “Weaknesses”:\n\n1. Our work is related to vast literature on SVT and selection and we included many citations and discussions of related work throughout the introduction. The prior work on SVT that can be viewed as a predecessor of Target Charging is the paper by Hardt and Rothblum (FOCS 2010) [18].  All that said, we are very happy to include a related work section if this is the preferred format.\n\n2. Please see our general response where we numerically demonstrate the improvements over prior work.\n"}, {"review_id": "w8I2sMFmyN", "reviewer": "Reviewer_MAFe", "summary": "This paper proposes Target Charging Techniques: a method that generalizes sparse vector technique and top-k selection from private candidates. Specifically their goal is to obtain better privacy guarantees in the settings where only a small number of computations are *successful*. One of their main ideas is to consider a prior on the output that has high probability (some sort of a default output), and only pay in privacy if the output of the algorithm is not equal to that prior.\n\nThey suggest a definition \"$q$-target\" for a subset of events $T$ and a private algorithm $M$. Roughly speaking, this definition helps us measure the actual privacy exposure when the algorithm $M$ hits an event in T. For every $1/q$ private accesses we're going to have $1$ hit (we'll have $ M(D)$ in $T$).\n\nSuppose we have a dataset $D$, a set of $\\epsilon$-DP algorithms $A_i$'s and events $T_i$, and a threshold $\\tau$. They show an algorithm that outputs $A_i(D)$'s until $\\tau$ many of $A_i(D)$'s are in $T_i$ and then stops is $(\\tau / q \\epsilon, \\exp(O(\\tau))$ private.\n\nIn the rest of the paper they apply their technique to multiple use cases.\n\nSome examples of the use cases of this technique include: private learning when we want to release only if the answer has high quality, greedy coverage, and above threshold tests.", "questions": "suggestion: add some text around definition 2.1 to explain what's going on in the definition and to help interpret lemma 2.2\n\nLemma 2.2 talks about $A_i$'s and $\\tau_i$'s, but algorithm 1 only has $A$ and $\\tau$.\n\nIn line 374: can you give a more complete explanation of what their result is and what are the guarantees that you obtain?", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper provides a simple framework for accounting for privacy that is applicable to a number of problems in dp such as top-k selection and sparse vector technique with individual privacy charging. These problems mostly had tailor-made algorithms and analysis prior this work. The framework in this paper recovers some of the previously known bounds on these problems and improves on some of them, often through a simpler analysis.", "weaknesses": "I expected the authors to include at least one setting where this framework significantly improves upon prior work on a specific application. This paper provides a pipeline that is simple, nice, and will probably be useful. Still, I am not convinced that the applications of this framework provide a significant improvement in terms of results compared to prior work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nResponse to “weaknesses”:  Please see our general response regarding numerical comparisons and a demonstration of the practicality of TCT and concrete improvements over prior work.\n\nResponse to Questions:  \n\n  -- Definition 2.1 formalizes the notion of a “target” that was discussed in the introduction.  We will add a backward reference to the informal use in the intro.\n\n -- We modified the statements of Lemma 2.2  to remove the explicit index notation. It is the case that new algorithm-target pairs $(A_i,\\tau_i)$ are input in each iteration but we made the notation consistent. \n\n-- Line 374: please see additional details we provide on “SVT with individual privacy charging” in the general response.  The idea in [KMS] [20]  is to do a more fine-grained privacy analysis of threshold tests on counting queries that keeps a budget for each item (that is charged only when the item “participates”) instead of one overall budget.  This allows us to answer more queries with the same privacy budget.  Compared to the algorithm (and analysis) of [20], our Algorithm 5 with TCT analysis is simpler (adds noise once), more informative within the privacy budget as it can also release actual estimates with above-threshold responses, and is vastly more accurate:  can add much smaller noise for the same privacy budget (see general response).\n"}, {"review_id": "frbr6HL88d", "reviewer": "Reviewer_5m6N", "summary": "Introduced Target-Charging Technique (TCT) for privacy analysis over interactive private computations", "questions": "1. Thank you author because the best presentation as far as I have seen. Even after this, I will also use comment feature for algorithm or coding snippet of my paper.", "limitations": "1. I am missing experimental result.", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1.  Introduced Target-Charging Technique (TCT) for privacy analysis over interactive private computations", "weaknesses": "1. They could add experiment part", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nResponse to “weaknesses”:  Please see our general response with numerical comparisons and a demonstration of the practicality of TCT and concrete improvements over prior work.\n"}, {"review_id": "faYXHfdFxO", "reviewer": "Reviewer_o37L", "summary": "This paper introduces the Target Charging Technique (TCT) privacy analysis framework that focuses on providing better privacy utility trade-off on sensitive dataset with multiple differential private algorithm  access. The essential idea is to only pay budget cost to the positive target and negative targets become free. TCT framework can improve several classical DP algorithms such as private Top-K, conditional release, private learning with non-private models etc.", "questions": "See weakness.", "limitations": "No", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper studies a very important problem and proposes a very generalized framework that works for several classical algorithms and with many applications. The framework provide tighter privacy-utility trade off by considering the amortized overheads over user desired target. When the number of hits is large, the $log(1/\\delta)$ privacy charge amortized to O(1) per target hit.\n\nThe intuition behind this paper is well presented in which if the computations do not touch user targets then the overhead should be small.\n\n", "weaknesses": "The assumption in q-Target definition seems to be stringent. How to ensure the randomized algorithm M satisfy such condition? \n\nWhile it is a formal paper, it would still benefits with some empirical evidence. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nResponse to “weaknesses”:  \n\n1. [q-target] We agree that the definition is formal. We do not ensure that this holds (there is always a target with $q=1$ but this is not very interesting) but instead show how to use its existence in privacy analysis.  We then demonstrate that there are natural q-targets, in particular “not prior” (all outcomes but a selected one in any private algorithm).  Not-prior is our workhorse in multiple applications but we also demonstrate there is a value in this generality (rather than limiting ourselves to “not prior” targets).  For example, in the “BetweenThreshold” application we demonstrate the  $q$-value of the “between” outcome (the target) depends on the width.\n\n2. [empirical evidence] Please see our general response with numerical comparisons and a demonstration of the practicality of TCT and concrete improvements over prior work.  We plan to incorporate it in the paper.\n"}, {"review_id": "RJQP9DY5tr", "reviewer": "Reviewer_fHHh", "summary": "Drawing inspiration from the Sparse Vector Technique (SVT), the authors introduce a privacy analysis framework called Target Charging Technique (TCT). TCT operates by primarily accounting for the privacy loss incurred through queries that hit pre-specified target sets. This framework relies on the concept of q-targets, which model a structural property of the distribution of privacy mechanism outputs. The authors show that q-targets appear in a variety of use cases, leading to natural applications of TCT. Of particular interest is the application of TCT in the privacy analysis of one-shot k-top selection and conditional releases. Also, the authors theoretically demonstrate that the parameter degradation of TCT improves over known techniques.", "questions": "As highlighted in the Weaknesses Section, the primary limitation of the present paper lies in the absence of numerical experiments that demonstrate the benefits of the proposed framework. It would be advantageous for the reader if the authors could include some illustrative simulations, even if they are relatively simple in nature. This addition would provide valuable insights into the practical advantages of the proposed framework.", "limitations": "The authors' treatment of the limitations of the proposed method could be improved. Specifically, there is a lack of empirical experimentation to showcase the benefits of TCT.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The problem is rather natural, as well as the proposed algorithm\n\n2. The framework is flexible enough to accommodate interesting applications, e.g., one-shot k-top selection and conditional releases. Furthermore, it can be generalized to multiple targets.\n\n3. The technical part of the paper seems to be solid.", "weaknesses": "The reviewer acknowledges that the primary focus of the present paper is to establish the foundations of TCT and prove some of its theoretical properties. However, the absence of numerical experiments poses a significant weakness. Considering the authors' expressed intention for TCT to be adopted in practice, it is important to supplement the theoretical analysis with concrete evidence through the inclusion of some simulations. Such simulations would provide valuable insights into the practical implications and potential benefits of employing TCT in real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nResponse to “weaknesses”:  Please see our general response with numerical comparisons and a demonstration of the practicality of TCT and concrete improvements over prior work.  We hope this will at least partially address the concern!  We plan to incorporate this in the paper.\n"}]

Author rebuttal:
We are grateful to the reviewers for their comments.  All reviewers expressed a desire to see some numerical comparisons of the gains of TCT with respect to prior work. In this comment, we place our results in this context and plan to revise our presentation accordingly.  Responses to additional comments are provided individually.

– “BetweenThresholds” queries (see Section 2.6):  

For dataset $D = \{x_1,\dots, x_n\}$ and threshold $0\leq t_l<t_r\leq 1$, we process a sequence of queries specified by functions $f$ from the domain to $[0,1]$.  The aim is to compare $\frac{1}{n} \sum_{i=1}^{n} f(x_i)$ to the thresholds and return "below","between", and "above".  We include a plot that demonstrates significant improvement over prior work. The plot reports the number of "target hit" queries ($y$-axis) that we can perform with an overall privacy budget of $\varepsilon=1$ subject to accuracy requirement of relative error $0.01$ with confidence $1-1/n$.  This as a function of the dataset size $n$ ($x$-axis). "Target hits" are “between” responses. Note a factor of 95 improvement of TCT over the method of Bun-Steinke-Ullman [3]. We also performed an “optimistic” analysis of the constants in BSU [3], that can be interpreted as an “upper bound” on what is achievable with their approach. TCT gained a factor of 6 improvement even compared with that optimistic bound.

TCT offers additional advantages over [3]:  Our algorithm is simpler and natural (add Laplace noise and compare with thresholds).  Importantly, it allows for asymptotically narrower gaps between the thresholds compared with [3]:  [3] requires a gap of  
$|t_r -t_l | >= \frac{12(\log(1/\varepsilon) + \log(1/\delta))}{\varepsilon}$, whereas TCT allows for gaps as small as $2/\varepsilon$ with almost no decrease in the $q$-value. This is particularly significant in applications where we are interested in a single threshold and incurring privacy loss only on queries that are close to that threshold.  The narrower gap means much fewer target hits.

– SVT with  Individual Privacy Charging (Section 2.8 for details):  

We compare TCT with the prior work of Kaplan Mansour Stemmer [20]. We can achieve the same privacy guarantees with much lower levels of  noise:  [20] uses standard deviation $O( \sqrt{log(1/\delta)} \log(1/\varepsilon) /\varepsilon)$ whereas TCT uses $O(1/\varepsilon)$.  We can not do an empirical comparison because [20] only provided asymptotic analysis with “constants” that appear much larger (we have the same constants as without individual charging).  We can do a forgiving (to [20]) comparison by ignoring constants: If we take $\varepsilon=0.01$ and $\delta  = 10^{-8}$ the noise magnitude  with TCT is smaller by a factor of 20. 

Additionally, our algorithm is simpler and the privacy analysis is few lines compared with several pages.  Moreover, TCT analysis allows for releasing estimated counts with no additional privacy charge.   



– General gains of TCT

The two examples (BetweenThresholds and Individual charging) are in the “noisy Lipschitz” setting where there is prior work to compare with. Zooming out a bit, TCT is a broad and flexible framework.  Its primary advantage is that it allows for incurring privacy loss only on “target hits” in natural settings that are outside “noisy Lipschitz” regime.  These include one-shot top-k selections and private tests  with general private algorithms (aka not necessarily noisy Lipschitz).  The relevant prior work here is either changing the algorithm or applying DP composition over $n$.  TCT gains are significant as $k$ can be much much smaller than $n$ (the total number of tests or the total number we select from).  Moreover, our analysis does not hide large constants.  Lemma 2.2 states simplified privacy bounds for TCT with some asymptotic notation, but In the supplementary we included exact expressions in the statement of Theorem B.4. We include numerical examples in Remark B.5: TCT analysis generally gains when $n/k > 2.5$ when there are hundreds of target hits. The needed ratio is larger with fewer target hits. For 10 target hits we need $n/k > 12$ to gain over composition.  These regimes are in the practical realm.  In applications such as PATE (see section 2.7.1) one aims to incur privacy loss on a small fraction of examples.

Meta-review: The reviewers were all unanimously supportive of this paper and its contributions. The reviewers felt that the authors addressed any remaining concerns in the discussion period.
Decision: Accept (poster)