Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification
Authors: Jan Schuchardt
Mihail Stoian
Arthur Kosmala
Stephan Günnemann
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Privacy-Preserving Machine Learning
Amplification
Subsampling
Accounting
Primary area: privacy
TL;DR: We propose a unified procedure for deriving amplification-by-subsampling guarantees and use it to analyze group privacy under subsampling.

Abstract: Amplification by subsampling is one of the main primitives in machine learning with differential privacy (DP): Training a model on random batches instead of complete datasets results in stronger privacy. This is traditionally formalized via mechanism-agnostic subsampling guarantees that express the privacy parameters of a subsampled mechanism as a function of the original mechanism's privacy parameters. We propose the first general framework for deriving mechanism-specific guarantees, which leverage additional information beyond these parameters to more tightly characterize the subsampled mechanism's privacy. Such guarantees are of particular importance for privacy accounting, i.e., tracking privacy over multiple iterations. Overall, our framework based on conditional optimal transport lets us derive existing and novel guarantees for approximate DP, accounting with Renyi DP, and accounting with dominating pairs in a unified, principled manner. As an application, we analyze how subsampling affects the privacy of groups of multiple users. Our tight mechanism-specific bounds outperform tight mechanism-agnostic bounds and classic group privacy results.

Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification
Jan Schuchardt', Mihail Stoian?; Arthur "ossmala Günnemann' {j. sisshuchhardt, a. kosmala, s gguennmmnnn@@uum de, mihail. setaailsstooi stt.sssiiiii stoian@utn. de Deptt of Computer Science & Munich Data Science Institute, Technical University of Munich Dept. of Engineering, University of Technology Nuremberg
Abstract
Amplification by subsampling is one of the main primitives in machine learning with differential privacy (DP): Training a model on random batches instead complete datasets results in stronger privacy. This is traditionally formalized via mechanism-agnossicc subsampling guarantees that express the privacy parameters of subsampled mechanism parameters. We propose the first general framework for deriving mechanism- specific guarantees, which leverage additional information beyond these parameters to more tightly characterize the subsampled mechanism's 's privacy. Such guarantees are of particular importance for privacy accounting, i.e., tracking privacy over multiple iterations. Overall, our framework based on conditional optimal transport lets us derive existing and novel guarantees for approximate DP, accounting with Rényi DP, and accounting with dominating pairs in unified, principled manner. As an application, we analyze how subsampling affects the privacy of groups of multiple users. Our tight mechanism-specifie bounds outperform tight mechanism- agnostic bounds and classic group privacy results.
function of the original mechanism's 's privacy
Introduction
Composability and amplification by subsampling are two key properties of Differential Privacy (DP) [+3 that make it possible to provide provable privacy guarantees for machine learning algorithms that iteratively learn from batches of data.
Composability means that privacy gracefully deteriorates when iteratively applying a differentially private mechanism to a dataset (2). Kairouz et al. 44. Murtagh and Vadhan [5] ultimately derived tight composition theorems that optimally characterize the privacy parameters (s', 8') of a composed mechanism as a function of the component mechanisms' parameters (E, 8). However, later work demonstrated that these guarantees are only tight in a mechanism-agnosti sense (6) Stronger mechanism--peettee speciific composition guarantees can often be obtained by using additional information beyond the fact that the mechanisms satisfies some notion of DP. Methods for tracking privacy over multiple iterations (e.g. (6122) are refererred to privacy accountants.
Amplification by subsampling means that privacy can be strenghtened by applying a differentially private mechanism to randomly sampled batches of a dataset [13] 14. Similar to Kairouz et al.
4. Balle al. [15] ultimately proposed framework for deriving tight subsampling theorems that optimally characterize the privacy parameters (s', 8') of subsampled mechanism as function of the underlying base mechanism's 's parameters (e, 6).
However, their framework for deriving subsampling theorems has two key limitations. Firstly, as shall demonstrate, the resultant guarantees are generally only tight in mechanism-agnostic
Equal contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

sense: Given (E. 8), one can construct some worst-case (c,5)-DP mechanism that (=',8")-DD )DD under subsampling. The specific mechanism at hand may however be significantly more private. Secondly, their framework does not explain how to derive subsampling guarantees for privacy accountants. In fact, there is so far no unified framework for deriving subsampling guarantees for privacy accountants.
To address these two limitations, we propose novel framework for unified mechanism-speciee amplification by subsampling analysis, using conditional optimal transport. Our proposed framework (1) lets us derive mechanism-speeific subsampling guarantees, which can be stronger than mechanism- agnostic guarantees, (2) lets us recover mechanism- agnostic guarantees via a pessimistic upper bound essentially subsuming the approach from [15] and (3) lets us derive guarantees for approximate differential privacy (2). moments accounting 6 (i.e., Rényi differential privacy 77), and accounting
with dominating pairs [10] (e.g., numerical accounting [6 g 17 in unified, principled manner.
As practical application, we consider the prob- lem of tightly analyzing group privacy under subsampling (see Fig. D. Assume scenario where K individuals may independently decide to contribute dataset. Further assume that this dataset is processed by randomly sampling batch and applying an (e, 5)-DP base mecha- nism. A special case of this setting is discussed in a recent technical note (22]. which assumes that the K individuals co collaboratively agree to either contribute or not contribute all their data and that the base mechanism is Gaussian. In the general setting we consider, the best known method for providing privacy guarantees for the entire group is to (1) use existing bounds to show that the subsampled mechanism guaran- tees (E', 88' DDP for individuals and (2) use the group privacy property (23) to show that this im- plies (K e', K K.s' -DD for the group.
11 X2
Xxy
X
x²2 x
Subeampling scheme S
Pr = (1 -ry"
Pr 2r(1 -n)
Pr m
X1 X2 No.
X5 X, x
Xg x1 x22
X10 X6 Xs
X, X1 X2
117 x25 X1
Base mechanism B
Group members 2/ contribute to dataset, while group member z/g does not. For small subsampling rates it is unlikely to access single (Pr = 2r(1 -)) or even both (Pr r²) in- serted elements when applying base mechanism B to a subsampled batch (e.g., the yellow one). This further obfuscates which data was contributed by members of group {x1, 241,2222%))
Figure 1:
Our proposed framework lets us derive stronger, tight group privacy amplification guarantees. By analyzing group privacy and subsampling jointly, these guarantees accurately capture that it is unlikely for a large fraction of the group's s data to simultaneously appear a batch. Our framework further lets us derive dominating pairs [10), which enables tight tracking of group privacy under composition. Overall, our main contributions are that we
demonstrate for the first time that there is a qualitative difference between mechanism- specific and mechanism -aahanis--aanootiic tightness in privacy amplification,
propose general framework for deriving mechanism-specific amplification by subsampling guarantees, subsuming prior work on mechanism-agnostic amplification,
develop the first unified method for deriving subsampling guarantees for privacy accounting, and derive the first tight subsampling guarantees for general group privacy.
As part of our group privacy analysis, we also significantly generalize recent results derived for subsampled matrix mechanisms (24]. which is of independent interest. Experimental evaluation demonstrates that our tight mechanism-speciff guarantees outperform both tight mechanism-agnostic bounds and post-hoc use of the group privacy property.
2 Background and preliminaries
Problem setting. We consider the same setting as Balle et al. [15] but with an additional privacy accounting and group privacy perspective. We assume a space of datasets X, a space of batches Y that can be constructed from these datasets, and an output space Z. For the sake of exposition, we assume that X is the powerset PAA) of some finite discrete set A, that Y = { S x x E X}. and that Z D. We further consider a random subsampling scheme S - Y that generates batches from datasets, and a random buse mechanism B: Y RRP that maps batches to outputs. We write 8 (y) for the pmf of S(X) and and by( for the pdf of B(y). Appendix D)
we introduce a more general setting that admits arbitrary spaces, for which we derive all our results. Our goal is to
2

---

provide formal privacy guarantees for the subsampled mechanism = B o S, which takes a dataset, subsamples a batch from it, and then applies the random base mechanism to this batch.
Dataset and batch relations. Specifically, we want to prove privacy under neighboring relations _x X between datasets. For example, the insertion/remooal relation =1,x x' implies that ='= x {a} or x' = x \ {a} for some a. The substitution relation x ~A.x x' implies that x' { (a' for some a, a.a'. In addition, we assume that is equipped with batch neighboring relation CyC Y². The batch relation my can be distinct from the dataset relation =x.
Subsampling schemes. While we consider arbitrary subsampling schemes S X Y. shall later apply our framework to three particularly common ones: Subsampling without replacement and with replacement sample sets and multisets of fixed size |y/ q uniformly at random. Poisson subsampling includes each element of x with independent probability ("rate") r E [0, 1].
under symmetric neighboring relation 2g when the distributions of (az) with densities mg. m² are almost indistinguishable for all x =x x', Approximate differential privacy (ADP) [2] quantifies
Approximate differential privacy. A mechanism M X - DR is privacy-preserye
this via hockey stick divergences (25]
Definition 2.1. For E 2 0, a mechanism M : - R is (s, 6)-DP under symmetric relation ~x iff Vx =x x': Her (m,y m S ô with H. (m. mma)) = JRD max (x) (z) 03-m> (2) dz.
Note that this divergence-basee definition of approximate differential privacy is equivalent to requiring
for all datasets x =x x' and all events $ C TR. that Pr[M(()) E S) S e Pr(M(x') E S] + 6.
Rényi differential privacy, Privacy accounting was first popularized by methods that used moment bounds instead of (c, 5) pairs better track privacy under composition 26) (7)) These methods were later developed into a moments-basee based notion of privacy - Rényi differential privacy (RDP) 77]
Definition 2.2. For a 2 1, a mechanism M: X DD (a, p)-RDP under symmetric relation ~x iff Vxz "x x':
lAa (aa(aAammaaa (m=llm=>) (a 1) S with Ao (m (ma) = JRD m²(2)² (2)"))))))()())) 1zz
Note that A. is not the Rényi divergence, but its ath moment, i.e., scaled and exponentiated Rényi divergence. We use this notation to climinate exponential terms that arise in amplification for RDP (see 28 30). If mechanism is (a. p)-RDP, its T-fold self-composition is (a, T p)-RDP, These RDP parameters can then be converted to ADP parameters (c, 5), albeit in a lossy manner 7 31 32
Dominating pairs. Later work proposed other numerical [16 g 21 or analytical accounting techniques p 33 28
34 35). Zhu et al. [10 developed unified view on these works by introducing
the notion of dominating pairs:
Definition 2.3. A pair distributions (P, with densities (p, q) is dominating pair for mechanism M under neighboring relation =x, if H. (m.l S (pllgg for all =x x' and all a 2 0.
Given a dominating pair (P,Q), one can use various numerical analytic techniques, such as convolution of privacy loss distributions [66] or central limit theorems of tradeoff functions (9) to track the privacy of mechanism M under composition (see Fig. in I0)..
Group privacy. The group privacy property is the graceful decay of privacy when considering multiple user's data. This is normally formalized via the notion of induced distance (see 7 15
Definition 2.4. The distance (x, x²) induced by relation 2x is the length of the shortest sequence
(Zi,..., TK -1) 1) Example 2.5. Let <x be the insertion/removal relation - Then the induced distance dx between [1,2] and x' (2,3) 3) because [1,2] - 21,3,3 ~+ (2.3).
- such that x =x 31, Vk: 2g 2x Fk+11 and -K- =x x'.
Proposition 2.6 (Vadhan (23). If mechanism M : X + RDD is (s. DDD under relation 2x, then it (K E, k.e -DP under group relation {( 2') E x2 dx(x, K).
That is, for sufficiently small the ADP parameters deteriorate appproximately linearly with induced distance. As basclines for our experiments, we use even tighter bounds (see Appendix C.I.4.
3 Unified mechanism-speciff. amplification by subsampling
Our goal to develop general procedure for (tightly) deriving ADP parameters (E',8)) RDP parameters (a', p'), or dominating pairs (P', Q') for the subsampled mechanism M = Bo with
3

---

subsampling scheme S and base mechanism B. Based on Definitions 2.1 to 2.3 this requires that we evaluate or bound the hockey stick divergence H., or the scaled and exponentiated Rényi divergence Aa between the distributions of (x) and M(x') with x =x x'. To discuss both simultaneously, let us write V. for either Ha or Aa and assume that a 2 or a 2 1, respectively.
There are two challenges: Firstly, the distribution of M (z) is high-dimensional mixture distribution with one component per possible batch y E Y' and weights given by batch probabílitites 5y (y), i.e., (=(=) = Eyey (z)= s (v). Secondly, there may be no simple analytic formula for the component densities. For instance, evaluating the density of perturbed model gradients in noisy SGD [36 requires backpropagation. Both challenges make it hard evaluate or bound (m.
A useful property that will help us in addressing the first problem of having a large number of mixture components is the joint convexity of Va in the space of probability density functions [37] [38]
Lemma 3.1. Consider arbitrary densities f(²) f()).
f(2) f(22)
.RD - B. and weight w E [0. 1].
Then, Vo (u +(1 11--w -w] "| + (1-w) 22 (2)) S W. (1 ) + V. (22 (22 (11)))
(1)
[
In our case, the Iss can be base mechanism densities by with different y E Y. and the weights can be given by the subsampling distribution. We could thus upper-bound the mixture divergence L (mz]|m,, ) in terms of component divergences if the mixtures had identical weights. This is generally not the case, since subsampling mass functions sz (-) and (-) depend on datasets I # x'.
To still leverage the joint convexity of V. (m=llm=.) we want to rewrite m, and myr as mixtures with identical weights. This is exactly what is offered by couplings between probability mass functions. Intuitively, coupling between two pmfs Pt. P2 Y - [0, 1] specifies for every v1, V/2 Y how much probability should be transported from to 3/2 to transform pi into p2. Couplings can be formalized and generalized to multiple pmfs as follows (for more thorough introduction, see (39]):
Definition 3.2. A coupling between N pmfs PI...., PN
Y + 10, 1] on batch space Y is a joint pmf y: Y - [0, 1] where the rith marginal is pn, i.e. Po (1%) Eyer" 1 [y vil 73y).
Given valid coupling ? between subsampling mass functions 8, and Sa', we can use marginalization to rewrite (=) as Σyevz by, (z)) Similarly, we can rewrite myr as Σyevs byg (g) Now, both mn and my are mixtures with identical weights and one component per pair of batches in
Y2. We can thus recursively apply Lemma 3.1 to show (full proof in Appendix E
Theorem 3.3. Consider a subsampled mechanism M = B a S, and an arbitrary coupling 7 between subsampling mass functions (x()) and 8x (-). Then,
V a (ma (m S Σ
ca (v 12)) (1
yE
with cost function ca: Y x Y + R4 defined by ca (1
(1()),((2) (()) = =v (a(by. (b,,,o116b..)))) (1b))c)))
We write ( instead of y1 to simplify later notations. While every coupling 7 yields a valid upper bound, the guarantees can be tightened by finding a coupling Y that minimizes the r.h.s. of Eq. (I). We thus have an optimal transport problem, where the cost c, of transporting probability from batch (1)) to batch (2) depends on the divergence V. of base mechanism densities by,: and by:
Unfortunately, experimental evaluation in Appendix B. shows that the resultant guarantees can be much weaker than those from prior work even with an optimal coupling -- This because Theo- rem 3.3 results from recursively applying the joint convexity property (Lemma 3.1 to (m [m..) Each recursive step splits each mixture into two smaller mixtures and further upper-bounds the divergence that is achieved by our specific subsampled mechanism M on specific puir of datasets x, x'. Upon fully decomposing the overall divergence into divergences between single-mixture com- ponents, this sequence of bounds is in fact larger than even the divergence V. (ma (ma)) achieved by worst-case subsampled mechanism M on worst-case pair of datasets ă, ø'. To overcome this limitation, we propose to limit the recursion depth in order to obtain a tighter upper bound that matches our specific subsampled mechanism M a worst-case pair of datasets b. 3'.
Limiting the recursion depth to which Lemma 3.1 is applied means upper-bounding (m l|mz) in terms of mixture divergences that have not been fully decomposed into their individual compo- nents. Specifically, we propose to do so by defining an optimal transport problem between multiple subsampling mass functions conditioned on different events (proof in Appendix E

---

Theorem 3.4. Consider a subsampled mechanism M- = B S. Further consider two disjoint partitionings
= A4= and - " of batch space 'I such that all A, and Ej have non-zero probubility under the distribution of Sn and Sat, respectively. Let 7 be an arbitrary coupling between conditional muss functions 8z(- Ai)..... 88(. Ar), (ar Ei),...,88 Bar ET). Then, co co ()) ,2))) ((x( ,y(
[a(mal| -
Σ DEV!-J
with cost function Y x V. + R++ defined by
() (2)) Va
Σ b b Pr(S(() A.ll Σ uga Pr(S(x') E Ej] j=1
(2)
In other words: We now have optimal transport problem between I + probability mass functions coupled by 7. The transport cost Ca is a divergence between two mixtures. The components of the first mixture are base mechanisms densities given batches yi (1) Y from batch tuple y E Y The weights of the first mixture are probabilities of events A,. The second mixture is defined analogously.
Note that we can recover Theorem 3.3 by conditioning on a single event, i.e., A1 = Y, E W. As we shall demonstrate, more fine-grained partitioning lets us obtain tighter bounds that match the divergence V. (m& [aa) ) of our specific subsampled mechanism M on a worst-case pair of datasets f, In the extreme case of defining event per possible batch, Theorem 3.4 holds with equality.
Overall, Theorem 3.4 reduces the broad problem of bounding mixture divergences to the canonical problem of optimal transport between conditional distributions. But before we can apply it, we need to address two open problems: Evaluating the cost function and designing optimal couplings.
Cost function bound. Not having an analytic expression for every base mechanism density by (=) may make it intractable to evaluate cost function co- We thus propose to bound it via an approach that is inherent to differential privacy: Considering worst-case inputs (proof in Appendix E.
Proposition 3.5. Consider ())) E y E vV, and cost function defined in Eg. 2 Let du be
the distance induced by my (see Definition 2.44. Then, ca ca ((2)) S ca (y(()), y (2) with
Ca(y (2) max Ca(g (2))
subject to Vk, E [1,2), VL, u: dr 1 dr(y) (()) and ( E (2))) y
Put differently: We construct two new mixtures with components that are adversarially chosen to maximize divergence while retaining the pairwise distances between batches in y and y( Note that, for the special case of V,,, H., and / = J 1, this bound corresponds the "group privacy profile" in [15). As we shall demonstrate in the next sections, this bound è can often be evaluated using hivellevel information about the base mechanism B Y IR., such as global sensitivity.
Sufficient optimality condition. While every coupling 7 yields a valid upper bound in Theorem 3.4 this bound can be tightened by designing optimal coupling y², To inform this design, we generalize the notion of distance compatibee couplings from 15] to an arbitrary number of distributions:
Definition 3.6. A coupling y between mass functions P1,--.-PPM PN on batch space Y is dy-compatible when ( > 0 only if Vu > 1 dy(11, Yu) = dx(( (( }, supp((..) and Vuu > >> 1 : dy (Yuu yt) = dy (supp(P:), su)p(pw)), where supp(p.) is the support of 8, and the distance between two sets is the minimum distance of their elements.
Essentially, dy-compatible coupling only assigns probability to tuple of batches y when all pairs ye, yj have the smallest possible distance to y1 and each other while still being in the support their distributions. In Appendix [P we prove that dy-compatibility is sufficient for optimality. We further show that the optimal value has a canonical form whenever a dy-compatible couplings exists.
Summary. To summarize, we propose the following three-step procedure for deriving subsampling guarantees: (1) Define two partitions of the batch space into / and J events. (2) Define simultaneous coupling between the corresponding 7 + J conditional distributions to obtain bound in terms of divergences between small mixtures with and components. (3) Bound these mixture divergences by considering I + J worst-case mixture components under pairwise batch distance constraints.
5

---

3.1 Tight mechanism-specifie group privacy amplification
As concrete example, and to illustrate the difference between mechanism ppchanism-specific and -agnostic (see Section 3.2) bounds, let us consider the group privacy setting from Fig. [T] We have a group of K users that can independently decide to contribute or not contribute their data, and the resulting dataset is Poisson subsampled. 'o provide formal privacy guarantees to the group, we need to prove that the distributions of M(x),, (x') are almost indistinguishable for xt x' with induced distance d1,x(x,x') x²) & K. Let x: KK,.K_ x' be the relation that implies that K+ records are inserted and K_ records are removed to construct x' from 2. We can then show (full proof in Appendix Mi:
Theorem 3.7. Let M B o S, where is Poisson subsampling with rate т. Let my be the insertion/removal batch relation 21, Then, for all x 2K,,K- x x', Va (mal) mlm.) ) is l.e.q.
K-+1
K++1 Σ
max V. y
Σ
o Binom - 11 K- r)ll
b ( Binom(j k+,+)) (4) ";
subject to constraints y -K well as AI {1,2), Vt, dr( (9 (00 S 1t u/. and Vt, u: dr(vt. ( S 1) (u-
Proof sketch. We let A, and Es be the events that Six) contains i deleted elements and S(x') contains - 1 inserted elements, respectively. Our coupling defines the following generative process: We sample vi from s.(( A1) and let y +- yi
(1) We then iteratively generate the other y/!h) by
sampling a permutation in which we add the K_ deleted elements to We then generate the other y3 by sampling permutation in which we add the K+ inserted elements y!² The result then follows from the cost function bound in Proposition 3.5 and dx-compatibility of the coupling. Batches y and y/ and have a distance bounded by |u t/. because one can be obtained from
the other by removing/inserting |u t| elements. The constraints for y/u (2) and yi
(2) are analogous.
Batches ((4 and v/2 have a distance bounded by (1 ---i i) + (u 1) because we need to remove elements and insert u elements to construct one from the other.
Next, we can solve the constrained optimization problem in Theorem 3.7 i.e., determine worst-case components obtain mechanism-speciffe guarantees. For instance (proof in Appendix M.2.1
Theorem 3.8. Let M B o S, where S is Poisson subsampling with rate and B is the Gaussian mechanism h + V with h Y - RDD and V ~ N(0,00 o ID)). Define the Ez-sensitivity L2 = maXy21. Ilf(y) f(2/)l2. Then for all _K_KK_E x', V Va (axmllmm)) is l.e.q.
+1
K++1 Σ
(2) Binom - K2,rr) k
Va
Σ
.inomoi - 1
1=1
with univariate normal densities p!"= - N (1- 1), L2),
-(i- L2).
Note that this bound is rechannss-sppcinn in that it explictly depends on B being Gaussian mechanism with standard deviation and sensitivity L2. The bound can be numerically evaluated to arbitrary precision using standard techniques from privacy accounting literature (see Appendix [M.4). In Appendix M.2 we derive similar guarantees for Laplace and randomized response mechanisms.
Tightness. These bounds are tight in mechanism-specciff sense: One cannot derive stronger ADP or RDP guarantees without additional information about the datasets x, x' E X or the underlying function h (proofs in Appendix M.3).
Asymptotic bounds. Our focus is on tight bounds that can be explicitly computed. However, some early works on RDP accounting (e.g. 6 28 also provided asymptotic versions of their bounds, e.g., as a function of divergence parameter a. For completeness, we use Theorem 3.8 to generalize the
asymptotic bounds of Abadi et al. 6 the group privacy setting in Appendix N.5
Other contributions. Our solutions to the optimization problem in Theorem 3.7 are of independent interest: The special case of V Ha. K_ 0 or K4 0, and Gaussian mechanisms was

---

S(0)
S(O)
500
S(X)
5(0)
5(x
500)
5(x)
S
S
500)
A2
so0
soc &
5001 A.
500 A,
SE0)
6
E,.....
-00)
OT
OT
OT
OT
(b)
(c)
(d)
Figure 2:
Mechanism Mechanism-agnostic guarantees for (a) graph modification 440 42
(b) inser-
tion/removal [4 13| 29 30] (c) substitution 44
can be derived from (d) our proposed
framework. In (b-c), events A, and E, indicate the presence of inserted or substituted elements.
derived to analyze matrix mechanisms in [24 We significantly generalize it via an entirely different proof strategy that admits V. E (Ho, }, arbitrary K4, K_ E No. and non-Gaussian mechanisms (see Appendix
3.2 Tight mechanism-agnosti group privacy amplification
To further illustrate the difference between mechanism-specific and -agmostic bounds, let us apply
the framework of Balle et al. [15] to the same setting: For K_ = 0 or K+ = 0 and 2 O, their ansatz shows that the subsampled mechanism M = a S is (E', -DD with e' = log(1 (1 + (1
Binom[( | K, r)) (ef - 1)) and 8' = E = Binom K,r) - 82. with group privacy parameters 5x max H Hexp(e) (byllby)) s.t. dy(v. v I k (see Appendix No.
Tightness. This bound is tight in a mechanism-age aagnostic sense, i.e., for every & 2 0, one can construct some worst-case mechanism that exactly attains the bound (see Appendix N.2
Meceanism-speeiffic vs pechanism-agnostte tightness. An apparent advantage of this result is that it expresses (s', .8)) simple analytic formula of base mechanism DP parameters 61,..., , 5g- However, this simplicity comes at a cost: As we show in Appendix N.3 this guarantee implicitly upper-bounds the tight mixture divergence bound from Theorem 3.7 in terms of its component divergences using joint convexity As we experimentally demonstrate in Section this relaxation leads to weaker privacy guarantees for group size K > 2. This gap has gone unnoticed in earlier work, because Theorem happens to be identical to the bound of Balle et al. [15) for the special case of K (see proof of Proposition 30 in [TO).. By studying the more complex group privacy setting, we demonstrate for the first time that there is qualitative difference between mechunism-agnosice and mechanism-specisfe tightness privacy amplification.
3.3 From meshanism-speeific to mechanism-agnostic guarantees
The observed relation between tight mechanism-speccffe and mechanism-agnosticc bounds does in fact
extend beyond group privacy (see Fig. 2 As we demonstrate in Appendices G and H mechanism- agnostic subsampling guarantees from prior work can equivalently be derived by (1) conditioning on
at most 4 events indicating the presence of inserted / deleted / substituted elements, (2) defining
simultaneous coupling, and (3) using joint convexity upper-bound the resultant mechanism-speciffe guarantee by component divergences. This includes the ADP guarantees of Balle et al. [15] (and thus
prior work [4 43 44
and the RDP guarantees from 28
40
Subsumption of [15]. Going even further, we show in Appendix G.2 that our approach subsumes the
entire framework of Balle et al. [15): Any mechanism-aggnsticc guarantee derived via their ansatz can cquivalently be derived by defining a (potentially suboptimal) simultaneous coupling between four subsampling distributions and upper-bounding the resultant guarantee via (advanced) joint convexity.
Contribution. Importantly, our contribution not in the bounds themselves, but in the identification of this implicitly underlying pattern that unifies prior work. We further generalize this pattern through our proposed framework to enable tight analysis for more challenging scenarios like group privacy.
Novel RDP accounting bounds. In Appendix ! we use this observation to derive variety of novel mechanism agchanism-agnosticc RDP bounds for different combinations of m', Sy, and subsampling schemes, such insertion/removal and subsampling without replacement. We further derive simple but tight mechanism-specife guarantee for subsampled randomized response under substitution (see Theorem I.3) that outperforms the best known mechanism-agnostie bound (see Section 4
In combination with "advanced joint convexity"
SS

---

3,4 From mechanism-specific guarantees to dominating pairs.
Because the mechanism -ppeniciisssssssiicccceeeeeiiiit guarantees derived via our framework do not obfuscate the un- derlying distributions, they can be used to identify dominating pairs. These dominating pairs can then combined with arbitrary (numerical) accountants to track privacy under composition. For example, can immediately read off from Theorem 3.8 that the Gaussian mixtures are dominating pair for the "insert-K constructing dominating pairs when the bound is weighted sum of multiple mixture divergences. We can thus determine dominating pairs for any bound derived via optimal transport. As we demonstrate in Appendix K the dominating pairs for subsampled mechanisms derived by Zhu al. [IO] (special can equivalently be proven via our framework.
K_ relation. In Appendix we describe a procedure for
cases of which appear in
8 17
Subsampling with replacement. As novel contribution, derive for the first time dominating pairs for subsampling with replacement (see Theorem L..). which were posited but not proven [8] (see discussion in Appendix [ This is enabled by solution to the problem in Theorem 3.7 As
experimentally show in Appendix [B.15]] these bounds can be much stronger than those derived via the framework of Balle al. [15]. These results thus demonstrate that there qualitative difference
between mechanism-specifie and mechanism-agnonn tightness even for group size =
3.5 Limitations and future work
Limitations. While our proposed framework can be applied to arbitrary subsampling distributions, conditioning on a finite set of events may be too restrictive in certain settings (e.g., continuous batch spaces). Also, while we found conditioning on the number of modified elements to be sufficient for all considered scenarios, an automated procedure for selecting events would be desirable. Maximal couplings fulfill this purpose in [15. but only yield pairs of distributions.
Future work. natural direction is applying our ansatz to novel settings other than group privacy. In particular, it could potentially be used to provide epoch-level guarantees for correlated subsampling (e.g.. batching via shuffling), similar to 38). We present preliminary result for 2-fold odnaadattvve composition in Appendix Future work could also use our solutions to the problem in Theorem 3.7 generalize the matrix mechanism analysis from [24 to substitutions and non- non-Gaussian distributions.
4 Experimental evaluation
The purpose of the following experiments is to verify that there can be benefit to using mechanism- specific over archannssmagnosiee subsampling bounds, and that a joint analysis of subsampling and group privacy
offer stronger guarantees than post-hoc application of the generic group privacy property. In all figures, "specific" refers to our proposed mechanism-specifie bounds, "agnostic" refers to (tight) mechanism-agnostie bounds, and "post-hoc" refers to applying the generic group privacy property to tight mechanism-speciff bounds derived for group size For all experiments. assume Ep sensitivities of 1. Further details the experimental setup are provided in Appendix C An implementation will be made available at https://ss.ci www.ics..cittuu tttt.tum.dee
10-2
Agnostic
Agnostic Specific
Group size
Specific
0.6
RDP p(a))
ADP 8(e) ((e)
10
0
0.4
8
0.9
0.75
0.2
10-6
0.6
0.0
101
102
103
104
0
5
RDP &
ADP
Figure 3: Randomized response with WOR sub- Figure 4: Laplace mechanisms with scale À = sampling (q / N = 0.001), group size 1, and varying true response probability 0.
1, Poisson subsampling (r = 0.2), and varying group size.
8

---

4.1 Mechanism-agnose and mechanism-specifie guarantees
Randomized response and RDP. One potential source of looseness in mechanism cechanism-agnostic bounds is that they bound mixture divergences in terms of component divergences that can be summarized by a single privacy parameter. As an example, let consider the best known guarantee for substitution, subsampling without replacement, and RDP from (88] As discussed by the authors, it is only tight up to factors that are constant a. In Fig. 3 we compare it to our tight mechanism-specifit bound for randomized response (see Theorem I.3 with batch-to-dataset ratio g N = 0.001 and true response probability {0.6, 0.75, 0.9). In Appendix [B.1.] we consider other ratios. The tight guarantee
eliminates the constant factors and thus achieves much smaller p for wide range of E (1, 10
Group privacy and ADP. Another potential source of looseness in mechanism-agnoote bounds is that they stem from binary partitioning of the batch space (recall Fig. 2, which may not be sufficient when there are multiple possible levels of privacy leakage (e.g. number of sampled group elements). We demonstrate this in Fig. by comparing the tight mechanism mechanism-agnnstic group privacy bound derived via the framework from [15] our tight mechanism -ppccffc bound for Laplace mechanisms (see Theorem M.2). ADP, scale À = 1, subsampling rate 0.2, and varying group size. Appendix B.. we repeat the experiment with other mechanisms and parameter values, and also consider RDP. As discussed in Section 3.2 the mechanism-agne aagiostic bound is identical to the
mechanismS-ppecffic bound for group size K 1. For group sizes K 2 2, however, the fine-grained partitioning underlying the mechanism-specific bound yields stronger privacy guarantees. These results confirm that we need to distinguish between aechanism-agnosiie and mechanism--ppecific
tightness when analyzing complex subsampling settings.
4.2 Post-hoc and mechanism-speecfic group privacy analysis
Single-iteration group privacy. Our next goal to demonstrate the benefit of analyzing group privacy and subsampling jointly. In Fig. 5 we evaluate our tight guarantee for Gaussian mechanisms (see Theorem 3.8 with 2, rate
0.2, and varying group size. As baseline, we evaluate the same tight guarantee with K+ + K_ = 1 and apply the generic group privacy property (see Ap- pendix C.1.4) post-hoc manner. As can be seen, our tight analysis can lead to much stronger privacy guarantees. However, we interestingly observe in Appendix [B2. that the generic group privacy properties of ADP and RDP can serve as increasingly tight upper bounds when considering more private base mechanisms (e.g., 5) and much smaller subsampling rates (c.g.. r 10-3).
Composed group privacy. Nevertheless, even the gaps tightness for very private mechanisms may quickly accumulate when repeatedly applying these mechanisms to dataset. In Fig.
6 we use the dominating pairs derived via our framework to conduct tight PL.D accounting 16 with "connect
the dots" " [20] quantization using Google's s dp_accounting library [5]. For o = 5, 10 10-3, and fixed 2 (for other pararameters and mechanisms, see Appendix B.2.3). the post-hoc analysis quickly diverges with increasing group size and number of iterations. For example, with group size 16 and privacy budget 6 = 10-6 the post-hoc analysis allows less than 100 iterations of DP-SGD training (36 (). whereas our tight analysis enables training for over 1000 iterations. In Appendix B.2.5 we train an image classification model on MNIST with PLD accounting to demonstrate that this increased number of training iterations can translate much higher model utility.
0.6
Post-hoc
Group size
Post-hoc Specific
10
Specific
16
ADP d(e)
0.4
ADP A(E)
10-10
10
10-16
Group size
2
0.2
16
10-22
8
0.0
1
2
3
250
500
750
1000
ADP
Iteration
Figure 5: Gaussian mechanisms with standard
Figure 6: PLD accounting for Gaussian mecha- deviation a 2, Poisson subsampling (r 0.2), nisms = 5), Poisson subsampling (r 10-3), and varying group size.
and varying group size at & = 2.

---

5 Related Work
Amplification by subsampling for ADP. Using subsampling to strenghten (s. d) guarantees
has long history [3 [4] particularly in privacy-preserving machine learning 46 47 6
For
thorough introduction to subsampling and its interaction with composition, we refer the reader to 48
Balle et al. [T5] ultimately proposed framework for deriving tight mechanism-agnossiee subsampling guarantees. Our work subsumes theirs and enables the derivation of mechanism- -speississsssssseeeeeeeeeeeeeeee guarantees.
Amplification for privacy accountants. Abadi et al. 66's seminal work on moments accounting already considered subsampling. Similiar results were derived for the more general notion of RDP 7 in [28) More recent works on accounting generally include a discussion of either Poisson subsampling or subsampling without replacement [17-19 21 IT] Subsampling with replacement is
discussed in [8), albeit without complete proofs, which we provide in Appendix [ We demonstrate that amplification guarantees for the central notions of RDP Z and dominating pairs [[0] can just like guarantees for ADP - be derived via optimal transport. Our novel approach not only unifies prior, but also enables principled analysis of challenging scenarios like group privacy.
Group privacy amplification. A special case of group privacy amplification (which we use as an example to demonstrate the utility of our general framework) with hockey stick divergences, Gaussian mechanisms, and groups that collaboratively agree to contribute all their data was posited in [24 and proven in recent follow-up note [22] However, their result (and proof strategy) does not cover Rényi divergences, other mechanisms (Laplace, randomized response), and the standard notion of group privacy under which group members are not forced to collaborate (see, e.g..
9 [5 23
Hierarchical randomized smoothing. Randomized smoothing 51 is a technique for construct-
ing provably robust models via DP achieved through input perturbations (e.g. (52 68) ). Similar to
subsampling, Scholten et al. [69] proposed to only apply perturbations to randomly sampled parts of an input. We repurpose their technique of treating subsampling indicators as observable random vari- ables in order to construct dominating pairs from weighted sums of divergences (see Appendix [.T].
Unified amplification for f-DP. Wang et al. 70 proved form of joint concavity for the tradeoff
functions underlying f-DP accounting ( R. This enables them to analyze mixtures induced by random initialization and shuffling in unified manner. However, they do not consider amplification by subsampling, and explicitly state that they need to address this problem in future work. Note that dominating pairs, which can be derived via our proposed framework, can be used in f-DP accounting due to duality of privacy profiles and tradeoff functions 9 10
Conclusion
The main purpose of this work is to provide a unified, principled framework for mechanism-specifee subsampling analysis and subsampling analysis for privacy accountants. To this end, we proposed three-step procedure based on optimal transport between conditional subsampling distributions.
Beyond recovering known guarantees for Rényí DP and dominating pairs, this procedure lets us derive novel results that were previously only available for approximate DP, such as non-standard combinations of subsampling schemes and neighboring relations, or subsampling with replacement. We then applied this procedure to the problem of analyzing group privacy under subsampling. Our experimental evaluation demonstrates that our mechanism-speciffic group privacy amplification bounds are not only tight, but can also significantly outperform tight mechanism-agnostic bounds and traditional group privacy results - even under composition. On higher level, these bounds represent a novel contribution to a larger body of work (e.g., [38 72 that demonstrates the benefit of analyzing multiple properties of differential privacy jointly instead of independently.
7
Acknowledgements
We are grateful to Georgios Kaissis for valuable discussions and feedback on generalizing our work beyond Rényi differential privacy, Yan Scholten for pointing out connections between subsampled mechanisms and hierarchical randomized smoothing, as well as Leo Schwinn and Nicholas Gao for proofreading our manuscript. This research was funded by the German Research Foundation, grant GU 1409/4-1, and the Munich Data Science Institute (MDSI) at Technical University of Munich (TUM) via the Linde/MDSI Doctoral Fellowship program and the MDSI Seed Fund.
10

---

References
[1] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pages 265-284. Springer, 2006.
[2] 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.
[3] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3 (1:2:1))10777 2014.
[4] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1336 1387,1 2015.
[5] Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, pages 157-175, 2015.
[6] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the SIGSAC conference on computer and communications security, pages 308-318, 2016.
[7] Ilya Mironov. Rényi differential privacy. In IEEE 30th computer security foundttion symposium (CSF), pages 263 275, 2017.
[8] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pages 2560-2569, 2020.
[9] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3337 2022.
[10] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pages 4782-4817, 2022.
[11] Wael Alghamdi, Juan Felipe Gómez, Shahab Asoodeh, Flávio P. Calmon, Oliver Kosut, and Lalitha Sankar. The saddle-point method in differential privacy. In International Conference on Machine Learning, 2023.
[12] Jiachen Tianhao Wang, Saced Mahloujifar, Tong Wu, Ruoxi Jia, and Prateek Mittal, A random- ized approach to tight privacy accounting. Advances in Neural Information Processing Systems, 36, 2023.
[13] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
[14] Ninghui Li, Wahbeh Qardaji, and Dong Su. On sampling, anonymization, and differential pri- vacy or, k-anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security. pages 32-33, 2012.
[15] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
[16] Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approxi- mate differential privacy. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, pages 247-264, 2018
[17] Antti Koskela and Antti Honkela. Computing differential privacy guarantees for heterogeneous compositions using fft. In International Conference on Learning Representations, 2021.
[18] Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft. In International Conference on Artificial Intelligence and Statistics, pages 3358-3366, 2021.
11

---

[19] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy, Advances in Neural Information Processing Systems, 34:1 34:11631-11646 2021.
[20] Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings on Privacy Enhancing Technologies, 2022.
[21] Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Faster privacy accounting via evolving discretization. In International Conference on Machine Learning, pages 7470-7483, 2022.
[22] Arun Ganesh. Tight group-level dp guarantees for dp-sgd with sampling via mixture of gaussians mechanisms. arXiv preprint arXiv:2401. 10294, 2024.
[23] Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptog- raphy, pages 347-450, 2017.
[24] Christopher A. Choquette- Choo,, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Privacy amplification for matrix mechanisms. In International Conference on Learning Repre- sentations, 2024.
[25] Gilles Barthe and Federico Olmedo. Beyond differential privacy: Composition theorems and relational logic for f-divergences between probabilistic programs. In Fedor V. Fomin, Rūsinš Freivalds, Marta Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming, pages 39-60, 2013.
[26] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint 160iv:1603.01 187, 2016.
[27] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658, 2016.
[28] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235, 2019.
[29] Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 10530, 2019.
[30] Yuqing Zhu and Yu- Yu-Xiang Wang. Poisson subsampled rényi differential privacy. In International Conference on Machine Learning, pages 7634-7642, 2019.
[31] Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis testing interpretations and renyi differential privacy. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108, pages 2496-2506, 2020.
[32] Shahab Asoodch, Jiachun Liao, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. A better bound gives hundred rounds: Enhanced privacy guarantees via f-divergences. In IEEE International Symposium on Information Theory (ISIT), 2020.
[33] David M. Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem differential privacy. Proceedings on Privacy Enhancing Technologies, 2019(2):455200 2019.
[34] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020(23):10-1162, 2020.
[35] Hua Wang, Sheng Gao, Huanyu Zhang, Milan Shen, and Weijie J Su. Analytical composition of differential privacy via the edgeworth accountant. arXiv preprint arXiv:2206.042366 2022.
[36] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In IEEE global conference on signal and information processing, pages 245-245 2013.
12

---

[37] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsam- pling. Journal of Privacy and Confidentiality, 10(1). 2020.
[38] Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems, 35:703-715, 2022.
[39] Cédric Villani. Couplings and changes of variables, pages 5-20. 2009. ISBN 978-3-540-71050-
[40] Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, and Prateek Jain. Node-level differentially private graph neural networks. In ICLR 2022 Workshop on PAIRM2Struct: Privacy, Accountability, Interpretability, Robustness, Reasoning on Structured Data, 2022.
[41] Morgane Ayle, Jan Schuchardt, Lukas Gosch, Daniel Zügner, and Stephan Günnemann. Training differentially private graph neural networks with random walk sampling. In Workshop Trustworthy and Socially Responsible Machine Learning, NewrIPS, 2022.
[42] Zihang Xiang, Tianhao Wang, and Di Wang. Preserving Node-level Privacy in Graph Neural Networks. In IEEE Symposium on Security and Privacy (SP), pages 4714 4732, 2024.
[43] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634-649, 2015.
[44] Jonathan Ullman. Cs7880: Rigorous approaches to data privacy. https://wwa kwwury mortheastern. http://ewtrree//m/////aaaaaa//// 2024.
pdf, 2017. Accessed May 21,
[45] Google Differential Privacy Team. Privacy loss distributions. https://rar
Privacy_Loss
wiw.oossss.sssiuuutiioosssss pdf 2024. Accessed May 22, 2024.
[46] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In IEEE 55th annual symposium on foundations of computer science, pages
2014.
[47] Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pages 2502,,502,10 2015.
[48] Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00597, 2022.
[49] Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy, pages 656-672, 2019.
[50] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in neural information processing systems, 2019.
[51] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, 2019.
[52] Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 34, pages 4593- 2020.
[53] Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference Machine Learning, 2020.
[54] Marc Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transfor- mations via randomized smoothing. Advances in Neural information processing systems, 2020.
13

---

[55] Yihan Wu, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günnemann. Completing the picture: Randomized smoothing suffers from curse of dimensionality for a large family of distributions. In International Conference on Artificial Intelligence and Statistics, 2021.
[56] Aounon Kumar and Tom Goldstein. Center smoothing: Certified robustness for networks with structured outputs. Advances in Neural Information Processing Systems, 2021.
[57] Jan Schuchardt and Stephan Günnemann. Invariance-aware randomized smoothing certificates. In Advances in Neural Information Processing Systems, 2022.
[58] Motasem Alfarra, Adel Bibi, Naeemullah Khan, Philip HS Torr, and Bernard Ghanem. De- formRS: Certifying input deformations with randomized smoothing. In Proceedings of the AAAI Conference on Artificial Intelligence, number 6, pages 6001-6009, 2022.
[59] Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized message- cassuggcinterecption smoothing: Gray-box certificates for graph neural networks. In Advances in Neural Information Processing Systems, 2022.
[60] Nikita Murarev and Alcksandr Petiushko. Certified robustness via randomized smoothing over multiplicative parameters of input transformations. In International Joint Conference Artificial Intelligence, 2022.
[61] Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input- dependent randomized smoothing. In International conference on machine learning. 2022.
[62] Mikhail Pautov, Olesya Kuznetsova, Nurislam Tursynbek, Alcksandr Petiushko, and Ivan Os- eledets. Smoothed embeddings for certified few-shot learning. Advances in Neural Information Processing Systems, 2022.
[63] Jan Schuchardt, Tom Wollschläger, Aleksandar Bojchevski, and Stephan Günnemann. Localized randomized smoothing for collective robustness certification. In International Conference on Learning Representations, 2023.
[64] Taras Rumezhak, Francisco Girbal Eiras, Philip HS Torr, and Adel Bibi. Rancer: Non-axis aligned anisotropic certification with randomized smoothing. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 4672-4680, 2023.
[65] Aman Saxena, Tom Wollschläger, Nicola Franco, Jeanette Miriam Lorenz, and Stephan Gün- nemann. Randomized smoothing-inspired quantum encoding schemes with formal robustness guarantees. In Quantum Techniques in Machine Learning, 2023.
[66] Samuel Pfrommer, Brendon G. Anderson, and Somayeh Sojoudi. Projected randomized smoothing for certified adversarial robustness. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
[67] Jan Schuchardt, Yan Scholten, and Stephan Günnemann. Provable adversarial robustness for group equivariant tasks: Graphs, point clouds, molecules, and more. In Advances in Neural Information Processing Systems, 2023.
[68] Zhuoqun Huang, Neil Marchant, Keane Lucas, Lujo Bauer, Olya Ohrimenko, and Benjamin
I. P. Rubinstein. RS-Del: Edit distance robustness certificates for sequence classifiers via randomized deletion. In Advances in Neural Information Processing Systems, NeurIPS, 2023.
[69] Yan Scholten, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Hierarchical randomized smoothing. Advances in Neural Information Processing Systems, 36, 2023.
[70] Chendi Wang, Buxin Su, Jiayuan Ye, Reza Shokri, and Weijie Su. Unified enhancement of privacy bounds for mixture mechanisms via $ff-differnntial privacy. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[71] Jason Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35, 2022.
14

---

[72] Antonious Girgis, Deepesh Data, and Suhas Diggavi. Rényi differential privacy of the sub- sampled shuffle model in distributed learning. In Advances in Neural Information Processing Systems, volume 34, pages 29181-29192, 2021.
[73] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109. 12299 2021.
[74] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference Machine Learning, pages 394-403, 2018.
[75] Ü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-2479 2019.
[76] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Advances in CrypologyEEUROCRYPT,, pages 375-403, 2019.
15

---

A Table of contents
Additional experiments
18
B.
I
Mechanism cannassts-agootticcccc and mechanism-specile bounds
18
B.2
Post-hoe and fight group privacy
25
Experimental setup
36
Evaluation of privacy guarantees
36
C.2
Computational resources
37
Assets and licenses
37
D
General setting and definitions
38
D.I
Spaces
38
D.2
Neighboring relations
38
D.3
Mechanisms and subsampling schemes
38
D.4
Differential privacy notions
39
D.5
Joint convexity
39
D.6
Couplings
39
Proof of optimal transport bounds
40
Proof of Theorem 3.3
40
Proof of Theorem 3.4
40
Proof of Proposition 3.5
Distance-compatible couplings of multiple distributions
42
Recovering known mechanism-agnostic ADP guarantees
45
Overview of Balle et al. framework]
45
G.2
Subsumption of Balle et al. framework
46
Deficiencies of mechanism- agnossic ADP bounds.
48
H
Recovering known mechanism-agnostie RDP guarantees
49
H.I
Subsampling without replacement and substitution
49
H.2 Poisson subsampling and insertion/removal
H.3 Graph subsampling without replacement and node modification.
54
[
Novel RDP guarantees
56
Hybrid neighboring relations
56
Subsampling without replacement under insertion/removal
57
1.3 Tight mechanism-speeiffc subsampling without replacement for randomized response
59
F
frmm mechanism-speccife guarantees to dominating pairs
61
Step 1: Eliminating weighted sums
61
16

---

J.2
Step 2: Resolving non non-constancy in dataset pairs
62
J.3
Step Resolving non-constancy in divergence order
63
Recovering known dominating pairs
64
K.1
Poisson subsampling and insertion/removal
64
K.2
Subsampling without replacement and insertion/removal
65
Subsampling without replacement and substitution
65
L
Novel results for dominating pairs
67
Subsampling without replacement and substitution
67
Subsampling with replacement and substitution
68
M Tight meceenism-speecffic group privacy amplification
71
M. Proof of Theorem 3.7
M.2 Instantiations
72
M.3 Tightness
74
M
Numerical evaluation
76
N
Tight mechanism-agnostic group privacy amplification
78
N.I
ADP guarantee
78
N.2 Tightness of ADP guarantee
79
N.3 Relation to tight mechanism-speciifee bound
80
N.4 RDP guarantee
81
N.5
Asymptotic RDP guarantees
0
Worst-case mixture components
83
0.1
Gaussian and Laplacian mixtures
83
0.2
Reduction of the divergence to univariate integral
0.3
Randomized Response Proofs
92
Towards epoch-level subsampling analysis
97
P.
Problem setting
97
P2
Optimal transport without conditioning
97
P3
Optimal transport with conditioning
98
P.4
Experimental Evaluation
99
Broader impact
100
17

---

B Additional experiments
B.1 Mechanism-agnostic and meehanism--ppecine bounds
B.1.1 Randomized response and RDP
In Fig. 7 we repeat the experiment from Fig. with other ratios of batch and dataset sizes. That is, we compare our tight mechanism-sper speccifi RDP guarantee from Theorem I.3 the best known mechanism -agnostic bound from (28 to illustrate that pecchanism-agnoste bounds may loose privacy by bounding mixture divergences terms component divergences even outside the group privacy setting. The tight guarantee eliminates constant factors and thus achieves much smaller for wide range of a E (1, 10*), especially for small ratios.
q/ N 0.01
9 N NN 0.1
10-1
Agnostic
10-2
Specific
RDP p(a))
RDP p(a)
10-1
0
10-3
0.9
10
10
0.6
101
10a
10a
104
10a
10a
10a
10a
RDP
RDP
N 0.2
N = 0.5
109
10
RDP p(a)
RDP p(a))
10-1
10
10-2
10
10a
103
101
10a
103
10a
RDP a
RDP a
Figure 7: Randomized response under subsampling without replacement, with varying true response probability 9 and batch-to-datase ratio N. Theorem 1.3 significantly improves upon the bascline for a wide range of a.
B.1.2 Group privacy and ADP
In Figs. and we repeat the experiment from Fig. for other subsampling rates r. standard deviations and also with Laplace mechanisms. That is, compare our tight mechanism-specific group privacy guarantees to the tight mechanism-agnostic bounds derived via the framework of [15] The results demonstrate that mechanism-spene specific tightness is stronger property that result in better privacy guarantees although the difference in significantly more pronounced for Laplace mechanisms and/or larger group sizes.
In Fig. 10 we repeat the experiment with randomized response mechanisms. Here, both approaches yield identical guarantees. This verifies that randomized reseponse is indeed the worst-case mecha- nisms for which the mechanism-agnoose bound is optimal (see [[5] and Appendix N.22).
18

---

Gaussian mechanism
0.1,0=1
0.1,
0.3
Agnostic
Group size
0.4
Specific
16
ADP 8(e)
ADP 5(e)
0.2
0.2
2
0.1
0.0
10
0
4
5
ADP
ADP
y= 0.1, 0 5
1 0.2, a 2
0.10
ADP (())
ADP ((e)
0.4
0.05
0.2
0.00
0.0
0.0
0.5
1.0
1.5
2.0
0
2
5
6
ADP
0,2, 5
0.5, =
1.00
0.2
ADP d(E)
ADP d(E)
0.75
0.50
0.1
0.25
0.0
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
4
8
10
ADP
ADP
== 0.5, 0 2
y 0.5, 0 5
0.8
ADP 8(e)
ADP 8(8)
0.4
0.6
0.4
0.2
0.2
0.0
0.0
10
0
5
6
ADP E
ADP g
Figure 8: Gaussian mechanisms under Poisson subsampling, with varying standard deviation a, subsampling rate and group size. The tight mechanism-specinn guarantees are stronger than the tight mechanism-agnen agnossic bounds, especially for larger group sizes and smaller subsampling rates.
19

---

Laplace mechanism
0.1, = 0.5
-.1,0
0.6
Agnostic
Group size
0.4
ADP d(e)
Specific
16
ADP ((e)
0.4
0.3
0.2
0.2
0.1
0.0
0.0
2
4
10
0
4
ADP
E
ADP
0.1, À =
0.2,
0.5
0.3
0.8
ADP d(e)
0.2
ADP d(e)
0.6
0.4
0.1
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0
6
ADP
ADP
r 0.2, À = 2
0.5, = 0.5
1.00
ADP 8(e)
0.4
ADP 8(c)
0.75
0.50
0.2
0.25
0.0
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0
2
4
8
10
ADP E
ADP E
0.5,
0.5, =
1.00
0.8
0.75
ADP d(e)
ADP 5(e)
0.6
0.50
0.4
0.25
0.00
0.0
ADP
ADP
Figure 9: Laplace mechanisms under Poisson subsampling, with varying scale X, subsampling rate r, and group size. The tight mechanism-speeific guarantees are stronger than the tight mechanism- agnostic bounds, especially for larger group sizes.
20

---

Randomized response mechanism
= 0.1, 0 = 0.7
7 0.1, = 0.8
0.3
Agnostic Specific
Group size
16
0.4
ADP d(e)
ADP ADP
0.2
0.2
0.1
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
ADP
E
ADP E
0.1,0 2
0.2, 0.7
0.4
0.6
ADP d(e)
ADP 5(e)
0.3
0.4
0.2
0.2
0.1
0.0
0.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
ADP
ADP
T= 0.2, = 0.8
T 0.5, 0 = 0.7
0.6
0.4
ADP 8(e)
0.4
ADP 8(e)
0.2
0.2
0.1
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
ADP g
ADP E
0.5, 0 0.8
r 0.5, 0.9
0.6
ADP a(e) ((e)
0.4
ADP 5(e)
0.6
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
ADP E
ADP
Figure 10: Randomized response under Poisson subsampling, with varying true response probability subsampling rate r, and group size. Randomized response the worst-case mechanism for which the mechanism-agnostic guarantee is optimal, so both ansätze yield identical results.
21

---

B.1.3 Group privacy and RDP
In Fig. 11 we repeat our comparison of mechanism-agnossic (Theorem N.5 and tight mechanism- specific group privacy amplification (Theorem (.8) with RDP instead ADP. We observe that the tight guarantee delays the phase transition from a high- to low-privacy regime that was already observed in (30]. other words, we have small for larger a, which beneficial for conversion to ADP after composition (see conversion formulae in
= 0.1,0=1
== 0.001, a =
10$
Agnostic Specific
10a
RDP p(a)
10a
Group size
RDP p(a)
10a
10
10
10
10 4
1.1 X 10
2 10" RDP a
10
1.1 109
4 x 100
10
RDP &
y= 0.1,
y= 0.001, 0 2
104
104
RDP p(0)
102
RDP p(a)
10a
100
10-2
10-5
10
x 109
100
101
10a
RDP
RDP
== 0.001, =
T= 0.001, 0 =
103
10
RDP ((a)
RDP p(a)
109
10a
10-3
10-1
10-6
10-3
101
102
103
101
10a
103
10a
RDP &
RDP a
Figure 11: Gaussian mechanisms under Poisson subsampling, with varying standard deviation a. subsampling rate and group size. The mechanism-specinn guarantee delays the phase transition from high to low privacy.
22

---

B.1.4 Benefit of conditioning
Next, we demonstrate the benefit of coupling multiple conditional distributions over coupling just two subsampling distributions deriving amplification guarantees. Specifically, we evaluate Proposi- tion Hi7 which can be derived via Theorem 3.3 i.e., optimal transport without conditioning. Note that, unlike with the guarantees of Wang et al. 128], this bound depends on both the dataset size and the batch size, not just their ratio. We make the following observations: For large Proposition H.7 converges to the baseline. Furthermore, this approach never outperforms the baseline for group size 1. Neither does it outperform the baseline for ratios / L E {0.01, 0.001}. But, for q L 0.1, there is a sweet spot of alphas between 10 and 10a in which it offers stronger guarantees. This further reinforces our claim that there is benefit treating group privacy and amplification jointly, Furthermore, we observe that the case of 1, Proposition H.7 outperforms the baseline for large alpha, since it can capture that cannot possibly include more than one substituted element in singleton batch.
Overall, we can conclude that there is a benefit to jointly analyzing group privacy and subsampling this manner, but that optimal transport without conditioning not sufficient for tightly analyzing such complicated scenarios.
N = 10 10
N = 10 ; 102
104
No conditioning
No conditioning
RDP p(a)
102
Post-hoc
RDP p(()
10a
Post-hoe
Group size
Group size
10
10-2
2
2
10-2
10-5
10a
103
101
102
10a
RDP a
RDP a
N = 10 == 103
= -0 10a
104
No conditioning
No conditioning
RDP p(a))
102
Post-hoc
RDP p(a)
10a
Post-hne
Group size
Group size
10"
10
2
2
10-2
10-5
104
102
103
104
101
10a
10a
104
RDP &
RDP &
N 10 : = 102
10
.0 = 10
104
No conditioning
conditioning
102
Post-hoe
10
Post-hoe
RDP p())
RDP p(a)
Group size
Group size
10a
10-2
4
10-2
10-5
101
102
103
104
101
102
103
104
RDP &
RDP &
Figure 12: Proposition H.7 derived from Theorem 3.3 applied Gaussian mechanism (a 5.0) under sampling without replacement for varying dataset size N, batch size g, and group size. Optimal transport without conditioning does not always improve upon the baseline.
23

---

B.1.5 Subsampling with replacement
The previous experiments demonstrated that mechanism-speeific analysis can improve upon non-tight mechanism-agee -agnostic and in the group privacy setting tight talaaniis--gnostte analysis. In the fol- lowing, we demonstrate that mechanism-speecfic bounds can improve upon tight mechanism-agnostic bounds even for single-element relations, i.e., group size 1. To this end, we consider subsampling with replacement for Gaussian mechanisms under the substitution relation, comparing Theorem L.5 Theorem 10 Balle al. [T].
Fig. 13 shows the resultant privacy profiles for standard deviation o = L. dataset size N = 100, and batch size q 8. For 2 2, the mechanism-speeifft bound more than an order of magnitude smaller. Intuitively, this gap can be explained similarly to the gap in the group privacy setting: The single substituted element can sampled 0, 1, 2, up to g times, with each case causing different levels of privacy leakage. Mechanism-agnostie bounds rely on binary partitioning of the event space, which is not sufficient for capturing this granular behavior (recall Fig. 2
Note that due to the relaxations of distance constraints we performed in deriving Theorem L.5 the mechanism-speciffi bound not tight. tight bound might lead experiments further reinforces that there is qualitative difference between mechanism-specifie and mechanism-agnosti tightness.
larger gap. Thus, this
10-3
10-5
ADP d(e)
10 10-7
Agnostic
10-9-
Specific
100
10a
ADP
Figure 13: Gaussian mechanism (a under sampling with replacement for single-element substitutions, dataset size N = 100, and batch size q = 8. Using the mechanism-specific bound results in stronger privacy guarantees.
24

---

B.2 Post-hoc and tight group privacy
B.2.1 Single-iteration ADP
In Figs. 13 we repeat the experiment from Fig. 5 for other subsampling rates r, standard deviations d, and mechanisms. That is, we compare our tight mechanism-spenn speciffc guarantees to post-hoc use of the group privacy property. For all mechanisms, the tight bachannsm--speciffe analysis yields stronger privacy guarantees than the baseline particularly for large group sizes. However, we interestingly see that with increasing base mechanisms noise level and decreasing subsampling rate, the post-hoc bound converges towards the tight bound.
25

---

Gaussian mechanism
0.1,0=1
0.1, =
0.6
Post-hoc
Group size
0.3
Specific
16
ADP 8(e)
0.4
ADP 8(E)
0.2
0.2
0.1
0.0
10
0
4
5
ADP
ADP
y= 0.1, a 5
1 0.2, 0
1.00
ADP 8())
ADP d(e)
0.75
0.50
0.05
0.25
0.00
0.00
0.0
0.5
1.0
1,5
2.0
4
8
10
ADP
0,2, 5
0.5,
1.00
ADP d(E)
0.2
ADP d(E)
0.75
0.50
0.1
0.25
0.0
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
4
8
10
ADP
ADP
y= 0.5, 0 2
r 0.5, 0 5
1.00
0.6
ADP 8(8)
ADP 8(E)
0.4
0.50
0.2
0.00
0.0
0
10
0
5
6
ADP E
ADP g
Figure 14: Gaussian mechanisms under Poisson subsampling, with varying standard deviation a, subsampling rate r. and group size. Analyzing group privacy and subsampling jointly instead of in post-hoc manner offers stronger guarantees.
26

---

Laplace mechanism
0.1, = 0.5
T= 011,1
1.00
Post-hoc
Group size
0.6
0.75
Specific
16
ADP d(e)
ADP8(e)
0.4
0.50
0.2
0.25
0.00
0.0
0
4
10
0
1
3
4
0.1, À 2
0.2,
0.5
1.00
0.3
ADP ADP d(e)
ADP d(e)
0.75
0.2
0.50
0.1
0.25
0.0
0.00
0.0
0.5
1.0
1.5
2.0
ADP
ADP
T 0.2, À = 2
0.5, = 0.5
1.00
0.6
ADP 8(e)
ADP 5(c)
0.75
0.4
0.50
0.2
0.25
0.0
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0
2
4
8
10
ADP g
ADP E
0.5,
r 0.5, =
1.00
1.00
ADP (e))
d(e)
0.75
ADP 5(e)
0.75
0.50
0.50
0.25
0.25
0.00
0.00
ADP
ADP
Figure 15: Laplace mechanisms under Poisson subsampling, with varying scale X, subsampling rate r, and group size. Analyzing group privacy and subsampling jointly instead post-hoc manner offers stronger guarantees.
27

---

Randomized response mechanism
0.1, 0 = 0.7
0.1, = 0.8
1.00
0.6
Post-hoc
Group size
ADP d(e)
Specific
16
ADP 8()) (()
0.75
0.4
0.50
4
0.2
2
0.25
0.0
0.00
0.0
0.5
1.0
1.5
2.0
1
2
3
4
5
6
ADP 8
ADP
0.1,0 2
0.2, 0 0.7
1.00
ADP d(e)
0.75
ADP d(e)
0.75
0.50
0.25
0.25
0.00
0.00
2
0.0
0.5
1.5
2.0
ADP
ADP
0.2,0 = 0.8
T 0.5, 0 = 0.7
1.00
1.00
ADP d())
ADP d(c)
0.75
0.50
0.50
0.25
0.25
0.00
0.00
0
1
2
3
0
1
2
3
4
5
6
ADP E
ADP
0.5, 0 0.8
r 0.5, 0.9
1.00
1.00
ADP ADP ((e)
0.75
ADP5(e) ((e)
0.75
0.50
0.50
0.25
0.25
0.00
0.00
ADP
ADP
Figure 16: Randomized response mechanisms under Poisson subsampling, with varying true response probability subsampling rate r, and group size. Analyzing group privacy and subsampling jointly instead of in a post-hoc manner offers stronger guarantees.
28

---

B.2.2 Single-iteration RDP
In Fig. 17 we repeat our comparison of tight mechanism-speciife group privacy amplification and post-hoc group privacy for RDP instead of ADP. The tight analysis yields stronger guarantees and delays the phase transition from high- to a low-privacy regime. However, as with ADP, the post-hoc bound can be a good upper bound for small subsampling rates and very private base mechanisms.
0.1,a=1
0.001, a
10
Post-hoc Specific
10a
RDP p(ax)
10
Group size
RDP p(o)
10a
10
10-1
10
10
1.1 X 109
x 10"
x 10
1.1 10"
x 10
10
RDP
RDP
r= 0.1, =
y= 0.001, 0 =
104
104
RDP p(a)
102
RDP p(a))
10
10-2
10
10-5
10-2
1.1 x 10"
x 10"
10
10
RDP &
RDP &
y 0.001,
0.001, 0
103
103
RDP p(a))
RDP p(a)
109
10a
10-3
10-1
10-6
10-3
101
102
103
104
104
102
103
10
RDP
RDP
Figure 17: Gaussian mechanisms under Poisson subsampling, with varying standard deviation subsampling rate r, and group size. Analyzing group privacy and subsampling jointly instead of in post-hoc manner delays the phase transition from high to low privacy. For very private base mechanisms and small subsampling rates, the baseline nevertheless good upper bound.
29

---

B.2.3 PLD Accounting
In Figs. 18 21 we repeat our comparison of tight mechanism-specific and post-hoe group privacy amplification guarantees under composition from. We consider different combinations subsampling rate standard deviation privacy parameter privacy scenarios, where the mechanism-specific and post-hoc analysis yield similar results on single-iteration level, the sepcffcs guarantees significantly stronger under composition. Specifically, the post-hoc analysis diverges to much larger after some number of iterations. In settings with moderate privacy (c.g. 1) or large group sizes (c.g. 16), the bascline diverges after less than 100 iterations.
well as Laplace mechanisms. Even in high
Gaussian mechanism (r = 0.001)
0.5, a
8 0.5, 0 5
10-2
Group size
10-4
ADP K(c)
10-6 -5
16
ADP 8(s)
10-10
10-8
10-16
Post-hoc Specific
10-11
10-22
250
500
750
1000
250
500
750
1000
Iteration
Iteration
L, =1
L, 5
10-1
10
ADP ((E)
10-5
ADP 8(E)
10 10-10 10
10-9
10-16
10-13
10-22
250
500
750
1000
250
500
750
1000
Iteration
Iteration
8 2,0=1 =1
8 = 2,0 5
10
10-1
ADP 8(E)
10-7 7
ADP 8(E)
10 10-10
10 10-12
10 16
10
10-22
250
500
750
1000
250
500
750
1000
Iteration
Iteration
Figure 18: Self-composed Gaussian mechanisms under Poisson subsampling with subsampling rate r 0.001 and varying standard deviation privacy parameter and group size. For sufficiently large group sizes, the post-hoc analysis divergence from the tight mechanism -echafism-specific guarantee within less than 1000 iterations.
30

---

Gaussian mechanism (r = 0.01)
0.5,0.
8 0.5, a =
10-1
Group size
10
ADP ((c)
16
ADP ADP 8(c)
10
10-3
10-15
10-5
Post-hoc Specific
10-21
200
400
600
800
1000
250
500
750
1000
Iteration
Iteration
= 1,011
==
10-1
10-3
ADP 8(E)
10-3
ADP 8(E)
10
10-5
10-15
10-7
10-21
200
400
600
800
1000
250
500
750
1000
Iteration
Iteration
8 = 2,0=1 =1
8 = 2, 5
10-1
10
ADP 8(=)
10-4
ADP ((=)
10
10
10
10
10-21
250
500
750
1000
250
500
750
1000
Iteration
Iteration
Figure 19: Self-composed Gaussian mechanisms under Poisson subsampling with subsampling rate r = 0.01 and varying standard deviation a, privacy parameter and group size. For sufficiently large group sizes, the post-hoc analysis divergence from the tight mechanism-specifie guarantee within less than 1000 iterations.
31

---

Laplace mechanism (r 0.001)
0.5, 0
8 0.5, = 5
10-2
10
Group size
ADP A(=)
10-7
16
ADP ADP ((E)
10
10 10-11
10 10
Post-hoc Specific
10-15
10-14 14
250
500
750
1000
250
500
750
1000
Iteration
Iteration
L,A=1
8 5
10-2
10
ADP A(E)
ADP A(E)
10
10-7
10-10
10-11
10-14
10
250
500
750
1000
250
500
750
1000
Iteration
Iteration
8 2, X =1
6 = 2, X =5
10-2
10-3
ADP (())
ADP 8(e)
10-6
10-7
10-10
10
10-15
10-14
0
250
500
750
1000
250
500
750
1000
Iteration
Iteration
Figure 20: Self-composed Laplace mechanisms under Poisson subsampling with subsampling rate = 0.001 and varying scale X, privacy parameter and group size. For sufficiently large group sizes, the post-hoe analysis divergence from the tight mechanism-specife guarantee within less than 1000 iterations.
32

---

Laplace mechanism (r 0.01)
e 0.5, A
=
8 0.5, = 5
10-3
Group size
10
ADP A(E)
10
16
ADP ADP f(E)
10
10-11
10-10
Post-hoc Specific
10-15
10-14
250
500
750
1000
250
500
750
1000
Iteration
Iteration
1, =1
=
10-2
10
ADP A(E)
ADP ADP A(E)
10-6
10-7
10-11
10-10 10
10-15
10-14
250
500
750
1000
250
500
750
1000
Iteration
Iteration
8 2, À =
6 = 2, =5
10
10-3
ADP (())
ADP 8(E)
10
10
10 11
10-10 10
10-15
10-14
0
250
500
750
1000
250
500
750
1000
Iteration
Iteration
Figure 21: Self-composed Laplace mechanisms under Poisson subsampling with subsampling rate = 0.001 and varying scale X, privacy parameter and group size. For sufficiently large group sizes, the post-hoe analysis divergence from the tight mechanism-specifee guarantee within less than 1000 iterations.
33

---

B.2.4 RDP accounting
Finally, compare tight group privacy amplification the post-hoc approach for RDP accounting. We begin with the Gaussian mechanism and subsampling rate 0.001 in Fig. [2 Our bound offers stronger group privacy guarantees for 1.0. but both results almost identical for very private base mechanisms with a = 5.0. We suspect that this is because the phase transition from high to low privacy (recall Fig. 17p. which the tight guarantee delays, gets shifted to very high a regions that are not useful for conversion to (e, 6)-DP.
also consistent with earlier results: For moderate subsampling rates = 0.1, our guarantees are stronger, particularly for group size 8 and large numbers of iterations. But, when decreasing the subsampling rate 0.001, both methods are almost identical. Nevertheless, group privacy amplification can demonstrably improve upon direct combination of independently derived group privacy and amplification guarantees.
Our observations for randomized response mechanisms (see Fig.
Note that these observations are mostly of theoretic interest. In practice, one would use PLD accounting, which tightly characterizes the composed mechanism's 's privacy Icakage, instead of the [8 looser RDP accounting. As shown in Figs. to the tight mechanisms mechamisms-specffe specific analysis drastically outperforms the post-hoc analysis for PLD accounting.
Gaussian mechanism
0.001,
0.001,
Post-hoc
Specific
109
Group size
10
ADP E
ADP
10
10
10a
10a
10a
10
104
10a
10
10a
10a
10a
10a
10a
Iteration t
Iteration t
Figure 22: Self-composed Gaussian mechanisms under Poisson subsampling with privacy parameter 8 10-6 subsampling rate 0.001, and varying standard deviation a and group size. The tight mechanism-spede analysis yields better privacy guarantees than the post-hoc baseline, except for large a where the baseline good upper bound.
Randomized response mechanism
0.1,0 = 0.6
0.001, 0.6
104
Post-hoc
Specific
10"
Group size
ADP
10a
ADP
10
10a
2
10
10-3
10a
10
10a
3
104
10a
10a
10a
10a
10
10
Iteration t
Iteration t
Figure 23: Self-composed randomized response mechanisms under Poisson subsampling with privacy parameter 5 10 true response probability 0 0.6, and varying subsampling rate and group size. The tight mechanism-speciffe analysis yields better privacy guarantees than the post-hoc baseline, except for small where the baseline is good upper bound.
34

---

B.2.5 Model utility
The previous results demonstrated that handling group privacy via tight mechanism-spent specciiiissssicccccoe analysis allows for a larger number of compositions, i.e., iterations a given privacy budget than post-hoc use of the group privacy property. In the following, we demonstrate that this increased number of iterations can fact result increased utility for group-private machine learning models.
We train a convolutional neural network (2 convolution layers with kernel sizes 3 and 32 64 channels. followed by two linear layers with hidden dimension 128) for image classification on MNIST (55000 training. 5000 validation, 10000 test samples). We set the gradient clipping norm of DP-SGD 6 to
10 the Gaussian noise standard deviation 0.6 C, and the subsampling rate to 64 / 55000. The optimizer is ADAM with learning rate 1 3. If the privacy budget is used up earlier, training terminated after epochs, with [55000] 64] iterations per epoch.
Even with a large privacy budget of needs to terminate after less than 200 iterations. With the mechanism-specifie analysis, á does even exceed le 7 after 8 epochs, i.e., the model could potentially be trained for even more iterations. The resultant validation accuracy's are 79.6% and 91.2%, respectively. This showcases the superior privacy-utility trade-off that can be achieved by analyzing subsampling and group privacy jointly.
and 5 = 1e - 5, training with the post-hoc privacy analysis
1.0
ADP 8(e = 8)
10-4
Val. accuracy
0.8
10
Post-hoc
0.4
10-10 10
Specific Budget
Post-hoc
0.2
Specific
0.0
0
2000
4000
6000
Iteration
Epoch
(a) Privacy
(b) Utility
Figure 24: Differentially private training of 2-layer convolutional network on MNIST with PLD accounting for group size Our tight mechanism-speeiff analysis allows us to train for significantly more epochs or to terminate training after 8 epochs with less privacy leakage and higher accuracy.
35

---

C Experimental setup
C.1 Evaluation of privacy guarantees
all experiments we assume that all mechanisms have underlying sensitivity w.r.t. &o (randomized response), & (Laplace), or & (Gaussian) output norms. We thus only specify noise parameters or X, rather than the ratio of a or X and the sensitivities.
C.1.1 Single-iteration approximate differential privacy
Privacy parameters. We evaluate all guarantees for 121 equidistant values of in [0, 4] and 121 logspace-equidistant values 10-3 -3, _10 i..., {10a x E {-3, -3- + 4 T20...., 1,]]. We clip values of ((s) that are larger than 1 to [o, 1]. For our baselines, we enforce that ö(e) is monotonically decreasing by taking a running minimum from larger to smaller (this may improve but never worsens the baselines).
Mechanism-agnostic group privacy baseline. our mechanism-agnootiic group privacy baselines, we use Proposition N.1 We take the maximum over the two cases (K+ = K, K 0) and (K+ 0, K_ K). where is the group size. For Gaussian and Laplace mechanisms, we evaluate group privacy profiles (e) by determining (()) for the same mechanism with sensitivity k. For randomized response, we let d; = 81. This is referred to to as "white-box" group privacy in [I5). We evaluate this baseline analytically.
Post-hoc group privacy baseline. For our post-hoc baseline, we combine the tight Poisson sub- sampling guarantee for insertion/removal from [I5] with the group privacy property of approximate differential privacy (see Appendix (C.1.4 below). We evaluate this baseline analytically.
Tight mcchanism-speeiffic group privacy. In all ADP figures "specific" refers to our tight group privacy guarantees for Gaussian (Theorem (.8). Laplace (Theorem M.2), randomized response mechanisms (Theorem M.3). We take the maximum over all K+, K_ E Nç with K + K_ K, where K is the group size. To evaluate the bounds for Gaussian and Laplace mechanisms, we pessimistically invert the privacy loss of dominating pairs P, Q via binary search (see details in Appendix M.4). as implemented in the dp_ ap_accounting library 45). We set the precision to 10 i.e. find the global optimum over multiples of 10-6. The bound for the randomized response mechanism is evaluated analytically in (1).
C.1.2 Single-iteration Rényi differential privacy
Privacy parameters. We evaluate all guarantees for a E (2. 1000), as well as 121 logspace- equidistant values in [0, 104] rounded to the next smallest integer (without 1), and 121 logspace- equidistance values in (1, 10). For our baselines, we enforce that p(ax) is monotonically increasing by taking running minimum from smaller larger (this may improve but never worsens the baselines).
Mechanism-agnostic group privacy baseline. As our mechanism-agnooticc group privacy baselines, we use Proposition N.1 We take the maximum over the two cases (K_ K, K_ = 0) and (K+ 0, K_ K). where K is the group size. For integer a,
the binomial expansion
in Eq. (33) (without factor 2). For Gaussian and Laplace mechanisms, we evaluate group privacy
profiles (a) by determining {(a) for the same mechanism with sensitivity k. For randomized response, we let ÇE Ç1. For continuous a, we apply tanb-sinh-quadrature with 50 digits of decimal
precision to Eq. 33
Post-hoc group privacy baseline. For our post-hoc basclines, we combine either tight Poisson subsampling guarantee for insertion/removal from (30) or the subsampling without replacement guarantee for insertion/removal from (28) with the group privacy property of approximate differential privacy (see Appendix C.I.4 beloow.. For Poisson subsampling and integer a, we use the binomial expansion from (30 (without factor 2). For continuous a, we apply hunb-sinh-quadratum with 50 digits of decimal precision. For subsampling without replacement,
the improved self- consistency bound (Theorem 27 from (28). which we evaluate via tanh-sinh -uadr-uuarrature with 50 digits of decimal precision due to the intractability of the nested binomial expansions for larger a.
Tight mechanism-specific group privacy. RDP figures "specific" refers to our tight group privacy guarantees for Gaussian (Theorem 3.8 Laplace (Theorem M.2), randomized response
36

---

mechanisms (Theorem M.3 We take the maximum over all K. No with K + K_ = K, where K is the group size. To evaluate the bounds for Gaussian and Laplace mechanisms, we use tanb-sinh-quadratue with 50 digits of decimal precision (see discussion in Appendix M.4).. The bound for the randomized response mechanism is evaluated analytically in O(1).
C.1.3 Privacy accounting
RDP accounting. For RDP accounting, we simply evaluate the single-iteration guarantees as described in Appendix C.1.2 We then multiply the p(a) with the number of iterations, apply the improved EDP-to-ADER formula from [31,, and take the minimum over all obtained values. For the post-hoc baseline, we apply the group privacy property before composition (which is equivalent to applying after composition, due to additivity of composition).
PLD accounting. For PLD accounting with dominating pairs. we use the implementation of the dp_ aocaccutniing library [45]. To quantize the privacy loss distribution, we use "connect the dots" [20] with pessimistic estimates, discretization interval size of 10 and truncation of of the probability mass. During composition, we truncate 10-15 of the tail mass. For the post-hoc baseline, we apply the group privacy property after composition.
C.1.4 Post-hoc group privacy
ADP. For RDP, we use the following result from the proof of Lemma 2.2 in (23, which provides tigher guarantees than Lemma 2.2 itself: Let M be (e, 6)DP under neighboring relation =x. Then,
M is (e', O'D with g 8. K and 8' Σx= Are
RDP. For RDP, than the upper bound in their Proposition 2. Let D& be log(Aa) (a - 1). This Da fulfills the following triangle inequality:
the following result from Corollary 4 of 77. which provides tighter guarantees
Da s a a-
(pllr) + a- D2a (rll)(
We recursively apply this bound loga (K) times when evaluating the group privacy of our baselines for groups of size K.
C.2 Computational resources
We conduct all experiments on set of Xeon E5-2630 v4 CPUs @ GHz.
We use one worker and job per subsampling theorem, base mechanism noise level, subsampling rate, and combination of group privacy parameters K_, K+. Per job, we allocate 2 CPU cores, 4 GB and 10 minutes of runtime (in practice, most jobs were completed in few seconds). In total, 13060 such jobs for ADP, 9731 for RDP, and 984 for RDP accounting. We estimate that over the course of the full research project twice many jobs executed.
C.3 Assets and licenses
To perform high-precision quadrature RDP guarantees, we use the tanh-sinh quadrature im- plementation from the mpmath library (version 1.3.0.), which is available under the BSD-3-Clause com
license at /attps://githie http://ommmmm/mmmmaaaaaaaaaa.ee mmpmthh
For PLD accounting and evaluation of ADP guarantees via bisection, we use and extend the dp_accco appoacunnnin library [45] (commit 1o0.:588004e0077774441000006666.
which is available under Apache-2.0 license at
differential-privaccy
For conversion from RDP to ADP guarantees, we use the get__privcc__pentt method implemented (version 1.4.1), which is available under Apache-2.0 license at https
in the Opacus library 73
//github. //ggihuu.cco//ytoorr. wwwppttooocccccccccccccooooooctt opacus
An implementation will be made available at http:://e..ctttmm..ce/m////ppppp
37

---

D General setting and definitions
In the following, we generalize some of the definitions introduced in Sections 2 and to their meesure-theoretic equivalents. The purpose of this generalization is to handle both continuous and discrete spaces, base mechanisms, and subsampling schemes, without having make constant case distinctions.
We these more general definitions throughout the remaining appendix sections. The theoretic results presented in Section follow as special cases.
D.1 Spaces
Unlike before, we assume that dataset space X is some arbitrary space, whose elements do not have to be sets. Instead, datasets z E X can also be graphs, sequences or any other data collection. We further assume that the batch space is a measurable space (Y, 3") with o-algebra Y For example, Y can be composed of subsets, subgraphs, or subsequences. We also assume the output space to measurable space (Z, 2). Finally, we assume the existence of some measure À the output space, such as the Lebesgue measure for continuous or the counting measure # for discrete
Whenever we consider Poisson subsampling, we assume that X S P(A), Y = {v E y/ = PYY), where Å is some discrete, finite set and P(-) is the powerset.
Whenever we consider subsampling without replacement with batch size q, we assume that C {ar E P(A) |a|| g) Y = {y C E X, |y| 9), y P(Y), where A. is some discrete, finite set and (-)) is the powerset.
D.2 Neighboring relations
For set-valued datasets and batches, the insertion/removal relation and the substitution relation are formally defined as follows:
Definition D.1. Sets F, x E X are related by the insertion/removal relation (x: = x²) if a + x' and there is some a such that x' = x U {a} or x' = x \ (a).
Definition D.2. Sets x, x' E X are related by the substitution relation (z = x²) if there some E x and a' & such that x' = r {a} U {a'}.
In our general setting, also allow non-symmetric neighboring relations.
D.3 Mechanisms and subsampling schemes
As before, the term "mechanism" refers to random functions that map to the output space (Z, 2). Formally, a random function M X Z is family of random variables indexed by elements of X. Definition D.3. A random function M : -> Z is a function M X x Ω + Z, where (2,FF P) is some probability space and all M (z: -) : w + M (z,w) measurable.
We write PM. 2 - [0, 1] for the distribution of random variable M(x). We further assume that each PM, is absolutely continuous w.r.t. the aforementioned output measure X, i.e., Va E X Pas, X, and write m2 I + RR, for the corresponding Radon-Nikodyy derivative dPM., / dA. For example, when the output space (Z, Z) is continuous and is the Lebesgue measure, then m. is the density.
Similarly, we define our base mechanism to random function : - Z and write PB, Z [0, for the distribution of base mechanism outputs given batch y E Y. We assume that each PB, absolutely continuous
output measure À and write by Z - R2 for dPp, / /dx
Finally, we define our subsampling scheme to be a random function S X - and write Ps. y [0, for the distribution of batches given dataset E X. We generally do not require Ps. to be absolutely continuous w.r.t. some other measure. When Ps. is absolutely continuous w.r.. counting measure #. write s Y + [0. for the corresponding probability mass function dPss, d#
In particular, Poisson subsampling and subsampling without replacement are defined as follows: Definition D.4. Poisson subsampling with rate E [0. 1] has probability mass function s,(v) plol(1 (1 r) la -Ivl for batches C x.
38

---

Definition D.5. Subsampling without replacement with batch size has probability mass function (v) = ( for batches y C x: with ly| = 4-
As before, our goal is to provide privacy guarantees for subsampled mechanisms M = Bo S. Similar to our discussion in Section its distribution PAs, given a dataset x E X is mixture with
mz(=)) / (2) dPs,
There is one component per batch y from batch space Y, and the weights depend subsampling distribution Ps..
D.4 Differential privacy notions
Since we no longer require the output space to be continuous, we also need to generalize the definitions of approximate differential privacy, Rényi differential privacy, dominating pairs, and the divergences underlying their definition. For this, recall that À is our assumed measure output space (Z, Z).
Definition D.6. For 2 0, mechanism M X - Z is (s, 6)-DP under relation mi if V' mx Hesp(e) (myl mmr) S and Hesp(e) (ma mm²) I 8 with hockey stick divergence
/ max (z) /
Ho (mz
a, 0} my (z) d)(2).
(6)
Definition D.7. A pair of distributions (P, Q) with = dPp dd and dQ / yd is a dominating pair for mechanism M under neighboring relation =x, if H (m (mm') H (pl1g) for all =x x! and all a 2 0.
Definition D.8. For 2 1, a mechanism M X F. (a, p) -DDP under neighboring relation mx if V/ mx x': logg(A, (A [mx]|mm))))) (a 1) S and log( Aa (m m,)) / (a - 1) S with
Aa(m=]lma)) = (z) mz (2) 1=) dz.
JRD
Importantly, note that A, is not the Rényi divergence as used in 77. It is its ath moment, i.e., a scaled and exponentiated Rényi divergence. This is why logarithm and quotient appears in Definition D.8 We use this definition, so that we can simultancously discuss ADP and RDP without notational clutter.
D.5 Joint convexity
The joint convexity of V. (Ha, A.) is not limited densitites, but also applies to other non- negative Radon- derivatives of probability distributions [37,
Lemma D.9. Consider arbitrary Radon-Nikodym derivatives , (1) (2) (2)
,
R2 and
weight w E [0, 1]. Then,
Va (w ( + +(1 w)st (wf + (1 - --) I w. VVaali
(1)))) + (1 w) v (f )
D.6 Couplings
As with the discrete, finite-support subsampling distributions we considered in Section 3 the key tool we use for analyzing amplification are couplings. However, we no longer assume the subsampling scheme to always have a mass function. We thus use more general notion of couplings between distributions instead of couplings between mass functions:
Definition D.10. A coupling between probability measures Pi..... PN on space (Y,)) is a proba- bility measure on product space (Y,))* where the nth marginal Pa. i.e., T o क. = P, with projection म. ( Vn-
Here, is the composition operator and ग. is the preimage (not necessarily the inverse) of the projection function. As before, when considering a coupling between two distributions P1, Pz. the value [(T, R) specifies for all events T, R y how much probability should be transported from (T(T") to (2) to transform P1 into Pz.
aassumng that (v, 2) + PB, (2) is valid Markov kernel
39

---

E
Proof of optimal transport bounds
E.1 Proof of Theorem 3.3
In the following, we show a more general statement for the general setting introduced Appendix [ Theorem (.n follows in the special case where batch space Y is finite and discrete, and the subsampling distribution has probability mass function Sg.
Theorem E.1. Consider a subsampled mechanism M Bo S, and an arbitrary coupling I' between subsampling distributions Ps. and Ps.. Then
Va(mallma - [ colu")) (2)) ,
(8)
with cost cost function Ca (1 y(2) V Val0,,011br.s))
Proof. Recall that my and my mixtures with m²(2) f [by(2) dPs, (v) and mz
by (2) dPss, (v). Since r is coupling between Ps. and Ps we can use the projection
Ta (y) = Yn and change of variables to rewrite these mixtures as
m=(2)= = S by(z) d (T कं (v) (v)=
= //e (m) dT = Jyz by by dT)).
/
(2) ( by(=)) (T و. (v) [ bxzler (T) f by (2) dr)).
Since mz (2) and m (z) are now expectations w.n.t. the same measure, we can use the joint convexity of V. (Lemma D.9. to show Vr (Ma my') foz Wa(by, (6)))) dy)
E.2 Proof of Theorem 3.4
As before, we prove more general statement from which Theorem 3.4 immediately follows. For this, recall that y is the o-algebra of batch space V), and that P(T R) P(T R) P(R). Theorem E.2. Consider a subsampled mechanism M = S. Further consider two dis- joint partitionings U Ai = =Y and U E, = Y such that all AG, E, are in y and have non-zero measure under Sy and Sx, respectively, Let be an arbitrary coupling between (s Ai), (- Ps), ( (. Es). Then,
Va (m 1lmm) L ca 2) () yy))))
with cost functiun e: 4 x WJ + R24 defined by
Ca ( (2) V.
Σ b ( Ps. (A.))l
Σ b (2) Ps,, (Fi))
(9)
j=1
Proof. Using the law of total expectation, linearity of integration, and change of variables with projection n, (y) Yn shows that
(2)
Σ
by(2) dPs. (l)) Ps, (A,)
1=1
bx(2) Ps. (Ar) dPs Ad)
1 Σ (z) Ps. (Ai) d(T o प, (g)
Σ bz)(2) Ps, (Ai) dT
81-2 im1
40

---

and
mx((2) -
Σ
buutn (z) Ps (Ei)) dI
12++
Since my (2) and m are now expectations w.r.t the same measure, use the joint convexity of Va (Lemma D.9. to show
Va(mellmp' /
Va
Σ bg (z) .c).Ps.CC (A.)l
bug+n (3) Ps. (s,()))
dr
----
change of indexing via y; (1) y; and yj (2)
y(++)) concludes our proof.
E.3 Proof of Proposition 3.5
Proposition 3.5. Consider (2) E Y! y(2)) E Y) and cost function defined in Eg. 2). Let de be
the distance induced by my (see Definition 2.41.
Then, ca (yy ((2) & (g y with
( (2) (2))
max ca (a 9(2))
(3)
ge0 100
subject to vk,1 E (1,2), Vl, u: dr (k) yu < dy( (K) ) and f() E Y f0 E EV
Proof. The original tuples of batches 11) E Y and R) E Y constitute feasible solution to the maximization problem, since they fulfill the constraints with equality, i.e., bk. t, u dy (ve (k) _ = dy ,yh") The value of any feasible solution to a maximization problem is l.eqg its optimal value.
41

---

Distance-compatible couplings of multiple distributions
supp(s)
supp(s))
y
supp(sg)
supp(s:)
3/2
3/3
supp(sg)
93
supp(s))
(a) Distance-computibbe coupling
(b) Distance-incompaaible coupling
Figure 25: Example of distance- compatible and a distance- innaumcciniommtiblle coupling
In the following. we generalize the notion of distance-com contnncbbleatibbeeeee couplings proposed in [S] from two distributions to an arbitrary number of distributions. This provides a sufficient optimality condition for Theorem
Note that we use more general, measure- definition of distance-com cesaacc-compaibiiityy (see Defini- tion F.4). Definition i.6 special case for subsampling schemes with finite, discrete support.
As discussed in Section 3 a dy-compatible coupling between (conditional) subsampling distributions only assigns probability tuples of batches y when all pairs Vs. M/ have the smallest possible distance to y/2 and to each other, while still being in the support their respective distributions.
To avoid having to make additional assumptions about the topology of batch space (Y,)), we will assume that all subsampling schemes have densities and reason about the support of these densities.
Definition F.1. The support of function p Y + R+ is supp(p) {y E Y p(y) 0}.
Based on this notion support, we can define notion of distance between a batch y e Y and the support of a density:
Definition F.2. Consider a distance dy induced by a neighboring relation my. The distance between an element y Y and the support of a function p RR, is defined as supp())) Eispy'Esupp(p) dy (y,y").
Furthermore, can define notion of distance between the support of two different densities: Definition F.3. Consider a distance dy induced by neighboring relation my. The distance between the support of functions P1. P1.P2: Y - R4 is defined as
dy (s(pp((())) supppp)))))suppppp))) = min (y (2) s.t. Ei E (1,2) yı E supp(p:).
Based on these definitions, we can now formally define distance-compattbbee couplings between multiple distributions.
Definition F.4. Consider a coupling I' between probability measures Pı,..., PN on measurable space (Y, with symmetric neighboring relation my and induced distance dy. Assume that Vn Pa & Vn for some measures V/....,11 vN and define = dP,, / dv,, Further assume that r < II Vn with product measure II, Pn, and define 7 dl' / I Vn- Then, I is dy-compatible coupling if (y E sT) = Yu > dv(11. ya) dv (11, supp(ss)))
A (y E supp(T) = Vu > t > 1 dv(un. y1) = de (supp((s))) supp(s.))).
That is, I' o'only assigns probability tuple of batches if all y/ and yv close possible to y1 and as close as possible to each other, while still being in the support of their corresponding densities. Note that choice of focusing y1 is arbitrary, and dy-compatibility could also be defined for any other reference index n E [I.....N).
We shall now prove that do-compatibility is sufficient optimality condition for our optimal transport problem. For this proof, we will use the following lemma, which immediately follows from Defini-
tions P2 and] +
42

---

Lemma F.5. Consider distance dy induced by relation my and two functions P1.P2 Y - Rt. Then, for all V1 E supp(pi), 4/2 supp(p2).
dr 92) 2 dy(y1, supp(pz)) 2 (issuppp(p))suppppp)
Theorem F6.. Consider subsampled mechanism M B. Further consider two finite partitions A A A Y and Ei....,BB E5 E y of such that all A; and Eg have non-zero measure under Sz and Sye, respectively. Let dy be the distance induced by a symmetric neighboring relation my. Let 1 be a do-commaeeble coupling between Ps (111),.... Ps
(-1 ..,,...,PP..
E1)...., Ps (- Es),
which have Nikooy- derivatives $1...., 514J. Then, for all
f , ar( (2)))
I E
arg min DeG
(10)
Jyt+s
where G is the set of valid couplings between the 1 + measures, and io : Y x Y + RR is the cost function upper bound defined in Proposition 3.5
Proof. Consider an arbitrary, not necessarily dy-compatible coupling T. By definition of è and symmetry of =, have
Jyn (a (2) (y (1 (²)
- -fyr
max ca (U.r. (r.) s.t. Vt < u dr Dw) S dv(U.. dr (JEVI4J
with original cost function Ca Y J R defined in Theorem
We can now use Lemma F5 tighten the constraints of the optimization problem inside the integrand and thus lower-bound its optimal value for all y E supp(T):
max Calu, 91.) s.t. Vt < dr( 0n) s dx(yi. OEY!-J
2 max ca (a.11.1 91:) JEV!-U
s.t. Vu > 1 d Dn) S dr(3) supp(ss))
Yu > t dr 0.) dy (supp(()).supp((s.))
We notice that the lower bound only depends on /1 and shall thus refer as Ka (21). Further note that any & supp(T') does not contribute to the integral. Since is a valid coupling, we can marginalize out all variables except 1/1 via projection ni (B) y11 show
I C, (r)
(a(TT(() (y = ( ka(B1) d(T Oo (v1) = -f (a() dPs. (va A1).
By construction of Ka. this holds with equality whenever I is a dy-compatible coupling.
Finally, the exact derivations used for Theorem F.6 can also be used to show that the optimal value of our transport problem has a simple, canonical form whenever dy-compatible coupling exists: Corollary F.7. Consider subsampled mechanism M = B. Further consider two finite partitions Ay...., A₁ E y and E1...., E, E y of such that all A; and Ej have non-zero measure under Sz and Sz, respectively. Let dy be the distance induced by a symmetric neighboring relation my. Assume that a de-compatible coupling between Ps_ (- A1)....,P, (-) Ar), Ps_, (- E.)...., Ps (- with Radon-Nikodym derivatives 81,..., 8T4JJ exists. Then, for all (- E-)
min { () (2)) (y (1) (1) TEG _xI-
ka(v1) dPs, (v1 A1),
(11)
where G is the space of valid couplings between the I + J meusures,
8a (a()1) = max C. (ū.,))))) s.l. Vu > 1: dv( Dm)) < dv(y), supp(ss)))
3E21-3
Yu > > 1: (Dc. Iw) < dy (s(pp((())) supp(ss))
and ca. Y! x Yd + R4 is the original cost function defined in Theorem E.2
43

---

Thus, we can focus on constructing Distance--ompattee couplings when trying to derive existing or novel amplification by subsampling guarantees. Note that these result also generalize asymmetric neighboring relations zy. We just wanted to avoid further complicating the indexing. Future work may want to generalize these results to more general, topological notion of support that does not rely on the existence of subsampling densities.
44

---

G Recovering known mechanism-agnostic ADP guarantees
In the following. first provide overview of the framework for deriving mechanism-agnosie ADP guarantees proposed by Balle et al. [13]. We then show that the same guarantees can be derived via optimal transport between multiple subsampling distributions. Finally, we use observations made during the proof to explain why the mechanism-agnostii guarantees derived via this approach can be suboptimal.
G.1 Overview of Balle et al. framework
The framework from [5] uses four steps to derive tight mechanism-agnossiee guarantees for subsam- pled mechanisms: (1) Partitioning the subsampling distributions via maximal couplings. (2) applying advanced joint convexity, (3) applying joint convexity, and (4) defining two couplings involving two distributions.
Maximal couplings are construction that makes it possible to partition the subsampling probability mass functions as
sy (1) = (1 -1- w ()) + wq (y)
(v) = ()) + war
with probability mass functions pr, 91- Y - [0, 1] chosen such that and yor have disjoint support and [o, 1] is as small possible.
Note that, when considering typical subsampling schemes (Poisson, without replacement. with replacement) and single-clement neighboring relations (insertion/removal,, substitution), this partition simply equivalent to
Sh (y) Pr[S, A.] sx A1) Pr[S, E Ag] -x( A2)
8x/ (v) = Pr[Sz E Fi] ( En) + Pr(S., E F22 (2 F22),
where A₁ and Ej are event that the inserted/removed or substituted element not sampled, and A2. E2 are their complements (see Appendix B in [15).
Using this construction, the densitities my and m. of subsampled mechanisms M B S can be rewritten as
my (z) = - w
Σ by(=)p=()) + w
Σ by(=)x=(v)
(12)
yEY
yEY
my (2) = (1 w)
by (z)p.r + w
(z)
(13)
yE
DEY
Next, rewrite the divergence Ha(m.ll m via the following property:
Proposition G.1 (Advanced joint convexity [I5).. Let my, m' - [0, 1] be probability mass
functions satisfying my (z) (1 w) f() + wz(z) and (z) = (1 (2) ) wg' (z) for some
w E [0, 1], f.g.9' - [0, 11. Given a 2 1, let a' 1lwwwa - and B = a' Then the
following holds:
Ded (mallmp) = D. - / 3g').
Applying advanced joint convexity, followed by joint convexity to Eqs. and (1) shows that
Ha (m m 5(1 -3)HLa
Σ bx)x(())
Σ
byp (v)
yEr
VEY
BH Σ DEY
Σ byge (v)
DEY
Finally, one can construct coupling 7 y22 [0, 1] between Oa and Pa. well as coupling
7' : 722 + [0, 1] between and far One can then invoke a special case of Theorem 3.3 with show
V Ha and the cost function upper bound from Proposition 3.5ittionn.5tt t.5
Har (m S (1 ()) Σ (1) ( ())))) (1) y (2))
B Σ (1) .y (/ 9)
2)
DE
W
45

---

Since we are only considering pairs of batches, we have
ea (y y () = max Ha Ma(bgolllgg)) s.t. (y , S d
9
with induced distance dy from Definition 2.4 This specific cost function bound is referred as "group privacy profile" in [1].
G.2 Subsumption of Balle et al. framework
Next, we show that we can always obtain the same guarantee by defining a (potentially suboptimal) coupling between four subsampling distributions, and then pessimistically upper-bounding the guarantee would obtain through Theorem 3.4
Theorem G.2. Consider a subsampled mechanism M = B o S and some I, I, E X. Assume
that subsampling pmfs Sz, 82 : Y [0, 1] satisfy s=((z) (1 w pp)))))) wqz (z) and s (2)
(1 - w ()Px(2) (2) + uq for some E [0. 1] and Pz. 92: 9x : Y - [0. 1]. Let Y - [0, 1] be an
arbitrary coupling of 92. Ps, and y/ : Y - [0, 1] be an arbitrary coupling of qu Pwt Then, there
a coupling F Y + [0, 1] of Ps. qu P2. 9r such that for all a 2
Ha (m)yllm)))) s
( y (00
yE2242
S (1 - B)
Σ DEM++1
,
01
,0)
Σ (220) 131)),
WEY1+1
with cost function upper bound én defined in Proposition 3.5 a' = + w(a - 1), and B = a¹ a.
Proof. The main idea is to invoke Theorem 3.4 with a specifically crafted coupling, and then apply advanced joint convexity and joint convexity.
Specifically, we define a coupling 7: (0, 1] that corresponds to the following generative process: We first sample w/" and y/2 from the coupling 7/ (recall that coupling is joint mass function). This gives us two elements from the support of ga and 9z', respectively. Then, we sample (3) from element from the support of px- Finally, we let y/² y/
Y conditioned on 2/5 This gives Formally, this coupling can be defined as
700 vi (1)
7 ()
17/ - =1]
2u 2v(22)) (1)
Validity of coupling. Before proceeding, need to verify that this is valid coupling, i.e., its four marginals are Pe: oz Pay qu- For any yi (1)
E V. we have
Σ
700 1/2 111 V2
(1) (1) (2) (2)
EY
(1) (1)
Σ
Yw2 (2)
7u0 1911
12
gx(u22)
V2 U/ EY
HV (1)
Σ
(x(2
g=(v22) (1)
Mey
Σ
7w .991 ())
(2)
92
(1)
where the first inequality is due the indicator function, the second equality follows from marginal- izing 7/, and the last equality follows from marginalizing 7.
The proof for any v1²) E Y is analogous.
46

---

For any 1/2 E.Y Y, we similarly have
E
7001 " (1) (2)
:11 .8/2
(14)
(1) 22 EY3
Σ
1(222 (1) (2)
1/2
709 1/11
2x 1
(1) (1)
(15)
vi 1/2 E2
= Σ
7(12 11 (
(16)
vi ex!
=q. -V22122 ),
(17)
and for any v/²² we have
Σ
7011 (1) (1) (2) (2)
22/ U2
(18)
wfth 1/2 m
2) EY3
7V2 (1) (1)
Σ
Y(22
(1) (2)
1/2
On (1/2 )
vi
(19)
31 M/ EY?
7 (1) (2) 2o((22)
11/2
(20)
(x (1)
EY
qs (
(21)
First inequality. Now that we have valid coupling, we can use the same joint-convexity argument as in our proof of Theorem 3.4 combined with our cost function bound èn to show
Har (mx]lm=>) S
Σ max Ha ((1 (11 wW] a + wh (. w)), g + whb (03))
() ())
())
with each of the |Y optimization problems being constrained by 1k,,,,, u dr(al (1) ((0)) S
dy(vi yuu
(k) ()) and (1) Y2 g(t) E Y2, This corresponds to the first equality in our Theorem.
Second inequality. Due to construction of our coupling, we always have dy dy (2) v1 )2) = 0, i.c. (3) (2) We can thus use advanced joint convexity, joint convexity, and linearity of summation to obtain a looser bound via
Ha (mxllmm))) S(1 - 3)
Σ
max Ho
16 (1) (2))
y2
2
3
max Ha 12
(b )00) ()) ,2))
42+2
with each of the 2 2 optimization problems being constrained by Vk, L, t, u : dy (1) ( < dy(v(h)
(k) , and (())) E W2, .)(2) E V2
(2) in the Next, we can further loosen this bound by dropping all constraints involving w1²) and y2
first optimization problem. We can also drop all constraints involving yi and y in the second optimization problem. Thus, by definition of the group privacy profile, we have
Ho (mzl mx)) S(1 B)
Co
y2
(1) yy
(2)(1)
(1) (2))
+ 3
Ea
U2
72 (1) (2)
y2+2
Note that the first cost function term does not depend on V1 (2) term does not depend on (1) nor y! (2) We can thus marginalize out these variables (recall Eq. 16 and Eq. (20) to conclude our proof.
nor y (2) and the second cost function
47

---

The same argument also applies to the general problem setting defined in Appendix D Given two couplings I", I",, we can define product coupling I' oc I'. II,, invoke Theorem 3.4, and then apply (advanced) joint convexity to pessimistically upper-boune bound the guarantee that would obtained through our proposed framework.
G.3 Deficiencies of cathaanis--gnnottic ADP bounds.
Following our discussion, can identify three potential sources for looseness in this approach for deriving mechanism-agnostie bounds. Firstly, it only uses a binary partitioning of subsampling pmfs & and sz' The resultant mechanism-speccfic guarantee only depends on divergences between two-component mixtures, which may not be sufficient to tightly bound the overall divergence in
complicated scenarios like group privacy. Secondly, it neglects the pairwise distances of yy and (2) resulting in potentially very large values of the cost function. Thirdly, the bound might be further loosened by applying joint convexity once more.
48

---

H Recovering known mechanism-agnostic RDP guarantees
In the following, we demonstrate that existing amplification by subsampling guarantees for Rényi-DP can be derived by instantiating proposed framework (see Fig. 2 Specifically, demonstrate that these guarantees can be derived via the procedure discussed Section 3.3 and shown in Figs. 2b and 2c) (I) Conditioning
most 4 events indicating the presence of inserted / deleted substituted elements, (2) defining a simultancous coupling, and (3) using joint convexity to upper-bound the resultant mechanism-speciffe guarantee by component divergences.
These guarantees are mechanism-agnosti
the sense that they express the subsampled mechanism's 's privacy parameters (a, p) function of the base mechanism's 's privacy parameters. We derive guarantees for the general seeasure-theorete problem setting introduced in Appendix D where the
base mechanism can be either discrete or continuous.
The reader may notice that parts of the proofs in Appendices and H.2 are very similar those in [28 [30, safe for the discussion of couplings and dy-compatibility. That is precisely the point: There an optimal transport problem that implicitly underlies results from prior work, which we have identified and can now generalize to more challenging scenarios like group privacy amplification.
For this section, recall that A. is not the Rényi divergence, but its oth moment, i.e., a scaled and exponentiated Rényi divergence (see Definition D.8)
H.1 Subsampling without replacement and substitution
For subsampling without replacement and substitution relation ~ we first show a more general result Theorem H.T We then demonstrate that it can be upper-bounded via joint convexity of exponentiated Rényí divergence Aa to recover the guarantee from 28
Theorem H.1. Let M = B o S be a subsampled mechanism, where S is subsampling without replacement with batch size q. Let =y be the substitution relation =a,.. Then, for and all x =AX of size N,
Aa S max Aa - w) bb, + au-66 aa) 1[l - w) -6,00 + w b.))) V22
U2
(1) subject to da, (x, (1 s 1, da ( = q //N. N.
(1) (,),))))))) s 1, d
(12 d
S 1, Vi (1) vi and with (2)
Proof. Consider arbitrary ~A, x'. By definition of =A, there must be some E xr, a' E x such that \ {a} U {a']. We thus define both A₁ and Ej from Theorem E.2 to be the event that neither nor a' is sampled, i.., A Ei {y E Y y {a, a'} Ø). We further define Ag and Eg to be the event that a or a' is sampled, i.e., A A₁ and E2 ET.
By definition of subsampling without replacement, we have
Ps, Ps,, (Ei) = HyperGeom(0) N, 1, () = N'
Ps. = Psy, (Ez) = HyperGeom(1 N, N,1.4) = q
N
which corresponds to the weights (1 w) and respectively. We further have
(1x) (1=
y S S= sxlv A2) (3:))))
if EzAay, otherwise
sx(y A1)
otherwise
and
(1=1-)
if C otherwise
C'y otherwise
8 ( E,)
82(v E2)
0
Coupling. We now define a coupling : y2+2 + R, that corresponds to the following generative process: We first generate (1) by sampling batch that does not contain uniformly at random from
49

---

We then let y1 to generate 1/2 and 1/2 (2)
(2) + yi
(1) Finally, we pick random element ā of y and replace it with and a'
respectively. More formally:
so((f (2) A1)
if yf fulfills H2
yl y())
otherwise.
Condition H.2. A tuple y(d) Y2 y(8) Y fulfills this condition when vi v1 and (1)
3ā E Vi 1/2 1/ Aa vi \aaj ud'))
Validity. We now show that this constitutes a valid coupling. Consider yi (1), and only 8y (V) (I)
A1) > 0, there are exactly g combinations of 1/2 (1) (2) (2) for which 7(3) is non-zero. Thus, 1/2
Σ
(V)) q- 20(11 (2) A1)-
88 22 1 EY3
Me
The proof for y12)
analogous.
(1) and only if 8x A1) > O, there are exactly |ær| elements that could Specifically, these elements are all elements that
Next, consider y/
(1) from y2 (1)
have been replaced by generate y2
do not appear in We thus have
7(0) = (la1) -)- (|zl - 4) 9!
| - 1 q
Σ
x
9
vi
22 (9)
EY3
The proof for y/2 Compatibility. Finally, we show that y is do-compatible coupling (see Appendix P). Whenever (y) > 0, then
(2) analogous.
dx(v1" (1)
1/22 (1)) dy (g1") supp(s>( A2))
dv(vi .11 (2)) dx (v()) supp(s (.1 F1)) = -0
(1)
(1) 1/2 (2)) = di (1 supp(s E2)) = 1. dx(v1
(1)
Similarly, the pairwise distances between all with u > / > 1 are identical to the distance of their respective supports: The batches have distance of 1 because one can transform one into another using a single substitution. The supports have a distance of because one can transition from one another using a single substitution.
The result then immediately follows from Corollary
E7
Next, we can derive the upper bound from 28 For this derivation, we will use the following Lemma, which is proven in Appendix of [6):
Lemma H.3. Consider probability measures P, P.Q output measure space (Z, Z, Define = dP dA and dQ / dx. Then
Σ (00) 1=2
(a = 1+
The following proof essentially follows that of 28 but skips their Appendix B.2, since we have already successfully decomposed mixtures m. and mg into small terms that only involve base mechanism densities.
50

---

Proposition H.4 (Wang et al. (28)) Let M = B S be subsampled mechanism, where S is subsampling without replacement with batch size q. Let my be the substitution relation MAy. Then, for >> 1 and all =Axx x' of size N, Da Aa(mz/1mm is Le.q.
1+ 2
a2
W
max yo
A((b,lbbr),
with w = q/N
(2) Using the constraint y/ V/ in Theorem H.1
(1)
Proof.
we can rewrite its objective
max
(a w) b + w
[1 w) yn + w b go)
(1) :92
(2)
Using Lemma
H.3 we can upper-bound its optimal value via
Aa((1 w) be(")) + w-wa max
(z) |1(1 w) y + (.))
Mi .22
(w b 9/
w - b (2))
max
1
a
4/
1-1 dd((2)
Mi U2
(11-w) w) y1 + w
(2)
42
a
a w¹ ʃ
1b ()) (2)
max
1
Σ 1=2
92
1-1 d)(2)
(1) (1) (2)
((1 - w) b (1) + w
1/2
bb 1/2
b
w
max W2
(1 w)) b
02
1-1
dd(z);
I=0
91
W22
(2)
where each of the a + optimization problems is independently constrained by du dv(vi) (1) dv(v) (1) (2)) < 1, and dr dv(v2 ,32 (2) 1.
1//2
Next, we bound the optimal value of each of the + 1 optimization problems. Using the joint convexity of xr y + x. yy y--ا, which implies convexity in the second component, shows that
1b () b cnl
/
max (1) (1)
dA(z)
393 M/2
(2)
(1--w) w)
6 10
+
w
U/
lb
b
1
bb () - b 1
Mi ./2 M/2
max
(2)
(1 w)
b' B-11
dx(z)
+ +
bi_1 (2)
92
dA(z)
bb
b
1
1b
b call
<(1 w)
max
(1)
02
B-1
d)(z)
+ w
max
1/2
111
Ub
d)(z)
vi N2 19
(2)
b
1
16
b
<(1 w)
(1) 2012 .012
max
93
1-1
MB
dA(z)
+ w
( .22
b (1)
V2
dx(z)
91
91
(1) 19)
max
dx(2),
(2)
b'
Vi 993 M12
where all optimization problems independent, with each one being independently constrained by dr(w)" (1) (1) < 1, (vi ., )) < 1, and dv(v2 yy2 (2)) S Note that, for the last inequality, we 1/2
(2) in the second maximization with y which essentially adds degree of freedom replaced a 3/2
(1)
and thus leads to an upper bound.
In 28 the optimal value of the final problem is referred to as the dernary/x/'-divergeen of b,, b y0 and b m. As shown in their Lemma 19, it can be upper bounded via maxyza,7 (b bby) which concludes our proof.
51

---

Additional terms. Note that [28] derive three additional bounds (see their Lemma 17, Lemma 19, and Theorem 27) on the the ternary-Ix Io-auyyll--dveeeeenee -divergence. This introduces additional terms, but does not change the fact that their result is lower-bounded by Theorem H.1 We use their full theorem as baseline in our experiments.
H.2 Poisson subsampling and insertion/removal
Next, we show that the Poisson subsampling guarantees in [30 7 follow from another optimal transport problem. For our proof, will use the following Lemma, which corresponds to the "novel alternative decomposition" in Appendix A. of [30].
Lemma H.S. Consider K + 1 N distributions P. ......... QK output measure space (Z, 2, X), and define = dP/ / dd, qi = dQk ad. Further consider some wI...., W.K E [0, 1] with Σk=1 Wk = 1. Then,
K wi qi 1p
Aa
Pl
Wk qk
S
wk
Da
9k
+
Proof. Based on the definition of A., we have
A
Wk q
p==)a
a-1 d)(z)
Σ kk=1 we q (x))
EE Wik qu(2))
+ =p(z)= - (Ek wi - a(z))) dA(2)
Ekkn wh =q((z)
a-1
=== Wk (q=(2) + p(z) - Ex= wi m(2))) (>=))>>((=)))
d)(z)
Ek Wk go gx(2))
a-1
The result then follows from joint convexity of A..
Note that the proof of this lemma is very similar to the proof strategy we used in deriving Propo- sition H.4 using Lemma H..) We add 0
with some to the numerator (which leads to the binomial expansion in Lemma H.3) and then apply joint convexity to obtain an upper bound.
Proposition H.6 (Zhu and Wang (0). Let M B S be a subsampled mechanism, where $ is Poisson subsampling with rate r. Let my be the insertion/removal relation - Then, for a > and all x 21,x x', Aa (m, [m,r) is Le.g.
2
Σ 1=0
r11 -r)"
max Ar(bylbbyr) w=
Proof. Since we are concerned with insertion/removal, we need to consider two cases:
Case 1: Removal. In this case, there is some x such that x' = x \ {a}. We let A be the event
that a is not sampled, i.c. A₁ = {y E Y & y}. and let A₁ = AT. We let Ej = V. i.c, do not condition on any particular event.
By definition of Poisson subsampling, we have Ps, (A1) = 1 - r. Ps, (A2) = r. and Ps, =
We further have
rrlv (1 - (r-)) 101- if Cry
Su (y A1)
0
otherwise
rly -1 - --) ifyCrAnes
s (y/ A2)
0
otherwise
52

---

and
[rlv1(1 r) fyyct 00
[rlvl(1 - ((0--))(--00 r) y S a
Sor(1) E1)
otherwise
00
otherwise
Note that (1 A1) = (1 FT).
Coupling. We now define coupling y 2 + R. that corresponds to the following generative process: We first generate vi by sampling batch that does not contain a via Poisson subsampling
(2) from x \ fa). We then let V/1 + vi Finally, we deterministically insert to generate (1) This
can be formally defined via
(2 9 A1)
if yi (1) y1 Ag vi U ffa}
7V y())
otherwise.
Validity. We can verify the validity of this coupling as follows: For every y1 with 8x (vi A1) > 0.
(1)
there is exactly one combination (1) (2)
M/1 for which (y) 0, namely y1 v (1)
and y/
(1)
yi (1) U {a}. We thus have Ef r(vi" 1/2 .1 = =s=(vi" A1). The proof for y1 is
(1)
(2)
analogous. For every 1/2 (1) we have exactly one combination of yf yi for which ((7) > 0, namely (1)
(2)
yi Vi
(2) (1)
1/2 \ {a}. We thus have
Σ
7(0) (1) 92 .3)2))
(1)
M 21 EY"
(22 {a} A1) 1-15"1-((1 (111)))00--01 -1vl--(11-
r)lll-lvll 52(2²² A2).
Compatibility. Finally, it can be easily shown that 7 is dy-compatible coupling (see Appendix Whenever (v) > 0, then
dx(v1 (1)
1// ) dx (vi). supp(sa(- (AA))) = 1,
dr dr(w1 11
(1) (2) = dx (v))) supp(s Bi)) = 0.
(1)
Similarly, the pairwise distance between y/2 and y
(2) is always This is identical to the distance of their supports, because one can always transition between them via single insertion/removal
(1)
It thus follows from Corollary
F.7 that
Ao (ma [mar S
max
-r) (1((1r)) bb,) + b,
1a0lb (0) 2i
d= (1) (1)
1/2 S 1, 1 = (2) d (1) (2)
s.t.
S (1)
Because ( y1() and because y (v) , 92 < is equivalent vi (1) can be restated as
(1) (1)
1 U2
this bound
Da (m=llm)>) < max Aa ((1 - r) by r by 11b,)
Finally, one can use the definition of A. and binomial expansion to show
((1 (2), + rzy) max g=
<
d)(2)
Jz.
by(2)a-1
(2) + rbyy(z) (2) dA(z)
max
VE Jz
by(
[
(1 (1-r) r) + by (2) (x)
(z(2) dA(z)
max D=LLNo'
by(2)
( r'(1 )r((( r) --- ((bb)]6b)))
max ツー 1=
()) 7(1
r) max Ar(bulbby) v=
1=0
53

---

Note that this is smaller than the term in Proposition H.6 by a factor of 2.
Case 2: Insertion In this case, there is some E x' such that x: = x' {a). Very similar before, we let A1 = Y, i.e., we do not condition on any partieular event. We further let E1 be the event that a is not sampled, i.c. E1 = {y E Y a & y). and let Es = Ej. We notice that we have exactly the same conditional distributions in the first case. We can thus define exactly the same coupling (up to changes in indexing) to show that
Da (mx [m S max
Aa (b - r
) + rby))
V=L.V
Next, applying Lemma H.5 and using the definition of Aa shows that
(m m (
< max
An Aa(byl(1 - r)bb + rby.)
V==.VV'
S max
(1 - r) aa + b2 - ((1 rr)by + rbbb )1by)) + r raalby + by ((1 r))b, + +bbg))
V==.VV'
max (1 (1-17 (1-r))a((1 ((1 + r)by - 1b,)) + r r ((1 - r:bby' + rb,y1bg/)
This corresponds exactly Eq. 6 of the "novel alternative decomposition" in Appendix A.1 of (30] One can then through the remaining steps in their Appendix A to show that this term is at most two times larger than the one we derived in the deletion case.
As already mentioned at the beginning of this section, the proof is very similar to that in 30 except for the discussion of couplings and dy-compatibility We emphasize that the crucial aspect, which is not discussed in any prior work on Rényi-DP amplification, is that there is an implicit, underlying optimal transport problem between conditional subsampling distributions. Now that we have identified this connection, broader range of amplification by subsampling scenarios for Rényi-DP.
apply this more general optimal transport principle to much
Further tightening. The factor 2 in Proposition ca be eliminated for distributions with particular symmetries (see Theorem 5 in (29) or bounded Pearson- Vajda x' --sseudoddivergence (see Theorem 8 in (30). We thus do not include the factor 2 when using this amplification guarantee baseline in our experiments.
H.3 Graph subsampling without replacement and node modification
Daigavane et al. [40] consider setting that differes from the usual insertional/removal into datasets: Node-level privacy for graphs. There, the dataset space is the set of all directed, attributed graphs
X == U UN DEN NDD XD x {0, 1 which are composed of continuous feature matrix and discrete adjacency matrix. Two graphs xt, xx' are related by dataset relation =x if x' can be constructed by inserting a node (including new edges) into x, or removing a node (including its edges) from x.
To analyze this problem setting, they perform preprocessing step (see their Algorithm 2) to represent each graph by a set of subgraphs, with each subgraph corresponding to a node in the graph. Via this construction, they return to the traditional setting where X C P(A) for some set A, and the modification of a node's 's features and edges corresponds to the substitution of K elements i.c.
~ ((x, x') E X 3g E x x', g' E x' \ x x' = x NoxNg Uu lgl = Ig'l =K), (22)
where K depends on the maximum considered graph degree.
Irrespective of the graph neural network specific details, this discussion suggests that group privacy and differentially private learning for graphs are related.
We shall now demonstrate that their result for subsampling without replacement can be derived from Theorem E. i.e. optimal transport without conditioning.
Proposition H.7 (Daigavane et al. [40). Let M = B S be subsampled mechanism, where S is subsampling without replacement with batch size q. Let mny be the substitution relation AA. Let
'Note that they do not actually consider insertion/removal, because their analysis assumes the number of subgraphs to remain constant.
54

---

KKA x be the K-fold substitution relation defined in Eq. 22 of size N,
Then, for a > 1 and all x KKAX o'
Da (a S
Σ
Wk
max BE
(b(bybbby)
with wa- Hypeereemm(i N, K,q).
Proof. Consider arbitrary =AXx x x'. By definition of =A, there must be some x 22) g' a such that x' = x
9 U \g
and [g] Ig'l = K.
We condition on the events A = Y and Ej Y. meaning
(
if y Cx otherwise
F1) (1) (
y otherwise
Sx(y A1) =
and (x
Coupling. We now define coupling via 7 Y R+ that define the following generative process: We first define y() by sampling batch of size from without replacement. We then remove all elements that are in g and insert an equal number elements, which are chosen uniformly at random from g'. This coupling can be formally defined as
(x((1)
A1) (9ong))
if fulfills Condition H.8 otherwise.
Condition H.8. A tuple (()) E Y, ( E Y fulfills this condition when there exists a S such that g2) = (d) \ و and y n = (g()) ngl..
Validity. We now show that this constitutes valid coupling. Consider any ( with sn (y AA) > and ()( n gl = k. There are exactly (k) different y² for which r(y) is non-zero, and each one has the same probability. Thus,
(K)
K (K)
= 8x (y( | A1). (100-1) )
Σ g
7V))
Sx (2 A1)
k
9
The other case is analogous.
Compatibility. Evidently, this is dy-compatible coupling, because (a) whenever ωy2) contains k elements from g. it has distance of ie from Sx/ (y E,) and (b) whenever (()) contains k elements from we generate y(2) by substituting exactly &s elements.
It thus follows from Corollary F7 that
Aa A (mmllmmar -
Σ (0( Ai (1)
with
Ni (1) max Au (b, lbbr) V.y/
s.t. de(y. $ 1g (1) ngl.
The result then follows from the definition of induced distance, the definition of the K-fold substitution relation ~KAX and the fact that (2) O gl is a random variable with distribution HyperGeom(N, K.
Note that 40 instantiate this result with Gaussian mechanisms with sensitivity C, for which
max / Ao (b,) exp(a (a- K²()).
we experimentally demonstrate that this result can improve upon the baseline of combining 28 with the traditional group privacy property, but is not sufficiently tight to consistently outperform across wide range parameters. This emphasizes the benefit of considering optimal transport between proper conditional distributions when deriving amplification guarantees.
In Appendix 1.4
55

---

I Novel RDP guarantees
Now that we have a framework that enables generic subsampling analysis for Rényi differential pri- vacy, derive variety of novel guarantees that were previously only available for approximate differential privacy.
In the following, we first demonstrate that RDP guarantees for dataset relation =x can be derived from a base mechanism that only known to be RDP under a different batch relation my, i.e., "hybrid neighboring relations" [15] We then show that we can derive RDP guarantees for non- standard combinations of subsampling schemes and neighboring relations, such as subsampling without replacement and insertion/removal. Finally, we derive simple, tight mechanism-specifee subsampling guarantee for randomized response. We use this guarantee in Section 4 to demonstrate RDP bounds instead of mechanism-speciine RDP bounds.
the limitations of using mechanism-agnon
For this section, recall again that Aa is not the Rényi divergence, but its oth moment, i.e., scaled and exponentiated Rényi divergence (see Definition D.8
1.1 Hybrid neighboring relations
Hybrid neighboring relations have thus far not been discussed in the context of Rényi-DP. Analyzing such scenarios may be particularly useful when the dataset space X and the batch space (Y.)) are different from each other, e.g,, when mapping from large text corpora to short sequences of token embeddings. Note that hybrid relations may also be useful for noisy stochastic gradient descent with fixed batch sizes (see end of Appendix [.2].
As an example, we consider the following scenario: Subsampling without replacement, with sub- stitution relation = -Ax for datasets and insertion/removal relation # for batches. The proof is largely identical to that of Theorem H.T but uses the fact that a substitution can be represented by an insertion, followed by a removal.
Let M = B o S be subsampled mechanism, where S is subsampling without replacement with batch size q. Let =y be the insertion/removal relation = and my be the substitution relation =a Then, for a > 1 and all x =Ax x' of size N,
Theorem L.1
Aa (m (m)) ) S max (a w) b byas + w b un |[ w) byj + w 8/2
y
with E W2+2 subject to 1 = vi (2) di,r(vi (1) 21 < 2, d d (1) -1 s 2, x (1) _122)) S 2. and with w = N.
Proof. Consider arbitrary ~ x'. By definition of ~A, there must be some a E x. a' E x' such that x' = x \ {a} U {a']. We thus define both A₁ and Ej from Theorem E.2 to be the event that neither a nor a' sampled, i.e., A En = {y E Y y n fa, a'} Ø). We further define Ag and Eg be the event that a or a' is sampled, i.e., A A1 and Eg ET.
By definition of subsampling without replacement, we have
(AI) Pss., (Ei) = HyperGeom(( N, q) = N Ps, = Ps.. (Ez) = HyperGcom(1 N,1, = q
N
which corresponds to the weights (1 - w) and w. respectively.
Coupling, We now define coupling via 7 Y + R.:
(x (1) A1) if ( ( fulfill Condition H.2 otherwise.
(1) () (2)
Condition H.2. A tuple (1) E Y2, y(2) E Y fulfills this condition when (2) = vi and 3ā E vi (v0)) = (1) \ (aju (a} A (2) = ()) (d)))
56

---

As explained before, 7 defines the following generative process: We first generate (2) by sampling batch that does not contain a uniformly at random from x. We then let y (2) + yi Finally, we pick
random element à of y/" and replace it with and a' to generate y/2 (1) and 1/2
(2) respectively. Note
that each of these substitution corresponds to exactly one insertion and one removal.
Validity. The validity of this coupling has already been demonstrated in our proof of Theorem since validity of a coupling does not depend on batch neighboring relation my.
Compatibility, We can thus focus on showing that is a dy-compatible coupling (see Appendix Whenever 7()) 0, then
(1) ( = dx (vi") supp(sa( A2)) = 2, dv 1/2 dr ( .11 (2)) = dr (v1") supp(s, (- Bi)) = 0,
dx(v1) ( ) = dx (1 supp(s (: E2)) = 2.
We see that the pairwise distances between all yes Yo with u > t are identical to the distance transform one into
of their respective supports: The batches have distance of 2 because another using a single substitution, i.c. an insertion and a removal. The supports also have distance of 2 because can transition from to another using single substitution.
The result then immediately follows from Corollary F7
If we wanted express this result terms of the Rényi-DP parameters of the base mechanism, we could go through the same derivations as in our proof of Proposition H.4 to show that
(m S 11+2 Σ (
ww max (c(bylbby) v.
s.t. d=>(v.,))
with w / N. The inner term can, for instance, be evaluated using the traditional group privacy property from (3I.
1.2
Subsampling without replacement under insertion/removal
To demonstrate that our framework is not limited to analyzing the usually considered combination of subsampling without replacement and substitution or Poisson subsampling and insertion/removal. we consider the following non-standard combination: Subsampling without replacement and inser- tion/removal.
We show that we can derive a guarantee that is qualitatively similar to that of (30], while preserving a fixed batch size. Such results could be useful when implementing noisy stochastic gradient descent in deep learning frameworks with static computation graphs, where the variable batch sizes resulting from Poisson subsampling may be problematic. However, that this guarantee only guarantees privacy for spaces of datasets whose elements are larger than some Q E N with Q q. where is the batch size.
For the following proof, we condition on the same events as in our proof of Proposition H.6 but need construct different dy-compatible coupling, since have different subsampling distribution.
Theorem 1.2. Assume a dataset space and batch space defined by X C {x P(A) |z| Q} E X, ly| = g). y = P(Y) and finite set A. with Q,4 q E N and Q > q. Let M B o S be subsampled mechanism, where S is subsampling without replacement with batch
{y C |
size q r. Let my be the insertion/removal relation 11,. Then, for a > and all x ~ 11 x',
Aa mm < max
2. Σ 2=
(1)
(
w w)- 1-
max Abb,llbb, s.t. dy v) $2) 22) 9.3
NEN
subject N Q and with q N.
Proof. Like in our proof of Proposition H.6 need to distinguish between insertion and removal.
57

---

Case 1: Removal. In this case, there is some a E æ such that x' = x {a). We define N = = which fulfillss N Q by definition of dataset space X.
We let A, be the event that is not sampled, i.e. A1 {y E Y a & f). and let A2 = Ar. We let
E1 Y, i.e., do not condition on any particular event.
By definition of subsampling without replacement, we have Ps. (A1) = qN, Ps, (A2) q N, and ps,,( (E,) 1. We further have
(5)
-1
if CInagy otherwise
8z(1 A2) = (1-1)
if CIAaEy otherwise
82(1 (1) =
and
(
if C
8x 8x (y F1)
otherwise
Note that sy | A1) sy E1) and that all three conditional distribution are subsampling without replacement from sets of size N, not of size N + or N - Further note that, for event A1, we only need to sample q - 1 elements, since one element is always fixed to be a.
Coupling, We now define coupling via 2
R
sz (v) AA)
(1) = vi A vi U
7l y ()
otherwise.
Simply put, 7 defines the following generative process: We first generate yi by sampling a batch that does not contain via subsampling without replacement from x {a]. We then let y\ v(") We then randomly replace one of the batch elements with to generate y/2"
Validity. We verify the validity of this coupling as follows: For every (1) with ( !
A1) > O, there are exactly q combination 1/2 Mi
(2) for which 71)) > 0. We thus have
En m (2) Exa 1(11 1/2 Di
(1) (1) (2) sv
(1) A1). The proof for yi is analogous.
(2)
For every there are exactly N - (g 1) combinations of :/
(2)
for which >(y) > 0. This is
because must have replaced one of the N 1) elements of x' that are not in 3/1 thus have
(2)
Σ
(1)
(1)
(2)
1/2 Vi
91 (2)
e
N
1 = N - 9 (M) = 9-11
N N - -
= =(N (q 1))
Compatibility. Finally, it can be easily shown that 7 dy-compatible coupling. Whenever ((1) > 0, then
dx(v() (1) 11) = dx (v1") supp(su(-) A22)) 2,
dv(v1 (1) (2) dv (vi") supp(sw(( Ei)) 0.
(1) and y (2) is always 2. This is identical to the distance of their supports, because one can always transition between them via a substitution, i.e., an insertion and removal.
Similarly, the pairwise distance between V2
thus follows from Corollary
E. that
Aa (mm
<
max
Aa((1 (1-9/N1)
N). 1 + N lublbbb. ()) (
w of vi
s. , ./2
(1) (1) < $ 11 = v1
(2) dd.((1,) 11²²) 2
58

---

As in our proof of Proposition H.6 one can use the definition of Aa and binomial expansion to finally show that
a ( w w)a- max A1(bgllbgr) s.t. dyy.y/ S 2.
Aa Am
with v = N. Note that this is smaller than the term in Proposition H.6 by a factor 2.
Case 2: Insertion In this case, there is some E x' such that x' {a}. We can thus define the same events and the same coupling symmetric manner to show
w) /
(1 u (uy - -by (z)
Aa Mm S max(1
bx(2) dA(=)
V.y
bz(2)
(1 by (z) + (2) by (2)
t
by (z) d)(=),
subject to dy(y.8') I 2. with w N. Again, this corresponds exactly to Eq. 6 of the "novel alternative decomposition" in Appendix A.1 of [30]. One can then through the remaining steps in their Appendix A show that this term is most times larger than the deletion case.
derived in the
Finally, since this bound depends on N, and want the guarantee to hold for all x = x', need to determine the that maximizes the bound.
Hybrid Relations. Note that we could have also gone through the above derivations with batch substitution relation - Then, each substitution would correspond to an actual substitution, instead of pair of insertion and deletion, and we would obtain
a
Ao (m lmmm
max
Σ 1=
w (1
(1-w)a- max Ac(byl(by)) "
s.t. N Q.
NEN
with w = 9
I.3 Tight mechanism-specific subsampling without replacement for randomized response
As mentioned earlier, the following result is meant simple example demonstrate the benefit of using mechanism-specte over mechanism-agnostie RDP bounds in Section 4 For the following discussion, recall Theorem [..I] which proved in the previous section.
Theorem H.1.
Let M B o S be subsampled mechanism, where S is subsampling withou replacement with batch size 9. Let my be the substitution relation ~ A,Y. Then, for a and all =AX x' of size N,
An(mal S max A ((1 w) - b,, + w as |[(1 - w) b,, + w (o-b b.
9
1/2
subject to da x 1322 w = q N.
(1) (1) < da da (1) .222) S da 2 s 1, v1 vi and with
We shall now solve Theorem H. for randomized response and prove the tightness of the resultant guarantee.
Theorem I.3. Let B be the randomized response mechanism 1h - (1 - V)I with h V (0, 1). V ~ (f) and true response probability 0 [0, 1). Let S be subsampling without replacement with batch size g. Then, for all =Ax of size N, Ao (m (mm is l.e.q.
max Aa w) Bern( (]) + wBern(- [)][ Beree ( wBern(- | 1--)) 7))
subject to T E {0, 8} and with w = N.
Proof. Because we have no further information, we must consider the worst possible underlying function h Y {0, 1}.
59

---

Due to the last constraint in Theorem H.1 we must have h(rl = ).((12)). Due to symmetry in
Aa (we are summing over 2 E {0, 1J), we can assume w.l.o.g. that h(vl - h(vl ( = and thus b n0 (z) of go) = Bern (8)
(1) and (()) can differ from y1 (1)
Because the batches y/2 values k(y22) and h(y2 (2)) arbitrarily. To make Aa greater than 1, the two mixtures must be different
we can choose the corresponding function
from each other. Thus, we must choose either h(y2 ) = and h(y2 (2) = 0, or h(y2 h(yz1) = 0 and
hV22 (2) 1. This corresponds to b go (z) Bern(= r) and b car (2) Bern( 7) with E [0, 0). Maximizing over both options yields our result.
1/2
Note that this guarantee can be evaluated (1): We need iterate over two possible values of and evaluating the corresponding A,, requires summing over two values E {0, 1}.
Next, prove the mechanism-speciffe tightness of this result, meaning it is not possible de- rive stronger guarantees without additional information about dataset space X and the function underlying the randomized response mechanism.
Theorem L4. Let S be subsampling without replacement with arbitrary batch size q N and [0, 1] be some true response probability. There exists a dataset space X and a batch space (Y))) fulfilling the constraints in Definition D.5 well pair of datasets x =ax of size N, and function h + (0, 1}, such that the corresponding subsampled randomized response mechanism M = B S fulfills
Aa Aa(m=llm=z)
=max (a w) B)rBrn(. 0) wBern(- +) Bern( ( + wBern(- | 7))
subject to E ( 0} and with w =
Proof. Let X for a' E N Define x' x {a} {a'}.
I > 4) Consider an arbitrary X and select arbitrary elements æ,
Assume w.l.o.g. that the divergence is maximized by 0. We now construct an indicator function h: Y {0, 1} for and a' that leads to the largest possible divergence.
ff, =
hwy)
if e
By construction of h, the corresponding base mechanism pmf
Bern( (= ()
f =
(2) = Bern(2 & () if
Bern(z
0) if EV
Under the distribution of S(x), the first case occurs with probability 1- and the second case occurs with probability Under the distribution of S(x), the first case occurs with probability and the second case occurs with probability w. We thus have
my (z) (1 w) Bern( 0) + wBern( [0) myr (z) = (1 Bern( () + wBern( (= 1 0).
which exactly attains the desired divergence when is the optimal value.
60

---

J From mechanism-specific guarantees to dominating pairs
Our proposed optimal transport approach lets us derive mechanism-specific guarantees, which upper- bound the hockey stick divergence between the distribution M (a)) and M (x') with a =x x' via weighted sum f of mixture divergences, i.e.
K
Ha Ha(m=llm=z)
((raar) a,k
Ha (Pakk l1aa,
(2.22)) (100r (1g))))))
(23)
k=
(a.2") Here, the aakk are weights with Σ wark
(x,x') 1, which depend on the chosen coupling ? (n.a')
and are indexed by a 2 0, 1 S k I K. and x, x' E X. The Pa.k and (ax=") are densities of (z.x") mixture distributions plz.x') and 4a,K on the output space IR which are also indexed by a 2 0, a.k 1 k < K, and x, X.
Our goal construct dominating pairs from such bounds, so that we can then use them for privacy accounting. For this discussion, recall the definition of dominating pairs:
Definition 2.3. A pair of distributions (P,Q) with densities (p. q) is dominating pair for mechanism M under neighboring relation ~xx, if H (mmllmm))) s H. (pllg) for all mx x' and all 2 0.
(a,x') and 92.k the densities on the r.h.s. of Eq. 23 are constant in a, k. x, and x', i.c.. Pa.k immediately identify that the corresponding distributions
(a.²)
with some densitities q, then P and Q are dominating pair. For instance, in Section 3.4 could immediately determine that the two Gaussian mixtures in Theorem 3.8 are a dominating pair for Poisson subsampling and the +
relation.
However, this is generally not the case. In the following, we discuss a three-step procedure that let us (1) reduce the weighted sum of divergences in Eq. (23) to single divergence (2) resolve non-constancy in the dataset pairs (z, x'), and (3) resolve non-constancy in the divergence order a.
Note that, depending on the considered setting, it may be possible to skip one or multiple of these steps (like our group privacy example).
J.1 Step 1: Eliminating weighted sums
Consider some fixed order a and fixed datasets x =x x'. Let us thus omit the corresponding indexes. In this step, we construct a pair of distributions P. with densitities ý and q such that
K Σ wk (p Ha (pllg).
To achieve this, we notice that there is no requirement for dominating pairs to distributions on same space RD, Taking inspiration from hierarchical randomized smoothing [69], we thus construct p and y that are mixtures of the pı and qa and additionally release their component indices:
Lemma J.1. Consider arbitrary densitities Pt.... ,K,, PoK.qI...... ......, . RRD + R. and arbitrary weights wI...., .. E [0, 1] with Ek= wk = 1. Further let r (1...., K} - [0, be the probability mass function of Categorical(w),.-.. (w)icaal((,,,,...... wk). Define p. RRD x {l, K} R4 as 5(2,1) k) (2) rkk) and ã(2, k) (z) rkk). Then, H (all))) = Σk_ wk Ha(lll))))
"assuming the batch space finite and discrete "the arguments in this section also apply to the general problem setting from Appendix D arbitrary output spaces
where we allow
61

---

Proof. By the definition of hockey stick divergence and p. q. we have
((2, v)
Ha(pll
Σ
max
((2, u) 0) (((2,)) 3 dz
3D
km1
(x(2) rr(k)
(x(22) -(()) .0 (x((2) rk() de
max
3D
K
(2) (x(=))
r(k)
max
0 (z(2)) dz
K
Ha (p*)19))-
Note that one could equivalently construct continuous distributions P and Q by defining the categori- cal distribution transformation of uniform distribution. Further note that the distribution of privacy loss random variable log(ū(2) Z) / @) with Z P is simply a weighted sum of the components' privacy loss distributions, which can be easily shown via law of total probability. This makes this construction amenable to numerical privacy accounting.
J.2 Step 2: Resolving non-constancy in dataset pairs
After applying the construction from the previous step, have bounds of the form Ho (m S Ha (a "11"=""|1"000 )). If these bounds are not constant in the datasets x, x' E X, we cannot simply read off a dominating pair.
However, the ultimate goal behind identifying dominating pairs is to use them in a privacy accounting method to algorithmically derive guarantees for all possible pair 2x x' under composition. Providing guarantees for all possible pair does not require that we derive guarantees for all pairs simultaneously. To formalize this, recall that the neighboring relation ~xx a set of tuples from X
Lemma J.2. Consider any 2 O, mechanism M and L different neighboring relations ~(1) S c!') for
(D) X2. Assume that there are L constants (.),...,,,!,, such that Ha all l E (1,..., I.} and all x 1) x.. the neighboring relations partition =x, iee, =x= U =11) then
Va my x': Ho (me m S !
Proof. Consider any x 2x x'. Because the neighboring relations partition =x, there must be some such that x (1")) x' and thus Ha (m, [mmm)) S c(l)) < max c(t)
For the purposes privacy accounting, is thus sufficient to determine some sufficiently tre-gnained partition (1) ..... (LL) such that for all / (l,..., L} and all > 0
Yx -1) x': H. (ple. (1 = Ha Ha (1!1))
where pl. and d are families of densities indexed by partition index / and divergence order One can then perform privacy accounting independently for each of the relations.
This goal can always be achieved by having one atomic relation per possible pair of neighboring elements. practice, however, much more coarse-grainee partitions may be sufficient. Zhu et al. I0 applied this ansatz to the insertion/removal relation, by deriving dominating pairs for insertion and removal separately. In our work, we partition the group insertion/removal relation for groups of size K into K different "insert-Ka -rmovve---ee- relations with K + K_ K.
62

---

J.3 Step 3: Resolving non-constancy in divergence order
Consider some fixed partition index I {l..... ........,.................. L}. which we omit in the following. We are now left with a bound of the form Vx = x': : Ha (m2 [m I H (Pallla)) If the families of densitities Pa. da constant in a, i.c.
va H. (Pa l(aa) = H.
with some P. q. then the corresponding distributions P, Q are dominating pairs. Importantly, the numeric value of the bound can vary with a. We just want the numeric value to be identical to the divergence Ha of two specific distributions for all a.
jejust
this is not the case, there are two options to construct a dominating pair. The first option uses a characterization of dominating pairs
function of privacy profiles. It was applied by Zhu et al. [0] to determine dominating pairs for subsampling without replacement and the substitution relation. The second option is enabled by our novel optimal transport and constrained optimization perspective on subsampling.
J.3.1 Option 1: Convex conjugation of privacy profiles
The following result from [00] establishes correspondence between privacy profiles and dominating pairs, as well as providing a formula for constructing dominating pairs from privacy profiles:
Proposition J.3 (Zhu et al. (IO). For given f : IR+ + R, there exists P, Q such that Vo 2 0 (a) = (PP (P.Q) if and only if E where
F= (f: + R f is convex, decreasing, f(0) = 1 and f(x) max x, 02]
(24)
Moreoever. one can explicitly construct such P and Q: P has CDF 1 + f* 1) in [0, 1) and Q Uniform((O, 1]), where f is the convex conjugate of f.
Next, we show how to construct function f(a) E F from our families of densities aa, da indexed by a that allows us to determine dominating pairs.
Lemma J.4. Consider two families of densities Pa. qa indexed by a 2 0 such that Vo x' Ha Mammllmm S Ha (Paillla) Define the functionn f IR+ + IR with
f(a) = max H (pallga). 820
Then is a valid privacy profile, i.e., F with H defined in Eq. 24
Proof. For every 3 2 O, let fa(a) = H. (pallqa) be the privacy profile associated with a specific pair from the considered families. All these functions are elements of F per the first part of Proposition J.3] We thus know that each fo is convex, decreasing, and has value 1 at a = 0. Naturally, their maximum is also convex, decreasing, and has value 1
O. We further know that, for all B 2 0, far 2 max x. 0}. Thus, we have f()) 2 fe(x) 2 (1 r) for any 3 2 0. D
We can then invoke the second part of Proposition J.3 to define our dominating pair.
As mentioned earlier, Zhu et al. 10 applied this principle to subsampling without replacement by taking a maximum over two different pairs of distributions. Lemma [.4 generalizes this principle to larger families.
J.3.2 Option 2: Relaxation of cost function constraints
novel solution is enabled by our proposed framework for deriving mechanism-speciife subsampling guarantees: Recall that the densitities Pa and fo. are the result of identifying worst-case mixture com- ponents under pairwise batch distance constraints (Proposition 3.5). In Appendix L we demonstrate that it is possible to relax some of these constraints to obtain a single pair of densitities that bounds Ha (mz mz for all a and pairs of datasets ~ x'. Specifically, we apply this principle to the substitution relation and subsampling without replacement, as well as subsampling with replacement. Due to the relaxation, these dominating pairs are not necessarily tight. They may however be easier to use in practice than convex conjugation, which requires solving an optimization problem.
63

---

K Recovering known dominating pairs
In this section, we demonstrate that known dominating pairs for the standard combinations of Poisson subsampling under insertion/removal and subsampling without replacement under substitution, as well as subsampling without replacement under insertion/reemoaa, can also be derived via our proposed optimal transport framework.
As before, our contribution are the guarantees themselves. Our contribution is identifying that, guarantees for ADP and RDP, these guarantees can be derived by defining an (optimal) coupling and then identifying worst-case mixture components under pairwise batch distance constraints.
just like mechanism-agnne
K.1 Poisson subsampling and insertion/removal
As discussed in Appendix D it beneficial to partition the insertion removal =+x into two relations:
The insertion relation +. where J =+,x x' implies that there is some & x such that x' x and the removal relation =- where = implies that there some a a such that x' = x. {a).
While we could derive dominating pairs for both relations from scratch, we can use the following result from [0] to reduce our workload:
Lemma K.1. If distributions (P, Q) are a dominating pair for mechanism M under the insertion relation + then (Q, P) are dominating pair under the removal relation =
Next, we use our proposed framework derive the following guarantee in a very natural manner that does not require reasoning about tradeoff functions and optimal testing rules (c.f. proof of Lemma 29 in IT]..
Proposition K.2 (Zhu al. (10). Consider subsampled mechanism M B o S. where S is
Poisson subsampling with subsampling rate r E [o, 1]. assume that (P,Q) are a dominating pair for base mechanism B under the batch insertion relation + Then, (P, (1 - r) rQ) are
dominating pair for M under the dataset insertion relation = and ((1 r] rQ, Q) are
dominating pair M under the dataset removal relation =
Proof. We begin by deriving the dominating pair for the removal relation =_ Consider arbitrary pair x =_ x' and an arbitrary a 2 0. Recall from our proof of the mechanism-agnoosiic Poisson
subsampling guarantee Proposition H.6 that we can construct a dy-compatible coupling show that
Ha (m, m max H ((1 -r)b,
rb rbb. (
subject to E y2+1, v/ y dy (v2 vi (1) < 1, (v
80.
The last constraint is because there is sequence of deletions that will result in insertion. It can be ignored, meaning our optimization problem is equivalent to
max y
Ha((1 r)by + (by)
Using the definition of hockey stick divergence this can be restated as
max Ho - r)by + rbby1bby)
5=--8 yy
(1 r)y (z) + rby(2) -a.0) by (2) dz
max y=-9/
max
JRD
by (z)
(z)
a,, 0 (z) dz
max -2--8
max
(1 - r) + byr (z)
JRD
(2)
--1--)
1-r r by (z) dz
max r
max
(2)
RRD
Forr simplicity, we assume that we have continuous-vall mechanisms, but the same proof strategy can also be used for the more general definition of hockey stick divergence from Appendix D by calculating d((1 r), + rP',)) / dPP,.
64

---

We can now distinguish two cases, based on the value of a' = -
Case I: Assume that a' 0. Then, the integrand is always non-negative, and the objective function
evaluates to a constant r(1 a'). We can thus choose y arbitrarily, because
max Ho ((L - r>yy + rbyllby) r(1 -') Hl. ((1 r)g + rpllg), y=+ y
where p and q the densities of dominating pair (P.
Case Assume that a' 2 Because (P.Q) a dominating pair for the batch insertion relation
+,Y, we know from Lemma K.1 that (Q, P) is dominating pair for the batch removal relation
y. Thus
max ((1 r)bby + (bby)
==-
max r- Ha-(byllbyr)
y=-Ø
Sr Har (allp)
= -o ((1 r)p + rall4)
This shows that ((1 - P)P + +Q Q) is a dominating pair for the removal relation - It then follows from Lemma K.1 that (Q, (1 - P rQ) is dominating pair for the insertion relation
++
Note that case (but not case 2) of Theorem 11 in 110 states that ((1 r)Q r), were dominating pair for the removal relation. This does however appear to be typographical error, since the authors the same symmetry argument (Lemma K.I for their proof.
K.2
Subsampling without replacement and insertion/removal
The proof for the following result is virtually identical to the previous one. They only differ in the coupling which we need to construct, which again highlights the generality and usefulness of our proposed framework.
Proposition K.3 (Zhu al. [T0). Assume dataset space and batch space defined by X {or X. lyl = q}. and finite set A with < N. Consider
P(A) |=| E - Y a subsampled mechanism M = B where S is subsampling without replacement with batch size q, and define aatch-to-datased ratio = / N. assume that (P, Q) are a dominating pair for
( =
S
base mechanism B under the batch substitution relation SAy Then. (P, (1 w) P + w() are
dominating pair for M under the dataset insertion relation = and ((1 w) P uQ, Q) are dominating pair for M under the dataset removal relation -
Proof. As in the previous proof, we begin with removal relation =_ Consider arbitrary pair I = x' and an arbitrary 2 O. Recall from our novel proof of the mechanism-agnoste RDP guarantee for subsampling without replacement and insertion/removal (see Theorem 1.2) that we can construct a doycomitti coupling to show that
Ha (m.rl/m.') I max Ha((1 - w)b 10 wh oo (b)
y
subject to E 22+1 (1) = 1() ( dx 2 ()) S 1, dy (vl (1) 22 1)) < 1.
By definition of the induced distance, this optimization problem is equivalent to max Ha rbby + rbyl(by)) BWay'
We can now go through exactly the same steps as in our derivation of Proposition K.2 every occurrence of ">__" with ">" conclude proof.
replacing
K.3 Subsampling without replacement and substitution
In the case of subsampling without replacement and substitution (as well Poisson subsampling and insertion/removal without partitioning of the neighboring relation) we do not need to provide
65

---

new proof. This is because Zhu et al. [10] prove this result by invoking tight mechanism agnostic subsampling guarantee derived by Balle al. [5] and then applying advanced joint convexity in reverse order (see proof of Proposition 30 in [T0)
As discussed in Appendix G.2 and formalized in Theorem G.2
any guarantee that is derived via the framework from [15] can be equivalently derived by defining (potentially suboptimal) coupling between multiple conditional subsampling distributions. Thus, we know that the guarantee could have equivalently been derived via our proposed framework
Proposition K.4 (Zhu et al. [0]. Consider subsampled mechanism M = S, where S is subsampling without replacement with batch size E N. Assume that (P.Q) are dominating pair for base mechanism B under the batch substitution relation =A,x- Consider arbitrary x =AX x' of size N and define batch-to-de to-tasss ratio q N. Then
[H1(( - w)4 + wpllg) for a 2 (p, (1 - w)p + mgllg)) for 0 < a <<1
Ha (m') &
Note that this result does not immediately specify a dominating pair. However, as shown in 10 one construct a dominating pair via convex conjugation (recall Appendix J.3.1 and Proposition J.3
66

---

L Novel results for dominating pairs
In the following, we formally derive dominating pairs for subsampling with replacement under the substitution relation. We also derive an alternative dominating pair for subsampling without replacement under substitution which does not require convex conjugation (c.f. Appendix K.3) These results are novel in three respects.
Novel contribution 1 - Formal guarantees. Using the dominating pairs we shall shortly derive for privacy accounting was already proposed in []. However, the authors did not provide a formal proof for why they should lead valid privacy guarantees. They only proved that if two pairs of multivariate Gaussians with colinear means were to be a dominating pair then one could use a change of variable and marginalization to reduce them univariate dominating pair (see Appendix B.1 in [ They did not prove why this assumption should hold. A formal proof of this assumption is now enabled by the analysis conducted for solving the group privacy optimization problem in Theorem M.6 (see Appendix(O) (O).
Novel contribution 2 Other base mechanisms. The generality of our solution to the group privacy optimization problem in Theorem (.6ore//M66less us not only derive dominating pairs for Gaussian mechanisms, but also for Laplace mechanisms and randomized response.
Novel contribution 3 Resolving non-constancy via constraint relaxation. Perhaps most impor- tantly, our proposed framework offers a novel perspective on an issue encountered when analyzing subsampling without replacement: While one can derive a tight mechanism-speciiee guarantee depends on different mixture distributions for a < 1 and a 2 1 (see Proposition| K.4 [TO] and our more general discussion in Appendix [..)). Thus, one cannot simply read off a dominating pair from this mechanism-specifie guarantee, as we did with our group privacy bounds. However, as we shall demonstrate, this issue no longer appears when we relax some of the batch distance constraints in our proposed cost function bound from Proposition 3.5 This suggests that this could be a more general approach for addressing this non-constancy issue. While the resultant dominating pairs are not necessarily tight, they may be casier use in practice than the convex conjugation construction from [10).
guarantee, this
L.1 Subsampling without replacement and substitution
We begin with subsampling without replacement to demonstrate the potential benefit of relaxing batch distance constraints determine tractable dominating pairs.
Theorem L.1. Let M = S, where S is subsampling without replacement with batch size q, and B the Gaussian mechanism h + V with h Y + RRD and V ~ (O, o² Define the seseniiiivvyy L2 = maxy=A.ve vy (1) - ff( ll2, where = is the substitution relation. Consider an arbitrary dataset size N E N and define batch-to toahh-t--dttssr ratio w -. Then, for any pair x =Ax x' of size N,
mmmmm S Ha (FF)
(1 (1- w) +) 522 w|lf(() (1- - w) + (((2 .w)
(25)
with univariate normal densities f!=)= NV (i-1), 1), L2). 14²) -N( -(j 1), L2).
Proof. Recall from our proof of the mechanism- subsampling without replacement guaran- construct a dy commatite coupling show that
tee Proposition H.4 that
H (m S max H ((1 - w)b, (1- + wh g [I(1 - w)b v1
+ wb ) 2
subject to y E 22+1 3/ (1) = vi (2)
( 22 (1) - 1, dv (1) w (2) < 1, dr 31 SL
(1)
Next, we relax the constraint between the two components that contain a substituted element: (v) (1))))))))))))))))))))) (2) 2.
We now observe that this optimization problem is identical to the optimization problem from our
group privacy bound (Theorem 3.7) with one insertion (K_ = 1), one deletion (K_ 1), and subsampling rate r = w. The result thus follows immediately from our mechanism-specifee group privacy amplification bound for Gaussian mechanism (Theorem
'Technically, the notion of dominating pairs [00 had not been introduced at this point, which is why the authors discuss vaguer notion of "worst-case distributions". similar to other early work numerical accounting.
67

---

We can generalize this result to other mechanisms by using group privacy amplification bounds for Laplace mechanisms (Theorem M.2) and randomized response mechanisms (Theorem M.2)).
We see that the upper bound Eq. (25) depends on the same pair of mixture distributions for all 2 0. Thus, this pair of mixture distributions is dominating pair for subsampling without replacement under substitution.
L.2 Subsampling with replacement and substitution
Next, we provide the first formal derivation of dominating pairs for subsampling with replacement.
In subsampling with replacement, single element may appear in batch multiple times. To formalize this, we assume a dataset space X C ((A) that is composed of sets (not multisets) of elements from an underlying set A. We further assume a batch space S Pmulti (A) that composed of multisets of elements from A. Given some E Y, we write Ey (a) for the number of times that a appears in We further define the support of batch y E Y as supp(y) = {a Y (g( 2 0}.
Definition L.2. Subsampling with replacement with batch size q has probability mass function
(x) = ( for batches E with supp(y) C x and
y = q-
Given this subsampling scheme, we can use optimal transport to derive the following constrained optimization problem, which we shall then relax and solve:
Theorem L.3. Let M = Bo where is subsampling without replacement with batch size q. and B the Gaussian mechanism h V with h Y - RD and V NO, I² Define the e--sensitivity T = maxy= a. vy (V) - f12 where = is the substitution relation. Consider an arbitrary dataset size N E and define batch-to-dataset ratio w N,
+. Then, for any pair x = x' of size
9+1
9-1
Ha (a(mallma))) S max H y
Σ
bay
Σ
(2)
Wj
j=1
subject to y E ((++))+(+))) v,,,u dv and with weights w, = (+)) (1 +)
(i
(1)
S
u/. Vl, u dr(si (1) 221)) S max((, u).
Proof. By definition of the substitution relation ~ there is some a with a x' and some a' E x' with a' & such that x' {a} U {a').
To simplify indexing, we define zero-based indexed events Ao,... Ag and Eo...., Eg. We define A; to be the event that a is sampled times, i.e., Ev(a) = i. We define Ej to be the event that a' is sampled times, i.e., E, (a)) =j.
By definition subsampling with replacement, we have Ps. wi, and Ps, (E₃) = wy with weights w; (+))*
+1
For dataset size N, we have
(N- ()-1))
if supp(()) C A Ey(a) =i
Sx A.)
otherwise
( N-11
j0-2 1)! 1)! (a))
1
if supp(v) x Ey(a) =
0
otherwise
and
(NN1))+(--))11) q-i
if supp(y) S Ey(a/)=) =j
EE))
0
otherwise
1
18- (q
i)
if supp(y) C ^ Ey(d) = otherwise
N-T
ista' (o))
Note that 8 (y | Ao) = 8z (1 Fg). Further note that 8x Ag) 1(supp(v) = {a} A 1w1 =1
and s (y) Eg)= = 1 [(supp(y) {a') 1 Iyv q].
68

---

Coupling, We now define a coupling 7: ((++1)-(o+1) + R4 that corresponds to the following generative process: We first generate Ui by constructing batch of size q whose elements are all a. Beginning at + 9, we then iteratively generate y from vi by replacing one instance of with an element ä E x: a that is sampled uniformly at random. Finally, we construct the yj by replacing every occurence of a in Vj with a'. More formally,
if y ( fulfills Condition L.4 otherwise.
(l
(2))
N-
Condition L.4. A tuple (L)) yot! ((t1) E yk+t1 fulfills this condition when Sy." (a) (1)
y (a') = y and Vi, 3ā E \ (a) Vi-1 v {aj (ā) and Vi, vā & {a,a')) s (ū)
E a (a) and on (a) = (a)). Uy
Validity. To verify the validity of this coupling, consider an arbitrary and an arbitrary y such that ( (2)) 0. We know that there are (g (q-1i) ()) IIaa (aa)) sequences of yy (1) -1g--11---322 w/th
that could have generated
We further know that there are
possible sequences of
( v........ " that can be generated from " All v/8) are deterministically determined by y We
thus have
Σ
w) (2)) 1 (1)
N -1 (N-T)²
= (gg i)!
La()
āza
(q- i)! II d
N
Sy(a))
52(y)) Ax).
The proof for the 8/") analogous. Compatibility. Finally, it can be easily shown that y is do-compatible coupling (recall Appendix F) Whenever (1) > 0, then
VISis.- K_ dx(v0) (1) (1 dx (10 (1) (s A)))
YO $ S k du (v :V: (1)
(2) dv (16"
(1) supp(s> E2)) =
because we generate the ( from 1 by substituting exactly elements, and construct the y) by substituting exactly elements. Similarly, we have for the pairwise distances that do not involve yo (1)
VO 1 < u S K_ dx(xt") (1) vil
= dv (supp(s | Ar), supp(sa Aa))) = It - ul, (2) yu (2)) dv (supp(sa(( (- supp(s (: Ex))) 11 ul.
VO 1 u K_ (v)
VO u K_ dx(ui") (1) (2))) dx (supp(s. At), supp(sa(( E.))) max (t, u).
The last equality holds for i < because construct (2) from yi
y/u
(1)
need to substitute all
occurrences of a with a' and then substitute u t additional elements with a' It also holds for >> u. because then need to replace occurences of with a' and then replace another occurences with values other than a'.
Applying Corollary F. with (Ai) = Wi. Ps. (E₂) Wy. shows that
Finally, we can relax and solve Theorem L..3 for specific mechanisms, such as the Gaussian mecha- nism:
69

---

Theorem L.5. Let M B S. where S is subsampling with replacement with batch size and B is the Gaussian mechanism h V with Y - R and V ~ ~N, Ip)) Define the lz se-seiiitii T/2 = maxy==,.1 [V] ((//)ll where is the substitution relation. Consider an arbitrary dataset size N E N. Then, for any pair x = x' of size N,
H mmmallmm - Ha
wi
(26)
1=1
with univariate normal densities f = N. (i ((-1),, 1) L2). 11 = N(: - - 1), 0/ L2), and weights x 9 (1 )) p-1
by replacing the last constraint Vt, u: : (v y I maxft, u with a new constraint Vt, dz (1) yu sttw u.
Proof. We first relax the optimization problem in Theorem
This leaves us with
max H
Σ S
wall Σ
(2) Wij
t + and subject to y E y(++))+(++1) V1,t (v v It u/. vt, u. dx(vi") (h with weights w; = (*) (1 (1- -²
We now observe that this optimization problem is identical to the optimization problem from our group privacy bound (Theorem 3.7 with g insertions (K+ ②). q deletions (K_ Q). and different set of weights. The result thus follows immediately from our solution to the group privacy weights.
amplification problem from Theorem 3.7 which did not make any specific assumptions about the
We see that the upper bound Eq. 225 depends on the same pair of mixture distributions for all 2 0. Thus, this pair of mixture distributions is dominating pair for subsampling without replacement under substitution.
70

---

M Tight mechanism-specifie group privacy amplification
In the following, we first prove our generic group privacy amplification guarantee for Poisson subsampling and insertion/removal. which gives us constrained optimization problem whose optimal value bounds Ya (m< Laplace, and randomized response mechanisms. After that, we prove the mechanism-specitn tightness for the resultant guarantees. Finally, we discuss how to evaluate these guarantees numerically.
We then solve this constrained optimization problem for Gaussian,
M.1 Proof of Theorem 3.7
Theorem 3.7. Let M B S. where is Poisson subsampling with rate Let my be the insertion/removal batch relation =2 Then, for all x = K x X', Vo (ma m[ is Le.q.
K-t Σ
K++1
max V. y
bn Binom K-, r)
Σ
b (2) Binom(j 1 | k+trr)
(4)
j=1
subject to constraints y "yk-+K++ as well as vl [1,2), Vt, u dr(v ( (2 S 1t u/. and Vt, u: : dr (v())) (1) y - (t - 1) 1)-
Proof. By definition of the "insert K+ remove K_ "_""reii relation K K- x there is some inserted set 9+ E size K+ with g+ n x = 0 and some removed set g- S x of size K_ with g- n x' = such that x' 9
To simplify indexing, we define zero-based indexed events Ag, .u.....AAs AK_ and Ep, Ek_, We define A, to be the event that i removed elements are sampled, i.e. ly n -n-g-g--- i. We define E, to be the event that j inserted elements are sampled, i.e. ly n 9+1 = j.
By definition of Poisson subsampling, we have Ps, (A:) = Binom(i K K_,r), and Ps, (Eş) = Binom(j K r). We further have
rlll(1 - 1=) Binom(i K_ K- if C lg- nyl =
Sx A.) =
otherwise
11all-(1 r) - (K
if y S x nyl= =i
0
otherwise
and
(rlu((1 (1 -r)lal-bul |inom(i K+,r)-1
of =
Se (y Ej)
0
otherwise
(plvl-1(1 (om1->(1-))1---11 11))) (KT))
if s' A A nyl=
0
otherwise
Note that syr Eo) = (y Ao).
Coupling, We now define a coupling 7 (KK++))(K++)) + R., that corresponds the following generative process: We first generate (1) by sampling a batch that does not contain any inserted or removed elements via Poisson subsampling from x (..... We then let y yo Finally, we sample uniformly at random an order in which we include removed elements from g- and inserted elements from g+ to iteratively construct batches from (A))s>1 and (E,);>1, respectively. More formally,
4) = sn (10 Ao) (K4! -_!)- if ()) fulfills Condition M. otherwise.
Condition M.I. tuple (1) E yk-+1 (2) E 4K++ fulfills this condition when (1) (2) (1) (1)
yo y0
and Vi: : 3a_ E 9- \b Met vt Ufaf} and Vj Bay E 9+ \ \v)²) / v U [(a
(2) (2)
(2)
71

---

Validity. We can verify the validity of this coupling as follows:
For Ao and every y with (y Ao) > O, there are exactly K+1 K_! combinations with vo for which (3) > 0. We thus have Σ Eyerk, IK_ 12 1 ( = y))(v) = S Ao). The proof for Eo analogous.
Next, consider an arbitrary A, with 0 < is K For every y with (2 | AA) > 0, there are exactly
i! (K- - -)! k combinations with y/ (1) y for which ( > because there are (a) orders in which the removed elements leading up to i could have been sampled (b) (K- -K--a é!! permutations for the remaining removed elements (c) K+ permutations for the inserted elements that are only
relevant for (2)), We thus have
Σ DEY"
1 [w (1) = yl7(y)
(il (K- - (+!) sx (10 (1) An)) (K+!- K_!)-
(il (K_ - 6)! k+!) ,106" ") (1 r) |a| |al--16 180 21 ((K-), (K4! K_!)-
=il(K- - i)! -116 (1 - r) |-| 106 -(K-) ,(__))
-0116'011 --)=11-12 (-(-). (K_) -1
K_ -1
-plllli(1 (11 - r) bl (K -i)
For the last step, we have used that yu contains 0 of the removed elements from g-, whereas contains of the removed elements.
(1)
The proof for E, with 0 j S K+ is analogous.
Compatibility. Finally, it can be easily shown that y is a dy- co-copitii coupling (recall Appendix F). Whenever 7yy) > 0, then
V1 Liisk K_ dx(vo' .v, ") = dx (vo" (1)
(1)
(vo", supp((s())) A.)) i,
YA SISK dr(ub (1) ()(2)) dx (v)")
(1) supp(s E2)) =j
because we generate the y," (1) from yo by inserting exactly elements, and construct the yj by inserting exactly j elements. Similarly, we have for the pairwise distances that do not involve yo w0 t s K_ dz(vl") (1) (( dz (supp(s>< At), supp(s>( AAw)) It u/..
VO < t < u < K dz(x) (2) (22)) dy (supp(s sw (- Es), supp(s> (- E.))) = =It ul. VA S f < u < K_ dv(1)) (1) v dr (supp(sa(-) At), supp(s (s (- E.))) = + u. The last equality holds because construct y0²² from (2) we need remove / elements and insert elements.
The result then follows from Corollary F.7 Ps. (A.) Binom(i | K_,r), (E)) Binom K+, r), and reverting back to one-based indexing.
M.2 Instantiations
Next, we can solve the derived optimization problem. In this section, we only provide proof sketches in which we reduce the optimization problem over batches optimization problem the means of multiple Gaussian, Laplace, or Bernoulli random variables. Because solving these problems requires some further exposition, we then refer the reader Appendix
M.2.1 Gaussian mechanism guarantee
Theorem 3.8 Let M B o S, where is Poisson subsampling with rate r, and B is the Gaussian mechanism h + V with h Y + DDD and V oO)) Define the ez-sensitivity L2
72

---

y l1f(v) f//lll2 Then for all x KKiK-, x', V (a(mzll is l.eq.
K-+1
K++1
La a
Σ 1 Binom K-
Binon - K4,r)
j=1
with univariate normal densities f(") = (i 1),0 L2), 13 = -N(: - 1), L2). Proof sketch.
Recall from Theorem
3.7
that we need solve the optimization problem
+1
max Va
Σ
wi
(1)
b
w
b (2) Ms
y
i=1
j=1
subject to y E (((K +1), v1, u dx
(1
< - u/ vt, u de dy(ui yo ( (t-1)
(u 1). and with w!! Binom 1 K_ r). w Binom K),
Let p = h(, and 2 = h(y,))) Since we do not have any additional information about h beyond its fz-sensitivity, we have to make the worst-case assumption that the f 3 are
(1) (2)
arbitrary vectors constrained by u 1|m 1 112 - L2/ u/. Vl, 1 (1) tr 1|2 S T2 ((1 1) + (u 1)),
Thus, the optimization problem is equivalent to
K-+1
K++1
max (2
V
(1) wi
N(-1
p , 22)l
Σ
wj
a N(- uj 1 , L2)
j=1
subject to vl, 4: [| p 112 S jt - u/. Vt. u: ||
μ (2) 112 < (t - + 1).
In Appendix 0 rigorously prove that the maximum is attained by co-linear, equidistant means that fulfill these distance constraints exactly. Thus, we can perform a coordinate transformation such that
μ1 0 and f4; (1) (i 1)e1 and fu (2) (j 1)e, with firs-component indicator vector e1 R... Since the likelihood ratio in V. is Gaussian with zero mean in all but the first dimension, we can marginalize all other dimensions out obtain our one-dimensional result (cf. Appendix O
M.2.2 Laplace mechanism guarantee
Theorem M.2. Let M B S. where S is Poisson subsampling with rate r, and B is the Laplacian mechanism h + V with h Y - Rd and V Lap(0, 0² ID), with location 0 R D and diagonal scale matrix AID DRD which adds independent Laplacian noise each dimension. Define the l1 fi-sensitivity L1 = max (l) f(y')l1. Then, for all x = KK.KK_ x', W Va (ma)l (mm)) is
l.e.q.
K-+1 Σ
K++1
Va
" Binommi- k_,,,,
Σ
(22)
.)).Bonojjj k+,rr)
with univariate Laplace densities
= Lap(- | (i 1), L1). F,
= -ύ- - 1), L1).
Proof sketch. Recall from Theorem
3.7 that we need solve the optimization problem
K_+1 Σ
K++1
V,
w
(1)
Σ
b (3)
w
(2)
Mj
subject to y E +K+ Vl,t, u dy dy
(1)
< |t - u/. Vt, u : dy (1)
y3t (2)) S (t 1)+ (u-1).
3/4
and with w. Binom(i - 1 K r), w
(2)
Binom (j 1 K K+,
73

---

Let pi (1) = m) and 14 ). Since we do not have any additional information about
h beyond its l ---sesiitivity,
have make the worst-case assumption that the p4 M
(1) (2)
arbitrary vectors constrained by Vl, I| - 1|1 s L1lt u/. Vt, 11 (2) pun 111 - L1 ((t- - 1) + (u - 1)),
(2)
Thus, the optimization problem is equivalent to.
+1 Lap(-
ADD / L1) w 11 K Σ
max 1 (193)
V.
Σ
14 (1)
Lap(: 1y , L1) wjj
(2)
(2)
subject to vl,4, u: |1 1 S |t- u/. vl, u: || 1 p S (1 - + (u-1) 1).
In Appendix O we rigorously show that the maximum is attained by collinear, equidistant vectors along a single coordinate axis that leave no slack on the pairwise distance constraints. This then allows us to marginalize out all remaining dimensions to obtain our guarantee in terms of univariate Laplace densitities (see Appendix )
M.2.3 Randomized response mechanism guarantee
Theorem M.3. Let B be the randomized response mechanism 1h (1 V) with h Y 10, V ~ Bernoulli(f), and true response probability 0 E [0. Les M B o S be the corresponding subsampled mechanism, where S is Poisson subsampling with rate Finally, let my be the insertion/removal relation E.Y. Then, for all x ~ KK x', W. mma)) is L.eq.
max v ((1((1 - -ern) 0) + w Bern(( []] - (2) Bern( (0) + ( Bern( | 11)))
subject to {0, 1 0}, and with w(l) = - (1 r) and w =1 - (1 - -)) K+
Proof sketch. Recall from Theorem
3.7 that we need to solve the optimization problem
K=+1
K++1
Va
Σ
b
m)
mi
(11
Σ
w
(2)
21
subject y kK+ Vl,t, u dy dy( (1)
y/ S |t u/. Vt, a dy (x( (1 s (t-1))+uu 1).
and with wi Binom(i - 1 K r), w = Binom (j 1 K K+ r).
Let u4") h(, ) and 11)) hyy ( Since we do not have any additional information about
())
beyond mapping to {0, 13, we have to make the worst-case assumption that the p ,r] are only constrained by /12 = 1i
Thus, the optimization problem is equivalent to.
+1
K
max 1elts (4(2)
V
Bern(- (2)) w 2
Σ
Bern (: ) w
subject to (2)
111 (2)
In Appendix O rigorously show that the maximum is attained whenever all μ (1) with i >> 1 are
simultaneously set to either or 1, and all (1) with > are set to the opposite value.
(2)
Note that this guarantee can be evaluated in 011) We need to iterate over two possible values of r, and evaluating the corresponding V requires summing over two values {0,11] 1}.
M.3 Tightness
Next, we prove tightness by constructing datasets and underlying functions such that the corre- sponding base mechanism B exactly attains the different bounds under subsampling scheme S.
74

---

M.3.1 Gaussian mechanism tightness
Theorem M.4. Let S be Poisson subsampling with rate E [0, 1] and 8 E [0, 1] be some true response probability. There exists a dataset space X and batch space (Y.3), fulfillng the constraints in Definition D.4 well pair of datasets x K K- _x c' and function h Y + IR with
lz-sensitivity La, such that the corresponding subsampled Gaussian mechanism M = Bo fulfills
K-+1
K++1
Va (mmallmma = Va
Σ
f
.i.nonmi - 1_1KK_, -),
Σ
5 Binom(j - K+ 11(t,)))
==1
with univariate normal densities
= = (1- 1), 12), 13 = NN 1 -(j-1),0 L2).
Proof. Let = P(N). Consider an arbitrary x E X and select arbitrary deleted elements C s,
with |ol K_ and arbitrary inserted elements g X Define x' 9- U 9+-
We now construct counting function for that leads to the largest possible divergence under the sensitivity constraint. We define function h as follows:
(i 1) ei L2
lg nyl =i-1
h(y) 1 (jj e1b2
if 19 Nyl -j-1
with first-componett indicator vector 61 RR.
By construction, PM,, is mixture distributions with K + 1 components, each corresponding to a size of subset of g- that is included in batch y. These cases each have probability Binom (i K_,r) under subsampling distributions Ps_. Each component has distribution W( (i - 1), e: e1 o ID).
Analogously, Pm., is the other desired mixture of Gaussians.
As in our previous proof, we can now notice that the likelihood ratio Va is constant in all but the first dimension. We can thus marginalize out the remaining dimensions to obtain our result. O
M.3.2 Laplace mechanism tightness
Theorem M.S. Let S be Poisson subsampling with rate r E [0, 1] and 0 E 10 be some true response probability. There exists a dataset space X and a batch space (V, .)) fulfilling the constraints
in Definition D.4 as well a pair of datasets x KKi x x', and a function : Y - IRP with l sensiitivity L1, such that the corresponding subsampled Laplace mechanism M B o S fulfills
K Σ
K++1 Σ ==1
V (m=llm))) Va
f.Th "..inomme - K- K-
(2)
Binom - K4.r)
with univariate Laplace densities p! Lap(- (i -i- 1), L1). 1,30 Lap(- -i--i) 1), / L1).
Proof. The proof is identical to that of the tightness guarantee from Theorem M.4 We can construct exactly the same counting function that indicates the number of inserted or removed element that appear in a batch sampled from S₃ and Sg,, respectively.
As in our previous proof, first dimension. We can thus marginalize out the remaining dimensions to obtain our result.
now notice that the likelihood ratio in V. is constant in all but the
M.3.3 Randomized response mechanism tightness
Theorem M.6. Let S be Poisson subsampling with rate E [0, and 0 E [0, 1] be some true the constraints
response probability. There exists a dataset space X and a batch space in Definition D.4, well pair of datasets x 2K.,K_xx x I', and function h. Y - 0, such that the corresponding subsampled randomized response mechanism M = B o S fulfills
V. Vm(mm)lmm)
-max V. (a((1 (B))) (0) + to ( [)]l([ - (2 Bern(. () + w Bern(- | 7))
subject {0, 1 0}, and with (1) 1 - (1 - r and (2) 1 - (1 K+
75

---

Proof. The following proof is largely identical to our randomized response tightness proof for subsampling without replacement from Appendix 1.3
Let X = P(N). Consider an arbitrary x E X and select arbitrary deleted elements S 2, with ggl = K_ and arbitrary inserted elements g X x. Define x'
U++
Assume w.l.o.g. that the divergence is maximized by =
We now construct an indicator function h Y + {0, 1} for and a' that leads to the largest possible divergence.
h(y) 1 (g-
y +0
0 otherwise.
By construction of h, the corresponding base mechanism pmf is
Bern 0)
y n (g-
(=) = Bern (z 0)
gyng
Bern(z 1 0)
otherwise.
Under the distribution of S(x), the first case occurs with probability (1 - k)K and the second case occurs with probability (1 - r) K- Under the distribution S(x'), the first case occurs with probability (I r)* *+ and the second case occurs with probability 1 (1 r) r) We thus have
(2)²) = (1 - Bern(z 2 0) + (h) Bern(2 2 (),
my (z) = (x) Bern(= 0) + ( Bern(e 1 0), which exactly attains the desired divergence when is the optimal value.
M.4
Numerical evaluation
Evidently, we do not have closed-form analytical expression for our tight mechanism-speciff group privacy bounds. However, we can evaluate them to arbitrary precision using standard techniques from privacy accounting literature.
M.4.1 Gaussian mechanism
ADP. To evaluate the guarantee from Theorem 3.8
we can use Lemma from [00. which generalizes an alternative characterization of privacy profiles from (74] to dominating pairs. Let P,Q be the dominating pair of two univariate Gaussian mixtures. Define privacy loss random variables p(Z) with Z P and LQ
LP.Q
z(Z) with Z Q. Then
7(2)
p(Z)
(pll)) S Pr[LP,Q log(a))
<
Because the privacy loss between the Gaussian mixtures is monotonically increasing [ one can perform a change of variables via a binary search for a 2 such that log( ( z log(a). By picking one of the two search boundaries, one can either over- or under-approximate the hockey stick
divergence (see, e.g., g (44).
RDP via quadrature. To evaluate the guarantee for RDP, we can simply use numerical quadrature. This be done efficiently because only need to integrate approach was already proposed and used in Abadi et al. [6]' work on moments accounting.
univariate Gaussians. This
RDP via expansion. For the special case of K_ K and K, 0. one can also use multinomial
expansion (similar to prior work on RDP subsampling from 28 30 We have
Σ wk Ni pa, 021)
K
K ( Ni
Σ
a
II
w
mi I mas
OTT
lo...., lK
lot.+
k==
K II
K
Σ
I N(2 mb, o k=
Jo...., lx
lot
k=
76

---

Using quadratic expansion, we have
K
II
(/ | uu, o2
k=
=N
1 02I
lx pk,
exp
2
exp
20
1
E I
Since only the first factor depends on our problem reduces to computing the divergence
(N<21
lx Us o²1
V a
N
<1
2
[IV (z (=1(=00011)
for different 4. This can be done in closed form, shown in 77]
M.4.2 Laplace mechanism
ADP. Because the privacy loss constant on (-o0, - K.), ). monotonically increasing on [-K K_] and constant on (o), we again the same bisection method.
RDP. As with the Gaussian mechanism, we can evaluate the bound via univariate numerical quadrature. Because the privacy loss is non-smooth at the component means {-K+,-K. 1,..., 0, .,,.,..,A K_ we partition these means and integrate over each interval separately.
M.4.3 Randomized response mechanism
The guarantee for randomized smoothing can be evaluated exactly in O(1). We just need to iterate over the two options 7 E {0, 1}, and each one evaluate the divergence on space {0, 1}, which only requires evaluating two fractions and two sums.
77

---

N Tight mechanism-agnostic group privacy amplification
In this section, we apply the framework from [5] which we summarized Appendix G.I to the group privacy setting. We then show the tightness of the resultant guarantees, using the same proof strategy as in Section of [15]. We then demonstrate that directly related our tight mechanism-specife, guarantee through joint convexity. Finally, we derive qualitatively similar guarantee for RDP.
For this discussion, we focus on the special case where all of the K group members collaboratively agree insert their data (K+ K, K_ 0) delete their data (K- K_ K), so that the partition induced by the maximal coupling remains interpretable. We define the corresponding neighboring relation
K ((,,x' EX CCCAAAE |-] E x² +
1 (27)
In our experiments, we only evaluate the baseline for (K+ K, K_ = 0) and (K+ = - while we evaluate method for all K K_ K and take the maximum. This evaluation favors the baseline.
N.1 ADP guarantee
Proposition N.1. Let M = B o S, where S is Poisson subsampling with rate Let =y be the insertion/removal batch relation ~2,. Then, for all x =** x' and all 2
K
H Hexpler) (ma (//l ) S
Binom(k K,r) 6g.
with 5' log(l (1 (1 r) k)) (ee 1)) and group privacy parameters
8% max Hexp(e) (by (by:) dz(v.3') k. v.3/
Proof. Case 1: Deletion. We first consider the case where K elements are deleted, i.c., there is some deleted set g C of size K with g- n x = 0 such that x' = x 9.
The partition induced by the maximal coupling is
(v( (1 s) (v A2) + ws (y A1)
$2 (1) = - (1 A2) + ws (y A2).
where Ag {y y ng is the event that no element of is sampled, Ai is its complement, and w (1 - Ps. (A1). We use these indices for A₂ and A₁ because advanced joint convexity will later reverse their order.
Applying advanced joint convexity (see Proposition G.I and joint convexity shows that
Hexp(e') (mz)) S w- Hexp(e)
Σ by NEY
sn
ADII Σ by sx
A2)
(28)
DEY
Next, we can bound this mixture divergence by constructing coupling invoking Theorem 3.3 with the special case V Hexp(e)) For this, notice that
plul 1=11ll
if A otherwise.
s A1))
0
and
(1- ( 10'11
A
sy A₂) = ey (y)
otherwise.
as can be seen by the fact that w is the total variation distance of s., and sy, and that sz Az) and sz(y) A1) have disjoint support
78

---

Coupling, We define coupling y Y² - [0, 1] that corresponds to the following generative process: We first sample yL8) from (y A2). We then sample from a truncated binomial distribution how many elements from group should be included. Given this k, we sample uniformly at random g g from all size-k subsets of g and let yyt) + y(2)) U g. Formally this defined by
K (1 A2) + --inoom (ly ( ngll K,r) (19ngg))
under Condition N.2
0
otherwise.
Condition N.2. A tuple y()) Y, y() E Y fulfills this condition when there exists S 9 with |ø| 2 1 such that y() = y(8) Ug.
Validity. Next, we verify the validity of this coupling. For every y there is exactly one y such that (2) y((2) > O, namely y(2) = y( ' g'. Thus,
En (2) = ( 1 A2) _ Binom(ly ngl K,r) ( K y(3)
(gn (gK)) )
-rlv'sl (1 - r)-r) (1-r)(=a--- 1''1- 1
planel (1 - r) lunggl
w
=3 A1))
For every y22) there exactly (x)
batches y such that 7() y(1)) and (y()) ng Al.
Thus,
Σr .0)
Σ
K
K
1 Su Sy A2)
Binom K,r)
K -1
k
w
k
y(a)
K
= (y/
A2)
Binom K,
=s (y
A2).
Now that have proven the validity of the coupling, we can apply the optimal transport bound (Theorem 3.3) to Eq. 28 in order to prove
[esple)(mzlllng Sw-
Σ Tl(),
(2))))
K
K 1
(K)
K -1
Binom(k K,r)
w
K
Binom
K,r) 65-
Case 2: Insertion. In this case, the partition induced by the maximal coupling
$ (v) (1 ( A1) + ws (y/ A2) $y (y) = - -1- A1) + ws A1),
which is identical the previous partition, up to symmetry. The proof identical, except for changes in indexing.
Taking the maximum over both guarantees yields the result.
N.2 Tightness of ADP guarantee
Proposition N.3. Let S be Poisson subsampling with rate r. Let mx be the insertion/removal batch relation ~. Then, for all -** x' and all > 0, there exists worst-case base mechanism B
79

---

such that the corresponding subsampled mechanism M = B a S fulfills
K
Hl eexp(e (mx (m Binom(k K,r) ob.
(29)
with e' log(1 (1 (1-r)k) (e 1)) and group privacy parameters
8R = max Hesp(e) (by (bbr) s.1. dr(y,y') s k. 9.3/
Proof. To show tightness of the bound, we notice that the bound === Binom K,r) & is identical the bound for subsampling with replacement from [13] except for the numeric value of the weights in the weighted sum. We can thus use exactly the same proof strategy.
Assume w.l.o.g. that and x' = r U Consider an arbitrary E and define an arbitrary true response probability 0 E [0, Further define the randomized membership base mechanism
in the insertion case, i.e., there is some y of size K with g x
B(y) [1ly > 0] - (1 VVI
with V (0) is easy to verify 15 that 64 vh(()) = max 1 60 (1- (1)))), We thus have for the r.h.s. of Eq. 29
Binom(k K,r) 6n Binom(k] K,r) (e)(e) w (ha))).
Because Poisson subsampling is a "natural subsampling" 15
scheme that only yields elements from
the dataset it applied to, follows from Lemma 12 of [15 that also
H Hexp(e') (my = w- (o))).
N.3 Relation tight mechanism-speeific bound
In the following, we show that this mechanism-agnostic guarantee implicitly upper bounds our tight mechanism-speeiffe guarantee via joint convexity. Note that this is qualitatively different from our discussion in Appendix G There we showed, that the mechanism-agnostic guarantees can be derived from mechanism-speecffe bounds that only use binary partitioning of the batch space (unlike the mechanism-specific guarante considered here). We show this result w.l.o.g. for K_ = 0 and K+ K.
Theorem N.4. Let B: - be an arbtirary base mechanism. Let () W and (2) 4K+1
be arbitrary tuples of batches that fulfill VI, t, u dy (y] (!) I [t-u), and Vt, dr(y) (1) y S (t 1)+ + (u- 1). Then, for
K+1
K
Hal
b bwll
Σ
b (a)
Binom(j K,r)
Binom K,r) (a(
with w (1 R) a' 1 w(a 1) and group privacy parameters
(x) = max Ho (b,,116b))))) s.s. dx(y.8') S k.
v.y"
80

---

Proof. We can apply joint convexity to show
K+1
Ha'
6 mll
b
Binom(j K,r))
(30)
vi
K+1 b (2)
( Binom(j- [,,KK K,r))
= =Ha'
b M1
w)
+
b Ms
(31)
21
==2
=Ha'
b mwll
K+1
Σ
(1- (1-w) w) ( + w by(z)) (
--Binoo(j - -
K,r))
(32)
Mi
j=2
K+1
Binom() - K,r) Hor (Dypoll (11- w) w by + w ..,b.,)))
(33)
J=2
The result then immediately follows from advanced joint convexity (see Proposition G.1 and joint convexity.
N.4 RDP guarantee
For RDP, we can obtain qualitatively similar guarantee by simply applying the known mechanism-
agnostic RDP subsampling guarantee for Poisson subsampling from [29 33) to each of the K
divergences (although we could also derive this RDP guarantee from scratch optimal transport) in Eq. 33 of the previous derivation.
Theorem N.5. Let M
S, where S is Poisson subsampling with rate r. Let my be the insertion/removal batch relation 22, Then, for all K x' and all >> 0
K
Aa Mammmelle (
<
Binom K, K,r) 2.
Σ 1=
a w w (x(1)
1=
with w = (1 - (1- ) and group privacy parameters
(x()) = max Ar(by)lby)) s.t. dr(y. v/) 1 k.
2.3
The factor 2 in Theorem N.5 can be eliminated for distributions with particular symmetries (see Theorem 5 in (29] or bounded Pearson- Pearson-Vajda X apseudo-divergenn (see Theorem 8 in (30). We thus do not include the factor when using this amplification guarantee as baseline in our experiments.
N.5 Asymptotic RDP guarantees
our focus is on tight bounds that can be explicitly computed. However, analyzing the asymptotic behavior of these bounds provide potentially useful high-level picture of their behavior. As discussed in the previous section, and as can be seen from Eq. 333 Rényi
As mentioned in Section 3.1
divergence in the group privacy setting is bounded by a weighted sum of Rényi divergences between a single distribution and a mixture of two distributions. For the special case of additive Gaussian mechanisms with global sensitivity L. this bound is equivalent (see Appendix A of [30) to
K
Binom K,r) 2 Aa (N(O0, [)(( - w w),( w N(1, o (k ())) (34)
Asymptotic bounds Rényi divergences with one two components have been derived in prior work on privacy accounting [6] 28 48) We can apply these asymptotic bounds to each summand.
For instance (see Lemma 5 in 66):
Proposition N.6. Abadi et al. 10 Let 2 1 and S
1.
Then, for any positive integer S
165
2 In
1,
Aa (1(0 ()N((, + N(1 x La(a - 1) + 0 03).
(1 2)0z
81

---

Applying Proposition N.6 to Eq. yields the following asymptotic bound for RDP group privacy:
Theorem N.7. Let M = B o S. where S is Poisson subsampling with rate v and B is an additive gaussian mechanism with global sensitivity L under the insertion/removal relation = Consider arbitrary datasets a = = x'. Define weight w = (1 (1 - r))) K) 1f 2 k. and w S 16 holds for any positive integer a
then
ET In (1)) that
we
K
1LL2g 1)
(a
Binom K,r) 2 (1 ww- + O 02).
k=
Alternatively, one could apply the asymptotic bound from Theorem 38 from 48 to each summand. we were to instead consider group privacy under dataset-level substitutions, where each summand would include divergence between two mixtures with two components, we could instead use the asymptotic bounds from Appendix C of [28].
82

---

O Worst-case mixture components
0.1 Gaussian and Laplacian mixtures
We outline self-contained and extendable proving strategy which we
find dominat- ing pairs of Gaussian and Laplacian mixtures given divergences of the form (P(())) = JR f (P(x). -Q)))) dæ, where f is (not necessarily strictly) convex and increasing in both ar- guments. Our two main examples of the hockey stick divergence Va = Ha and (scaled and exponentiated) Rényi divergence Va = Aa special cases with faz y) max ay, 0} and f(z v) x" (-y) respectively. Throughout the subsection, we use M, N to denote the sets of means of the mixtures P. Q. We start with two general lemmata before treating the Gaussian and Laplacian mixture cases in particular. Together, they provide a constructive toolset to connect any
mixture pair with means (M, N) dominating mixture pair with means (M*, N via path of geometric transformations (M, N) (M (()) + - (M", N concretely, these
mirroring the means of the two mixtures onto opposite sides of hyperplane, and pushing such hyperplane-separatee means further away along the hyperplane normal.
In the first part of this section, we prove that the divergence can only stay equal or grow under any such transformation. Afterwards, construct explicit path of transformations that maps any Gaussian, as well as any Laplacian mixture onto a dominating pair which is feasible under the pairwise distance constraints discussed in Appendix M.2
Lemma O.1. Given E {1,2}, consider two mixtures of the form Par(x) = En wxP(l<= (kllz), Qx( E wxp(l1æ uxllp) with means in M {μo: .... pK) RD, N {vo, ..., PK} C RD and a decreasing p: ER + [0, Consider all hyperplanes which contain zero and are normal to L2-unit vectors ñt E Hy. where
(1) H1 = (or 0 < K ( (+,-))U (01), 10 S i K, (t:
(2) H2 SD, the unit D-sphere.
(x nx")) < 0} and upper half-space R (x e and define the lower half-space R = fxc E R
RD| 1(x n) > 0}.
Consider the map
DAARD--A RR
x x
1 (z)) x)
which mirror-reflect the lower into the upper half-space, and its image M = -R R. and N CRP \ R
The reflected pair of mixtures has equal greater divergence:
La (1N:11QN:,)) V. (PMllQN).
Remark O.2. Lemma 0.1 applies to Laplacian and Gaussian mixtures with p -1 and p respectively.
Proof. We will need the following lemma.
Lemma O.3. Given p E {1,2). hyperplane normal to ñ Hp. and points I1, x2 E R.,, we have
((x1)) (x2) I || x2 llp ((x1)% (x2) = ||=| - x2 llp
if E A V (x1 E E A R
else.
Corollary 0.4. If the sets M, N are feasible under pairwise p-norm distance constraints, then so are M2, N'
Proof of Lemma 0.3 If sign(n" æ1) = sinn(nz 22)) then ( (-)2, acts uniformly both vectors and the condition clearly holds. Else, assume w.l.o.g. that æ2 R,A We start with the case 1.
83

---

First, assume ń E faēē |0 K,0 E [+.-}} Since (-), now acts only on vector component
i, we can write (1(x)); 1a (a2)% 1 - ||| - 02l11 ||ē" æ1 12,xx2l x211 - lēī Φ₁ - ē.¹ ويه S by the inverse triangle inequality.
Now assume instead that á E { v2 ( + o2āE) S i + - D, E (+1,-1))
Now, (+ 1/ acts only vector components i and Thus, l1(=1) (a22)/ 11 || æ2||
[| [(x1), 1/2, (#2)) [| [x] æ2]]| || where x(6.5) denotes projection onto the subspace spanned by the basis vectors é; éy. is useful to write
max la |m ((a))% )/2 (a22) 06(-1+110
|a
Fij [(01) (222%al
Tid [0) 02 + +(22() x2)
max o
The argument of the max function admits two cases. Either, o² (Fr 0, in which case Jo" Tii [(11)// - (x2))al o mJj the inverse triangle inequality,
[x] =22]l. In the other case, Ti.o - 32mm m. Then, by
2
oo Tis [(11)n - (x2)/al = V2
tň² σ1 F
x2
+ 2n
2n"x2
22
+n x1 + +n x2
V2
2
2
V2 + (1 x1 - In x2 |]| 5
V2" n (x) x2) = =1o TT.
x2
For completeness, we also prove p= 2. By invariance of the scalar product under mirror reflection,
|ay x/2 12 x: 01 25L x/2
2x: 2/2 a 21 2z3 x2 2x x2 2(n" x2) m1)
[ --22222 22 + 2(n x22 (n
x - 2 22112-
We recall the notation introduced at the start of the section, V. (PIIQ) - JR (P(z), da, where we assume an integrand f that is convex in both arguments. The statement of Lemma 0.1 will follow from the next lemma, which informally states that at any point in the upper half-space, the mirror-reflection of means contained in M causes an increase of the integrand f (PM (a), Q (z:) which dominates the corresponding decrease at the mirror image point x' in the lower half-space.
Lemma O.5. Given hyperplane normal á E Hp as defined in Lemma 0.1 as well as any point , along with its mirror image x' 22 2 (x. n) R, the change of I satisfies
s (PMg(()), -Qx", (2z) - -Qx()))
+ f (PMr (x'), -QN (z0) - (Px(2x', - 2Nx(x')) (xx 2 0.
Proof of Lemma 0.3
We introduce the following notation,
Po(x) ==
Σ
wup(l< [kllp))
Qo(æ)= == Σ
waP([10 vxell),
P.EMAR R
8P(x)= = Σ
whP((x=-Mslpp)
-
5Q(x)= = Σ
(xp((1x-vzlll))
HAEMOR
MENNEE
thus decomposing the densities into part that stays fixed and part that gets mirror-reflected Using Lemma 0.3 and the monotonicity requirement on p. we can directly verify that
Po(x) 2 Po(x"), 8P(x) S 6P(x')
(35)
(o(x)) 2 (x')..
-8Q(x) < -0Q(2').
(36)
Using invariance of distances under simultancous mirroring of both vectors, we rewrite the expression of the lemma
(P)(z) - - -(() Q0)
[Q(=)]
((t))))))())))))((())-- sQ(x))) - (Po(=') + QQ(('') 8Q(x))
The statement of the lemma follows from convexity of f in both arguments by Jensen's 's inequality.
84

---

We now proceed to prove Lemma
0.1 The difference of divergences can be rewritten as
Va PMg 1Qwx.. Va (PM)
/
RRD [s (PMr.. (z)) (Mg (00) (x) - (P) dx
Sog [r (Parg, (20), -QNIA (2) - (P(r)()) -Qx Q2((x))) de
[ (Par (2r), -QNLA (1)) - (P(M)()) -Nx(m)) de
f [ (Paz (a')) (w)_(())) -1 (Paa(a))) QNx(()))))(()))
R
[ Pagg (a:), - -NNS, (1)) (PM (Qx())) de
0
Apart from Lemma 0.5 we used the fact that mirror reflection has a unit absolute Jacobian determi- nant, and that the hyperplane, a null set, does not contribute to the integral.
Lemma 0.I shows that
construct dominating mixture by mirroring all means onto opposite
sides of a suitable hyperplane. This is exactly the condition under which the follow-up transform
discussed in the next lemma yields equal or greater divergence. We slightly change perspective and
consider the means of both mixtures as a joint vector. Given two sets of means M = {1o,
14K h
N {vo, .... PK} we define (in arbitrary ordering). μ (Po..... MK, Po. .... 2x) E F C
[Dx(K+K) where F denotes the region feasible under the distance constraints. With this implicit mapping (M, N) ++ la between sets and vectors of means, we can treat the divergence as a function
Va 1 JRP [ær ft)dæ with integrand fxx, p1) == (PMM(m)) -((=)). Now we can state:
Lemma O.6. For E [1,2], let i E Hp be normal vector, M, N with corresponding vector Ps as above be two sets of means for which M I R and N n R_ are empty (i.e., the hyperplane separates the two sets), and let V. denote either Na or Ha-
Then, the normal directional derivatives of the divergence with respect to the means ir and vs are nonnegative for all I E E{,, fI,..., K),, i E K),
(md d V. V. (1) = lim 5-0
1 V ((po..... M4 .ñ.....,k.) V. (11) 2 0
dlu) Vo (4):= lim - Va ((Po,..., .ñ. px)) Ua (w)) 2 0.
1
8-0 g
In the case Va Har the above expressions are instead defined in the sense of weak derivatives.
The lemma quite intuitive: once both sets of means are already separated by a hyperplane, pushing them apart in the normal direction, thereby increasing the margin to the hyperplane, never decreases the divergence. As we will only ever use the directional derivatives within line integrals, the weak sense in which the lemma holds for V. Ha is sufficient for our purposes.
We first check that for all a E R and fa E F, the derivative 0 (possibly in the weak sense) exists and is dominated by an integrable function. In the case of Gaussian or Laplacian mixtures and V, A., existence of the derivative is clear. For Gaussian mixtures, the integrability condition holds since 0 O (exxp( ( ||===11133 2=(())), for Laplacian mixtures 0,f O(exp( ((exp(-1aa01) || since the privacy loss factor in the integrand eventually becomes constant. the case V. = H.. has a weak derivative 0 = 1 On
Proof of Lemma 0.6
aQ), which agrees with derivative except where the latter is not defined (i.c., the null set of means and the boundary of exact DP). Integrability
85

---

follows again from 0nf O(exp(-1(z11)) In the case of v. = Aa.
Va (1²)
[
wxp(l1x - malle) 07
1-a
{
d(mi)
Σ wxp( 1a vello)
dæ
RD
k==
Par(a))
a-1
dlwi) p([1 p(1=
aw!
Hilp))do
JRD
QN(x))
Par + pi)
((m)) x(11=11p) dx
awi
JPP
QN(x + pi)
Consider a E R and its mirror image x E R By Lemma
O.3
and the assumption that the hyper-
m1lmmtl Par
plane separates M and N, Qx(++p))
(a((tt))
Pu(a Q
Pa(aa)
Per (an(tt More-
pl 1m (x)
QN(w))
over, also by Lemma 0.3 p([|=]1p) ((Ip= and therefore d( -d ((])=)Il>)
p(1|x11p) = d(m)) p(11=')lp) =
Similarly, observe how in dlrr Va (14)
K
1C
1-a
Wk wkp(11> x - melle)
dun)
Σ 1==0
wxp (1 x - velle)
dx
(x)
(-1)(1 arw
g(un) p(|1= - us villedd
220
QN
(a- 1)w /
Pas (xr v.))
(1,) p(||=1|p) dæ
QN + v.)
RD
the negative signs - n and (1 a) cancel and apply analogous reasoning thereafter.
The statement for V Aa now follows in analogy to the proof of Lemma 0.1 via Lemma 0.5 For Va Ha. find
((m) Va (p)= wi [ 1 ((P())) (006)) d(nr) p(11= H1ll)dd
JRD
(a)) p(((=e1pp) da
11 I Paglattnn 20 (Niwlnm
RD
Vn Va (H) = - W.
(-d(i) p(11 vell)) dx
RRD
w.
RD (Q 20
1 (y(
th ((11)|1p)) da
and can proceed by analogous reasoning from here on.
We are now equipped to construct the sequence of transformations taking two arbitrary sets M, N of Gaussian or Laplacian mixture means to the means M N of a dominating pair. We start with the Gaussian case.
O.1.1
Dominating pair of Gaussian mixtures
Theorem 0.7. Let V = H or V = Ag. Any pair of Gaussian mixtures with means satisfying
distance constraints of the form
H4 = vo =0 1|p4 - -P3ll2 I sli-1 - 5l
0A - JSKK || - vr s jl
0A < 4, T
is dominated by mixture with means
#4 k.ê Vk (O..... K).
Vx = Vx E {0, .... KJ. with RDD |é11 = 1.
86

---

Proof. We start by proving the following lemma.
Lemma O.8. Any pair of Gaussian mixtures with means at a fixed set of radū,
|| = Tke || 1 Px: TO Po 0, 0, Tk Pw. E B vk (L, KY E {I, K),,
and satisfying the constraints of Theorem i.7 dominated by feasible pair with means at equal radii that are collinear on diametral half- lineliies through zero, i.e..
P4k = Tk é, Ve - é E (0, Kj VR E {0, ...,..,K K. with é E RD,, ||ē||2 =
Proof of Lemma 0.8 Without loss of generality, we can pick as the collinearity direction from the lemma è = C1, the first canonical basis vector, since the divergence is rotation invariant. Pick any orthogonal direction, say, the second basis vector e2. By Lemma[O.1] we can mirror the two mixtures onto opposite sides of the hyperplanes with normal vectors éς and é2 such that éf pa 2 0 2 E Pa for all & and ēf UR 2 2 Ei yy: for all K.
Now, consider a hyperplane with normal vector n0) = é1 cos( + ée si), 0 E [0, r/2.. Intu- itively, we let this hyperplane undergo full rotation and "scoop up" all the means which are not in the hyperplane normal to é2, giving new set of means which are. Formally, we find that by the above sign condition, there is an angle 0g [0, x/2] for every such that sign (0) (&)) sign(0; 0). Namely, using to denote the projection onto the subspace spanned by vectors é1 and é2, T12/kK ||11/|0|222 (sin(f;)ē cos(6x) )2)). Consider the paths " [0, π / RP, where
7% (0) (0L-020)/4k + (0--0<o) ((1 112) + || 2|2 (sin(0)é c0s(
and sign-flipped construction with angles 0₂ and curves SN for the means Mxx For the derivatives along the curves, we find 7/ = |121//1|/2ñ(00 and (,) - 22 Also, by construc- tion, f (l) 2 0 > (.. (0). Hence, the prerequisites for Lemma 0.6 are fulfilled at every E [0, / 2/2 . By evaluating the path integral along these curves and invoking Lemma 0.6 we find
that the divergence along the path M, N + M, N cannot decrease:
L (PM [1 aa
K
(1)) Va ((71,..., Yk. SI...., (x) n
K
( Va (11..... 7K
.K SI Si...,, (x) d0 2 0
Clearly, the paths also preserve the radius of each mean. The final set of means M {T1 (TT))))...... 7K [ N = (T/2),...... (x(T) is contained in the hyperplane normal to ē2. We can now simply repeat this procedure with all basis vectors orthogonal to é to find the set from the lemma. Since is collinear with the same radii as M, N, and the means M, N are feasible, the new set is also feasible by the Cauchy-Schwar inequality.
Since we can map any set of Gaussian mixture means onto one with the same radii that is collinear without decreasing the divergence, we can from now on study the problem restricted single radial dimension, using
K
K
V
R
R
R
Ré
k==0
Kmm()
(ro...., TK, Po. ........P....................... .K.. Va
@wWN(-Pre,de Σ wwN(ne0
We can now state the next lemma which implies Theorem 0.7
Theorem 0.9. (0, 1,..,, K, K,O,...,K) Po 0. Ir. ryl < - Vi.j (...................... K}. lp. -prl s |
K)) is global maximizer of V.
under the constraints
Ré
VL, (0.... K].
87

---

Proof of Theorem 0.9 To avoid clutter, we constrain ourselves to the case with only means μa and single 1/ 0, since the proof involving several Vi2 completely analogous. Consider the line integral of the gradient
K RK
0 Dro
2
R
(ro...... .P...... rx)
V
Vo ŌTK
k=
Ro
between any feasible (ro....,,Pe rk) and the point (O..... K) along the connecting path
K
Pro [0,
k=0
(Ko...., (K) + to = (ro...., rK) + [(0,... K) (ro..... ..k]
First, observe that Fk < kVk E {o...., K} anywhere the feasible region, since T k-1 1 k. This means that v is componentwise- k- 1yt1 ryl S 2j=0
Σjz (1z+1 ry) & Lj=0
nonnegative and vanishes only if (ro....., rk) (0, ....... K). By Lemma 0.6 the gradient V Va
R
is componentwiie-nooneaaaiee anywhere along Tra We may thus conclude that
(O,... K) V. l
(vo....,
R
(v) f
VVa(((()) 20.
This concludes the proof of Theorem 0.7
O.1.2 Dominating pair of Laplacian mixtures
We also find an analogous result for Laplacian mixtures.
Theorem O.10. Let V. = Ha or V. = Ag. Any pair of Laplacian mixtures with means in
.........k uK] IR. satisfying pairwise L distance constraints M (Po. Mx ), (Vo, .........
To = Po = 0, 11lu 2اll S l - jl Vi.j E dominated by a pair for M N of the form
- us 1l S l/ T| Ve, E (O....,K.,,
11 = k é é, V k- é Vk E tO, KYVK E 10, ..., K.
with é tē,
where 1 < < D such that é; is the i-th canonical basis vector of TR.
Proof.
Lemma O.11. There is dominating pair M", N* located in diametral quadrants of RP: given the component-wise sign function,
3o E (+, sign(uu) = - =iign(vv Vpk E M Ue N
Proof. This is an immediate consequence of considering the canonical basis vectors as normal vectors in Lemma 0.1
Lemma O.12. For pa E M, E N, define the offset vectors dhm us 14- 8V == Vn Vx for 1 S K, S K S K. A dominating pair M No has offset vectors located on diametral simplices of the 1-sphere: 3o E {+1,-1}" 5ug So. ōv E S_o. with So = {x E B !
=-== = 1}. k e [L...,K]VKe ( K.)
88

---

Proof. For any pair M, NN of means not satisfying this condition, we will construct a new pair that does and has least equal divergence. By Lemma O.II we can assume without generality loss that (D( (D) {+11, - - sign( O(D) sign((=) Vyg, E M, Vs. N, where we put a superscript (D) above a for later reasons. At later stage of the proof, we will invoke that shifting the means along the basis vector directions with signs prescribed by o(D) are positive almost anywhere
as a consequence of Lemma 0.6
is useful to recast the optimization constraints in terms of the offset vectors: Vk E K....,,VVV... K.).
No = Po- = 0, |1óp&|11 = max oE(-1.+1)D
(oTōp)) 1, || =
max oe(-1+t10
(a ov S 1,
where the constraints between non-ascending and non-neighboring index pairs are implied by the symmetry and triangle inequality of the norm. For 0 s S K, and S K S K. set 1ix = pkk
(0)
Un Vic, and define (recursively for 1 S i < D) the paths
(0) 10.1| RR, 7
(t) = Hk 1k
(1-1)
tt [=1
(1-
10) Top (oof--1) 1)) ((o1D))Te)) e
Topi
ōul (1-1) (1-1) (1-1)
Mi Mi-1 of (0)
(oF
(1) = 7k (1),
(2)
arg max
uk
oE(-1,+1)
o" ,, )=)2=(011))) E:
10,10 + R2 (1)= ((-1) +t Σ (1 - T (-(o(D))Tee) en
5v/(-11 1) = vll ((1-1) 1) v (i-1) o!0
(o"oo((-i).
11 = -
arg max
oE|-1,-1)0 oz 6e1-1,-1)0.00 (o(D)))
By construction,
(8)
(1-1)
+ -1- (0) () (011)) Ei,
(v ov (i-1) + (o- To (-(0(D)) és e..
We can easily check that 6p4 S s., du E S for 1 k K, k k ".
We can moreover verify that, based the definitions of (1) and 0% the feasibility conditions
[16p (i (8-1) ||1 s and || 1112 S 1 imply [|ōp(" ||1 max (oTöpl) opuk) (i)
(8)
I and
@ 1|2
(oTáv\") I 1. Since, furthermore, Mo (1) puu 0, 1/ (1) Vo 0 for
1 < < D. and M, N are feasible by assumption, all pairs of M(0) == {1O ....,,KK }. NO =
(2)
(6)
(v) "x. are also feasible by induction.
Finally, the above simplex and feasibility properties together imply that Vk E (1....,,} K}, VK E ef ou = - (00(D))"
(1.... sign (ef (((6)())) (1) = (D)))" T è; and sign
T è; if j 2 i. But this
means in particular that we can identify of = - = (D) for S k < K and S K S.
Putting everything together, we conclude that the pair (D), (D) obtained from M.N by con- catenation of all paths is feasible and has offset vectors on diametral simplices, 8pk (D) E SaiD) )v E S (D()) Vk E (I...., K}. VK E K.). What is left to show is that M(D), N(DD has at least the same divergence as M, N. To this end, define the product curves
(1) (A7 x000)(00))))) N))) [0, 1] - R (K+K)X t tr (10 (4) (t), (t)..... ... K (1), 20 (4) (t).............. ..... (()), (0), 1SiSD
89

---

connecting the endpoints (M (((()))) and (M _NO), and the image sets C()) == (M x
((0, 11) c (K+ The divergence difference is sum of line integrals:
V Va(Dr(DI1NN(1)) - V.(MI)N) = Σ v (M(O0I))))) Va (a (1
Σ
(M + Σ glvc) Va V (NT
(11111100))) ds
==1
N==
D
(vm)) nr:
(A
Σ
(o- (0)
(of POo )
K v
(M
( (1)
Σ (- di 2 20:
+
k0
At the start of the proof, we made the assumption without generality loss that 3o( E -+1;; sign(us) = o(D) -iign(u,) Vuu M, Ux. E N. Therefore, the directional derivatives df d/(,t)) (1x) along the curve directions Iń; = ((o(D))Tei) é; are nonnegative. The determinant factors Σ 11 (1- ( 5pf "I) and (1 - (a. 1) are nonnegative due to the feasibility of MO, NO Vi E D).
Lemma 0.13. There is a dominating pair M N with i E (1.....,D)) D} and a E (-,+} such that 5ytg dē; 5v2- -oê;; k E {1,....K) K3 V E KK).
Proof. By Lemma 0.12 we may assume without generality loss that 3o E {+1, 11 6uz E So.
ōu, E S_a. with S. == (æc E RD o² x = 1}. vk E (I,..., E (I....,K). K.).
The following curves will be useful. For 1 si D, (I,..., D} define
(00) [0, 1] RR.. 7k
(t)
(t)
for for k < l [i + 1(a" T (ef (( - -of
7k
for fork)
<:0: |0, - R
C
(00 (1) (1)
UN for <1
+ t(o T (e? 5y, ( e,)e, - (oTe))e) for k: 2 (10)
(110) (0) = pk. Sk (0) v/ To
(111)
(1fl) (1) = 0, 50 (15)) (1) = 0, 7 (1) ( (1)
By construction, 7
ōug for 1 < k + 1 < K, Ch (1j0) (1) (1) (1j1) (1) = Sun for 1 S K # 1 K.
0 form=
(7 (1) (1)) ém
(eTo)ooTee + (e)o) /off è for =
dur em clse.
and
0 for (-ēT é (-e5o)) é for m j
(1) (1)) T
ém
ou em else.
In particular, this implies that the new pairs of sets (M() = (160) (M, : =(500 (1)....
(1f)) (1), (1).....7. 100 100 (090 (1)),
Sk (1))) are feasible.
(15c)
Assume that 31 {1....,K] K), m E {I..... {l....,K, E DJ...,DD. j E {1, (L...., DJ. i # j: (fufee é:) * 0 A (fuT, } * 0. Note that we include the possibility of 1 = m. We can then assume without generality loss (by Lemma O.I) that the conditions of Lemma Lemma[0.6]hon hol for either 2. = J/2 ((oTée)ee - ()))) or á = vz
- (o (zzr))) In the case of â.
consider the product curve
(M) N): (0, 1] + L K+XXD
+ (70 (3/5
(151) (t), ..,, 7K
(860) (t), vo. ... VK)
90

---

and the image set (()) = (M x (),, 1)). The divergence difference has the form
V. (a(MOIIN)) ( (M =Sc
(m v. (MMM) (1T)))1))) ds
R=U
- L=0
t=1
Σ (mw) T (a((
v2(ooT (e) 2 20:
By construction, the directional derivatives d Va (tM(I)) are nonnegative. Likewise, the determinant term v2(a" (é) Óμx) is nonnegative by the simplex condition together with feasibility of N)
the separability condition is fulfilled for ń instead, we can repeat the argument with indices + swapped and index instead of I.
An analogous argument holds if 3i (I,...,K,, E KI, (I,...D} {1..... D). i i (ōv, e,) * 0 (ōv #
Theorem 0.10 immediately follows from Lemma 0.13 by induction.
0.2 Reduction of the divergence to a univariate integral
In the previous subsections, we showed that a (M) is maximized by collinear and equidistant sets of means. This allows to evaluate V (M) through one-dimensional integral via marginalization. Recall (Theorem 0.9). Note furthermore that in both cases, constraining the first element of either N or MM into the origin incurs no generality loss due to the translation invariance of v a..
Being able to constrain the problem to a single dimension, we now show
Lemma O.14. In the collinear case, we may evaluate Va as the one-dimensional divergence A between two mixtures E (rk, Ex= WnNpspss of univariate Gaussians centered around the means Tk and -Prs
V
Σ
Σ w,N((ne, w!
Σ WwW o
Σ wyn (rrr k=0
Proof. Without loss of generality, may assume è to be the indicator vector of the first component due to rotation invariance of a. Using bracketed superscripts (0) to indicate the first vector component, and (1 to indicate the rest, use Fubini's theorem to write
K
K
V
Ww I)Il
Σ
((me),))))
k=
(1-a)
Σ www
-pné,
wrN(w mzē,01))
de (0) (1)
D
Σ WcNN(x( | (1-0)
(z:(11)) 10,021 darl)))
Σ
--px; 02)
de
BD-1
Lm=0
K
K whW WhNN 02
1. DD
Pkc,
K=0
k=
The proof is analogous for the Laplacian mechanism.
91

---

0.3 Randomized Response Proofs
The following two results (first for the Rényi divergence, second for the hockey stick divergence) show that our (group) privacy guarantees for randomized response are given by the maximum of two terms that can be evaluated in constant time.
Theorem 0.15.
K +1
12 (D))
a
K
+1
1-a
arg rE(O.1] (
Σ
Σ
2 (1 (1-12--9 wi
Σ
22) ms
(1 11-12
11-12-1,-11
(2
+0+00 +1)
==U
subject to
(1) E (0,1-0),
(1) E (0, - 0), Vj,
3
(1) = 1
with
(1) Binomial(i - 1 K_,r),
(2) Binomial(j - r);
j
is given by
arg max ( (00 (m+a>]|mm(r)))
where
(11) = 71 =ITE E 10, 1 0) (symmetric),
=11)
=1- - T,
(K.,,(K4 (K++1) +1)
(2)
2,....K_11 (K-+1) +1) =
and
11 = (2)
(1)
= E {0, 0} (symmetric),
(1)
2 (K₃ +1) =,,
(2)
2 2K.... (K- (1) = 1
Proof.
The strategy is to show that
(a) Any mixture pair (m (,, my(.:) where mya has greater mass in (1 - 7), i.e.
Σ
(2) dominated by (m+a), m+())
w
J:T/ 11=---7
(b) Any mixture pair
()), (m (1), m m2(2)) where my has greater mass in (1 7). i.e.
wi
w is dominated by (m+a), m4(2))
2: =1-7
d:r (2)())=1- =1-
Notation:
K
K_+1 Σ
1-a
Σ
Σ w (1-12 -0-
(1-1-
12)
Σ f(x(2))o(v(=))
2=0
where / strictly convex, increasing, and strictly convex, decreasing.
Trivial case: 0 = 1, thus assume 0 af 1 for the rest of the proof.
92

---

t
(here:
8x @
: -
r'
(here:
Figure 26: Visualization of dæ and 8 Color legend: The color "blue" refers to terms with superscript
(1), while "red" refers to those with (2).
Proof of (a):
Given: Pair of mixtures (m, m,(()) such that wi-r
Σ
W
Σ
(2)
=1-T
jiry
=1--
(2) wi wi--T"
(1) Further define Wr =
(1)
(2)
wi- WT
W1-1
Define new mixture via
(1) (2)
11
1
(11
2..,K_ K-11 = -T,,
(2) (2) Vi.
Assume w.l.o.g. that To m0 0), else swap roles of 0 in the argument.
Decompose x: ax)) ==)==) + 6x(2), where
xo(2)= = (1) - 1a (1 1---711 r)]) - ( (1 - 22 r)), i.e., "part that stays fixed"; see Fig. 26
d<(2)= = (w - )1 - | -1==))): i.e., "part that relocates"; see Fig. 26
Similarly,
z'(z) ==(22) + dz dz'()),
and by construction,
(=) = =o(=),
8z (2) = 6r(1 - 2) (+)
We can assume w.l.o.g. = max 0} = 8x(1) > 8x((0) (**) (else, swap 1 <+ 0)
Then, f + 2. hence assume w/ w(t) (1) (else, m' = in the first place).
L (m, m))) (m.,),
[f (0) dx(1)) (z) (())) (f (zo(1) - (z))))
Then, using that f is strictly convex, we have
(++) ('(xo(0) + 6zx(0)) (z(0))
dr(()) (()())))(((rr(()+++)))))) ((0))(()(+()))))))))))))))))() 5x(0))
Where f'(x) = a_ and thus f((x)((v) (a - (5)
a-1
(o((0)
+xx()))x00))) 5x)
a-1 (T)()) + 5xx(1)
a-1
(a 1)
(8x(1) 5xx())
3(0)
y(1)
(
(1 (1- w 11) (1 - T)
(1)
a-1
wi
(1)
+ (1 w (1 T)
(1)
a-17
(a (a-1) 1)
W1
(ōx(1) dzx(0))
(1-
2
w
(2) r w (2)
(1 T)
0.
93

---

(here: r]
5y
f
(here:
Figure 27: Visualization of dy and oy'. The color "blue" refers to terms with superscript (1), while "red" refers those with (2).
The last inequality follows from the following facts. Since assume w. wi" (else, m' in the first place), we can bound the second term by:
w (1) + (1 (1- (1 a-1
a-1
(1 - (1-wi_r wi-)T + w1 7)
(i)
()) w - 1 (2) w
(1 w/ 2 (1 7)
Moreover, have that the first term is bounded by
(1 - - (1) -1 - +
2 1
(1 W (1 (1- (1 + wi-,7
(strict > if (1) w The conclusion follows from (1), (ii), and since WLOG 7 >> (1 ()-
We have shown so far:
Va (m,r1),, myr(2))) Va (M, my
To complete the proof of (a), we show now that vi o (maa), m3(2s) > Vo m,p
Idea: Apply symmetric argument to means T(2)-
Since = wT + ww (1) w!? (2)
ww - we have
w w
(2) (
wol w
where wir, ( are defined like w x22)
(1)
(2) but for new means 7'.
Decompose y/: g²(2 36(2) + 6// (2), where
(=) w = - r[), i.e., "part that stays fixed"; see Fig. 27 óy/ (=) = (2) - (1 T) T))), i.e., "part that relocates"; see Fig. 27
We can assume w.l.o.g. that 7 = max - 0). so 5y > (1)(1).
V. (m m4(2)) - V.
m2)))
=f(x' (966 (0) (g)( g666 (0) + 00000-00000000000000000000000000 (1) o1)(1)
And using the strict convexity of o we have
(f(22(1)) (1) + /y (1)) -
(16 + +y (6)(0) oy
x' 20(
x(11
(a (a-1)) 1)
(6 (1)
(0) + 6y' (1)
(6(1) 80
( (1 7) + (1 - w
w (1 w (1 -T) 7)
(a 1)
(8y'(0) oz)(1))
(2)
(1 vo (1
w
0.
94

---

Proof of (b) is fully analogous.
This proves the theorem statement, since condition (a) (b) is fulfilled for any mixture pair, and hence any mixture pair is dominated by the argmax of the two mixture pairs stated the theorem.
Theorem O.16.
K++
K_+1 Σ ==1
]
arg max +
Σ
" 12) - -
c²
w 22) (1 -1- 1
+ +1)
i=1
subject to
T (1) (0,1-0), 0), Vi,
{ (1) E [0,1 - 0), Vj,
(1) (2)
T 1
with
w (1) Binomial(t r),));
w) (2) Binomial(j - 1 k),r),
is given by
arg max V (m+cn)lm4ca)) (m4collmaaa))
where
(1) = +1 =I E {0, 0} (symmetric),
2K...K +1) = -- T.
(2)
2K....KK +1) =
and
+(1) (2) =: {8, 0} (symmetric),
(11)
2K... =T,
(2) (.....(++)) +1)
Proof sketch.
The strategy is to show that
(a) Any mixture pair (m (m, my where my0) has greater mass in (1 7). i...
Σ
w
w is dominated by (m4c), m40)))
1 =1-7
(b) Any mixture pair (1), my))) ) where my has greater mass in (1 - T), i.c. (2) dominated by (m4t), mpm))
(1)
Notation:
Σ 2=0
K
K=+1
Σ
w (1) - (1-12-172 -1=-7,011 e
Σ
11-------
2
= Σ ((()))
"
1=1
2=0
where / = [. is convex and differentiable anywhere except at 0.
Trivial case: 0 1, thus assume 0 + 1 for the rest of the proof.
95

---

Proof of (a):
Given: Pair of mixtures (m,a), m,(1) such that w wi- ==
Σ
Σ
w
(2)
R:
=1--
j.y (2)
=1-
W1 ---
Further define w. -i-7 WT
(1)
(2)
(2)
Wi-r'
Define a new mixture via
(1) (2) T
7
(1)
2 K 1 - T
(2) (2)
7;
Vi.
Assume w.l.o.g. that To max (0, 1 - 0) else swap roles of 0 ++ 1 in the argument.
Decompose x(z) =0(2) (2) + dz((2), where
zo(z)= (1) - 12 (1 +) - w ( (1 - |2 T)), i..,, "part that stays fixed"; see Fig. 26
6z(2)= = (w - wf (1 - |z - -)), i... "part that relocates"; see Fig. 26 Similarly,
x' z'(:) =6((2) + de' dz)
and by construction,
<x)x)) = =o(2),
5z'(2) = 5r(1 - 2) (+)
We can assume w.l.o.g. To max(0. [0,1 8] = 8x(1) > (0 (**) (else, swap ++ 0)
Then, + 2" hence we can assume w
w
(else, m' = m in the first place).
V (m,,i, m)))) 1/ (m,(), (2)
(*) [f (0) + 8x e y(0) f (zo y(())
[f (zo(1) + 5x(1) - c11(11) - (=o(() - v(1)))
Assume for now that (0) + 6x(0) - e0)(0) #0 z0(1) + 6x(0) - ey)(
(+))
2 (f'( + 5r(0) e'v(0)) - (0( (x(() - ef)())) (6x(1) - 5x(())
f' [(11 ((1- ((1 -1) w - (1 (1- (2) -) + [[- (6x(1) 5x(())
f [wwf) (1- w/ ( (1 7)) -
(6x(1) 8x((0)
(1) (,,7) -
(2)
(2) +) (fx(1) 5x(())
/' (1
(1) T w
c (1- w
2 (1- T
(2)
w/
22)
) (8x(1) 8x)
0.
The second-to-lass inequality follows from w w (1) (else, = m' in the first place). The last
inequality follows from w ( > w (2) and the prior assumption that, WLOG, 7 > т.
(0) + (0) ( xo + 6x(0)= (1) and (1( 1) + (x) Ef((1 0. then we can arrive at the same conclusion by using any subderivative of f in [0, 1] so (1) 5x(() - e (1) instead.
We have shown far:
v (amman, m.pca)) 2 Vo (m,cy, m.))).
Continue in analogy to Theorem 0.15
96

---

P Towards epoch-level subsampling analysis
Standard composition theorems assume that the outputs of composed mechanisms conditionally independent, meaning each output only depends on the previous outputs and the dataset (see, e.g.. the proof of Proposition considers subsampling schemes like Poisson subsampling or subsampling without replacement, which yield independent batches in each iteration.
77] and the proof of Theorem 27 in (TO). For this reason, one typically
However, there may be scenarios where batches are not independent, such as when creating batches by permuting dataset and splitting into equal sized chunks. Such correlated subsampling schemes are appealing because one can, for instance, limit privacy leakage by ensuring that any element appears in only iteration per epoch when training model. A downside of these corellated subsampling schemes is that they may brake the conditional independence assumption of standard compositions theorems.
There already exist approaches to analyzing compositions of correlated mechanisms, such as proba- bilistically upper-bounding mechanism's privacy leakage with uncorellated mechanisms 775 24]. Furthermore, permutation-basse baasd batching has already been discussed the context of convergence guarantees for noisy SGD [38]. Nevertheless, this problem setting provides great opportunity to demonstrate that the utility our conditional optimal transport framework extends beyond the subsampling schemes that are typically discussed in amplification-by-eeee bubbbsapllii literature.
P.1 Problem setting
For this example, we consider non-adaptive composition of mechanisms, where batches created by permuting a dataset and splitting it in half. We assume that our dataset space is composed of size 2.V subsets of some finite, discrete set i.e. X S {x E P(A) |x| 2N), }, and equipped with substitution relation N subsets, i.e., Y {y S x X A y N). which is also equipped with substitution relation =A. Finally, we assume base mechanism B : W + Z with conditional density by Z > R that maps from this batch space some output space.
We further define per-iteration batch space Y that is composed of size
To apply our framework to epoch-level subsampling distributions, we define the composed batch space Y, which consists of equal-sized partitions of datasets X. i.e..
(3/1 322 Vori
3x X y1 Uy2 = x)
(37)
On this composed batch space, we can now define our epoch-level subsampling scheme: Definition P.1. The permute-and--aattiion subsampling scheme is the subsampling scheme S: X
Y with
(2N)
if y yy=zz = otherwise
This definition follows from the fact that permuting-andd-arriee batch of size N without replacement for the first batch and using the remaining N elements for the second batch. We further consider the non-adaptively composed base mechanism B v z² with B(yn.va) w2) = (By, BBy) and resultant joint density b(g). = by byz.
is equivalent sampling
P.2 Optimal transport without conditioning
As baseline, we use Theorem 3.3 i.e., optimal transport without conditioning, to provide Rényi- DP bound for the composed, subsampled mechanism. This guarantee captures the intuition that by permuting-ande and-partitioning we only leak elements' private information once. Again, note prove this result for non-adaptive composition.
Theorem P.2. Assume dataset space X C {o E P(A) [a|] 2N), batch space V = {u S r X |yl = N). and base mechanism substitution relation = A.y. Let S: X be the permute-aid and and-partition subsampling scheme defined in Definition P.I. Let B be the composed base mechanism with B(y = (B Byz)- Then the subsampled, composed mechanism M B also (ax, DD- w.r.t single-element substitution relation A.X.
- Z, that (a, -R-ne-iinii-D- w.r.t. single-element
97

---

Proof. Consider an arbitrary pair of datasets 2 >Ax.. By definition of the substitution relation, there must be some a and some a' E x' such that x r {a} {a'}
We can now define the following simple coupling between S. and Syr
i E Au Vi (1) {a) A32 = U2
((()
(2) .222) .22
(11
(2)
-1 if E 1/2 Ay2 = =y² ua) Ayi (1) = y1
(1)
(2)
(2)
otherwise.
This coupling generates pair of batch sequences by first applying permute-andd-partiion to original dataset and then replacing a with a' in the one batch it appears in. Because we only couple pairs that are identical in one batch and differ by a substitution in the other batch, we have Theorem 3.3
V (vizz [(xa'') S
max
(b 1
11 (2) (,a))) M/2
(of
(1)
(3) E
subject to (gf DAY vi ( A (v2 = 1) (32 the factors cancelled out when computing the likelihood ratio in the definition of Rényi-divergenee (see Eq. 7 We thus have
DAYY 02
()
(0) - v 2) Either way, one of
(m [ma))
max (2) Mi EY2
(b on 16
subject to vf =A, Vi
The result then follows from the definition of Rényi-DP (see Definition 2.2
P.3 Optimal transport with conditioning
Next, we use Theorem 3.4 i.c., optimal transport between conditional subsampling distributions, to derive a stronger guarantee. Again, note we prove this result for non-adaptive composition. Note that this result is similar in spirit amplification by shuffling 76 75). but considers central differential privacy of mechanisms operating on batches, instead of locally differentially private mechanisms that operate on individual elements. Again, note that we do not claim be the first consider the permute-ang cermute-and-pee -nd--ttttatttiiioonnnnn scheme for composed mechanisms (see, e.g., (38]). It is just nice showcase for the versatility of our framework in analyzing different subsampling schemes.
(1)
For the following result and proof we will use the following indexing convention: Vi,k is a batch
associated with the first mixture my, event A,, and the kth iteration. Similarly, Vj,k a batch associated with the second mixture mar' event Ejj, and the kth iteration.
Theorem P.3. Assume dataset space X C {ar E P(A) | |x| 2N), and corresponding batch E X lul = N), equipped with single-element substitation relation =A, Let S X + & be the permute coctute-ann-paae and--and---aa and-partition subsampling scheme defined in Definition P. and let W > be some base mechanism. Let B be the composed base mechanism with B(y).z))
space V = {y S x E
(By, Byz). and M Bo S the subsampled, coposed mechanism. Then, for all
2AX x'
T. (ammlllm
1
1
(1) (2)
max
VA
b b,a
81.1
41.2
(1) b. ay ())
2
v1.2
vi.1
2
66 (2)
81.1
b,
21. Mi.1
m (2)
subject to Vi - V1.1-
(2)
Proof. By definition the substitution relation, there must be some a E x and some E x' such that x' = x {a} U (a').
For the original subsampling scheme S, we let A₁ be the event that appears in the first batch and A₂ be the event that appears in the second batch. For the modified subsampling scheme S,, we let E, the event that a' appears in the first batch and E. be the event that a' appears in the second batch. We have Ps. (A1) Ps, (Ag) Psy (E1) Psy (E2) _.
98

---

One can sample from the distributions conditioned on A1 or E1 by first sampling uniformly at random N elements from the 2 N elements that are not or d', and then using the remaining elements as the first batch. Similarly, one can sample from the distributions conditioned on A2 E2 by first sampling uniformly random N elements from the 2. N elements that are not a or a', and then using the remaining elements as the second batch.
We thus have
(2
if vf E A otherwise
1
if yf A otherwise
(1/1 (1) A1) =
A2)
00
and
Sy (y1
(2)
E1)
(2N-1) -1
if vi E E1 otherwise
(0((22
(2)
Eg)
{
(2N (2N-11)
yf Eg otherwise
Next, we can define coupling via
y 922
(1)
(1)
M1 1/2
(2) (2)
(3 (1)
A1)
Condition P.4 is fulfilled
otherwise
Condition P.4. Batch tuples 1/1 A1,y2 A2,
(1)
(1) (2) Vi
(1)
(2)
E1, 1/2 Eg fulfill Condition P.4 when
(2)
Vi.1 1/22. and vi.2 V2.1. and v1.2 21.2.
and 12 32.1 and vi.1 vi. Laj
[a' and
22.2 12,2 {a)
(2)
In short: We sample uniformly random batch tuple (Vi.1 Vi.2) from A1. We then generate batch tuple from Ag by permuting the A₁ tuple. We then generate a batch tuple from F. by replacing with a' in the Ag tuple. We finally generate batch tuple from Ej by permuting the Eg tuple.
(1)
Because for each possible value of a batch tuple there is only one combination of the other three batch tuples such that (g) 0, and in this case r(y) 1)
-! this is valid coupling.
The result then follows from Theorem 3.4 and the constraints imposed by Condition P.4
Note that this result could be generalized to K iterations: We can upper-bound the subsampled, composed mechanism's divergence by adversarially choosing a K-fold partition of æ, constructing mixture with K (not K!) components, with each component corresponding to appearing in specific batch, and finally constructing a modified mixture by replacing every occurence of with a'.
P.4 Experimental Evaluation
compare epoch-level amplification guarantees obtained via optimal transport with and without conditioning. As an additional baseline, we use 2-fold composition of subsampling without replacement with batch size 2. Note that, with the baseline, modified element may appear in 0, or 2 of the iterations. For the sake of this simple example, we consider output space = R, and let base mechanism be the Gaussian mechanism standard deviation a E {0.5, 1.0, 2.0, 5.0]. By this construction we do not need to reason about f's sensitivity determining the worst-case mixture components.
Finally,
(0, with ʃ Y - (0, 1} and univariate
We make the following observation: For small a, both epoch-level guarantees are almost identical and outperform the without replacement guarantee. With increasing subsampling without replacement outperforms Theorem P.2 for some ranges a. Theorem P2 which derived via conditional optimal transport, however yields smaller
The main takeaway of this example should be that (a) there a benefit to using conditional optimal transport to bound privacy in terms of mixtures and (b) conditional optimal transport can be used to reason about schemes other than the typically considered Poisson subsampling, subsampling without replacement, and subsampling with replacement.
99

---

q N = 0.01
9 / N = 0.1
10a
Without replacement
Without replacement
Theorem P.2
Theorem P2
Theorem P.3
Theorem P.5
RDP [())
RDP {(o)
10
10 RDP order
10a
10
10a
RDP order
/ = 0.2
q N 0.5
Without replacement
Without replacement
104
Theorem P.2
Theorem P22
Theorem P3
Theorem
E(a)
RDP s(o)
10a
10-1
10
10-2
10a
102
10a
102
RDP order
RDP order
Figure 28: Comparison of our epoch-level permute-and-partition guarantees with (Theorem P.3 and without (Theorem P.22) conditioning, well as subsampling without replacement, for 2-fold non-adaptive composition. The base mechanism is a Gaussian mechanism with f Y + {0, 1] and varying standard deviations a. With increasing a, Theorem P.3 and subsampling without replacement become more similar, while Theorem P.3 consistently yields stronger guarantees.
Q Broader impact
Our work contributes towards provably protecting users, and specifically groups of users, from the negative societal impact of privacy leakage. However, differential privacy may have negatively impact other aspects of trustworthy machine learning, such as fairness robustness. Also, training for differentially private machine learning is often performed with 1 < E I 10. This is useful for relative comparisons between models, but does not impose any meaningful constraints absolute privacy leakage (the probability of any event may increase by a factor of up to 22000) and may thus be used to falsely advertise privacy.
100

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We verify the generality of our proposed framework by formally deriving various known and novel subsampling guarantees Appendices G to ! and K to M We verify the benefit of using mechanism-speee sppccifc guarantees and analyzing group privacy and subsampling jointly through our experimental evaluation in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Our main contribution is framework for proving theoretic results, as such many of the points listed below do not apply.
Justification: We discuss limitations in Section 3.5
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
101

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Yes, we provide formal proofs for all theoretical results in Appendii(EJthoouue Ehthoughh
Appendix P All theorems and lemmata state the underlying assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
We further provide an implementation with the supplementary material, which includes the needed environment, code, configuration files, and plotting scripts.
Justification: We fully describe our experimental setup in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
102

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide an implementation that includes the needed environment, code, configuration files, and plotting scripts for reproducing our experimental results at httpss//es.ci.uuu.deeddm/////// proprrapiaaaaaiiiaitioon
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
onmoooicl)ll for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
CooeeSumeeieeeeeeeeeee ssi owoooonoolllllloooooooooooiiiill for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We fully describe our experimental setup in Appendix C Note that these experiments only require numerical evaluation of different divergences, meaning there no involved data splits or optimizers.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our experiments only require numerical evaluation of different divergences. There are no typical sources of randomness like data splits or weight initializations that could be visualized with error bars.
Guidelines:
103

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, report the type and number of CPUs, as well as the number of workers and allocated runtime Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research in this paper conforms, every respect, with the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
104

---

Justification:
Yes, we discuss both positive and negative broader impact in Appendix Q which we reference our "Limitations, broader impact, and future work" section Sec-
tion 3.5
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not propose any new data or models that could be released.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We list the libraries that we use and/or extend conduct our numerical experiments in Appendix C.3 including version numbers and licenses. We cite the original papers where applicable.
Guidelines:
The answer NA means that the paper does not existing assets.
105

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets..paerssttt paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
106

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
107


Reviews:
[{"review_id": "JTmzMdm22V", "reviewer": "Reviewer_eK4M", "summary": "This work proposed a novel analysis of mechanism-specific amplification via subsampling. The authors decompose the subsampled mechanism into two parts: batch subsampling + mechanism. Then the analysis decompose the probability density into sums of pdf of every batch. The authors then provide upper bound to the divergence and specifically applied to group privacy under poisson distribution. The empirical analysis shows that the proposed analysis is able to significantly improves upon prior mechanism-agnostic group privacy bounds.", "questions": "See above.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposed novel analysis for group privacy. The application to poisson subsampling + gaussian mechanism seems solid.\n- Solid theoretical guarantees.\n- Simulation results look promising.", "weaknesses": "- Theorem 3.4 + proposition 3.5 themselves seem very costly to compute. I appreciate the authors for providing example of poisson subsampling. Still I'm wondering whether, e.g. proposition 3.5, is easy to solve for non Poisson distribution. \n- Similar to the previous point, a small weakness for Theorem 3.7 is it's unclear how hard it is to solve for mechanisms such as Laplace. If it does not have a closed form (or closed form hard to derive), it might lead to un-tight upper bound or costly numerical simulation in practice. (Edit: I see the Laplace analysis in the appendix)\n- The theoretical guarantees consist of a lot of notation. Might be helpful for the authors to add small interpretation of the bounds in e.g. Eq  2 and Eq 4 for better readibility.\n- Could the authors add group size = 1 in the experiment for completeness?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\nWe are excited to hear that you find our submission worthy of acceptance.\n\n### Computational cost of computing Theorem 3.4+Proposition 3.5\nBefore discussing the main question of your first bullet point,\nwe would like to briefly clarify the following:\nThe optimal transport problem in Theorem 3.4 and the constrained optimization problem in Proposition 3.5 are not primarily intended to be solved via computational methods. Rather, they are **meant as a recipe for formally deriving amplification guarantees**, so that researchers do not need to \"reinvent the wheel\" whenever they want to analyze a different subsampling scheme or neighboring relation.\n\nNevertheless, operationalizing these two results as a form of automatic theorem proving could be an exciting direction for future work. Thank you for this inspiring idea!\n\n### Can Proposition 3.5 be solved for non-Poisson distributions?\n**Yes, in fact we do so in our paper**.\nSpecifically, we solve the problem for subsampling without replacement and two mixture components to provide an alternative proof for the dominating pairs originally derived by Zhu et al. [1] (see Appendices K.2 and K.3)\n\nWhen considering the same neighboring relation, the optimization problem for Poisson subsampling and subsamling without replacement essentially only differ in the mixture weights / event probabilities. Our solution to the optimization problem in Theorem 3.7 is independent of the mixture weights (see Appendix O - \"Worst-case mixture components\").\n\n### Can Theorem 3.7 be solved for non-Gaussian distributions?\nAs you correctly point out in your edit, we do in fact also solve this problem for Laplace and Bernoulli (randomized response) distributions.\n\nIn fact, our proof strategy does in principle extend to **arbitrary distributions whose isocontours are given by $\\ell_p$-norm balls** (see, e.g.,  Lemma O.1). However, in order to simplify the notation of our Lemmata and to keep the scope of our paper more manageable, we have decided to focus on mechanisms commonly used by the community.\n\nIf you would like to discuss this generalization further, please let us know during the discussion period!\n\n### Interpretation of Eq. 2 for and Eq. 4 to improve readability\nUpon re-reading our manuscript, we agree that we should use the additional content page to provide more detailed explanations of these results.\n\nUnfortunately we cannot upload a revised manuscript during the rebuttal period. But **we intend to add the following explanations:**\n\nEq. 2:  \n\"We now have an optimal transport problem between I+J probabability mass functions, coupled by $\\gamma$. The transport cost $c$, given batch tuples $\\mathbf{y}^{(1)} \\in \\mathbb{Y}^I$ and $\\mathbf{y}^{(2)} \\in \\mathbb{Y}^I$, is a divergence between two mixtures. The components of the first mixture are base mechanisms densitities given batches $y_i^{(1)} \\in \\mathbb{Y}$ from $\\mathbf{y}^{(1)}$. The weights are probabilities of events $A_i$.  The second mixture is defined analogously.\"\n\nEq. 4:  \n\"This bound instantiates Eq. 2 with binomial mixture weights.\nBatches $y^{(1)}_u$ and $y^{(1)}_t$ have a distance bounded by $|u-t|$ because one can be obtained from the other by removing/inserting $|u-t|$ elements. The constraints for $y^{(2)}_u$ and $y^{(2)}_t$ are analogous. Batches $y^{(1)}_u$ and $y^{(2)}_t$ have a distance bounded by $(t-1) + (u-1)$ because we need to remove $t-1$ elements and insert $u-1$ elements to construct one from the other.\"\n\nDepending on the remaining space after implementing the other reviewers' suggestions, we intend to provide similar explanations for other results (e.g. Theorem 3.3 and Theorem 3.8). Thank you for helping us in further improving the readability of our paper!\n\n### Could the authors add group size 1 to the experiments for completeness?\nOf course. For an example, please **see Fig. 1 in the pdf attached to the global rebuttal comment above**. We will make the same change for all figures once we can upload a revision.\n\nNote that our experiments with randomized response and Renyi differential privacy (e.g. Fig 3 in our original manuscript) already considered group size 1. There, we outperformed the best known guarantee even for group size 1.\n\n---\nThank you again for your efforts.  \nWe hope that we addressed all your comments to your satisfaction.  \nPlease let us know if you have any further questions during the author-reviewer discussion period!\n\n---\n\n[1] Zhu et al. \"Optimal Accounting of Differential Privacy via Characteristic Function\". AISTATS'22", "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": "", "extra_scores": {}}, {"review_id": "DPVhTmwg4z", "reviewer": "Reviewer_7Wbe", "summary": "The authors propose a framework for privacy accounting of amplification by subsampling. An existing principle for this problem is to consider couplings between the output distribution of the mechanism on neighboring datasets and apply joint convexity of the privacy measure at hand. The primary contribution is to select the optimal coupling and minimize the resulting privacy bound by viewing it as an optimal transport problem.", "questions": "Small editorial suggestions:\n- It is difficult to follow the quantifier constraints in some places e.g. p.5 l.193\n- p.4 l.178 Missing $y^{(1)}$ and $y^{(2)}$ under sum\n- p.36 l.852 should this be $x'$ not $x$?", "limitations": "While the paper leverages their framework to provide new tighter bounds for the group privacy setting, the framework is only used in the other privacy accounting settings to reproduce known results (from e.g. Zhu et al 2022 or Balle et al 2018). A future direction for this work, which the authors do mention, is to apply the framework to address the practical gaps in privacy accounting for machine learning.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper provides a novel technical framework for accounting of subsampling amplification. The authors are able to reproduce important closure properties of dominating pairs using their framework (e.g. Proposition K.3), suggesting their framework may be used to analyze mechanisms that previously evaded accurate accounting (e.g. shuffling).", "weaknesses": "The main technical result Theorem 3.4 did not feel clearly motivated in terms of Theorem 3.3 and the experiments in Appendix B. It was not clear to me from the justification provided on p.4 lines 171-174 why Theorem 3.4 is able to improve substantively upon the preceding result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your suggested editorial changes!\nPlease let us first respond to your higher-level comments, before discussing the smaller editorial changes.\nNote that we cannot update the manuscript during the rebuttal period, but will include all your suggestions in a revision as soon as possible.\n\n### Motivation for main theorem\nUpon re-reading the relevant section, we agree that more could have been done to even better motivate Theorem 3.4. The original manuscript only states that conditioning lets us limit the recursion depth to which joint convexity is applied (see ll. 168-171). However, it does not explain why this might be necessary / desirable.\n\nOnce we can upload a revision, we intend to provide the following, more in-depth explanation:  \n\n\"Theorem 3.3 is the result of recursively applying the joint convexity property (Lemma 3.1) to the mixture divergence $\\Psi_{\\alpha}(m_x || m_{x'})$. Each application splits each mixture into two smaller mixtures and --as per joint convexity-- further upper-bounds the divergence $\\Psi_{\\alpha}(m_x || m_{x'})$ that is achieved **by our specific subsampled  mechanism  $m$ on our specific pair of datasets $x,x'$**. Upon fully decomposing the overall divergence into divergences between single-mixture components, this sequence of bounds is in fact larger than the divergence $\\Psi_{\\alpha}\\left(\\tilde{m}\\_{\\tilde{x}} || \\tilde{m}\\_{\\tilde{x}'}\\right)$ achieved **by a worst-case subsampled mechanism $\\tilde{m}$ on a worst-case pair of datasets $\\tilde{x},\\tilde{x}'$**. We experimentally demonstrate this via comparison with the bounds of Balle et al. in Appendix B.1.4.  To overcome this limitation, we propose to limit the recursion depth in order to obtain a smaller upper bound that matches **our specific subsampled mechanism $m$ on a worst-case pair of datasets $\\tilde{x},\\tilde{x}'$**. Limiting the recursion depth means upper-bounding $\\Psi_{\\alpha}(m_x || m_{x'})$ in terms of mixture divergences that have not been fully decomposed. Specifically, we propose to do so via [...]\".\n\nPlease let us know if you find this explanation more helpful.\n\n### Beyond group privacy and a unified view on known results\nWe agree with you on this point. The potential applications of our framework beyond group privacy are more exciting than the typical Poisson / without replacement / with replacement subsampling setting.\n\nWe would nevertheless like to point out that our unified view lets us **close gaps in existing literature that have not previously been discussed.** Specifically, we derive Renyi differential privacy bounds for various combinations of subsampling schemes, dataset relations, and neighboring relations -- effectively bringing the generality of Balle et al.'s work [1] to moments accounting (see Appendix I). While moments accounting has been supplanted by PLD accounting in the context of DP-SGD, it still finds use in various other applications of DP (e.g. [2]). We further provide the first formal derivation of dominating pairs for subsampling with replacement, which appear in prior work [3] but are not formally proven therein.\n\n### Editorial suggestions\n\n**Simplifing quantifier constraints, e.g., l.193**  \nFollowing your feedback, we will make the simplifying assumption that the batch neighboring relation is symmetric throughout the main text. We will further eliminate domain subscripts when clear from context.   This will allow us to rewrite the constraint in l.193 (also l.225) as $\\forall t, u: d(\\hat{y}^{(1)}_t, \\hat{y}^{(2)}_u) \\leq d(y^{(1)}_t, y^{(2)}_u)$, which should be  easier to parse.\n\n**Missing variables under sum in l. 178**  \nThank you, we will specify the summation variables in our revision.\n\n**$x'$ not $x$ in l. 852**  \nThank you for pointing out this typo, we will correct it.\n\nAgain, please remember that we unfortunately cannot upload a revision during the rebuttal period.\n\n---\n\nAgain, thank you for your review!  \nTo conclude, we hope that we addressed all your comments to your satisfaction.  \nPlease let us know if you have any further questions or comments during the author-reviewer discussion period!\n\n---\n\n[1] Balle et al. \"Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences\". NeurIPS'18  \n[2] Chen et al. \"Improved Communication-Privacy Trade-offs in 𝐿2 Mean Estimation under Streaming Differential Privacy\". ICML'24  \n[3] Koskela et al. \"Computing Tight Differential Privacy Guarantees Using FFT\".  AISTATS'20", "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": "", "extra_scores": {}}, {"review_id": "0EzPv9hLUd", "reviewer": "Reviewer_T1S1", "summary": "The authors propose a general framework for deriving mechanism-specific differential privacy guarantees for amplification by subsampling. The current methods are generally only tight in a mechanism-agnostic sense, but may possibly be significantly more private. The authors propose a new framework using conditional optimal transport, which allows stronger mechanism-specific subsampling guarantees, while still recovering the mechanism-agnostic guarantees. They also derive guarantees for privacy accountants in a unified manner. As an application, they derive tight guarantees for group privacy, where previously only a weak bound is known.", "questions": "- Is there any intuition about the types of scenarios where this new framework gives improvements over existing mechanism-agnostic bounds?", "limitations": "- See weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The problem being studied is important and relevant for practical applications.\n- The framework derived in this paper seems general and broadly applicable.", "weaknesses": "- The authors only demonstrate improvements in the privacy bounds using their framework for group privacy. It would be interesting to see if their general framework could give improvements in other practical areas. It would also be good to demonstrate utility improvement in practice when doing DP training with these improved bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for you are review!  \nWe are glad to hear that you find the studied problem important and the proposed framework broadly applicable.\n\n### Application to other practical areas\nWe agree that, while group privacy is highly important in practice,  future work should focus on applying our framework to other practical areas where data is subsampled or transformed via random functions.\n\nWe would like to point out that we do in fact demonstrate improvements for another practically relevant application besides group privacy:\n**Differentially private deep learning where batches are not created via i.i.d. subsampling, but via shuffling of the dataset**. We discuss this in Appendix P, which we reference from our \"Future Work\" section. In this preliminary result,  we assume the batch size to be half the dataset size. By analyzing the distribution of all batches in the epoch jointly, we can derive tight bounds that demonstrate the benefit of shuffling over i.i.d. subsampling (see Fig. 24). As such, this can be seen as a step towards \"tight epoch-level subsampling analysis\", as opposed to the currently prevalent \"iteration-level subsampling analysis\".\n\n\n## Utility improvement in DP training\nThank you for this suggestion!\nAs the experiments in our initial submission already demonstrate (e.g. Fig. 6), our tight group privacy analysis lets us train for more epochs before exceeding a given privacy budget $\\varepsilon$ at a given $\\delta$ -- regardless of which specific dataset, model architecture, or hyperparameters we consider.\n\nBased on your suggestion, **we have additionally investigated the effect this longer DP-SGD training has on training a model** for MNIST image classification (for details, see Fig. 2 in the pdf attached to the global rebuttal comment above).\n\nEven for group size $2$ and a large privacy budget of $\\varepsilon=8$ and $\\delta=10^{-5}$, post-hoc application of the group privacy property only allows training for $283$ iterations. This causes the training to stagnate at $79.6\\%$ validation accuracy. Our tight mechanism-specific analysis allows us to either train for significantly more epochs or to terminate training after a few epochs with less privacy leakage and higher accuracy.\n\nOnce we can upload a revision, we plan to repeat this experiment for a wider range of parameters, and also train or fine-tune on some larger-scale image dataset.\n\n### Intuition for improvements\nThis is a great question. Our intuition is as follows: As Fig. 2 in our original submission shows, all prior work on subsampling analysis relies on a binary partitioning of the subsampling event space. This is sufficient for many scenarios in which we either have maximum or no privacy leakage, e.g., \"the modified element is sampled\" vs \"the modified element is not sampled\".\n\n**Our framework is advantageous in scenarios where there are granular levels of privacy leakage.** For instance, when considering group privacy, we may sample $0$, $1$, or up to $K$ elements simultaneously. Another example is subsampling with replacement, where a single modified element can be sampled multiple times (see Fig. 3 in the pdf attached to the global rebuttal comment).\n\nBy partitioning the batch space into multiple events, we can conduct a more fine-grained analysis than the binary partitioning underlying prior work. This results in tighter bounds.\n\n---\n\nAgain, thank you for your review.  \nWe hope that we addressed all your comments to your satisfaction.  \nPlease let us know if you have any further questions or comments during the author-reviewer discussion period!\n\n---", "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": "", "extra_scores": {}}, {"review_id": "kvsBcM0Mqy", "reviewer": "Reviewer_cbWU", "summary": "The paper proposes a principled approach to analyzing group-privacy amplification through sub-sampling by generalizing the coupling arguments of Balle et al., 2018. This generalization extends the analysis from $1$-neighboring datasets to $K$-neighboring datasets. The core idea is to define a coupling between partitions of batches rather than the batches themselves, ensuring that the divergence of the output distribution, conditional on the partitioning, is bounded individually by the worst-case divergence. By carefully selecting the partitioning and the optimal coupling specific to the sub-sampling mechanism, the authors demonstrate that improved Rényi and Approximate DP bounds for group privacy can be achieved, surpassing the bounds obtained by applying privacy amplification by subsampling and group-privacy theorems separately. The paper shows that the combined analysis of grouping and subsampling can be tailored to a specific base mechanism, leading to mechanism-specific privacy amplification bounds that are superior to mechanism-agnostic bounds. Although the DP bounds presented are not in closed form, they can be numerically approximated to arbitrary precision using standard techniques from the literature. The paper also provides a comprehensive evaluation of how privacy is amplified for different group sizes under Gaussian, randomized response, and Laplace base mechanisms.", "questions": "I don't have any specific questions. I encourage authors to explain or address the problems I described in the weakness section. Based on how convincing the answers are, I'm open to adjusting my score.", "limitations": "Authors discuss some of the limitations of the paper. Following are some additional limitations that need addressing.\n\n- The ansatz is unwieldy for finding general use.\n- Closed-form asymptotics for the presented bounds are missing.\n- It's not clear if mechanism-specific subsampling bounds can be strictly better than mechanism-agnostic subsampling bounds for group size=1.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper presents an in-depth analysis of privacy amplification due to subsampling under groupings. This topic has not been extensively studied before, making it an interesting paper to read.\n\n- The paper demonstrates that there is a significant interplay between subsampling and grouping concerning privacy, which is not captured in standard analyses. This finding is an important contribution to the privacy community.\n\n- The paper argues that by considering the underlying base mechanism, the amplification bounds due to subsampling can be refined beyond the tight mechanism-agnostic bounds established by Balle et al., 2018. While the results indicate this improvement for group privacy, the paper also claims it applies more generally. This could be a significant finding (although I am not entirely convinced of its validity).", "weaknesses": "- The authors argue that tailoring privacy amplification through subsampling to a specific mechanism can yield better bounds than the tight amplification bounds established by Balle et al., 2018. However, it appears that the paper only demonstrates privacy amplification under subsampling for Approximate-DP with groups of size 2 or larger. Does this imply that for the standard setting with no grouping (i.e., group size of 1), there is no additional subsampling amplification achievable by tailoring the analysis to the mechanism?\n\n - I remain unconvinced that tailoring the analysis to a specific mechanism can result in tighter amplification-due-to-subsampling bounds for a group size of 1. Could the authors provide an example of two mechanisms, $\\mathcal{M}_1$ and $\\mathcal{M}_2$, that both satisfy $(\\epsilon, \\delta)$-DP tightly, but for some subsampling mechanism $S$, mechanism $\\mathcal{M}_1 \\circ S$ is $(\\epsilon', \\delta')$-DP while $\\mathcal{M}_2 \\circ S$ cannot achieve $(\\epsilon', \\delta')$-DP? \n\n- The figures in the paper (Figure 4 to Figure 10, Figure 13 to 15, Figure 17 to 20) do not include a baseline comparison with the separate application of tight amplification by subsampling and group privacy as described in lines 58-64. Without this comparison, it is unclear the gap between the bounds in this paper and the standard approach.\n\n- Definition 2.2 of Rényi divergence is misleading; a concave function $f(\\bullet) = \\frac{1}{\\alpha - 1} \\log(\\bullet)$ needs to be applied to your expression for $R_\\alpha(m_x\\Vert m_{x'})$ to obtain the Rényi divergence. The paper's expression for $R_\\alpha(m_x\\Vert m_{x'})$ is typically referred to as the $\\alpha$th moment of the privacy loss random variable. Although the moment $R_\\alpha$ may be jointly convex (a property heavily used in the paper), the Rényi divergence is not jointly convex due to the mapping $f$ being concave. Additionally, showing that $R_\\alpha$ shrinks by a factor of $p$ on subsampling does not mean that the Rényi divergence shrinks by a factor of $p$ due to the concavity of $f$. \n\n- The paper does not provide analytical bounds to help understand the asymptotics of the subsampling amplification results proved. Without the asymptotics, it's hard to verify claims of tightness.\n\n### Minor Concerns:\n\n- The privacy amplification results are not presented in a closed-form solution, making them difficult to operationalize.\n\n- The subsampling bounds for Rényi DP have not been compared with other existing works, such as [1,2].\n\n- The placement of figures does not match the respective appendices where they are discussed, making referencing the figures very challenging.\n\nReferences:\n\n[1] Steinke, Thomas. \"Composition of differential privacy & privacy amplification by subsampling.\" arXiv preprint arXiv:2210.00597 (2022).\n\n[2] Zhu, Yuqing, and Yu-Xiang Wang. \"Poisson subsampled Rényi differential privacy.\" International Conference on Machine Learning. PMLR, 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nPlease excuse our brevity, there is a character limit and you posed a lot of interesting questions. We cannot upload a revision during rebuttals, but will include your suggestions as soon as its possible.\n\n### Specific vs agnostic for group size 1\nFor group size 1, and **the special case of Poisson/WOR subsampling**, the agnostic bounds of Balle et al. [1] are tight in a mechanism-specific sense. This is a known result: Zhu et al. [2] used them to derive their tight dominating pairs (see proof of Prop. 30 in [2]).\n\nWe will add the following statement to ll.256-257:\n\"This bound is tight in a mechanism-agnostic sense [...]. For the **special case of group size $K=1$ and Poisson/WOR subsampling** this translates to mechanism-specific tightness (see [...])\".\nUpon discussion with reviewer 1 (eK4M), we will also include group size $1$ experiments.\n\n### Counterexample for group size 1\nThere are, nevertheless, schemes whose mechanims-specific bounds are stronger even for group size 1. An example is subsampling *with* replacement under substitution. In **Fig. 2 of the pdf attached to the global rebuttal comment above**, we compare the tight agnostic bound of Balle et al. [1] to the mechanism-specific bound posited by Koskela [3], which we proved in our work.\nThe bound of Koskela yields stronger privacy guarantees.\n\nUsing your notation, S is **subsampling with replacement**, $M_1$ is a Gaussian mechanism, $\\delta'$ is the mechanism-specific bound, and $M_2$ is the randomized membership mechanism from Section 5 of [1].\n\n### Comparison to group privacy  + tight bounds\nPlease note that **this baseline is precisely what \"post-hoc\" (i.e. post-hoc application of the group privacy property) refers to in our  figures**.\n\nWe will add the following to l. 311:\n\"In all figures, *agnostic* refers to tight mechanism-specific bounds and *specific* refers to tight mechanism-specific bounds. *Post-hoc* refers to post-hoc application of the group privacy property to tight mechanism-specific bounds for group size $1$.\"\n\n### Definition of Renyi divergence\nIt seems like there was a **misunderstanding due to notation, which we will correct**.\nThe expression $R_{\\alpha}$ is not intended to be the Renyi divergence.  We apply a concave transform to recover the Renyi divergence from $R_\\alpha$ in Definition 2.2 (l. 110). Joint convexity of this term is precisely  what is used in prior work on subsampling for Renyi DP, e.g., by Zhu & Wang [4].\n\nBased on your feedback, we will\n* Replace $R$ with a different character\n* Refer to it as \"$\\alpha$th moment of the Renyi divergence\" instead of \"scaled and exponentiated Renyi divergence\"\n\n### Asymptotic bounds\nWhile we focused on optimally charaterizing privacy with arbitrary precision to enable differentially private training, asymptotic upper bounds could provide an interesting alternative perspective. We assume that you refer to bounds as in \"Deep Learning with Differential Privacy\" [5].\n\nAs shown in Appendix N.4, the $\\alpha$th moment of the Renyi divergence for group size $K$ is bounded by $\\sum_{k=1}^K \\frac{1}{w} \\mathrm{Binom}(k \\mid K,r)\n\\sum_{l=1}^\\alpha \\binom{\\alpha}{l}w^l (1-w)^{\\alpha-l} \\zeta_k(l)$ with group profile $\\zeta_k(l)$ and $w=1-(1-r)^K$.\nFor Gaussian mechanisms, each of the $K$ inner sums is identical to the bound from [5] with varying sensitivity. We can thus directly use their result to obtain the asymptotic bound\n$\\sum_{k=1}^K \\frac{1}{w} \\mathrm{Binom}(k \\mid K,r)\n\\cdot\n\\left(w^2 k^2 \\alpha (\\alpha+1) \\mathbin{/} ((1-w) \\sigma^2) +\n\\mathcal{O}(w^3 k^3 \\mathbin{/} \\sigma^3)\\right)$.\n\nAlternatively, we could apply the analysis of Steinke [6] to each summand.\n\nFinding even better asymptotic bounds could be an interesting direction for future work. We will gladly include this result once we can upload a revision, thank you.\n\n### Judging tightness without asymptotic bounds\nPlease note that we can not only judge tightness (despite not providing asymptotic bounds in our initial submission), but **in fact formally prove it**. We do so by explicitly constructing a worst-case pair of datasets and  a worst-case sensitivity-bounded function that exactly attain our bound (see Appendix M.3).\n\n### Operationalizing the bounds\nYou are right, our mechanism-specific bounds sacrifice closedness in favor of tightness. They are nevertheless **easy to operationalize, because they let us determine a dominating pair of distributions** (see Section 3.4). Given a dominating pair, the bounds can be efficiently  evaluated to arbitrary precision via binary search, see Appendix M.4.1. This procedure is implemented in accounting libraries, which can analyze arbitrary dominating pairs in a plug-and-play manner.\n\n### Comparison to Zhu&Wang\nPlease note that their bound is precisely what we use as a baseline in our experiments on RDP (e.g. Fig.11) (see \"post-hoc\" discussion above).\n\n### Comparison to Steinke\nThank you for pointing out this great resource, which we will include in the related work section!\nNote that they primarily survey known results. Tight bounds for ADP were derived by Balle et al. [1], which we compare against. Similarly, their RDP bounds are restating results from Zhu & Whang [4], which we compare against.\n\n### Appendix figure placement\nOnce we can upload a revision, we will make sure that figures match their appendix sections.\n\n---\n\nAgain, thank you.\nWe look forward to the discussion period.\n\n[1] Balle et al. \"Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences\". NeurIPS'18  \n[2] Zhu et al. \"Optimal Accounting of Differential Privacy via Characteristic Function\". AISTATS'22  \n[3] Koskela et al. \"Computing Tight Differential Privacy Guarantees Using FFT\". AISTATS'20  \n[4] Zhu & Wang. \"Poisson subsampled Rényi differential privacy.\" ICML'19  \n[5] Abadi et al. \"Deep Learning with Differential Privacy\". CCS'16  \n[6] Steinke. \"Composition of Differential Privacy & Privacy Amplification by Subsampling\". arXiv", "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": "", "extra_scores": {}}, {"review_id": "6BiuDF0NS4", "reviewer": "Reviewer_t4hg", "summary": "The study proposes a framework utilizing optimal transport theory to derive mechanism-specific and mechanism-agnostic guarantees for subsampling mechanisms in differential privacy. It focuses on leveraging conditional optimal transport to establish tight bounds on privacy parameters such as α and β, crucial for various privacy scenarios including Rényi differential privacy and moments accounting. The experiments evaluate privacy guarantees under different mechanisms including Gaussian, Laplace, and randomized response, with specific settings for noise parameters and group sizes.", "questions": "Will the approach be adopted to LDP?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Defining partitions into events based on dataset manipulation scenarios.\n        - Creating couplings between conditional distributions to ensure compatibility.\n        - Bounding mixture divergences using worst-case mixture components.\n        - Employing advanced joint convexity techniques to tighten divergence bounds.\n        - Applying distance-compatible couplings to enhance robustness of privacy guarantees.", "weaknesses": "This manuscript is too long, which are 100 pages.  \nLack of theoretical analysis in the main text", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n### Concerning appendix length\nPlease let us explain how we ended up with the current page count. Our work proposes a framework for conducting subsamling analysis.\nWe claim that this framework lets us prove any known subsampling guarantee (as well as novel guarantees, such as group privacy amplification) using a standard recipe.\n**We did not see any way of verifying this claim, other than going back through approximately 8 years of privacy amplification literature and re-deriving their respective results**, as well performing similar derivations for other subsamling settings.\n\nThe **appendix sections that we would actually consider to be supporting  the core of our paper** are\n* D - General setting and Definitions (2 pages)\n* E - Proof of optimal transport bounds (2 pages)\n* F - Distance-compatible couplings (3 pages)\n* M.1-M.3 - Group privacy amplification & Tightness (5 pages)\n* O.1 - Worst-case mixture components for Gaussian & Laplacian mechanisms (8 pages)\n\nWhen focusing on these appendices, that are not merely meant to verify the above claim, this appendix length is much more in line with other machine learning conference papers on differential privacy, e.g., [1].\n\n### Theoretical analysis in main text\nThank you for this suggestion.\nBased on your comment, **we will move Theorem M.4 and its proof, which show the **tightness of our group privacy bounds**, to the main text.** We think that this specific theoretic result could be particularly interesting for future readers, as it helps illustrate the difference between mechanism-agnostic and mechanism-specific bounds.\n\nPlease let us know if there is any other specific analysis that you would like us to move to the main text instead. Note that we cannot upload a revised manuscript during the rebuttal period, but will make these changes as soon as its possible.\n\n### Adoption to local differential privacy\nThis is an interesting question that we can answer in the positive.\nLocal differential privacy is concerned with privately sharing the information of a single user. As such, there is usually not a collection of multiple records that we could subsample from.\n\nHowever, one can consider a scenario where this  **single user has a collection of $N$ attributes, $K$ of which are sensitive** (e.g. age, income, gender). If they randomly sample a subset of attributes (or functions thereof) to privately share via a noisy mechanism, then our results are directly applicable. They will either share $0$, $1$, or up to $K$ of the sensitive attributes with a certain probability.  We can thus use exactly the same group privacy amplification bound derived in our work.\n\n---\n\nAgain, thank you for helping us in further improving our manuscript.  \nPlease let us know if you have any further questions or comments during the author-reviewer discussion period!\n\n---\n\n[1] Zhu et al. \"Optimal Accounting of Differential Privacy via Characteristic Function\". AISTATS'22", "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": "", "extra_scores": {}}]

Author rebuttal:
We are very grateful for the helpful reviews we received.  
While we have already individually responded to each of the reviewers' insightful comments, we would like to use this global rebuttal comment to
1. Provide an overview of the figures in the attached pdf file
2. For the area chair's convenience, summarize the (small) changes we intend to make make to our manuscript once we can upload a revision.

Please note that **none of the intended changes affect our main contributions or the validity of any of our results**.  
Instead they provide novel perspectives or slightly more detailed explanations, in order to further improve accessibility for future readers.

## Attached pdf with figures

**Figure 1** shows that we will now also include group size 1 (i.e. traditional differential privacy) in our group privacy experiments.

**Figure 2** demonstrates that the increased number of training iterations enabled by our tight mechanism-specific group privacy analysis can in fact translate to higher model utility at a given privacy budget.

**Figure 3** showcases that mechanism-specific bounds can outperform tight mechanism-agnostic bounds even for group size 1 (here: subsampling *with* replacement).

## Intended changes

### Reviewer 1 (eK4M)
As suggested by reviewer 1, we will
* provide a short textual interpretation of Eq. 2 for accessibility (see rebuttal below for formulation),
* provide a short textual interpretation of Eq. 4 for accessibility (see rebuttal below for formulation),
* include group size 1 (i.e. traditional differential privacy) in all our group privacy experiments (see Fig.1 in attached pdf).

### Reviewer 2 (7Wbe)
As suggested to reviewer 2, we will
* slightly expand our textual motivation of Theorem 3.4 (see rebuttal below for formulation).

### Reviewer 3 (T1S1)
As suggested by reviewer 3, we will
* include an experiment on trained model utility (see Fig. 2 in attached pdf).

### Reviewer 4 (cbWU)
Following feedback by reviewer 4, we will
* clarify that mechanism-agnostic tightness *can* translate to mechanism-specific tightness for the special case of group size $1$ (see rebuttal below for formulation),
* include an experiment on subsampling with replacement to demonstrate that mechanism-agnostic tightness *does not always* translate to mechanism-specific tightness for group size 1 (see Fig. 3 in attached pdf),
* clarify that "post-hoc" in our figures refers to applying the group privacy property to tight group-size-1 bounds (see rebuttal below for formulation),
* include a novel asymptotic group privacy amplification bound at the end of Section 3.1 to provide *an additional perspective* on our tight guarantees (see rebuttal below for formula)
* cite Thomas Steinke's book chapter "Composition of Differential Privacy & Privacy Amplification by Subsampling", which surveys methods we compare against and could serve as a great introduction to future readers.

### Reviewer 5 (t4hg)
Following a suggestion by reviewer 5, we will
* move Theorem M.4 and a shortened version of its proof to the main text, to more directly showcase the theoretically proven tightness of our bounds.


### Notation / Formulations / Formatting
In addition to the above changes that improve accessibility and provide novel perspectives, we will
* Simplify constraint quantifiers in l. 193 and 225 to $\forall t, u: d(\hat{y}^{(1)}_t, \hat{y}^{(2)}_u) \leq d(y^{(1)}_t, y^{(2)}_u)$
* add missing variables under the sum operator in l.178,
* replace $x$ with $x'$ in l.852,
* correctly align figures in the appendix with their respective sections,
* replace $R_\alpha$ with a different character to avoid confusion between this "$\alpha$th moment" with the actual Renyi divergence,
* refer to it as $\alpha$th moment instead of "scaled and exponentiated Renyi divergence".

Meta-review: Reviewers were rather positive on this submission. Mechanism-specific privacy accounting has been quite a trend recently, giving markedly improved privacy bounds for a number of important applications. Reviewers appreciated this novel approach which is able to incorporate subsampling into the process. There were some critiques, e.g., the bounds are a bit tough to operationalize, and the paper is rather long (100 pages) and thus hard to check every detail. Nonetheless, we all agreed that it is a very interesting framework for an important problem, and thus worth of acceptance to the conference.
Decision: Accept (poster)