Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement
Authors: Jeremiah Birrell
Mohammadreza Ebrahimi
Rouzbeh Behnia
Jason Pacheco
Venue: NeurIPS 2024 poster (2024)
Keywords: privacy preserving machine learning
differential privacy
differentially private stochastic gradient descent
fixed-size subsampled mechanisms
privacy amplification lemma
Primary area: privacy
TL;DR: We provide a new privacy accountant and comprehensive analysis for differentially private stochastic gradient descent with tighter privacy guarantees under fixed-size resampling with or without replacement.

Abstract: Differentially private stochastic gradient descent (DP-SGD) has been instrumental in privately training deep learning models by providing a framework to control and track the privacy loss incurred during training.  At the core of this computation lies a subsampling method that uses a privacy amplification lemma to enhance the privacy guarantees provided by the additive noise. Fixed size subsampling is appealing for its constant memory usage, unlike the variable sized minibatches in Poisson subsampling. It is also of interest in addressing class imbalance and federated learning. Current computable guarantees for fixed-size subsampling are not tight and do not consider both add/remove and replace-one adjacency relationships. We present a new and holistic Rényi differential privacy (RDP)  accountant for DP-SGD with fixed-size subsampling without replacement (FSwoR) and with replacement (FSwR). For FSwoR we consider both add/remove and replace-one adjacency, where we improve on the best current computable bound by a factor of $4$. We also show for the first time that the widely-used Poisson subsampling and FSwoR with replace-one adjacency have the same privacy to leading order in the sampling probability. Our work suggests that FSwoR is often preferable to Poisson subsampling due to constant memory usage. Our FSwR accountant includes explicit non-asymptotic upper and lower bounds and, to the  authors' knowledge, is the first such RDP analysis of fixed-size  subsampling with replacement  for DP-SGD. We analytically and empirically compare fixed size and Poisson subsampling, and show that DP-SGD gradients in a fixed-size subsampling regime exhibit lower variance in practice in addition to memory usage benefits.

Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement
Jeremiah Birrell Texas State University jbirrell@xstate..cmm edu
Reza Ebrahimi University South Florida ebrahimim@usf. edu
Rouzbeh Behnia University of South Florida behniaQusf edu
Jason Pacheco University of Arizona pachecoj@cs, arizona. edu
Abstract
Differentially private stochastic gradient descent (DP-SGD) has been instrumental in privately training deep learning models by providing a framework to control and track the privacy loss incurred during training. At the core of this computation lies subsampling method that uses a privacy amplification lemma to enhance the privacy guarantees provided by the additive noise. Fixed size subsampling appealing for its constant memory usage, unlike the variable sized minibatches also of interest in addressing class imbalance and
in Poisson subsampling. federated learning. Current computable guarantees for fixed-size subsampling are not tight and do not consider both add/remove and replace-one adjacency relationships. We present new and holistic Rényi differential privacy (RDP) accountant for DP-SGD with fixed-size subsampling without replacement (FSwoR) and with replacement (FSwR). For FSwoR we consider both add/remove and replace-one adjacency, where we improve on the best current computable bound by factor of 4. We also show for the first time that the widely-used Poisson subsampling and FSwoR with replace-one adjacency have the same privacy to leading order in the sampling probability. Our work suggests that FSwoR is often preferable to Poisson subsampling due to constant memory usage. Our FSwR accountant includes explicit non con-asymptotic upper and lower bounds and, to the authors' knowledge, is the first such RDP analysis of fixed-size subsampling with replacement for DP-SGD. We analytically and empirically compare fixed size and Poisson subsampling, and show that DP-SGD gradients in fixed-size subsampling regime exhibit lower variance in practice in addition memory usage benefits.
Introduction
Differentially private stochastic gradient descent (DP-SGD) (Abadi et al., 2016) (DP-SGD) has been one of the cornerstones of privacy preserving deep learning. DP-SGD allows so-called moments accountant technique to sequentially track privacy leakage (Abadi al., 2016). This technique is subsumed by Rényi differential privacy (RDP) (Mironov, 2017). relaxation of standard differential privacy (DP) (Dwork and Rothblum, 2016) that widely used in private deep learning and implemented in modern DP libraries such as Opacus (Meta Platforms, 2024) and autodp (Zhu and Wang, 2019; Zhu al., 2022). RDP facilitates rigorous analysis when the dataset accessed by sequence of randomized mechanisms as in DP-SGD, While other privacy accountant frameworks such
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

as f-DP (Dong et al., 2022), privacy loss distributions (PLD) (Koskela et al., 2020), Privacy Random Variable (PRV) (Gopi et al., 2021), Analytical Fourier Accountant (AFA) (Zhu et al., 2022), and Saddle-Point Accountant (SPA) (A (Aighamdi et al., 2023) have been proposed to improve conversion to privacy profiles, RDP is still one of the main privacy accountants used in popular deep learning tools and applications. Thus, we expect providing tighter bounds specific to RDP will have important practical implications for the community. Each iteration of DP-SGD can be viewed as a private release of information about a stochastic gradient. DP accounting methods bound the total privacy loss incurred by applying a sequence of DP-SGD mechanisms in training. Privacy of the overall mechanism is ensured through the application of two random processes: 1) a randomized mechanism that subsamples minibatches of the training data, 2) noise applied to each gradient calculation (e.g., Gaussian). Informally, if mechanism MM is (e, 6DD then mechanism that subsamples with probability E (0, 1) ensures privacy (O(ge), -6)- a result known as the "privacy amplification lemma" (Li et al., 2012; Zhu and Wang. 2019). Computing the privacy parameters of mechanism requires an accounting procedure that can be nontrivial to design. Abadi et al. (2016) compute DP parameters for the special case of Gaussian noise, which was later extended to track RDP parameters by Mironov (2017). These analyses are limited to Poisson subsampling mechanisms which produce minibatches of variable size. This creates engineering challenges in modern machine learning pipelines and also does not allow for sampling with replacement. Fixed-size minibatches are preferable as they can be aligned with available GPU memory, leading to higher learning throughput. In practice, fixed size minibathces are of interest in practical applications such as private federated learning. To address the issue, Wang al. (2019) and Zhu et al. (2022) propose the latest fixed-size accounting methods. Wang et al. (2019) provide computable RDP bounds for FSwoR that cover general mechanisms under replace-one adjacency, while Zhu et al. (2022) give computable bounds for FSwoR under add/remove adjacency. Specifically, the study in (Wang et al., 2019) provides general formula to convert the RDP parameters of a mechanism M to RDP parameters of a subsampled (without replacement) mechanism, but the bounds they provide are only tight up to a constant factor at leading order (i.e., comparing dominant terms in the asymptotic expansion in q). Moreover, while the FSwoR results under add/remove adjacency relationship in (Zhu et al., 2022) are in parallel to our results, their accountant is not readily applicable to FSwoR under replace-one adjacency relationship.
In our work, we (1) present a new and holistic RDP accountant for DP-SGD with fixed-size subsam- pling without replacement (FSwoR) and with replacement (FSwR) that considers both add/remove and replace-one adjacency. We note that FSwoR is equivalent to shuffling the dataset at the start of every iteration and then taking the first B elements, which is conveniently similar to the default behavior of common deep learning libraries (e.g. Pytorch's 's DataLoader iterator object) while FSwR latter is implemented, e.g., in Pytorch's RandomSampler, and is widely used to address class imbalance in classifiers (Mease et al., 2007) and biased client selection in federated learning applications (Cho et al., 2022). (2) Our FSwoR improves on the best current computable bound under replace-one adjacency (Wang et al., 2019) by factor of 4. (3) Our FSwR accountant includes non-asymptotic upper and lower bounds and, to the authors' knowledge, is the first such analysis of fixed-size RDP with replacement for DP-SGD. (4) For the first time, we show that FSwoR and the widely-used Poisson subsampling have the same privacy under replace-one adjacency to leading order in the sampling probability. This has important practical benefits given the memory management advantages of fixed-size subsampling. Thus our results suggest that FSwoR is often preferable to Poisson subsampling. The implementation of our accountant is included in Supplementary Materials and is also publicly available to the community at https:/ / //githu.. thub. com/ ////starr-iii ailab/FSRDP.
2 Background and Related Work
Mironov (2017) proposed differential privacy definition based on Rényi divergence, RDP, that subsumes the celebrated moments accountant (Abadi et al., 2016) used to track privacy loss in DP-SGD. RDP and many other flavors of DP rely on subsampling for privacy amplification to ensure that privacy guarantees hold when DP-SGD is applied on samples (i.e., minibatches) of training data (Bun al., 2018; Balle et al., 2018). Later works such as (Mironov et al., 2019; Zhu and Wang, 2019) propose generic refined bound for subsampled Gaussian Mechanism that improves the tightness of guarantees in RDP. However, these methods also produce variable-sized minibatches. Bun et al. (2018). Balle et al. (2018), and Wang et al. (2019) propose fixed-size subsampled mechanisms. Balle et al. (2018) provide general fixed-size subsampling analysis with and without replacement but their bounds focus on tight (c, 6DP bounds for single step, and are not readily applicable to DP-SGD.
2

---

The AFA developed by Zhu et al. (2022) is an enhancement of the moments accountant offering lossless conversion to (e, guarantees and is designed for general mechanisms. However, in the context of DP-SGD, there are still technical and practical difficulties. For instance, in DP-SGD there generally a large number of training steps, in which case the numerical integrations required by Algorithm in Zhu et al. (2022) involve the sum of a large number of oscillatory terms. This can lead to numerical difficulties, especially in light of the lack of rigorous error bounds for the double (Gaussian) quadrature numerical integration approach discussed in their Appendix E. 1. In addition, the bounds Zhu et al. (2022) are not readily applicable under replace-one adjacency. Due to these considerations, and the fact that RDP is still widely used, in this work, we focus improving the RDP bounds from Wang et al. (2019).Haes et al. (2024) uses the results in (Zhu et al., 2022) to provide a bound specific to DP-SGD when one is only concerned with training data reconstruction attacks rather than the membership inference attacks, which leads to a relaxation of DP to provide a bound that is only applicable to defending against data reconstruction and not membership inference. Our work can be viewed as a complimentary work to (Hayes et al., 2024) that is specific to DP-SGI) and provides conservative bounds protecting against membership inference attacks (and thus any other type of model inversion attacks including training data reconstruction) in the RDP context.
In summary, to our knowledge, Wang et al. (2019) provide the best computable bounds in the fixed- size regime for RDP that are practical for application to DP-SGD, While the computations in (Wang general mechanism, in this work, we show
et al., 2019) have the attractive property of applying that there is room for obtaining tighter bounds specific to DP-SGD with Gaussian noise. Our FS-RDP bounds address this theoretical gap by employing novel Taylor expansion expansion approach, which precisely captures the leading order behavior in the sampling probability, while employing a computable upper bounds the integral remainder term to prevent privacy leakage. For convenience, we provide the definition of RDP below.
Definition 2.1 ((a, RDDD (Mironov et al., 2019)). Let M be a randomized mechanism, i.c., M(D) is a probability distribution for any choice of allowed input (dataset) D. A randomized mechanism is said to have (a, R)-RDP if for any two adjacent datasets D, D' it holds that Do(M(D))M((D)) s where the Rényi divergence of order a > 1 is defined by
((T)) D (QI a log [ (P(())
a P(r)dr
(1)
The definition of dataset adjacency varies among applications. In this work we consider two such relations: 1) The add/remove adjaceney relation, where datasets 1) and D' to be adjacent if one can be obtained from the other by adding or removing a single element; we denote this by 1) -a/r D'. 2) The replace-on one adjacency definition, denoted D z D', wherein D is obtained from D' by replacing single element. In the next section we derive new RDP bounds when M is DP-SGD using fixed-size minibatches, with or without replacement.
3 Rényi-DP Bounds for SGD with Fixed-size Subsampling
In this section we present our main theoretical results, leading up to Rényi-DP bounds for SGD for fixed-size subsampling done without replacement (Thm. 3.3 for add/remove adjacency and Thm. 3.4 for replace-one adjacency) and with replacement (Thm. 3.7). In Sec. 3.4, we also compare our results with the analysis in (Wang et al., 2019) and show that our analysis yields tighter Rényi bounds by factor of approximately 4.
3.1 FS-RDP: Definition and Initial Bounds
Given a loss function L, a training dataset D with [D] elements, and a fixed minibatch size, we consider the DP-SGD NN parameter updates with fixed-size minibatches,
1 [B]
e 0P GeG
G.
Clip(V Z, IEB!
Σ
(2)
where is the iteration number, the initial condition of independent of D. q) are the learning rates, the noises Z, are Gaussians with mean 0 and covariance C2 of I. and the Bdd are random minibatches
3

---

with fixed size; we denote the fixed value of [B,"] by [B] for brevity. We will consider fixed-size subsampling both without and with replacement: the former, BP is a uniformly selected subset of (O...., [] - } of fixed size [B| for every / and in the latter, Bi is uniformly selected element of (O.... D] - for every t. We assume the Gaussian noises and minibatches are all independent jointly for all steps. Here Clip denotes the clipping operation on vectors, with E bound C' > i.e. C1ip( := x/ //maxxx1 |a:ll2/C) We derive RDP bound (Mironov, 2017) for the mechanism consisting of T steps of DP-SGD (2), denoted:
(D. = (0 O.)
Specifically, we consider the cases without replacement, M PS (D), and with replacement, [o.T]
[o.T]" (D). To obtain these FS-RDP accountants we bound D, (M D' is any dataset that is adjacent to D; as previously stated, we will consider both add/remove and replace-one adjacency. By taking worst-case bounds over the input state each step, as done in Theorem 2.1 in (Abadi et al., 2016), we decompose the problem into a sum over steps
[0,27 (D) (D)) where
Da FS (0.7) (D'))
FS
sup Da (e D'))
(4)
t=0 8.
where the time- inmeiiinooogeeouss transition probabilities are,
1
pr D) 11B11a11
N Nu.0o...),5000+11))
(5)
(0 b, D) = - 1) Clip(VoL(O,, D.),
iEb
Here Nu.a=(0) is the Gaussian density with mean l and covariance 121, o3 = of /BB. and the summation is over the set of allowed index minibatches, b, with normalization constant Z Z1B111D1 (())) for FS and ZIBIID = D for FSwR-RDP. When additional clarity FS.s to distinguish the transition probabilities for these needed we use the notation p. FS.. and pt
respective cases.
3.2 FS RDP Upper Bounds
The computations thus far mimic those in (Abadi et al., 2016; Mironov et al., 2019), with the choice of subsampling method and adjacency relation playing no essential role. That changes in this section, where we specialize to the case of subsampling without replacement. First, in Section 3.2.1 we consider the add/remove adjacency relation; the proof in this case contains many of the essential ideas of our method but is simpler from a computational perspective. The more difficult case of replace-one adjacency will then be studied in Section 3.2.2
3.2.1 Add/remove Adjacency
In Appendix A we derive the following Rényi divergence bound for FS "Swok-subsampled DP-SGD under add/remove adjacency.
Theorem 3.1. Let D Sajr D' be adjacent datasets. With transition probabiiiiir defined as in (5)
and letting q = |B|/|D| we have
sup Da (vt (05500000440000 D) (0000 < DalgN (1 (6) 0,
The key step in the proof consists of the decomposition of the mechanism given in Lemma A.1. We note that the r.h.s. of (6) differs by a factor of 1/4 in the variances from the corresponding result for Poisson subsampling in Mironov et al. (2019). This is due to the inherent sensitivity difference between fixed-size and Poisson subsampling under add/remove adjacency; see (28) (29). To bound the r.h.s. of (3.1) we will employ a Taylor expansion computation with explicit remainder bound. As the r.h.s. of (6) has the same mathematical form as the Poisson subsampling result of Mironov et al. (2019), and therefore can be bounded by the same methods employed there, the Taylor expansion

---

method is not strictly necessary in the add/remove case. However, we find it useful to illustrate the Taylor expansion method in this simpler case before proceeding to the significantly more complicated replace-one case in Section 3.2.2, where the method in Mironov et al. (2019) does not apply.
The Rényi divergences the r.h.s. of (6) can be written
1
Da(9N1,0714 (1
log oo (4)l
a
where for any > 1, 0 we define
Ha,o (q) = (
q / + (1 (11--9)No, N).o..2/4(()) /o.o=
(8)
Na.0=/a(0)
Eq. (8) does not generally have closed form expression. We upper bound via Taylor expansion with integral formula for the remainder at order m (c.f. Thm. 1.2, (Stewart, 2022));
m-1 8² dh
Ha (1)
(a) + Ra)am()))
(9)
k! dgh
k=
where the remainder term is given by
aa.am m (4) 9" /
(1 8)m-1 d (m 1)!
dam Ho Ha. (sq)ds.
(10)
Note that we do not take - and Ho.o is not required to be analytic in order to make of (9). Also note that (9) is an equality, therefore we can compute/upper-boung each the terms then will arrive at computable non-asymptotic upper bound Ha.((1), without needing to employ non-rigorous stopping criteria for an infinite series, thus avoiding privacy leakage. The order m is parameter that can be freely chosen by the user. To implement (9) one must compute the derivatives d
dy Ha. (0) and bound the remainder (10). We show how to do both of those steps for general m in Appendix B; in the following theorem we summarize the results for m = 3, which we find provides
sufficient accuracy in our experiments.
Theorem 3.2 (Taylor Expansion Upper Bound). For q < 1 we have
o² Ha,o (g) =1 aala- 1) + Ra,
(11)
where the remainder has the bound
Σl -a]-3 (Ta)-3-013++])
( d [[a]-3) B Bo.43 + Ba,
ifa - 3 >>0
Rog,,3(9) - 13)aaa-1jaa--
11 q) Bo,3
ifa - 3
=Ra,a,(4))
(12)
and the M and B parameters are given by (41) and (44) respectively.
The reason for the complexity of the formulas (1 (12) is the need to obtain rigorous upper bound, and not simply an asymptotic result. Results for other choices of m are given in Appendix B.
Combining Theorem 3.2 with equations (4) (8) we now arrive at computable T-step FS -DDP guarantee.
Theorem 3.3 (T-step FS Upper Bound: Add/Remove Adjacency). Assuming 9 < 1, the mechanism M M PSun
(D). defined (3), has (a, [0,T] ( RRDP under add/remove adjacency, where [o.T]
FSnn
o² 1+ a(a 1)M Ra.0.aa))
FS 10.77
(a)
Σ
log
(13)
2
t=0
where M and R are given by (41) and (12) respectively.
More generally, using the calculations in Appendix B one obtains RDP bounds for any choice of the number of terms, m. The result (13) corresponds to m 3, which we find to sufficiently accurate in practice; see Figure 6.
5

---

3.2.2 Replace-one Adjacency
Theorem 3.1 applies to add/remove adjacency, but our method of proof can also be used in the replace-one adjacency case, where yields the following FS -DDP upper bounds.
Theorem 3.4 (FSwoR-RIDE Upper Bounds for Replace-one Adjacency). Let D z D' be adjacent datasets. Assuming q = |Bl/D|| < for any integer m Z 3 we have
sup Dr (p: (pt (0.4) 10,, D) Soess00000
D) 10++1
(14)
01
log 1 + paaa - 1) (ellrr - -2lor)
m-1
Σ R=3
Faoor + Ea.mm(a)
+
k!
where Fa.o. is given by (80) and ma. by (87).
The derivation, found in Appendix C, follows many of the same steps the add/remooe-adjaceney case from Theorem 3.1, though deriving bounds on the terms in the Taylor expansion is significantly more involved and the resulting formulas are more complicated. The decomposition from Lemma A. again constitutes a key step in the proof. For comparison purposes, in Appendix C.I we derive the analogous result for Poisson-subsampling under replace-one adjacency; see Theorem C.9.
corresponding T-step RDP bound, analogous to Theorem 3.3, for replace-one adjacency can similarly be obtained by combining Theorem 3.4 with Eq. (4).
Theorem 3.5 (T (T-step FS RDDP Upper Bound: Replace- one Adjacency). Assuming < and FS.
for any integer m 2 3, the mechanism M (D), defined in (3), has (a, ((.T) (o)) under replace-one adjacency, where
1Sme (a) 10,T
T-1
log 1 12aaala-10 10laa-))) (1) -2100))
m-1
Σ
- k!
Faork (o)
(15)
Here Fa,or,k is given by (80) and Ea,o,, (q) by (87).
We emphasize that one strength of our approach that it provides a unified method for deriving computable bounds in both the add/remove and replace-one adjacency cases. We also note that Theorem 1 (bb of Zhu et al. (2022). Theorem 6 of Balle et al. (2018), and Theorem 5 in Mironov al. (2019) combine provide an alternative method for deriving the add/remove result of Theorem 3.1 but not the replace-ons one result of Theorem 3.4. Unlike in the corresponding add/remove theorems, using m in Theorems 3.4 and 3.5 is often required to obtain acceptable accuracy, though we generally find that m = 4 is sufficient; see Figure 2.
3.3 RDD Upper and Lower Bounds
We similarly obtain RDP bounds for DP-SGD using fixed-size minibatches with replacement, i.e., (2) with minibatches Bi that are iid uniformly random samples from {o. [D] - 1) First we present upper bounds the RDP of 1555. (D). The derivation follows similar pattern to that of [0.7]
our results for IFS -ubsaampin,, first using a probabilistic decomposition of the mechanism (see Lemma D.1) and then expanding (see Appendix D.
Theorem 3.6 (Fixed-size RDP with Replacement Upper Bound), Assuming [D] |B] and under FS.R. add/remove adjacency, the mechanism M (D) has (a, '(o.T) (a:))-DDP with ( (Ha.o given by (8)
T-1
FS (a) 1..
<
log
Σ n=1
an Ha.Ha...i Ha..o
(16)
a
1=0
(1B3)
T == 7= (1 - [D] 18
Ön = q
D - (1 1DI111118-
The functions Ha.a were previously bounded above in Theorem 3.2 (for order m 3), and more generally in Appendix B (for general m). It is straightforward to show that q O(g) and ă.

---

0l Therefore, recalling the asymptotics (11) of Ha.o, the behavior of FSuR (a) and FS (a) (0,77
(0o77
is the same at leading order in q. We also present the following novel lower bounds on the Rényi divergence for one step of FS DP-SGD; see Appendix D.2 for the derivation.
Theorem 3.7 (Fixed-sizz size RDP with Replacement Lower Bound). Let the mechanism M,...eD (D. O1)
denote the t 'tth step of FS DP-SGD (2) when using the training dataset D and starting from the NN parameters Oe, i.e. the transition probabilities (5) where the average is over minibatches b that are elements of {0...., [D] - 131B1, In this result we consider the choice of [ to be fixed but will allow D and Og vary. Suppose there exists OG, d, and d' such that
Clip C000, d)) = C (o,,(,, and [[Clip( di)1 = |[Clip(V d')) C,
i.e, when using the NN parameters 0,, the clipped gradients at the samples d and d' are anti-parallel and saturate the clipping threshold. Then for any integer 2 and any choice of dataset size N we have the following worst-case Rényi divergence lower bound
|88 Σ Bloona
Da (MMM (D.001I.
any On On 8 Eies amzy
sup (6,, (...D.D'):ID =N D' D'
log
(17)
where On == (1 (11) --
The lower bound (17) provides a complement to one step of the upper bound from Theorem 3.6. We demonstrate the behavior of the lower bound (17) in Figure I, where we employed the computational method discussed in Appendix D.2.1. Specifi- cally, we show the FS RDP lower bound as a function of a for fixed q and several choices of [B] For small a, the lower bounds for different B 's are approximately equal. This holds up until a critical B -dependent threshold where there is "phase transition" to a regime with non-trivial BB] dependence (even for fixed q) wherein the RDP bound increases quickly. This is in contrast to RDD which depends on [B] only through the ratio q. The critical is smaller for larger [B, which implies worse privacy guarantees for larger [B), with all else being equal. Intuitively, larger minibatch size provides a greater chance for the element that distinguished D from D' to selected multiple times in a single minibatch. If is selected too many times then it can overwhelm the noise and become "noticeable", thus substantially degrading privacy; this is the key property that distinguishes FSwgfrrm FS In practice, this behavior implies that FSD requires much smaller minibatch sizes than FS in order to avoid this critical threshold and maintain privacy.
One Cnop Lower Bound
Figure 1: FS.x
FS-g-RDP RDP lower bounds from Theorem 3.7 as function of a, with 6 and q 0.001.
3.4 Comparison with (Wang et al., 2019)
We compare our fixed-size RDP upper bounds with the upper and lower bounds obtained by applying the general-purpose method from Wang et al. (2019) to DP-SGD with Gaussian noise. First compare the results asymptotically to leading order in q and 1/0?, which is the domain relevant to applications, and then we will compare them numerically using the full non-asymptotic bounds. Unless stated otherwise, from here on the phrase leading order implicitly refers to the parameters and 1/o
The method from Wang et al. (2019) applied to DP-SGD (App. E. gives the one-step Rényi bounds
(a) 22
1) + 0 = 842 0 O(9))
(18)
In contrast, to second order in y. one step of our FS-RDP results under add/remove adjacency from Theorem 3.3 or Theorem 3.6 gives
82 <((a) S a 4/07 - -1) 0(9))) = 2/ Ol'))
2
7

---

One-step FSwoR, RDP Bound (r:a)
while our WOR RDP bound under replace-one adjacency from Theorem 3.4 gives
30-1
<(a) spa
22002 -1) (99)) -2q/ +
(19)
he-1
Thm 3. upper bound
Thmm bound
101
1mm 3.4 upper bound 5)
Wang al. upper bound
Therefore, to leading order, our methods all have the same behavior and give tighter RDP bounds by factor of 4 than that of Wang et al. (2019). We emphasize that the adjacency relation used by Wang al. (2019) is replace- one and therefore, strictly speaking, should be compared only with our Theorem 3.4, which also uses replace-one adjacency. Figure 2 shows a non-asymptotic comparison
Wang lower
20
40
50
62
Figure 2: Comparison of FS bounds under replace-one adjacency from Theorem 3.4 for various choices of m with the upper and lower bounds from Wang et al. (2019). ae = 6. [B] 120, DI = 50, 000. between these RDP bounds, with ours being tighter significantly tighter than that of Wang al. (2019). In particular, our bound from Theorem 3.4 with m = remains close to the theoretical lower bound from Wang et al. (2019) over the entire range of a's pictured, which is a sufficiently large range for practical application to DP, e.g., larger than the default range used in Meta Platforms (2024).
Following the setting in (Abadi et al., 2016), we provide corre- sponding (c, DD guarantees in Figure 3 shows corresponding c for 8 [1c- - 4, le- 5, le 6, le 7, 1c 8, Ic 9. le 10} after 250 training epochs in DP-SGD. To translate RDP bounds to (e, d)DP, we used Theorem 21 in (Balle et al., 2020), which is also used in the Opacus library. As shown in Figure 3, our FS bounds with v E {3, 4, 5] (solid lines) are close to the lower-bound provided in (Wang et al., 2019) (circles) over range of 6's that depend on the value of m. These guarantees are sig- nificantly tighter than the upper bound from Wang et al. (2019) (dashed line). In our experiments, we observe that m and m 5 yields essentially the same results and we find that m = 4 suffices obtain good results in practice while outperforming (Wang et al., 2019).
Thin 2.4 upore hound in 3
Thm. J.4 uppor bound 2m 4:
Thmm, upper bounz
"Mrr uppur bourd
FS (c, 6)- guar- antees under replace-one adjacency; comparison of Wang al. (2019) up- per and lower bounds with our The- orcm 3.4 for various choices of m. = 6, B = 120, |D| = 50, 000.
Figure 3:
4 Comparing Fixed-size and Poisson Subsampling
In Sec. 3.4 we demonstrated that our Rényi-DP-SGI bounds with fixed-size subsampling in Thm. 3.3 are tighter than the general-purposs fixed-size subsampling method from Wang et al. (2019). However, the most commonly used implementations of DP-SGD rely on Poisson subsampling, not fixed-size, and there the comparison is more nuanced. In this section we compare Poisson and fixed-size subsampling and point out advantages and disadvantages of each.
4.1 Privacy Comparison
In terms of privacy guarantees, all else being equal, when using replace-one adjacency we find that DP-SGD with fixed-size subsampling yields the same privacy guarantees as Poisson subsampling to leading order; specifically, when moving from add/remove to replace one-adjacency, our fixed- size subsampling DP bounds do not change at leading order but the Poisson subsampling DP bounds change by factor of 2 to match the fixed-size results. In contrast, when using add/remove adjacency we find that Poisson subsampling has a natural advantage over fixed-size subsampling by approximately factor of 2. Here we outline the reason for this intuitively.
The derivation of Rényi-DP bounds when using Poisson subsampling, (see Abadi al. (2016); Mironov et al. (2019)) shares many steps with our derivation for fixed-size subsampling without replacement in Appendix A. In both cases, to leading order the bound on the Rényi divergence is proportional to || μ 112 where and μí' are the sum of the gradients under the adjacent datasets D and D'. When using Poisson subsampling, under add/remove adjacency, μí differs from ja by the addition or deletion of a single term in the sum with probability q. while under replace-one adjacency, yl differs from y by the replacement of one element with probability q. Therefore the former case, ||u - p') || is the norm of single clipped vector, hence it scales with the clipping threshold, C, while
8

---

in the latter, I|u- is the norm of the difference between two clipped vector, hence it scales with 2C, as in the worst case the two vectors are anti anti-parallel. In fixed-size subsampling and under both adjacency relations, ja' differs from fA by replacing one element with another (due to the fixed-size minibatch constraint) and therefore I| - μ²ll scales like 2C. After squaring and at leading order, this leads to a factor of 4 difference in the Rényi divergences between Poisson and fixed-size cases under add/remove adjacency while under replace-one adjacency the Poisson and fixed-size results agree; see Appendix C.1 for more precise analysis of the latter comparison.
Translating this to (c, 8)-DP then leads to an approximate factor of difference in for the same ó under add/remove adjacency, as shown in Appendix G, while under replace-one adjaceney the different subsampling methods lead the same DP guarantees at leading order. When the higher order terms are taken into account, Poisson subsampling regains slight privacy advantage under replace-one adjacency; see Figures 4 and 7.
4.2 Comparison on CIFARIO
Our numerical comparisons in Section 3.4 showed that F'SOOR-DPP yields significantly tighter guar- antees than its counterpart from Wang et al. (2019). It is also useful to compare the empirical privacy guarantees of fixed-size versus the Poisson subsampling RDP commonly used in DP implementations such as Opacus. To this end, we use CIFARIO 10 and a simple convolutional neural network (CNN) to compare the canonical Poisson subsampling RDP with FS-RDP. Our setup closely follows the procedure in (Abadi et al., 2016). Note that the goal of this comparison is not to achieve the of the-art privacy guarantees on CIFARIO with any specific neural network. Instead we aim to compare the performance and guarantees with the alternative fixed-size and Poisson subsampling methods. Following Abadi et al. (2016), we used simple CNN network that pre-trained on CIFAR 100 dataset non non-privately. Our CNN has six convolutional layers 32, 32, 64, 128, 128, and 256 square filters of size 3, in each layer respectively. Since using Batch Normalization layers leads to privacy violation, we used group normalization instead as common practice that is also used the Opacus library (Meta Platforms, 2024). Our network has 3 group normalization layers of size 64, 128, and 256 after the second, fourth, and sixth convolution layer. Similar to Abadi et al. (2016), this model reaches the accuracy of 81.33% after 250 epochs of training in a non non-private setting. For the Poisson subsampling RDP, we simply used the one in Opacus.
Our Thm. 3.4 upper bound Im 4]
Fig. 4 compares the privacy guarantees (c. 8) for FS RDP and the method proposed by Wang et al. (2019) on the above CNN model after 250 training epochs with o; 6, |B] 120. clipping
Wivnng el houn: Poisson subsmmpeed
325
threshold C 3.0, and learning rate |r = le- 3 on CIFARI0 following the same setting Abadi et al. (2016). Fig. 4 also compares the testing accuracy of Poisson subsampled RDP in Opacus with our FS - We ran each method times with different random seeds for sampling: 0, 1, 364, 2, 560, 3, 000, and 4, 111. Shaded areas show 3-sigma standard deviations around the mean. Both logical and physical minibatch sizes were set to 120 in Opacus. Experiments were run on a single work station with an NVIDIA RTX 3090 with 24GB memory. The runtime for all experiments was under 12 hours. As shown in Figure 4, FSwok RDP yields substantially tighter bounds than (Wang et al., 2019)
60 8
15
(top panel) and reaches the average accuracy of 63.87% after 250 epochs (vs. 61.57% for Poisson subsampled RDP) (bottom panel). Figure 4 indicates that for a fixed a, -RDP surpasses the accuracy of Poisson subsampled RDP Opacus, but with slightly higher epsilon guarantees, as shown in the top panel. This behavior matches the approximate calculation from Eq. (150) as well as the discussion in Section 4.1; specifically, Poisson and FS FSRRR- RDP agree to leading order but the higher order contributions give Poisson subsampling a slight privacy advantage at the same level of added noise. We emphasize that these results all apply to the replace-one notion of adjacency, as used in (Wang et al., 2019) and also our Theorem 3.4; we did not find existing computable RDP bounds for buusonn-ubsampling under replace-one adjacency and so we used the new result in Theorem C.9. We conjecture that the performance difference observed in the bottom panel of Figure 4
RSP (m)-10)
Polsson Subsampled RDP (Opacus)
185
255
Figure 4: Privacy guarantees of FS RDP, Wang et al.'s, and Pois- Subsampled RDP (top). Com- paring FS..R- against Poisson subsampled RDP (bottom). a. = 6. C = 3. [B] 120, |D] 50, 000, Ir = 1e - 3.
performance

---

is due to the difference in variance between Poisson and fixed-size subsampling, which we derive in Appendix F. Specifically, there we show that fixed-size subsampling has reduced variance compared to Poisson when the parameters are away from minimizer. Additional experiments, gauging the sensitivity of Fo to key parameters including and B are given Appendix H.
4.3 Memory Usage Comparison
The RDP accountant used in common DP libraries assumes Poisson subsampling mechanism that leads to variable-sized minibatches during the training. That is, the size of each mini-batch cannot be determined in advance. Allowing the minibatches to have variable sizes creates an engineering challenge: an uncharacteristically large minibatch can cause an out-of-memory error, and depending how fine tuned the minibatch size is to the available GPU memory this could be a frequent occurrence. To tackle this issue, the Opacus implementation requires the additional complication of wrapping the Pytorch DataLoader object into SraechMMeorryMaaagee object, to alleviate the memory intensive nature of Poisson subsampling. BatchMemoryWaaageer requires privacy practitioners to define two minibatch sizes: one a logical minibatch size for Poisson sampling and the other is a physical minibatch size that determines the actual space allocated in memory and is determined by the practitioner via a variable named max physical batch size (Meta Platforms, 2024). This design follows the distinction between "lots' and minibatches described in the moments accountant (Abadi et al., 2016).
FD (Ours) (Opacus) FDP (Opscus nay [Osecus)
Our proposed FS-RDP does not require this memory man- agement and is much less memory intensive. Figure 5 depicts the GPU memory footprints during 100 epochs
33500-
GPU memary Usage (MB)
of privately training the above CNN on CIFARIO with
17990
FS and three of the most common DP accoun- tants: RDP (Mironov et al., 2019), f-DP (Dong et al.,
15003
12390
2022), and PRV (Gopi et al., 2021). As shown in Figure 5, the memory usage of FS-RDP remains constant at 14,826
30000
MB. However, the memory usage varies from 7,984 MB to 23,280 MB (almost twice larger than FS-RDP) for Poisson subsampled RDP in Opacus. Similar memory usage is observed for other Opacus accountants that use Poisson subsampling mechanism (i.e.. f-DP and PRV). This fluctu- ating memory usage could result in undesirable outcomes in settings where resource-cond conttrcc-cnnt devices consid- cred. For instance, in federated learning environments, erratic memory usage could result in higher dropout rate and delay the global model's convergence (Liu et al., 2021). It could also undermine model's 's accuracy and fairness, preventing lower-end devices from participating in the training process (Imteaj al., 2021).
1500
oparc
Figure 5: Comparing memory usage of FS-RDP with other Opacus privacy ac- countants in each training epoch. We used |B] 120, and |D| 50, 000. Un- like other methods, FS-RDP's memory usage remains constant.
Conclusion
Differentially private stochastic gradient descent with fixed-size minibatches has attractive properties including reduced gradient estimator variance and simplified memory management. Our work presents holistic RDP accountant for DP-SGD with fixed-size subsampling without replacement (FSwoR) and with replacement (FSwR) and, in the FSwoR case, consider both add/remove and replace-one adjacency. As we showed theoretically and empirically, since FSwoR under replace-one adjacency leads to the same leading-order privacy guarantees as the widely-used Poisson subsampling, we suggest using the former over the latter to benefit from the memory management and reduced variance properties. For subsampling without replacement under replace-one adjacency, we obtained significantly tighter RDP bounds (4 times improvement) over the most recent computable results (Wang et al., 2019). For subsampling with replacement we obtained the first non msymmpttt upper and lower RDP bounds for DP-SGD. We also provided the first comparison of gradient estimator's variance and privacy guarantees between FS-RDP and Poisson subsampled RDP commonly used DP libraries. Our analysis revealed that FS-RDP reduces the variance of the gradient estimator. We highlighted the memory usage advantages of FS-RDP over Poisson subsampled RDP, which makes a practical choice for privately training large deep learning models. We made FS-RDP's implementation and its evaluations available online such that it can be added to common DP libraries.
adjacen
10

---

Acknowledgements
Behnia acknowledges support from the University of South Florida Sarasota-Manatee Office of Research via the Interdisciplinary Research Grant program.
References
Abadi, M.. Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages -08-118.
Alghamdi, W., Gomez, J. F., Asoodeh, S., Calmon, F., Kosut, O., and Sankar, L. (2023). The saddle-point method in differential privacy. In International Conference on Machine Learning, pages 508-528. PMLR.
Balle, B., Barthe, G., and Gaboardi, M. (2018). Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems (NeurlPS), 31.
Balle, B., Barthe, G., Gaboardi, M., Hsu, J., and Sato, T. (2020). Hypothesis testing interpretations and Rényi differential privacy. In Chiappa, S. and Calandra, R., editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2496-2506. PMLR.
Bun, M., Dwork, C., Rothblum, G. N., and Steinke, T. (2018). Composable and versatile privacy via truncated CDP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74-86.
Cho, Y.J., Wang, J., and Joshi, G. (2022). Towards understanding biased client selection in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 10351-10375. PMLR.
Dong. J., Roth, A., and Su, J. J. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society: Series (Statistical Methodology). 84(1):3-37.
Dwork, C. and Rothblum, G. N. (2016). Concentrated differential privacy. CoRR, abs/1603.01187.
Folland, G. B. (1999). Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons.
Gopi, S., Lee, Y. and Wutschitz, L. (2021). Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34:11633:11111 1631-116642.
Hayes, J., Balle, B., and Mahloujifar, S. (2024). Bounding training data reconstruction in dp-sgd. Advances in Neural Information Processing Systems, 36.
Imteaj. A., Thakker, U., Wang, S., Li, J., and Amini, M. H. (2021). A survey on federated learning for resource-constrained iot devices. IEEE Internet of Things Journal, 9()::1-24.
Koskela, A., Jälkö, and Honkela, A. (2020). Computing tight differential privacy guarantees using FFT. In Chiappa, S. and Calandra, R., editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 2560-2569. PMLR.
Lebeda, C., Regehr, M., Kamath, G., and Steinke, T. (2024). Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition. arXiv preprint 24Xiv:2405.20769
Li, N., Qardaji, W., and Su, D. (2012). On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 32-33.
Liu, J., Xu, H., Wang, L., Xu, Y., Qian, C., Huang, J., and Huang, H. (2021). Adaptive asyn- chronous federated learning resource-constrainned edge computing. IEEE Transactions on Mobile Computing.
11

---

Mease, D., Wyner, A. J., and Buja, A. (2007). Boosted classification trees and class probabil- ity/quantile estimation. Journal of Machine Learning Research, 8(3).
Meta Platforms, (2024). Opacus. http:////ppcccsaaaccc/ccttttttoa 01/21/2024).
(Accessed on
Mironov, I. (2017). Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE.
Mironov, I., Talwar, K., and Zhang, I.. (2019). Rényi differential privacy of the sampled Gaussian mechanism. arXiv preprint a90iv: 10530.
Stewart, D. (2022). Numerical Analysis: Graduate Course. CMS/CAIMS Books in Mathematics. Springer International Publishing.
Van Erven, T. and Harremos, P. (2014). Rényi divergence and Kullback-Leible divergence. IEEE Transactions on Information Theory, 6077):3777-3820.
Wang, Y.X.., Balle, B., and Kasiviswanathan, S. P. (2019). Subsampled Rényi differential privacy and analytical moments accountant. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1226-1235 PMLR.
Zhu, Y., Dong, J., and Wang, Y-X. (2022), Optimal accounting of differential privacy via characteris- tic function. In International Conference Artificial Intelligence and Statistics, pages 4782-4817. PMLR.
7hu, Y. and Wang, Y.-X. (2019). Poission subsampled Rényi differential privacy. In International Conference on Machine Learning, pages 7634-7642, PMLR.
12

---

A Proof of Theorem 3.1: FS Bound under Add/Remove Adjacency
In this appendix we prove one-step Rényi bound for DP-SGD using subsampling without replace- ment under the add/remove adjacency relation, as stated in Theorem 3.1. To do this, we will show that the sum over minibatches 6 in (5) can be rewritten an average of Gaussian mixtures with parameter [B /I. This will then allow us to mimic several steps from the derivation in Mironov et al. (2019), which applies to Poisson subsampling. In the Poisson subsampling case the Gaussian mixture structure is more or less apparent from the start, but here it requires some additional work to isolate. We first consider the case where D' is obtained from D by removing one element. Without loss of generality we can let D' = (Do: ...., D DI-2). Later we will show that the bound we derive in this case also bounds the case where D' has one additional element.
Noting that No Es is simply the expectation with respect to the distribution of B,, start by showing that the distribution of B, can be obtained from the distribution of B,"' through the introduction of two auxiliary random variables J and B as follows: Let J be Bernoulli(g) random variable where q = | and let (B', B) be random variables independent
such that B' is uniformly selected subset of {o..... | - 22 of size [ (so B' ~ B,') and P( E | = 1/) is the uniform distribution on subsets of 1' of size [B] 1. Defining the random variable B by
B' if 0, BU BUD 13 i
B =
(20)
have the following:
Lemma A.1. The distribution of B. defined in (20), equals that of B.P.
Proof. It is clear that B valued in the subsets of {o,.... [D] - 1} having size [B). Given b C
{0, DI - }} of size [B] we have
P(B b) P b. = = 0) P(B =
(21)
=P(B' = 0) + P(BU 0)
[D] - b) =
If [D] - 1 & then b C (0, []] - 2) and the second term in (21) is zero, hence
P(B = b) =P('' = (1 (0)-)) 1-9
-101-1B)/12)
(22)
-(DTT"
- - -1 [B))
-PBBP =
((D))
as claimed. Now suppose
D) - 1 1 b. Then b {ID) - -1} is a subset of (0, | - 2} of size
B
1, hence
B
P(B =
- 1 11= - bb
(23)
B
[ 111B''))
D
B
EV B
[LNIDII P b) - 11D1 = 67]
D
1
1 | - --BI
P(b
D
D
1
P(BP- -b.
B
This completes the proof.
Using Lemma A. we can express the expectation with respect to B. in terms J. B', and B. This will provide us with the desired decomposition of the sum in (5). The definition (20) is reminiscent
13

---

of the constructions in Proposition 23 in Appendix C of Wang et al. (2019), however our analysis will also result in tighter bounds for DP-SGD than one gets from the purppss method in Wang et al. (2019).
Using Lemma A.1 in the manner discussed ahove, the transition probabilities (5) for one step of DP-SGD with FS "SwoR-subsampling can be rewritten as follows:
Pe(0(41(0e, D) =B [ (x.10....),,;((1+11)
(24)
=E (B,(Br @N (1P1) (0z+1) + (1
Recalling that B' B,'' and noting that (O,, B', D = p4(( B', D) (as D' agrees with D except for the last missing entry. which by definition cannot be contained in B'), the transition probabilities Pe(0r+1/0 0c. D*) can similarly be written
Pr(Oe+110r, =EuwB [N
(25)
The outer expectations in the expressions (24) and (25) now both with respect to the same distribution, with the key difference being captured by the parameter q. The construction (20) was introduced precisely that we might obtain such decomposition. It allows the next step proceed as in DP-SGD with Poisson subsampling Abadi et al. (2016); Mironov et al. (2019). Namely, we use quasiconvexity of the Rényi divergences (i.e., the data processing inequality) Van Erven and Harremos (2014) to obtain
Da (p(0++ 10,, () D)))
(26)
< max D. (NN (0,,0,,,1111)) + (1 (... (8())
=max D. (g.
(D)l + (1 N No.07)
(b)
where, as in Abadi et al. (2016); Mironov et al. (2019), we used a change of variables to reduce the computation to I-dimension in the last line.
Remark A.2. We note that the above analysis can be applied to any divergence, D, that is quasiconvex in its arguments, not just the Rényi divergences. In the general case one similarly finds
((p(0--110,, (0) D') maxx D ( (0, + (1 N) (o (0,, (8(
(27)
For instance, this holds for all / divergences, including the important class of hockey-stick divergences that are important for other DP frameworks such as Zhu et al. (2022).
Returning to (26), recalling that C is the clipping bound and that b c b' and |b' 1, we can compute
13, D) bu (IDI (0,,
(28)
CClip( D(-
Σ Clip(VoC(O,, D.))
|B
10 B = +?
(29)
We note that this result is times large the corresponding calculation in the case of Poisson subsampling, i.e., the sensitivity in the case of fixed-sized subsampling is inherently twice that of Poisson subsampling when using add/remove adjacency. This is because Poisson subsampling when the minibatch from D differs from that of D' it is due to the inclusion of a single additional element. However, fixed-size subsampling, when the minibatches are not identical then they differ by replacement; this contributes more to the difference in means by a factor of 2.
14

---

obtain Combining (29) with the fact that scaling the means in Gaussian mixtures by the same factor e 2 1 can only increase the Rényi divergence, see Section 2 in Mironov al. (2019), we obtain the following uniform Rényi bound.
sup Da (p(0+++ |10,, (0 D')) S Da (gN.... + ( No.0?)
(30)
Now we show that the right-hand-side of (30) also bounds the case where D' has one additional clement. Repeating the steps the above derivation, this case we obtain
sup Da (p(0c+110... 0.
D))) - Da (No 11 m, os + (1 N),,),
(31)
where 7 B + 1); the appearance of D' = |D| + 1 here is due to the interchange of the roles of D and D' the decomposition (20) for this case. Next use Theorem in Mironov al. (2019) to obtain
Da I + (1 (1- (1- No.5;) s Da + (1 N) No.a;)
(32)
Quasiconvexity of the Rényi divergences implies the right-hand-side (32) is non-decreasing in q. Therefore, as q S q, we obtain
sup Da (p(00(1110) () D))) S Da(gN + (1 - q) N,.a No,aa))
(33)
The upper bound here is the same as the one we obtained in (30) when D' had one fewer element than D. Finally, by changing variables rescale the mean to 1 and therefore, noting that
= =01/2
(34)
sup Do Da D)lpp((0++1100 D')) s Do 10/4 + (1 /aNoo3/al/Nooo3//4 (35)
0:
This completes the proof.
B Taylor Expansion of Ha. (q)
In this appendix we provide details regarding the Taylor expansion (9) of Ha (g) (Eq. (8)), which can be written
Ha, (g) = - Ni.0//1000
(1 (1- N No. No,
N1, (4( (Noooo0//// (0)
a
In Section 3.2.1 we obtained one-step RDP bounds in terms of the Rényi divergence
1 Da(gNN, (1 N). No,00 a log[Ho., (4)
(36)
To obtain the computable RDP bounds in Theorem 3.3 and also in Theorem 3.6 we must bound Ha. (g). We proceed by computing the coefficients in its Taylor expansion, including an explicit upper bound on the remainder term (10). First note that using the dominated convergence theorem (see, c.g., Theorem 2.27 in Folland (1999)), it is straightforward to see that Ho,o (q) is smooth in and can be differentiated under the integral any number of times:
dt de H.. (n)
[a (a (a- )) /
1-1
N1.0=//44 (0( ( (1 -1--))
N Noo.0//(0
(N1.02//(0))
(oo02/1(0)
-1)
No. (O))d/
1=
(37)
This justifies the use of Taylor's theorem with integral remainder to Ho,g for any order m E Z to arrive at
Ho.o (g) =1+
II (a j) Mo, + Ra)ama))
(38)
k
2=
15

---

where
Ma,k == (M -1) No.o² (0
(39)
(note that the Ma, = O, which is why the summation in Eq. (38) starts at A: 2) and the remainder term is given by
S.'
(1 -1-33 s)m-1 dm (m 1)! dg H (sq)ds.
Ra =qth gTh)
(40)
For integer & 2 0, the Mo, 8 can be computed using the binomial theorem together with the formula for the moment generating function (MGF) of a Gaussian:
k
(() /
(K)
N (NNno1/100))
M
1-1) k-f
N No.o2/((0))
No,o2/a(0)d0
(41)
t=
Σ
(-1) (0)
1/120/144 /4) /
[01((02/4) N2
t=
Σ
(-1)
6 ele-1)/(0(1))
1=
kk)
11/1-1)/0? + (-1)-- 1).
t=2
In particular, M,,0 = and Ma,1 0. If a is an integer then the expansion (38) truncates at a finite number of terms (terms with are zero). but for non-integer a one must bound the remainder term. To enhance numerical stability of the computations, in practice we add terms starting from the highest order and proceeding to the lowest order.
Bounding the Taylor Expansion Remainder Term:
To bound the remainder term (40) we need bound 2े the calculation into two cases, where different methods are appropriate. Here we assume q < 1.
d"h Ha.o for 1 E (0, 1). We will break
In these bounds, it will be useful to employ the following definition for integer j 2 0:
Bos = 1
N (2 '
1
No.00/1(0)
No.o2//(O)d0.
(42)
For j even we have Bo. Mo.j and for j odd we can use the Cauchy-Schwarz inequality to bound
Bo,
M2/ Moj-1Ma M1/2
(43)
as + 1 are both even. Therefore explicitly computable upper bound for all integer j > 1 is given
by
Maj 1/2 M 1/2
if even
Baj 5
Bay
(44)
a-j-1 ag++1
if j odd
where Mo. is given by (41).
16

---

Case 1: a:a- > 0
Using the bound zamm S + + fm] for all x > 0 can compute
d Har (sq)
(45)
d
m--1
/
sq N /4(02/4(00)
[a]-m)
N |1.02/4(0)
a
أl
1+
+ (1 sq)
No,02/4(0)dB
No.
/4(0) No.02/4(0)
No.o2/4(0)
1=0
/
N N1,02 /1,02//(0) -1) +1)
[al-m m
N N1102/4(0))
aa
89
//,02/1(00)
-1 N/,02/1(0)
No,0z/1 Ba,m
m-
[al-m Σ
[[o|] m
N1.02/100)
1)
(sq)²)
(46)
No.02/1(0)
j=0
N /4)))/((0)) -1 No.o2/a(O)dBB + Bo
x
No,02/1(00
[a] m m
[[a] - m
a jl
Σ F=
(sq)* B. B. + Bo.
1=0
Therefore
(47)
m
m
a
5|
[a|
Σ
[a] m ) Boottm S'"
(1 (m-
s'ds +
1
B Bo,
(m 1)!
m!!
j=0
1=0
[a]-m
([a] [m]
1
m
a
jl
Σ
Baeem Bo,m
([a]
m f)1(mn + 8)1
me!
5=0
Case 2: m < 0 In this case we have
N2, 22/02/1(0)
+ (1 (1-ss)) sq)
a-m
sq
No. 2/102/1(0)
$ (1 am
(48)
and therefore
dm dgm Ha (sq)
5 (1- 9) a-m
aa Bo,
(49)
This leads to the following bound on the remainder
RR.oom (g)) 5m [.
(1 - 8)
1
(1 9)
ja B Bs
(50)
(m 1)!
1=0
9" m
m-
④)
a
a jiBoom
(51)
mn!
1=0
where Ba.m is defined by (44).
Explicit bounds for 3: We find that 3 generally yields sufficiently accurate bounds. Here we specialize the above results to this case. For q < we have
q² a(a 1)M.2 + Ra,a3(9)
Ho,o (g) =
(52)
2
17

---

with
fal-3 3
1==0 o [1a -31 Ba Ba + bB,3
[Ta] -31-
if 3>
Ra,0,3(9) s q² - 1)/a - 21
[ 9)
a- Ba,3
-
(53)
This completes the proof of Theorem 3.2.
To illustrate the use these bounds, and the fact that m = 3 is often sufficient in practice, in Figure 6 plot the FS bound from Theorem 3.3 (which uses the expansion and bound (52) (53)) for one step (i.e, 7 = 1) and with the parameter values o; = 6, B = 120, and |] = 50, 000. Note is negligible over wide range of
that the difference between the bound for 3 and
(sufficient to cover the default a range needed by Meta Platforms (2024)). The value of in this example is far from being unrealistically small; smaller values of q will only make the effect of m even less important. Therefore m 3 is generally sufficient.
One-step FSwoR-RDF RDP Bound (alr)
Thm.3.3 bound
Thm.3.3 upper bound (m 4)
10
20
50 60
Figure 6: One step Theorem 3.3 for m = 3, 4, using the parameter values o; 6, |B] 120, and
D 50, 000.
C Proof of Theorem 3.4: TSwoR-RDP Bound under Replace-One Adjacency
We now prove the FSwoR-RDP bound under replace-one adjacency as stated in Theorem 3.4 above. Without loss of generality, derivation shares several initial steps with the add/remove case from Appendix A. Specifically, we apply Lemma A. to the transition probabilities for one step of DP-SGD with FS "SwoR-subsampling both for D and for D' (as they now have the same number of elements), to obtain
assume that / and D' share all elements except the last. The
Pe (e(004200,, D) = =E (B
JNN ne (..,,b (0.+1) + (1 p. (D),...
Pr(0.+1 D') =E 1) B)
qN (. (0.+1) + (1
(54)
similarly to (24). Now again use quasiconvexity, this time in both arguments simultaneously. bound the effect of the mixture (expectation) over (b' b) by the worst case, yielding the one-step Rényi bound
Da (p(0:+110,, D) D')) < max D. (qQ; + P + (1--1(1)))) 9)P() (55) (6)))
2; N 11000,01111-11100..33 0 = N ",00,,.0(1000000000...
Pe. == NA.0....).a :) Pr = Nu.(O..
18

---

Using the fact D and D' agree on the index minibatch 8' and hence (b, D/ D) = pe 8' D"). we see that Ps. pa. We can therefore change variables to center both of their means zero, giving
Da (v(00++110 ()+ D'))
(56)
max Da Am (),07 + (1 4) N,,0, 5,, + (1 g).o,,z))
(v/b6)
Apa(b', b) == (1, (1D) 13, 1), Me(0,, b', D),
Apt(b', b) = 14 (0,, b (IDI - -1,, D') - (e b' D).
The means of the Gaussians satisfy the bounds
AB Ti S... res | S., [lp((,, Apt(b', rr.
(57)
where Te was defined in (29); the first two inequalities follow directly from (28) while the proof of the third is almost identical due to and D' differing only in the last element.
Remark C.I. Note that, similarly to Remark A.2, Eq. (56) remains true when the Rényi divergences Dr are replaced by any other divergence 'D that is quasiconvex in both of its arguments, e.g.. the hockey-stick divergences. This fact is useful for other differential privacy paradigms, though using the quasiconvexity bound does always lead the tightest possible bounding pair of distributions; see Lebeda et al. (2024).
The key difference between the bound (56) and the corresponding result (26) in the add/remove adajcency case is that both arguments the Rényi divergence on the right-hand side of (56) are now Gaussian mixtures with mixing parameter q; in the add/remove adjacency case only one argument is a Gaussian mixture. This difference makes the following computations more involved, though the same Taylor expansion technique can be applied.
Using the definition of Rényi divergences we can write
Da (9N (gN + (1 - N).No.;; 11 An:( + (1 -.)...))
1
log [Fa
a
(N. (A 3) (0) + (1 N) (0) (8))
Fa(g)= =
(58)
( (0) + (1 - N) (0) a-
Next we Taylor expand the argument of the logarithm:
d dt
Fa(g) = Σ
(0) + Ea,m (4),
(59)
kd dg
k=0
where here the remainder term is given by
En.m (4) = =m S/ (1- (1-s)m- m- d
(m 1)! dam Pa(s)dds.
(60)
Using the formula d² justify differentiating under the integral, the derivatives be computed as follows:
de-s de (f9)= Σ (2) d f dok-s 9 along the dominated convergence theorem to
d
Fa Fa(9) d
(61)
k
II (a 0) E=
-o) /
II (II
(
(ト-jー) (1 (1-a a
(NN (oVAmi D) D),09 (0) + (1 -) (1.
(NN ") (1 g).No.z7
a+h-j-1
1=0
E=0
(Nsm..e. No.x;(01)² (N (NA No.=;(1) k-j d0.
19

---

Taylor expansion coefficients for k = 0, Evaluating (61) at q = 0 we have
d dgh
(o
(62)
[a(a- -0 o) ( (a (a+te-1) (T(( (NAmit.B),,3(0)) /
Σ j=0
h (-1)
(3)
[II f0
-1) R-j (0) - () b), D) (0))Noo0 (0) No.5z (0)
Note that we have not yet been able to maximize over by doing so while incorporating the constraints (57) is nontrivial and constitutes one of the the primary difficulties in obtaining sufficiently tight bounds. We will make particular attention to the first few terms and then use looser (but still sufficiently tight in practice) approximations for the higher order terms. First note that F. (0) 1
and
d Fa(0) - -0 -a 1 NN (NAu(U No.,,(0)) d0 dq
(63)
+ / (N (o,0 (0)) do = 0.
For we can expand (62) and then evaluate the integrals by using the formula for the MGF of Gaussian to obtain
d²
(0)
(64)
dgp
(b, (1) oi
Apt(V, b)
A4 )
=a(a- - 1)
exp
+ exp
2 exp
Using the third constraints Eq. (57) we obtain the bound
Ab, b) Apt(b'
exp
(65)
o7
|| Apn(' 10', 8)112 12 + 11444 D)11 (K..) (4(,,D))1
exp
207
Abu 12 + A1444 (.D6111 -r?
2 exp
207
Elementary calculus along with the bounds (b (V/ ..]1 S Tr. A1 (V,(),))) b)]l S r2 then imply
d²
(0) $20(a 1) - -22/2200)) = 20(a - 1) (e//0²² 21
(66)
2g²
where we used (34). These terms are sufficient to precisely capture the leading-order behavior.
Bounding the coefficients for k 2 For the higher-order terms we obtain an upper bound which relies on the following lemmas. It will be useful to phrase various bounds in terms of the x" divergences.
Definition C.2. For 3 >> 0 define the x divergences
x (Q) P) Er ErldQ/dP- 1
(67)
will also be convenient to adopt the notation D2" := 1, despite not defining a divergence.
The following property is imply consequence of Hölder's inequality.
Lemma C.3. Let 7 2 B > 0. Then
D (QIIP) < 8/1
(68)
20

---

The next lemma will be used to obtain a uniform bound, i.e., not dependent on 8' b, or 0,.
Lemma C.4. For k 2 0 an integer we have
max
x**
(NAm.cV.)) (1 I Book
(69)
max x* (Nopice by Aw B),07) S Baoks
b
where B was defined in (44). These bounds also hold with Auy and Ap4 interchanged.
Proof. Duu the I divergence corresponding to fa(v) = ly - 1 therefore it is jointly convex in (Q, P). Therefore the same argument as in Section 2 of Mironov et al. (2019) (which only relies on convexity of the divergence) implies
x (Nami (1.033)
Sxxx (Nr.0ellNo.s))
(70)
xxx= W1
Bock Book:
where we used (57) and (44). The second result in (69) is proven in similar manner, where we must also change variables center the second Gaussian zero and then employ the third bound in (57).
The second lemma we require is slight improvement on Lemma 24 of (Wang al., 2019).
Lemma C.5. Let p, r be strictly positive probability densities and k 2 1 be integer. Then
/
(()) (M00 r(0)
(m())-((0) r(0)dB
(71)
<Px((1lpp) + Dx* (pllg) + D Px* (pllr) + P2x (allr)
if k is even if k is odd
Remark C.6. Note that key difference between our technique and that of Wang et al. (2019) is that only apply Lemma C.5 to the higher order terms (i.e., when k > 2) while we bounded the leading contribution (66) more precisely. In contrast, Wang et al. (2019) used Lemma C.5 (their Lemma 24) on all terms.
Proof. We proceed by breaking the domain of integration into four regions, depending on the sizes of p, q, and then use the appropriate bounds to replace one of the densities with another:
(()) (())
r(0)do
(72)
r(0)
= =/
(p(0) -()))*
(p(0) 9(0)**
do
r(0)k-1 d0
r(0)k-1
repaz2
(p(0) (0))
(p(#) q(0))* r(0)k-1 d0
d0
r(0)--1
Ip(0) - (0)
Ip(0) (0)
d0
d0
p(0)a-1
q(0)=-1 k-1
r2p
rrppr22
Snepercaaz
((())
d0 -(0)--1
if l: even
(p(0) - r(0)*
r(0)6-1 d9
Jreprcegep
if l is odd
(p()) (8))
(p())
a (0) d0
p(0)-11 d0 (Q(#) r(0) (0)=
d0
if is even
+ /
(p(0) r(0))*
r(0)a-1 d8
if is odd
This completes the proof.
21

---

Lemma C.7. Let $1. > 0 with 81 + 32 and integer. Then
/
|Naauio 8).03 An (0)/No (,,00,0)),,,)))N))))))
(0) - 1 10)
(0)-
-1/² No.oz(0) (0)d0 (73)
max H,b
N
<Bor.i+t22> where Bo, was defined in (44).
Proof. Let p.g > be conjugate exponents, i.e., they satisfy 1/p + 1/9 = 1. Using Hölder's inequality we can compute
f NAm (0)NNo (0) - -1) |N"" (Ann(0 (0)NNo, (0) -1 11/ (0) (74)
(0)) -11")
SDx0r (Nami D) I1 (l,
1/8 Depze (Nou((U 3).07 (I,o.)))
1/9
We now use simple heuristic that allow for p, to be chosen so as to minimize the right-hand side of this upper bound when $1, 32 are large. Lemma C.4 together with (44) and (41) suggest that the two factors on the right-hand side approximately behave like exp (2p3// and exp(2g82 respectively. Therefore, to make the upper bound as tight as possible, we want to to minimize p.f + 88 subject to p > 1, q p/(p - p = + 82/ 31. 9 = 1 + /2. Making this choice, using Lemma C.3 to convert to integer orders, and then employing Lemma 69 find
1). 1). Simple calculus shows that the minimum occurs at
32.
/ N b) (0) (0)/No,z (0) 1 |
N AA 3).0 (0)/No.z 11 No.5z(0) (0) (75)
B2
9//Tapp Dyirzal (N (N by ll
SD Sxnman
s <Boo.1spp1) 99/T8rr) (Bor.1991)
92/[800l
In the case where 31 + B2 is integer the above can be simplified via
82/[829] (Bo. 91/18pp (Bor.192a)
Bo,.B.+02
We use these lemmas to bound the higher order derivatives as follows. First rewrite (62) as
d
(0)
(76)
dat
d
kK)
=(a - 1)aa k1
1)
k-
1=0
(N
(), (0) ()ooi)),,,,00)/ooo.. (0) - -1) (N (N (0) -1)
No.o; (0)d0
+ (a 1)a*=1
1b a
I[a-e/ e/m))
II
(1+ (1+(( (t (4-1)/)))) -1
- 1==
E=0
x (NArit (0) No.; (0) - -1)" (O'N (NAr(( 6) (O)/No..: (0)- k-j
(o)a
=(a - 11 / ( (Na 3). (0)/No, (0) - N A ,. 00) (0) (0)) i No.zz(0)dB
4
+ (a 1)a k-
Σ (11
1 a
[[a-e/a)
(1 (t (4- 13//o) (6-1)//0) ) -1
II
-
(==
E=0
(Naaalle (0)) (NAm)(0,)00
k-j
No.z; (0)a0.
22

---

The first family of integrals can be bounded using Lemma C.5 and then Lemma C.4 to obtain
/ 4Mo..k
&
AppiCo 3p (0),
N Ao (.pt0/.B. No.0z (0)d
(77)
if is even
if is odd
The second family of integrals can be bounded by using Lemma C.7 (when j, -j > 0) and Lemma C.4 (when j = or j = k), which yields
/ (0))),) (0) (N)
(0) k-j No.zy (0)d0
(78)
< &Back:
Therefore we find
d Po dg
(79)
4Mo.,
if & is even
S(a 1)aa
3M
or,k-1 1 0.,
M 1/2
if is odd /-1
k
(K-j-1
+ (a - 1)0 k-1
II f/a)) E=
II t=
(1+ (e (e((e1))a)) 11/0s) - Book
==
=Fa,ockk
(80)
where M and B are given by (41) and (44) respectively.
Bounding the remainder term: We now proceed to bound the remainder term (60). Using (61), for
q < 1 we can compute
1/'
(1-8)m 8) m-1
d
Ea)m(1))= S Tm
dgm Fa(sq)
ds
(81)
(m 1)!
m-
Sq
m
la el)
II (a (a+
1=0
==
(sq.V An 37 (0)/N, (() (0) + (1 - (q)
a-j
(1 - 5)m-1
x
(m - 1)!
a+m---I
0
SqN Au( 37 (0) 0.07 (0) + (1 sq)
N NAA 3),07 ()).))))(((0N...... (0) | N NA 3).07 (0)/No,z((0)) -1 1m-3
No.3; (0)
m
9T
(1 9) (a+mm-i-1) m
a el
(a K Ka,m)(9), F=
m! 1=0
Pm
Ka,m.i(g) = m //'² 1) s)m /( (SqNN Ap (b),), b) (0)/No, (f) + (1 (qs
(1-1))-
N (A 5) (0)/No. (0) - 1" (N M) (0)/N (0)
m m-
No. (0)ddss,
where obtain the final inequality we used the fact that m j j and
sqN A 5),,, (0)) (0)/N,, (0) + (1 sq) 2 q.
(82)
to upper bound the reciprocal of the denominator.
To bound the integrals Kamm, we consider the following two cases.
23

---

Case 1: a -j-j S 0: In this case we use
s An. (b) 8) (0)/No,, (1 sq) a-j
S (1-9)
(83)
bound the first factor in the integrand. Then, using Lemma C.7 and Lemma C.4, we can compute
Ka (m.mm.(9 (g)
(84)
<(1 - 9)003/ / IN Namii
1"
(0)d0
5(1 - 9)0-31 Bo
Case 2: a jejja >
In this case use the bound 0a-1 < 1 plll- for all x 0, followed by the binomial formula and Lemma C.7 to compute
Ka.ma (1) S m (1 (1-s)m-) /(1 (( s8g AunNAnc Apr( ()) (0) + (1 - (1-x4) aa
(85)
x Am b) (0) (0)) - 11/|xx I B), (0) (00) - m-j
No. (0)d0ds
m- - N (tr 5) (0)/No. (0) 1 1' N NAui(U D) (0)/No,=;
No (0)d0
[a]
Σ of [aa] (1a) 8 1)) / (1 -s) (N (0)
(0) 1) R
+ m
-10 11/ (340 -1
m-j
x
Abe 3) (0)/No,= (0)
No.0; (0)d0ds
[al-j
([a] 5}mm!
<Bo.
Σ
[Ta] - j- - 1) + E]! etm.
Putting the above two cases together we arrive at the remainder bound
Ema, (4)l S nm 1/" (m - 1j!
(1-s) m-
dm Fa
(og)
ds
(86)
dgm
mn-j1
7
(1 ④)
(m- m
a -e-ee el)
II (a [I F=
m!!
1=0
A=n
a)a= Barm
if faajs50 i50
Borm + Elal-1 o [Ta (1) +2) Bo L+m
(Ia - plmm
if j>
=Fa.
(87)
Combining the above results, obtain the following FS cency:
RDD bounds under replace-one adja-
sup
(88)
0.
log 1 + saa(a 1) (64/m9-22/11 + Σ Fao + Ea
k!
(4) is given by (87); both of these where 2 3 is an integer, Fa.ar is given by (80), and Ea, quantities are expressed terms of M and B, as given by (41) and (44) respectively. This completes the proof of Theorem 3.4.
Remark C.8. The same M's appear many times during in the formulas for Fa. J and Fo (g). Therefore, in practice, compute all required values once and recall them needed.
24

---

C.1 Comparison with Poisson Subsampling under Replace-one Adjacency
In this appendix we provide a precise comparison between RDP for fixed-size and Poisson subsam- pling under replace-one adjacency, complimenting the intuitive discussion in Section 4.1.
Here we Iet p p (0.+1 [0,, D) denote the transition probabilities for one step of DP-SGD with Poisson subsampling. By Mirroring the analysis in Section of Mironov al. (2019), but now under the assumption that D and D' have the same size and differ in only their last elements, we arrive at the one-step Rényi divergence bound
Da (ppoisson (0c+1 (0c+1 D) Poisson
Poisooo (0t+1 (0,, D'))
(89)
S T Da (T)) (1 N) Nl ( + g).o
(T) He(0,, U [ -1, -r((,,, D),
(p)(T) pu(0,,T ( D') 1u(0r, T, D),
where 7 denotes the collection of indexes from (0,....11 [D] - 2} that were randomly selected during Poisson sampling.
This is similar to the result (56) for FS Subsamuubs,,,inng except here the means satisfy the constraints
(T) S r./2, |A S r./2, (T) AP((T) rz.
(90)
and these bounds are achieved when the differing elements from D and D' are anti mnt-pparalll and saturate the clipping threshold C. As we will show, this difference only contributes higher order.
We now mirror the analysis from earlier in this section, taking the new constraints (90) into account. We again have Taylor expansion of the form
Da ( (NNAp(())) + (1 - 2) llell11 A + (1 2) N).
(91)
1
log
r dh kt dg
Fa + (g)
(92)
The coefficient at h 2 can be computed as in (62), which gives
d²
(o)
(93)
dg²
|| 07
(TA - 2expp o?
Aui(T) (A)()
=a(a-1) -1)(exp
exp
+ +exp
22
<2a(a 1)
1/07 - -1/07
This bound is optimal that equality is achieved when the distinct elements in D and are anti-parallel and saturate the clipping bound. To leading order in 1/0ł therefore have
d
Fa < 4a(a 1)/oł +(1/0))) dy²
(94)
which agrees with the leading order behavior of the corresponding term in the FS -suasamplbbagggg case (66). As the second order coefficient in the Taylor expansion controls the dominant behavior of the RDP bound, we can therefore conclude that Poisson and Subsamibs give the same DP bounds under replace-one adjacency to leading order.
Our method for bounding the higher order terms, as in (80), and remainder, as in (86), only uses bounds on the norms of Ajr' and μ ; it does not incorporate the bound that couples these two quantities. Therefore the corresponding bounds on
higher order terms for Poisson subsampling are obtained by simply replacing r with r in our prior calculations; this is equivalent to replacing a, with 20; in (80) and (86). Therefore we arrive at the following non-asymptotic bound for Poisson subsampling under replace-one adjacency.
25

---

Theorem C.9 (Poisson-RDP Upper Bounds for Replace-one Adjacency), Let D -nio D' be adjacent datasets. Assuming 9 = |B|/|D| 1, for any integer m we have
sup (p Prissoy (0++ (0+ D) 6.
( (0+1100,
(95)
m-1
5 log 1+ 1+ (1 -E -
Fa,2... + Eo 20.00.m
where F 2a and Ea, (g) are computed via (80) and (87) respectively (with replaced by 20,).
While our and Poisson-subsamplee RDP bounds agree leading order, the effect of the higher order terms leads to Poisson subsampling having a slight privacy advantage over FS weoo---ubsampling in practice, especially when larger a a's are required. This proven in Figure 7. where we see that the upper bound on Poisson-subee -usssoslu RDP (dashed line) is slightly below the theoretical lower bound for S5ooR-uubsampee bound from Theorem 3.4 (solid line) is slightly above the theoretical lower bound. All three are significantly below the upper bound from Wang al. (2019) (dot-dashed line). We emphasize that the Poisson result does not contradict the lower bound from Wang et al. (2019), which only applies to FS wo subsampled RDP.
RDP derived in Wang al. (2019) (circles) while our Fo
One-step RSWOR-RDP -WORRRDDP Bound (r-o)
FSwoR upper bound (m 5)
Poisson upper bound (m
6.6
Wang et al. upper bound
Wang bound
0.2
Figure 7: Comparison of our FSP and Poisson- RDDP upper bounds under replace adja- cency, Theorems 3.4 and C.9 respectively, with the upper and lower bounds on FS RDD from Wang et al. (2019). We used a; = 6, [ 120, and [] 50, 000.
D Rényi DP-SGD Bounds for Fixed-size Subsampling with Replacement
In this Appendix we provide a detailed derivation of Rényi DP-SGD bounds when using fixed-size subsampling with replacement (FSwR). In addition to the lower bound stated in Theorem 3.7, we also derive an upper bound.
As in without replacement in Appendix A, key step is decomposition of the sampling distribution into a baseline (where D and D' agree) and a perturbation where they disagree. The derivation for subsampling with replacement is non-trivial generalization of sampling without replacement, with Lemma D. below requiring a several key new ingredients, as compared to Lemma A.I.
First let D' be obtained from D by removing one element. Without loss of generality, assume it the last (i.e.. at index |D 1) and call that element d. Let B' (B,, BB))) where the components iid Uniform( (0, .... DD 1}} random variables, so that B' uniformly samples from {0, .... DDI- with replacement. Now let N ~ Binomial( B | and II be uniformly random permutation of (1, ..., [B). Assume that B', N. and II are independent. In the following lemma we show how sampling from D with replacement can be obtained from B', N, and IT. In short, N will determine the number of entries of B' are replaced by [D] and IT will determine the indices of the entries that are to be replaced.
26

---

Lemma D.1. For = 1,... [B] define
[ -1 B
ifTT(j) = for some j S N == =B, NII.)
B.
(96)
otherwise
Then the B₁ itd (niform((O,.... -1111 13) random variables, i.e,, B = (B1. my B(B)) uniformly
samples from {0, (0,....11.. [D] 1} with replacement.
Proof. Let b E {0, .... [ - 1/1l and define n = [i: b, = |
11 Let fi,,,.. in be the unique indices with by; D 1. If B b then must have N n, therefore we let Sn denote the
of permutations on {1, [1,..,)) m) have
P(B = PB b, N (II(1) [[n)] in))
(97)
Σ
P ( b, for i o
n, (LI(),. = (I,())...,, d(m)))
TES
Σ P = by for i (i....., In = (I.()).... (i+(2) ... br(n))
TES..
Using independence and that D = |D| and |S = no! we can then compute
P(B = b)
(98)
Σ TES
II
P( = b.))
P(N P(B(=b.)
((T(1), [[())) = (1,(1))...,7 kr(m))
(1B1) DI DD- |D| - ( n)!
Σ
D ((BB))
n2
B
TES,
[B]
[B n)!
=n! D
[
B
=|D|-181
This holds for all b, therefore
conclude that the distribution of B is the uniform distribution on (0, (0,....14) [D - 1) All the remaining claims then immediately follow from this fact.
Using Lemma D.1 we can decompose the transition probabilities for one step of DP-SGD with FSwR Suws-uubsa as follows
/ N Nu.0,,, (m100)..),,(((0--11)pp) (db'' (db'd)).
(99)
pr(00(+100r. = / Nur(e. (d.e
(100)
[B]
= -/Σ
B
D "(1 1D1 NN ow. (ar,n(db'dd
n
Noting that (r b', D' ue (0,0', U, D), as D' differs from only by removal of the element, we now use quasiconvexity compute
Dalpe(dDe+ 10,, D) 10,, D'))
(101)
B
B
< max Da a.
Σ
D (1
|D] 1D "N N0.00.000..m)))) NM D).
n=0
Remark D.2. As in Remarks A.2 and C.I. Eq. (101) remains true when the Rényi divergences D,, are replaced by any other divergence D that quasiconvex both its arguments, e.g., the hockey-stick divergences. This fact is useful for other differential privacy paradigms.
27

---

D.1 Upper Bound on FS
The next stages in the calculation are more complex than in the case of sampling without replacement, as the first argument the above Rényi divergence a mixture of B + 1 Gaussians, as opposed to simply two as in the case without replacement. This is because the binomial random variable N in (D.1) is playing the role that the Bernoulli random variable J did in Lemma A.I.
Start by rewriting Eq. (101) as
(d(p((d0:+1100 (1100 D))) S max Dr
Σ On N A o8 No.oz
On - 72
((11)) DI "(1 -1-1D-1))111 Ayp, = pele,, F(b n. R). D) (4,, 8. (,,,,, (102)
Let K S [B], choose 7 satisfying
1+ ag
(103)
m== On
and decompose the mixture of distributions as follows
[BI
Σ
an N Apm.
No.
+
an N Apn
Σ
ag N Nanni?
(104)
n= K+1
~ 0. +
On @ ANa
+ (1-
Σ =+1
an Nn Ap
K
8o = 00 (1/Ā 1)
Σ
On on = an/ō for 2 1.
The assumption (103) implies a. E [0. 1] and To + Ex= "n + >n=K+1 On = 1 and therefore we can use convexity to bound (102) as follows:
|B
(pr(0e++111 00, (301p((00++111))), D'))
(105)
K
On /
N NAun..p(0) (p()
+ (1 ((1-7) )) No.zz (0)a0
< max 8x
log
+
1 No.o7 (0)
0
n=1
Σ an /
(Naun
N
No.z;(0)d8)
(0)
n=
K
N1,o;/(Ane) (0)
<
log
0g
On
q No.o (1n))) No.02/(An))(00
+ (1-1)
No.o2/(nn))000))
n=1
[8]
Σ
ane 20 1)02/1/0//0
+
n K+1
[B]
log 0g
Σ
a
H Ha /
(
Σ n=*+1
a 23aa-11n3//3
0
where H was defined in Eq. (8) and be bounded using the techniques from Appendix B. Now suppose D' is obtained from D by adding one new element. By reversing the role of D and D in Lemma D.I and then mirroring the above derivation while also employing Theorem 5 in Mironov
28

---

et al. (2019) we arrive at
Da (p
(d D))
(106)
a log
a H 00.0///9 +
Σ
d e 20(0-11n2210
B
d
D2 n (1 1011-111118
0 = dj (1/q - 1) Σ an कn = d n
n=
whenever satisfies (103). Note that (103) also implies
d
z
1+ K
ΣK
Exm 0l2
(107)
due the fact that ag is increasing in [D] and an decreasing in D] for 2 These properties also imply
do H
Σ
e
2a(a-1)n210
(108)
n=K+1
[B|
ag H (n
Σ
ag 20(a-1))2210
K+1
and therefore we can conclude that
Da Da(Pe(d0(+1
(0,
D'))
(109)
K
- log
ao + an H
Σ (a
+
Og 2a Bala-11nn//e
a -
R=1
n= K+1
whenever D' 2a/r D and any choice of that satisfies
1+ ao
1 12 12
(110)
n= On
Note that if one chooses 7 (1
then āo = 0. If one also takes K |B] then
an
q 1 (1 11)18, This is the version of the result we present above in Theorem 3.6.
D.2 Lower Bound on FS
Here we derive lower bound on the one-step RDP of SGD with fixed-size subampling with replacement. To do this, suppose that all entries of D' are the same, equal to d', and that the extra entry d in D satisfies d + d'. Moreover, suppose there exists 6, such that the clipped gradients at d and d' are anti anti-parallel with both having norm equal to the clipping bound, C. In this case, (4,,, V, D) and (0,, (VV. n, n), D) are independent of both and D/ and
(0, B. D) pl0r. (b' n. n) D)Ll nr:
(111)
29

---

This also implies that (101) is equality (and the argument of the divergence is independent of R and T). By changing variables and using (111) we can therefore write
Da (pe((drr pe)
(112)
131
B
max Do b,
Σ
|
D
No.77
n=0
B
[181]
=aa
Σ
11-1111111111111-111111111111111
Nnr 53 No.37
n=0
B
[B]
=a
Σ
"(1 DD 11
No.02/4
n=0
This gives the one-step RDP lower bound
a
4(a)= a-1
1
log /
Σ
[ n
D (1-
(DI1)B
No. (0.07/1(0) (1.07/1(0)d8
Nn, //(())
(113)
The integral over can be computed as follows. First note that summation in (113) is the average of (1), /40))/((()))) under the Binomial distribution Binomial([B). | |DI As convenient shorthand we write this average as f .n.dd. With this notation, for integer we can rewrite the
argument of the logarithm in the lower bound (113) iterated integral, then exchange the order of integrals and evaluate the integral over using the formula for the MGF of Gaussian as follows
B n
11- Nn,o//4(0)
DI "(1
-1-11111)
1DI1))81111----
No.o2/a(0)e)
(114)
No.02/1(0)
N //100/1100))))
dn No
No.o (0)
E. / (2)+0 ai/(o" (o N No.o? (0)dn
Eies nin, dn d
(115)
Therefore we arrive at the lower bound
(aa) 2 log /... 1 Eies nons dnn...dna
(116)
Recalling the definition of the dn, 's, this completes the proof of Theorem 3.7.
The lower bound (115) behaves somewhat differently from the one derived for subsampling without replacement in Wang et al. (2019) and restated in Appendix F.2. In particular, note that the explicit |B] and [D] dependence in the lower bound (113) cannot be removed simply by reparameterizing the expression in terms of q / In contrast, the FS lower bound in Appendix E.2 depends on [ and [] only through g. This fact can be further illustrated through simple loosening |B]
of the bound (113), where we bound the sum below by the term
to obtain
N (NBI,77/1(0) 1
<((a)
log
DD-aal
No.o2// (4)))//(0))))
No.oz/a(0)d0)
(117)
a
a: B
(2 B (a 1)/0; - log B log(1/q))
a
For fixed ratio == BB] the right-hand-side of (117) approaches xo as B - oo. Therefore we conclude that (a) has nontrivial [B] dependence, even for fixed g claimed. This accounts for
30

---

One-step RDP Lower Bound
10
10"
d=3.0
16-7
0=4.0
10-1
6.0
100
175
[8]
Figure 8: FS lower bounds as function of [B], with 2 and q 0.001.
some of the difference in behavior between fixed-size subsampling with and without replacement. This behavior is also illustrated numerically in Figure 8, where show the exact value of the lower bound (113) as a function of [B] for a = (this case is straightforward to compute via the binomial theorem and MGF of Gaussian) and for fixed & 0.001; show results for several values of Note that initially each curve starts out horizontal, mirroring the case of FSwoR-RDP. which has no [B] dependence outside of q. However, for each there is threshold value of B] which there is "phase transition", i.c., after which the explicit [ dependence becomes important and the RDP value increases rapidly.
D.2.1 Comptutable FS Lower Bounds
When a is an integer the lower bound (116) can, in principle, be computed exactly by recalling that the integrals with respect to dn; are shorthand for the expectation with respect to the distribution Binomial(B: B, [D] -1). Therefore the lower bound (116) consists each. Clearly, when is larger than 2 and [B] is not small iterated summation this quickly becomes computationally impractical. The looser lower bound (117) is easy to compute, but is much too inaccurate for most purposes. Here, for integer a, will show how obtain lower bounds that are both practical and significantly more accurate.
nested sums |B] + terms
Recall that the integrals with respect to the dn's are actually finite sums, each over B + +1 elements, and in principle the above expression can be computed exactly but still practical. We next show how to obtain recursively defined lower bounds that are significantly less computationally expensive than the O())() computations that the more naive formula (116) requires. begin, any integer k 2 2 define
f eres ). ain dnng... drg...dn..
Folc, d)
(118)
For we reduce the computation single summation by using the formula for the MGF of the Binomial distribution:
B
[BB]]
F2(c,
Σ n=0
DI
-0 - + + (119)
31

---

For h > 2 we explicitly write out the integral over n as summation and then simplify to obtain
Fa(c,d) d)
(120)
- -1...
( 1 mon ni
elo metd d
18|
>
[B]
D - (1 1-1-111111110111 cr>sted 2n miny mny Itsl "i el elo2iut midd)n d
1BI
(11B))
[DI- 1DI111111111-00 f.n Tnied Ei nnyy Eisl "dd--11.. dni
[8]
[BB]]
(1- 1 F Ic, en).
0
As stated, the recursive formula provided by (119) and (120) is still too computationally expensive due each recursive call requiring the summations over [B] elements. However, noting that terms in the summations are all positive, we can obtain a practical lower bound by retaining only small number of terms. More specifically, given choices of Ts C [o, ..., [B]] for each k, if recursively define
(
[B] n
Pr.((,,)== = Σ
D - du Fx-1(c, d on,
(121)
nET
with
BB]
Frz(c,d) d) = Σ
DI -11- (1-1)-))-1 011 DD 1
(122)
nET,
Then, by induction, we have (c 2 (T, d) for all k. T, c, d and therefore
((a) 2 - Fr. (4.
(123)
for all and all choices of Tu, k 2,... a. By appropriately choosing the number of terms Tk for each one trades between accuracy and computational cost. In particular, each [Txl 1 then the computation of (123) only requires O(a) computations. If [T'l é > 2 for all & then the computation of (123) required ( computations. In contrast, using the exact recursive formula (120) requires D[[B|=1] computations, which is intractable unless or B is sufficiently small. However, despite this improvement, we should note that computational difficulties persist for cases where the number of nontrivial terms is too large.
In our experiments in Figure we find that that using Tj = B for 1: > 2 and T2 {0, .... [B} gives an accurate and computationally tractable lower bound. In the example in Figure more terms were required; we show results obtained by using Tą = {0, 1, 2, [B for k > 2 and T2 = {0. BI}.
D.3 Comparison of Upper and Lower FS Bounds
Now we will compare our lower bound for FSRR-RDP from Theorem 3.7 with the upper bound derived in Appendix D.I. In Figure 9 show the FS upper bound (solid line) and lower bound (circles) and, for comparison, we also show our bound on FS (dashed line). Note that all three are very similar when is close to this is be expected, due them having the same leading order behavior in g. given by (19). However, as a increases the non-leading order behavior becomes more important and we observe that, after some threshold a. both the FSW upper and lower bounds increase rapidly. A similar "phase transition" was observed earlier in Wang et al. (2019) for subsampling without replacement, though for these parameters it occurs at much higher values of a. A key difference between these two cases is that, for FS the phase transition can be brought on by increasing [B] while leaving q / fixed, as demonstrated in Appendix D.2; see (117) and Figure 8. In contrast, the lower bound for FS FS RDP from Wang et al. (2019) depends on B and [D] only through their ratio q. We anticipate that the gap between the upper and lower bounds on FS in Figure 9 could be reduced by using higher order expansion in q, but we leave that future work. We also emphasize that the dashed SSORR-DD upper bounds is only for comparison purposes it does not apply to the case considered in this section.
32

---

10r
One step RDP Bound
Fr A3P R.P upper bound
10"4
ADP lower bound in - term)
F5net-RDP RDP upper bound
10
Figure 9: Comparison of our upper and lower bounds FSwR-RDE from Theorems 3.6 and 3.7. We
used a, = 6, | = 120, and |D] = 50, 000.
E Comparison with Wang et al. (2019)
In Wang et al. (2019), Rényi-DP enhancement of fixed-size subsampling was analyzed in framework that applies to arbitrary mechanisms. In this appendix specialize their results fixed-size subsam- pling DP-SGD with Gaussian noise. This will facilitate comparison with our results. Specifically, we will show that our specialized method results in a factor tighter bounds by approximately a factor of 4.
E.1
Upper Bound from Wang et al. (2019), Theorem 9
For integer 2, the following the general fixed-size subsampling Rényi-DP enhancement bound (for one step) was derived in Wang et al. (2019):
(() x Ki(a),
(124)
2q 1) (l--))e
(i(a) log
+ 24 ()(c(1(2) -1
Σ j=3
(if & 2 then the empty summation is interpreted to be zero), where ( denotes a Rényi-DP bound for the mechanism without random subsampling. For DP-SGD we have
j1lu - nll?
2jC² n
2j
D3(N az
(125)
207
B
20?
o
and therefore can
2j 4 = of
(126)
Note that (125) uses the same bound on the means that we use in our method, and therefore (126) will yield fair comparison. Comparing the leading order behavior of (124) with the leading order
behavior of single step of our result in Theorem 3.3, we see that our bound is smaller by a factor of In practice we find similar behavior even when including the higher order terms; see Figure 2.
For non-integer a 2 2 they use the following bound, which follows from convexity of K2(a) in az
1 1- (a [a]) Ke((a)) a
|a]
<((a)
Kc(la] 1),
(127)
a
where
[x] denotes the floor of For a E (1, the convexity bound is
<(a) < a K2(2) = K,(2)
(128)
which simplifies to
{(a) {(2), (L,2).
(129)
33

---

E.2 Lower Bound from (Wang et al., 2019), Proposition 11
general lower-bound on fixed-size subsampling enhancement was also derived in (Wang al., 2019); we repeat it here for convenience. For integer a 2 2 they show
<{(a) a
a log(1 9) +
log 1
-
(99 9 11-9)
) )
(1-1))((1)
q
j!
==2
(130)
where (f) is again given by (126). In Figure we demonstrate that result is very close this theoretical RDP lower bound.
E.3 Comparison with Replace-One Adjacency Bounds in Theorem 3.4
The analysis in Wang et al. (2019) is done under the replace-one adjacency definition and is therefore directly compatible to our Theorem 3.4. Section 3.4 we showed that our replace-one and our add/remove adjacency results, Theorem 3.4 and 3.1 respectively, lead to the same RDP bounds to leading order in y and 1/02, including the factor of improvement over Wang et (2019); this confirms that the improvement made by our approach is not reliant on the adjacency definition.
In this appendix we provide a conjecture comes from the calculations (64)-(66), where we used the constraints on the means from (57):
the origin of this difference. The leading order behavior
( Tiıl S rt, ( b)ll S rt, ( b) (b, b)ll S rz.
(131)
However, one doesn't use the constraint on the difference and only uses the first two upper bounds on the means then the best bound on the dot product becomes
|pe(b' b) Ap b)I <
(132)
and so the bound (66) is weakened to
d²
(0) s 2a(a - 1)) (1) cc 16a(a ( 1)/o? + 0(1/of)
(133)
dq²
which at leading order is factor of 4 larger than our result (66) which was derived using all three constraints in (57). The strategies we employ differ from Wang et al. (2019) in a way that makes difficult to pinpoint exactly what the essential differences are, however the above calculation leads us to conjecture that the difference originates in the failure to account for the constraint that couples Apt and Apt. See also Remark C.6.
F Variance of Fixed-size vs. Poisson Subsampling
In this appendix we provide detailed calculations of the variance comparison that was discussed in Section 4.2. Let a; E IR, I.., [D] (for application to DP-SGD, can take a; VeL(d, the gradient the loss at the i'th training sample d, in the direction v) and let [B] E {1,... DI]. Let Jr, i = 1,..., |D) be iid Bernoulli B|/| random variables, B be random variable that uniformly selects a subset of size [B| from {,...., [D]), and Ry. j = 1, [ be iid uniformly distributed over [1.... DD}. We will compare the variance of the Poisson subsson--ubaapple average,
D
1
Zp
a,
(134)
B
with that of fixed-size subsampling with replacement,
1
Zn
an
(135)
B
and with fixed-size subsampling without replacement,
1
ZB =
a;
(136)
B
iEB
34

---

They all have the same expected value, equaling the average of the samples:
E[Zp]
1
111
1
3 04
D
a==0
(137)
B
B
D
1
E|Zn|
E
E|an,]
E
(138)
B
B
|B|
D
1
a,P(R, = =
04 = a.
B
D
and
D
(
B
Σ
a B) = B
d
(12
a
(139)
The variances are
[pp]
0:a; [[:J]] - a
(140)
B
a
[[J
+
Σ
e;a - ह
B
2
|B| itj
2 +
Σ
Σ 0;aj
0:aj
D
B
D
D
8
D
1
1
1
Σ
of
|B|
D
1
Var 1R
ElaR, and a²
|B
2
fØ==
[B]
Ft +
F[any Flannl a²
|B| 2
B
(
[B]
E (aa
+
Σ
22 n
|B3
2
|B²
j=1
[B]
|B3
E
RR
0
+
|B
(IB - |B|)a² -2
DD]
B
E R
+ (1- (1 a
B
B
P(R
B
j=1
D
22
D
B
1
=(1 (BI -oVol)-'aar/aa
Var[Zp]
B
35

---

and
DI
Var [al
a.ayPli B,j E -
(141)
|B|
a P(i B) +
0:0j
P(i B.j E B) a²
B
B
a
B
B
2
(B)
(DD)
B
D
11
[D]
Σ
af
D
1
- 1)
Σ $
a:ag
[D]
1
Var [p]
a² x²)
|D]
-1
B
D
Therefore, defining a² relations
[D]
Σ a7 when
<
[] and a² + we obtain the following variance
Var
a²
1
(142)
Var 7rp
a
Var [3]]
(1- π2
(1-3)
(143)
Var ppl
1/|D|
and
1 1 1/| 1 [a)]
Var[ZR]
(144)
In particular, we see that fixed-size subsampling with replacement always has larger variance than fixed-size subsampling without replacement by the constant multiple I-1/|DI > 1; however, this 1-g
factor close to when is small. Therefore, for practical purposes we can consider them equivalent from the perspective of the variance. When [B] |D] the ratio of fixed-size and Poisson variances is
Var ZB]
(145)
Var Ppp
1/ID|
a
The Cauchy-Schin Seheaar- inequality implies 0 a² a²/a² < and when a * O and DI is sufficiently large; in DP-SGD the condition a * 0 corresponds to being away from (local) minimizer critical point of the loss. This calculation suggests that fixed-sized minibatches are better to use when one is away from the optimizer, as they lead to a (potentially substantial) reduction in variance, but they can become (slightly) worse than Poisson-sampled minibatches when one is close to local minimizer (i.e., क RJ O). However, for typical training-set 1 and so the variance advantage of Poisson subsampling when ā ~ 0 is very minor. In addition, due to the effect of noise, DP-SGD cannot reach ă = 0. Therefore, from the perspective of the variance, we conclude that fixed-size subsampling (with or without replacement) is generally preferable over Poisson subsampling.
that Var[Z Var [r)
size [D] > 1 have (1 1/|
G Comparison of Poisson and Fixed-size DP Bounds under Add/Remove Adjacency
Using the conversion from Proposition 3 in Mironov (2017), if mechanism satisfies e' e((a)-RDP then it satisfies (c, 6DP with
e e= e'aa) + log(1/8)
(146)
Or -
36

---

Under add/remove adjacency, to leading order, both Poisson and fixed-size subsampling satisfy RDP bounds with c'(a) aR for some (see Abadi et al. (2016); Mironov al. (2019)) and (19). Assuming that the optimal is not close to one, and hence we can approximate a with = minimizing over a gives
log(1/0)) a --1
log(1/0) 2 logg(///)).
c= inf asl
d(a))
inf A5O
AR
(147)
For steps of fixed-size subsampling (with without replacement), and with constant variance o, Eq. (19) implies
Res N tq 2 (E - -1) x2
26q²
(148)
In contrast, for Poisson subsampling the results in Abadi et al. (2016); Mironov et al. (2019) imply
Rp ~ to² (cl -1 =
tq²
(149)
202
Therefore Rps 2 4Rp at leading order and so (147) implies
EFS = 2 21 log(1 R 2ep.
(150)
From a privacy perspective, this suggests that e for Poisson subsampling has an intrinsic advantage fixed-size subsampling by approximately factor of 2 when using the add/remove adjacency relation. Noting the scaling of (150) with a, we see that fixed-size subsampling requires noise 2n to obtain the same privacy guarantee (at leading order) Poisson sampling with noise Tighter translation between RDP and (e. 8) -D,,, such as Theorem 21 in Balle et al. (2020) which is used by Meta Platforms (2024), alters this story somewhat but the general picture we have outlined here is corroborated by the empirical comparison provided in Section 4.2. We emphasize that this factor of two gap disappears when using replace-one adjacency; in that case Poisson subsampling and FSWOR subsampling lead to the same DP guarantees, as discussed in Section 4.1.
H
Additional Experiments
To assess the sensitivity our proposed method to important parameters such as a and batch size [B], we conducted series of additional experiments to compare our proposed fixed-size method with the non-fixed size setting while varying values of B e {50, 100, 150, 200} and a e (3.0, 4.5, 6.0, 12.0). Figure 10 depicts the results of these experiments.
As shown in Figure 10, the results for varying values of and [ align with what we reported in Section 4.2, showing that the proposed method is not sensitive to parameter settings.
37

---

200
120
106
300
130
spech
Performance with different values of (3.0, 1.5, 6.0, 12.0)
15-50
120
200
Mlam RDP ynw00
Plasr 10" SnwwO
Plus RD inwwo0t Feloumpied 4pozhh
b Performance with different values of batch size B E (50, 100, 150, 2003
Figure 10: Comparing Fixed and Non-Fixed Size Performance with different o (a) and batch sizes (b) on CIFAR10
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The paper provides the first fixed-size subsampled analysis of DP-SGD, which practically contributes constant memory usage in DP applications. The improvements on the state-of-the-ar fixed size method proposed by Wang et al. is clearly shown by theory and in practice on CIFAR-10.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 4.3 and Figure clearly state the benefits and limitations with respect to both state-of-the-ee art fixed size uub-sampling methods and traditional non-fixed-size sampling supported by empirical results on CIFAR-10.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
39

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The paper provides rigorous and complete proof's for the upper-bounds obtained
in the fixed-size regime, both for with and without replacement cases. All proofs and derivations carefully double-checked to be correct and complete.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: In addition meticulously stating key parameters in the experiments in Section 4 and all plots, the code to exactly replicate our results in Section 4, accompanied with all the numerical analysis and generated plots throughout the paper was made available during submission. We will also make the privacy accountant publicly available upon acceptance.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
40

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We submitted the code of our privacy accountant to allow exact replication of our results. The repository includes the code to replicate the results in Section 4, example using our accountant on CIFAR 10 as well as the numerical analysis and generated plots throughout the paper. We will also make the repository for privacy accountant and experiments publicly available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c co/
mablic/guides Saaeeee//ooeuuuiiiiiiiooo oliic) for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips wttpccccpppppcpttccccccccccccctc wwtpc//ggges///eeee http://oooSSSuiiiieoeeee www.uummiiisiooooooiicoo.. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The key (hyper)parammeters are meticulously stated in the experiment section as well as all numerical analyses.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
41

---

Justification: We noted in the main body that Figure 4 was plotted with 3-sigma standard deviation around mean based on five runs each with different random seeds for sampling: 1, 1,364, 2, 560, 3, 000, and 4, 111. Also, the code that generates the plots were provided in our provided source code. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, 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
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.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors 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 the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper states that the experiments were run single work station with NVIDIA RTX 3090 with 24GB internal memory. The runtime for all experiments was under 12 hours.
Guidelines:
The answer NA means that the paper does 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: : http://ewurrr.c.cccee hc.ppublic/thhiccuuiieee Ethicssuiddeliees
Answer: [Yes]
Justification: We envision no negative impacts of our work. Not human subjects was used. Datasets are publicly available. Also, the code associated with this work not envisoned to be used for malicious purposes.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
42

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The introduction and conclusion both highlight the positive societal impact of our work privacy preserving machine learning by providing a new privacy accountant that advances the status quo in enhancing users privacy as machine learning and deep learning becomes more ubiquitous individuals lives. As noted above, we do not envision any negative societal impact.
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 direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
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)?
Question:
Answer: [NA]
Justification: The dataset a publicly available common benchmark. Also the the proposed accountant helps privacy-preserving ML and is not envisioned to be used in a malicious manner.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
43

---

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: The CIFAR-10 dataset and Opacus library are both widely-used open-source and were properly cited the main body. No other external assets was used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code comes with readme file that includes an example of using our privacy accountnt and describes how to replicate the results in the experiment section.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: No human subject or crowdsourcing involved in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
44

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsouring human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "GK1Nb5x2if", "reviewer": "Reviewer_uSpK", "summary": "This paper studies the Renyi DP guarantees of a with- or without replacement subsampled Gaussian mechanism. Authors present a privacy analysis tailored for the subsampled Gaussian mechanism, which improves the earlier general bound for $\\epsilon(\\alpha)$ by Wang et al. 2019 by a factor of four. Authors show analytically, that the subsampling induced variance (i.e. the variance of the noise arising from using minibatches instead of full data) is smaller for without replacement subsampling than for the more commonly used Poisson subsampling. Authors also give a theoretical analysis of the differences between WOR and Poisson subsampling, showing that the Poisson subsampling leads to approximately half the $\\epsilon$ of the WOR sampling. Authors demonstrate empirically that for fixed noise level, the WOR leads to better accuracy than Poisson subsampling in a CIFAR10 based deep learning task, suggesting that the difference is due to the lower subsampling noise. Finally, authors show that the WOR sampling leads to more stable memory usage.", "questions": "- As you acknowledge towards the end of Section 3.5, Wang et al. 2019 use the substitute neighbourhood relation which differs from the add/remove used in this paper. Can you clarify, is this difference taken into account in Figure 3?\n- Fig. 2: I'm a bit confused on the upper bounds show in this Figure. It seems that after some $\\alpha$, your proposed upper bound exceeds the one from Wang et al. Does this suggest that the Wang et al. bound is tighter in some regime of $\\alpha$?\n-  In the Appendix D, you derive the RDP bounds for the substitute relationship using mixture of Gaussians with weight $1-q$ on Gaussian centered at $0$ and weight $q$ for the \"adjacent\" point. A recent work by Lebeda et al. 2024, suggest that this might not be the worst-case distribution for woR-sampling (see Section 7 in Lebeda et al.). While their analysis is tailored for approximate-DP and not RDP, I wonder if the same holds RDP.\n\n**Typos and other minor things**\n- Eq. 57, extra parenthesis in the expression for $M_{\\sigma, 4}$\n- I guess the NN abbreaviation is never explained. However, I don't think using it is necessary for the paper to begin with as you analysis applies to any learning task using DP-SGD.\n- Fig. 2: the caption is overlapping with the axis label. Also, I think this figure is never referred to in text.\n- \"... even without using the convexity technique; ...\": which convexity technique are you talking about?\n- \"$a_i = \\nabla_\\theta L(d_i) \\cdot v$\", what is the $v$ here? Also, since the gradient is multidimensional, are you talking about dimension-wise variance?\n- \"addtional\"\n\nLebeda, Christian Janos, et al. \"Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition.\" arXiv preprint arXiv:2405.20769 (2024).", "limitations": "I think authors should still address whether other accounting tools can solve this problem more efficiently that their method in the approximate DP domain. Other than that I believe the limitations are well addressed.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The DP-SGD algorithm is by far the most widely applied tool for DP machine learning. Since WOR sampling is more commonly used in non-DP ML than Poisson subsampling, improving the privacy bounds for WOR sampling is a interesting and important contribution. The theoretical analysis based on Taylor expansion of the Renyi divergence is a novel contribution and allows stricter bounds than the general result by Wang et al. 2019. Furthermore, the fact that WOR results into smaller subsampling noise is an interesting finding as well. \n\nThe numerical results for the accounting highlight the significant improvement over the current state-of-the-art WOR sampling privacy accounting, showing over a factor of two improvement in the $\\epsilon$ after conversion to approximate DP bounds. Also the empirical comparison on memory usage demonstrates the benefits of WOR sampling.", "weaknesses": "While the presented analysis provides important insights and improvements over the previous RDP analysis for WOR sampled Gaussian mechanism, I wonder if the problem is already solved with the modern privacy accounting tools. For example, Zhu et al. 2022 solve the WOR sampled Gaussian mechanism in their characteristic function formalism. Given that the conversion from RDP to approximate DP is lossy, I would imagine the bounds presented in this work are more loose than the bounds of Zhu et al when converted to approx DP domain. Since the approx DP bounds are more commonly used than RDP bounds, I'm not sure if the tight RDP analysis is really needed. Or is there some practical reason, e.g. an implementation difficulty, that would not allow using the characteristic function accounting for this problem?\n\nZhu, Yuqing, Jinshuo Dong, and Yu-Xiang Wang. \"Optimal accounting of differential privacy via characteristic function.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Relation to Zhu et al. (2022)**\nPlease see the response to this comment in the general rebuttal section above.  \n\n**Lossy conversion to $(\\epsilon, \\delta)$ guarantees**\nWe acknowledge (as the reviewer correctly states) that RDP guarantees are not lossless when converted to $(\\epsilon, \\delta)$ guarantees. However, for RDP accountants, regardless of the conversion that is used, with our method it is possible to significantly improve guarantees (by a factor of 4). To our knowledge this is the strongest improvement on RDP for DP-SGD. Given that RDP is one of the most widely used methods in DP libraries, using our method leads to substantial improvements in a myriad of real-world applications. \n\n**Substitute neighborhood relation of Wang et al.** \nThanks for asking for clarification on this. We show in our Appendix D.4 that the behavior of our bounds is the same for both replace-one and add/remove adjacency notion to leading order. To be consistent across the paper, in all of our implementations, we used the add/remove adjacency notion in Figure 3 and other Figures. We clarified this in the main body of the manuscript.\n\n**Upper bounds in Fig. 2**\nThe behavior of bounds for large $\\alpha$ is addressed beginning on Line 196.  In practice, for any choice of $\\delta$ one need only consider the bound in a range of $\\alpha$'s near 1 to convert from RDP to $(\\epsilon,\\delta)$-DP  and so the behavior of our bounds for large $\\alpha$ is irrelevant in practice.  This can be seen by Figure 3.  In addition, by combining our bounds with the convexity technique discussed in Appendix D.3 one can eliminate this large $\\alpha$ issue; see the solid black line in Figure 9. \n\n**Worst-case bounds for woR-sampling**\nThe worst case in Lebeda et al. 2024 holds for HS-divergence and not RDP. As these are different divergences, the worst case distributions aren't necessarily the same. For RDP, we prove in our Appendix D that the worst-case is what we presented. \n\n**Convexity technique**\nThe convexity technique we refer to on p. 6 was introduced in Wang et al. (2019).  Please see Appendix D.3 for more details on application of the convexity technique to Theorem 3.1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pyTbqcmR8B", "reviewer": "Reviewer_kPGW", "summary": "The paper first proves new privacy bound for the subsampled Gaussian mechanism under fixed-size sampling with and without replacement, which improves over the tightest known prior results in (Wang et al. 2019) by a constant of four. The proofs rely on a careful coupling of the sampling processes on neighboring datasets (similar to the design in Wang et al. 2019) to reduce the problem of analyzing divergence between Gaussian mixtures, for which the analyses in (Mironov et al. 2019) are applicable. \n\n- For fixed-size sampling without replacement, the paper proves integral upper bounds for the remainder term of the Taylor expansion of the privacy bound, to obtain tighter constants compared to the privacy bound in Wang et al. 2019. \n- The method extends to fixed-size sampling with replacement. It allows an upper bound that is similar to the upper bound for sampling without replacement in the leading term to sampling probability q. The authors also prove a lower bound under such settings and numerically investigate its dependence on the batch size and the Renyi divergence order.\n- The authors analytically showed that the empirical gradient variance is larger under Poisson sampling compared to fixed-size sampling, but the privacy bound is smaller under Poisson sampling compared to fixed-size sampling, indicating an interesting privacy-utility trade-off depending on the choice of sampling schemes, when fixing the sampling probability the same.", "questions": "1. The reason for improved tightness of DP bound by a constant factor (see weakness for more details)\n2. It is interesting that the paper shows that Poisson sampling enables smaller RDP bound than fixed-size sampling when keeping the sampling ratio the same. However, I wonder if it is a phenomenon that is unique to the add-or-remove-one notion of differential privacy. Could the authors comment on whether there will be a similar gap between Poisson sampling and fixed-size sampling when considering the replace-one notion of differential privacy?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- An interesting way of computing DP guarantee for subsampled Gaussian mechanism, via computing integral upper bounds for the remainder term of its Taylor expansion.\n- The proposed method yields a tighter RDP guarantee for subsampled Gaussian mechanism under fixed-size sampling without replacement, compared to prior results (Wang et al. 2019) by a constant factor of four.\n- The method extends to fixed-size sampling with replacement. It allows an upper bound that is similar to the upper bound for sampling without replacement in the leading term to sampling probability q. The authors also prove a lower bound under such settings and numerically investigate its dependence on the batch size and the Renyi divergence order.", "weaknesses": "- The reason for the improved constant factor compared to (Wang et al.) is not crystal clear. Is the integral upper bound for the remainder term of Taylor expansion of the DP bound contributing to the tighter constant? Unfortunately, the Taylor expansion is not explained in much detail in the main paper (e.g., in Theorem 3.2, the crucial terms related to $A$ and $M$ are not presented nor explained).\n- Although it is interesting that the paper shows tighter constant in leading order term of the DP bound (via analytical approach), the value of this contribution in practice needs more explanation. As the divergence between Gaussian mixtures could be tightly computed numerically following (Mironov 2019.), it is unclear why we need an tighter analytical bound given by integral upper bound for the remainder term of Taylor expansion of the DP bound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**\"The reason for the improved constant factor compared to Wang et al. is not crystal clear\"**\nThanks for pointing this out. We clarified further at the end of the introduction (see also the discussion in Appendix D4) that we compute the Taylor expansion of the Renyi divergence in the sampling probability, q, with explicit upper bounds on the error terms. As q is small in practice, the error terms are small.  Therefore the fact that we exactly capture the leading-order behavior in q  leads us to have nearly optimal bounds in practice, as seen by our comparison between upper and lower bounds in Figure 2.  This is in contrast to the method of Wang et al, which does not capture the leading order behavior in q and therefore is not tight for DP-SGD. \n\n**\"The value of this contribution in practice needs more explanation...\"**\nThe Taylor expansion is used because it allows the leading order behavior in q to be captured exactly, which provides tighter RDP  bounds.  We used explicit bounds on the error terms rather than the numerical approach of Mironov et al. because it requires computing  fewer terms.  \n\n**\"Could the authors comment on whether there will be a similar gap between Poisson sampling and fixed-size sampling when considering the replace-one notion of DP?\"**\nThank you for this insightful question. No, under replace-one regime, there would be no gap between the Poisson and fixed-size, to leading order.  We clarified this point in the comparison in section 4.2 as well as in Appendix D4.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FdDtGY2V9M", "reviewer": "Reviewer_JRin", "summary": "This paper analyzes Differentially Private-SGD with fixed batch size (with and without replacement), through the lens of Rényi-DP. The bounds without replacement have a much better constant than previous ones; the ones with replacement are brand new.", "questions": "Since you reduce to the same intermediary quantity as https://arxiv.org/pdf/1908.10530 (in Eq. 6), does it mean that:\n- the bound of that paper applies as-is to fixed batches using your proof (i.e., if one were using the Opacus accountant with fixed batches as a heuristic, it’s actually not a heuristic)?\n- if not, why is that?\n- if so, how does your new bound compares? (other than enabling the analysis with replacement, which is cool!)\nI think that the paper would benefit from discussing those to give a bit more context. S4.2 is related, as it gives an interesting discussion of where the different factor comes from (so the quantity is not identical I guess), but not all of this, like whether you could use the previous approximation as is, and how the two numerical procedures compare.\n\nAfter reading S4.2, I am wondering if the difference is a bit artificial, or at least tied to the notion of sensitivity. For instance, Poisson sampling would also pay a factor two under the change one definition (I think?) whereas your approach would mostly not change I believe (I only skimmed the appendix on sensitivity to I’m not completely sure, but intuitively it’d make sense—the section doesn’t seem to discuss the implications on Poisson vs. fixed batch). Is it the case that your approach pays a 2x factor, but also gets the stronger change-one for free, whereas Poisson gets the better guarantee under add/remove, but its equivalent under change-one? It would be an interesting thing if that’s the case I think (change-one is pretty popular in other applications, I don’t think it’s really less conventional as the paper claims).", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The results are important and likely to be impactful in the niche of DP deep learning. It’s cool to see progress on DP analysis that gets closer to what practitioners actually do. \n- The paper is really well written and thorough in its discussions. I really enjoyed reading it.", "weaknesses": "It’s a bit of a nitpick, but the paper keeps claiming that this analysis is DP-SGD specific, and that’s what enables the tight bounds. It seems like it is specific to:\n- the Gaussian mechanism (with specific subsampling approaches)\n- and I guess additive contributions of datapoints to the function?\nAnyway, it might be good to give the specifics in a slightly more general/abstract fashion, and then discuss why it applies to well to SGD? Just so that the reader doesn’t expect tight couplings with the optimization or something, and also because it may be slightly more broadly useful.\n\nMinor:\n- several citations seem off: the “standard differential privacy (DP)” citation is CDP, poisson sampling from RDP cites the RDP paper instead of this one I assume https://arxiv.org/pdf/1908.10530.\n- \"even without using the convexity technique” p. 6 -> this has never been mentioned before. You need more details here for context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**DP-SGD Specific**\nThat is an accurate comment, in that we do not use the fact that the additive terms involve gradients. Our method is applicable to any Gausian Mechanism with fixed-size subsampling where each sample contributes an additive term to the mean and those terms are uniformly bounded. The only aspect of DP-SGD that we do not explicitly use is the fact that each additive term is a clipped gradients. These specific structural aspects of DP-SGD are what allow us to obtain tigher bounds than Wang et al. (2019). \n\n\n**Relationship to Mironov et al. 2019**\nThanks for pointing this out. The answer is no. The reason is that if one uses Opacus implementation with Fixed Size sampling mechanism that would lead to incorrect privacy bounds.  Our previous wording gave the false impression that the Mironov et al.'s method applies to the cases under consideration here and so we have removed that sentence.  The relation between Mironov et al. and our work is discussed in detail in Section 4.2. \n\n\n**Section 4.2: Adjacency Relations**\nThank you for this insightful question. You are correct, the 2x factor is the same whether one considers add/remove or replace adjacency relations, as we show in Appendix D4. Therefore our approach gets change-one for free as you say, while Poisson achieves tighter bounds under add/remove but gives equivalent bounds to leading order under replace-one adjacency, as shown by a similar computation to what is currently in Appendix D4.  We have added text in the introduction as well as in Sections 4.2 and Appendix D4 to further highlight this fact.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZSe4os6ogm", "reviewer": "Reviewer_Rv66", "summary": "The paper studies the Rényi differential privacy (RDP) guarantees of the subsamplied Gaussian mechanism with fixed-sized random minibatches, when the so called add/remove neighborhood relation of datasets is considered. It uses similar techniqes as were used in the paper \n\nMironov, Ilya, Kunal Talwar, and Li Zhang. \"R\\'enyi differential privacy of the sampled gaussian mechanism.\" arXiv preprint arXiv:1908.10530 (2019),\n\nwhich augmented the seminar paper Deep Learning with DP (Abadi et al., 2016) and gave rigorous RDP guarantees for the Poisson subsampled DP-SGD.\n\nThe paper also studies both analytically and numerically the benefits of carrying out subsampling with fixed-sized minibatches instead of Poisson subsampling.", "questions": "Can you comment on the accuracy of the upper bound in case of \"with replacement\"? Is it still open/unclear, how tight those bounds are?\n\nCould you provide \"with replacement\" upper bounds also for the hockey-stick divergence, i.e., do you obtain a dominating pair of distributions for the hockey-stick divergence?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "- The analysis looks solid, generally a well-written paper\n- The variance analysis and the numerical experiments showing the benefits of fixed-size subsampling without replacement seem novel and interesting\n- The analysis for the \"with replacement\" subsampling seems interesting though it is quite limited", "weaknesses": "- Clearly the biggest deficit of the paper is that it does not take into account some of the recent research in this area. Most importantly, it overlooks the work\n\nZhu, Yuqing, Jinshuo Dong, and Yu-Xiang Wang. \"Optimal accounting of differential privacy via characteristic function.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022. https://proceedings.mlr.press/v151/zhu22c/zhu22c.pdf\n\nThe main result of this paper is a special case of the Thm. 11 by Zhu et al. (2022) : If $(P,Q)$ are a dominating pair of distributions for the base mechanism in substitute relation, then the fixed-size random subsampling without replacement give a dominating pair $(q P + (1-q) Q, Q)$ for removal neighbours and $(P, (1-q) P + q Q)$ gives a dominating pair for add neighbors. Then, we know the dominating pair $(P,Q)$ of the Gaussian mechanism in case of substiture relation of datasets (pair of one-dimensional Gaussians) and the result of this paper's mmain result (Thm. 3.1) follows since if a pair if dominating pair for the hockey-stick divergence, by the Blackwell theorem it dominates also for other $f$-divergences. \n\nSince this \"without replacement\" result consitutes such a big part of the paper, I think this is a major deficit and there should be a major revision before accepting this paper.\n\nThis with replacement upper bound seems interesting, however my impression is that it is quite conservative (see e.g. Fig. 7 of the appendix). Only the experimental results for the lower bound in case of \"with replacement\" are given in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Relation to Zhu et al. (2022)**\nPlease see the response to this comment in the general rebuttal section above. As the analysis of Zhu et al. does not investigate application to DP-SGD, the results of Theorem 11 in the DP-SGD setting are hypothetical until or unless directly demonstrated.  The reviewer provides a proof sketch that does not result in a rigorous reduction of Thm. 11 (Zhu et al.) to our Thm. 3.1. We note that DP-SGD operations in practice are much more complicated than simple Gaussian Mechanism. \n\n\n**Accuracy of the upper bound \"with replacement\"**\nOur results, which include both a lower and upper bound, show that sampling with replacement catastrophically increases in the Renyi bounds. This aligns with intuition as the fact that one (i.e., an adversary) can get multiple same samples in the same batch is a drastic violation of privacy, and this is what we show in our Figure 7.\n\n**With replacement upper bounds for hockey-stick divergence**\nBounding HS divergence with replacement is a nice research question, but is not trivial and requires substantial work that warrants further study. Our study focuses on Renyi divergence.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their time and very useful feedback!  We provide responses to each reviewer individually.  Please see below for responses to a common point.

**Relation to Zhu et al. (2022)**

Reviewers uSpK and Rv66 ask whether our WOR result of Theorem 3.1 is a corollary of Theorem 11 in Zhu et al. (2022).  Their work leads to the analytical Fourier accountant (AFA) for Gaussian mechanisms in general. AFA is not specific to DP-SGD, which is the main topic of our work. Our work should be viewed as an extension of Wang et al. (2019) that is specific to DP-SGD with Gaussian noise and focuses on the strong composition afforded by RDP. Theorem 11 of Zhu et al. (2022) accounts for addition and removal of neighbors in the general Gaussian mechanism case. We could not find any evidence that the analysis in Thm 11 yields a privacy bound for DP-SGD with a large number of training steps that is tighter than and as rigorous as what we have provided. Our reasons are as follows:
DP-SGD requires the consideration of Gaussian mixtures, and therefore the characteristic function required by the method of Zhu et al must be  computed numerically. We anticipate this can be difficult for a large number of compoisitions, as is typical in DP-SGD, due to the required integrations of a sum of a large number of terms, as required by Algorithm 1 in Zhu et al. In addition, there is potential privacy leakage due to lack of rigorous error bounds for the double (Gaussian) quadrature numerical integration approach as discussed in their Appendix E.1. Using Gaussian quadrature for DP-SGD presents major practical difficulties that do not seem to be addressed in Zhu et al's work. Our approach is a specialized method for DP-SGD that avoids the practical concerns associated with numerical integration. 

Hayes et al. (2024) uses the results in (Zhu et al., 2022) to provide a bound specific to DP-SGD when one is only concerned with training data reconstruction attacks rather than the membership inference attacks, which leads to a relaxation of DP to provide a bound that is only applicable to defending against data reconstruction and not membership inference. Our work can be viewed as a complimentary work to Hayes et al. (2024) that is specific to DP-SGD and provides conservative bounds protecting against membership inference attacks (and thus any other type of model inversion attacks including training data reconstruction) in the RDP context. Overall, the applicability of Thm 11 in Zhu et al. (2022) to fixed-size subsampled DP-SGD is hypothetical until or unless they are explicitly demonstrated in the DP-SGD context.

We discussed both of these studies in our background and related work.

    * Zhu, Y., Dong, J. and Wang, Y.X., 2022, Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics (pp. 4782-4817). PMLR.
    * Hayes, J., Balle, B. and Mahloujifar, S., 2024. Bounding training data reconstruction in dp-sgd. Advances in Neural Information Processing Systems, 36.

Meta-review: The paper studies the privacy accounting of DP-SGD under the sampling-without-replacement model but unlike in previous work that worked with a "replace" neighbor relationship, this paper uses an "add/remove" neighbor relationship. 

The main claim is that for DP-SGD, they can improve the best known Renyi-DP bound by a factor of 4 when the order $\alpha$ is smaller than a threshold and that (at least numerically) the restricted range $\alpha$ still supports stronger composition in DP-SGD.

Reviewers acknowledged the importance of the problem and the claimed improvement but found the following aspects unsatisfying.

1. the use of "add/remove" relationship in amplification by WOR sampling was studied in a prior work [ZDW'22], with a direct analysis of $(\epsilon,\delta)$-DP by analyzing the hockey-stick divergence of a dominating pair.

2. One reviewer is skeptical of the claim that the particular Gaussian mixture being a dominating pair for the WOR sampling case in the Renyi ordering, as it was shown in the recent work of Lebeda et al that it isn't in the "Blackwell ordering".  The same reviewer also comments on other issues in Appendix D.4. such as:

> "I don't see where the bound of Eq. (108) comes from, why is there no additional factor 2 (or 4 after squaring)."
 
3.  The techniques used are similar to those in Mironov et al. 2019, and Wang et al. 2019.

I only have a limited amount to time to look into these issues. For Point 1,  I do believe that a tighter RDP analysis has its own value even if it does not give a tight epsilon-delta DP bound as the Hockey-Stick Divergence. 

- If the authors add a comparison of the RDP-converted approx-DP privacy profile to the latest FFT-based numerical account as in Lebeda et al., it should be sufficient in addressing this concern.

Point 3 was acknowledged in the paper. The particular coupling used is similar to Wang et al. 2019 and the Taylor expansion of the mixture of Gaussian into quantities one can evaluate with Gaussian CDF calls is due to Mironov et al. 2019.  The authors however clearly discussed the differences in the proof.

In the discussion period, the reviewers and the AC tried to resolve Point 2, but it requires more time than we had. However, in general, dominance in Blackwell ordering and dominance in Renyi ordering are different. It is perfectly possible that the mixture of gaussian pair does not dominate in Blackwell ordering (as was shown in prior work) but it dominates in Renyi ordering.  We did not catch any obvious error in the proof of Theorem 3.1, so it should check out! 

I wanted to add that the authors also proved new results about the "replace" neighbor in appendix D.4, which the authors wrote in the rebuttal that they should have focused a bit more on it.  I agree that "replace" neighbor is more natural for random subset sampling.   The paper ran into the same issue of having mixture of two Gaussians in both the numerator and denominator as in Wang et al. 2019 when applying joint convexity directly.   Wang et al., 2019 went through a ternary-type divergence and then the binomial expansion, which resulted in a general result with more precise control of the higher order terms, but incurred a factor of 4 in the leading term.  The current paper directly applied Taylor expansion twice (first over q near q = 0, then for e^x near x = 0) in a way similar to the approach Abadi et al (2016) took. This argument ended up resulting in an expression that allows one to complete the square in Eqn (107), hence reducing the factor of 2 ( factor of 4 after squaring) in the leading term.   The reviewer's confusion of how (108) avoids the factor of 2 stems from that the sensitivity is now defined to be 2x the clipping threshold. This got clarified in the AC-reviewer discussion.

I think this is a nice step forward on the problem introduced 5 years ago by Wang et al 2019.  For this reason, I think the paper deserves to be published.

------------
Other comments the authors could consider:

1.  For the Add/Remove case, q is different for the two neighbor datasets.   |B| / n vs |B| / (n-1).  For the definition to make sense, one needs to either make n known or define the space of the dataset to be n > certain public threshold, then state the results according to that pubic threshold.  This was discussed in [ZDW'22].

2. Because of the above, it is more natural to use the Replace neighbors for WOR, and the result hidden in Appendix D.4. could be emphasized and moved to the main paper?

3. Results in Appendix D.4 are worth developing a bit further so that the higher-order terms in the Taylor expansions are replaced with valid upper bounds.  I also suspect the bound to be weaker than that of Wang et al 2019 when we are outside the regime of \sigma being large and q being very small.

4. As I mentioned before, numerically adding comparison to the FFT-based numerical accountants that skips RDP would make it clear the practical impact of the result here.
Decision: Accept (poster)