Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification

Authors: jan  schuchardt
mihail  stoian
arthur  kosmala
stephan  günnemann
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:09:49

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.

Main paper: 
 introduction: 
 Composability and amplification by subsampling are two key properties of Differential Privacy (DP) [1] [2] [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. [4] , Murtagh and Vadhan [5] ultimately derived tight composition theorems that optimally characterize the privacy parameters (ε ′ , δ ′ ) of a composed mechanism as a function of the component mechanisms' parameters (ε, δ). However, later work demonstrated that these guarantees are only tight in a mechanism-agnostic sense [6] . Stronger mechanism-specific 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. [6] [7] [8] [9] [10] [11] [12] ) are refererred to as 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 et al. [15] ultimately proposed a framework for deriving tight subsampling theorems that optimally characterize the privacy parameters (ε ′ , δ ′ ) of a subsampled mechanism as a function of the underlying base mechanism's parameters (ε, δ).However, their framework for deriving subsampling theorems has two key limitations. Firstly, as we shall demonstrate, the resultant guarantees are generally only tight in a mechanism-agnostic sense: Given (ε, δ), one can construct some worst-case (ε, δ)-DP mechanism that is (ε ′ , δ ′ )-DP 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 a novel framework for unified mechanism-specific amplification by subsampling analysis, using conditional optimal transport. Our proposed framework (1) lets us derive mechanism-specific subsampling guarantees, which can be stronger than mechanismagnostic 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 [7] ), and accounting with dominating pairs [10] (e.g., numerical accounting [16, 8, [17] [18] [19] [20] [21] ) in a unified, principled manner. Pr = (1 -𝑟𝑟) 2 Pr = 2𝑟𝑟(1 -𝑟𝑟)Pr = 𝑟𝑟 2 � � � � � � � � � 𝑥𝑥𝑥 3Figure 1 : Group members x ′ 1 , x ′ 2 contribute to a dataset, while group member x ′ 3 does not. For small subsampling rates r, it is unlikely to access a single (Pr = 2r(1 -r)) or even both (Pr = r 2 ) inserted elements when applying a base mechanism B to a subsampled batch (e.g., the yellow one). This further obfuscates which data was contributed by members of group {x ′ 1 , x ′ 2 , x ′ 3 }.As a practical application, we consider the problem of tightly analyzing group privacy under subsampling (see Fig. 1 ). Assume a scenario where K individuals may independently decide to contribute to a dataset. Further assume that this dataset is processed by randomly sampling a batch and applying an (ε, δ)-DP base mechanism. A special case of this setting is discussed in a recent technical note [22] , which assumes that the K individuals 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 guarantees (ε ′ , δ ′ )-DP for individuals and (2) use the group privacy property [23] to show that this implies (K • ε ′ , K • e K•ε ′ • δ ′ )-DP for the group.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 data to simultaneously appear in 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 mechanismspecific and mechanism-agnostic tightness in privacy amplification, • propose a 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-specific guarantees outperform both tight mechanism-agnostic bounds and post-hoc use of the group privacy property. 
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 P(A) of some finite discrete set A, that Y = {y ⊆ x | x ∈ X}, and that Z = R D . We further consider a random subsampling scheme S : X → Y that generates batches from datasets, and a random base mechanism B : Y → R D that maps batches to outputs. We write s x (y) for the pmf of S(X) and b y (z) for the pdf of B(y). In Appendix D, we introduce a more general setting that admits arbitrary spaces, for which we derive all our results. Our goal is to provide formal privacy guarantees for the subsampled mechanism M = B • 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 2 between datasets. For example, the insertion/removal relation x ≃ ±,X x ′ implies that x ′ = x ∪ {a} or x ′ = x \ {a} for some a. The substitution relation x ≃ ∆,X x ′ implies that x ′ = x \ {a} ∪ {a ′ } for some a, a ′ . In addition, we assume that Y is equipped with a batch neighboring relation ≃ Y ⊆ Y 2 . The batch relation ≃ Y can be distinct from the dataset relation ≃ X .Subsampling schemes. While we consider arbitrary subsampling schemes S : X → Y, we 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 ∈ [0, 1].A mechanism M : X → R D is privacy-preserving under symmetric neighboring relation ≃ X when the distributions of M (x), M (x ′ ) with densities m x , m ′ x are almost indistinguishable for all x ≃ X x ′ . Approximate differential privacy (ADP) [2] quantifies this via hockey stick divergences [25] :Definition 2.1. For ε ≥ 0, a mechanism M : X → R D is (ε, δ)-DP under symmetric relation ≃ X iff ∀x ≃ X x ′ : H e ε (m x ||m x ′ ) ≤ δ with H α (m x ||m x ′ ) = R D max{m x (z)/m x ′ (z)-α, 0}•m x ′ (z) dz. Note that this divergence-based definition of approximate differential privacy is equivalent to requiring for all datasets x ≃ X x ′ and all events S ⊆ R D that Pr[M (x) ∈ S] ≤ e ε • Pr[M (x ′ ) ∈ S] + δ.Rényi differential privacy. Privacy accounting was first popularized by methods that used moment bounds instead of (ε, δ) pairs to better track privacy under composition [6, 26, 27] . These methods were later developed into a moments-based notion of privacy -Rényi differential privacy (RDP) [7] :Definition 2.2. For α ≥ 1, a mechanism M : X → R D is (α, ρ)-RDP under symmetric relation ≃ X iff ∀x ≃ X x ′ : log(Λ α (m x ||m x ′ )) / (α -1) ≤ ρ with Λ α (m x ||m x ′ ) = R D m x (z) α • m x ′ (z) 1-α dz.Note that Λ α is not the Rényi divergence, but its αth moment, i.e., a scaled and exponentiated Rényi divergence. We use this notation to eliminate exponential terms that arise in amplification for RDP (see [28] [29] [30] ). If a mechanism is (α, ρ)-RDP, its T -fold self-composition is (α, T • ρ)-RDP. These RDP parameters can then be converted to ADP parameters (ε, δ), albeit in a lossy manner [7, 31, 32] . Dominating pairs. Later work proposed other numerical [16, 8, [17] [18] [19] [20] [21] or analytical accounting techniques [9, 33, 28, 34, 35] . Zhu et al. [10] developed a unified view on these works by introducing the notion of dominating pairs: Definition 2.3. A pair of distributions (P, Q) with densities (p, q) is a dominating pair for mechanism M under neighboring relation ≃ X , if H α (m x ||m x ′ ) ≤ H α (p||q) for all x ≃ X x ′ and all α ≥ 0.Given a dominating pair (P, Q), one can use various numerical or analytic techniques, such as convolution of privacy loss distributions [16] or central limit theorems of tradeoff functions [9] , to track the privacy of mechanism M under composition (see Fig. 2 in [10] ).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, 23] ): Definition 2.4. The distance d X (x, x ′ ) induced by relation ≃ X is the length of the shortest sequence (x 1 , . . . , x K-1 ) ∈ X K-1 such that x ≃ X x 1 , ∀k : x k ≃ X x k+1 , and x K-1 ≃ X x ′ . Example 2.5. Let ≃ X be the insertion/removal relation ≃ ± . Then the induced distance d X between x = {1, 2} and x ′ = {2, 3} is 2, because {1, 2} ≃ ± {1, 2, 3} ≃ ± {2, 3}. Proposition 2.6 (Vadhan [23] ).If mechanism M : X → R D is (ε, δ)-DP under relation ≃ X , then it is (K • ε, K • e K•ε • δ)-DP under group relation {(x, x ′ ) ∈ X 2 | d X (x, x ′ ) = K}.That is, for sufficiently small ε the ADP parameters deteriorate appproximately linearly with induced distance. As baselines for our experiments, we use even tighter bounds (see Appendix C.1.4). 
unified mechanism-specific amplification by subsampling: 
 Our goal is to develop a general procedure for (tightly) deriving ADP parameters (ε ′ , δ ′ ), RDP parameters (α ′ , ρ ′ ), or dominating pairs (P ′ , Q ′ ) for the subsampled mechanism M = B • S with 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 Λ α between the distributions of M (x) and M (x ′ ) with x ≃ X x ′ . To discuss both simultaneously, let us write Ψ α for either H α or Λ α and assume that α ≥ 0 or α ≥ 1, respectively.There are two challenges: Firstly, the distribution of M (x) is high-dimensional mixture distribution with one component per possible batch y ∈ Y and weights given by batch probabilitites s x (y), i.e., m x (z) = y∈Y b y (z) • s x (y). 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 to evaluate or bound Ψ α (m x ||m x ′ ).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 Ψ α in the space of probability density functions [37, 38] :EQUATION: R D → R + and weight w ∈ [0, 1]. Then, Ψ α (wf(1) 1 + (1 -w)f (1) 2 ||wf (2) 1 + (1 -w)f (2)2 ) ≤ wΨ α (f(1) 1 ||f (2) 1 ) + (1 -w)Ψ α (f (1) 2 ||f (2)2 ).In our case, the f s can be base mechanism densities b y with different y ∈ Y, and the weights can be given by the subsampling distribution. We could thus upper-bound the mixture divergence Ψ α (m x ||m x ′ ) in terms of component divergences -if the mixtures had identical weights. This is generally not the case, since subsampling mass functions s x (•) and s x ′ (•) depend on datasets x ̸ = x ′ .To still leverage the joint convexity of Ψ α (m x ||m x ′ ), we want to rewrite m x and m x ′ as mixtures with identical weights. This is exactly what is offered by couplings between probability mass functions. Intuitively, a coupling between two pmfs p 1 , p 2 : Y → [0, 1] specifies for every y 1 , y 2 ∈ Y how much probability should be transported from y 1 to y 2 to transform p 1 into p 2 . Couplings can be formalized and generalized to multiple pmfs as follows (for a more thorough introduction, see [39] ): Definition 3.2. A coupling between N pmfs p 1 , . . . , p N : Y → [0, 1] on batch space Y is a joint pmf γ : Y N → [0, 1] where the nth marginal is p n , i.e., p n (y* n ) = y∈Y N 1[y n = y * n ] • γ(y).Given a valid coupling γ between subsampling mass functions s x and s x ′ , we can use marginalization to rewrite m x (z) as y∈Y 2 b y1 (z)γ(y). Similarly, we can rewrite m x ′ (z) as y∈Y 2 b y2 (z)γ(y). Now, both m x and m x ′ are mixtures with identical weights and one component per pair of batches in Y 2 . We can thus recursively apply Lemma 3.1 to show (full proof in Appendix E): Theorem 3.3. Consider a subsampled mechanism M = B • S, and an arbitrary coupling γ between subsampling mass functions s x (•) and s x ′ (•). Then,Ψ α (m x ||m x ′ ) ≤ y∈Y 2c α (y (1) , y (2) ) • γ(y (1) , y (2) )with cost function c α : Y × Y → R + defined by c α (y (1) , y (2) ) = Ψ α (b y (1) ||b y (2) ).We write y (1) instead of y 1 to simplify later notations. While every coupling γ yields a valid upper bound, the guarantees can be tightened by finding a coupling γ * that minimizes the r.h.s. of Eq. (1) . We thus have an optimal transport problem, where the cost c α of transporting probability from batch y (1) to batch y (2) depends on the divergence Ψ α of base mechanism densities b y (1) and b y (2) .Unfortunately, experimental evaluation in Appendix B. 1.4 shows that the resultant guarantees can be much weaker than those from prior work -even with an optimal coupling γ * . This is because Theorem 3.3 results from recursively applying the joint convexity property (Lemma 3.1) to Ψ α (m x ||m x ′ ). 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 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 even the divergence Ψ α ( mx || mx ′ ) achieved by a worst-case subsampled mechanism M on a worst-case pair of datasets x, x′ . 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 on a worst-case pair of datasets x, x′ .Limiting the recursion depth to which Lemma 3.1 is applied means upper-bounding Ψ α (m x ||m x ′ ) in terms of mixture divergences that have not been fully decomposed into their individual components. 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 I i=1 A i = Y and J j=1 E j = Y of batch space Y such that all A i and E j have non-zero probability under the distribution of S x and S x ′ , respectively. Let γ be an arbitrary coupling between conditional mass functions s x (• | A 1 ), . . . , s (1) , y (2) ) • γ((y (1) , y (2) )), with cost function c α : Y I × Y J → R + defined by c α (y (1) , y (2) x (• | A I ), s x ′ (• | E 1 ), . . . , s x ′ (• | E J ). Then, Ψ α (m x ||m x ′ ) ≤ y∈Y I+J c α (yEQUATIONIn other words: We now have an optimal transport problem between I + J probability mass functions coupled by γ. The transport cost c α is a divergence between two mixtures. The components of the first mixture are base mechanisms densities given batches y(1) iAs a concrete example, and to illustrate the difference between mechanism-specific and -agnostic (see Section 3.2) bounds, let us consider the group privacy setting from Fig. 1 . 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. To provide formal privacy guarantees to the group, we need to prove that the distributions of M (x), M (x ′ ) are almost indistinguishable for x, x ′ with induced distance d ±,X (x, x ′ ) ≤ K. Let x ≃ K+,K-,X x ′ be the relation that implies that K + records are inserted and K -records are removed to construct x ′ from x. We can then show (full proof in Appendix M): Theorem 3.7. Let M = B • S, where S is Poisson subsampling with rate r. Let ≃ Y be the insertion/removal batch relation ≃ ±,Y . Then, for all x ≃ K+,K-,X x ′ , Ψ α (m x ||m x ′ ) is l.e.q.EQUATIONsubject to constraints y ∈ Y K-+K++2 , as well as ∀l ∈ {1, 2}, ∀t, u : d Y (yEQUATIONu ) ≤ |t -u|, and ∀t, u : d Y (y(1) t , y (2) u ) ≤ (t -1) + (u -1).Proof sketch. We let A i and E j be the events that S(x) contains i -1 deleted elements and S(x ′ ) contains j -1 inserted elements, respectively. Our coupling defines the following generative process: We sample y(1)1 from s x (• | A 1 ) and let y (2) 1 ← y (1)1 . We then iteratively generate the other y h + V with h : Y → R D and V ∼ N (0, σ 2 I D ). Define the ℓ 2 -sensitivity L 2 = max y≃ ±,Y y ′ ||f (y) -f (y ′ )|| 2 . Then for all x ≃ K+,K-,X x ′ , Ψ α (m x ||m x ′ ) is l.e.q. Ψ α   K-+1 i=1 f (1) i • Binom(i -1 | K -, r)|| K++1 j=1 f (2) j • Binom(j -1 | K + , r)   , with univariate normal densities f (1) i = N (• | (i -1), σ / L 2 ), f (2) j = N (• | -(j -1), σ / L 2 ).Note that this bound is mechanism-specific in that it explictly depends on B being a Gaussian mechanism with standard deviation σ and sensitivity L 2 . 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 a mechanism-specific sense: One cannot derive stronger ADP or RDP guarantees without additional information about the datasets x, x ′ ∈ 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 α. For completeness, we use Theorem 3.8 to generalize the asymptotic bounds of Abadi et al. [6] to 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 Ψ α = H α , K -= 0 or K + = 0, and Gaussian mechanisms was𝑆𝑆(𝑋𝑋)| 𝐴𝐴 1 𝑆𝑆(𝑋𝑋)| 𝐴𝐴 2 𝑆𝑆(𝑋𝑋𝑋)| 𝐸𝐸 1 𝑆𝑆(𝑋𝑋𝑋)| 𝐸𝐸 2 𝑆𝑆(𝑋𝑋)| 𝐴𝐴 1 , , 𝑆𝑆(𝑋𝑋)| 𝐴𝐴 𝐼𝐼 , 𝑆𝑆(𝑋𝑋𝑋)| 𝐸𝐸 𝐽𝐽 OT OT OT � � � � � � 𝑆𝑆(𝑋𝑋𝑋) 𝑆𝑆(𝑋𝑋𝑋)| 𝐸𝐸 1 , 𝑆𝑆(𝑋𝑋) 𝑆𝑆(𝑋𝑋𝑋) 𝑆𝑆(𝑋𝑋) 𝑆𝑆(𝑋𝑋𝑋) OT 𝑆𝑆(𝑋𝑋𝑋) 𝑆𝑆(𝑋𝑋) JOINTCONVEXITY 𝑆𝑆(𝑋𝑋)| 𝐴𝐴 1 𝑆𝑆(𝑋𝑋)| 𝐴𝐴 2 𝑆𝑆(𝑋𝑋) JOINTCONVEXITY (a) (b) (c) (d)Figure 2 : Mechanism-agnostic guarantees for (a) graph modification [40] [41] [42] (b) insertion/removal [14, 15, 29, 30] (c) substitution [43, 44, 15, 28] can be derived from (d) our proposed framework. In (b-c), events A i and E j 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 Ψ α ∈ {H α , Λ α }, arbitrary K + , K -∈ N 0 , and non-Gaussian mechanisms (see Appendix O).To further illustrate the difference between mechanism-specific and -agnostic bounds, let us apply the framework of Balle et al. [15] to the same setting: For K -= 0 or K + = 0 and ε ≥ 0, their ansatz shows that the subsampled mechanismM = B • S is (ε ′ , δ ′ )-DP with ε ′ = log(1 + (1 - Binom(0 | K, r)) • (e ε -1)) and δ ′ = K k=1 Binom(k | K, r) • δ k , with group privacy parameters δ k = max y,y ′ H exp(ε) (b y ||b y ′ ) s.t. d Y (y, y ′ ) ≤ k (see Appendix N).Tightness. This bound is tight in a mechanism-agnostic sense, i.e., for every ε ≥ 0, one can construct some worst-case mechanism that exactly attains the bound (see Appendix N.2).Mechanism-specific vs mechanism-agnostic tightness. An apparent advantage of this result is that it expresses (ε ′ , δ ′ ) as a simple analytic formula of base mechanism DP parameters ε, δ 1 , . . . , δ K . 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. 2 As we experimentally demonstrate in Section 4, this relaxation leads to weaker privacy guarantees for group size K ≥ 2. This gap has gone unnoticed in earlier work, because Theorem 3.8 happens to be identical to the bound of Balle et al. [15] for the special case of K = 1 (see proof of Proposition 30 in [10] ). By studying the more complex group privacy setting, we demonstrate for the first time that there is a qualitative difference between mechanism-agnostic and mechanism-specific tightness in privacy amplification.The observed relation between tight mechanism-specific and mechanism-agnostic bounds does in fact extend beyond group privacy (see Fig. 2 ): As we demonstrate in Appendices G and H, mechanismagnostic 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 a simultaneous coupling, and (3) using joint convexity to upper-bound the resultant mechanism-specific guarantee by component divergences. This includes the ADP guarantees of Balle et al. [15] (and thus prior work [14, 43, 44] ) and the RDP guarantees from [28] [29] [30] 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-agnostic guarantee derived via their ansatz can equivalently 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 is 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 I, we use this observation to derive a variety of novel mechanism-agnostic RDP bounds for different combinations of ≃ X , ≃ Y , and subsampling schemes, such as insertion/removal and subsampling without replacement. We further derive a simple but tight mechanism-specific guarantee for subsampled randomized response under substitution (see Theorem I.3) that outperforms the best known mechanism-agnostic bound (see Section 4).Because the mechanism-specific guarantees derived via our framework do not obfuscate the underlying distributions, they can be used to identify dominating pairs. These dominating pairs can then be combined with arbitrary (numerical) accountants to track privacy under composition. For example, we can immediately read off from Theorem 3.8 that the two Gaussian mixtures are a dominating pair for the "insert-K + -remove-K -" relation. In Appendix J, we describe a procedure for constructing dominating pairs when the bound is a 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 et al. [10] (special cases of which appear in [8, [17] [18] [19] 11] ) can equivalently be proven via our framework.Subsampling with replacement. As a novel contribution, we derive for the first time dominating pairs for subsampling with replacement (see Theorem L.5), which were posited but not proven in [8] (see discussion in Appendix L). This is enabled by our solution to the problem in Theorem 3.7. As we experimentally show in Appendix B.1.5, these bounds can be much stronger than those derived via the framework of Balle et al. [15] . These results thus demonstrate that there is a qualitative difference between mechanism-specific and mechanism-agnostic tightness even for group size K = 1.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. A 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 a preliminary result for 2-fold non-adaptive composition in Appendix P. Future work could also use our solutions to the problem in Theorem 3.7 to generalize the matrix mechanism analysis from [24] to substitutions and non-Gaussian distributions. 
experimental evaluation: 
 The purpose of the following experiments is to verify that there can be a benefit to using mechanismspecific over mechanism-agnostic subsampling bounds, and that a joint analysis of subsampling and group privacy can offer stronger guarantees than post-hoc application of the generic group privacy property. In all figures, "specific" refers to our proposed mechanism-specific bounds, "agnostic" refers to (tight) mechanism-agnostic bounds, and "post-hoc" refers to applying the generic group privacy property to tight mechanism-specific bounds derived for group size 1. For all experiments, we assume ℓ p sensitivities of 1. Further details on the experimental setup are provided in Appendix C. An implementation will be made available at https://cs.cit.tum.de/daml/group-amplification. RDP ρ(α) θ 0.9 0.75 0.6Figure 3 : Randomized response with WOR subsampling (q / N = 0.001), group size 1, and varying true response probability θ. Randomized response and RDP. One potential source of looseness in mechanism-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 us consider the best known guarantee for substitution, subsampling without replacement, and RDP from [28] . As discussed by the authors, it is only tight up to factors that are constant in α. In Fig. 3 we compare it to our tight mechanism-specific bound for randomized response (see Theorem I.3) with batch-to-dataset ratio q / N = 0.001 and true response probability θ ∈ {0.6, 0.75, 0.9}. In Appendix B.1.1 we consider other ratios. The tight guarantee eliminates the constant factors and thus achieves much smaller ρ for a wide range of α ∈ (1, 10 4 ].Group privacy and ADP. Another potential source of looseness in mechanism-agnostic bounds is that they stem from a 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. 4 , by comparing the tight mechanism-agnostic group privacy bound derived via the framework from [15] to our tight mechanism-specific bound for Laplace mechanisms (see Theorem M.2), ADP, scale λ = 1, subsampling rate r = 0.2, and varying group size. In Appendix B.1.2 we repeat the experiment with other mechanisms and parameter values, and also consider RDP. As discussed in Section 3.2, the mechanism-agnostic bound is identical to the mechanisms-specific bound for group size K = 1. For group sizes K ≥ 2, however, the fine-grained partitioning underlying the mechanism-specific bound yields stronger privacy guarantees. These results confirm that we need to distinguish between mechanism-agnostic and mechanism-specific tightness when analyzing complex subsampling settings.Single-iteration group privacy. Our next goal is 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 r = 0.2, and varying group size. As a baseline, we evaluate the same tight guarantee with K + + K -= 1 and apply the generic group privacy property (see Appendix C.1.4) in a post-hoc manner. As can be seen, our tight analysis can lead to much stronger privacy guarantees. However, we interestingly observe in Appendix B.2.1 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 (e.g., r = 10 -3 ).Composed group privacy. Nevertheless, even the gaps in tightness for very private mechanisms may quickly accumulate when repeatedly applying these mechanisms to a dataset. In Fig. 6 , we use the dominating pairs derived via our framework to conduct tight PLD accounting [16, 8] with "connect the dots" [20] quantization using Google's dp_accounting library [45] . For σ = 5, r = 10  
related work: 
 Amplification by subsampling for ADP. Using subsampling to strenghten (ε, δ)-DP guarantees has a long history [13, 14] particularly in privacy-preserving machine learning [46, 47, 6] . For a thorough introduction to subsampling and its interaction with composition, we refer the reader to [48] . Balle et al. [15] ultimately proposed a framework for deriving tight mechanism-agnostic subsampling guarantees. Our work subsumes theirs and enables the derivation of mechanism-specific guarantees.Amplification for privacy accountants. Abadi et al. [6] 's seminal work on moments accounting already considered subsampling. Similiar results were derived for the more general notion of RDP [7] in [28] [29] [30] . More recent works on accounting generally include a discussion of either Poisson subsampling or subsampling without replacement [17-19, 21, 11] . Subsampling with replacement is discussed in [8] , albeit without complete proofs, which we provide in Appendix L. We demonstrate that amplification guarantees for the central notions of RDP [7] and dominating pairs [10] can -just like guarantees for ADP -be derived via optimal transport. Our novel approach not only unifies prior, but also enables a 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 a 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., [3, 7, 9, 15, 23] ).Hierarchical randomized smoothing. Randomized smoothing [49] [50] [51] is a technique for constructing provably robust models via DP achieved through input perturbations (e.g. [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [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 variables in order to construct dominating pairs from weighted sums of divergences (see Appendix J.1).Unified amplification for f -DP. Wang et al. [70] proved a form of joint concavity for the tradeoff functions underlying f -DP accounting [9, 34] . This enables them to analyze mixtures induced by random initialization and shuffling in a 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-specific subsampling analysis and subsampling analysis for privacy accountants. To this end, we proposed a three-step procedure based on optimal transport between conditional subsampling distributions. Beyond recovering known guarantees for Rényi 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-specific 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 a higher level, these bounds represent a novel contribution to a larger body of work (e.g., [38, 71, 72] ) that demonstrates the benefit of analyzing multiple properties of differential privacy jointly instead of independently. 
acknowledgements: 
 We In Fig. 7 , we repeat the experiment from Fig. 3 with other ratios of batch and dataset sizes. That is, we compare our tight mechanism-specific RDP guarantee from Theorem I.3 to the best known mechanism-agnostic bound from [28] to illustrate that mechanism-agnostic bounds may loose privacy by bounding mixture divergences in terms of component divergences -even outside the group privacy setting. The tight guarantee eliminates constant factors and thus achieves much smaller ρ for a wide range of α ∈ (1, 10 4 ], especially for small ratios.q / N = 0.01 RDP ρ(α) q / N = 0.5 RDP ρ(α)Figure 7 : Randomized response under subsampling without replacement, with varying true response probability θ and batch-to-dataset ratio q / N . Theorem I.3 significantly improves upon the baseline for a wide range of α. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: Yes, we report the type and number of CPUs, as well as the number of workers and allocated runtime Appendix C.2.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, or 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: Yes, we discuss both positive and negative broader impact in Appendix Q, which we reference in our "Limitations, broader impact, and future work" section Section 3.5. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 out 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 are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 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 by 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 a best faith effort. 12. Licenses for existing assets Question: 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? Answer: [Yes] Justification: We list the libraries that we use and/or extend to 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 use existing assets. 
 
 Appendix: In Figs. 8 and 9 we repeat the experiment from Fig. 4 for other subsampling rates r, standard deviations σ, and also with Laplace mechanisms. That is, we 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-specific tightness is a stronger property that can 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 mechanisms for which the mechanism-agnostic bound is optimal (see [15] and Appendix N.2). ADP δ(ε)Figure 10 : Randomized response under Poisson subsampling, with varying true response probability θ, subsampling rate r, and group size. Randomized response is the worst-case mechanism for which the mechanism-agnostic guarantee is optimal, so both ansätze yield identical results.In Fig. 11 we repeat our comparison of mechanism-agnostic (Theorem N.5) and tight mechanismspecific group privacy amplification (Theorem 3.8) with RDP instead of ADP. We observe that the tight guarantee delays the phase transition from a high-to a low-privacy regime that was already observed in [30] . In other words, we have small ρ for larger α, which is beneficial for conversion to ADP after composition (see conversion formulae in [7, 31] ). Next, we demonstrate the benefit of coupling multiple conditional distributions over coupling just two subsampling distributions in deriving amplification guarantees. Specifically, we evaluate Proposition H.7, which can be derived via Theorem 3.3, i.e., optimal transport without conditioning. Note that, unlike with the guarantees of Wang et al. [28] , 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 q / L ∈ {0.01, 0.001}. But, for q / L = 0.1, there is a sweet spot of alphas between 10 1 and 10 2 in which it offers stronger guarantees. This further reinforces our claim that there is a benefit to treating group privacy and amplification jointly. Furthermore, we observe that in the case of q = 1, Proposition H.7 outperforms the baseline for large alpha, since it can capture that one cannot possibly include more than one substituted element in a singleton batch.Overall, we can conclude that there is a benefit to jointly analyzing group privacy and subsampling in this manner, but that optimal transport without conditioning is not sufficient for tightly analyzing such complicated scenarios. under sampling without replacement for varying dataset size N , batch size q, and group size. Optimal transport without conditioning does not always improve upon the baseline.N = 10 5 , q = 10 4The previous experiments demonstrated that mechanism-specific analysis can improve upon non-tight mechanism-agnostic and -in the group privacy setting -tight mechanism-agnostic analysis. In the following, we demonstrate that mechanism-specific 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 to Theorem 10 of Balle et al. [15] .Fig. 13 shows the resultant privacy profiles for standard deviation σ = 1, dataset size N = 100, and batch size q = 8. For ε ≥ 2, the mechanism-specific bound is 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 be sampled 0, 1, 2, or up to q times, with each case causing different levels of privacy leakage. Mechanism-agnostic bounds rely on a 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-specific bound is not tight. A tight bound might lead to an even larger gap. Thus, this experiments further reinforces that there is a qualitative difference between mechanism-specific and mechanism-agnostic tightness. That is, we compare our tight mechanism-specific guarantees to post-hoc use of the group privacy property. For all mechanisms, the tight mechanism-specific 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. In Fig. 17 we repeat our comparison of tight mechanism-specific 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 a 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.EQUATIONPost-hoc Specific r = 0.001, σ = 110 1 1.1 × 10 0 4 × 10 0 RDP α 10 -410 -1 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 a post-hoc manner delays the phase transition from high to low privacy. For very private base mechanisms and small subsampling rates, the baseline is nevertheless a good upper bound.In Figs. 18 to 21 we repeat our comparison of tight mechanism-specific and post-hoc group privacy amplification guarantees under composition from. We consider different combinations of subsampling rate r, standard deviation σ, privacy parameter ε, as well as Laplace mechanisms. Even in high privacy scenarios, where the mechanism-specific and post-hoc analysis yield similar results on a single-iteration level, the mechanism-specific guarantees are significantly stronger under composition. Specifically, the post-hoc analysis diverges to much larger δ after some number of iterations. In settings with moderate privacy (e.g. σ = 1) or large group sizes (e.g. 16), the baseline diverges after less than 100 iterations.Gaussian mechanism (r = 0.001) ADP δ(ε)ε = 0.5, σ = 1Figure 21 : Self-composed Laplace mechanisms under Poisson subsampling with subsampling rate r = 0.001 and varying scale λ, privacy parameter ε and group size. For sufficiently large group sizes, the post-hoc analysis divergence from the tight mechanism-specific guarantee within less than 1000 iterations.Finally, we compare tight group privacy amplification to the post-hoc approach for RDP accounting.We begin with the Gaussian mechanism and subsampling rate r = 0.001 in Fig. 22 . Our bound offers stronger group privacy guarantees for σ = 1.0, but both results are almost identical for very private base mechanisms with σ = 5.0. We suspect that this is because the phase transition from high to low privacy (recall Fig. 17 ), which the tight guarantee delays, gets shifted to very high α regions that are not useful for conversion to (ε, δ)-DP.Our observations for randomized response mechanisms (see Fig. 23 are also consistent with earlier results: For moderate subsampling rates r = 0.1, our guarantees are stronger, particularly for group size 8 and large numbers of iterations. But, when decreasing the subsampling rate to 0.001, both methods are almost identical. Nevertheless, group privacy amplification can demonstrably improve upon a direct combination of independently derived group privacy and amplification guarantees.Note that these observations are mostly of theoretic interest. In practice, one would use PLD accounting, which tightly characterizes the composed mechanism's privacy leakage, instead of the looser RDP accounting. As shown in Figs. 18 to 21, the tight mechanisms-specific analysis drastically outperforms the post-hoc analysis for PLD accounting.Gaussian mechanism r = 0.001, σ = 1 , true response probability θ = 0.6, and varying subsampling rate r and group size. The tight mechanism-specific analysis yields better privacy guarantees than the post-hoc baseline, except for small r where the baseline is a good upper bound.The previous results demonstrated that handling group privacy via a tight mechanism-specific analysis allows for a larger number of compositions, i.e., iterations at 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 in fact result in 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 C = 10 -4 , the Gaussian noise standard deviation to 0.6 • C, and the subsampling rate to r = 64 / 55000. The optimizer is ADAM with learning rate 1e -3. If the privacy budget is not used up earlier, training is terminated after 8 epochs, with ⌈55000 / 64⌉ iterations per epoch.Even with a large privacy budget of ε = 8 and δ = 1e -5, training with the post-hoc privacy analysis needs to terminate after less than 200 iterations. With the mechanism-specific analysis, δ does not even exceed 1e -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. In all experiments, we assume that all mechanisms have underlying sensitivity 1 w.r.t. ℓ ∞ (randomized response), ℓ 1 (Laplace), or ℓ 2 (Gaussian) output norms. We thus only specify noise parameters σ or λ, rather than the ratio of σ or λ 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 in 10 -3 , 10 1 , i.e., {10 x | x ∈ {-3, -3 + 4 120 , . . . , 1}}. We clip values of δ(ε) that are larger than 1 to [0, 1]. For our baselines, we enforce that δ(ε) 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. As our mechanism-agnostic 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 Gaussian and Laplace mechanisms, we evaluate group privacy profiles δ k (ε) by determining δ(ε) for the same mechanism with sensitivity k. For randomized response, we let δ k = δ 1 . This is referred to to as "white-box" group privacy in [15] ). We evaluate this baseline analytically.Post-hoc group privacy baseline. For our post-hoc baseline, we combine the tight Poisson subsampling guarantee for insertion/removal from [15] with the group privacy property of approximate differential privacy (see Appendix C.1.4 below). We evaluate this baseline analytically.Tight mechanism-specific group privacy. In all ADP figures "specific" refers to our tight group privacy guarantees for Gaussian (Theorem 3.8), Laplace (Theorem M.2), or randomized response mechanisms (Theorem M.3). We take the maximum over all K + , K -∈ N 0 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_accounting library [45] . We set the precision to 10 -6 , i.e., find the global optimum over multiples of 10 -6 . The bound for the randomized response mechanism is evaluated analytically in O(1).Privacy parameters. We evaluate all guarantees for α ∈ {2, 3, . . . , 1000}, as well as 121 logspaceequidistant values in [0, 10 4 ] rounded to the next smallest integer (without 0 or 1), and 121 logspaceequidistance values in (1, 10] . For our baselines, we enforce that ρ(α) is monotonically increasing by taking a running minimum from smaller to larger α (this may improve but never worsens the baselines).Mechanism-agnostic group privacy baseline. As our mechanism-agnostic 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 α, we use the binomial expansion in Eq. ( 33) (without factor 2). For Gaussian and Laplace mechanisms, we evaluate group privacy profiles ζ k (α) by determining ζ(α) for the same mechanism with sensitivity k. For randomized response, we let ζ k = ζ 1 . For continuous α, we apply tanh-sinh-quadrature with 50 digits of decimal precision to Eq. ( 33)Post-hoc group privacy baseline. For our post-hoc baselines, 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.1.4 below). For Poisson subsampling and integer α, we use the binomial expansion from [30] (without factor 2). For continuous α, we apply tanh-sinh-quadrature with 50 digits of decimal precision. For subsampling without replacement, we use the improved selfconsistency bound (Theorem 27 from [28] ), which we evaluate via tanh-sinh-quadrature with 50 digits of decimal precision due to the intractability of the nested binomial expansions for larger α.Tight mechanism-specific group privacy. In all RDP figures "specific" refers to our tight group privacy guarantees for Gaussian (Theorem 3.8), Laplace (Theorem M.2), or randomized response mechanisms (Theorem M.3). We take the maximum over all K + , K -∈ N 0 with K + + K -= K, where K is the group size. To evaluate the bounds for Gaussian and Laplace mechanisms, we use tanh-sinh-quadrature 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).RDP accounting. For RDP accounting, we simply evaluate the single-iteration guarantees as described in Appendix C.1.2. We then multiply the ρ(α) with the number of iterations, apply the improved RDP-to-ADP 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 it after composition, due to additivity of composition).PLD accounting. For PLD accounting with dominating pairs, we use the implementation of the dp_accounting library [45]. To quantize the privacy loss distribution, we use "connect the dots" [20] with pessimistic estimates, a discretization interval size of 10 -3 , and truncation of e -50 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 (ε, δ)-DP under neighboring relation≃ X . Then, M is (ε ′ , δ ′ )-DP with ε ′ = ε • K and δ ′ = K-1 k=0 e k•ε • δ. RDP.For RDP, we use the following result from Corollary 4 of [7] , which provides tighter guarantees than the upper bound in their Proposition 2. Let D α be log(Λ α ) / (α -1). This D α fulfills the following triangle inequality:D α (p||q) ≤ α -1 2 α -1 D 2α (p||r) + α α -1 D 2α-1 (r||q).We recursively apply this bound log 2 (K) times when evaluating the group privacy of our baselines for groups of size K.We conduct all experiments on a set of Xeon E5-2630 v4 CPUs @ 2.2 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 a few seconds). In total, we ran 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 as many jobs were executed.To perform high-precision quadrature for RDP guarantees, we use the tanh-sinh quadrature implementation from the mpmath library (version 1. In the following, we generalize some of the definitions introduced in Sections 2 and 3 to their measure-theoretic equivalents. The purpose of this generalization is to handle both continuous and discrete spaces, base mechanisms, and subsampling schemes, without having to make constant case distinctions.We use these more general definitions throughout the remaining appendix sections. The theoretic results presented in Section 3 follow as special cases.Unlike before, we assume that dataset space X is some arbitrary space, whose elements do not have to be sets. Instead, datasets x ∈ X can also be graphs, sequences or any other data collection. We further assume that the batch space is a measurable space (Y, Y) with σ-algebra Y. For example, Y can be composed of subsets, subgraphs, or subsequences. We also assume the output space to be a measurable space (Z, Z). Finally, we assume the existence of some measure λ on the output space, such as the Lebesgue measure for continuous Z or the counting measure # for discrete Z.Whenever we consider Poisson subsampling, we assume thatX ⊆ P(A), Y = {y ⊆ x | x ∈ X}, Y = P(Y), where A is some discrete, finite set and P(•) is the powerset.Whenever we consider subsampling without replacement with batch size q, we assume thatX ⊆ {x ∈ P(A) | |x| > q}, Y = {y ⊆ x | x ∈ X, |y| = q}, Y = P(Y), where A is some discrete, finite set and P(•) is the powerset.For set-valued datasets and batches, the insertion/removal relation and the substitution relation are formally defined as follows: Definition D.1. Sets x, x ′ ∈ X are related by the insertion/removal relation (x≃ ± x ′ ) if x ̸ = x ′ andthere is some a such that x ′ = x ∪ {a} or x ′ = x \ {a}. Definition D.2. Sets x, x ′ ∈ X are related by the substitution relation (x ≃ ∆ x ′ ) if there is some a ∈ x and a ′ / ∈ x such that x ′ = x \ {a} ∪ {a ′ }.In our general setting, we also allow non-symmetric neighboring relations.As before, the term "mechanism" refers to random functions that map to the output space (Z, Z). Formally, a random function M : X → Z is a family of random variables indexed by elements of X. Definition D.3. A random function M : X → Z is a function M : X × Ω → Z, where (Ω, F, P ) is some probability space and all M (x, •) : ω → M (x, ω) are measurable.We write P Mx : Z → [0, 1] for the distribution of random variable M (x). We further assume that each P Mx is absolutely continuous w.r.t. the aforementioned output measure λ, i.e., ∀x ∈ X : P Mx ≪ λ, and write m x : Z → R + for the corresponding Radon-Nikodym derivative dP Mx / dλ. For example, when the output space (Z, Z) is continuous and λ is the Lebesgue measure, then m x is the density.Similarly, we define our base mechanism to be a random function B : Y → Z and write P By : Z → [0, 1] for the distribution of base mechanism outputs given a batch y ∈ Y. We assume that each P By is absolutely continuous w.r.t. output measure λ and write b y : Z → R + for dP By / dλ.Finally, we define our subsampling scheme to be a random function S : X → Z and write P Sx : Y → [0, 1] for the distribution of batches given a dataset x ∈ X. We generally do not require P Sx to be absolutely continuous w.r.t. some other measure. When P Sx is absolutely continuous w.r.t. counting measure #, we write s x : Y → [0, 1] for the corresponding probability mass function dP Sx / d#.In particular, Poisson subsampling and subsampling without replacement are defined as follows: Definition D.4. Poisson subsampling with rate r ∈ [0, 1] has probability mass function s x (y) = r |y| (1 -r) |x|-|y| for batches y ⊆ x.Definition D.5. Subsampling without replacement with batch size q has probability mass functions x (y) = |x| q -1for batches y ⊆ x with |y| = q.As before, our goal is to provide privacy guarantees for subsampled mechanisms M = B • S. Similar to our discussion in Section 2, its distribution P Mx given a dataset x ∈ X is a mixture 3 withEQUATIONThere is one component per batch y from batch space Y, and the weights depend on subsampling distribution P Sx .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 on output space (Z, Z). Definition D.6.EQUATIONDefinition D.7. A pair of distributions (P, Q) with p = dP / dλ and q = dQ / dλ is a dominating pair for mechanism M under neighboring relationEQUATIONImportantly, note that Λ α is not the Rényi divergence as used in [7] . It is its αth moment, i.e., a scaled and exponentiated Rényi divergence. This is why a logarithm and quotient appears in Definition D.8. We use this definition, so that we can simultaneously discuss ADP and RDP without notational clutter.The joint convexity of Ψ α ∈ {H α , Λ α ) is not limited to densitites, but also applies to other nonnegative Radon-Nikodym derivatives of probability distributions [37, 38] :Lemma D.9. Consider arbitrary Radon-Nikodym derivatives fEQUATION:Z → R + and weight w ∈ [0, 1]. Then, Ψ α (wf (1) 1 + (1 -w)f (1) 2 ||wf (2) 1 + (1 -w)f (2) 2 ) ≤ wΨ α (f (1) 1 ||f (2) 1 ) + (1 -w)Ψ α (f (1) 2 ||f (2)2 ).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 a more general notion of couplings between distributions instead of couplings between mass functions: Definition D.10. A coupling between probability measures P 1 , . . . , P N on space (Y, Y) is a probability measure Γ on product space (Y, Y) N , where the nth marginal is P n , i.e., Γ • π -1 n = P n with projection π n (y) = y n .Here, • is the composition operator and π -1 n is the preimage (not necessarily the inverse) of the projection function. As before, when considering a coupling between two distributions P 1 , P 2 , the value Γ(T, R) specifies for all events T, R ∈ Y how much probability should be transported from P 1 (T ) to P 2 (R) to transform P 1 into P 2 .In the following, we show a more general statement for the general setting introduced in Appendix D. Theorem 3.3 immediately follows in the special case where batch space Y is finite and discrete, and the subsampling distribution has a probability mass function s x . Theorem E.1. Consider a subsampled mechanism M = B • S, and an arbitrary coupling Γ between subsampling distributions P Sx and P S x ′ . ThenΨ α (m x ||m x ′ ) ≤ Y 2c α (y (1) , y (2) ) dΓ((y (1) , y (2) ))with cost function c α (y (1) , y (2) ) = Ψ α (b y (1) ||b y (2) ).Proof. Recall that m x and m x ′ are mixtures with m x (z) = b y (z) dP Sx (y) and m x ′ (z) = b y (z) dP S x ′ (y). Since Γ is a coupling between P Sx and P S x ′ , we can use the projection π n (y) = y n and change of variables to rewrite these mixtures asm x (z) = Y b y (z) d Γ • π -1 1 (y) = Y 2 b π1(y) (z) dΓ(y) = Y 2 b y1 (z) dΓ(y), m x ′ (z) = Y b y (z) d Γ • π -1 2 (y) = Y 2 b π2(y) (z) dΓ(y) = Y 2 b y2 (z) dΓ(y).Since m x (z) and m x ′ (z) are now expectations w.r.t. the same measure, we can use the joint convexity of Ψ α (Lemma D.9) to show (1) , y (2) ) dΓ((y (1) , y (2) )), with cost function c : Y I × Y J → R + defined by c α (y (1) , y (2) Ψ α (m x , m x ′ ) ≤ Y 2 Ψ α (b y1 ||b y2 ) dΓ(y).Ψ α (m x ||m x ′ ) ≤ Y I+J c α (yEQUATIONProof. Using the law of total expectation, linearity of integration, and change of variables with projection π n (y) = y n shows thatm x (z) = I i=1 Y b y (z) dP Sx (y | A i ) P Sx (A i ) = Y I i=1 b y (z) • P Sx (A i ) dP Sx (y | A i ) = Y I i=1 b y (z) • P Sx (A i ) d(Γ • π -1 i )(y) = Y I+J I i=1 b yi (z) • P Sx (A i ) dΓ(y)andm x ′ (z) = Y I+J   J j=1 b y (j+I) (z) • P Sx (E j )   dΓ(y).Since m x (z) and m x ′ (z) are now expectations w.r.t. the same measure, we can use the joint convexity of Ψ α (Lemma D.9) to showΨ α (m x ||m x ′ ) ≤ Y I+J Ψ α   I i=1 b yi (z) • P Sx (A i )|| J j=1 b y (j+I) (z) • P Sx (E j )   dΓ(y).A change of indexing via y ). Then, c α (y (1) , y (2) ) ≤ ĉα (y (1) , y (2) ), with ĉα (y (1) , y (2) ) = maxEQUATIONEQUATIONEQUATIONu ) and ŷ(1)∈ Y I , ŷ(2) ∈ Y J .Proof. The original tuples of batches y (1) ∈ Y I and y (2) ∈ Y J constitute a feasible solution to the maximization problem, since they fulfill the constraints with equality, i.e., ∀k, l, t, u : d Y (yEQUATIONEQUATIONu ). The value of any feasible solution to a maximization problem is l.e.q. its optimal value. In the following, we generalize the notion of distance-compatible couplings proposed in [15] from two distributions to an arbitrary number of distributions. This provides a sufficient optimality condition for Theorem E.2.Note that we use a more general, measure-theoretic definition of distance-compatibility (see Definition F.4). Definition 3.6 is a special case for subsampling schemes with finite, discrete support.As discussed in Section 3, a d Y -compatible coupling between (conditional) subsampling distributions only assigns probability to tuples of batches y when all pairs y i , y j have the smallest possible distance to y 1 and to each other, while still being in the support of their respective distributions.To avoid having to make additional assumptions about the topology of batch space (Y, Y), we will assume that all subsampling schemes have densities and reason about the support of these densities. Definition F.1. The support of a function p :Y → R + is supp(p) = {y ∈ Y | p(y) > 0}.Based on this notion of support, we can define a notion of distance between a batch y ∈ Y and the support of a density: Definition F. = dΓ / d ν n . Then, Γ is a d Y -compatible coupling if (y ∈ supp(Γ) =⇒ ∀u > 1 : d Y (y 1 , y u ) = d Y (y 1 , supp(s u ))) ∧ (y ∈ supp(Γ) =⇒ ∀u > t > 1 : d Y (y u , y t ) = d Y (supp(s t ), supp(s u ))) .That is, Γ only assigns probability to a tuple of batches y if all y t and y u are as close as possible to y 1 and as close as possible to each other, while still being in the support of their corresponding densities. Note that our choice of focusing on y 1 is arbitrary, and d Y -compatibility could also be defined for any other reference index n ∈ {1, . . . , N }. ĉα (y (1) , y (2) ) dΓ((y (1) , y (2) )).(EQUATIONwhere G is the set of valid couplings between the I + J measures, and ĉα : Y I × Y J → R + is the cost function upper bound defined in Proposition 3.5.Proof. Consider an arbitrary, not necessarily d Y -compatible coupling Γ. By definition of ĉ and symmetry of ≃, we haveY I+Jĉα (y (1) , y (2) ) dΓ((y (1) , y (2) ))= Y I+J max ŷ∈Y I+J c α ( ŷ:I , ŷI: ) s.t. ∀t < u : d Y (ŷ t , ŷu ) ≤ d Y (y t , y u ) dΓ(y), with original cost function c α : Y I × Y J → R + defined in Theorem E.2.We can now use Lemma F.5 to tighten the constraints of the optimization problem inside the integrand and thus lower-bound its optimal value for all y ∈ supp(Γ): maxŷ∈Y I+J c α ( ŷ:I , ŷI: ) s.t. ∀t < u : d Y (ŷ t , ŷu ) ≤ d Y (y t , y u ) ≥ max ŷ∈Y I+J c α ( ŷ:I , ŷI: ) s.t. ∀u > 1 : d Y (ŷ 1 , ŷu ) ≤ d Y (y 1 , supp(s u )), ∀u > t > 1 : d Y (ŷ t , ŷu ) ≤ d Y (supp(s t ), supp(s u )).We notice that the lower bound only depends on y 1 and shall thus refer to it as κ α (y 1 ). Further note that any y / ∈ supp(Γ) does not contribute to the integral. Since Γ is a valid coupling, we can marginalize out all variables except y 1 via projection π 1 (y) = y 1 to show Y I+J ĉα (y (1) , y (2) ) dΓ((y (1) , y (2) ))≥ Y I+J κ α (π 1 (y)) dΓ(y) = Y κ α (y 1 ) d(Γ • π -1 1 )(y 1 ) = Y κ α (y 1 ) dP Sx (y 1 | A 1 ).By construction of κ α , this holds with equality whenever Γ * is a d Y -compatible coupling.Finally, the exact derivations we 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 a d Y -compatible coupling exists: Corollary F. ĉα (y (1) , y (2) ) dΓ((y (1) ,EQUATION)where G is the space of valid couplings between the I + J measures, κ α (y 1 ) = maxŷ∈Y I+J c α ( ŷ:I , ŷI: ) s.t. ∀u > 1 : d Y (ŷ 1 , ŷu ) ≤ d Y (y 1 , supp(s u )), ∀u > t > 1 : d Y (ŷ t , ŷu ) ≤ d Y (supp(s t ), supp(s u )),and c α :Y I × Y J → R + is the original cost function defined in Theorem E.2.Thus, we can focus on constructing distance-compatible couplings when trying to derive existing or novel amplification by subsampling guarantees. Note that these result also generalize to asymmetric neighboring relations ≃ Y . We just wanted to avoid further complicating the indexing. Future work may want to generalize these results to a more general, topological notion of support that does not rely on the existence of subsampling densities.In the following, we first provide an overview of the framework for deriving mechanism-agnostic ADP guarantees proposed by Balle et al. [15] . 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-agnostic guarantees derived via this approach can be suboptimal.The framework from [15] uses four steps to derive tight mechanism-agnostic guarantees for subsampled 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 a construction that makes it possible to partition the subsampling probability mass functions as s x (y) = (1 -w)p x (y) + wq x (y) s x ′ (y) = (1 -w)p x (y) + wq x ′ (y), with probability mass functions p x , q x , q x ′ : Y → [0, 1] chosen such that q x and q x ′ have disjoint support and w ∈ [0, 1] is as small as possible.Note that, when considering typical subsampling schemes (Poisson, without replacement, with replacement) and single-element neighboring relations (insertion/removal, substitution), this partition is simply equivalent tos x (y) = Pr[S x ∈ A 1 ] • s x (y | A 1 ) + Pr[S x ∈ A 2 ] • s x (y | A 2 ) s x ′ (y) = Pr[S x ′ ∈ E 1 ] • s x ′ (y | E 1 ) + Pr[S x ∈ E 2 ] • s x ′ (y | E 2 ),where A 1 and E 1 are the event that the inserted/removed or substituted element is not sampled, and A 2 , E 2 are their complements (see Appendix B in [15] ).Using this construction, the densitities m x and m x ′ of subsampled mechanisms M = B • S can be rewritten asEQUATIONEQUATIONNext, one can rewrite the divergence H α (m x ||m x ′ ) via the following property: Proposition G.1 (Advanced joint convexity [15] ). Let m x , m ′ x : Z → [0, 1] be probability mass functions satisfying mx (z) = (1 -w)f (z) + wg(z) and m x ′ (z) = (1 -w)f (z) + wg ′ (z) for some w ∈ [0, 1], f, g, g ′ : Z → [0, 1]. Given α ≥ 1, let α ′ = 1 + w(α -1) and β = α ′ / α. Then the following holds: D α ′ (m x ||m x ′ ) = wD α (g||(1 -β)f + βg ′ ).Applying advanced joint convexity, followed by joint convexity to Eqs. ( 12) and (13) shows thatH α ′ (m x ||m x ′ ) ≤(1 -β)H α   y∈Y b y q x (y)|| y∈Y b y p x (y)   + βH α   y∈Y b y q x (y)|| y∈Y b y q x ′ (y)  Finally, one can construct a coupling γ : Y 2 → [0, 1] between q x and p x , as well as a coupling γ ′ : Y 2 → [0, 1] between q x and q x ′ . One can then invoke a special case of Theorem 3.3 with Ψ α = H α and the cost function upper bound from Proposition 3.5 to showH α ′ (m x ||m x ′ ) ≤ (1 -β) y∈Y 2ĉα (y (1) , y (2) )γ(y (1) , y (2) ) + β y∈Y 2 ĉα (y (1) , y (2) )γ ′ (y (1) , y (2) ).Since we are only considering pairs of batches, we have ĉα (y (1) , y (2) ) = max ŷ H α (b ŷ(1) ||b ŷ(1) ) s.t. d Y (y (1) , y (2) ) ≤ d Y (ŷ (1) , ŷ(2) ) with induced distance d Y from Definition 2.4. This specific cost function bound is referred to as "group privacy profile" in [15] .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 we would obtain through Theorem 3.4: Theorem G.2. Consider a subsampled mechanism M = B • S and some x, x ′ ∈ X. Assume that subsampling pmfs sx , s x ′ : Y → [0, 1] satisfy s x (z) = (1 -w)p x (z) + wq x (z) and s x ′ (z) = (1 -w)p x (z) + wq x ′ (z) for some w ∈ [0, 1] and p x , q x , q x ′ : Y → [0, 1]. Let γ : Y 2 → [0, 1]be an arbitrary coupling of q x , p x , and γ ′ : Y 2 → [0, 1] be an arbitrary coupling of q x , p x ′ . Then, there is a coupling γ : Y 4 → [0, 1] of p x , q x , p x , q x ′ such that for all α ≥ 1H α ′ (m x ||m x ′ ) ≤ y∈Y 2+2ĉα ′ (y (1) , y (2) )γ(y (1) , y (1) )≤ (1 -β) y∈Y 1+1ĉα (y (1) , y (2) )γ(y (1) , y (2) ) + β y∈Y 1+1 ĉα (y (1) , y (2) )γ ′ (y (1) , y (2) ), with cost function upper bound ĉα defined in Proposition 3.5, α ′ = 1 + w(α -1), and β = α ′ / α.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 γ : Y → [0, 1] that corresponds to the following generative process: We first sample y 2 from the coupling γ ′ (recall that a coupling is a joint mass function). This gives us two elements from the support of q x and q x ′ , respectively. Then, we sample y Formally, this coupling can be defined as γ(y (1) , y (2) ) = γ ′ (y(1) 2 , y (2) 2 ) • γ(y (1) 2 , y (1) 1 ) q x (y (1) 2 ) • 1 y (2) 1 = y (1) 1 .Validity of coupling. Before proceeding, we need to verify that this is a valid coupling, i.e., its four marginals are p x , q x , p x , q x ′ . For any y(1) 1 ∈ Y, we have y (1) 2 ,y (2) 1 ,y (2) 2 ∈Y 3 γ(y (1) 1 , y (1) 2 , y (2) 1 , y (2) 2 ) = y (1) 2 ,y (2) 2 ∈Y 2 γ ′ (y (1) 2 , y (2) 2 ) • γ(y (1) 2 , y (1) 1 ) q x (y (1) 2 ) = y (1) 2 ∈Y q x (y (1) 2 ) • γ(y (1) 2 , y (1) 1 ) q x (y (1) 2 ) = y (1) 2 ∈Y γ(y (1) 2 , y (1) 1 ) =p x (y (1) 1 ).where the first inequality is due to the indicator function, the second equality follows from marginalizing γ ′ , and the last equality follows from marginalizing γ.(2) 1 ∈ Y is analogous.2 ∈ Y, we similarly haveEQUATION2 ∈Y 2 γ ′ (yEQUATION2 ) • γ(y1 ) q x (yEQUATION)EQUATION2 ),and for any y(2)2 we haveEQUATION(2)EQUATION1 , y2 , y1 , y2 )EQUATION2 ∈Y 2 γ ′ (yEQUATION2 )EQUATION2 , y1 ) q x (yEQUATIONFirst inequality. Now that we have a valid coupling, we can use the same joint-convexity argument as in our proof of Theorem 3.4, combined with our cost function bound ĉα to showH α ′ (m x ||m x ′ ) ≤ Y 2+2 max ŷ H α ′ (1 -w)b ŷ(1) 1 + wb ŷ(1) 2 ]||1 -w)b ŷ(2) 1 + wb ŷ(2)• γ(y (1) , y (2) ),with each of the |Y 2+2 | optimization problems being constrained by ∀k, l, t, u : d Y (ŷ (k) t , ŷ(l) u ) ≤ d Y (y (k) t , y1 ) = 0, i.e., yEQUATION1 . We can thus use advanced joint convexity, joint convexity, and linearity of summation to obtain a looser bound viaEQUATION• γ(y (1) , y (2) )+ β Y 2+2 max ŷ H α b ŷ(1) 2 ||b ŷ(2) 2• γ(y (1) , y (2) ),with each of the 2 • |Y 2+2 | optimization problems being constrained by ∀k, l, t, u : d Y (ŷ(k) t , ŷ(l) u ) ≤ d Y (y (k) t , y (l) u ) and ŷ(1) ∈ Y 2 , ŷ(2) ∈ Y 2 .Next, we can further loosen this bound by dropping all constraints involving y 1 in the second optimization problem. Thus, by definition of the group privacy profile, we haveEQUATION• γ(y (1) , y (2) )EQUATION• γ(y (1) , y (2) ).Note that the first cost function term does not depend on y 1 . We can thus marginalize out these variables (recall Eq. ( 16) and Eq. ( 20)) to conclude our proof.The same argument also applies to the general problem setting defined in Appendix D: Given two couplings Γ, Γ ′ , we can define a product coupling Γ ∝ Γ • Γ ′ , invoke Theorem 3.4, and then apply (advanced) joint convexity to pessimistically upper-bound the guarantee that would be obtained through our proposed framework.Following our discussion, we can identify three potential sources for looseness in this approach for deriving mechanism-agnostic bounds. Firstly, it only uses a binary partitioning of subsampling pmfs s x and s x ′ . The resultant mechanism-specific 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 y In the following, we demonstrate that existing amplification by subsampling guarantees for Rényi-DP can be derived by instantiating our proposed framework (see Fig. 2 ). Specifically, we demonstrate that these guarantees can be derived via the procedure discussed in Section 3.3 and shown in Figs. 2b and 2c : (1) Conditioning on at most 4 events indicating the presence of inserted / deleted / substituted elements, (2) defining a simultaneous coupling, and (3) using joint convexity to upper-bound the resultant mechanism-specific guarantee by component divergences.These guarantees are mechanism-agnostic in the sense that they express the subsampled mechanism's privacy parameters (α, ρ) as a function of the base mechanism's privacy parameters. We derive guarantees for the general measure-theoretic 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 H.1 and H.2 are very similar to those in [28, 30] , safe for the discussion of couplings and d Y -compatibility. That is precisely the point: There is 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 ∆ α is not the Rényi divergence, but its αth moment, i.e., a scaled and exponentiated Rényi divergence (see Definition D.8).For subsampling without replacement and substitution relation ≃ ∆ we first show a more general result Theorem H.1. We then demonstrate that it can be upper-bounded via joint convexity of exponentiated Rényi divergence ∆ α to recover the guarantee from [28] .Theorem H.1. Let M = B • S be a subsampled mechanism, where S is subsampling without replacement with batch size q. Let ≃ Y be the substitution relation ≃ ∆,Y . Then, for α > 1 and allx ≃ ∆,X x ′ of size N , ∆ α (m x ||m x ′ ) ≤ max ŷ ∆ α ((1 -w) • b y (1) 1 + w • b y (1) 2 ||(1 -w) • b y (2) 1 + w • b y (2)2)EQUATION1 , y2 ) ≤ 1, d ∆,Y (yEQUATION2 ) ≤ 1, d ∆,Y (yEQUATION2 ) ≤ 1, y= y(2)1 , and with w = q / N . Proof. Consider arbitrary x ≃ ∆,X x ′ . By definition of ≃ ∆ , there must be some a ∈ x, a ′ ∈ x ′ such that x ′ = x \ {a} ∪ {a ′ }. We thus define both A 1 and E 1 from Theorem E.2 to be the event that neither a nor a ′ is sampled, i.e., A 1 = E 1 = {y ∈ Y | y ∩ {a, a ′ } = ∅}. We further define A 2 and E 2 to be the event that a or a ′ is sampled, i.e., A 2 = A 1 andE 2 = E 1 .By definition of subsampling without replacement, we haveP Sx (A 1 ) = P S x ′ (E 1 ) = HyperGeom(0 | N, 1, q) = 1 - q N , P Sx (A 2 ) = P S x ′ (E 2 ) = HyperGeom(1 | N, 1, q) = q N ,which corresponds to the weights (1 -w) and w, respectively. We further haveEQUATIONs x ′ (y | E 1 ) = |x|-1 q -1 if y ⊆ x ′ ∧ a ′ / ∈ y 0 otherwise , s x (y | E 2 ) = |x|-1 q-1 -1 if y ⊆ x ′ ∧ a ′ ∈ y 0 otherwise .Coupling. We now define a coupling γ : Y 2+2 → R + that corresponds to the following generative process: We first generate y1 by sampling a batch that does not contain a uniformly at random from x. We then let y(2)1 ← y (1)1 Finally, we pick a random element ã of y1 and replace it with a and a ′ to generate y γ(y (1) , y (2) ) = s x (y 1) , y (2) fulfills H.2 0 otherwise.(1) 1 | A 1 ) • 1 q if y (Condition H.2. A tuple y (1) ∈ Y 2 , y (2) ∈ Y 2 fulfills this condition when y(2) 1= y(1) 1 and ∃ã ∈ y Validity. We now show that this constitutes a valid coupling. Consider y 2 for which γ(y) is non-zero. Thus,y (1) 2 ,y (2) 1 ,y (2) 2 ∈Y 3 γ(y) = q • s x (y (1) 1 | A 1 ).The proof for y 2 . Specifically, these elements are all elements that do not appear in y (1) 2 . We thus haveEQUATION2 ∈Y 3 γ(y) = (|x| -q) • (|x| -1 -q)! • q! |x| -1 • 1 q = |x| -1 q -1 -1.The proof for y2 is analogous. Compatibility. Finally, we show that γ is a d Y -compatible coupling (see Appendix F). Whenever γ(y) > 0, thend Y (y (1) 1 , y (1) 2 ) = d Y y (1) 1 , supp(s x (• | A 2 )) = 1, d Y (y (1) 1 , y (2) 1 ) = d Y y (1) 1 , supp(s x ′ (• | E 1 )) = 0, d Y (y (1) 1 , y (2) 2 ) = d Y y (1) 1 , supp(s x ′ (• | E 2 )) = 1.Similarly, the pairwise distances between all y t , y u with u > t > 1 are identical to the distance of their respective supports: The batches have a distance of 1 because one can transform one into another using a single substitution. The supports have a distance of 1 because one can transition from one to another using a single substitution.The result then immediately follows from Corollary F.7.Next, we can derive the upper bound from [28] . For this derivation, we will use the following Lemma, which is proven in Appendix B of [6] : Lemma H.3. Consider two probability measures P, Q on output measure space (Z, Z, λ). Define p = dP / dλ and q = dQ / dλ. Then∆ α (p||q) = 1 + α l=2 α l (p(z) -q(z)) l q(z) 1-l dλ(z).The following proof essentially follows that of [28] , but skips their Appendix B.2, since we have already successfully decomposed mixtures m x and m x ′ into small terms that only involve base mechanism densities.Proposition H.4 (Wang et al. [28] ). Let M = B • S be a subsampled mechanism, where S is subsampling without replacement with batch size q. Let ≃ Y be the substitution relation ≃ ∆,Y . Then, for α > 1 and all x ≃ ∆,X x ′ of size N , ∆ α (m x ||m x ′ ) is l.e.q.1 + 2 α l=2 α l w l max y≃ ∆,Y y ′ ∆ l (b y ||b y ′ ),with w = q / N .Proof. Using the constraint y(1)1 = y (2)1 in Theorem H.1, we can rewrite its objective as maxy (1) 1 ,y (1) 2 ,y (2) 2 ∆ α ((1 -w) • b y (1) 1 + w • b y (1) 2 ||(1 -w) • b y (1) 1 + w • b y (2) 2 ).Using Lemma H.3, we can upper-bound its optimal value via maxEQUATION(2) 2EQUATION2 ,yEQUATION2 ,yEQUATION2-b y (2) 2 | l (1 -w) • b y (1) 1 + w • b y (2) 2 l-1 dλ(z),where each of the α + 1 optimization problems is independently constrained by d Y (y2EQUATION2 ) ≤ 1, and d Y (yEQUATION2 ) ≤ 1. Next, we bound the optimal value of each of the α + 1 optimization problems. Using the joint convexity of x, y → x l • y 1-l , which implies convexity in the second component, shows thatEQUATION(1 -w)EQUATION2 ,yEQUATION2 ,yEQUATION2 ,yEQUATION2 ,yEQUATION2 ,y(2) 2 |b y (1) 2 -b y (2) 2 | l b l-1 y (1) 1 dλ(z),where all optimization problems are independent, with each one being independently constrained by d Y (y1 , y2EQUATION1 , y2 ) ≤ 1, and d Y (yEQUATION2 ) ≤ 1. Note that, for the last inequality, we replaced a y(2) 2 in the second maximization with a y (1) 1 , which essentially adds a degree of freedom and thus leads to an upper bound.In [28] , the optimal value of the final problem is referred to as the ternary-|χ| l -divergence of b 2 , b y Additional terms. Note that [28] derive three additional bounds (see their Lemma 17, Lemma 19, and Theorem 27) on the the ternary-|χ| l -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 a baseline in our experiments.Next, we show that the Poisson subsampling guarantees in [30, 7] follow from another optimal transport problem. For our proof, we will use the following Lemma, which corresponds to the "novel alternative decomposition" in Appendix A.1 of [30] . Lemma H.5. Consider K + 1 ∈ N distributions P, Q 1 , . . . , Q K on output measure space (Z, Z, λ), and define p = dP / dλ, q k = dQ k / dλ. Further consider some w 1 , . . . , w K ∈ [0, 1] withK k=1 w k = 1. Then, ∆ α p|| K k=1 w k • q k ≤ K k=1 w k • ∆ α q k + p - K l=1 w l • q l ||q k .Proof. Based on the definition of ∆ α , we have∆ α p|| K k=1 w k • q k = p(z) α K k=1 w k • q k (z) α-1 dλ(z) = K k=1 w k • q k (z) + p(z) - K l=1 w l • q l (z) α K k=1 w k • q k (z) α-1 dλ(z) = K k=1 w k • q k (z) + p(z) - K l=1 w l • q l (z) α K k=1 w k • q k (z) α-1 dλ(z)The result then follows from joint convexity of ∆ α .Note that the proof of this lemma is very similar to the proof strategy we used in deriving Proposition H.4 using Lemma H.3: We add 0 = c -c with some c 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 [30] ). Let M = B • S be a subsampled mechanism, where S is Poisson subsampling with rate r. Let ≃ Y be the insertion/removal relation ≃ ±,Y . Then, for α > 1 and allx ≃ ±,X x ′ , ∆ α (m x ||m x ′ ) is l.e.q. 2 • α l=0 α l r l (1 -r) α-l max y≃ ±,Y y ′ ∆ l (b y ||b y ′ ).Proof. Since we are concerned with insertion/removal, we need to consider two cases:Case 1: Removal. In this case, there is some a ∈ x such that x ′ = x \ {a}. We let A 1 be the event that a is not sampled, i.e. A 1 = {y ∈ Y | a / ∈ y}, and let A 2 = A 1 . We let E 1 = Y, i.e., do not condition on any particular event.By definition of Poisson subsampling, we have P Sx (A 1 ) = 1 -r, P Sx (A 2 ) = r, and P S x ′ (E 1 ) = 1. We further haveEQUATION2 ,yEQUATION2 ) ≤ 1, yEQUATION1 ) ≤ 1 Because y(1) 1 = y (2)1 and because d ±,Y (y(1) 1 , y (1) 2 ) ≤ 1 is equivalent to y (1) 1 ≃ ±,Y y (1)2 , this bound can be restated as∆ α (m x ||m x ′ ) ≤ max y≃ ±,Y y ′ ∆ α ((1 -r) • b y + r • b y ′ ||b y ).∆ α (m x ||m x ′ ) ≤ max y≃ ±,Y y ′ Z ((1 -r)b y (z) + rb y ′ (z)) α b y (z) α-1 dλ(z) = max y≃ ±,Y y ′ Z (1 -r)b y (z) + rb y ′ (z) b y (z) α b y (z) dλ(z) = max y≃ ±,Y y ′ Z (1 -r) + r b y ′ (z) b y (z) α b y (z) dλ(z) = max y≃ ±,Y y ′ α l=0 α l r l (1 -r) α-l ∆ l (b y ||b y ′ ) ≤ α l=0 α l r l (1 -r) α-l max y≃ ±,Y y ′ ∆ l (b y ||b y ′ ).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 a ∈ x ′ such that x = x ′ \ {a}. Very similar to before, we let A 1 = Y, i.e., we do not condition on any particular event. We further let E 1 be the event that a is not sampled, i.e. E 1 = {y ∈ Y | a / ∈ y}, and let E 2 = E 1 . We notice that we have exactly the same conditional distributions as in the first case. We can thus define exactly the same coupling (up to changes in indexing) to show that∆ α (m x ||m x ′ ) ≤ max y≃ ±,Y y ′ ∆ α (b y ||(1 -r)b y + rb y ′ ).Next, applying Lemma H.5 and using the definition of ∆ α shows that∆ α (m x ||m x ′ ) ≤ max y≃ ±,Y y ′ ∆ α (b y ||(1 -r)b y + rb y ′ ) ≤ max y≃ ±,Y y ′ (1 -r)∆ α (b y + b y -((1 -r)b y + rb y ′ )||b y ) + r∆ α (b y ′ + b y -((1 -r)b y + rb y ′ )||b y ′ ) = max y≃ ±,Y y ′ (1 -r)∆ α ((1 + r)b y -rb y ′ ||b y ) + r∆ α ((1 -r)b y ′ + rb y ||b y ′ )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 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 d Y -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, we can apply this more general optimal transport principle to a much broader range of amplification by subsampling scenarios for Rényi-DP.Further tightening. The factor 2 in Proposition H.6 can be eliminated for distributions with particular symmetries (see Theorem 5 in [29] ) or bounded Pearson-Vajda χ l -pseudo-divergence (see Theorem 8 in [30] ). We thus do not include the factor 2 when using this amplification guarantee as a baseline in our experiments.Daigavane et al. [40] consider a 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 = N,D∈N R N ×D × {0, 1} N ×N , which are composed of a continuous feature matrix and a discrete adjacency matrix. Two graphs x, x ′ 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 a 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 ⊆ P(A) for some set A, and the modification of a node's features and edges corresponds to the substitution of K elements, 4 i.e.EQUATIONwhere 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.1, i.e. optimal transport without conditioning. Proposition H.7 (Daigavane et al. [40] ). Let M = B • S be a subsampled mechanism, where S is subsampling without replacement with batch size q. Let ≃ Y be the substitution relation ≃ ∆,Y . Let ≃ K∆,X be the K-fold substitution relation defined in Eq. (22) . Then, for α > 1 and all x ≃ K∆,X x ′ of size N ,∆ α (m x ||m x ′ ) ≤ K k=0 w k • max y≃ k∆,Y y ′ ∆ k (b y ||b y ′ ).withw k = HyperGeom(k | N, K, q).Proof. Consider arbitrary x ≃ ∆,X x ′ . By definition of ≃ ∆ , there must be some g∈ x \ x ′ , g ′ ∈ x ′ \ x such that x ′ = x \ g ∪ g ′ and |g| = |g ′ | = K.We condition on the events A 1 = Y and E 1 = Y, meanings x (y | A 1 ) = N q -1 if y ⊆ x 0 otherwise and s x ′ (y | E 1 ) = N q -1 if y ⊆ x ′ 0 otherwise .Coupling. We now define a coupling via γ : Y 1+1 → R + that define the following generative process: We first define y (1) by sampling a batch of size q from x without replacement. We then remove all elements that are in g and insert an equal number of elements, which are chosen uniformly at random from g ′ . This coupling can be formally defined as γ(y (1) , y (2) ) = s x (y (1) | A 1 ) • K |y (1) ∩g| -1if y (1) , y (2) fulfills Condition H.8,. 0 otherwise.Condition H.8. A tuple y (1) ∈ Y, y (2) ∈ Y fulfills this condition when there exists a g ⊆ g such that y (2) = y (1) \ g ∪ g and |y (2) ∩ g| = |y (1) ∩ g|.Validity. We now show that this constitutes a valid coupling. Consider any y (1) with s x (y (1) | A 1 ) > 0 and |y (1) ∩ g| = k. There are exactly K k different y (2) for which γ(y) is non-zero, and each one has the same probability. Thus,y (2) ∈Y γ(y) = K k • s x (y (1) | A 1 ) • K k -1 = s x (y (1) | A 1 ). |x -1| q .The other case is analogous.Compatibility. Evidently, this is a d Y -compatible coupling, because (a) whenever y (1) contains k elements from g, it has a distance of k from s x ′ (y | E 1 ) and (b) whenever y (1) contains k elements from g, we generate y (2) by substituting exactly k elements.It thus follows from Corollary F.7 that (1) ∩ g|. The result then follows from the definition of induced distance, the definition of the K-fold substitution relation ≃ K∆,X and the fact that |y (1) ∩ g| is a random variable with distribution HyperGeom(N, K, q).∆ α (m x ||m x ′ ) ≤ y s x (y (1) | A 1 )κ α (y (1) ) with κ α (y (1) ) = max y,y ′ ∆ α (b y ||b y ′ ) s.t. d Y (y, y ′ ) ≤ |yNote that [40] instantiate this result with Gaussian mechanisms with sensitivity C, for whichmax y≃ k∆,Y y ′ ∆ α (b y ||b y ′ ) = exp(α • (α -1) • k 2 C 2 σ 2). In Appendix B.1.4, 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 it across a wide range of parameters. This emphasizes the benefit of considering optimal transport between proper conditional distributions when deriving amplification guarantees.Now that we have a framework that enables generic subsampling analysis for Rényi differential privacy, we can derive a variety of novel guarantees that were previously only available for approximate differential privacy.In the following, we first demonstrate that RDP guarantees for a dataset relation ≃ X can be derived from a base mechanism that is only known to be RDP under a different batch relation ≃ Y , i.e., "hybrid neighboring relations" [15] . We then show that we can derive RDP guarantees for nonstandard combinations of subsampling schemes and neighboring relations, such as subsampling without replacement and insertion/removal. Finally, we derive a simple, tight mechanism-specific subsampling guarantee for randomized response. We use this guarantee in Section 4 to demonstrate the limitations of using mechanism-agnostic RDP bounds instead of mechanism-specific RDP bounds.For this section, recall again that Λ α is not the Rényi divergence, but its αth moment, i.e., a scaled and exponentiated Rényi divergence (see Definition D.8).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, 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 I.2).As an example, we consider the following scenario: Subsampling without replacement, with substitution relation ≃ ∆,X for datasets and insertion/removal relation ≃ ±,Y for batches. The proof is largely identical to that of Theorem H.1, but uses the fact that a substitution can be represented by an insertion, followed by a removal.Theorem I.1. Let M = B • S be a subsampled mechanism, where S is subsampling without replacement with batch size q. Let ≃ Y be the insertion/removal relation ≃ ±,Y and ≃ X be the substitution relation ≃ ∆,X . Then, for α > 1 and all x ≃ ∆,X x ′ of size N ,EQUATION2 ) ≤ 2, and with w = q / N . Proof. Consider arbitrary x ≃ ∆,X x ′ . By definition of ≃ ∆ , there must be some a ∈ x, a ′ ∈ x ′ such that x ′ = x \ {a} ∪ {a ′ }. We thus define both A 1 and E 1 from Theorem E.2 to be the event that neither a nor a ′ is sampled, i.e., A 1 = E 1 = {y ∈ Y | y ∩ {a, a ′ } = ∅}. We further define A 2 and E 2 to be the event that a or a ′ is sampled, i.e., A 2 = A 1 andE 2 = E 1 .By definition of subsampling without replacement, we haveP Sx (A 1 ) = P S x ′ (E 1 ) = HyperGeom(0 | N, 1, q) = 1 - q N , P Sx (A 2 ) = P S x ′ (E 2 ) = HyperGeom(1 | N, 1, q) = q N ,which corresponds to the weights (1 -w) and w, respectively.Coupling. We now define a coupling via γ : Y 4 → R + :γ(y (1) , y (2) ) = s x (y 1) , y (2) fulfill Condition H.2, 0 otherwise.(1) 1 | A 1 ) • 1 q if y (Condition H.2. A tuple y (1) ∈ Y 2 , y (2) ∈ Y 2 fulfills this condition when y(2) 1= y(1) 1 and ∃ã ∈ y(1) 1 : y (1) 2 = y (1) 1 \ {ã} ∪ {a} ∧ y (2) 2 = y (1) 1 \ {ã} ∪ {a ′ } .Case 1: Removal. In this case, there is some a ∈ x such that x ′ = x \ {a}. We define N = |x ′ |, which fulfills N > Q by definition of dataset space X.We let A 1 be the event that a is not sampled, i.e. A 1 = {y ∈ Y | a / ∈ y}, and let A 2 = A 1 . We let E 1 = Y, i.e., do not condition on any particular event.By definition of subsampling without replacement, we have P Sx (A 1 ) = 1 -qN , P Sx (A 2 ) = q / N , and P S x ′ (E 1 ) = 1. We further haveEQUATIONs x ′ (y | E 1 ) = N q -1 if y ⊆ x ′ 0 otherwise . Note that s x (y | A 1 ) = s x ′ (y | E 1 )and that all three conditional distribution are subsampling without replacement from sets of size N , not of size N + 1 or N -1. Further note that, for event A 1 , we only need to sample q -1 elements, since one element is always fixed to be a.Coupling. We now define a coupling via γ : Y 2+1 → R + :γ(y (1) , y (2) ) = s x (y(1) 1 | A 1 ) • 1 q if y (1) 1 = y (2) 1 ∧ y (1) 2 = y (1) 1 ∪ {a} 0 otherwise.Simply put, γ defines the following generative process: We first generate y1 by sampling a batch that does not contain a via subsampling without replacement from x \ {a}. We then let y(2) 1 ← y (1) 1 .We then randomly replace one of the q batch elements with a to generate y Validity. We can verify the validity of this coupling as follows: For every y 1 for which γ(y) > 0. This is because a must have replaced one of the N -(q -1) elements of x ′ that are not in y(2)1 . We thus havey (1) 1 ,y (2) 1 ∈Y 2 γ(y (1) 1 , y (1) 2 , y (2) 1 ) =(N -(q -1)) • N q -1 • 1 q = q N -q + 1 • N q -1 = N q -1 -1 .Compatibility. Finally, it can be easily shown that γ is a d Y -compatible coupling. Whenever γ(y) > 0, thend Y (y (1) 1 , y (1) 2 ) = d Y y (1) 1 , supp(s x (• | A 2 )) = 2, d Y (y (1) 1 , y (2) 1 ) = d Y y (1) 1 , supp(s x ′ (• | E 1 )) = 0.Similarly, the pairwise distance between y 1 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 a removal.It thus follows from Corollary F.7 thatEQUATION2 ,yEQUATION2 ) ≤ 1, yEQUATION1 ) ≤ 2As in our proof of Proposition H.6 one can use the definition of Λ α and binomial expansion to finally show thatΛ α (m x ||m x ′ ) ≤ α l=0 α l w l (1 -w) α-l max y,y ′ Λ l (b y ||b y ′ ) s.t. d Y y, y ′ ≤ 2.with w = q / N . 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 a ∈ x ′ such that x = x ′ \ {a}. We can thus define the same events and the same coupling in a symmetric manner to showΛ α (m x ||m x ′ ) ≤ max y,y ′ (1 -w) Z (1 + w)b y (z) -wb y ′ (z) b y (z) α b y (z) dλ(z) +w Z (1 -w)b y ′ (z) + wb y (z) b y ′ (z) α b y ′ (z) dλ(z),subject to d Y (y, y ′ ) ≤ 2. with w = q / 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 to show that this term is at most two times larger than the one we derived in the deletion case.Finally, since this bound depends on N , and we want the guarantee to hold for all x ≃ ±,X x ′ , we need to determine the N that maximizes the bound.Hybrid Relations. Note that we could have also gone through the above derivations with batch substitution relation ≃ ∆,Y . Then, each substitution would correspond to an actual substitution, instead of a pair of insertion and deletion, and we would obtainΛ α (m x ||m x ′ ) ≤ max N ∈N 2 • α l=0 α l w l (1 -w) α-l max y≃ ∆,Y y ′ Λ l (b y ||b y ′ ) s.t. N > Q,with w = q / N .As mentioned earlier, the following result is meant as a simple example to demonstrate the benefit of using mechanism-specific over mechanism-agnostic RDP bounds in Section 4. For the following discussion, recall Theorem H.1, which we proved in the previous section. Theorem H.1. Let M = B • S be a subsampled mechanism, where S is subsampling without replacement with batch size q. Let ≃ Y be the substitution relation ≃ ∆,Y . Then, for α > 1 and allx ≃ ∆,X x ′ of size N , ∆ α (m x ||m x ′ ) ≤ max ŷ ∆ α ((1 -w) • b y (1) 1 + w • b y (1) 2 ||(1 -w) • b y (2) 1 + w • b y (2)2)EQUATION2EQUATION2EQUATION2 ) ≤ 1, y1 , and with w = q / N .We shall now solve Theorem H.1 for randomized response and prove the tightness of the resultant guarantee. Theorem I.3. Let B be the randomized response mechanism |h -(1 -V )| with h : Y → {0, 1}, V ∼ Bern(θ), and true response probability θ ∈ [0, 1]. Let S be subsampling without replacement with batch size q. Then, for allx ≃ ∆,X x ′ of size N , Λ α (m x ||m x ′ ) is l.e.q. max τ Λ α ((1 -w)Bern(• | θ) + wBern(• | τ )||(1 -w)Bern(• | θ) + wBern(• | 1 -τ ))subject to τ ∈ {θ, 1 -θ} and with w = q / N .Proof. Because we have no further information, we must consider the worst possible underlying function h : Y → {0, 1}.Our proposed optimal transport approach lets us derive mechanism-specific guarantees, which upperbound the hockey stick divergence between the distribution of M (x) and M (x ′ ) with x ≃ X x ′ via a weighted sum5 of mixture divergences, i.e.,EQUATIONHere, the w(x,x ′ ) α,kare weights withK k=1 w (x,x ′ ) α,k= 1, which depend on the chosen coupling γ and are indexed by α ≥ 0, 1 ≤ k ≤ K, and x, x ′ ∈ X. The p(x,x ′ ) α,kand p 6 which are also indexed by α ≥ 0, 1 ≤ k ≤ K, and x, x ′ ∈ X.(x,x ′ ) α,K are densities of mixture distributions P (x,x ′ ) α,k and q (x,x ′ ) α,K on the output space R D ,Our goal is to 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 a dominating pair for mechanism M under neighboring relation ≃ X , if H α (m x ||m x ′ ) ≤ H α (p||q) for all x ≃ X x ′ and all α ≥ 0.If the densities on the r.h.s. of Eq. ( 23) are constant in α, k, x, and x ′ , i.e.., p(x,x ′ ) α,k = p and q (x,x ′ ) α,k= q with some densitities p, q, then we can immediately identify that the corresponding distributions P and Q are a dominating pair. For instance, in Section 3.4 we could immediately determine that the two Gaussian mixtures in Theorem 3.8 are a dominating pair for Poisson subsampling and the "insert-K + -remove-K -" 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 a single divergence (2) resolve non-constancy in the dataset pairs (x, x ′ ), and (3) resolve non-constancy in the divergence order α.Note that, depending on the considered setting, it may be possible to skip one or multiple of these steps (like in our group privacy example).Consider some fixed order α and fixed datasets x ≃ X x ′ . Let us thus omit the corresponding indexes. In this step, we construct a pair of distributions P , Q with densitities p and q such thatK k=1 w k • H α (p k ||q k ) = H α (p||q).To achieve this, we notice that there is no requirement for dominating pairs to be distributions on the same space R D . Taking inspiration from hierarchical randomized smoothing [69] , we thus construct p and q that are mixtures of the p k and q k and additionally release their component indices: Lemma J.1. Consider arbitrary densitities p 1 , . . . , p K , q 1 , . . . , q K : R D → R + and arbitrary weights w 1 , . . . , w K ∈ [0, 1] with K k=1 w k = 1. Further let r : {1, . . . , K} → [0, 1] be the probability mass function of Categorical(w 1 , . . . , w K ). Define p, q : R D × {1, . . . , K} → R + asp(z, k) = p k (z) • r(k) and q(z, k) = q k (z) • r(k). Then, H α (p||q) = K k=1 w k • H α (p k ||q k ).Proof. By the definition of hockey stick divergence and p, q, we haveH α (p||q) = K k=1 R D max p(z, v) q(z, v) , 0 • q(z, v) dz = K k=1 R D max p k (z) • r(k) q k (z) • r(k) , 0 • q k (z) • r(k) dz = K k=1 r(k) • R D max p k (z) q k (z) , 0 • q k (z) dz = K k=1 w k • H α (p k ||q k ).Note that one could equivalently construct continuous distributions P and Q by defining the categorical distribution as a transformation of a uniform distribution. Further note that the distribution of privacy loss random variable log(p(Z) / q) 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.After applying the construction from the previous step, we have bounds of the formH α (m x ||m x ′ ) ≤ H α (p (x,x ′ ) α ||q (x,x ′ ) α). If these bounds are not constant in the datasets x, x ′ ∈ 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 x ≃ X 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 ≃ X is a set of tuples from X 2 . Lemma J.2. Consider any α ≥ 0, mechanism M and L different neighboring relations ≃ (1) , . . . , ≃ (L) ⊆ X 2 . Assume that there are L constants c (1) , . . . , c (L) such that H α (m x ||m x ′ ) ≤ c (l) for all l ∈ {1, . . . , L} and all x ≃ (l) x ′ . If the neighboring relations partition ≃ X , i.e.,≃ X = L l=1 ≃ (l) , then ∀x ≃ X x ′ : H α (m x ||m x ′ ) ≤ max l c (l) .Proof. Consider any x ≃ X x ′ . Because the neighboring relations partition ≃ X , there must be somel * such that x ≃ (l * ) x ′ and thus H α (m x ||m x ′ ) ≤ c (l * ) ≤ max l c (l) .For the purposes of privacy accounting, it is thus sufficient to determine some sufficiently fine-grained partition ≃ (1) , . . . , ≃ (L) such that for all l ∈ {1, . . . , L} and all α ≥ 0∀x ≃ (l) x ′ : H α (p (x,x ′ ) α ||q (x,x ′ ) α ) = H α (p (l) α ||q (l) α ),where pl α and q(l) α are families of densities indexed by partition index l 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. In practice, however, much more coarse-grained partitions may be sufficient. Zhu et al. [10] 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 + 1 different "insert-K + -remove-K -" relations with K + + K -= K.Consider some fixed partition index l ∈ {1, . . . , L}, which we omit in the following. We are now left with a bound of the form ∀x ≃ x ′ : H α (m x ||m x ′ ) ≤ H α (p α ||q α ). If the families of densitities pα , qα is constant in α, i.e.∀α :H α (p α ||q α ) = H α (p||q),with some p, q, then the corresponding distributions P , Q are dominating pairs. Importantly, the numeric value of the bound can vary with α. We just want the numeric value to be identical to the divergence H α of two specific distributions for all α.If this is not the case, there are two options to construct a dominating pair. The first option uses a characterization of dominating pairs as a function of privacy profiles. It was applied by Zhu et al. [10] 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.The following result from [10] establishes a 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. [10] ). For a given f : R + → R, there exists P , Q such that ∀α ≥ 0 :EQUATIONMoreoever, one can explicitly construct such P andQ: P has CDF 1 + f * (x -1) in [0, 1) and Q = Uniform([0, 1]), where f * is the convex conjugate of f .Next, we show how to construct a function f (α) ∈ F from our families of densities qα , qα indexed by α that allows us to determine dominating pairs. Lemma J.4. Consider two families of densities pα , qα indexed by α ≥ 0 such that ∀x ≃ x ′ :H α (m x ||m x ′ ) ≤ H α (p α ||q α ). Define the function f : R + → R with f (α) = max β≥0 H α (p β ||q β ).Then f is a valid privacy profile, i.e., f ∈ F with H defined in Eq. (24) .Proof. For every β ≥ 0, let f β (α) = H α (p β ||q β ) be the privacy profile associated with a specific pair from the considered families. All these functions are elements of F as per the first part of Proposition J.3. We thus know that each f β is convex, decreasing, and has value 1 at α = 0. Naturally, their maximum is also convex, decreasing, and has value 1 at α = 0. We further know that, for all β ≥ 0, f β (x) ≥ max{1 -x, 0}. Thus, we have f (x) ≥ f β (x) ≥ (1 -x) for any β ≥ 0.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 J.4 generalizes this principle to larger families.A novel solution is enabled by our proposed framework for deriving mechanism-specific subsampling guarantees: Recall that the densitities pα and qα are the result of identifying worst-case mixture components 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 H α (m x ||m x ′ for all α and pairs of datasets x ≃ 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.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/removal, can also be derived via our proposed optimal transport framework.As before, our contribution are not the guarantees themselves. Our contribution is identifying that, just like mechanism-agnostic 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.As discussed in Appendix J, it is beneficial to partition the insertion removal ≃ ±,X into two relations:The insertion relation ≃ +,X , where x ≃ +,X x ′ implies that there is some a / ∈ x such that x ′ = x ∪ {a} and the removal relation ≃ -,X , where x ≃ -,X implies that there is some a ∈ x such that x ′ = x \ {a}.While we could derive dominating pairs for both relations from scratch, we can use the following result from [10] 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 a dominating pair under the removal relation ≃ -.Next, we use our proposed framework to 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 [10] ). Proposition K.2 (Zhu et al. [10] ). Consider a subsampled mechanism M = B • S, where S is Poisson subsampling with subsampling rate r ∈ [0, 1]. assume that (P, Q) are a dominating pair for base mechanism B under the batch insertion relation ≃ +,Y . Then, (P, (1 -r)P + rQ) are a dominating pair for M under the dataset insertion relation ≃ +,X and ((1 -r)P + rQ, Q) are a dominating pair for M under the dataset removal relation ≃ -,X .Proof. We begin by deriving the dominating pair for the removal relation ≃ -,X . Consider an arbitrary pair x ≃ -x ′ and an arbitrary α ≥ 0. Recall from our proof of the mechanism-agnostic Poisson subsampling guarantee Proposition H.6 that we can construct a d Y -compatible coupling to show thatEQUATIONEQUATIONEQUATION2 ) ≤ ∞. The last constraint is because there is no sequence of deletions that will result in an insertion. It can be ignored, meaning our optimization problem is equivalent tomax y≃-y ′ H α ((1 -r)b y ′ + rb y ||b y ′ ).Using the definition of hockey stick divergence, 7 this can be restated asmax y≃-y ′ H α ((1 -r)b y ′ + rb y ||b y ′ ) = max y≃-y ′ R D max (1 -r)b y ′ (z) + rb y (z) b y ′ (z) -α, 0 • b y ′ (z) dz = max y≃-y ′ R D max (1 -r) + r b y (z) b y ′ (z) -α, 0 • b y ′ (z) dz = max y≃-y ′ r • R D max b y (z) b y ′ (z) -α - 1 -r r , 0 • b y ′ (z) dzWe can now distinguish two cases, based on the value of α' = α -(1 -r) / r.Case 1: Assume that α ′ < 0. Then, the integrand is always non-negative, and the objective function evaluates to a constant r(1 -a ′ ). We can thus choose y, y ′ arbitrarily, becausemax y≃+y ′ H α ((1 -r)b y ′ + rb y ||b y ′ ) = r(1 -a ′ ) = H α ((1 -r)q + rp||q),where p and q are the densities of dominating pair (P, Q).Case 2: Assume that α ′ ≥ 0. Because (P, Q) is a dominating pair for the batch insertion relation ≃ +,Y , we know from Lemma K.1 that (Q, P ) is a dominating pair for the batch removal relation ≃ -,Y . Thusmax y≃-y ′ H α ((1 -r)b y ′ + rb y ||b y ′ ) = max y≃-y ′ r • H α ′ (b y ||b y ′ ) ≤r • H α ′ (q||p) =H α ((1 -r)p + rq||q)This shows that ((1 -r)P + rQ, Q) is a dominating pair for the removal relation ≃ -,X . It then follows from Lemma K.1 that (Q, (1 -r)P + rQ) is a dominating pair for the insertion relation ≃ +,X .Note that case 1 (but not case 2) of Theorem 11 in [10] states that ((1 -r)Q + rP, P ) were a dominating pair for the removal relation. This does however appear to be a typographical error, since the authors use the same symmetry argument (Lemma K.1) for their proof.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 et al. [10] ). Assume a dataset space and batch space defined by X ⊆ {x ∈ P(A) | |x| ∈ {N, N -1}, Y = {y ⊆ x | x ∈ X, |y| = q}, and finite set A, with q < N . Consider a subsampled mechanism M = B • S, where S is subsampling without replacement with batch size q, and define batch-to-dataset ratio w = q / N . assume that (P, Q) are a dominating pair for base mechanism B under the batch substitution relation ≃ ∆,Y . Then, (P, (1 -w)P + wQ) are a dominating pair for M under the dataset insertion relation ≃ +,X and ((1 -w)P + wQ, Q) are a dominating pair for M under the dataset removal relation ≃ -,X .Proof. As in the previous proof, we begin with removal relation ≃ -,X . Consider an arbitrary pair x ≃ -x ′ and an arbitrary α ≥ 0. Recall from our novel proof of the mechanism-agnostic RDP guarantee for subsampling without replacement and insertion/removal (see Theorem I.2) that we can construct a d Y -compatible coupling to show thatEQUATION2 ) ≤ 1. By definition of the induced distance, this optimization problem is equivalent tomax y≃∆y ′ H α ((1 -r)b y ′ + rb y ||b y ′ ).We can now go through exactly the same steps as in our derivation of Proposition K.2, replacing every occurrence of "≃ -" with "≃ ′′ ∆ , to conclude our proof.In the case of subsampling without replacement and substitution (as well as Poisson subsampling and insertion/removal without partitioning of the neighboring relation) we do not need to provide a new proof. This is because Zhu et al. [10] prove this result by invoking a tight mechanism-agnostic subsampling guarantee derived by Balle et al. [15] and then applying advanced joint convexity in reverse order (see proof of Proposition 30 in [10] ).As we 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 a (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. [10] ). Consider a subsampled mechanism M = B • S, where S is subsampling without replacement with batch size q ∈ N. Assume that (P, Q) are a dominating pair for base mechanism B under the batch substitution relation ≃ ∆,Y . Consider arbitrary x ≃ ∆,X x ′ of size N and define batch-to-dataset ratio w = q / N . ThenH α (m x ||m x ′ ) ≤ H α ((1 -w)q + wp||q) for α ≥ 1 H α (p, (1 -w)p + wq||q) for 0 < α < 1Note that this result does not immediately specify a dominating pair. However, as shown in [10] , one can construct a dominating pair via convex conjugation (recall Appendix J.3.1 and Proposition J.3).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 [8] . However, the authors did not provide a formal proof for why they should lead to valid privacy guarantees. They only proved that if two pairs of multivariate Gaussians with colinear means were to be a dominating pair 8 , then one could use a change of variable and marginalization to reduce them to a univariate dominating pair (see Appendix B.1 in [8] ). They did not prove why this assumption should hold. A formal proof of this assumption is now enabled by the analysis we conducted for solving the group privacy optimization problem in Theorem M.6 (see Appendix O).Novel contribution 2 -Other base mechanisms. The generality of our solution to the group privacy optimization problem in Theorem M.6 lets 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 importantly, our proposed framework offers a novel perspective on an issue encountered when analyzing subsampling without replacement: While one can derive a tight mechanism-specific guarantee, this guarantee depends on different mixture distributions for α < 1 and α ≥ 1 (see Proposition K.4 [10] and our more general discussion in Appendix J.3). Thus, one cannot simply read off a dominating pair from this mechanism-specific 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 easier to use in practice than the convex conjugation construction from [10] .We begin with subsampling without replacement to demonstrate the potential benefit of relaxing batch distance constraints to determine tractable dominating pairs. Theorem L.1. Let M = B • S, where S is subsampling without replacement with batch size q, and B is the Gaussian mechanism h + V with h : Y → R D and V ∼ N (0, σ 2 I D ). Define the ℓ 2 -sensitivity L 2 = max y≃ ∆,Y y ′ ||f (y) -f (y ′ )|| 2 , where ≃ ∆ is the substitution relation. Consider an arbitrary dataset size N ∈ N and define batch-to-dataset ratio w = q N . Then, for any pairEQUATIONwith univariate normal densities fEQUATIONj = N (• | -(j -1), σ / L 2 ).Proof. Recall from our proof of the mechanism-agnostic subsampling without replacement guarantee Proposition H.4 that we can construct a d Y -compatible coupling to show thatH α (m x ||m x ′ ) ≤ max y H α ((1 -w)b y (1) 1 + wb y (1) 2 ||(1 -w)b y (2) 1 + wb y (2)2)subject to y ∈ Y 2+1 , yEQUATION1 , y2EQUATION1 , y2EQUATION1 , y1 ) ≤ 1. Next, we relax the constraint between the two components that contain a substituted element:d Y (y (2) 1 , y (2) 1 ) ≤ 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-specific group privacy amplification bound for Gaussian mechanism (Theorem 3.8).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 in Eq. ( 25) depends on the same pair of mixture distributions for all α ≥ 0. Thus, this pair of mixture distributions is a dominating pair for subsampling without replacement under substitution.Next, we provide the first formal derivation of dominating pairs for subsampling with replacement.In subsampling with replacement, a single element may appear in a batch multiple times. To formalize this, we assume a dataset space X ⊆ P(A) that is composed of sets (not multisets) of elements from an underlying set A. We further assume a batch space Y ⊆ P multi (A) that is composed of multisets of elements from A. Given some y ∈ Y, we write ξ y (a) for the number of times that a appears in y. We further define the support of batch y ∈ Y as supp(y) = {a ∈ Y | ξ y (a) ≥ 0}. Definition L.2. Subsampling with replacement with batch size q has probability mass functions x (y) = |x|+q-1 q -1for batches y ∈ Y with supp(y) ⊆ 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 = B • S, where S is subsampling without replacement with batch size q, and B is the Gaussian mechanism h + V with h : Y → R D and V ∼ N (0, σ 2 I D ). Define the ℓ 2 -sensitivityL 2 = max y≃ ∆,Y y ′ ||f (y) -f (y ′ )|| 2, where ≃ ∆ is the substitution relation. Consider an arbitrary dataset size N ∈ N and define batch-to-dataset ratio w = q N . Then, for any pair x ≃ ∆,X x ′ of size N ,EQUATIONu ) ≤ max{t, u}, and with weightsw i = 1 N i • 1 -1 N q-i .Proof. By definition of the substitution relation ≃ ∆ there is some a ∈ x with a / ∈ x ′ and some a ′ ∈ x ′ with a ′ / ∈ x such that x ′ = x \ {a} ∪ {a ′ }.To simplify indexing, we define zero-based indexed events A 0 , . . . , A q and E 0 , . . . , E q . We define A i to be the event that a is sampled i times, i.e., ξ y (a) = i. We define E j to be the event that a ′ is sampled j times, i.e., ξ y (a ′ ) = j.By definition subsampling with replacement, we have P Sx (A i ) = w i , and P Sx (E j ) = w j with weightsw i = 1 N i • 1 -1 N q-i .For dataset size N , we haves x (y | A i ) = (N -1)+(q-i)-1 q-i -1 if supp(y) ⊆ x ∧ ξ y (a) = i 0 otherwise = ( 1 N -1 ) q-i (q -i)! ã̸ =a 1 ξy(ã)! if supp(y) ⊆ x ∧ ξ y (a) = i 0 otherwise and s x ′ (y | E j ) = (N -1)+(q-i)-1 q-i -1 if supp(y) ⊆ x ′ ∧ ξ y (a ′ ) = j 0 otherwise = ( 1 N -1 ) q-i (q -i)! ã̸ =a ′ 1 ξy(ã)! if supp(y) ⊆ x ′ ∧ ξ y (a ′ ) = j 0 otherwise Note that s x (y | A 0 ) = s x ′ (y | E 0 ). Further note that s x (y | A q ) = 1[supp(y) = {a} ∧ |y| = q] and s x ′ (y | E q ) = 1[supp(y) = {a ′ } ∧ |y| = q].Theorem L.5. Let M = B • S, where S is subsampling with replacement with batch size q, and B is the Gaussian mechanism h + V with h : Y → R D and V ∼ N (0, σ 2 I D ). Define the ℓ 2 -sensitivityL 2 = max y≃ ∆,Y y ′ ||f (y) -f (y ′ )|| 2, where ≃ ∆ is the substitution relation. Consider an arbitrary dataset size N ∈ N. Then, for any pair x ≃ ∆,X x ′ of size N ,EQUATIONwith univariate normal densities fEQUATION= N (• | -(j -1), σ / L 2 ), andweights w i = 1 N q • 1 -1 N q-i .Proof. We first relax the optimization problem in Theorem L.3 by replacing the last constraint ∀t, u :EQUATIONt , yu ) ≤ max{t, u} with a new constraint ∀t, u :EQUATIONt , yu ) ≤ t + u. This leaves us withEQUATIONu ) ≤ t + u, and with weightsw i = 1 N i • 1 -1 N q-i .We now observe that this optimization problem is identical to the optimization problem from our group privacy bound (Theorem 3.7) with q insertions (K + = q), q deletions (K -= q), and a different set of weights. The result thus follows immediately from our solution to the group privacy amplification problem from Theorem 3.7, which did not make any specific assumptions about the weights.We see that the upper bound in Eq. ( 25) depends on the same pair of mixture distributions for all α ≥ 0. Thus, this pair of mixture distributions is a dominating pair for subsampling without replacement under substitution.max y≃ ±,Y y ′ ||f (y) -f (y ′ )|| 2 . Then for all x ≃ K+,K-,X x ′ , Ψ α (m x ||m x ′ ) is l.e.q. Ψ α   K-+1 i=1 f (1) i • Binom(i -1 | K -, r)|| K++1 j=1 f (2) j • Binom(j -1 | K + , r)   , with univariate normal densities f (1) i = N (• | (i -1), σ / L 2 ), f (2) j = N (• | -(j -1), σ / L 2 ).Proof sketch. Recall from Theorem 3.7 that we need to solve the optimization problemEQUATIONu ) ≤ (t -1) + (u -1), and with wEQUATIONj = Binom(j -1 | K + , r). Let µ (1) i = h(y (1) i ) and µ (2) j = h(y (2)j ). Since we do not have any additional information about h beyond its ℓ 2 -sensitivity, we have to make the worst-case assumption that the µ (l) t -µ (l) u || 2 ≤ L 2 |t -u|, ∀t, u : ||µ (1) t -µ (2) u || 2 ≤ L 2 ((t -1) + (u -1)),Thus, the optimization problem is equivalent to max µ (1) ,µ (2) EQUATIONu || 2 ≤ (t -1) + (u -1). In Appendix O, we 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 µ L 1 = max y≃ ±,Y y ′ ||f (y) -f (y ′ )|| 1 . Then, for all x ≃ K+,K-,X x ′ , Ψ α (m x ||m x ′ ) is l.e.q. Ψ α   K-+1 i=1 f (1) i • Binom(i -1 | K -, r)|| K++1 j=1 f (2) j • Binom(j -1 | K + , r)   , with univariate Laplace densities f (1) i = Lap(• | (i -1), λ / L 1 ), f (2) j = Lap(• | -(j -1), λ / L 1 ).Proof sketch. Recall from Theorem 3.7 that we need to solve the optimization problemEQUATIONu ) ≤ (t -1) + (u -1), and with wEQUATIONj = Binom(j -1 | K + , r).Theorem M.4. Let S be Poisson subsampling with rate r ∈ [0, 1] and θ ∈ [0, 1] be some true response probability. There exists a dataset space X and a batch space (Y, Y) fulfilling the constraints in Definition D.4, as well a pair of datasets x ≃ K+,K-,X x ′ , and a function h : Y → R D with ℓ 2 -sensitivity L 2 , such that the corresponding subsampled Gaussian mechanism M = B • S fulfillsΨ α (m x ||m x ′ ) = Ψ α   K-+1 i=1 f (1) i • Binom(i -1 | K -, r)|| K++1 j=1 f (2) j • Binom(j -1 | K + , r)   , with univariate normal densities f (1) i = N (• | (i -1), σ / L 2 ), f (2) j = N (• | -(j -1), σ / L 2 ).Proof. Let X = P(N). Consider an arbitrary x ∈ X and select arbitrary deleted elements g ⊆ x, with |g| = K -and arbitrary inserted elements g ⊆ X \ x. Define x ′ = x \ g -∪ g + .We now construct a counting function for h that leads to the largest possible divergence under the sensitivity constraint. We define function h as follows:h(y) = (i -1) • e 1 L 2 if |g -∩ y| = i -1 -(j -1) • e 1 L 2 if |g + ∩ y| = j -1 with first-component indicator vector e 1 ∈ R D .By construction, P Mx is a mixture distributions with K + 1 components, each corresponding to a size of a subset of g -that is included in batch y. These cases each have probabilityBinom(i -1 | K -, r) under subsampling distributions P Sx . Each component has distribution N (• | (i -1), e 1 L 2 , σ 2 I D ).Analogously, P m x ′ is the other desired mixture of Gaussians.As in our previous proof, we can now notice that the likelihood ratio in Ψ α is constant in all but the first dimension. We can thus marginalize out the remaining dimensions to obtain our result.Theorem M.5. Let S be Poisson subsampling with rate r ∈ [0, 1] and θ ∈ [0, 1] be some true response probability. There exists a dataset space X and a batch space (Y, Y) fulfilling the constraints in Definition D.4, as well a pair of datasets x ≃ K+,K-,X x ′ , and a function h : Y → R D with ℓ 1 -sensitivity L 1 , such that the corresponding subsampled Laplace mechanism M = B • S fulfillsΨ α (m x ||m x ′ ) = Ψ α   K-+1 i=1 f (1) i • Binom(i -1 | K -, r)|| K++1 j=1 f (2) j • Binom(j -1 | K + , r)   , with univariate Laplace densities f (1) i = Lap(• | (i -1), λ / L 1 ), f (2) j = Lap(• | -(j -1), λ / L 1 ).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 x and S x ′ , respectively.As in our previous proof, we can now notice that the likelihood ratio in Ψ α is constant in all but the first dimension. We can thus marginalize out the remaining dimensions to obtain our result.Theorem M.6. Let S be Poisson subsampling with rate r ∈ [0, 1] and θ ∈ [0, 1] be some true response probability. There exists a dataset space X and a batch space (Y, Y) fulfilling the constraints in Definition D.4, as well a pair of datasets x ≃ K+,K-,X x ′ , and a function h : Y → 0, 1, such that the corresponding subsampled randomized response mechanism M = B • S fulfillsΨ α (m x ||m ′ x ) = max τ Ψ α ((1 -w (1) )Bern(• | θ) + w (1) Bern(• | τ )||(1 -w (2) )Bern(• | θ) + w (2) Bern(• | 1 -τ ))subject to τ ∈ {θ, 1 -θ}, and with w(1) = 1 -(1 -r) K-and w (2) = 1 -(1 -r) K+ .Using quadratic expansion, we haveK k=0 N (z | µ k , σ 2 I) l k /α =N z | k l k α µ k , σ 2 I • exp - 1 2σ 2 k l k α ||µ k || 2 2 • exp 1 2σ 2 k ||( l k α µ k )|| 2 2Since only the first factor depends on z, our problem reduces to computing the divergenceΨ α N z | k l k α µ k , σ 2 I ||N z | 0, σ 2 Ifor different l k . This can be done in closed form, as shown in [7] .M.4.2 Laplace mechanism ADP. Because the privacy loss is constant on (-∞, -K + ), monotonically increasing on [-K + , K -] and constant on (K -, ∞), we can again use 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, 1, . . . , K -}, we partition R at these means and integrate over each interval separately.The guarantee for randomized smoothing can be evaluated exactly in O(1). We just need to iterate over the two options τ ∈ {0, 1}, and for each one evaluate the divergence on space {0, 1}, which only requires evaluating two fractions and two sums.In this section, we apply the framework from [15] , which we summarized in Appendix G.1, to the group privacy setting. We then show the tightness of the resultant guarantees, using the same proof strategy as in Section 5 of [15] . We then demonstrate that it is directly related to our tight mechanism-specific guarantee through joint convexity. Finally, we derive a qualitatively similar guarantee for RDP.For this discussion, we focus on the special case where all of the K group members collaboratively agree to insert their data (K + = K, K -= 0) or delete their data (K + = 0, K -= K), so that the partition induced by the maximal coupling remains interpretable. We define the corresponding neighboring relation asEQUATIONIn our experiments, we only evaluate the baseline for (K + = K, K -= 0) and (K + = 0, K -= K), while we evaluate our method for all K + + K -= K and take the maximum. This evaluation favors the baseline.N. EQUATION)) and group privacy parametersδ k = max y,y ′ H exp(ε) (b y ||b y ′ ) s.t. d Y (y, y ′ ) ≤ k.Proof. Case 1: Deletion. We first consider the case where K elements are deleted, i.e., there is some deleted set g ⊆ x of size K with g -∩ x ′ = ∅ such that x ′ = x \ g.The partition induced by the maximal coupling 9 iss x (y) = (1 -w)s x (y | A 2 ) + ws x (y | A 1 ) s x ′ (y) = (1 -w)s x (y | A 2 ) + ws x (y | A 2 ),where A 2 = {y ∈ Y | y ∩ g = ∅ is the event that no element of g is sampled, A 1 is its complement, and w = (1 -(1 -r) K ) = P Sx (A 1 ). We use these indices for A 2 and A 1 because advanced joint convexity will later reverse their order.Applying advanced joint convexity (see Proposition G.1) and joint convexity shows thatEQUATIONNext, we can bound this mixture divergence by constructing a coupling invoking Theorem 3.3 with the special case of Ψ α = H exp(ε) . For this, notice thats x (y | A 1 ) = 1 w • r |y| • (1 -r) |x|-|y| if y ∈ A 1 ∧ y ⊆ x 0 otherwise. and s x (y | A 2 ) = s x ′ (y) = r |y| • (1 -r) |x ′ |-|y| if y ∈ A 2 ∧ y ⊆ x ′ 0 otherwise.Coupling. We define a coupling γ : Y 2 → [0, 1] that corresponds to the following generative process:We first sample y (2) from s x (y | A 2 ). We then sample from a truncated binomial distribution how many elements k from group g should be included. Given this k, we sample uniformly at random a g ⊆ g from all size-k subsets of g and let y (1) ← y (2) ∪ g. Formally this is defined by γ(y (1) , yEQUATIONCondition N.2. A tuple y (1) ∈ Y, y (2) ∈ Y fulfills this condition when there exists a g ⊆ g with |g| ≥ 1 such that y (1) = y (2) ∪ g.Validity. Next, we verify the validity of this coupling. For every y (1) , there is exactly one y (2) such that γ(y (1) , y (2) ) > 0, namely y (2) = y (1) \ g ′ . Thus, yγ(y, y (2) ) =s x (y\ g | A 2 ) • 1 w • Binom(|y ∩ g| | K, r) • K y ∩ g| -1 =r |y\g| • (1 -r) |x ′ |-|y\g| • 1 w • r |y∩g| • (1 -r) K-|y∩g| =s x (y | A 1 ).For every y (2) , there are exactly K k batches y (1) such that γ(y (1) , y (2) ) > 0 and |y (1) ∩ g = k|. Thus, y (1) γ(y (1) , y)= K k=1 K k s x (y | A 2 ) • 1 w • Binom(k | K, r) • K k -1 =s x (y | A 2 ) • 1 w • K k=1 Binom(k | K, r) =s x (y | A 2 ).Now that we have proven the validity of the coupling, we can apply the optimal transport bound (Theorem 3.3) to Eq. ( 28) in order to prove 1) ,y (2) γ(y (1) , y (2) )δ d Y (y (1) ,yEQUATIONEQUATIONCase 2: Insertion. In this case, the partition induced by the maximal coupling iss x (y) = (1 -w)s x (y | A 1 ) + ws x (y | A 2 ) s x ′ (y) = (1 -w)s x (y | A 1 ) + ws x (y | A 1 ),which is identical to the previous partition, up to symmetry. The proof is identical, except for changes in indexing.Taking the maximum over both guarantees yields the result.Proposition N.3. Let S be Poisson subsampling with rate r. Let ≃ Y be the insertion/removal batch relation ≃ ±,Y . Then, for all x ≃ K±,X x ′ and all ε ≥ 0, there exists a worst-case base mechanism B such that the corresponding subsampled mechanism M = B • S fulfillsEQUATION)) and group privacy parametersδ k = max y,y ′ H exp(ε) (b y ||b y ′ ) s.t. d Y (y, y ′ ) ≤ k.Proof. To show tightness of the bound, we notice that the boundK k=1 Binom(k | K, r)• δ k is identical to the bound for subsampling with replacement from [15] , 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 we are in the insertion case, i.e., there is some g of size K with g ∩ x = ∅ and x ′ = x ∪ g. Consider an arbitrary ε and define an arbitrary true response probability θ ∈ [0, 1]. Further define the randomized membership base mechanismB(y) = |1[|y ∩ g| > 0] -(1 -V )| with V ∼ Bern(θ).It is easy to verify [15] that δ k = ψ θ (ε) = max{θ -e ε (1 -p), 0}. We thus have for the r.h.s. of Eq. ( 29)K k=1 Binom(k | K, r) • δ k = K k=1 Binom(k | K, r) • ψ θ (ε) := w • ψ θ (ε).Because Poisson subsampling is a "natural subsampling" [15] scheme that only yields elements from the dataset it is applied to, it follows from Lemma 12 of [15] that alsoH exp(ε ′ ) (m x ||m x ′ ) = w • ψ θ (ε).In the following, we show that this mechanism-agnostic guarantee implicitly upper bounds our tight mechanism-specific 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-specific bounds that only use a 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 : Y → Z be an arbtirary base mechanism. Let y (1) ∈ Y 1 and , y (2) ∈ Y K+1 be arbitrary tuples of batches that fulfill ∀l, t, u : d Y (y(l) t , y (l) u ) ≤ |t -u|, and ∀t, u : d Y (y (1) t , y (2) u ) ≤ (t -1) + (u -1). Then, for α ≥ 1 H α ′   b y (1) 1 || K+1 j=1 b y (2) j • Binom(j -1 | K, r)   ≤ K k=1 Binom(k | K, r) • δ k (α) with w = (1 -(1 -r) K ), α ′ = 1 + w(α -1) and group privacy parameters δ k (α) = max y,y ′ H α (b y ||b y ′ ) s.t. d Y (y, y ′ ) ≤ k.Proof. We can apply joint convexity to showEQUATIONEQUATIONThe result then immediately follows from advanced joint convexity (see Proposition G.1) and joint convexity.For RDP, we can obtain a qualitatively similar guarantee by simply applying the known mechanismagnostic RDP subsampling guarantee for Poisson subsampling from [29, 30] to each of the K divergences (although we could also derive this RDP guarantee from scratch via optimal transport) in Eq. ( 33) of the previous derivation. Λ α (m x ||m x ′ ) ≤ K k=1 1 w • Binom(k | K, r) • 2 • α l=0 α l w l (1 -w) α-l ζ k (l)with w = (1 -(1 -r) K ) and group privacy parametersζ k (l) = max y,y ′ Λ l (b y ||b y ′ ) s.t. d Y (y, y ′ ) ≤ k.The factor 2 in Theorem N.5 can be eliminated for distributions with particular symmetries (see Theorem 5 in [29] ) or bounded Pearson-Vajda χ l -pseudo-divergence (see Theorem 8 in [30] ). We thus do not include the factor 2 when using this amplification guarantee as a baseline in our experiments.As mentioned in Section 3.1, our focus is on tight bounds that can be explicitly computed. However, analyzing the asymptotic behavior of these bounds can provide a potentially useful high-level picture of their behavior. As discussed in the previous section, and as can be seen from Eq. ( 33), Rényi 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] ) toEQUATIONAsymptotic bounds on Rényi divergences with one or 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 [6] ): Proposition N.6. Abadi et al. [6] Let σ ≥ 1 and q ≤ 1 16σ . Then, for any positive integer α ≤ σ 2 ln 1 qσ -1, Λ α (N (0, σ)||(1 -q)N (0, σ) + q • N (1, σ)) ≤ q 2 α(α -1) (1 -q)σ 2 + O(q 3 α 3 / σ 3α ≤ σ 2 k 2 •L 2 ln 1 wσ -1 that Λ α (m x ||m x ′ ) ≤ K k=1 1 w • Binom(k | K, r) • 2 • k 2 L 2 q 2 α(α -1) (1 -w)σ 2 + O(k 3 L 3 w 3 α 3 / σ 3 ).Alternatively, one could apply the asymptotic bound from Theorem 38 from [48] to each summand. If we were to instead consider group privacy under dataset-level substitutions, where each summand would include a divergence between two mixtures with two components, we could instead use the asymptotic bounds from Appendix C of [28] .and the image set C (l) := ( M (l) × N )([0, 1]). The divergence difference has the formΨ α (M (l) ||N ) -Ψ α (M ||N ) = C (l) K k=0 d (µ k ) n+ Ψ α ( M (l) ||N ) ds = t=1 t=0 K k=l d (µ k ) n+ Ψ α ( M (l) (t)||N ) √ 2(σ T êi )(ê T i δµ l )dt ≥ 0 :By construction, the directional derivatives d(µ k ) n+ Ψ α ( M (k) (t)||N ) are nonnegative. Likewise, the determinant term √ 2(σ T êi )(ê T i δµ l) is nonnegative by the simplex condition together with feasibility of (M, N ).If the separability condition is fulfilled for ninstead, we can repeat the argument with indices i ↔ j swapped and index m instead of l.An analogous argument holds if ∃ι ∈ {1, . . . , K}, π ∈ {1, . . . , K}, i ∈ {1, . . . D}, j ∈ {1, . . . , D}, i ̸ = j : (δν T ι êi ) ̸ = 0 ∧ (δν T π êj )} ̸ = 0.Theorem O.10 immediately follows from Lemma O.13 by induction.In the previous subsections, we showed that Ψ α (N ||M ) is maximized by collinear and equidistant sets of means. This allows to evaluate Ψ α (N ||M ) through a one-dimensional integral via marginalization. Recall (Theorem O.9). Note furthermore that in both cases, constraining the first element of either N or M into the origin incurs no generality loss due to the translation invariance of Ψ α .Being able to constrain the problem to a single dimension, we now show Lemma O.14. In the collinear case, we may evaluate Ψ α as the one-dimensional divergence Ψ 1D α between two mixturesK k=0 w k N (r k , σ 2 ), K κ=0 ω κ N (-ρ κ , σ 2 ) of univariate Gaussians centered around the means r k and -ρ κ , Ψ α K κ=0 ω κ N (-ρ κ ê, σ 2 I)|| K k=0 w k N (r k ê, σ 2 I) = Ψ 1D α K κ=0 ω κ N (-ρ κ , σ 2 )|| K k=0 w k N (r k , σ 2 ) .Proof. Without loss of generality, we may assume ê to be the indicator vector of the first component due to rotation invariance of Ψ α . Using bracketed superscripts (0) to indicate the first vector component, and (1 :) to indicate the rest, we can use Fubini's theorem to writeΨ α K κ=0 ω κ N (-ρ κ ê, σ 2 I)|| K k=0 w k N (r k ê, σ 2 I) = R D K κ=0 ω k N (x | -ρ κ ê, σ 2 I) α K k=0 w k N (x | r k ê, σ 2 I) (1-α) dx (0) dx (1:) = R D-1 N (x (1:) | 0, σ 2 I) dx (1:) R K κ=0 ω k N (x (0) | -ρ κ , σ 2 ) α K k=0 w k N (x (0) | r k , σ 2 ) (1-α) dx (0) = 1 • Ψ 1D α K κ=0 ω κ N (-ρ κ , σ 2 )|| K k=0 w k N (r k , σ 2 ) .The proof is analogous for the Laplacian mechanism.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 O.15.EQUATIONi (1 -|z -τ where f strictly convex, increasing, and g strictly convex, decreasing.Trivial case: θ = 1 2 , thus assume θ ̸ = 1 2 for the rest of the proof. Further define w(1)EQUATION1-τ , wEQUATION1-τ . Define a new mixture via τEQUATION2...,K++1 = 1 -τ, τEQUATIONi , ∀i. Assume w.l.o.g. that τ 0 = max{θ, 1 -θ}, else swap roles of 0 ↔ 1 in the argument. 1 (1 -|z -τ |), i.e., "part that stays fixed"; see Fig. 26 , δx(z) = (w (1) τ -w1 )(1 -|z -τ |), i.e., "part that relocates"; see Fig. 26 . Similarly,x ′ (z) = x ′ 0 (z) + δx ′ (z), and by construction,x ′ 0 (z) = x 0 (z), δx ′ (z) = δx(1 -z) (⋆) We can assume w.l.o.g. τ 0 = max{θ, 1 -θ} =⇒ δx(1) > δx(0) (⋆⋆) (else, swap 1 ↔ 0) Then, θ ̸ = 1 2 , hence we can assume wτ > w = [f (x 0 (0) + δx(1)) -f (x 0 (0) + δx(0))] g(y(0))) -[f (x 0 (1) + δx(1)) -f (x 0 (1) + δx(0))] g(y(1)) Then, using that f is strictly convex, we have (⋆⋆) > f ′ (x 0 (0) + δx(0))g(y(0))(δx(1) -δx(0)) -f ′ (x 0 (1) + δx(0))g(y(1))(δx(1) -δx(0)) Where f ′ (x) = x α-1 , and thus f ′ (x)g(y) = (α -1) x y α-1 = (α -1)x 0 (0) + δx(0) y(0) The last inequality follows from the following facts. Since we assume w(1)EQUATION1 (else, m ≡ m ′ in the first place), we can bound the second term by: w (1)1 τ + (1 -w (1) 1 )(1 -τ ) (1 -w (2) 1-τ )τ + w (2) 1-τ (1 -τ ) α-1(1 -w(1)1-τ )τ + w 1-τ (1 -τ ) (1 -w (2) 1-τ )τ + w (1) 1-τ (1 -τ ) ≤ 1 α-1 (i)Moreover, we have that the first term is bounded by(1 -w (1) 1-τ )(1 -τ ) + w (1) 1-τ τ (1 -w (2) 1-τ )(1 -τ ) + w (2) 1-τ τ α-1 ≥ 1(ii) (strict > if w (1) 1-τ > w (2)1-τ ). The conclusion follows from (i), (ii), and since WLOG τ > (1 -τ ).We have shown so far:Ψ α (m τ ′(1) , m τ ′(2) ) > Ψ α (m τ (1) , m τ (2) ).To complete the proof of (a), we show now that Ψ α (m τ (1) , m τ (2) ) > Ψ α (m τ ′(1) , m τ ′(2) ).Idea: Apply symmetric argument to means τ (2) .Since 1 = wτ + w(1)1-τ = w(2)EQUATION1-τ , we have wτ ′ = w (2) τ ≥ w (1) τ > wτ ′ , where wτ ′ , wτ ′ are defined like wτ , wτ but for new means τ ′ . Decompose y ′ : y ′ (z) = y ′ 0 (z) + δy ′ (z), where y ′ 0 (z) = w (2) τ (1 -|z -τ |), i.e., "part that stays fixed"; see Fig. 27 ., δy ′ (z) = w Trivial case: θ = 1 2 , thus assume θ ̸ = 1 2 for the rest of the proof.Next, we use Theorem 3.4, i.e., 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 to 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 to be the first to consider the permute-and-partition scheme for composed mechanisms (see, e.g., [38] ). It is just a nice showcase for the versatility of our framework in analyzing different subsampling schemes.For the following result and proof we will use the following indexing convention: yi,k is a batch associated with the first mixture mx , event A i , and the kth iteration. Similarly, y(2) j,k is a batch associated with the second mixture mx ′ , event E j , and the kth iteration. Theorem P.3. Assume a dataset space X ⊆ {x ∈ P(A) | |x| = 2N }, and corresponding batch space Y = {y ⊆ x | x ∈ X ∧ |y| = N }, equipped with single-element substitution relation ≃ ∆,Y . Let S : X → Ŷ be the permute-and-partition subsampling scheme defined in Definition P.1, and let B : Y → Z be some base mechanism. Let B be the composed base mechanism with B(y1,y2) = (B y1 , B y2 ), and M = B • S be the subsampled, coposed mechanism. Then, for all x ≃ ∆,X x ′ ,Ψ α ( mx || mx ′ ) ≤ max y (1)1,1 ,y1,2 ,y Proof. By definition of the substitution relation, there must be some a ∈ x and some a ′ ∈ x ′ such that x ′ = x \ {a} ∪ {a ′ }.For the original subsampling scheme S x we let A 1 be the event that a appears in the first batch and A 2 be the event that a appears in the second batch. For the modified subsampling scheme S x ′ we let E 1 be the event that a ′ appears in the first batch and E 2 be the event that a ′ appears in the second batch. We have P Sx (A 1 ) = P Sx (A 2 ) = P S ′x (E 1 ) = P S ′ x (E 2 ) = 1 2 .• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 96% CI, if the hypothesis of Normality of errors is 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 are out of range (e.g. negative error 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.Justification: The research in this paper conforms, in every respect, with the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).In combination with "advanced joint convexity"[15].assuming that (y, Z) → PB y (Z) is a valid Markov kernelWe shall now prove that d Y -compatibility is a sufficient optimality condition for our optimal transport problem. For this proof, we will use the following lemma, which immediately follows from Definitions F.2 and F.3:Note that they do not actually consider insertion/removal, because their analysis assumes the number of subgraphs to remain constant.assuming that the batch space is finite and discretethe arguments in this section also apply to the general problem setting from Appendix D, where we allow arbitrary output spacesFor simplicity, we assume that we have continuous-valued 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)PB y ′ + rPB y ) / dPB y ′ .Technically, the notion of dominating pairs[10] had not been introduced at this point, which is why the authors discuss a vaguer notion of "worst-case distributions", similar to other early work on numerical accounting.as can be seen by the fact that w is the total variation distance of sx and s x ′ , and that sx(y | A2) and sx(y | A1) have disjoint support 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- 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)
- 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.
- Could the authors add group size = 1 in the experiment for completeness?
questions: questions: See above.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Small editorial suggestions:
- It is difficult to follow the quantifier constraints in some places e.g. p.5 l.193
- p.4 l.178 Missing $y^{(1)}$ and $y^{(2)}$ under sum
- p.36 l.852 should this be $x'$ not $x$?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: - Is there any intuition about the types of scenarios where this new framework gives improvements over existing mechanism-agnostic bounds?
limitations: limitations: - See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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?

 - 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? 

- 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.

- 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$. 

- 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.

### Minor Concerns:

- The privacy amplification results are not presented in a closed-form solution, making them difficult to operationalize.

- The subsampling bounds for Rényi DP have not been compared with other existing works, such as [1,2].

- The placement of figures does not match the respective appendices where they are discussed, making referencing the figures very challenging.

References:

[1] Steinke, Thomas. "Composition of differential privacy & privacy amplification by subsampling." arXiv preprint arXiv:2210.00597 (2022).

[2] Zhu, Yuqing, and Yu-Xiang Wang. "Poisson subsampled Rényi differential privacy." International Conference on Machine Learning. PMLR, 2019.
questions: 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: limitations: Authors discuss some of the limitations of the paper. Following are some additional limitations that need addressing.

- The ansatz is unwieldy for finding general use.
- Closed-form asymptotics for the presented bounds are missing.
- It's not clear if mechanism-specific subsampling bounds can be strictly better than mechanism-agnostic subsampling bounds for group size=1.
paper_summary: paper_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.
strength_weakness: strength_weakness: This manuscript is too long, which are 100 pages.  
Lack of theoretical analysis in the main text
questions: questions: Will the approach be adopted to LDP?
limitations: limitations: NA

Comments: title: Response
comment: Thank you for the clarifications! The expanded exposition for Thm 3.4 is much clearer to me. I have no further questions.
Thanks for the clarifications, I have no further questions.
Thank you for your response. I have no further questions.
Thank you for the detailed answers; it resolves many of my concerns. I've adjusted my score accordingly.