Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Authors: Andy Dong
Wei-Ning Chen
Ayfer Ozgur
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
federated learning
privacy amplification
model parallelism
data subsampling
Primary area: social_aspects->privacy
TL;DR: When each data point only interacts with a randomly chosen subset of model parameters or training iterations, it yields nontrivial privacy amplification—and our work is the first to formalize and quantify this effect under RDP.

Abstract: We study how inherent randomness in the training process—where each sample (or client in federated learning) contributes only to a randomly selected portion of training—can be leveraged for privacy amplification. This includes (1) data partitioning, where a sample participates in only a subset of training iterations, and (2) model partitioning, where a sample updates only a subset of the model parameters. We apply our framework to model parallelism in federated learning, where each client updates a randomly selected subnetwork to reduce memory and computational overhead, and show that existing methods, e.g. model splitting or dropout, provide a significant privacy amplification gain not captured by previous privacy analysis techniques. Additionally, we introduce balanced iteration subsampling, a new data partitioning method where each sample (or client) participates in a fixed number of training iterations. We show that in certain regimes, this method yields stronger privacy amplification than Poisson (i.i.d.) sampling of data (or clients). Our results demonstrate that randomness in the training process, which is  structured rather than i.i.d. and interacts with data in complex ways, can be systematically leveraged for nontrivial privacy amplification.

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Andy Dong' Wei-Ning Chen Ayfer Ozgur'
Abstract
leakage, offering strong protections even against adversaries with auxiliary information. The standard way to achieve DP is to inject randomness into the training process, typi- cally by adding noise- such as in DP-SGD (Abadi et al., 2016)-hiich provides formal privacy guarantees. How- ever, this comes a cost: injecting more noise strengthens privacy protections but often degrades model performance.
We study how inherent randomness in the train- ing process-whers where each sample (or client in fed- crated learning) contributes to only a randomly selected portion of training-an can be leveraged for privacy amplification. This includes (1) model partitioning, where sample updates only sub- set of the model parameters, and (2) data parti- tioning, where sample participates in only a subset of training iterations. We apply our frame- work to model parallelism in federated learning, where each client updates randomly selected subnetwork reduce memory and computational overhead, and show that existing methods, e.g. model splitting or dropout, provide significant privacy amplification gain not captured by pre- vious privacy analysis techniques. Additionally, we introduce Balanced Iteration Subsampling, a new data partitioning method where each sam- ple (or client) participates in fixed number of training iterations. We show that this method yields similar stronger privacy amplification than Poisson (i.i.d.) sampling of data (or clients). Our results demonstrate that randomness in the training process, which is structured rather than i.dd and interacts with data in complex ways, can be systematically leveraged for significant privacy amplification.
In this paper, we ask: instead of relying solely on large noise injections to achieve strong privacy guarantees, can we leverage the inherent randomness already present the training process? Many widely used techniques, such as dropout (which helps mitigate overfitting) and model par- allelism (which reduces memory and computational over- head), naturally introduce randomness can be modified to incorporate randomness without fundamentally altering the training process. However, this kind of structured ran- domness interacts with data in complex ways, making the associated privacy gains difficult to quantify.
The idea of leveraging randomness for privacy amplifica- tion-to reduce the amount of noise required-has been previously explored, primarily in two specific settings. The first is random subsampling, where each data point (or client in federated learning (Kairouz et al., 2021)) is randomly selected to participate in each training iteration (indepen- dently across iterations) (Kasiviswanathan et al., 2011; Li et al., 2012; Bassily et al., 2014; Wang et al., 2015; Balle et al., 2018; Wang et al., 2019; Zhu & Wang, 2019; Balle et al., 2020). The second is shuffling, where client data is individually privatized and then randomly reordered to plify privacy (Erlingsson et al., 2019; Girgis et al., 2021 Feldman et al., 2022; 2023; Chua et al.). More recently, random gradient compression has also been shown to pro- vide privacy amplification (Chen et al., 2024b;a). However, amplification by model parallelism techniques has not been studied before.
1. Introduction
Ensuring user privacy in machine learning critical, es- pecially in applications involving sensitive data such as healthcare, finance, and social networks. Differential pri- vacy (DP) (Dwork et al., 2006; Dwork, 2006) provides rigorous mathematical framework to quantify and limit data
In this paper, we investigate privacy amplification in more general context: whenever each sample (or client in the FL setting) contributes to only randomly selected portion of the training process, this randomness-if kept secret- can be leveraged enhance privacy. This includes data partition- ing, where sample (or user) participates in only a subset of the training iterations, model partitioning, where sam-
Depaartment of Electrical Engineering, Stanford University, Califomia, USA "Merossott. Correspondence to: Andy Dong <dxa@ stanford.edu>..
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
ple contributes to updating only a randomly chosen subset of model parameters in each iteration. The randomness we leverage in both cases is more structured than independent subsampling or uniform shuffling and has complex interac- tions with the samples. For example, gradients computed for random subnetworks cannot be represented as simply masked versions of full gradients, so prior privacy amplifi- cation methods fail under such scenario.
privacy amplification can be achieved through variety of derieylent-friendlly approaches.
Balanced Iteration Subsampling can be used in both cen- tralized training and federated learning. In the latter case, it can be viewed as a generalization of random check-ins (Balle et al., 2020), where each client in random check-ins chooses to participate in exactly one iteration with some fixed probability, whereas in our approach, each client par- ticipates in exactly i randomly chosen iterations out of T total iterations.
We develop a unified mathematical framework for privacy amplification that applics to both data and model partitioning. Specifically, our theoretical re- sults establish privacy amplification guarantees in the below settings.
Our Contributions:
2. Background and Definitions
In this section, we provide background and definitions for the paper and set up the problem.
Model Parallelism: When a model is partitioned into (disjoint or overlapping) subnetworks and each sample (or client) is assigned update only a randomly chosen sub- network in each iteration, this assignment introduces addi- tional privacy beyond standard methods. Existing privacy accounting techniques fail to capture this amplification ef- fect. This privacy gain is particularly relevant for federated and distributed learning, where model parallelism is already employed for computational and memory efficiency, e.g., using various model partitioning techniques (Yuan et al., 2022; Dun et al., 2022; Fang et al., 2024), dropout layers (Hinton et al., 2012; Konečný, 2016) or training models in ensemble configurations (Sagi & Rokach, 2018; Ganaie et al., 2022). Our experiments show that when training a 44 million parameter model with partial model splitting and DP-SGD with (8, 10-1)--D accounting for privacy ampli- fication with our theory yields higher validation accuracy than using existing accounting methods.
Differenital privacy measures the stability of a randomized algorithm given changes in an input instance, thereby quan- tifying the extent to which an adversary can infer specific inputs based on the algorithm's output. Mathematically, let S be the set of all possible datasets. We say that S, S' e S are adjacent datasets if S' U (x) or S' = SU {a} for some single data point x:
Definition 2.1. (Dwork, 2006) A randomized mechanism M : S + Ω is said to satisfy (c, 6)-P if, for all pairs of adjacent datasets S, S' E S and for all measurable set A, it holds that IPM E A) I P(M(SS) E A) + 6.
It is often useful to analyze privacy guarantees under the notion of Rényi DP (RDP): Definition 2.2 (Mironov (2017); Abadi al. (2016)). A randomized mechanism M S - Ω is said to satisfy (a, c)- RDP with a (1, oc) if for all pairs of adjacent datasets S, S E S, it holds that
Balanced Iteration Subsampling: Our framework also extends privacy amplification beyond standard independent subsampling across iterations. We introduce new subsam- pling method in which each sample is used in fixed number of training iterations, rather than being sampled indepen- dently in each iteration (as in Poisson Subsampling)! While Poisson subsampling has been a standard tool in DP due to its analytical simplicity, its practical limitations- sucoonsss-chaa as un- even user participation and unpredictable system load can undermine fair use and operational stability, so has spurred interest in alternative subsampling schemes (Chua al.). In contrast, Balanced Iteration Subsampling ensures equi- table contribution and stable system behavior. Our analysis shows that this method retains the desirable privacy-utilig -tility tradeoffs of Poisson sampling while addressing its prac- tical drawbacks, further expanding the toolkit of privacy- preserving subsampling techniques. By rigorously quantify- ing its privacy guarantees, we offer compelling alternative to Poisson subsampling, reinforcing the broader insight that
PM Da (M(S))IM(S)) - log Swen Pwee S
One key property of RDP is its additive nature under adaptive composition (Mironov, 2017). If mechanisms MM..,,,.,,,M Mr each satisfies (ax, RR)-DP, their com- bined mechanism satisfies (a, E RDD, simplifying privacy accounting in iterative algorithms and giving tight composition method.
An (a, c(a))-RDP guarantee can be converted to an (c. 8)- DP guarantee (Bun & Steinke, 2016; Canonne et al., 2020; Asoodeh et al., 2020):
Proposition 2.3. M satisfies (a, c(a)))RDP, it also sat- isfies (c + log 1 8DP for any 0 < 8 < 1. -
In this work, we use RDP to analyze the privacy guarantees of model and data partitioning techniques, allowing for fine- grained tracking of privacy loss and facilitating efficient composition analysis in complex training settings.
Note that this differs from shuffling, which ensures that each sample appears only once during training.
2

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
3. Main Results
we study in disjoint model splitting where k 1. In model splitting, each ja E Sa,t corresponds vector, where an entry of 1 in μ corresponds to block whose norm is constrained to c (the gradient clipping norm), while an entry of O in corresponds to a block whose gradient is 0 (i.e. not included in the submodel). The set Sa, is then the set of possible gradient vectors generated by the different submodels we could form, before adding noise. On the other hand, the mean of Q is the gradient of if is not used in training- is O.
potential gradient
3.1. Main Technical Result
In this section, we present the main result as a mathemati- cal statement outside of the context of differential privacy, although we give an overview of why it is what we need in Remark 3.3. We discuss the intermediate lemmas in the proof of the theorem in top-down fashion in Section 3.4 and defer the details to the appendix. In Section 3.2, we will show how our main theoretical result applies to quan- tifying the privacy amplification of model parallelism. In Section 3.3, we will define Balanced lteration Subsampling and show how the same result applies to quantifying its privacy gain.
The above bounds look complicated and not easily inter- pretable. We argue that this is intrinsic to the problem of characterizing the Rényi divergence between mixture of Gaussian and Gaussian, which is difficult problem to tightly characterize with existing results (Michalowicz et al., 2008; Durrieu et al., 2012; Nielsen & Sun, 2016a;;), which do not yield useful bounds for our purposes. The bound designed to be implemented on a computer to get a numerical answer. In later sections, we will plot this bound against existing baselines when we plug in suitable numbers for a variety of training settings.
Theorem 3.1. Let Sa,k {u E 10, | ||a|]== k) be the set of all binary vectors in IRd with k number of Is and d - k number of Os. Let P = [Sa Euesax-V NVCH, I²Ia) be a mixture of Gaussians and Q = NO Ia) be a Gaussian centered at O, where and o² are positive constants. Then,
1
: max {Da(PI Da
(1)
< max
1 n-T
log Σl
[(]
exp
2n
Enjeno 14 {f}
3.2. Privacy Amplification by Model Parallelism
ceck( k) k)
a²² 2d
+
1
log
exp
In this section, we apply Theorem 3.1 various model paral- lelism techniques starting with disjoint model splitting. This approach has been utilized in (Yuan et al., 2022; Fang et al., 2024) to limit the memory and computational overhead per node in a distributed setting. We describe this framework in the language of federated learning where each client assigned a random submodel, while the same discussion also applies to distributed training. In the following sections we extend model parallelism to overlapping subnetworks, where only subset of the parameters of the model are split between subnetworks (Dun et al., 2022). Finally, we discuss how the analysis applies to models with dropout layers.
2(a 2(a
(aexp(
(Q((d=)) k) x²
+ (1a) 1
k
d - k k- - l
ac?l
< max
log
exp
(
1
20
1=
ad?iid (c@
2²
1
log
exp
odd
2d
a exp
_u(dd 1)
o2
+(11a))
for all a 2 2,a E N, where [()] is the set of all a- length tuples with entries from (1...., ( and μ is the ith element of Sa..-
3.2.1. DISJOINT MODEL SPLITTING
Consider a model with m trainable parameters. In each iteration, we partition the model into d disjoint submodels (which do not need to contain the same number of param- eters). The partition may or may not be the same across iterations. That is, we may form completely different sub- models in each iteration, or may use the same partitioning strategy throughout. The model partitioning, random or not, is assumed to be known by the adversary and is not used for privacy amplification. What we leverage for pri- vacy amplification is the random assignment of one of the d submodels to each client, which remains hidden to an adversary. More precisely, for each client we independently and uniformly select one of the d submodels and send it for an update. The clients compute the gradients on their corresponding submodels and send these gradients back to
Remark 3.2. In the equation above, the first term of (1) is upper bounded by the first term of (2), which is in turn upper bounded by the first term of (3); likewise for the second terms. Since the Rényi divergence is not symmetric in its arguments, they are not the same and both are necessary for the completeness of analysis, but numerically the second terms are dominated by the first terms in the max. Also, we note that (2) gives a tighter upper bound while (3) is much more computationally efficient, so one should use (2) whenever possible. We discuss this in more detail in later subsections.
Remark 3.3. Although later sections will show applications of Theorem 3.1 and prove why it is useful in the appendix, we preliminarily give an overview of why this the object
3

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Algorithm 1 Differentially Private Model-Parallel Training
16
Standard DP-SGD Accounting
Input: T iterations, mn model weights, d submodels, dataset S, clipping norm c, noise variance o² M t init(m) // initialize weights
Our Accounting for Submodels
14
Accounting Submodels
Epsilon Privacy Budget
Accounting for Submodels
Our Accounting for Submodels
for / - 7o T' do
M1. .M.....,. Ma < create subnets(M, d) grad_sum + zero_vector (siiztt (size-m)
10
for r in do
+ raandon (1,2, (1,,)...,d)
grad + 9
7M Loss (M,, z) // gradient descent,
treating gradient of entries not in M₁ as 0 grad + clip (grad, c)
grad sum + grad sum grad
end for
Noise Standard Deviation
poisy.grad. sum t N ((grad sum, σ²) update_model (M, noisy-gradisum) end for
Figure I. The graph compares the noise standard deviation vs the privacy cost (c, 6)-DP with and without applying our amplifi- cation. where d = 10-5 and we train for 1200 iterations. The data is Poisson suhsampled with rate 0.1. Lower e and less noise are better.
the server. The server collects the gradients, treating the gradient of any parameter not in the submodel as O, and clips the per-client gradient norm to c. The server then sums or averages the clipped gradients and adds per-coordinate Gaussian noise with variance determined through privacy accounting. We summarize the centralized counterpart of this in Algorithm 1, which can be extended to the federated setting by treating the dataset as the set of clients.
we can proceed by dividing the model into "non-split" part and a "split" part. In the example above, the non-split part would be the first and the last blocks of ResNet and the split part would be the middle blocks. We use separate clipping norms for these two parts, and for the non-split part we can use regular privacy accounting method while the split part can benefit from privacy amplification via the method described in Sections 3.2.1. The RDP costs of the two parts can be directly added together by the composition theorem of RDP.
Theorem 3.4. Each iteration of Algorithm 1 (d submodels, noise standard deviation a, gradient clipping norm e) with a deterministic disjoint model splitting method satisfies (a, c)- RDP with given by Theorem 3. I, where k- 1.
The proof is in Appendix A.9.
Figure 1 compares the DP guarantee provided by Theo- rem 3.4 to baseline analysis with no amplification, for {2 6,83 submodels. The baseline is calculated using RDP accounting for the DP-SGD Gaussian mechanism (and is shared by all numbers of submodels because existing methods do not take model parallelism into account). The improvement is significant. More figures can be found in the appendix, in Figures 5 and 6.
3.2.3. MODEL SPLITTING WITH DROPOUT
In Sections 3.2.1 and 3.2.2, we show how the analysis ap- plies to models with some parameters subject to splitting and some not, while requiring that the parameters subject to splitting be split into disjoint subsets. This section shows that the requirement for disjoint subnets can be relaxed. For example, subnetworks can be created locally and indepen- dently at each client by using dropout. This approach has been used in (Konečný, 2016; Wen et al., 2022; Guliani et al., 2022) to limit per client communication and computation.
3.2.2. PARTIAL MODEL SPLITTING
In practice, the model splitting method we use may not split the entirety of trainable parameters into disjoint submodels. For example, (Dun et al., 2022) argues that when applying independent subnet training ResNet, the first few blocks and the last few blocks of the model sensitive to pruning while the middle blocks are less sentitive. When forming submodels, we may want to include the first and last blocks in all submodels while partitioning the middle blocks into d disjoint sets.
In Section 3.2.1, any arbitrary way to split the model into disjoint submodels is valid. In fact, if we have multiple ways to split the model into disjoint submodels, we can also use probabilistic mixture of these disjoint partitionings as stated in the next theorem. In order to assign a subnetwork to client in given iteration, we now proceed in two steps. We first choose a way to partition the model into disjoint submodels (possibly in probabilistic manner, not necessar- ily uniformly at random) and then one submodel from the chosen partitioning uniformly random, which is then as-
In this such cases, Theorem 3.4 does not directly apply, but

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
signed to the client. While the subnetwork assigned to each client comes from this probabilistic mixture of disjoint par- titionings, assignment is still independent across different users. Also note that with this probabilistic mixture model, it is possible the submodels trained in a given iteration are no longer disjoint. In the next theorem, we show that a similar privacy guarantee to Theorem 3.4 still holds in this case.
Algorithm 2 Differentially Private Training with Dropout
Input: T itterations, m model weights, dataset S, clipping norm c, noise variance o²
M < init(m) // iniitialize weights
for ( = 1o T do grad_sum + zero_vect (size-m) for x in S do grad f aM Loss n, dropout.rate-0.5)
// gradient descent
Theorem 3.5. Each iteration of Algorithm 1 (d submodels, noise standard deviation a, gradient clipping norm c) with model splitting method that is probabilistic mixture of disjoint model splitring methods satisfies (a,, c)-RDP with given by Theorem 3.1, where k- = 1.
grad + clip (grad, c) grad.sum t grad_sum + grad end for
noisy grad sum + (grad sum, 
update_model (M, noisy.grad.sum end for
The proof is in Appendix A.
Remark 3.6. We believe Theorem 3.5 can be potentially tightened. It only utilizes the randomness in submodel se- lection conditioned on disjoint partitioning of the model, but not the randomness in how the disjoint partitioning is selected. Thus, it has the same privacy guarantee Theo- rem 3.4.
3.3. Balanced Iteration Subsampling
In this section, we present a novel data subsampling scheme, and show that Theorem 3.1 can be applied to analyze its associated privacy gain. This data subsampling method can be used both in centralized (single-server) private training or in a federated scenario. We note that this data partitioning approach is orthogonal to the model partitioning approaches we studied in the previous section.
As a corollary, Theorem 3.5 applies to special case of dropout-that is, dropout layers that drop each node in the layer (and its associated inputs and outputs) with probability 0.5, which happens be a common choice of dropout rate when applied to a hidden layer. In a broad sense, dropout can be seen as a form of implicit model parallelism, as it effectively trains different submodels by randomly deacti- vating neurons during training.
Consider the following sampling scheme for differentially private neural network training. Let T be the total number of iterations in the training process. For each sample in our dataset, we randomly choose l of the T iterations, include in the & chosen iterations, and not include x in the remaining T - k iterations. Then, for each iteration, we form our training subset by gathering all samples for which we chose this iteration. The randomization in the procedure (i.e. samples used in each iteration) shall remain hidden from the adversary. In the case of federated learning (where instead of samples we assign clients iterations). this procedure is similar random check-ins (Balle et al., 2020), in which each client "opts in" at random iteration with probability and "opts out" from training entirely with probability 1 1- p. When 1, this model corresponds to Balanced Iteration Subsampling for = 1.
To state it formally, we first note that if a node in a network is dropped out, gradients of the weights touching that node in the preceding and succeeding layers are O, because in the preceding layer, weights that contribute the dropped node no longer participate in training, and in the succeeding layer, weights that interact with the dropped node are no longer in training. Assuming dropout is applied to subset of the hidden layers, we consider the "split part" of the network (see Section 3.2.2) to be the model coefficients preceding and succeeding these dropout layers (this the set of parameters that can be potentially impacted by dropping the nodes in these layers). Similar to Section 3.2.2, we use Algorithm 2 to update the gradients in this "split part" (and regular SPD on the "non-split part") which results in the following privacy amplification guarantee.
It is also worthwhile to compare Balanced Iteration Subsam- pling to Poisson Subsampling (Zhu & Wang, 2019), where in each iteration, we include each sample with probability y. The main difference is that in Poisson sampling, the num- ber of times each sample is included in training follows a Binomial(T,1) 7) distribution, with an expectation of T7 but it could range from to T. whereas in our case, each sample is included in training exactly is times. If = T as T + co,
Corollary 3.7. Each iteration of Algorithm 2 (noise stan- dard deviation o, gradient clipping norm c) satisfies (a, e)- RDP with given by Theorem 3. I, where d and k 1.
A concurrent work (Feldman & Shenfeld, 2025) analyzes the same subsampling technique and proposes RDP bound that a special case of our (2) with & = 1. See Remark 3.9 for more.
The proof is in Appendix A.
5

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
these two subsampling schemes become equivalent.
Theorem 3.8. Balanced Iteration Subsampling composed with Gaussian Mechanism with l/ sensitivity c satisfies (a, e)-DD with given by Theorem 3.1, where d = T, the total number of iterations, and k is the number of iterations each sample participates in.
8
Balanced Iteration Subsampling
Poisson Subsampling
epsilon
The proof is found in Appendix A.12.
Remark 3.9. When k = 1, the first term in (2) is exactly the same as the expression computed in the unpublished work (Liew& & Takahashi, 2022) and the concurent work (Feldman & Shenfeld, 2025) modulo minor combinatorial simplifications, where it appears that in the former, the au- thors mistakenly use the bound for the Shuffle Gaussian Mechanism. In the Shuffle Gaussian Mechanism, each sam- ple is used in only one random iteration, but the assignments of different samples to iterations are dependent since the batch size used in each iteration is fixed, so the analysis (A. does not apply to this case. Our Balanced Iteration Subsampling with k 1 is similar to the Shuffle Gaus- sian Mechanism in the sense that each sample is used in only one random iteration but it maintains independence across samples. We also remark that the second term in (2) is numerically smaller than the first term, so (2) and the aforementioned works are practically the same, while (3) is slightly looser but much more computationally efficient. Remank 3.10. When applying Balanced Iteration Subsam- pling, we could also use a small T and k and compose N sequential training runs, where each run would be one epoch. Doing so would incur slightly higher privacy cost than running TN iterations total and using each data point in &N random iterations, which intuitive because there is less randomeess in the first case when the iterations are organized in smaller epochs. Figure 4 showcases this.
3
2.0
2.5
3.0
3.5 alpha
4.0
4.5
5.0
Figure 2. The c(a) vs a graph for Balanced Iteration Subsampling and Poisson Subsampling, where T = 1000, 100, and o 2. Lower e is better. For large T like this, the noise standard deviation to achieve the same privacy guarantee almost identical.
is better than Poisson Subsampling whenever & 2 0.2 and similarly wins by a larger margin when T very small.
The similarity in performance of these two subsampling methods when T, k are large is intuitive, because the num- ber of times data point gets used by Poisson Subsampling tends to be close to its expectation as the number of iter- ations is large, so the two methods become similar in the limit T + co. Figure 2 shows this.
On the other hand, when T' is small-for example, on the order of 10-there is nontrivial probability that the number of times Poisson Subsampling picks a sample significantly exceeds the expectation, which will leak more information about that particular sample. In these cases, a large a will keenly capture this nontrivial probability of failure, leading to a sharp increase in the RDP privacy guarantee e we can provide for Poisson Subsampling. as illustrated in Figure 3. This comparison also sheds light on why the <Poisson (o:) curve spikes up for large values of a relative to T. Fig- ure 4 showcases the difference between the two subsampling methods when converted to the (c, 6DD domain.
It is natural to compare the privacy guarantee in Theorem 3.8 to Poisson Subsampling, whose RDP privacy guarantee is stated in the below theorem for reference.
Theorem 3.11. (Zhu& & Wang, 2019) The Poisson Subsam- pled Gaussian Mechanism with 12 sensitivity e and subsam- pling rate y satisfies (a, R)- with
<(a) = 1
log (1 -1-1) (1-))0-'(07) +1+1)
a -
More comparisons of these two subsampling methods (both the large and T small cases) can be found the Appendix in Figures and 8.
1(1 1(1-1) - 1)c²)
+ 2
(1 -11-1/ exp
202
In conclusion, we presented Balanced Iteration Subsam- pling as an appealing alternative to Poisson Subsampling with better privacy guarantees, More importantly, we have shown that two completely different sources of randomness in model and data partitioning can have a similar structure underneath and can yield nontrivial privacy amplification
When using the tighter upper bound given by (2), the RDP privacy guarantee of Balanced Iteration Subsampling is al- ways better than Poisson Subsampling, with a small margin when T, A are large and a slightly larger margin when T is very small. The computationally efficient upper bound (3)
6

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
4.5
Balanced Iteration Subsampling
10
4.0
Subsampling
3.5
10
10-5
3.0
epsilon
delta
10
2.0
10
1.5
10
Balanced Iteration Subsampling
Bal. Iter. Subsampling Composed
1.0
10-9
Polsson Subsampling (RDP)
Poisson Subsampling (PLD)
0.5
10-10
40
50
60
70
80
90
100
5
7
10
Total Number of Iterations
alpha
Figure 4. The 5 vs graph for Balanced Iteration Subsampling and Poisson Suhsampling, where 10, = $ 0.4, and 2. Lower d and more iterations better. Balanced Iteration Subsam- pling Composed treats 10 iterations as an epoch, using each sample times in each epoch, and composing multiple epochs together, as suggested in Remark 3.10. Poisson Subsampling accounting done using RDP with Theorem 3.11 and using PLD with Google's PLD library (Google Differential Privacy Tcam, 2024). Under these settings, with commonly used budget 6 10-5 (the dotted line), either method of Balanced Iteration Subsampling is able to perform more iterations out 60.
Figure 3. The c(ax) vs a graph for Balanced Iteration Subsampling and Poisson Subsampling, where T' = 10, k 4, and 2. Lower is better. As a becomes large, Balanced Iteration Subsam- pling starts to perform much better than Poisson Subsampling.
gain via the same analysis.
3.4. Proof Overview of Theorem 3.1
In this final subsection, present overview of the proof of Theorem 3.1.
We first bound D., (Piil))wwhich which we refer to as the forward divergence-wiin the help the following lemmas.
i...d. y it holds that 11) dist. um/ Mjj then Pá
Lemma 3.12. Let P = Σ ViN (pss o2) and Q N (0,0²1) for some vectors μ. 1 I S and probability measure v. Then,
D
Σ Vn (HI))21)
( |N(0002))
20 1 || N ((,, 20
a (22a)))
(a(P
$ D2
Σ uN
His a
log
exp
Σ
for > E
20²
SE|nJo
NET
(.jE(a]
The proof is in Appendix A.2. The mixture centers Sa.b and mixture measure that assigns [ to everything in Theorem 3.1 satisfy the requirement of Lemma 3.13 because Sa, contains all permutations of the vector comprised of k 1s and d - k Os, so by symmetry, under Pg.1% i.idd. v, the distribution of jrJ is invariant given μ4j. Combining Lemma 3.13 with Lemma 3. 12 and plugging in a = 2, we get the following upper bound on the forward divergence.
The proof is in Appendix A. we apply this to the setting in Theorem 3.1. it gives the first item in Eq. (2). Although this gives non-integral representation of D. (P || Q), the time complexity to compute the RHS is still (n))), ), where n is the number of mixtures in P. and in this case, (0) so the time complexity to compute the RHS is O (dkaa, In practice, to do privacy accounting, we need to efficiently calculate Rényi DP for = 2.3..... 100, so we need the following lemma further reduce computation.
Corollary 3.14. Let P and Q be defined the way as in Theorem 3.1. Then,
Lemma 3.13. Let P; N(,, I² for = 1,2....,n be the elements of a mixture of Gaussians. For a mix- ture measure v, if for two randomly chosen mixture centers
k
d - k
ac21
(P S log
(d (
1
exp
20

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
When k = the above is further simplified to
Lemma 3.15 but offset by - 1, so can apply the trans- lational invariance of Renyi divergence.
ac
+ (d (d-11))
log
exp
2
Now we have two multivariate Gaussians with the same mean but different covariance matrices, whose Rényi diver- gence we can also calculate exactly.
Corollary 3.14 merges the summation of (1) terms into a sum of combinatorial terms. A detailed breakdown in Appendix A.3. It can now be computed in (dk) time when >>1 and O(1) time when k: =
Corollary 3.19. Let Q" and P" be defined the same way as in Lemma 3.18. Let Q' and P be defiend the same way as in Lemma 3. 15. Then,
The following lemmas build up the upper bound of Da |I P) P)-which we refer to as the reverse divergence.
Da(Q P') Da(Q" P")
by translational invariance
Lemma 3.15. Let Sa, = {μ E [0,1]² 1= 1 k} be the set of all binary vectors in Rd with l number 1s and k number of Os. Let P = [Ranl Euesan NNc,, 1² and Q- oN(0,01),, where and 0² are constants. Let Q' M[suu Euesar H. I² = NN( (&21,00 be Gaussian centered at the average of P's mixture centers. Then
ac kcdk(d-))
1 $ 2( 2(xx-1 (10 1)
exp
o²d
log
exe
<2k(d-hi 0'
+ (1-1a))
The proof is in Appendix A.8.
Proof of Theorem 3.1. Combining Corollary 3.17 and Corollary 3.19 bounds RHS of Lemma 3.15. Further com- bining with Lemma 3.12 and Corollary 3.14 gives Theo- rem 3.1.
+ (Q 11 P) = + P)
for all a >1
Remark 3.16. The setup in the lemma can be more general- ized, but the current statement is sufficient for our purpose.
4. Experiments
4.1. Model Splitting
Again, the proof is deferred to Appendix A.4. We now seek to calculate or upper bound each of (Q || Q') and (Q' || P) individually. Since Q and Q' are both multi- variate Gaussians with the same covariance matrix, we can compute the exact divergence between them.
In this section, we train ResNet- 101 on CIFAR-10 with model splitting under both centralized setting and federated setting, and analyze their respective privacy guarantees by using the techniques and theoretical results presented in Sec- tions 3.2.1 and 3.2.2. We simulate a differentially private ine-tuning scenario. We split the dataset into two halves, each containing half of the images from each class. We the first half to pre-train the model without DP, but only with 8 of the 10 classes. This non- non-privee on-private pretraining resembles having access to public data with different distribution or a pretrained model for a different task. We end the pre- training when validation accuracy reaches 70%. Then, we use the second half of the dataset for private finetuning. Un- der centralized training, we train for 1000 iterations using (8, 10 10-5)-DP. Under federated training, each user holds 2 samples and we train for 250 sessions. In each training session, each user trains their received model locally for 3 it- erations, sends the model update to the server, and the server aggregates the model updates and adds noise to ensure a user-level (8, 10-5)-DP. To make the training compatible with DP, we replace the batch normalization layers in the model with group normalization layers.
Corollary 3.17. Let Q and Q' be defined the same way as in Lemma 3.15. We have
Da(Q k2
202dd
proof is in Appendix A.6.
The following lemma deals with the second addend on the RHS of Lemma 3.15.
Lemma 3.18. Let Sa,= = (u 10, || k} be the set of all binary vectors in Rd with i number of is and d - lo number of Os. For some fixed constants c, a 1 EpeSa, P 5/2 be the mean of Sa,k Ler let po =B.
p" Saxl EyESSu N[c(H - Ho), Ia) be a mixture of Gaussians with centers Sa.k normalized to have a mean of O and scaled by e. Let Q" = ~N0,,² Then,
DQ" || Pd) s D. (Q" N (0.0² exp
(k(d-k) o
Ia
We compare three solutions. The first "baseline" uses inde- pendent subnet training for private fine-tuning as introduced in Section 3.2.2 but the privacy analysis is done with exist- ing tools (i.e., the standard RDP accounting for SP- pipeline). The second "amplification" uses the same exact
for all a 2 2.
The proof is again deferred to Appendix A.7. Note that Q" and p" in Lemma are the same as Q' and in
8

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
4.2. Balanced Iteration Subsampling
Table Comparison of three domain adaptation methods with data subsampling rate of 0.1, under centralized setting for sample- level (8, 10 DDD. Noise standard deviation is relative to the clipping norm (and already divided by expected batch size). Val- idation accuracies are best of random seeds and have standard deviations around 0.7%.
We experimented with differentially private training using Balanced Iteration Subsampling vs Poisson Subsampling as the data subsampling technique. Since the number of training iterations is large (on the order of 1000), the two methods have a similar training dynamic and privacy guar- antec. In particular, the noise standard deviations differ from each other by less than 1% (similar to Figure 8b). Thus, the statistics of the validation accuracy show little difference. For training WideResNet-40-44 from scratch on CIFAR-10, 10, (8, 18.10-5p 18,10-5j-DD DDP 2000 iterations, using each sample 655 times for Balanced Iteration Subsampling and with probability 655 in each iteration for Poisson Subsampling. Balanced 2000
# VALIDATION ACCURACY
NOISE STD. DEV.
ADDRESSES LIMITED COMPUTE?
METHOD
SUB- MODELS
BASELINE
79.80%
6.02 x 10"1
AMPLIFICATION
82.43%
5.44 10
(OURS)
BASELINE
76.80%
6.62 10
V
Iteration Subsampling injects noise with o = 10.17 for val- idation accuracy of 70.21%, while Poisson Subsampling injects noise with σ 10.20 for validation accuracy of 70. 13%. For finetuning ResNet-101 (using the same setting as Section 4.1 but without model splitting), Balanced Itera- tion Subsampling injects noise with 2.36 for validation accuracy of 84.86%, while Poisson Subsampling injects noise with a = 2.34 for validation accuracy of 84.99%. The results are best of 3 random seeds. This shows that the two subsampling methods achieve very similar privacy-aceuracy tradeoff's experimentally, which reinforces our point that Balanced Iteration Subsampling is valid alternative when we cannot apply Poisson Subsampling.
AMPLIRICATION
80.52%
1.96 x 10
VV
(OURS)
RELAXATION 84.99%
6.62 x 10-4
X
Table 2. Comparison of three domain adaptation methods under federated setting for user-level (8, 10 10- Noise standard de- viation is relative to the clipping norm (and already divided by number of users). Validation accuracies are best of 3 random seeds and have standard deviations around 0.7%
# or SUB- MODELS
VALIDATION ACCURACY
NOISE STD, DEV.
ADDRESSES LIMITED COMPUTE?
METHOD
5. Conclusion
BASELINE
78.47%
6.75 x 10"*
In this work, we identify and leverage the inherent random- ness in ML training algorithms for privacy amplification. These sources of randomness emerge whenever each sample interacts with randomly selected portion of the training process, whether through submodels or structured subsam- pling, However, existing methods have not fully captured these effects. We introduce a mathematical framework to quantify the privacy gains achieved through model splitting and dropout- two techniques used in federated learning that help reduce computational and communication costs- as well through Balanced Iteration Subsampling, an alterna- tive to Poisson Subsampling that provides improved privacy guarantees in certain regimes.
AMPLUTCCTION
80.28%
5.72 10
(OURS)
BASELINE
76.96%
6.75 10
V
AMPLIRICATION
79. 1%
5.36 x 10
V
(OURS)
RELAXATION
82.18%
6.75 x 10-
X
training method but privacy accounting is done with our method in Section 3.2. In both cases, we do not split the first 5 and last 2 blocks of ResNet-101 but partition the middle 22 blocks into three or eight disjoint sets to form subnetworks, one of which is then randomly assigned to each sample. The third "relaxation" assumes client compute is not a problem and each client tunes the full model (with- out model splitting). The results are shown in Table for centralized setting and Table 2 for federated setting, The results of this experiment show that in both setting, the use of model parallelism techniques to handle limited client compute is a viable strategy with some decrease in overall accuracy due to model splitting, but our privacy amplifica- tion technique improves the accuracy of model splitting by allowing to inject less noise for the same privacy guarantee.
This work makes one step forward to systematically quanti- fying all forms of randomness encountered in training and their contributions to privacy amplification. To this end, we provide a deeper understanding of how structured ran- domness enhances more rigorous analysis of these interactions will lead to better thcoretical bounds and improved implementations of preeeccire methods. A promising future direction is to extend this framework to other training paradigms, further strengthening the connection between structured random- ness and differential privacy.
machine learning. A

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Acknowledgments
Canonne, C. L., Kamath, G., and Steinke, T. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676-15688 2020.
This work was partially supported by the NSF grant CIF- 2213223.
Some of the computing for this project was performed on the Sherlock cluster. We would like to thank Stanford University and the Stanford Research Computing Center for providing computational resources and support that contributed to these research results.
Chen, W.-N., Isik, B., Kairouz, P., No, A., Oh, S., and Xu, Improved communication-priveie trade-off's in 1.2 mean estimation under streaming differential privacy, arXiv preprint arXiv:2405.02341 2024a.
Chen, W.-N., Song, D., Ozgur, A., and Kairouz, P. Privacy amplification via compression: Achieving the optimal arvvcc-aceuracy accurrccy-commuiicatio trade-off in distributed mean estimation. Advances in Neural Information Pro- cessing Systems, 36, 2024b.
Impact Statement
This work represents an important first step in quantifying the privacy amplification effects of model parallelism meth- ods, offering new insights into enhancing pereeeevii machine learning. By leveraging the inherent randomness in model partitioning and subsampling, our approach con- tributes to the development of more secure and efficient distributed learning frameworks, particularly federated learning settings. This study lays the groundwork for further exploration into the interplay between model parallelism and differential privacy, fostering ongoing innovation in privacy-preserving AI.
Chua, I.,, Ghazi, B., Kamath, P., Kumar, R., Manurangsi, P., Sinha, A., and Zhang, C. How private are dp-sgd implementations? In Forty-first International Conference Machine Learning.
Dun, C., Wolfe, C. R., Jermaine, C. M., and Kyrillidis, Resist: Layer- wise decomposition of resnets for dis- tributed training. In Uncertainty in Artificial Intelligence, pp.
PMLR, 2022.
References
Durrieu, J.-L., Thiran, J.-P., and Kelly. F. Lower and upper bounds for approximation of the kullback-leibler diver- gence between gaussian mixture models. In 2012 IEEE International Conference Acoustics, Speech and Sig- nal Processing (ICASSP), pp. 1433-4836.. Iece, 2012.
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L.. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Dwork, C. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Asoodeh, S., Liao, J., Calmon, F. P., Kosut, O., and Sankar, L. A better bound gives a hundred rounds: Enhanced privacy guarantees via f-divergences. In 2020 IEEE In- fernational Symposium Information Theory (ISIT). pp- 920-925. IEEE, 2020.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrat- ing noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284- Springer, 2006.
Balle, B., Barthe, G., and Gaboardi, M. Privacy amplifica- tion by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
Erlingsson, U. Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. Amplification by shuffling: From local to central differential privacy via anonymity. Proceedings of the Thirtieth Annual ACM-SIAM Sym- posium on Discrete Algorithms, pp. 3468-2477 SIAM, 2019.
Balle, B., Kairouz, P., McMahan, B., Thakkar, O., and Guha Thakurta, Privacy amplification via random check-ins. Advances in Neural Information Processing Systems, 33:4623-4634 2020.
Fang, W., Han, D.-.,, and Brinton, C. G. Submodel par- titioning in hicrarchical federated learning: Algorithm design and convergence analysis. ICC 2024-IEEE In- ternational Conference on Communications, pp. 268 273. IEFE, 2024.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foun- dations of computer science, pp. 464-473. IEEE, 2014.
Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, pp. 635-658. Springer, 2016.
Feldman, V. and Shenfeld, M. Privacy amplification by random allocation. arXiv preprint arXiv:2502.08200 2025.
10

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Feldman, V., McMillan, A., and Talwar, K. Hiding among the clones: A simple and nearly optimal analysis of pri- vacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 954-964. IEEE, 2022.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What we learn privately? SIAM Journal Computing, 40(3):993-826, 2011.
Konečný, J.
Federated learning: Strategies for im- proving communication efficiency. arXiv preprint arXiv: 1.XX::0610 2016.
Feldman, V., McMillan, A., and Talwar, K. Stronger pri- vacy amplification by shuffling for rényi and upproximate differential privacy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4966 4986.-998.100 SIAM, 2023.
Li, N., Qardaji, W., and Su, D. On sampling, anonymization, and differential privacy or, k-anonymization meets differ- ential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pp. 32-33, 2012.
Ganaie, M. A., Hu, M.. Malik, A. K., Tanveer, M., and Suganthan, P. N. Ensemble deep learning: A review. Engineering Applications of Artificial Intelligence, 115: 105151, 2022.
Liew, S. P. and Takahashi, T. Shuffle gaussian mechanism for differential privacy. arXiv preprint arXiv:2206.09569, 2022.
Gil, M., Alajaji. F., and Linder, T. Rényi divergence mea- sures for commonly used univariate continuous distribu- tions. Information Sciences, 249:124-131, 2013.
Michalowicz, J. V., Nichols. J. M., and Bucholtz, F. Calcu- lation of differential entropy for a mixed gaussian distri- bution. Entropy, 10(3):200, 2008
Girgis, A., Data, D., Diggavi, S., Kairouz, P., and Suresh, A. T. Shuffled model of differential privacy in federated learning. In International Conference on Artificial Intelli- gence and Statistics, pp.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263- 275. IEEE, 2017
PMLR, 2021a.
Girgis, A. M., Data, D., Diggavi, S., Suresh, A. T., and Kairouz, P. On the renyi differential privacy of the shuffle model. In Proceedings of the 2021 ACM SIGSAC con- ference on computer and communications security, pp- 2321-2341, 2021b.
Mironov, I., Talwar, K., and Zhang, L. Rényi differential pri- vacy of the sampled gaussian mechanism. arXiv preprint arXiv: /908. 10530, 2019.
Nielsen, F. and Sun, K. Guaranteed bounds on the kullback- leibler divergence of univariate mixtures. IEEE Signal Processing Letters, 23(11):1543-1545 2016a.
Google Differential Privacy Team. Google differential pri- vacy library, 2024. URL https: /ttp://gitttt thub. com/ google/ http://ifffeeeetalaalaaaaeeee 27, 2025.
Accessed: Feb
Nielsen, F. and Sun, K. Guaranteed bounds on the kullback-leibler divergence of univariate mixtures us- ing piecewise tog-sum-exp exp inequalities. arXiv preprint arXiv: 160.008000 2016b.
Guliani, D., Zhou, L.,, Ryu, C., Yang, T.-J., Zhang, H., Xiao, Y., Beaufays, F., and Motta, G. Enabling on-device train- ing of speech recognition models with federated dropout. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8757-8761. IEEE, 2022.
Rényi, A. On measures of entropy and information. In Pro- ceedings of the fourth Berkeley symposium on mathemati- cal statistics and probability, volume I: contributions the theory of statisties, volume 4, pp. 547-562. University of California Press, 1961.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual leam- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Sagi, O. and Rokach, L. Ensemble learning: A survey. Wiley interdisciplinary reviews: data mining and knowledge discovery, 8(4):e1249 2018.
Hinton, G. E., Srivastava, N., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. R. Improving neural networks by preventing co-adaptation of feature detectors. arxiv 2012. arXiv preprint 1207.0:207.058// 2012.
Wang. Y.-X., Fienberg, S., and Smola, A. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pp. PMLR, 2015.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. Foundations and trends& in machine learning, 14(1-2):1-210, 2021.
Wang, Y.-X., Balle, B., and Kasiviswanathan, S. P. Subsam- pled rényi differential privacy and analytical moments accountant. In The 22nd international conference on arti- ficial intelligence and statistics, pp. 1226-1235 PMLR, 2019.

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Wen, D., Jeon, K.-J., and Huang, K. Federated dropout-a simple approach for enabling federated learning source constrained devices. IEEE wireless communica- tions letters, 11(5):923-99 99779927777.. 2022.
Yuan, B., Wolfe, C. R., Dun, C., Tang, Y., Kyrillidis, A., and Jermaine, C. Distributed learning of fully connected neural networks using independent subnet training. Pro- ceedings of the VLDB Endowment, 2022.
Zhu, Y. and Wang, Y.-X. Poission subsampled rényi differ- ential privacy. In International Conference on Machine Learning, pp. 7634-7642. PMLR, 2019.
12

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
A. Proofs.
A.1. Proof of Lemma 3.12
Let be the dimension of p4. Then,
(a(PI
a log
da
Rdd
11l12-(a 1)1|=r|12 )) da
log
(2TT2)3
Ui
exp
2x
Rd
IE(r]a
iEl
TE!
1 1ulle- 1)11=1122 )) dx
log
exp
Σ iE!
(2TT2))
20
IE[n]
Rd
log
II VEET
Σ
2x
/E[n]"
The T in the superscript means transpose. The second line comes from expanding the exponentials. The third line comes from linearity. The fourth line comes from completing the squares then integrating multivariate Gaussian densities.
A.2. Proof of Lemma 3.13
Apply Lemma 3.12 to both sides and replace y with the uniform distribution to get
v )
D.
log
Σ
exp
Σ
(4)
TE(N)
i.E(al) ic!
Similarly,
D2
Σ
pi:
-0
|
N
00,
20 2
))
llog
n²
Σ exp
Φ2 2 14] (11111)) 112 )
1
SE(n]2
Exponentiating both sides and rearranging, want to show that
gZ 2 1² 1711i1 p12 ))
Σ
Σ
Σ
1 a
exp
exp
n
LjE(a), icj
rE[n]2
Notice that the LHS is the MGF
M! of the random variable
X= Σ
Pl,
AjEla),
where 7 ~ Uni]([ and / = 1. uT, uT, where T ~ (ni]([n] i.c.
72. The RHS is likewise the MGF (y of Y, who is the sum of a i.i.d. copies of
Y
1T PT
2
where 7 L.d. Unif (In]²) for k = 1,2, 1,2..... 1, and Next, since each entry of T is chosen according to v and we can set Th to be equal to Tl for k = .,..., and leave Y with the same distribution (and thus the same MGF). Next, since now the Tt's are the same, we can set up bijection between outcomes of and the outcomes of Tę follows:
dist. we assume that p. 11 My for Pg: ph
(J,, Iz, Ts, J4....,Ta) - (TH,T), T2 T
T
1
13

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
and can verify that both random objects follow the same distribution Uni(([n])). This means if now let / Uni[([n]9) and
x=
ML, isj
E
Y=
PL.
these two random variables would have the same distribution as first specified. Next, we condition on specific histogram (where histogram is defined the above section). The random variable a constant as X sums up all pair-wist wise correlations no matter the order. On the other hand, the distribution of Y is non-trivial but has mean equal X because can rewrite and as
a X
Y, Σ M,,u 11,00s
Σ
Yj,
a Y
2
and the Yj's have the same distribution given h. So, we have
Bie"
2 e [B|||]]
Eietx h] for 2 0.
Note that / 2 0 is always satisfied as /. = 1 0²
2 O. With the Law of Iterated Expectations,
(t) En Eyle |t]]] 2 E,
[e ex | Ni] Mx(().
A.3. Proof of Corollary 3.14
The mixture centers of P are
(0.
1)2
Σ U/ h
Combining Lemma 3.13 and Equation 4, we have the following upper bound on the forward divergence:
D. (P < log
exp 20244(1))
First, since Sa, contains all permutations of binary vectors with 1s, by symmetry, the value of Ei= exp @ (GTHT11) 11) is dependent on μs, so we reduce
12
(g
log
exp
j=1
Next, we count how many ways ETy can equal 2l for 0 < S k. The vector My needs to have number of is in the first entries, and the rest k - number of is in the last d k entries, giving a total of (+) (d=h) ways. So,
k
d d k k
ac
D&(PI log
exp
(5)
20
t=0
In the case that (used in model splitting), the above is further reduced to
log
a
1 d (d-1)
(0)
exp(0) (1)(d=
d
1
exp
20
ac²
))
log
exp
2
ac²
+
(d
(d-1))
14

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
A.4. Proof of Lemma 3.15
Without loss of generality, let is scaling factor for all Gaussian centers so we can instead re-scale the standard deviation to achieve the same effect. To prove the lemma, we apply an offset vector
d 1 to the integrand of (Q, P),
II exp
20 (2t )
Da(Q' P) = - log
(2ma?)-
dei dra
a-1
Bd [Sa.kl EpESa,e
Il:= exp
(- 2n2 (z; - -1s)3)
d exp
1
(3) a/b + d )
log
(2TT²)
20
dx daa
Rd [Sa.kl EpESa,e
exp exx=
(-
(x; - M4 + (g) 2) 11000
2
In the exponents of the numerator,
k
ka
2
k
2 01)
k x + 2 1) +
kk (a (2
The numerator can then be re-written
d
(- 202
k (d (a-1)) )
II exp
1
2
II exp (_20
k alla 1)1s
ad (a
20
202
exp
In the exponents of the denominator, μu is either or 0 since μ is binary vector. Case by case,
[x: 1+ ka
ka
2 ha
ka
(x; 162-177 1)2 +
+
d
d
d
and
+ ka
ka d
ka
2
x² +
Since every y contains è number of is and d k number of Os, exactly & of the terms in the product have the former form and the rest d - k terms have the latter form. We can re-write the denominator as
a-1
II
1 202
(z; - 12)²)
2o2 2 1)2s)
exp
exp
|Sa.k]
MESa, 1=1
202 (a 1) (al (a ((Kka)²
1
ka
))
exp
2k
d
The middle terms in the numerator and denominator the they cancel out, leaving with
The exp
(-2g 20 x?²)
Da(Q' P) a
1
log (2
I exp (- 2タ (x; 14)2) a- dx. .ra
Epesaa
Sa,
श ad (a(aa - -1))
exp
1 (a - 1) d ( 2 2k ko
exp
20
[Te exp (- + 1
1
log (2TO²)-3
a- day dra
I exp (- L (z: - ]1)3]]
[a EpeSun
Rd
15

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
1
exp
20²
1
ad
(ğ(a - 11)
+
log
1
exp
20
(a 1) (dl (d(=2)
2h
12 2 a a(a - 1)3)
1
exp
Da(Q P) --1
log
exp
2 d
u((a - 1)((r - 2))
Da(Q P) + log
1
exp
20 d
1 h2
a((a - -1)
Da(Q P) 20 d
DD(Q a
k
0
1
20
Da(Q P) - (Q(Q)Q)).
A.5. Rényi Divergence between Two Multivariate Gaussians
Proposition A.1. (Gil et al., 2013) Let Si = NN E) and f3 = NNji E) be two multivariate Gaussian distributions with the same covariance matrix and different means. Then,
Da(Ei ll [;) 2 7 - 111)) 15) M4))-
Proposition A.2. (Gil et al., 2013) Let f; = (1,,, Eg) and fj = (u, Eÿ) be two multivariate Gaussian distributions with the same mean. Then,
1
Σ 1-a Eg l
Dalfi fz) 2(a -1 log
(2ix)²
for
= = + (1- (1--a) a)L;
whenever a'. + (1 a)2, is positive definite.
A.6. Proof of Corollary 3.17
The two distributions N (0, o² and Q' =N (= 1,22). Using Proposition A.1,
Da(Q110) = a ck
11 (021) -1 ck
ac²k²
d
k²
Σ 0²
2 d
7
20
2nd
i=1
A.7. Proof of Lemma 3.18
The set Sa, = {u E {0, 13d || k} lies in a subspace of [R with dimension d - because there is one and only one sum constraint on the entries, which removes one degree of freedom. Since we also offset Sa, by its mean when forming the mixture centers of p" the zero vector also lies in the same subspace as S - μ. The following lemma establishes that we can instead look at Renyi divergence on the 1-dimensional subspace instead of Rdd.
Lemma A.3. Let Sa-1 be set points in Rd-1 and Sa be the set of points Rdd, where each point's 's last component O. Then,
|
Da (0
Σ (( = D. (o
EN(HOOTTa)
SSa-1l
Saa-ll
uESa-1
neSa
for all a
16

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Proof. For notational convenience, let wi:d-1 be the vector formed by taking the first d - components of x where R4
N (0,
Σ Nu(,O'l
Do
18a-1l
HESA
a log / (2TO2)
1
exp (- 2a ||=11]]
a-1 dæ ... dx
18a 1 Euesa exp (- 1-2 || - mm13)
/ (2TTO2)
1 log
(expl (- 2n2 (112 112 (x]))))))
[Sa-1 Epes, exp (- -6 (1| - Hiid-1 - (aad)))a))) a-I dr dr
0
1 log /
22
st
(exp (-
2n
1 111dd-
exp (- 2 x2))
a-I day ... dx
0
SSa-1 Eues, exp (- 20 F1dd11
Mi.d
exp (-2 x
1 log
/ (2TO+))
$
(exp
1 |11dd 111)) 2n
20 u2 dæi daa
1
a-I exp
a
[Sa-1] Evesa-i exp (- 20 F1:dd1 1 v113)
1 log /
d=1
(exp (- 2 |1
(2TTO2)
20 111 a-1 dz ... dr
a
15--1l Evesa exp
Do
N (0.02la-)))
Σ MESa-1
N (H, o
Sa-1l
Below the proof for Lemma 3.18.
Let pm (0, o² exp c )) We first establish that P0( pM' (0) S (0) To see that fact, the set S., is
a set that contains all vectors with & entries equal to c(d-k) and d - k entries equal to
ak d so
( (-11
- k))2 (d
22k2
(d - 13)) = (2 exp d²
(- 1
c²k(d k))
(0) = -(2mo²) cxp
cxp
2222 20
d²
k
20
d
ck(d- -k)
)
4
2kld =P"(
(0)
12T exp
exp
(2TO²) exp
0212
202d
= - 2 PO)
To the proof, first look the simple case when d = 2 and 1/ 1 so Sa, contains two elements. By Lemma A.3, we can reduce the dimension by and look at the scalar case where P" where we w.l.o.g. scale such that P has mixture centers at - and since scaling e by / is equivalent to scaling by 3- Then, p is a Gaussian centered at 0 and having variance o² exp (+) > o² such that ("= = (0). Since p has smaller variance compared to a and has mixture centers that surround 0 on both sides, as |x co, for small values of |z], (==)(=) either increases, or decreases slower than ( and for large values of |z] P"=z(2) decreases much faster than Piz (I)). Combined with the fact that P²=(0) = ( this means there exists constant a such that (T) 2 P (z)) for x E [0, a] and (x) PM for x E (a, oo). To complete the argument,
(N( (N 1o)))
and Q% = -0 o²),
1
Da(22 || PTZ2) (Q P(
17

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
(1))
(2)2(1)0
2i=2(1 (x)2(==)111 dæ d=2 (z)a--
P (d-2(x)
d 2z)2
du ua-1 dude
by the Fundamental Theorem of Calculus
P (=) P.
Q (Giz((o) (a-1) 1)
dudæ
u
(()
Pai=(())
Pdzz(1)
(2)=a a
22(a 11)
dudr
dudx
-(x).
1
(a)
(ain(())
Since (1)
and 2 (x)
are both decreasing functions in x for have for 20p E [0, a] and æn E (a, 00),
P (x) (=)
QoLz(ou) (z0) (z0)
(~1((1)) (2))(
(x1)
(z1)
so the first integrand is always greater than or equal to the second integrand in (+). Finally, since P and P are probability densities and need to integrate to the same value of 1,
Pizzle)
dudx - -fe (
- dudr 0,
Pr PT
so it follows that (+) 2 O. It is worthwhile to note the intuition behind the proof. Of Q", P", and p" the distribution Q" assigns the most probability mass near 0. So, to minimize D(Q" || P") over P", P needs to assigns more probability mass near O. And between p" and p"" the distribution p" is the one that assigns more mass around because they have the same value but moving away from 0 any direction is closer (at least) one of p"'s mixture centers, so around 0, pd always dominates pM so (Q" || P") < D(Q" || p" The same argument holds true for arbitrary d, k since the mixture centers of p" surrounds O, so along any ray from 0, there exists such that P" (x) 2 p" for x E [0, a). and the claim follows.
A.8. Proof of Corollary 3.19 In the context of Proposition A.2, have
(kk(d-k) 0212
(Ea)² o²² (aexp
Ckidd ck(d-k)) a1)
Σ =o2
Σg o² exp
exp
Ta.
la:
0212
(k(dd-))
+ (1- d
2hild k)a O²d
(Ea)*) = 2d
exe
2_1=-a-2d(11-00 2d((1-a),
E 0 2da exp
d²d²
So, by Lemma 3.18 and Proposition A.2,
Da(Q" || P") < Do
(0"
0, 0f exp
( (2 - (k)(d--b) 1b)
La)
o²d2
ac k(d-k)
1 log
1--aa E a
exp
2(a - 1) log
2(a= 1)
(Ea))
(aexp
[klld=k)) + (1 aa) r.
d'
18

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
A.9. Proof of Theorem 3.4
Let T'' e [d]lš] be a random vector with [S| entries, where the kth entry denotes which submodel is used to train data point k. Let S [d] + R be the gradient function that takes in the dataset and the model correspondence for the first [S] data points, and outputs the resulting non-noisy sum of gradients. That means, the output of f(S, T)) is deterministic and f("', T) is random value that depends on which model is assigned to the last data point The function f satisfies bounded difference as a result of gradient norm clipping of c. That is,
II((S', S(S, T) e
for all adjacent datasets S' and T. We express the output of M mixture of distributions,
M(S) E (I(S,T),oOT)
M(S) EPN (f(S" (T.
T
By the quasi-convexity of Renyi divergence,
Da(M(S) M(S)) z sup (f( (f(S' = sup Da (N (W | (f(S',T) - f(S,T),
where the last line comes as a result of the translational invariance of Renyi divergence.
The first term is a Gaussian centered at 0 and the second term is a mixture of Gaussians centered at the possible outcomes of f(S', T) - f(S, T), which has d different outcomes corresponding to which of the d models the data point ø is trained on, each with probability 1. The d different outcomes have disjoint support because the model parameters of the d submodels are disjoint. Let the non-zero parts of these outcomes be c1...., Cd such that ||c/||5 e for all S k S d. Since the covariances are symmetrie, we can apply rotation each of the different supports-and leave the first term N' (0, 1) unchanged that C becomes ||cx|/ez, where ejis the first standard basis. Now in each of the supports, the first and second terms are both product distributions that are different in the first entry and identical in the rest, so we can drop the coordinates where they are the same. The divergence thus becomes
Da (N(O, 02) 1 N (Ic)lle..'1)
Da(M(S) || M(S)) E
sup
||e Cellsse...lllllllss
Setting ||a||== ... ||ca|== would achieve the supremum since they give the maximum divergence from 0,
Da(M(S) I| M(S') D. (
Σ N (2))
where the first term matches Q and the second term matches P in Theorem 3.1 where k = 1. Switching the order of M(S) and M(S") requires a similar analysis, with the first and second terms switched. Thus,
= max ((S)M M(S))
S max (D.(PIQ))..(Q) P)).
A. Proof of Theorem 3.5
If we condition on how the model is split into submodels, then the privacy guarantee is given by Theorem 3.4, which does not depend on how the model is split. Therefore, if we do not condition on how the model is split, the resulting distribution of the submodel is a mixture of the conditional distributions, so the resulting distribution of the gradients is a mixture of the resulting conditional distributions of gradients, conditioned on how the model is split. Thus, by the quasi-convexity of Rényi divergence, the divergence between the unconditional distributions of gradients (resulting from using S vs S' for the dataset) is bounded by the max divergence between the conditional distributions of gradients, which is given in Theorem 3.4.
19

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
A.11. Proof of Theorem 3.7
The full proof has a lot of similarities the proof of Theorem 3.4, which we will not repeat but only focus on the different part.
We first consider the case of one dropout layer then the case of multiple dropout layers.
For one dropout layer, if we let the nodes of the dropout layer be UI...., Un and let the set of weights whose gradients are set to 0 by dropping node uk be W for = ........ n. then W1,..., Wn are disjoint sets that cover the parameters of the preceding and succeeding layers. Let the combined parameters of the preceding and succeeding layers be W such that W = UK== Wk- The set of weights W can be treated as full model for the scope of this proof since has its own gradient clipping norm c. Consider particular outcome of the dropout layer that keeps nodes {vi Jie. for some J [n], which is equivalent to forming a submodel W, = UşeJ W,. Consider the complementary submodel W UUee W, W W Then, conditioned on the event that the submodel formed by the dropout layer is either W, or Wy, each has conditional probability of 0.5 because each has the same unconditional probability of (0.5)", so W, and Wy form one way to partition the model. Then, the dropout layer is a mixture of W and Wy for all possible J, and thus Theorem 3.5 applies where = 2.
For the case of multiple dropout layers, if the dropout layers have no overlapping parameters whose gradients are directly affected (i.e., whose gradient will be 0 if a node it connects is dropped out), then the analysis remains the same. If there are, for example in the case where two dropout layers are applied to the input and output of another layer, then conditioned on .J (where J is now a subset of nodes in the union of the two dropout layers), the submodels UJe, W and jeg W, no longer cover W but are still disjoint, so the analysis to quantify the divergence between the two conditional distributions of gradients (conditioned on J) using Theorem 3.1 is still valid, since the gradients not covered by either the submodels are 0 regardless of which dataset is used, so we can throw away these coordinates in analyzing the Rényi divergence.
A.12. Proof of Theorem 3.8
Consider two adjacent datasets S, E S, where S" = S {-]] Let A E |xT be the random sampling matrix, whose entries are binary and each row contains iteration, and otherwise. Let As be the first [S] rows of A and A|ss be the last row of A, where A|s') will be disregarded if the dataset is S. Let P denote the implied distribution of any function of A. Let d be the number of parameters in the neural network with a gradient. Let Y2 E Rdd be the noisy of gradients in iteration t. Let gi be the gradient function of the tth iteration, which take in as inputs S or S' (the dataset), A., (the sampling mask used in this iteration), and yi,-.. - (the previous gradients, or equivalently, the previous model updates), and satisfies that
and T Os, where the entry at i, is if the ith data point is used in the ith
l9 (S, A.,i,,,,....... Ue) 9e (S' A,, ... 10ll c
for all (, A,,,, Ut. which follows from la norm clipping of each gradient. Let Po Yr) be the joint distribution of the noise gradients if S is used, and QY(Y)..... Yr) if S' is used. Their distributions can be written
Po ..... Yr)= Σ
P(As) ...... Yr As)
Ag
and
Qo Yr) Σ P(A)) Σ P (A Qo(Yi........................... ..... Yr As, A(s1).
As
Assi1
Since Renyi divergence is quasi-convex, the Renyi divergence between Po ... Yr) and Qo.Y,...., VY) ) is upper bounded by
(Po || Qo) S sup D.
[P(Yi,...,, Yr As)
Σ A
P (Aist) Qo Qo(Y,...,, Yr A) A1)
Ag
1
Po Ag)
sup Ag
log
.r A)) dy ... dyT
0 (Emooy P (A)ss) Qo( ..........
20

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Th- Polue yi.... 1,-1,, As) P ( s IT= Qolye ,1,...,,tt1 A))a
= sup As a -
log (EA(8)
dyi oth..ddyr dyr (+).
The conditional distributions in the numerator and denominator are
Polye 9i..... M.......-M..As! NV Mi.............................. B1-1), o²Ia), Qo(ye ,
A) (or("S, A, ..... 1t-1), 0² Td).
Consider the substitution
2t = = - yー (5 A.::; :1::............................ 1/--1)
so that
Po(æt 11.....,9-1.... As) NO0, o²Ia).
Qo(at ,1....,,B-1,,4 A) (V A.,181
............................ ,... .1-11 go A. ........ Vb-1), ,.....,
oa1a)
N(am, dala)
A A
N(0, 02
A = 0
(Aeel.i)) T²1a)
where e S and ||, both of which may depend on A. .I...... Mt-1- Also, since there a bijection between 2, and Yt given A, yi...., 9t-1, by recursive argument, there is bijection between 21...., Ie and y1,.... yt given A for all t, Thus, the conditioning ,/....,, V is equivalent conditioning $1...., 2t
write
Po(v y1....., V1-1: As) Po(y ; As).
Qo(ye y/, -1.-..,-t-1,, A) Qo x1. 21. A).
Lastly, for each variable ye in the integration in (+), we replace it by - 9e (S. A. Vi....... 11-1). (t-1)) The integration over y on Rd so the new integration region over y1- (S, A. 11-1) is still on Rd. Then we apply the substitutions,
II Po(x, I: (AA))) II Qo(a, f1,..., A)) A))a
(+) = sup
log
day .d.
As
EAper
ssup
log
dr ... dxy (Es(sr) ((A II Ni {A (1)) 02
As Q
sup Dr Ag
Σ PP (A1s II W(cvvl [119)=11) oala)
A
sup S.Sc |1
Da
I daaaa)
Σ p (A sr)) Al8
II Necnll (A0)), d²la) (**)
where the second-to-last line, P (A(ss) is a constant that does not depend on the choice of As, and the only item that depends on As is C, The supremum is achieved by the choice of o, and v, such that & = and v; = e, (or any vector with norm 1, but all are equivalent due to the rotation symmetry [[", (O, d² around 0). Then, since Z1.... : TT either e; 0 under Qo and 0 under Po. only need to integrate components since the rest have the same distribution under Pu and Qu. So,
their first components and ignore the rest
T II -
T
(+*) < D.
(V(00 02)
Σ P (AIS4) II [N(ee
[ o2)
1189
21

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
T
T II
= Da
II O(
Σ
Wiel = 13. of)
MEST.
r=1
Da
(N(0,
Σ MESr.e
Nien, I²)
=Da(P
The same proof goes for Da(Q P) by switching the numerator and denominator, and taking the maximum the two completes the proof.
22

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
B. More Graphs.
Our Accounting for Submodels
Accounting for Submodels
17.5
Our Accounting for Submodels
Accounting Submodels
Our Accounting for Submodels
Epsilon Privacy Budget
15.0
Our Accounting for 8 Submodels
Accounting for Submodels
Epsilon Privacy Budget
12-
Our Accounting for 8 Submodels Standard DP-SGD Accounting
Standard DP-SGD Accounting
12.5
10
5.0
2.5
2
1.0
Noise Standard Deviation
Noise Standard Deviation
(a) The graph compares the noise standard deviation vs the privacy cost in (e, 8)D with and without applying amplification, where 8 = 10 and we train for 400 iterations. The data Poisson subsampled with rate 0.1. Lower and less noise are better.
(b) The graph compares the noise standard deviation vs the e privacy cost in (c, 6)DDP with and without applying plification, where 6 10-5 and we train for 2000 iterations. The data is Poisson subsampled with rate 0.1. Lower and less noise are better.
10
Our Accounting for Submodels
Our Accounting for Submodels
Our Accounting for 4 Submodels
Our Accounting for 4 Submodels
Epsilon Privacy Budget
Our Accounting for Submodels
Epsilon Privacy Budget
10
Our Accounting for Submodels
8-
Our Accounting for Submodels Standard DP-SGD Accounting
Our Accounting for Submadels Standard DP-SGD Accounting
8-
4-
2-
2
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
Noise Standard Deviation
Noise Standard Deviation
(c) The graph compares the noise standard deviation vs the privacy cost in (e, 8)PDP with and without applying our am- plification, where 8 = 10-6 and train for 1500 iterations. The data Poisson subsampled with rate 0.08. Lower and less noise are better.
(d) The graph compares the noise standard deviation vs the privacy cost in (r, OD- with and without applying our amplification, where = 10-5 and train for 600 iterations. The data Poisson subsampled with rate 0.15. Lower and less noise are better.
Figure S. More comparison for disjoint submodel splitting.
23

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Submodels
Our Accounting with 2 Submodels
700
Our Accounting with 4 Submodels
4000
Our Accounting with 4 Submodels
Number of iterations
Our Accounting with 6 Submodels
Total T Number of iterations
Our Accounting with 6 Submodels
600
Our Accounting with 8 Submodels
Accounting
Standard DP-SGD Accounting
Standard DP-SGD Accounting
500
400
2000
200
100
0
3.0
3.5
4.0
4.5
5.0
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Noise Standard Deviation
Noise Standard Deviation
(a) The graph compares the noise standard deviation the number of training iterations with and without applying amplification, where (c, (I, (1,10-5) 10-5). The data Poisson subsampled with rate 0.1. More iterations and less noise are hetter.
(b) The graph compares the noise standard deviation the number of training iterations with and without applying amplification, where (c, 6) = (3, 10- The data Poisson
subsampled with rate 0.1. More iterations and less noise are better.
Our Accounting with Submodels
2500
Our Accounting with 2 Submodels
4000
Our Accounting with Submodels
Our Accounting with 4 Submodels
Number of Iterations
Our Accounting with Submodels
Total Number of Iterations
Our Accounting with Submodels
2000
Accounting Submodels
Accounting Submodels Standard DP-SGD Accounting
Standard DP-SGD Accounting
3000
1500
2000
1000
500
1.0
1.5
2.0
2.5
3.0
4.0
Noise Standard Deviation
Noise Standard Deviation
(c) The graph compares the noise standard deviation vs the number of training iterations with and without applying amplification, where (e,8) (5, 10- "). The data is Poisson subsampled with rate 0.15. More iterations and less noise are better.
(d) The graph compares the noise standard deviation vs the number of training iterations with and without applying amplification, where (e. 8) (8, 10 "). The data Poisson
subsampled with rate 0.3. More iterations and less noise are better.
Figure 6. More comparison for disjoint submodel splitting.
24

---

Leveraging Randomness in Model and Data Partitioning for Privacy Amplification
Balanced Iteration Subsampling
Balanced Iteration Subsampling
Poisson Subsampling
8
Poisson Subsampling
7-
epsilon
epsilon
6
5
5-
4
3-
3
2.0
2.5
3,0
3.5
4.0
4.5
5.0
2.0
2.5
3.0
3.5
4.0
4.5
5.0
alpha
alpha
(a) The e vs a graph for Balanced Iteration Subsampling and Poisson Subsampling, where T = 1000, & 100, and 2.
(b) The vs graph for Balanced Iteration Subsampling and Poisson Subsampling, where T 200, & 100, and o 4. Lower is better.
Lower better.
Figure 7. More comparison for Balanced Iteration Subsampling vs Poisson Subsampling.
Balanced Iteration Subsampling
9-
Poisson Subsampling
Balanced Iteration Subsampling
Subsampling
7-
epsilon
epsilon
6-
3-
5-
4-
2
Noise Standard Deviation
3.0
3.5
4.0
4.5
Noise Standard Deviation
(a) The privacy cost (in (c, 8)-DP) vs noise standard devia- tion graph for Balanced Iteration Subsampling and Poisson Subsampling, where e and less noise are better. For small T, Balanced Iteration Subsampling can achieve the same privacy guarantee with less noise injection.
(b) The privacy cost (in (c, 6D-)) noise standard devia- tion graph for Balanced Iteration Subsampling and Poisson Subsampling. where T 1500, 120, and 10-* Lower and less noise are better. For large T, the two curves are nearly identical.
I 5, and 8 10-6, Lower
Figure 8. More comparison for Balanced Iteration Subsampling vs Poisson Subsampling.
25


Reviews:
[{"review_id": "gWB6vOZWjh", "reviewer": "Reviewer_rbZT", "summary": "The paper proposes a unified privacy analysis for the applications of model and data partitions. The crucial theorem as shown in Theorem 3.1, which is novel and non-trivial to my best knowledge, states the renyi-divergence between a Gaussian distribution and a mixture of Gaussians. Upon to this theorem, the privacy analysis for applications such as model splitting, dropout, and balanced iteration subsampling,  can be amplified accordingly. The paper empirically compares the proposed privacy analysis and the analysis in the literature in their experiment.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and their valuable feedback.\n\nWe would like to clarify their main concern regarding \"a straightforward comparison between the proposed analysis and the analysis in the literature\" for the  model splitting methods in Section 3.2. We note that our paper is the first one to point out that model splitting has an inherent privacy amplification gain and to quantify this privacy gain. The baseline to compare this is the standard RDP analysis  for DP-SGD which does not take this amplification gain into account since it has remained unnoticed and unquantified in the literature. For one iteration, the standard analysis in the literature would give $\\epsilon = \\frac{\\alpha c^2}{2\\sigma^2}$ in contrast to the RDP bound in Theorem 3.1 (this expression for $\\epsilon$ does not have a dependence on the number of submodels, because again it does not take into account the fact that training uses model splitting).  Figure 1 presents a visual comparison of our analysis and the aforementioned standard analysis. We will make this point clear in the revision. To put this into perspective, for $(\\epsilon, \\delta)$-DP with $\\delta = 10^{-5}$, 1200 training iterations, data subsampling rate of 0.1, a noise standard deviation of 2, our analysis can guarantee $\\epsilon = [3.5, 4.0, 5.0, 7.4]$ for $[8, 6, 4, 2]$ submodels, while without using our analysis, the best guarantee is $\\epsilon = 11.0$ for all numbers of submodels. To give another example, with $\\sigma = 6$, our analysis guarantees $\\epsilon = [1.0, 1.2, 1.5, 2.1]$ while standard analysis gives $\\epsilon = 3.0$. We will add these as graphs to the revised version. \n\nConversely, we can fix the same $(\\epsilon, \\delta)$-DP for the final model and compare accuracy. We have done such experiments for both centralized and federated settings. In the centralized setting with sample-level $(8, 10^{-5})$-DP,  training ResNet101 with 3 submodels under the standard DP-SGD analysis achieves 79.80\\% accuracy and using our analysis accuracy increases to 82.43\\% (this is because our analysis accounts for the amplification gain for model splitting, allowing us to add less noise while still achieving the same DP guarantee); 8 submodels under the standard DP-SGD analysis has 76.80\\% accuracy and using our analysis accuracy increases to 80.52\\%. In federated setting with user-level $(8, 10^{-5})$-DP,  3 submodels with the standard analysis has 78.47\\% accuracy and using our analysis accuracy increases to 80.28\\%; 8 submodels with the standard analysis has 76.96\\% accuracy has using our analysis increases it to 79.11\\%.\n\nAs for the comparison between Balanced Iteration Subsampling and Poisson Subsampling, we would like to emphasize a point which we will make more clear in the revision. Balanced Iteration and Poisson Subsampling achieve similar privacy-accuracy trade-offs experimentally. This is because standard training includes a large number of iterations, and for large numbers of iterations, both the training dynamic and privacy guarantees of the two become comparable as noted in the paper. The main advantage of Balanced Iteration Subsampling is that it is more practical and deployment-friendly especially in the federated setting. Poisson Subsampling has implementation-related drawbacks as it gives a variable load to each client, which can overwhelm the resources of the client and undermine fair use policies. The DP community has been interested in studying other (more deployment-friendly) data subsampling techniques whose utility and privacy guarantees are comparable to Poisson Subsampling, for example random shuffling and random check-ins (Balle et al 2020). Our paper fills this gap by showing that this is indeed the case for Balanced Iteration Subsampling. As for the actual experiments, for CIFAR-10 with WideResNet-40-4,  $(8, 10^{-5})$-DP,  2000 iterations, using each sample 655 times for Balanced Iteration Subsampling and with probability $\\frac{655}{2000}$ in each iteration for Poisson Subsampling, Balanced Iteration Subsampling injects noise with $\\sigma = 10.17$ and achieves validation accuracy of $70.21\\%$ (with standard deviation $0.69\\%$), while Poisson Subsampling injects noise with $\\sigma = 10.20$ and achieves validation accuracy of $70.13\\%$ (with standard deviation $0.78\\%$). ResNet-101 gives similar results. We will include these experiments in the revision.\n\nWhile we are aware of the paper by (Mironov et. al.) which also considers Poisson subsampling with the Gaussian mechanism; we use the stronger analysis in (Zhu \\& Wang) for Poisson subsampling.\n\nLastly, the design choice to not partition the first and last layers of ResNet-101 is guided by insights from the model splitting literature (e.g. Dun et. al.). They argue that since these layers pick up important features, partitioning them leads to degraded accuracy. Following the guidance from this literature, we experimented with partial and not fully disjoint model splitting.", "claims_and_evidence": "The claims and evidence are mostly convincing to me. The only place that can be more supported is a straightforward comparison between the proposed analysis and the analysis in the literature. In the application of balanced iteration subsampling, the paper states the privacy guarantee of the analysis in the literature. However, a similar statement for the analysis in the literature is not shown for applications in Section 3.2. Moreover, the numerical comparison is only conducted with one choice of $\\sigma$.", "methods_and_evaluation_criteria": "The algorithms and the theoretical results make sense.", "theoretical_claims": "I have checked the proof of the theorems for the applications (Theorem 3.4 - 3.8), but have not checked the exact proof of Theorem 3.1 (in appendix).", "experimental_designs_or_analyses": "1. The empirical evaluation is conducted only with one dataset and model. As the comparison between the analysis in the literature and the proposed literature is not consistent for all cases (of hyperparameter configurations), empirical evaluation is necessary to show the effectiveness of the proposed analysis.\n2. Only one application, model partitioning, is evaluated in the experiment section. Other applications, such as dropout and balanced iteration subsampling, are not evaluated.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "[1] seems to also study the mixture of Gaussian for Renyi-DP, while it specifically calculates the single-dimensional situation. \n\n[1] Mironov, Ilya, Kunal Talwar, and Li Zhang. \"R\\'enyi differential privacy of the sampled gaussian mechanism.\" arXiv preprint arXiv:1908.10530 (2019).", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "The motivation statements (line 158-164) in Section 3.2.2 are not clear. For the blocks that are sensitive to pruning, why is it better to not partition them?", "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": "sWR6cQPyh3", "reviewer": "Reviewer_czZi", "summary": "The paper explores how inherent randomness in machine learning training can be used for privacy amplification, specifically model partitioning and data subsampling. These methods can potentially enhance the training privacy without adding excessive noise.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and  valuable feedback.\n\nWe would like to clarify their main question about \"whether the proposed\nstronger privacy comes at the cost of worse utility or convergence rate compared\nto the canonical DP-SGD method.\" The main contribution of our paper is to develop a mathematical analysis that is able to quantify the privacy gain that comes from various sources of randomness that share a common structure. Model splitting is already used in the literature both in the centralized and federated settings. We are not proposing a new technique here; we are pointing out that model splitting has a free privacy gain which has remained unnoticed in the prior literature (which requires nontrivial analysis to quantify). Since we are not changing the training, same utility and convergence rates can now be achieved with better privacy guarantees. Conversely, for the same privacy, we can achieve better utility and convergence rates than canonical DP-SGD since we need to inject less noise (see experimental results below). \n\nBalanced Iteration Subsampling is indeed a new subsampling method we propose. Balanced Iteration Subsampling is more deployment-friendly that Poisson subsampling, which has implementation-related drawbacks as it gives a variable load to each client. This can overwhelm the resources of the client and undermine fair use policies. The DP community has been interested in studying other (more deployment-friendly) data subsampling techniques whose utility and privacy guarantees are comparable to Poisson Subsampling, for example random shuffling and random check-ins (Balle et al). Our paper fills this gap by showing that Balanced Iteration Subsampling has comparable performance to Poisson subsampling (theoretically we can prove slightly better privacy guarantees for Balanced Iteration Subsampling, however in experiments we observe that Balanced Iteration Subsampling and Poisson subsampling have similar performance, see below for details). We will revise our paper to make these points more clear.\n\nRegarding the question about whether we use \"worst-case privacy, or average privacy across all samples\", we would like to point out that we always use the standard definitions of $(\\epsilon, \\delta)$-DP and $(\\alpha, \\epsilon)$-RDP in the literature. The definition of $(\\epsilon, \\delta)$-DP can be intuitively thought as the privacy leak in the worst $\\delta$-fraction of samples, so in that sense it makes intuitive sense that Poisson subsampling can have worse $(\\epsilon, \\delta)$-DP than Balanced Iteration Subsampling. \n\nThe baseline for our model splitting results is the canonical DP-SGD analysis as pointed out by the reviewer. For one iteration, the canonical DP-SGD analysis  would give $\\epsilon = \\frac{\\alpha c^2}{2\\sigma^2}$ RDP in contrast to the RDP bound in Theorem 3.1 (this expression for $\\epsilon$ does not have a dependence on the number of submodels because the canonical analysis does not leverage the privacy amplification gain due to model splitting, which is the contribution of our paper). Figure 1 presents a visual comparison of our analysis and the standard analysis. We will make this point clear in the revision. To put this into perspective, for $(\\epsilon, \\delta)$-DP with $\\delta = 10^{-5}$, 1200 training iterations, data subsampling rate of 0.1, a noise standard deviation of 2, our analysis can guarantee $\\epsilon = [3.5, 4.0, 5.0, 7.4]$ for $[8, 6, 4, 2]$ submodels, while without using our analysis, the best guarantee is $\\epsilon = 11.0$ for all numbers of submodels. To give another example, with $\\sigma = 6$, our analysis guarantees $\\epsilon = [1.0, 1.2, 1.5, 2.1]$ while standard analysis gives $\\epsilon = 3.0$. We will add these as graphs to the revised version. Note that because training remains the same and we only change the privacy analysis, utility remains the same in both cases.\n\nConversely, we can fix the same $(\\epsilon, \\delta)$-DP budget and compare utility. We have done such experiments for both centralized and federated settings. In the centralized setting with sample-level $(8, 10^{-5})$-DP,  training ResNet101 with 3 submodels under the standard DP-SGD analysis achieves 79.80\\% accuracy and using our analysis accuracy increases to 82.43\\% (this is because our analysis accounts for the amplification gain for model splitting, allowing us to add less noise while still achieving the same DP guarantee); 8 submodels under the standard DP-SGD analysis has 76.80\\% accuracy and using our analysis accuracy increases to 80.52\\%. In federated setting with user-level $(8, 10^{-5})$-DP,  3 submodels with the standard analysis has 78.47\\% accuracy and using our analysis accuracy increases to 80.28\\%; 8 submodels with the standard analysis has 76.96\\% accuracy has using our analysis increases it to 79.11\\%.\n\nWe will add these experiments to the revised version of the paper, and incorporate reviewer's suggestion about the restructuring of the results.", "claims_and_evidence": "It is somewhat unclear whether the study proposes an amplified privacy scheme or a tighter privacy analysis. The current claim leans towards the former, but it lacks a thorough privacy-utility tradeoff analysis and convergence analysis. This leaves open the question of whether the proposed stronger privacy comes at the cost of worse utility or convergence rate compared to the canonical DP-SGD method.\n\nA finer concern is the intuition behind the proposed balanced data subsampling. As it fixes the number of iterations each sample appears in, the proposed balanced sampling introduces less randomness than Poisson sampling. Does this balanced sampling improve only the worst-case privacy, or does it also improve the average privacy across all samples?", "methods_and_evaluation_criteria": "The proposed methods including model and data partitioning are relevant and make sense for privacy amplification in ML model training.", "theoretical_claims": "I checked the correctness of the proof outline in section 3.4.", "experimental_designs_or_analyses": "The current experiments do not address the comparison of the privacy-utility tradeoff between the proposed techniques and the existing DP-SGD training pipeline. Further experiments are needed to address how the privacy amplification methods affect the training performance, especially in convergence and model utility.\n\nIn addition, for the balanced sampling scheme, the experiment setup should elaborate on whether it evaluates the average or worst-case privacy of the proposed and baseline sampling methods, and how.", "relation_to_broader_scientific_literature": "The key contributions are closely related to prior works on DP, particularly in the context of model parallelism and randomized training processes. The authors build upon existing techniques such as model partitioning and Poisson subsampling to propose a novel approach that leverages randomness inherent in the training process for privacy amplification.", "essential_references_not_discussed": "The related works are properly cited.", "other_strengths_and_weaknesses": "The reviewer suggests clearly stating the baseline privacy analysis for a more direct comparison. It is currently only represented by a single line in the experimental figures, with no rigorous equations or specific experimental setups. It would be helpful to clearly state the baseline privacy guarantee, and mathematically compare it with the proposed Theorems 3.4, 3.5, and 3.8 to directly demonstrate the advantages of the proposed schemes.\n\nThe manuscript would benefit from better organization, particularly in making the theoretical analysis more intuitive. The proof of Theorem 3.1 could be summarized as a helper lemma in the main text, with full details in the appendix. Each model splitting and data sampling method should have a clear explanation of how it corresponds to Helper Lemma 3.1. For example, the connection between model splitting and the mixed Gaussian distribution in Theorem 3.1 should be explicitly stated. While Remark 3.3 touches on this, it lacks rigor and comprehensiveness.", "other_comments_or_suggestions": "The reviewer suggests adding more experiments with different model structures, training datasets and training hyperparameters.", "questions_for_authors": "- Please clarify whether the paper proposes a tighter privacy analysis or a better privacy scheme, and add a comparison to baselines in terms of mode utility and training convergence (see Claims And Evidence and Experimental Designs Or Analyses).\n\n- Please detail the baseline privacy analysis including theoretical formulations and experimental setups (see Other Strengths And Weaknesses).\n\n- Please clarify whether the proposed balanced sampling scheme improves worst-case privacy or average privacy (see Claims And Evidence).", "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": "4bKwFJtNSD", "reviewer": "Reviewer_iUZc", "summary": "The paper shows how Renyi DP guarantees can be amplified under two different kinds of data sub-sampling and partitioning strategies. The first is where all data points are used for the same number of iterations but in randomly distributed steps. The second is where different parts of the model are updated with randomly chosen data samples. In each case, the paper shows when the amplification is larger than what was previously known by existing bounds.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and their valuable feedback. We will incorporate their comments in our revised paper. \n\nFollowing the reviewer's suggestions, we have done additional experiments for both centralized and federated settings. In the centralized setting, training ResNet101 using 3 submodels    achieves 79.80\\% accuracy with sample-level $(8, 10^{-5})$-DP guarantee for the final model under the standard DP-SGD analysis, and accuracy increases to 82.43\\% for the same privacy guarantee using our analysis (this is because our analysis accounts for the amplification gain for model splitting, allowing us to add less noise while still achieving the same DP guarantee); training ResNet101 with 8 submodels  has 76.80\\% accuracy under the standard DP-SGD analysis and using our analysis accuracy increases to 80.52\\%. In the federated setting, training ResNet101 using 3 submodels achieves 78.47\\% accuracy and user-level $(8, 10^{-5})$-DP under the standard analysis, using our analysis accuracy increases to 80.28\\% under the same privacy guarantee; 8 submodels with the standard analysis has 76.96\\% accuracy, and using our analysis increases the accuracy to 79.11\\%.\n\nWe would like to clarify the main concern regarding the comparison between Balanced Iteration Subsampling and Poisson Subsampling. Even though we show that  Balanced Iteration Subsampling can have better privacy guarantees in some regimes, as the reviewer points out Balanced Iteration and Poisson Subsampling achieve similar privacy-accuracy trade-offs experimentally. This is because standard training includes a large number of iterations, so both the training dynamic and privacy guarantees of the two become comparable (see experimental results below). The main advantage of Balanced Iteration is that it is more practical and deployment-friendly especially in the federated setting. Poisson Subsampling has implementation-related drawbacks as it gives a variable load to each client, which can overwhelm the resources of the client and undermine fair use policies. The DP community has been interested in studying other (more deployment-friendly) data subsampling techniques whose utility and privacy guarantees are comparable to Poisson Subsampling, for example random shuffling and random check-ins (Balle et al 2020). Our paper fills this gap by showing that this is indeed the case for Balanced Iteration Subsampling. As for the actual experiments, for CIFAR-10 with WideResNet-40-4,  $(8, 10^{-5})$-DP,  2000 iterations, using each sample 655 times for Balanced Iteration Subsampling and with probability $\\frac{655}{2000}$ in each iteration for Poisson Subsampling, Balanced Iteration Subsampling injects noise with $\\sigma = 10.17$ and achieves validation accuracy of $70.21\\%$ (with standard deviation $0.69\\%$), while Poisson Subsampling injects noise with $\\sigma = 10.20$ and achieves validation accuracy of $70.13\\%$ (with standard deviation $0.78\\%$). ResNet-101 gives similar results. We will include these experiments in the revision.\n\nOn the second concern, Theorem 3.5 and Corollary 3.7 indeed utilize only one of the two sources of randomness for amplification because different training dynamics require different privacy analyses. While our analysis does not fully capture all sources of randomness in the setting of Thm 3.5 (this would require an extension of our current analysis), we hope the reviewer will appreciate that we demonstrate a significant improvement over ignoring randomness entirely and defaulting to the standard DP-SGD analysis. We hope our paper will inspire the DP community to further explore such inherent gains and develop stronger mathematical tools for their accounting.  This remains a promising direction for future work.\n\nRegarding Line 196, which proposes using two clipping norms—one for the parts of the model with model splitting and another for the parts without—it is, in our view, the only viable approach. If a single clipping norm were used, the worst-case $\\epsilon$ would occur when the gradient vector concentrates all its power on the part of the model without model splitting. In that scenario, there would be no privacy amplification at all. Therefore, two separate clipping norms appear necessary to the authors.\n\nOn the third point, our paper is not merely about introducing a theoretical tool to quantify privacy in specific cases; rather, we view the broader contribution of our paper as highlighting an important but previously overlooked insight —that inherent randomness in the training dynamics, such as model parallelism techniques already used in centralized and federated learning, can be leveraged for privacy amplification, at no additional cost. To our knowledge, this is the first work to identify and quantify such an amplification gain. Beyond the specific analysis presented, we aim to bring this perspective to the DP community and encourage further exploration of how different training dynamics yield privacy gains.", "claims_and_evidence": "Yes, I found most claims to be well-managed in terms of what is claimed and what is shown. The following cases were a bit problematic for me though it was not overclaiming per se -  \n\n1. That the amplification with model partitioning  can be helpful for federated and distributed learning- (see Line 074 left column), however there were no experimental setups proposed to show this. Given that the benefit large depends on the exact problem parameters it is hard to justify if this indeed results in a benefit and is not just a theoretical construct.\n\n2. Similarly for Balanced iteration subsampling, the introduction promised that balanced subsample iteration can overcome the issue of disparate sampling in poisson subsampling and can be used in both centralised and federated learning, but there wasn't an experimental validation of this (and the regime where advantage is shown to exist in Fig 2 and 3 were very limited)", "methods_and_evaluation_criteria": "Evaluation is severley lacking. See above for claims that would be good to verify.", "theoretical_claims": "I have not checked the proofs but the theorem statements are very well written and the proof sketches are well motivated. So I do not doubt that they are correct (or can be correct in case there are typos or mistakes)", "experimental_designs_or_analyses": "This is severely lacking as I have mentioned above.", "relation_to_broader_scientific_literature": "Well done.", "essential_references_not_discussed": "Well done.", "other_strengths_and_weaknesses": "1. The paper is very well written and with one reading it was very clear to me - what the gap in the literature is, how the authors are solving it, what the theoretical statements and roughly how they are proven. \n\n2. The technical novelty is not particularly large but it is still interesting in terms of the results that are proven. The problem setting is also itneresting.\n\n3. There are three major weaknesses.\n    i. The theoretical regimens of improvement, at least what is evident from the paper, is very limited. For example, if I have interpreted  Line 270 to 274 correctly (correct me if I am wrong) and if I make a parallel to classical non-private training, $\\gamma$ should be thought of as $1/\\mathrm{batch size}$ which is the RV indicating what fraction of iterations have that particular example. Now this is of the order of $1/256\\ll 0.005$. In this regime Poisson subsampling seems to be better. (I understand that the regime where the binomial heavily concentrates around its mean is where poisson subsampling should be better and this is precisely the case above but also this is the common regime)\n    ii) The paper seems to be incomplete in the sense that several things could be improved ( also highlighted by the author). For example, Theorem 3.5 only uses one of the two sources of randomness, Line 196 also seems to be a very loose way of going about it, and Line 305.\n\n    iii) Pending the above and the limited theoretical contribution, I am not viewing its theoretical contribution to be large enough to exempt the need for sufficient experimental evidence to validate its contribution. In this space, the paper's results are very limited.", "other_comments_or_suggestions": "Update: I have updated my score to weak accept.", "questions_for_authors": "Please address the above comments.", "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": "OaENMr1ngP", "reviewer": "Reviewer_j224", "summary": "The submission analyzes privacy amplification for Renyi DP in two settings where $N$ (sets of) records are independently assigned to $k$ out of $d$ components of DP-SGD:\n(1) Data partitioning, where each record from a dataset of size $N$ contributes to $k$ out of $d$ gradient steps (\"balanced iteration subsampling\"),\nand (2) model partitioning, where all records associated with one of $N$ clients are used to update $k=1$ out of $d$ subsets of model parameters.\n\nThe authors first present a general upper bound on the Renyi divergence on the Gaussian mixture distributions that arise from such random partitioning schemes.\nA proof for this main theorem is provided at the end of the methods section. The main objective of this proof is to determine sound upper bounds\nthat eliminate computationally intractable multinomial terms (forward divergence) or eliminate mixture densitities from the denominator in the Renyi divergence integral (reverse divergence).\n\nFor model partitioning, the general bound is first instantiated for disjoint partitionings of the model parameters. It is then generalized for non-disjoint partitionings by composing privacy guarantees for the intersection and symmetric difference of the parameter subsets. Next, the disjoint partitioning bound is generalized to probabilistic via joint quasi-convexity of Renyi divergences. Finally, this probabilistic disjoint partitioning bound is applied to the special case of parameter dropout, which partitions models into activated and deactivated neurons.\nFor data partitioning, the general bound is again instantiated to obtain epoch-level privacy guarantees, which are then compared to a composition of iteration-level privacy guarantees for Poisson subsampling.\n\nIn the experimental section, the authors evaluate the utility of ResNet-101 finetuned on CIFAR-10 with (1) model partitioning and bounds from prior work (2) model partitioning with the proposed bounds and (3) without model partitioning. The results show an improved privacy--utility trade-off for (2) compared to (1), achieving an accuracy closer to (3).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review of our paper and their valuable feedback.\n\nOur paper is indeed the first to point out and quantify the privacy gain from model parallelism techniques already employed in federated learning.\n\nFollowing the reviewer's suggestions, we have done more experiments for both centralized and federated settings. In the centralized setting with sample-level $(8, 10^{-5})$-DP,  training ResNet101 with 3 submodels under the standard DP-SGD analysis achieves 79.80\\% accuracy and using our analysis accuracy increases to 82.43\\% (this is because our analysis accounts for the amplification gain for model splitting, allowing us to add less noise while still achieving the same DP guarantee); 8 submodels under the standard DP-SGD analysis has 76.80\\% accuracy and using our analysis accuracy increases to 80.52\\%. In federated setting with user-level $(8, 10^{-5})$-DP,  3 submodels with the standard analysis has 78.47\\% accuracy and using our analysis accuracy increases to 80.28\\%; 8 submodels with the standard analysis has 76.96\\% accuracy, and using our analysis accuracy increases to 79.11\\%. The experiments are run with 3 random seeds and all have standard deviations of around 0.7\\%.\n\nThe design choice to not partition the first and last layers of ResNet-101 is guided by insights from the model splitting literature (e.g. Dun et. al.). They argue that since these layers pick up important features, partitioning them leads to degraded accuracy. Following the guidance from this literature, we experimented with partial and not fully disjoint model splitting.\n\nAs for the comparison between Balanced Iteration Subsampling and Poisson Subsampling, we would like to emphasize a point which we will make more clear in the revision. Balanced Iteration and Poisson Subsampling achieve similar privacy-accuracy trade-offs experimentally. This is because standard training includes a large number of iterations, and for large numbers of iterations, both the training dynamic and privacy guarantees of the two become comparable as pointed out in the paper. The main advantage of Balanced Iteration Subsampling is that it is more practical and deployment-friendly especially in the federated setting. Poisson Subsampling has implementation-related drawbacks as it gives a variable load to each client, which can overwhelm the resources of the client and undermine fair use policies. The DP community has been interested in studying other (more deployment-friendly) data subsampling techniques whose utility and privacy guarantees are comparable to Poisson Subsampling, for example random shuffling and random check-ins (Balle et al 2020). Our paper fills this gap by showing that this is indeed the case for Balanced Iteration Subsampling. As for the actual experiments, for CIFAR-10 with WideResNet-40-4,  $(8, 10^{-5})$-DP,  2000 iterations, using each sample 655 times for Balanced Iteration Subsampling and with probability $\\frac{655}{2000}$ in each iteration for Poisson Subsampling, Balanced Iteration Subsampling injects noise with $\\sigma = 10.17$ and achieves validation accuracy of $70.21\\%$ (with standard deviation $0.69\\%$), while Poisson Subsampling injects noise with $\\sigma = 10.20$ and achieves validation accuracy of $70.13\\%$ (with standard deviation $0.78\\%$). ResNet-101 gives similar results. We will include these experiments and show more graphs to compare the privacy guarantees of the two subsampling methods in the revision.\n\nIn Figure 2, the thin line at $\\gamma \\approx 0$ is due to discretization of $\\gamma$ values and the code arbitrarily ruling in favor of Balanced Iteration Subsampling when $\\gamma = 0$.\n\nOn the concern about Corollary 3.7, we would like to clarify that the privacy gain we utilize comes from the random (and independent) assignment of submodels to the clients. So, although in Algorithm 1, model splitting in done centrally, each client independently receives a submodel. Algorithm 2's parameter dropout can be seen as forming $2^m$ submodels (where $m$ is the number of parameters subject to dropout), and each client independently receives a submodel, so in that perspective, dropout is fundamentally no different, and thus it is a corollary that follows.\n\nThe dataset neighboring relationship is indeed add-/remove-one, which was briefly mentioned in Section 2.", "claims_and_evidence": "The submission makes two central claims:\n1. That the randomness inherent to different commonly used model partitioning strategies can be used to provide stronger privacy guarantees.\n2. That balanced iteration subsampling can offer stronger privacy amplification than Poisson subsampling for certain parameterizations.\n\nClaim 1 is proven by formally deriving corresponding amplification guarantees.\n\nClaim 2 is proven by deriving corresponding amplification guarantees and comparing them to tight amplification bounds for Poisson subsampling for different epoch lengths, subsampling rates, and fixed RDP parameter $\\alpha$ (See Fig. 2).\n\n**Rating: Good**", "methods_and_evaluation_criteria": "### Methods\nIn the case of model partitioning, the work does not provide new methods as such, but rather derives better privacy guarantees for these methods.\n\nThe proposed balanced iteration subsampling appears like a reasonable alternative to random shuffling or Poisson sampling. It fulfills its role in demonstrating that amplification-by-subsampling can also be attained by sampling non-i.i.d. lots/batches.\nHowever, it is not clear whether this subsampling method is preferable for model training (see \"Experimental Designs or Analyses\" below).\n\n### Evaluation Criteria\nPrivacy guarantees are compared by plotting (Renyi) privacy profiles, which is common practice.\nThe privacy--utility trade-off attained via the amplification bounds is evaluated by comparing accuracy at a fixed privacy budget, which also makes sense. CIFAR and ResNet are standard choices for such experiments in DP literature.\n\n**Rating: Good**", "theoretical_claims": "I went through the proofs in Section 3.4 and read the proofs of Theorems 3.4, 3.5, 3.7, and 3.8 in detail.\nI skimmed the other proofs in the appendix. **Overall, the proof strategy appears sound, but I did not not check each individual equation for correctness**.\n\nI have a minor concern w.r.t. Corollary 3.7 (Parameter dropout). The proof seems to largely follow that of Theorem 3.5 (Disjoint partitioning). However, Theorem 3.5 assumes that the partitioning is done centrally (see l. 172 in Algorithm 1), whereas dropout is applied independently per client (see l. 228 in Algorithm 2).\nI believe that the guarantee still holds due to parallel composition (i.e., we only need to apply Theorem 3.5 to the specific client that holds the inserted/removed record), but it would be good if the authors could clarify this.\n\n**Rating: Ok, but requires some clarification**", "experimental_designs_or_analyses": "As stated above, the evaluation in Section 4 is sound.\nHowever, the privacy utility trade-off is only investigated for a specific model partitioning scheme and one specific choice of privacy budget, and one random seed. The argument for leveraging the randomness in model partitioning in practice could be strengthtened by also:\n* Considering a wider range of privacy budgets to show some form of Pareto-domination of the baseline\n* Also considering fully disjoint model partitioning and random dropout partitioning.\n* Repeating the experiment with multiple random seeds and reporting standard deviations.\n\nSimilarly, the evaluation of the RDP profiles in Fig. 3 and Fig. 4 could be repeated for different choices of $T, k, \\sigma$ in the appendix to show that the derived bounds are beneficial beyond this very specific  choice of parameters.\n\nFinally, the privacy--utility trade-off attained by balanced iteration subsampling is not investigated. Thus, it is not clear whether there is any benefit to actually using this new data partitioning scheme for model training in practice.\n\n**Rating: Ok for a theory-focused work, but experimental evaluation could be expanded / be more thorough to show impact on practical applications**", "relation_to_broader_scientific_literature": "On a high-level, this work studies privacy amplification, i.e., leveraging elements of internal randomness that induce mixture distributions.\n\nThe proposed balanced iteration represents an alternative to commonly used subsampling schemes that sample each batch for a training epoch independently. Similar non-i.i.d. subsampling schemes have already been studied in prior work (shuffling, random check-ins, and balls-and-bins sampling). However, it generalizes them by allowing each record to contribute to multiple training steps. I.e., this aspect is somewhat novel.\n\nIt seems like analyzing amplification by model partitioning is completely novel, but I am not sufficiently familiar with this side of the literature to make a definite statement about its novelty.\n\nThe privacy analysis is conducted in the framework of Renyi differential privacy / moments accounting. This enables very simple privacy accounting for subsampled mechanisms, but overestimates privacy when converted to approximate DP. However, this framework has been superseded by other numerical and analytical (e.g., Fast Fourier Accounting (Koskela et al, 2019) and Analytical Fourier Accounting (Zhu et al., 2022)) approaches.", "essential_references_not_discussed": "Balanced iteration subsampling with $k=1$ has already been proposed in \"Balls-and-Bins Sampling for DP-SGD\" by Chua et al. (December 2024).\n\nHowever, this prior work appeared just one month before the submission deadline, so I do not think that the authors necessarily need to discuss it.", "other_strengths_and_weaknesses": "### Other Strengths\n* The paper is overall well-written and structured. Especially the main section which first states the main result, then applies it to different use cases, and finally discusses the technical details of its derivation.\n* The work clearly states a research question (paragraph 2 of Section 1), which is good.\n* The authors are transparent about limitations / avenues towards deriving tighter bounds (e.g., by leveraging the randomness of probabilistic model partitioning in Theorem 3.5)\n\n### Other Weaknesses\n* The work uses RDP, which overestimates privacy leakage when converted to approximate differential privacy\n* The caption of Fig. 2 states \"With different values of $\\alpha$, the graph shows a similar pattern.\" This should be substantiated by actually plotting the graph for different values of $\\alpha$ in the appendix.\n* The authors do not specify for which neighboring relation they derive their bounds. I assume it's insertion/removal of a single record (of a single client), but it would be good to clarify this.\n* In Fig. 1 \"No amplification\" and Section 4 \"baseline\", it is not clear how exactly the baseline privacy guarantes are computed. It would be better to clarify this in the appendix.", "other_comments_or_suggestions": "### Comments\nTheorem 3.4 states that the amplification guarantee holds for any disjoint model splitting method. However, the proof only considers deterministic splitting. Probabilistic splitting is only analyzed later in Theorem 3.5. You may want to add a quantifier: \"Each iteration of Algorithm 1 with a >deterministic< disjoint model splitting method [...]\".\n\n### Conclusion\nOverall, the submission makes substantial, well-presented contributions in two different directions: Privacy accounting for non-i.i.d. subsampling and leveraging internal randomness due to model partitioning.\n\nSince model partitioning is already used for computational reasons, the latter essentially provides additional privacy for free. As such, the work could potentially have high impact on federated learning literature. The main Theorem appears very general and may thus also enable the analysis of various other non-i.i.d. subsampling schemes. Thus, there may also be some impact on differentially private ML in the centralized setting.\n\nMy main concern is that the experimental evaluation is not sufficiently thorough to make any definite statements about how large the benefit of using these new sources of randomness actually is in practical applications. However, since the main contribution lies in the conducted theoretical analysis, I nevertheless recommend acceptance.\n\n## Update after Rebuttal\nThe authors have addressed most of my comments. I continue to recommend acceptance, see details in rebuttal response below.", "questions_for_authors": "* At the bottom of Fig. 2, there is a very thin green line. Does this mean that balanced iteration subsampling is better for $\\gamma \\to 0$, or is this a bug in the plotting code?\n* Could you please explain why Corollary 3.7 follows from Theorem 3.5, even though the model splitting is now done per client? (See \"Theoretical Claims\" above).", "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:

Meta-review: The paper proposes Renyi DP accounting for new DP-SGD variants: privacy amplification from updating random partitions of the model and accounting for balanced iteration subsampling.

Both of these as well as the underlying bound on Renyi divergence between a Gaussian and a mixture-of-Gaussians are interesting and valuable contributions.

All reviewers recommend acceptance, with main criticism related to limited experiments. The authors have added new experiments in the rebuttal, which seems sufficient for a theory-focused paper.

A minor weakness noted by Reviewer j224 and not addressed by the authors is the lack of comparison with state-of-the-art numerical accountants for Poisson subsampling (such as the PRV accountant that is the standard e.g. in Opacus). This would be necessary to fully judge the value of the proposed methods compared to state-of-the-art in $(\varepsilon, \delta)$-DP.
Decision: Accept (poster)