Individual Privacy Accounting via a Rényi Filter
Authors: Vitaly Feldman
Tijana Zrnic
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
Rényi differential privacy
adaptive composition
privacy filter

Abstract: We consider a sequential setting in which a single dataset of individuals is used to perform adaptively-chosen analyses, while ensuring that the differential privacy loss of each participant does not exceed a pre-specified privacy budget. The standard approach to this problem relies on bounding a worst-case estimate of the privacy loss over all individuals and all possible values of their data, for every single analysis. Yet, in many scenarios this approach is overly conservative, especially for "typical" data points which incur little privacy loss by participation in most of the analyses. In this work, we give a method for tighter privacy loss accounting based on the value of a personalized privacy loss estimate for each individual in each analysis. To implement the accounting method we design a filter for Rényi differential privacy. A filter is a tool that ensures that the privacy parameter of a composed sequence of algorithms with adaptively-chosen privacy parameters does not exceed a pre-specified budget. Our filter is simpler and tighter than the known filter for $(\epsilon,\delta)$-differential privacy by Rogers et al. (2016). We apply our results to the analysis of noisy gradient descent and show that personalized accounting can be practical, easy to implement, and can only make the privacy-utility tradeoff tighter.

Individual Privacy Accounting via a Rényi Filter
Vitaly Feldman Apple com com
Tijana Zrnie University of California, Berkeley jijana. meraazznicilli ceberkeekk edu
Abstract
We consider sequential setting in which single dataset of individuals is used perform adaptivelycchosen analyses, while ensuring that the differential privacy loss of each participant does not exceed pre-specified privacy budget. The standard approach to this problem relies on bounding a worst-case estimate of the privacy loss over all individuals and all possible values of their data, for every single analysis. Yet. in many scenarios this approach is overly conservative, especially for "typical" data points which incur little privacy loss by participation in most of the analyses. In this work, we give method for tighter privacy loss accounting based on the value of personalized privacy loss estimate for each individual each analysis. To implement the accounting method we design filter for Rényi differential privacy. A filter is a tool that ensures that the privacy parameter of a composed sequence of algorithms with adaptively-chusee privacy parameters does not exceed a pre-specified budget. Our filter simpler and tighter than known filter for (e, 3)-differential privacy by Rogers et al. [29). We apply our results to the analysis of noisy gradient descent and show that personalized accounting can be practical, easy to implement, and can only make the privacy-utility tradeoff tighter.
1 Introduction
Understanding how privacy of an individual degrades as the number of analyses using their data grows is of paramount importance in preecy-preeeriingg data analysis. This allows individuals to participate in multiple disjoint statistical analyses, all the while knowing that their privacy cannot be compromised by aggregating the resulting reports. Furthermore, this feature is crucial for privacy- preserving algorithm -nnhign--ntteadd of having to reason about the privacy properties of a complex algorithm, it allows reasoning about the privacy of the subroutines that make up the final algorithm.
For differential privacy (DP) [. this accounting of privacy losses is typically done using composition theorems. Importantly, given that statistical analyses often rely on the outputs of previous analyses. and that algorithmic subroutines feed into one another, the composition theorems need to be adaptive, namely, allow the choice of which algorithm to run next to depend on the outputs of all previous computations. For example, in gradient descent, the computation of the gradient depends on the value of the current iterate, which itself is the output of the previous steps of the algorithm.
Given the central role of adaptive composition theorems in differential privacy, they have been investigated in numerous works (e.g. [16] 23 In (2 26 4 29 g 30). While they differ in some aspects, they also share one limitation. Namely,
of these theorems reason about the worst-case privacy loss for each constituent algorithm in the composition. Here, "worst-case" refers to the worst choice of individual in the dataset and worst choice of value for their data, This pessimistic accounting implies that every algorithm is summarized via single privacy parameter, shared among all participants the analysis.
In most scenarios, however, different individuals have different effects on each of the algorithms, as measured by differential privacy. More precisely, the output of an analysis may have little to no
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

dependence on the presence of some individuals. For example, if we wish to report the average income in neighborhood. removing an individual whose income is close the average has virtually no impact on the final report after noise addition. Similarly, when training a machine learning model via gradient descent, the norm of the gradient given by data point is often much smaller than the maximum norm (typically determined by a clipping operation). As result, in many cases no single individual is likely to have the worst-case effect on all the steps of the analysis. This means that accounting based on existing composition theorems may be unnecessarily conservative.
In this work, we present a tighter analysis of privacy loss composition by computing the associated divergences at an individual level. In particular, to achieve a pre-sipeifiee privacy budget, we keep track of a personalized estimate of the privacy loss divergence for each individual in the analyzed dataset, and ensure that the respective estimate is maintained under the budget for all individuals throughout the composition. We do so by applying each analysis only to the points that are estimated to have sufficient leftover privacy budget.
1.1 Overview of main results
is feasible to measure the worst-case effect of a fixed data point on given analysis in terms of DP. One can simply replace the supremum over all datasets in the standard definition of (removal) DP with the supremum over datasets that include that specific data point (see Definition 2.5 However, a meaningful application of adaptive composition with such definition immediately runs into a technical challenge: standard composition theorems require that the privacy parameter of each step be fixed in advance For individual privacy, this approach requires using the worst-case value of the individual privacy loss over all the possible analyses at a given step. Individual privacy parameters are much more sensitive to the choice of analysis than worst-case parameters, and thus maximizing over all analyses is likely to negate the benefits of using individual losses in the first place.
Thus the main technical challenge in analyzing composition of individual privacy losses is that they are themselves random variables that depend on the outputs of all previous computations. If denote by .i,..., Or the output of the first / adaptively composed algorithms A,,..., Ar, then the individual privacy loss of any point incurred by applying algorithm A.41 is a function of a1.... at. Hence, to tackle the problem of composing individual privacy losses we need to understand composition with adaptively-chose privacy parameters. We refer to this kind of composition as fully adaptive.
The setting of fully adaptive privacy composition is rather subtle and even defining privacy in terms of the adaptively-chosen privacy parameters requires some care. This setting was first studied by Rogers et al. [29]. who introduced the notion of a privacy filter. Informally, a privacy filter is stopping time rule that halts a computation based on the adaptive sequence of privacy parameters and ensures that a pre-specified privacy budget is not exceeded. Rogers et al. define a filter for approximate DP that asymptotically behaves like the advanced composition theorem [6), but is substantially more involved and loses a constant factor. Moreover, several of the tighter analyses of Gaussian noise addition require composition to be done in Rényi differential privacy (RDP) [ 26).
Our main result can be seen as a privacy filter for RDP which justifies stopping the analyses based on the sum of privacy parameters far even under fully adaptive composition.
Theorem 1.1. Fix B 2 0, a 2 1. Assume A, (a, PtD- where Pt is any functionn of di..... -1-1- E' P: S B holds almost surely, then the adaptive composition of AI..... Ase is (a, BDD.
When PI...., Ps: are fixed, Theorem 1.1 recovers the usual composition result for RDP 26 Our RDP filter immediately implies a simple filter for approximate DP that is as tight as any version of the advanced composition theorem obtained via concentrated DP 4.. These <ényiidivergence-baaa analyses are known to improve on the classical rate (16) and, in particular, improve on the rate in 22)..
We instantiate our general result for fully adaptive composition in the setting of individual privacy accounting. This allows us to define an individual privacy filter, which, given fixed privacy budget, adaptively drops points from the analysis once their personalized privacy loss estimate exceeds the budget. Therefore, instead of keeping track of single running privacy loss estimate for all individuals, we track a less conservative, personalized estimate for each individual in the dataset. Individual privacy filtering allows for better, adaptive utilization of data points for given budget. It can also naturally be applied to accounting in the local DP model, whereby each user stops responding once their local implementation of the filter indicates that their personal privacy budget is exhausted.

---

Individual privacy parameters are particularly easy to compute for linear queries, as well as their high- nigh-dimensional generalizations. We show that our technique gives an algorithm for answering a sequence of adaptively-chosen linear queries that are sparse across time, meaning that, for any user, the number of queries that are non-zero on that user's data is small. Such queries arise, for example, when a platform counts the number of users that participate in certain activities (the type of activity being adaptive to the data collected in the previous days) and users generally participate in a small number of activities. Formally, a special case of our result implies the following theorem.
Theorem 1.2. There exists an algorithm A that, given a dataset S = (Xi,..., ..,) E Xx" sspar- sity parameter s and privacy level K, for any adaptively-chosen sequence of queries 91....:99 9g of arbitrary length k, where qi: XX + {0, 10, provides a sequence of answers d1,..., ag such that: (1) A is (ar, RKK) for all a 2 1; (2) for all t and any 8 E (0,1), 1), the probability that |at- - Ex,es, ((X))) > v s (1g(1/))/ k is at most 6, where S. = (X; E E Ej= (x.) S $8).
We note that the provided answers are guaranteed to be accurate only as long as the queries are truly sparse, meaning Σ Oj (X:) < s for (almost) all i E [r|]- This follows because the queries are accurate on the set St, hence St needs to be similar to S for the queries to be accurate on S. The privacy guarantee, on the other hand, holds for any sequence of queries of any length k. We describe a more general version of this result in Section 4.2 A natural application of our general theorem is the setting of high-dimensional linear queries generated by gradient descent. We apply our theory to the analysis of private gradient descent (.. and boow-both theoretically and empirically-thai individual accounting can be easy to implement and can only make the resulting privacy-utility tradeoff tighter. Independently, without any individual accounting, in our empirical evaluations we also observe that private batch gradient descent, when tuned appropriately, outperforms private stochastic gradient descent in terms of the privacy-utility tradeoff. While we make this observation only on MNIST, we believe this phenomenon holds more generally and is worth further investigation.
1.2 Related work
The main motivation behind our work is obtaining tighter privacy accounting methods through, broadly speaking, "personalized" accounting of privacy losses. Existing literature in DP discusses several related notions (22 [19 (1,, although typically with an incomparable objective. Ghosh and Roth [22] discuss individual privacy in the context of selling privacy at auction and their defimition does not depend the value of the data point but only on its index in the dataset. Cummings and Durfee 66 rely on a similar privacy definition, investigate an associated definition of individual sensitivity, and demonstrate a general way to preprocess an arbitrary function of a dataset into function that has the desired bounds on individual sensitivities.
Ebadi et al. [99 introduce personalized DP in the context of private database queries and describe a system which drops points when their personalized privacy loss exceeds budget. While this type of accounting is similar to ours in spirit, their work only considers basic and non-adaptive composition. Wang (11 considers the privacy loss of a specific data point relative to a fixed dataset and provides techniques for evaluating this "per-instance briefly discusses adaptive composition of per-instance DP as a straightforward generalization of the usual advanced composition theorem [16]. but the per-instance privacy parameters are assumed to be fixed. As discussed above, having fixed per- per-instance privacy parameters, while allowing adaptive composition, is likely to negate the benefits of personalized privacy estimates. The work of Ligett et al. 255 tightens individuals' personalized privacy loss by taking into account subsets of analyses in which an individual does not participate. Our work naturally captures this setting while allowing full adaptivity. Moreover, they consider the usual worst-case privacy loss, rather than an individual one, and the analyses in which user participates are determined in a data-independent way.
privacy loss for several statistical problems. Wang also
Our work can be seen as related to data-dependen approaches to analyses of algorithms such as smooth sensitivity 28 the propss-test-releass framework [9] and ex-post privacy guarantees (32] Our results are complementary in that we aim to capture the dependence of the output on the value of each individual's 's data point as opposed to the "casiness" of the entire dataset. Our approach also relies on composition to exploit the gains from individual privacy accounting.
Finally, adaptive composition of DP is key tool for establishing statistical validity of an adaptively-
chosen sequence of analyses [8]
17 3 In this context, Feldman and Steinke (2T] show that
individual KL-divergence losses (or RDP losses for a 1) compose adaptively and can be used to
3

---

derive tighter generalization results. However, this result still requires that the average of individual Ki-divergences be upper bounded by fixed worst-case value and the analysis is limited to a
Preliminaries
We let = -X denote the analyzed dataset, and 5 def (X,,..,, -........ X.) the analyzed dataset after removing point X,, We will generally focus on algorithms that can take as input a dataset of arbitrary size. If, instead, the algorithm requires an input of fixed size, one can obtain the same results for algorithms that replace X; with an arbitrary fixed element X (e.g. 0).
Definition 2.1
[33 12 D. A randomized algorithm A is (c. 6) -ifffeerrettillly private (DP) for all datasets $ = (X1. X,). i E [n], and measurable sets E,
Pr (S() E E S E Pr [A(S E E] + 8, and Pr [A(S*)) E E] S Pr((((()) E) + 8.
Our analysis will rely on Rényi differential privacy (RDP), a relaxation of DP based on Rényi divergences which often leads to tighter privacy bounds than analyzing Rényi divergence of order a E 00) between two measures μ and v such that μ & V/ is defined as:
DP directly. Formally, the
D. (a(ulp) = 1 log /
djc dv
dv.
The Rényi divergence of order a = 1 is defined by continuity, and recovers the KL-divergence. Relying common abuse of notation, we use A(-) to refer to the output distribution of randomized algorithm. Thus, Da (A((S)) denotes the divergence between the output distribution of A on input and the output distribution of AA on input S Similarly,
use A(S) denote
being sampled randomly from the output distribution of A on S. We also D (Hille) def max (D (n]]p), (v(li)) to denote the maximum of the two directions of Rényi divergence.
Definition 2.2 ((26)). randomized algorithm (a, Ré-Ré differentially private (RDP) ffr all datasets S (X,,...,, X,)) and E [n], D (A(S))IA(S ")) p.
A related notion that will make use of is zero-concentrated differential privacy (zCDP).
Definition 2.3 (4), A randomized algorithm A satisfies k-zero-concentrated differential privacy
(zCDP) if satisfies (a, RDP) for all a 2
Although guarantees will be stated in terms of RDP, the conversion to DP is immediate.
Fact 2.4 (26 ). If A is (a, PD-P then it is also (p log(11)))////
6). for any å E (0, 1).
Our main object of study adaptive composition. Here, for a given input dataset S and a sequence of algorithms (At))= one sequentially computes reports 0₂ A, (4. () S) as function of
the previous reports and the input dataset. We denote by (t) def (ai,...,..) az) the sequence of the first the composed algorithm -4-1, ) is (a,, RDD for all values a1,..., at-1, then the standard adaptive composition theorem for RDP says that (Ak) is (a. Σ RRDP (26 This implicitly assumes that /1,.... Pk are fixed and thus independent of the realized reports 01,-..,0k.
which produces (2) If (2 ( (A),........))))
I reports, and by (-) def
Individual privacy. Our individual accounting relies on measuring the maximum possible effect of an individual data point on dataset statistic in terms of Rényi divergence. This measure equivalent to an RDP version of personalized DP [99] For convenience we will refer to it as individual RDP. We note, however, that, by itself, bound on this divergence does not imply any formal privacy guarantee for an individual, since the individual RDP parameter depends on the sensitive value of the data point.
Definition 2.5 (Individual RDP). Fix n E N and data point X. We say that a randomized algorithm A satisfies (a,, -inddiivilll Rényi differential privacy for X for all datasets (Xi,..., Xm) such that < n and X; X for some i, it holds that D (A(S)]A((S))) S.
Therefore, to satisfy RDP, an algorithm needs to satisfy individual RDP for all data points X.
We give two simple examples of individual RDP computation.

---

Example 2.6 (Linear queries). Let S = XAn) E d". Suppose that A is a d-dimensional linear query with Gaussian noise addition, A(S) = EjE(n) x(x,) + & for some q: X - IRd and Ç ~ (O, TT). Then, A satisfies (ar, axlla((X))) (20" ) -iiidiiviaal RDP for X
Example 2.7 (Lipschitz analyses). Suppose that 9 (Rdd) - Rdd is Li-Lipschitz coordinate (in (g-norm). For q: X + RR let A(S) = g(g(X1),.. :.:::9((K0 (Xx.)) E. E ((, LZLx) Assume that for some X*, ((X)) is the origin. Then, if = (X...... Xi-1, (i+1, Xn), we get that A satisfies (a,, aL3 (xx ( -individuul RDP for X,,
3 Fully adaptive composition for Rényi differential privacy
Our main technical contribution is a new adaptive composition theorem for RDP, which bounds the overall privacy loss terms of the individual privacy losses of all data points. In what follows, we first state a general version of our main theorem, which bounds the privacy loss in adaptive composition in terms of bound on the sequence of possibly adaptive privacy parameters.
We let Pt denote the RDP parameter of order a of A,, conditional on the past reports. For the sake of generality and simplicity of exposition, introduce an abstract space S over pairs of datasets and let
Pt
def sup (S,S')ES
D (Ar(alt-1) (S)lA(-) (S)1A(((((-))))))
(1)
Typically Pr will be random due the randomness in (t--1), In the context of individual privacy, will set S to be the space of all dataset pairs where either dataset is obtained by deleting X, from the other. In usual RDP. S will be the space of all pairs of datasets that differ in any one element.
Theorem 3.1 states that, long as Et Pe is maintained under fixed budget, the output of adaptive composition preserves privacy.
Theorem 3.1. Fix any B 2 0, 2 1, and a set pairs of datasets S. For any sequence of algorithms AI..... As, if Ei=1 S B holds almost surely, where the sequence Pi..... Pk is defined in eq. (
then for all (S, S') E the adaptive composition (8)) satisfies D (S)IAA)))) < B.
The proof relies on showing that for any pair (S, E S, where (a S, S" a) denotes the privacy loss incurred up to time i, formally defined in the Appendix- is supermartingale. A related argument is presented in (5) (see Lemma 8), who study privacy composition when a pre-specified set of concentrated DP parameters is adaptively ordered.
S, aa),s" a))- (a-1)
We now instantiate Theorem 3.1 in the context of individual privacy. For a fixed point X, we let S(X,n) n) denote the set of all dataset pairs (S, (S) such that [S] < n and S' is obtained by deleting element X from S. More precisely, (S) E S(X, n) if S = (X1...., Xm), where m S and X, X for some i, and S' = S We use oi denote the individual privacy parameter of the I-th adaptively composed algorithm Ar with respect to X,, conditional on the past reports:
def sup (S (SSX")))(
(A ()
Since Pi is an instance of definition (T) we can state a direct corollary of Theorem 3.1 Notice that it provides data-specific criterion, while classical composition considers all hypothetical datasets.
(4)
Corollary 3.2. Fix any B 2 0, a 2 1. for any input dutaset S (X Xa), Σ P <
holds almost surely for all individuals E [n], then the adaptive composition A is (a, RDD.
In the following section we show how Corollary 3.2 can be operationalized.
4 Rényi privacy filter
Fully adaptive composition was first studied in 29 They defined the notion of a filteryfilter, a function that takes as input adaptively-chosen DP parameters e1, .,,,,,..,4t dt, as well as a global DP ,
budget cgs 6g. and outputs CONT if the overall report after rounds of adaptive composition with the corresponding privacy parameters is guaranteed to satisfy (Eg, 0gg. -DP. Otherwise, it outputs HALT.
5

---

We show that Theorem 3.1 immediately implies simple RDP analogue of privacy filter. Specifically, we show that simply adding up privacy parameters, as in the usual composition where all privacy parameters are fixed up front, is valid filter for RDP. First we define an RDP filter formally. This general definition used primarily to explain the relationship of our results to the notions and results in [29] Our individual privacy filtering application can be derived from Theorem [31 directly. As in equation (T). we let Pr denote the possibly random RDP parameter order a Ar, conditional on the past reports, defined over an implicit space S of pairs of datasets.
Algorithm 1 Adaptive composition with Rényi privacy filtering
: S X maximum number of rounds N E N, sequence of algorithms (At))==
Initialize k = 0
while k < N do
Compute Pk+1 (s.) D (A1,) ab. a S1)l 0k. S2))
if (PI...... px+1) = HALT then
BREAK
end
Compute ax+1 =
ak. S), S), set + ++1
end
Return (S) = (aI,..., ax)
Let Sox denote the set of all positive, real-valued finite sequences.
Definition 4.1 (RDP filter). Fix 2 1, 2 O. We say that Fa.B : Sec - {CONT, HALT) is valid Rényi privacy filter, or RDP filter for short, for any sequence (A&) and any pair of s B.
datasets (S1, S2), Algorithm
] with S S2) satisfies D (S)IIA)))))
Without loss of generality, we can assume the filter is monotone, namely that Ff. (PI..... ................................ .k) F CONT then Fa.B (P'..... Pk) CONT whenever & S. ps. Vi E [k]. This implies that an RDP filter can be applied with PI: defined using an arbitrary set instead of just a single pair of datasets.
Lemma 4.2. Fix 1, B 0. Ff Sop {CONT, HALT) is valid RDP filter, then for any sequence (A+) and any set S, Algorithm has sup D (5) S B.
We remark that the analyst might choose algorithm at time that exceeds the privacy budget, which will trigger the filter Fa.B 3 to halt. However, the analyst can then decide to change the computation at time retroactively and query the filter again, which then might allow continuation. This way, one can ensure a sequence of N computations with formal privacy guarantees, for any target number of rounds N. In the following subsection, we present an application of RDP filters individual privacy loss accounting which relies on this reasoning.
Theorem 4.3. Let
Fo, Pk) = CONT, if Et= Pt S B,
HALT, if Ek Pe B.
Then, Fo.n is a valid Rényi privacy filter.
Remark 4.4. For algorithms that satisfy zero-concentrated DP (zCDP), the stopping rule of Theorem 4.3 suffices for controlling zCDP privacy loss as well. Namely, if Ai(a...... 01-1. is Kt-ZCDP, then the halting criterion of the Rényi privacy filter with parameters (a, aus) is Σ 0KR S aR, which simplifies to Ek Kt S Since this stopping rule is independent of we conclude that the overall output is (ox, RDDP for all a 2 1, which is equivalent to R-ZCDP. More generally, Theorem 4.3 extends to tracking Rényi privacy loss for any set of orders {a;) Jei: if all filters in the set {Fa (Fa,BBB Bjez output CONT, then the adaptive composition satisfies (az, B)RDDP, Vj E I.
4.1 Individual privacy accounting via privacy filter
Now we design an individual privacy filter, which monitors individual privacy loss estimates across all individuals and all computations, and ensures that the privacy of all individuals preserved. The filter guarantees privacy by adaptively dropping data points once their cumulative individual privacy

---

loss estimate is about to cross pre-specified budget. More specifically, at every step of adaptive composition t, determines an active set of points S. C S based on cumulative estimated individual losses, and applies A, only to St.
Algorithm 2 Adaptive composition with individual privacy filtering
input: for ( 1,...,k do
sequence of algorithms (At))
(5) sup(s, S3)SS(X.) D (i((a-=)),s))l(((afaa
For all X; E S, compute Pt
Determine active set St (X; Fa.B(Pi ,r..,,'''''' (0)
CONT)
For all X, E S, set (0) (0) 1X, E {.}
Pi
Compute 0 = A. St)
end Return (dI....,ax)
Here, Fo.B is the filter from Theorem 4.3 Its validity implies that Algorithm 2 preserves RDP.
Theorem 4.5. Adaptive composition with individual privacy filtering (Alg. 2 satisfies (a,, -RD. Remark 4.6. Algorithm 3 can naturally be applied to privacy accounting in the local DP model. Here, each user would have a local implementation of the individual privacy filter and would stop responding when the filter halts. This is possible because the decision to halt continue for any data point does not depend on the other data points other than through the sequence of reports a
4.2 Answering linear queries
To illustrate the gains of individual privacy, we consider the task of answering adaptively-chosen high-dimensional linear queries. We aim to design an algorithm that receives sequence of queries X' + Rd for all t E N, and upon receiving Qi provides an estimate a of
q1.92..... where Ei=1 2: (X.), where S = ( typical user, many of the queries evaluate to a very small value (having norm close to zero). For example, in the context of continual monitoring [15 20,, platform might collect one real-valued indicator per user per day, and wish to make decisions based off the daily averages of these indicators across users. Here, X, would be a single user, and (X,, = x(() would be the corresponding user's indicator on day L. For example, X(" E {0, 1} could be binary indicator of a change of some state for user day I. For simplicity,
X²". In some applications it is natural to expect that, for
will treat the dataset as fixed, but our results apply more general setting in which the users' data can be updated after each query; for example, additional points might arrive in the process of the analysis (see, e.g.. (7)).
prototypical mechanism for answering linear queries is the Gaussian mechanism, which reports a. Ei=1 qe (X,) &t, where & oT.) If the range of qe is constrained (or clipped) to have norm at most C, then the worst-case RDP loss incurred by answering qi is (a., pt) (a, aC2 //20"((2))))))))))))))))))) This implies that the standard analysis mailysss-which only considers p: p:-allows answering at most ko = [2Bo² (COo)/((aa) queries in order to ensure (a, B BDD... As mentioned in Example 2.6 the
Gaussian mechanism satisfies (a: p()) -individuull RDP for X,, where
Pi = (2)))
Thus the individual privacy filter allows us to provide accurate answers to z as long as each user's responses are "sparse" (more generally, have small Σ₁= (X.) Formally, we obtain the following generalization of Theorem Corollary 4.7. There exists an algorithm A that, given norm budget Buorm and privacy level K for any adaptively-chon
sequence of queries .1.....9 of arbitrary length k, where q: X + Rd provides sequence of answers a1..... .g such that: (1) A is k-CCDP, that is, (a, RR))PPDPPP for all a 2 1; (2) for all t and any 8 E (0. 1), the probability that I|a. Σx.es, qel (Xi)) lo
/ BBoom log(d d/0)/// is at most 6, where S, (X, E S Σ |1 (X:) < Bnorm).
Corollary 4.7 follows from Theorem by setting each A. to be the Gaussian mechanism with o² = Bnorm/ (2x). Note that, due to P Pt. all points are active in St for at least the first k
7

---

computations, as prescribed by the usual worst analysis, and during those ko steps the answers are guaranteed to be accurate. Therefore, individual privacy provides more fine-grained way of quantifying privacy loss by taking into account the value of the point whose loss we aim to measure. While è technically allowed to be arbitrarily large, after a certain number of reports we expect few points to remain active; we discuss stopping criteria in the following section.
4.3 Filter for (c, diffferentaa privacy
By connections between RDP and DP 44 (6],, we can translate our Rényi privacy filter into filter for approximate DP. We define valid DP filter analogously to a valid RDP filter, the difference being that it takes as input DP, rather than RDP parameters, and that it is parameterized by global DP budget Eg 2 0, 8g E (0, 1). We denote by the possibly adaptive DP parameter of Ar.
C def
D (Ar(al-11) (a) ,5a))
sup (S1.52)
Here, Doc denotes the max- max-divergence, obtained as the limit of Rényi divergence by taking a + co. We also denote DP filter by Ge,.á,.
We focus on advanced composition of pure DP algorithms A,. As shown in [29 (see Lemma 3.3 in the latest Xiviv version), DP filter for approximately DP algorithms A, can be obtained by an extension of a filter for pure DP.
Our analysis implies a simple stopping condition for a DP filter, in terms of any zCDP level which ensures (e,, 6,) -DP. For clarity, we give one particularly simple translation from zCDP to DP, however one could in principle invoke more sophisticated analyse ses such as those of Bun and Steinke [4]
Theorem 4.8. Let B* be any 2 O such that B-zCDP implies (Eg, -DP. Then,
CONT, if 1 HALT, if Σ & B*
1 B":
Geg,5, (x)
a valid DP filter. For example, we can take B (- (oglog(( 1/bg) v (0gg)/6))) - Eg e²)
For example, if the privacy parameters are fixed up front and = simplifying the stopping
criterion of the above filter implies that the adaptive composition of c-DP algorithm satisfies
(Gke² + log(/g)) 6), for all 8 > O. This tightens the rate of Rogers et [29, whose filter halts when
(I 1+ C(Eg, og)
ke
) log(1/6g) > Eg.
2 ke(e- + 11)
/ 2 2kk² + C(eg,
[+ (1+ 0.5
where O(Eg,5,) 28.04 1785) The factor Cleg 6,) essentially determines the gap between our analysis and the analysis of Rogers et al., and our filter is noticeably tighter for non-nggligible values of C(ey, 5,). In addition, our filter has an arguably simpler stopping criterion.
Further improvements on the rate are possible via a more intricate conversion between zCDP and DP, as presented in 4
Private gradient descent with individual privacy accounting
A popular approach to private model training via gradient descent is to clip the norm of all gradients at every step and add Gaussian noise to the clipped gradients M. Existing analyses compute the privacy spent far by using uniform upper bound on the gradient norms, determined by the clipping value. Using the individual privacy filter, we develop a less conservative version of this approach, one which takes into account the realized norms of the gradients, rather than just their upper bound.
There are various ways to incorporate individual privacy filtering into private gradient descent (GD) 11. To facilitate the comparison, we present particularly simple one. As in private GD, at every step we clip all computed gradients and add Gaussian noise. However, after the round at which private GD would halt, we look at the "leftover" privacy budget for all points, and utilize them until their budget
8

---

runs out. The leftover budget is essentially the gap between the corst-case sum of squared gradient norms (determined by the clipping value) and the sum of squared norms of the realized gradients.
Algorithm Private gradient descent with filtering
input: dataset (X Xn), loss function {(0; Xt), learning rate (n+) noise scale > 0, clip value C. > O, number of steps kmax E N, squared norm budget Buorm >
Initialize 81 arbitrarily
for = 1.2..... kmax do
Compute gradients Sr (X;, + Vol(((;
Clip De (X:)
ge( min [19x(X:))2z C, BBoom 10 Vi
(X,
Add noise 9t < 1 - (X,, + NN(00 (0))))
n
Take gradient step d++1+ +- 0: 7:9t
end Return 0k+1
For at least Buoomm CC2 rounds, all gradients get clipped to have norm at most C. After that, points adaptively get filtered out once the accumulated squared norm of their (clipped) gradients hits Baorm- Proposition 5.1. Algorithm satisfies B -CCDP, or, equivalently, (a, " -RDP for all a 2 1.
When Buorm- = kC2, the guarantees of Algorithm 3 are the same as those of private GD with steps. However, they do not depend on the total number of steps kmax (himax need not be equal to k), which raises the question of how to set kimax. (Certainly kimax should be at least BBoomm/ Farmm/C /C2,, otherwise the privacy budget is not used up fully for any data point.) If kimax is small, we might stop the optimization too early and thus forgo a potentially higher accuracy; if kimax is large, then a lot of points might get filtered out and we might add high amounts of noise relative to the number of active points. One solution is to periodically estimate the number of active points in privacy- preserving fashion. After round [Buorm/ JC the analyst can estimate the size of the active set {i: E'j |6ø (X+) 112 S Buorm) } (which is a simple linear query) and use it to stop. To reduce the privacy cost of such estimates one can use the continual monitoring technique [15] since each point is filtered out only once. Alternatively, if one only wants to ensure that the size of the active set exceeds a fixed threshold, one can use the sparse vector technique [14] I0 and thus incur an even smaller privacy loss due to adaptive stopping. Another solution is to periodically check the training accuracy, which is again a linear query, and stop once it plateaus.
5.1 Experiments
As proof of concept, we compare the performance of private GD and its generalization with filtering (Algorithm 3) by training a convolutional neural network on MNIST (24). We use the default
architecture in the MNIST example of the Py PoTchh Opacus library B3
We remark that, in practice, it is more common to use private SGD, rather than batch GD. While in principle it is possible to compute individual privacy parameters for SGD, random subsampling of points requires computing gradients for all points at every step to observe gains from individual accounting. As result, SGD is no less computationally expensive than batch GD in the context of individual accounting. Nevertheless, GD requires fewer steps and-importantly-- we observe that achieves a significantly better privacy-utility tradeoff. For example, using the same architecture, the Opacus library reports accuracy (94.63% + 0.34%) for e = 1.16 and d = 10 which is almost the same accuracy we obtain with 0.5 and 8 10 5 (sce table below). Recent large-scall experiments on differentially private training of language models (2] similarly point to larger batches leading to higher utility, and we believe this phenomenon likely holds in many other settings and is worth further exploration.
All reported average accuracies and deviations are estimated over 10 trials. We fix the target DP parameters (e, 6). and evaluate the test accuracy. We set é = 10-5, and vary the value of c. In the first set of evaluations, for every we tune all algorithm hyperparameters to achieve high test accuracy with private GD. For private GD with filtering, to make the comparison as clear as possible, we adopt the same hyperparameters. After Buorm/ /C² steps, query the training accuracy fixed number

---

8 0.3, =1e-5
8 0.5, =1e-5
Number Of active points
Number of active points
40000
43000
20000
33800
20000
23000
Step
Step
Figure 1: Number of active points during one run of private GD with filtering in the tuned regime, for 0.3 (left) and 0.5 (right). The solid vertical line denotes step B Bnorm/ CC?.
of times in intervals of 5 steps and stop adaptively, when the training accuracy is observed be the highest. We provide the specifics the stopping rule and other experimental details in the Appendix.
GD (tuned)
GD (luned) w/ filtering
GD (suboptimal)
GD (suboptimal) w/ filtering
0.3
(93.29 + 0.49%
(93.64 + 0.46)%
(84.77 3.95%
(92.25 + 0.91)
0.5
(94.62 + 0.43|%
(94.90 + 0.26)%
(92.07 + 2.07]%
(94.30 + 0.58)
1.0
(96.25 0.23)%
(96.25 1 0.23)%
(94.45 14 0.45%
(95.33 + 0.34)%
Overall we observe modest accuracy improvements with individual filtering in the tuned regime. The benefits are more noticeable for small while for large c, the accuracy plateaus after Buorm/CC steps and hence we do not add extra steps. Figure I we plot the number of active points, i.e. those that have not yet exhausted their privacy budget, for E {0.33, 0.5}. Due to extensive hyperparameter tuning in this specific application, private GD is implicitly tuned clip the gradients in such way that hard-to-classify points exhaust their privacy budget. Such tuning, however, is not possible when queries are chosen by human analysts (which is also hard to run experiments on) and in federated settings where data is held by the clients and finding the optimal setting of hyperparameters is typically infeasible. Therefore we examine the benefits of individual filtering examples of such suboptimally tuned settings. For example, chosen to be larger than in the optimal setting (while keeping the noise level the same). Specifically, for E {0.3, 0.5}. set C' to be 1.5 the optimally tuned value, and for 1.0 set C' to be double the tuned value. We reduce the number of optimization steps accordingly to achieve the same privacy guarantee. In the suboptimal regime, the benefits of individual filtering become much more significant as a large fraction of points remain in the active pool after Bporm/ /C² steps. Similar results obtained when the noise rate is not optimally and include the results in the Appendix.
evaluate the performance when the clipping value C' is
Altogether, we view this application accounting is practical, easy to implement, and can only make the results better.
useful proof of concept: it demonstrates that individual
Acknowledgements
We thank Katrina Ligett, Kunal Talwar, and Neil Vexler for insightful discussions on individual notions of privacy and feedback on this work. We are grateful to Ryan McKenna for providing code and suggestions for the experiments. TZ acknowledges support from an Apple PhD Fellowship.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016.
[2] Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differentially private BERT. arXiy preprint arXiv:2108.01624 2021.
10

---

[3] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eightt annual ACM symposium on Theory of Computing, pages 1046-1059, 2016.
[4] Mark Bun and Thomas Steinke, Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-636-- Springer, 2016.
[5] Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In Algorithmic Learning Theory, pages 421-457, 2021.
[6] Rachel Cummings and David Durfee. Individual sensitivity preprocessing for data privacy. In Proceedings of the Fourteenth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 528-50 00--547.55 SIAM, 2020.
[7] Rachel Cummings, Sara Krehbiel, Kevin A Lai, and Uthaipon Tantipongpipat. Differential privacy for growing databases. In Advances in Neural Information Processing Systems, pages 8864 8873, 2018.
[8] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint 1005v:190,.02333, 2019.
[9] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380, 2009.
[10] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3-4):211 1-777, 2014.
[11] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint 1603.0 087, 2016.
[12] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology EUROCRYPT, pages 486-503, 2006.
[13] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pages 265 284, 2006. URL httphh//xx.......// doi. www.ii.rgg11...00 1007 2ttg//00.000/1111178881 111111111188811444
[14] 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, pages 381-390, 2009.
[15] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715-724, 2010.
[16] Cynthia Dwork. Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2010.
[17] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toni Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Advances Neural Information Processing Systems, pages 2350-2355 2358,235,2220 2015.
[18) Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the serty-seventh anmual ACM symposium on Theory of computing, pages 117-126, 2015.
[19] Hamid Ebadi, David Sands, and Gerardo Schneider. Differential privacy: Now it's getting personal. Acm Sigplan Notices, 50(1):69-81) 2015.
[20] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468-244 24882279..00 SIAM, 2019.

---

[21] Vitaly Feldman and Thomas Steinke. Calibrating noise to variance in adaptive data analysis. In Conference On Learning Theory, pages 535-544, 2018.
[22] Arpita Ghosh and Aaron Roth. Selling privacy at auction. In Proceedings of the 12th ACM conference Electronic commerce, pages 199-208, 2011.
[23] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. IEEE Transactions on Information Theory, 63(6):4037 4049, 2017.
[24] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: http://yann. www.aannwweuu..oooo com/exalbnurist, 2, 2010.
[25] Katrina Ligett, Charlotte Peale, and Omer Reingold. hounded-leakagee differential privacy, In 1st Symposium on Foundations of Responsible Computing (FORC), 2020.
[26] Uya Mironov. Rényi differential privacy. In IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[27] Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, pages 157-175. Springer, 2016.
(28) 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, pages 75-84, 2007.
[29] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: Pay-as-you-g composition. Advances in Neural Information Processing Systems, 29: 1921-1929, 2016.
[30] David M Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proceedings on privacy enhancing technologies, 2019(2) 2019.
[31] Yu-Xiang Wang. Per-instance differential privacy. Journal of Privacy and Confidentiality, 9(1), 2019.
[32] Steven Wu, Aaron Roth, Katrina Ligett, Bo Waggoner, and Seth Neel. Accuracy first: Selecting differential privacy level for eecuracy-constringe ERM. Journal of Privacy and Confidentiality. 9(2), 2019.
[33] A. Yousefpour, Shilov, A. Sablayrolles, Testuggine, K. Prasad, M. Malek, Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, G. Cormode, and I. Mironov, Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109. 12298, 2021.
12


Reviews:
[{"review_id": "o7-aRUhsB2F", "reviewer": "Reviewer_Qurk", "summary": "The paper carries out the “take suprema later” idea in DP. In particular, by moving the supremum over previous algorithm outputs and neighboring datasets outside of the expectation, they design a new filter for RDP that can potentially achieve savings in the DP parameters. As concrete evidences, they provide a theoretical result where a significant saving can be exploited from the sparsity, and a more practical one using MNIST showing that the saving is significant for suboptimal hyperparameters.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper carries out the “take suprema later” idea clealy. Their results are stronger and clearer than those in Rogers et al. I have many compliments regarding this in a previous review, so I will not repeat.\n\nCompared to the previous version, the formal statement about sparsity is satisfying. This resolves one of the issues I posed. However, I am not fully convinced about the following issue.\n\nThe current presentation of Algorithm 3 doesn't reveal its computational cost. In particular, an expensive loop is presented using universal quantifier and summation. Although the authors remarks that SGD and minibatch does not save time with filtering, it would be easier for readers to see if it is revealed in the algorithm.\n\nOn the same issue, I still don't see the running time even in the appendix. If the experiment is run on very expensive machines that only big companies can afford and it takes significantly longer time than SGD, then the authors argument about \"suboptimal hyperparameters are more common\" is less convincing --- the computational resources can be spent two ways\n\n1. Tune the hyperparameters really hard using SGD\n2. Change SGD to the more expensive GD and put all the hope on the filter proposed in this paper\n\nIt requires further evidence that 1 is better than 2. In particular, I don't know why there are less experimental details in this version (appendix included) than the previous one.\n\nOverall, I think it is a good paper. However, I'm very eager to hear the authors response. I'd love to change my score if I misunderstood.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 this time. A lot last time"}, "extra_text": {}}, {"review_id": "mbz65mrs2x6", "reviewer": "Reviewer_6u2m", "summary": "\n      The paper proposes an individual privacy accounting via a Renyi filter. In their algorithm, each data point maintains a fixed privacy budget; The privacy filter will adaptively drop points once their personalized privacy loss exceeds the budget. The authors provide a tighter analysis of privacy loss composition by tracking the associated divergences at an individual level. \n \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Weak points and question:\nI have a question about the experiments. When the epsilon increases, the gain of using the filter decreases. I am wondering if the benefits of the privacy filter will decrease in the low-privacy regime? \n\nStrengths:\n\n1. Their Renyi DP-based individual privacy filter is of huge potential usefulness to the Federated learning community. For example, their private gradient descent example can be generalized to the federated setting where each client can maintain a privacy budget. \n\n2. They provide a new adaptive composition theorem for RDP, which allows a sequence of adaptively chosen privacy parameters during the training. \n\n3. The related work section is helpful. The authors thoroughly compared their work to other personalized DP/data-dependent DP.   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5 hours"}, "extra_text": {}}, {"review_id": "cpZEIfqXB5m", "reviewer": "Reviewer_Aso5", "summary": "This work proposes to track each individual's privacy loss when applying mechanisms to a database to preserve Renyi DP, instead of using the worst-case privacy budget as in the common composition.\nMore experiments and discussions are needed to support claims in the abstract.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The idea of giving a tighter bound for privacy by considering each individual is appealing at the first glance\n- The extension to the adaptive case is natural, and the algorithm proposed has a simple form in the linear response situation\n\nWeakness:\n- The work aims to allow more responses with the same privacy guarantee since the previous bound is conservative. However, the experiment results are not strongly supportive of its effectiveness. More experimental evidence is definitely needed.\n- How to deal with the batch update? Is it worth exploiting the individual privacy loss?\n- It would be interesting to compare it with the local differential privacy\n- Minor problems with the notation and concepts, say, what's the point of Definition 2.5? Also, the Algo. 3 uses a different mechanism as before.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "addressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "P9KHXcB_WOc", "reviewer": "Reviewer_7fdb", "summary": "This paper present a fully adaptive composition theorem for the Renyi differential privacy that bounds the overall privacy loss by the personalized privacy losses of all data points. The proposed adaptive composition theorem generalizes the vanilla composition theorem for Renyi differential privacy. The individual privacy accounting is designed as a privacy filter, which monitors the individual privacy loss across all individuals and time to make sure that the data points are dropped when cumulative privacy loss is about to violate the privacy budgets. Besides the theoretical guarantees, the training procedure via DP-stochastic gradient descent is also discussed on how to incorporate individual privacy filtering. Empirical study on MNIST dataset also shows improvements on the proposed privacy filtering method.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Vanilla accounting approaches are too conservative and those harm the accuracy (utility); therefore, the proposed individual accounting approach aims to improve this shortcoming. In Section 4.2, the authors provide a scenario on high-dimensional linear queries where individual accounting leads to better privacy-utility tradeoff. The key is to compare the privacy budget in the worst-case RDP and that in the individual accounting. In particular, when the max norm of $q_t$ is larger than $\\sum_{j=1}^t\\|q_j(X_i)\\|_2^2$ (i.e., each user’s responses are sparse). In high-dimensional setting, it is possible. However, a query function is not usually high-dimensional and this scenario does not seem to be practical. Is there other more practical scenarios where the advantages of individual accounting can be theoretically proven? What are the general scenarios where the individual accounting will outperform vanilla accounting?\n\n2. When the learning model is carefully tuned, the privacy budgets are all spent and therefore in the empirical study on MNIST in Section 5.1, the improvement with filtering is very marginal comparing to GD (tuned). In most machine learning settings, the neural networks are perfectly tuned. The empirical study did not show the cases when it is hard to perfectly tuned the network parameters, e.g., distributed learning, transfer learning. To me,  the experiments are not sufficient to support the claims made in the Introduction.\n\n3. The paper uses a lot of space on Renyi-DP, but there is no empirical study on RDP in the experiments. How does different $\\alpha$  in RDP affects the performance of the filtering?\n\n4. The authors emphasize that GD is more computationally efficient comparing to private SGD and batch GD. A more thorough discussion is needed and run time reported. \n\n5. It will be great to show the decision made by the Renyi filter in the experiments, e.g., when to continue and when to halt. \n\n6. When the network weights are suboptimal, the Renyi filter improve the performance. Are the queries sparse in this case?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Personalized DP is a very important and practical topic in designing a DP mechanism, since the vanilla DP guarantee is often too pessimistic. There is not potential negative societal impact presented in this work. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns is presented in this paper. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "5Fh8uRIv-zc", "reviewer": "Reviewer_3v4m", "summary": "Overview: Privacy filters are probabilistic objects which allow one to study the composition of differentially private algorithms in a setting where the privacy parameters can be chosen adaptively. While filters have been constructed for the case of pure and approximate differential privacy, they have not been studied in the context of Renyi privacy. Moreover, there hasn’t been any study of individual privacy filters, objects which selectively drop elements out of the dataset when their privacy loss exceeds a certain preselected threshold.\n\nThis paper introduces Renyi privacy filters, objects providing theoretical guarantees for the composition of Renyi DP algorithms where the privacy rates can be chosen adaptively. In addition, the authors extend these filters to the individual level, allowing for selective removal of datapoints from the dataset in order to continue computation without exceeded a predetermined level of privacy. The authors provide a comparison of their privacy filters to others, showing significant closed-form improvement in several cases. Likewise, they provide experiments showing the application of individual privacy filters to private gradient descent.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: While privacy filters are not original to this, the extension of the concept to Renyi DP is useful as many of the tightest analyses of common mechanisms rely on this form of privacy. The mathematical analysis does not leverage any new techniques, but it does provide a clean solution to the problem. Individual privacy accounting is novel and seems like an invaluable way of extending the number of computations which can be done on a dataset.\n\nQuality: The paper is mathematically sound. Concepts are well motivated and rigorously presented. Some more investigation could have been done into using RDP filters to construct filters for approximate differential privacy, as this seems like one of the most promising applications of the results of the paper.\n\nClarity: The writing is mostly, and the paper flows well. Some sections (such as the experiments or applications to approximate DP) could have been further touched upon, as these really show the value of the theoretical contributions. Privacy loss is key to the paper, so perhaps it should be discussed more in the main body of the paper as opposed to the appendix.\n\nSignificance: The paper is the first to discuss Renyi filters, and leverages them to improve upon the original privacy filters found in [29]. \n\n---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nHigh-level Positives:\n-\tConstructing privacy filters for Renyi DP is very useful, as Renyi DP is used in many privacy accountants like those found in Tensorflow and PyTorch.\n-\tLikewise, the improvement over the original privacy filters in special cases (e.g. pure differential privacy) is impressive, especially given that the obtained bounds are (a) more readable, and (b) more closely match advanced composition.\n-\tThe proofs are all clean and easy to follow, which helps make the presentation of Renyi Filters very clear.\n\n\nHigh-level Negatives:\n-\tThe proofs are mostly straightforward and do not introduce novel analysis techniques. The main mathematical arguments just apply standard results from martingale theory or standard conversion results between forms of privacy.\n-\tThe use of Renyi Filters as approximate DP filters is very interesting. More comparisons would be valuable- even numerical ones if getting a closed form expression isn’t possible.\n\nAdditional Comments:\n\nSection 1:\n-\tThe problem is very well motivated, and the notions of filters, both at the individual and overall level are clear. Moreover, the relation to existing work is clear as well.\n\n\nSection 3:\n-\tIt might be useful to formally define the privacy loss in the body of the paper, as it is the key theoretical object used to prove results. Moreover, it is ultimately the object the filters are trying to control.\n-\tIn the statement of Theorem 1, you state that the sequence of algorithms is of finite length, consisting of k algorithms. I think you can have it be of infinite length and still be able to apply the optional stopping Theorem in the proof.\n\nSection 4:\n-\tYou handle the case of pure differential privacy, but only provide an explicit bound for the case where all privacy parameters, e_t, are chosen to be the same in each round. I think it would be very informative to show more general cases to demonstrate superiority over the bounds found in Rogers et. al.\n-\tPure privacy filters don’t immediately yield approximate privacy filters. There is a conversion cost necessary that can be quite large depending on the choice of privacy level epsilon. This wasn’t in the original version of [29], but more recent version have addressed this gap as an error was pointed out (such as the newest version on Arxiv I believe).\n\nSection 5:\n-\tThe experiments are interesting. Due to the fact the privacy filters allow you to change privacy levels based on previous algorithm outputs, it would be interesting to see if varying the privacy level as one goes would affect the convergence rate of gradient descent.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do adequately address limitations. For instance, in the experimental section, they discuss that they often times only see limited empirical improvement using individual privacy accounting. Otherwise, the theoretical contributions generally improve on pre-existing results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides new results for (differential) privacy filters that ensure that the individual privacy loss does not exceed certain thresholds. This is an important question in differentially private machine learning, and the paper gives non-trivial technical contributions. During the discussion, reviewers raised some questions regarding the experiments. The authors should provide further details about their experimental setup in the next revision.
Decision: Accept (Poster)