Privacy amplification by random allocation
Authors: Moshe Shenfeld
Vitaly Feldman
Venue: NeurIPS 2025 spotlight ()
Keywords: Differential Privacy
DP-SGD
subsampling
shuffling
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We consider the privacy guarantees of a new sampling method, which combines aspects of Poisson subsamplig and shuffling, and prove it can be approximated as Poisson subsampling.

Abstract: We consider the privacy amplification properties of a sampling scheme in which a user's data is used in $k$ steps chosen randomly and uniformly from a sequence (or set) of $t$ steps. This sampling scheme has been recently applied in the context of differentially private optimization [Chua et al., 2024a, Choquette-Choo et al., 2024] and is also motivated by communication-efficient high-dimensional private aggregation [Asi et al., 2025]. Existing analyses of this scheme either rely on privacy amplification by shuffling which leads to overly conservative bounds or require Monte Carlo simulations that are computationally prohibitive in most practical scenarios.

We give the first theoretical guarantees and numerical estimation algorithms for this sampling scheme. In particular, we demonstrate that the privacy guarantees of random $k$-out-of-$t$ allocation can be upper bounded by the privacy guarantees of the well-studied independent (or Poisson) subsampling in which each step uses the user's data with probability $(1+o(1))k/t$. Further, we provide two additional analysis techniques that lead to numerical improvements in several parameter regimes. Altogether, our bounds give efficiently-computable and nearly tight numerical results for random allocation applied to Gaussian noise addition.

Privacy amplification by random allocation
Vitaly Feldman Apple vitaly.edu@gmaal wwwwgmail....mmm com
Moshe Shenfeld"
The Hebrew university Jerusalem moshe.. shenfe ddmaad.mmmm.omm 1. ac ail
Abstract
We consider the privacy amplification properties of sampling scheme in which a user's data is used in steps chosen randomly and uniformly from a sequence (or set) of t steps. This sampling scheme has been recently applied in the context differentially private optimization [Chua et al. 2024a Choquette-
et al.) 2025] and is also motivated by communication-eche efficccenn high- high-dimensional private aggregation [Asi et al.] 2025]]. Existing analyses of this scheme either rely on privacy amplification by shuffling which leads to overly conservative bounds require Monte Carlo simulations that are computationally prohibitive in most practical scenarios.
We give the first theoretical guarantees and numerical estimation algorithms for this sampling scheme. In particular, we demonstrate that the privacy guarantees of random k-out-of-l allocation can be upper bounded by the privacy guarantees of the well-studied independent (or Poisson) subsampling in which each step uses the user's data with probability (1 + o(1)) k/t. Further, we provide two additional analysis techniques that lead to numerical improvements in several parameter regimes. Altogether, our bounds give cerciennly-compuuabbl and nearly tight numerical results for random allocation applied to Gaussian noise addition.
Introduction
One of the central tools in the analysis of differentially private algorithms are so-called privacy amplification guarantees, where amplification results from sampling of the inputs. In these results one starts with differentially private algorithms (or sequence of such algorithms) and randomized selection (or sampling) to determine which of the n elements in dataset to run each of the algorithms on. Importantly, the random bits of the sampling scheme and the selected data elements are not revealed. For a variety of sampling schemes this additional uncertainty known lead to improved privacy guarantees of the resulting algorithm, that is, privacy amplification.
In the simpler, single step first shown by/ Kasiviswanathan et al. [201T], if each element of the dataset included the subset with probability À (independently of other elements) then the privacy of the resulting algorithm is better (roughly) by a factor X. This basic result has found numerous applications, most notably in the analysis of the differentially private stochastic gradient descent (DP-SGD) algorithm [Bassily et al. 2014). In DP-SGD gradients are computed on randomly chosen batches of data points and then privatized through clipping and Gaussian noise addition. Privacy analysis of this algorithm is based on the so called Poisson sampling: elements in each batch and across batches are chosen randomly and independently of each other. The absence of dependence implies that the algorithm can be analyzed relatively easily downside of this simplicity is that such sampling less efficient and harder to implement within the standard ML pipelines. As result, in practice some form of shuffling is used to define the batches in
DP algorithm
randomly chosen subset of the dataset. As
direct composition of single step amplification results. The
Work partially done while author was intern at Apple
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

DP-SGD leading to a well-recognized discrepancy between the implementations of DP-SGD and their analysis [Chua et al. 2024b c Annamalai et al. 2024).
100.00
10.00
8
1.00
E. Local
Es Shuffle
Ep Polsson (PLD)
Ex Allocation (Our Direct)
0.10
E Allocation (Our Recursive)
E₁ Allocation (Our Decomposition)
0.00 0.23
0.29 0.32 0:37
0.47 0.53
0.60
0.67
0.76
0.86 0.97
1.39
2.00
Figure 1: Upper bounds privacy parameter as function of the noise parameter a for various schemes and the local algorithm (no amplification), all using the Gaussian mechanism with fixed parameters 5 = 10 t == 10 In the Poisson scheme À = 1/t. The "flat" part of the RDP based calculation is due to computational limitations, which was computed for the range E [2, 60).
Motivated by the shuffle model of federated data analysis [Bittau et al.) 2017 Cheu et al. (2019) Brlingsson et al. [019]] have studied the privacy amplification of the shuffling scheme. In this scheme, the elements order is used in the i-th step of the algorithm. This sampling scheme can be used to analyze the
randomly and uniformly permuted and the i-th element in the permuted
implementations DP-SGD used in practice [Erlingsson al. [0019 Feldman al.) 2021]. However, the analysis of this sampling scheme is more involved and nearly tight results are known only for relatively simple pure DP (8 0) algorithms [Feldman et al., 2021 2023 Girgis et al. 2021) In particular, applying these results to Gaussian noise addition requires using d-gaararatsesss of the Gaussian noise. This leads to an additional / Vl((1/5) factor in the asymptotic analysis and significantly worse numerical results (see Fig. T for comparison and discussion in Section
Note that shuffling differs from Poisson subsampling in that participation of elements is dependent both in each step (or batch) and across the steps. If the participation of elements each step is dependent (by fixing the total number of participating elements) but the steps are independent then the sampling scheme can tightly analyzed as a direct composition of fixed subset size sampling steps (e.g., using bound in Balle et al. [2188] Zhu et al. [2022). ). However, a more problematic aspect of Poisson sampling is the stochasticity in the number times each element is used in all steps. For example, using Poisson sampling with sampling rate 1/t over batches will result in roughly 1/e probability of not using the sample which implies dropping approximately 37% of the data, and the additional sampling randomness may increase the resulting variance as demonstrated in Appendix H In a distributed setting it is also often necessary to limit the maximum number of times a user participates in the analysis due to time communication constraints the protocol [Chen et al.) 2024 Asi et al. 2025). Poisson sampling does not allow to fully exploit the available limit which hurts the utility.
Motivated by the privacy analysis of DP-SGD and the problem of communication -effccicinnnnnn high- dimensional private aggregation with two servers [Asi et al.) 2025). we analyze sampling schemes exactly randomly chosen steps out of the total independently
where each element participates of other elements. We refer to this sampling as k-out-of-l rundom allocation. For & = 1, this scheme a special case of the random check-in model of defining batches DP-SGD [Balle et al.) 2020) Their analysis of this variant relies the amplification properties of shuffling and thus does not lead

---

to better privacy guarantees than those that are known for shuffling. Very recently, Chua et al. [2024a] have studied such sampling (referring to it as balls-and and-bins sampling) in the context of training neural networks via DP-SG) Their main results show that from the point of view of utility (namely,
accuracy of the final model) random allocation with k = 1 is essentially identical to shuffling and is noticeably better than Poisson sampling. Concurrently. Choquette- Chooe et al. (2025) considered the same sampling scheme for the matrix mechanism in the context of DP-FTRL. The privacy analysis in these two works reduces the problem to analyzing the divergence of specific pair of distributions on RR. They then used Monte Carlo simulations to estimate the privacy parameters of this pair. Their numerical results suggest that privacy guarantees of l-out-of-t random allocation are similar to those of the Poisson sampling with rate of 1/t. While very encouraging, such simulations have several limitations which we discuss in Appendix G.I most notably, achieving high-confidence estimates for small 6 and supporting composition appear to be computationally impractical. This approach also does not lead provable privacy guarantees and does not lend itself to asymptotic analysis (such as the scaling of the privacy guarantees with t).
1.1 Our contribution
We provide three new analyses for the random allocation setting that result in provable guarantees that nearly match or exceed those of the Poisson subsampling at rate k/t. The analyses rely on different techniques and lead to incomparable numerical results. We describe the specific results below and illustrate the resulting bounds in Fig.
In our main result we show that the privacy of random allocation is upper bounded by that of the Poisson scheme with sampling probability z k/L up to lower order terms which are asymptotically vanishing in t/k. Specifically, we upper bound it by the k-wise composition of Poisson subsampling with rate (1+7)k/t applied to a dominating pair of distributions for each step of the original algorithm
kln(k//') and
(Def. 2.60 with an additional tōp + 8' added to the 8 parameter. Here, Y 0 c
eo, do the privacy parameters of the original algorithm. The formal statement of this result that includes all the constants can be found in Thm. 4.1 Additionally, we show in Thm. 4.1 this lower
order term can be recursively bounded using (s", parameters of the same algorithm for some e' > E. This leads to significant numerical improvements in our results.
Our analysis relies on several simplification steps. Using a dominating pair of distributions for the steps of the original algorithm, we first derive an explicit dominating pair of distributions for random allocation (extending similar result for Gaussian noise in [Chua et al., [024a]] Choquette Chhoo
eet al. 2025)). D) Equivalently, we reduce the allocation for general multi-step adaptive algorithms to the analysis of random allocation for a single (non-adaptive) randomizer on two inputs. We also analyze only the case of & and then use a reduction from general k to A = 1. Finally, our analysis of the non-adaptive randomizer for k = 1 relies on decomposition of the allocation scheme into a sequence of posterior sampling steps for which we then prove a nigh-probability bound on subsampling probability in each step.
We note that, in general, the privacy of the composition of subsampling of the dominating pair of distributions can be worse than the privacy of the sampling scheme of a concrete algorithm, even if this pair tightly dominates it. This is true for both Poisson and random allocation schemes. However, all existing analyses of the Poisson sampling are effectively based on composition of subsampling for a dominating pair of distributions. Moreover, if the algorithm has a pair of neighboring datasets inducing this dominating pair, then our upper bound can be stated directly in terms of the Poisson subsampling scheme with respect to this pair. Such dominating inpul exists for many standard algorithms including those based on Gaussian and Laplace noise addition.
While our result shows asymptotic equivalence of allocation and Poisson subsampling, it may lead to suboptimal bounds for small values of t/k and large En. We address this using two additional techniques which are also useful as starting points for the recursive version of our main result.
We first show that of random allocation with A = 1 is at most a constant (z 1.6) factor times larger than a of the Poisson sampling with rate 1/1 for the same (see Theorem 4.3). This upper bound does not asymptotically approach Poisson subsampling but applies in all parameter regimes. To prove this upper bound we observe that Poisson subsampling essentially a mixture of random allocation schemes with various values of k. We then prove monotonicity property of random allocations
3

---

showing that increasing k leads to worse privacy. Combining these results with the advanced joint convexity property [Bllle et al. [2018] gives the upper bound.
Finally, we give a direct analysis of the divergence for the dominating pair of distributions. Due to the asymmetric nature of the add/remove privacy our bounds require different techniques for each of the directions. In the remove direction we derive a closed form expression for the Rényi DP [Mironov] 2017] of the dominating pair of distributions for allocation in terms of the RDP parameters of the original algorithm (Theorem 4.4). This method has two important advantages. First, it gives a precise bound on the RDP parameters of integer order (as opposed just an upper bound). Secondly, it is particularly easy to use in the typical setting where composition is used in addition to a sampling scheme (for example, when k or in multi-epoch DP-SGD). The primary disadvantage of this technique is that the conversion from RDP bounds to the regular (s, 5) bounds known to be somewhat lossy (typically within 10-20% range in multi-epoch settings). The same loss is also incurred when Poisson sampling is analyzed via RDP (refereed to as moment accounting (Abadi et al. 2016). ) Two more limitations of this technique result from the restriction to the range 2 2, and the computational complexity when is in the high tens.
For the add direction we give an approximate upper bound in terms of the usual composition of different, explicitly defined randomizer over the same domain. While this bound is approximate, the divergence for the add direction is typically significantly lower than the one for the remove direction and therefore, in our evaluations, this approximation has either minor or no effect on the maximum.
Overall, in our evaluations of this method for Gaussian distribution in most regimes the resulting bounds are almost indistinguishable from those obtained via RDP for Poisson distribution (see Fig. for examples). In fact, in some regimes it is better than Poisson sampling (Figure (5).
Numerical evaluation: In Section 5 we provide numerical evaluation and comparisons of our bounds those for Poisson sampling as well other relevant bounds Our evaluations across many parameter regimes give bounds on the privacy of random allocation that are very close, typically within 10% of those for the Poisson subsampling with rate k/t. This means that random allocation can be used to replace Poisson subsampling with only a minor loss in privacy. At the same time, in many cases. the use of random allocation can improve utility. In the context of training neural networks via DP-SGD this was shown in [Chua et al. 2024a]. Application of our bounds also lead to Asi et al. 2025J. We demonstrate that even disregarding
improvement over Poisson subsampling some practical disadvantages of Poisson subsampling, random allocation has better privacy-utility trade-off for mean estimation in low-dimensional regime. This improvement stems from the fact that random allocation computes the sum exactly whereas Poisson subsampling introduces additional variance, At the same time in the high-dimensional regime noise due to privacy dominates the final error and thus the trade-off boils down to the difference in the privacy bounds.
1.2 Related work
Our work builds heavily on tools and ideas developed for analysis of privacy amplification by subsampling, composition and shuffling. We have covered the work directly related to ours earlier and will describe some of the tools and their origins in the preliminaries. A more detailed technical and historical overview of subsampling and composition for DP can be found in the survey by /Steinke 2022]. The shuffle model was first proposed by Bittau et al. [2017). J. The formal analysis of the privacy guarantees in this model was initiated in [Erlingsson et al.) 2019 Cheu et al. 2019]. The sequential shuffling scheme that we discuss here was defined by Erlingsson et al. 2019 who proved
the first general privacy amplification results for this scheme albeit only for pure DP algorithms.
Improved analyses and extensions to approximate DP were given in [Balle et al. 2019 2020 Feldman
et al. 2021 2023
Girgis et al. 2021 Koskela al. 2022
DP-SGD was first defined and theoretically analyzed the convex setting by Bassily et al. [014]. Its use in machine learning was spearheaded by the landmark work of Abaai et al. [2016] who significantly improved the privacy analysis via the moments accounting technique and demonstrated the practical utility of the approach. In addition to wide range of practical applications, this work has motivated the development of more advanced techniques for analysis of sampling and composition. At the same time most analyses used in practice still assume Poisson subsampling when selecting batches whereas some type of shuffling is used in implementation. It was recently shown that
Pyython implementation of all methods is available in a GitHub project and in a package

---

results in an actual difference between the reported and true privacy level in some regimes
( Chua
al. c024b| Annamalai et al. 2024].
In a concurrent and independent work Dong et al. 2025 considered the same sampling method (referring to it Balanced Iteration Subsampling). Their results closest in spirit our direct bounds. Specifically, they provide RDP-based bounds for the same dominating pair of distributions in the Gaussian case for both add and remove directions. Their bound for general & is incomparable to ours as it is based on potentially loose upper bound for divergences of order a > 2, while using an exact extension of their approximation to k > 1. In contrast, our RDP-based bound uses a reduction from general & to k that is potentially loose but our computation for the k = 1 case is exact (for the remove direction which is typically larger than the add direction). In our numerical comparisons, the bounds in Dong et al.] [2025] are comparable or worse than our direct bounds and are often significantly worse than the bounds from our main result. We discuss these differences in more detail and provide numerical comparison in Appendix G.2
Preliminaries
We denote the domain of elements by and the set of possible outputs by y. Given dataset E X and output y E VM we denote by PMr Pv = P (Y y) the probability of observing the
Y~M(s)
output as the output of some randomized algorithm M which was given dataset s as input.
2.1 Sampling schemes
In this work, we consider t-step algorithms defined using an algorithm M that takes some subset of the dataset and a sequence of previous outputs as input. Formally, let y Uier 3" M takes dataset in X and view E y as its inputs and outputs value in y. A t-step algorithm defined by M first uses some scheme to define subsets s' s'..... s² C s. then sequentially computes y: M (s o"=1), where b² == (y1...., V/) are the intermediate views consisting of the outputs produced so far, and oo = 0. Such algorithms include DP-SGD, where each step consists of a call to the Gaussian mechanism (.2),, with gradient vectors adaptively defined as function of previous outputs.
The assignment of the elements in s to the various subsets can be done in a deterministic manner (e.g., s' =... s¹ s), or randomly using a sampling scheme. We consider the following three sampling schemes.
1. Poisson scheme parametrized by sampling probability À E [o, 1), where each element is added to each subset s² with probability À independent of the other elements and other subsets,
2. Shuffling scheme which uniformly samples permutation over [n]] where is the sample size, and sets s = { (in this case, the sample size and number of steps must match).
3. Random allocation scheme parameterized by number of selected steps & e [t). which uniformly samples k indices i = corresponding subsets s²1 ......""""
C [t] for each element and adds them to the
For t-step algorithm defined by M. we denote by PE,x (M) X y algorithm using M with the Poisson sampling scheme, S, (M) X >> yn for the shuffling scheme, and Ar, (M) : x > yd when M is used with the random allocation scheme. When & 1 omit it from the notation for clarity.
2.2 Privacy notions
We consider the standard add/remove adjacency notion of privacy in which datasets s, s' E X are neighboring s can be obtained from s' via adding or removing one of the elements. To appropriately augment the domain with "null" element 1, that is, we define X' == XU (1). When I-step algorithm assigns to M we treat it as empty set, that is, for any X y" we have M ( v) M(s, 1), v). We say
define sampling schemes that operate over fixed number of elements
5

---

that two datasets 8. s' E X" are neighbors and denote it by = s', if one of the two can be created by replacing a single element in the other dataset by L.
We rely on the hockey-stick divergence to quantify the privacy loss. Definition 2.1. Given k 2 0 and two distributions P.Q over some domain Ω2 the hockey-stick divergence between them is defined to be
E8 [ [
E wmp [
[1- ke:
Hx (P (P [PW)) - =Q(W)], du winq
where E (w;; P,Q) = In (())
P(w) is the ratio of the probabilities for countable domain or Q(w)
the Radon Nikodym derivative in the continuous case, and [x]] ma, When P, Q are
distributions induced by neighboring datasets = s' and an algorithm M, we refer to the log probability ratio as the privacy loss random variable and denote it by EM (1r; 8, s'). We omit M from the notation when it is clear from the context.
Definition 2.2 ([alle et al., 2018). Given an algorithm M : X + V. the privacy [0, 1] is defined to be the maximal hockey-stick divergence between the distributions induced by any neighboring datasets and past view. Formally, der(e) = sup (Hes (M(s,) v) (o(ss'.)))
profile 5m : TR.
== .v w-
Since the hockey-stick divergence is asymmetric in the general case, we use das and a to denote the remove direction where - E s' and dus = to denote the add direction when 1 Notice that (M(() ( (s)).
Another useful divergence notion is the Rényi divergence. Definition 2.3. Given > 1 and two distributions P. Q over some domain Ω the Rényi divergence between them is defined to be R., (PI()) =
1 a-1
E w-Q
[ea)(())P.11)
We now formally define privacy notions. Definition 2.4 (Dwork et al.
2006)). Given e > 0: 5 E [0, 1). an algorithm M will be called
(e, (g,))-di difffeerrnttlll private (DP), dM)()) S 5.
Definition 2.5 (Mironov] 2017)).
Given a 2 p: O, an algorithm M will be called (a, ().p))-ééy) sup
differentially private (RDP), if
(Ra, (M(s, (s', v))) S p.
S ..EY
One of the most common algorithms is the Gaussian mechanism No. which simply reports the sum of (some function of) the elements in the dataset with the addition of Gaussian noise. One of its main advantages that we have closed form expressions of its privacy (Lemma A.2
2.3 Dominating pair of distributions
key concept for characterizing the privacy guarantees of an algorithm is that of a dominating pair of distributions.
Definition 2.6 ((Zhu et al., ). Given distributions P. Q over some domain Ω, and P', ".Q' over
D. we say (P', .²') dominate (P, Q) if for all к > 0 we have Ha (P Q1 S H H.(P" || Q'). If dxr(s) < H., (P || Q) for all E R, we say (P,, Q) is a dominating pair of distributions for M. If the inequality can be replaced by an equality for all e, we say it is a tightly dominating pair. If there exist some ~ s' E X' such that P = M (8), s, Q = M (s') we say (s, 8') are the dominating pair of datasets for M. By definition, dominating pair of input datasets is tightly dominating.
We use the notion of dominating pair to define a dominating randomizer, which captures the privacy guarantees of the algorithm independently of its algorithmic adaptive properties.
Definition 2.7. Given a t-step algorithm defined by M, we say that R: [1,+} } - y is dominating randomizer for M and set R(*) = P and R(1)= = Q, where (P. Q) is the tightly dominating pair of M(.-) w.r.t. v over all indexes i E [t] and input partial views D²
Such pair always exists
Zhu et al.
2022
Proposition 8]

---

The definition of the Poisson and random allocation schemes naturally extends to the case where the internal algorithm is randomizer. In this case Pt,, (R) : {+, + y and Ar, (R) {+, + y
3 General reduction
We first prove two general claims which reduce the bound on arbitrary algorithms, datasets, and number of allocations, to the case of a single allocation (k 1) of a simple non-adaptive randomizer receiving a single element. Missing proofs can be found in Appendix B
From the definition of the dominating randomizer, for any e IR we have 5M(()) dg(e). We now prove that this is also the case for allocation scheme, that is A., S . (n) and that the supremum over neighboring datasets for Ar. (R) is achieved by the pair of datasets containing single element, that is [*]. s' {_ This results from the fact that random allocation can be viewed as a two steps process, where first all elements but one are allocated, then the remaining one allocated and the algorithm is ran for steps. From the convexity of the hockey-stick divergence we can upper bound the privacy profile of the random allocation scheme by the worst case allocation of all elements but the removed one. From Lemma Lemma[A.3] each intermediate call to the mechanism is a post process of the randomizer, which can be used to recursively define a randomized mapping from the random allocation over the randomizer to the allocation over the mechanism. Using the same lemma, this mapping implies that (A))())(E)) I (R)))))
Theorem 3.1. Given E N; k E [t] and a t-step algorithm defined by M dominated by randomizer R, we have ò (a)))()) S (R))
A special case of this result for Gaussian noise addition and k = 1 was given by Chua et al. [2024a]
Theorem I.. and in the context of the matrix mechanism by [Choquett--Chee Choo et al. [2025] Lemma
3.2]. The same bound for the Poisson scheme is direct result from the combination of Claim C.9
and Zhu et al. 2022 Theorem 11].
Next we show how to translate any bound on the privacy profile of the random allocation with k = 1 the case of k by decomposing
calls a out of t/ t/k steps allocation process.
Lemma 3.2. For any k E N, E > we have (n))))((() S 6% (n))(1)) (E)(E), where @k denotes the composition of ks runs of the algorithm scheme which in our case ALe/k! (R).
Combining these two results, the privacy profile of the random allocation scheme is bounded by the (composition of the) hockey-stick divergence between A, (R; *) and Ae (R; 1) R8* ((*( )) in both directions, which we bound in three different ways in the following section.
Privacy bounds
4.1 Truncated Poisson bound
Roughly speaking, our main theorem states that random allocation is asymptotically identical to the Poisson scheme with sampling probability Rs k/t up lower order terms. Formal proofs and missing details of this section can be found in Appendix
Theorem 4.1. Given Eg 0; 80 E [0, 1] and (8).8))- 6D) randomizer R. for any E, we have (A.( S (P),,, (e) 160 + 5, where vj == [[ー and y == min cosh(ee)) / (t), 1 - }
Furthermore, for any 5 > O and randomizer R we have (A(CR(()) S (p...( + Ae (E')
and 5 A,( - 3p,,,, (In)(E + Te -3A.1R (E'), where 17 == -.2 and T oz (et'"-11
Since 7/ corresponds to a sampling probability of 7 up to lower order term in f, this implies that the privacy of random allocation scheme is asymptotically upper-bounded by the Poisson scheme. While this holds for sufficiently large value of t, in many practical parameter regimes the second part of the theorem provides tighter bounds.
While the recursive expression might seem to lead to a vacuous loop, it is in fact a useful tool. Notice that A.,R) (E') (()) quickly diminishes E'/E grows, so it suffices to set é' Ce
7

---

for some constant 1 < C' for the second term to become negligible. Both parts of this theorem follow from Lemma C.1 which bounds the privacy profile of the random allocation scheme by that of the corresponding Poisson scheme with sampling probability 7) with an additional term roughly corresponding to a tail bound on the privacy loss of the allocation scheme.
4.2
Asymptotic analysis
Combining Theorem with Lemma 3.2 and applying it to the Gaussian mechanism results in the next corollary.
Corollary 4.2. Given 5, > 0, for any a > 8 max { Fun(//))//En(())))))) we have
(A)) < (N.) 26, where No is the Gaussian mechanism.
Using this Corollary we can derive asymptotic bounds on the privacy guarantees of the Gaussian mechanism amplified by random allocation. Since the Gaussian mechanism is dominated by the one-dimensional Gaussian randomizer (Claim D.3) where R(+)) _V1, and R(1) (0, a²), this corollary implies that for sufficiently large a, the random allocation scheme with the Gaussian
Rvln(e/5) x² x²v/nn(e/5) ovi
mechanism Ar, (No) is (c, 8)-DP for any Cm
for some universal
constant C (Lemma D.2). We note that the dependence of E on σ; 6; k; and t matches that of the Poisson scheme for X = k/t (Lemma D.I) up to additional logarithmic dependence on t (Poisson scales with ()), unlike the shuffle scheme which acquires additional /In(1/8) by converting approximate the DP randomizer to pure DP first, resulting in the bound 2 C" k-Im(1 /6) Feldman avt
et al. 202T]. A detailed comparison can be found in Appendix
The recursive bound (second part of Theorem 4.1 provides similar asymptotic guarantees for arbitrary mechanisms, when Eo < 1 for the local mechanism M. In this case, the privacy parameter of its corresponding Poisson scheme Ep is approximately linear the sampling probability. Setting the sampling probability to 1/t and combining amplification by subsampling with advanced composition
implies εp
0 neo / In(1/6)) = O In(2/6)
Setting s' = -Cep for some constant
1 < C < 1/ép, we get A 0 175 t- ln(1/8) = 2
In(1/8)
= O + +
While Theorem 4.1 provides full asymptotic characterization of the random allocation scheme, the bounds it induces could be suboptimal for small t or large Eg. In the following section we provide several bounds that hold in all parameter regimes. We also use these to "bootstrap" the recursive bound.
4.3 Poisson Decomposition
Theorem 4.3. For any > we have (,) - (p))(()))) and 8 A. (E) < - (m)
where o = 1-11- x 3 = 1 + - É = In(1+ - 1) and == In (1 (1 - c 1/7).
We remark that while this theorem provides separate bounds for the add and remove adjacency notion&" Fi] numerical analysis seems to indicate that the bound on the remove direction is always larger than the one for the add direction.
Setting À = 1/t yields 7 ~ e/(e 1) x 1.6, which bounds the difference between these two sampling methods up to this factor in e the regime.
Formal proofs and missing details can be found in Appendix
4.4
Direct analysis
The previous bounds rely on a reduction to Poisson scheme. In this section we bound the privacy profile of the random allocation scheme directly, which is especially useful in the low privacy regime
An earlier version of this work has mistakenly stated that an upper bound for the remove direction applies to both directions.

---

where the privacy profile of random allocation is lower than that of Poisson. Formal proofs and missing details of this section can be found in Appendix FF
Our main result expresses the RDP of the random allocation scheme in the remove direction in terms of the RDP parameters of the randomizer, and provides approximate bound in the the add direction While the privacy bounds induced by RDP are typically looser than those relying on full analysis and composition of the privacy loss distribution (PLD), the gap nearly vanishes as the number of composed calls to the randomizer grows, as depicted in Figure
Theorem 4.4. Given two integers i, E N. we denote by [o.())) the set of integer partitions of a!
consisting of S t elements. Given a partition II E [a), we denote by (it) Il and denote by C(Il) the list of counts of unique values in P (e.g. if a 9 and II = [1, (1,2,3,3) then
C(I) = 1, For any and randomizer R we have
Ra (Ai (R: x) (AA
In
1 ta
Σ (a
((L))
a II
II PEn
(p-- R
For the add direction we use different bound.
Theorem 4.5. Given Y E [0,1] and randomizer R, we define new randomizer R., which given imput samples For any & we have 3 (A) He (ReI(L)
where Try is the normalizing factor.
(+)) where = E
These two theorems follow from Lemmas R.1 and
F33 for P = R(*) and Q = R(1).
As is the case in Theorem 4.3 numerical analysis seems to indicate the bound on the remove direction always dominates the one for the add direction.
Since we have an exact expression for the hockey-stick and Rényi divergences of the Gaussian mechanism, these theorems immediately imply the following corollary.
Corollary 4.6. Given
0, and Gaussian mechanism No, we have for any integer a 2
Ra (Ai (No: (0))
In
Σ
a
each
20
2
a
(
-In(t)
C(II)
II
20
[Ell.
and A.(N))()) S ON,, (s') where o' Vla and el = 1-1ft for all R.
Corollary 4.6 gives simple way to exactly compute integer RDP parameters of random allocation with Gaussian noise in the remove direction. Interestingly. they closely match RDP parameters of the Poisson scheme with rate 1/t in most regimes (e.g. Fig. 6). In fact, in some (primarily large s) parameter regimes the bounds based on RDP of allocation are lower than the PLD-based bounds for Poisson subsampling (Fig. 55) The restriction to integer values has negligible effect, which can be further mitigated using [Wang et al. 2019 Corollary 10), which upper bounds the fractional Rényi divergence by linear combination the Rényi divergence of its rounded integer values. We also note that [a)) ) is sub-exponential in a which leads to performance issues in the very high privacy 1) regime (Large values Fig IT. Since the typical value of a used for accounting is in the low tens, this quantity can be efficiently computed using several technical improvements which we discuss in Appendix [F.T] On the other hand, in the very low privacy regime (5 > 1), the that leads to the best bound on E is typically in the range [1, 2) which cannot be computed exactly using our method. Finally, we remark that while this result is stated only for k 1, it can be extended to k > using the same argument as in Lemma 3.2 In fact, RDP based bounds are particularly convenient for subsequent composition which is necessary to obtain bounds for algorithms.
multi-epoch training

---

1,000
10,000
000 C91
1.00
157
133
151
LTL
2.20
2.50
0.65
6.74 043
0.55
L.7
1.53
1.3
1.50
177
2.00
0.00
0.63
0.66
049
0.72
0.75
0.79
0.52
0.8 200
Ep Polsson (PLD)
-B- E, Allocation (Our Combined)
Allocation (DC025
K. Allocation (CGHKOLMSZ24 Lower Bourd)
Figure 2: Bounds on privacy parameter as function of the noise parameter a for various values t, all using the Gaussian mechanism with ó 10 10 We compare the minimum over all our methods to the independent results in Dong et al. (2025), lower bound by Chua et al. 2024a], and to the Poisson scheme with À = 1/t.
Numerical evaluation
In this section demonstrate that numerical implementations of results give the first nearly- -iight and provable bounds on privacy amplification of random allocation with Gaussian noise, notably showing (Fig- 2 that they nearly match bounds known for Poisson subsampling. Compared the Monte Cased technique by Chua et al. 2024a (..] we show in many regimes our results match these bounds up constants in (logarithmic in E), and the computational limitation of the MC technique in the low and high confidence level regime. We additionally compare our results to the RDP-based approximation by Dong al. [2025] G.2 and demonstrate the advantage of our tight RDP analysis in the regime where k < L. Their bound is tighter than our direct analysis in the k Rs / regime, where the effect of amplification is small and is prohibitively large.
We demonstrate the utility degradation induced by Poisson subsampling relative to random allocation using the simple setting of estimating the mean of Bernoulli distribution from a sampled dataset (App.H) H). We derive theoretical approximations for the mean square error of the two schemes and match them with numerical simulations, that demonstrate random allocation always has lower for sufficiently large sample size. Together with the results of Chua et al.) [2024a], our results imply that random allocation (or balls-and- bins sampling) has the utility benefits of shuffling while having the privacy benefits of Poisson subsampling. This provides a (reasonably) practical way to reconcile long-standing and concerning discrepancy between the practical implementations of DP-SGD and its commonly-used privacy analyses.
Discussion
This work provides the first theoretical guarantees and numerical estimation algorithms for the random allocation sampling scheme. Its main analysis shows that its privacy guarantees are asymptotically identical to those of the Poisson scheme. We provide two additional analyses which lead to tighter bounds in some setting (Fig. [T. The resulting combined bound of the random allocation remains close to that of the Poisson scheme many practical regimes (Fig. 2 and even exceeds Unlike the Poisson scheme, our bounds are analytical and do not rely numerical PLD analysis, which results in some remaining slackness. Further, unlike PLD-based bounds, our (s, 5) bounds do not lend themselves for tight privacy accounting of composition. Both of these limitations addressed in our subsequent work [Feldman and Shenfeld (025) where we show that PLD of random allocation can be approximated efficiently, leading tighter and more general numerical bounds.
some.
$ An earlier version of this work has mistakenly stated that an upper bound for the remove direction applies to both directions.
10

---

Acknowledgments and Disclosure of Funding
We are grateful Kunal Talwar for proposing the problem that we investigate here as well as suggesting the decomposition-base approach for the analysis of this problem (established in Theorem 4.3). We thank Thomas Steinke and Christian Lebeda for pointing out that an earlier version of our work mistakenly did not analyze the add direction of our direct bound. We also thank Hilal Asi, Hannah Keller, Guy Rothblum and Katrina Ligett for thoughtful comments and motivating discussions of these results and their application in [Asi et al. 2025]. Shenfeld's work was supported by the Apple Scholars in AI/ML PhD Fellowship.
References
Martin Ahadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
Meenatchi Sundaram Muthu Selva Annamalai, Borja Balle, Emiliano De Cristofaro, and Jamie Hayes. To shuffle or not to shuffle: Auditing dp-sgd with shuffling. arXiv preprint arXiv:2411.1661 2024.
Hilal Asi, Vitaly Feldman, Hannah Keller, Guy N. Rothblum, and Kunal Talwar. PREAMBLE: Private and efficient aggregation of block sparse vectors and applications. Cryptology ePrint Archive, Paper 2025/490, 2025.
Borja Balle and Yu- Xiani Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. International Conference on Machine Learning, pages 394-403. PMLR, 2018.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. In Advances in Cryptology 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part 11 39, pages 138-667. Springer, 2019.
Borja Balle, Peter Kairouz, Brendan McMahan, Om Thakkar, and Abhradeep Guha Thakurta. Privacy amplification via random check-ins. Advances in Neural Information Processing Systems, 33: 4623 4634, 2020.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464 473. IEEE, 2014.
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings the 26th symposium on operating systems principles, pages 441 1-4,,, 2017.
Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 13:15676-15688, 2020.
Wei-Ning Chen, Dan Song, Ayfer Ozgur, and Peter Kairouz. Privacy amplification via compression: trade-off in distributed mean estimation. Advances in Neural Information Processing Systems, 36, 2024.
Achieving the optimal privacy.ccurayyycommuiic
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Advances in Crypolloy-EUROCCYT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I 38, pages 375-403. Springer, 2019.
11

---

Christopher Proqueete-Chooo Arun Ganesh, Saminul Haque, Thomas Steinke, and Abhradeep Guha Thakurta. Near-exact privacy amplification for matrix mechanisms. In Y. Yue, A. Garg. N. Peng, F. Sha, and R. Yu, editors, International Conference on Representation Learning, volume 2025, pages 98772-98802, 2025.
Christopher A Choquette- Choo, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Privacy amplification for matrix mechanisms. In The Twelfth International Conference Learning Representations, 2023.
Lynn Chua, Badih Ghazi, Charlie Harrison, Pritish Kamath, Ravi Kumar, Ethan Jacob Leeman, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. halls-and-bingg sampling for dp-sgd. In The 28th International Conference on Artificial Intelligence and Statistics, 2024a.
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. How private are dp-sgd implementations? In Forty-first International Conference on Machine Learning, 2024b.
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Scalable dp-sgd: Shuffling vs. poisson subsampling. Advances in Neural Information Processing Systems, 777-70026-70477, 2024c.
Andy Dong, Wei-Ning Chen, and Ayfer Ozgur. Leveraging randomness in model and data partitioning for privacy amplification. In Forty-second International Conference on Machine Learning, 2025.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, (114))211-407, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EUROCRYPT Crypology-ERRoCRYP
2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques. St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486-503. Springer, 2006.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1669.4479. SIAM, 2019.
Vitaly Feldman and Moshe Shenfeld. Efficient computation of the privacy loss distribution for random allocation, 2025. URL TRRLittts///opereriiiie nott/forunidddDDPWW1l.2233
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 202 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954-964. IEEE, 2021.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for rényi and approximate differential privacy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4966-4981. SIAM, 2023.
Antonious M. Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of federated learning: Privacy, accuracy and communication trade-offs. IEEE Journal on Selected Areas in Information Theory, 2(1) 2(1):464478, 2021.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385 PMLR, 2015.
Shiva P Kasiviswanathan and Adam Smith. On the 'semantics' of differential privacy: A bayesian formulation. Journal of Privacy and Confidentiality, 6(1), 2014.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793 8266, 2011.
Antti Koskela, Mikko A Heikkilä, and Antti Honkela. Numerical accounting in the shuffle model of differential privacy. Transactions on Machine Learning Research, 2022.
12

---

Seng Pei Liew and Tsubasa Takahashi. Shuffle gaussian mechanism for differential privacy, arXiv preprint orXiv:2206.09550 2022.
Xin Lyu. Composition theorems for interactive differential privacy. Advances Neural Information Processing Systems, 35:9700-9712, 2022.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security symposium (CSF), pages 263-275. IEEE, 2017.
Mehta Neelesh B., Wu Jingxian, Molisch Andreas F., and Zhang Jin. Approximating a sum of random variables with a lognormal. Transactions on Wireless Communications, 6(7):2990-299,, 2007.
Thomas Steinke. Composition differential privacy & privacy amplification by subsampling. arXiv preprint arXiv:2210.00597, 2022.
Salil Vadhan and Tianhao Wang. Concurrent composition of differential privacy. In Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 6-11, 2021, Proceedings, Part Il 19, pages 582-604 Springer, 2021.
Salil Vadhan and Wanrong Zhang. Concurrent composition theorems for differential privacy. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 507-519, 2023.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. The 22nd International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR, 2019.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pages 1782-4817, PMLR, 2022.
13

---

A Missing definitions and claims
Since Rényi divergence is effectively a bound on the moment generating function, it can be used to bound the hockey-stick divergence which is effectively tail bound.
Lemma A.1 (Rényi bounds Hockey-stick, Prop. 12 in Canonne al. (020 P. P.Q. if R. (PIIQ) S then He
Given two distributions
|| Q
- el Me-- d)
Lemma A.2 (Gaussian mechanism DP guarantees, [Balle and Wang 2018 Mironov 2017 0. let X y Rd. The Gaussian mechanism No is defined as
Given d N; (s) = NN I.)
If the domain of No the unit ball in Rd, we have (s) = & 2 - Eα) - - (- EA). where & is the CDF of the standard Normal distribution, and for any a 2 No is )
An important property of domination is its equivalence to existence of postprocessing.
Lemma A.3 (Post processing, Thm. 11.5 Kairouz et al. 2015)). ). Given distributions P. over some domain Ω and Pt, ,', Q' over S (P, Q) dominate (P", Q') if and only if there exists a randomized
function yp Q Q such that p = (P)) and Q' (()).
B Missing proofs from Section 3
Proof of Lemma 3.7 Given n E dataset & x and element æ E X, the random allocation
scheme A (M; (s, 2)) can be decomposed into two steps. First all elements in s are allocated, then x is allocated and the outputs are sampled based on the allocations. We denote by at n 1) the set
of all possible allocations of n elements into out of / steps, and for any a E aa**(n (n 1) denote
by (M: x)) the allocation scheme conditioned on the allocation of according to a. Given the neighboring datasets (s,x) x) and (s, -) we have,
Hx (Ar, (M: x)) || (M; (s, 1)))
H (ati(n- - aEa (n-1)
Σ
(M;
Σ (i.(M;(0,1))
aa (pinn-)
1)]
(n-1:
(H (Ai ()) (M
max oEa (n-1)
and similarly,
H (Ar, (8; Ar, (M; S
max
(Hn (M; (M;
eEat. (n-1)
where the inequality results from the quasi-convexity of the hockey-stick divergence.
Fixing a to be the allocation that maximizes the right-hand side of the inequality, we denote by 81...., 8, the subsets defined by a From the definition input prefix view va-1 we have (Tt(*). R(L)) dominates (M((s), ,x), w M((s), L), w so from Lemma A.3 there exists randomized mapping Pa5-1 such that M((s). .x), w
randomizer, for any index j E [(] and
Pp,-11 (R(+)) and M[s -), 1- Pus-1 (R())) Using these mappings,
will recursively
define another randomized mapping s. Given an output view v E yd, we define o' ~ (pv) by sequentially sampling v/ Pus (3))) for 1,...,& ft where v (yI...., ................................ }1) and w := 0.
We will now prove that (M; (s.z) z)) p(Ar, R)) and AC, (M; 1)) = p(Ar, k (R; 1)). which by invoking Lemma A.3 again, implies Ar, (M) is dominated by Ar, (R) and completes the proof.
'Conceptually, this is equivalent to considering the random allocation scheme over single element with sequence of mechanisms M,, defined by the various subsets.
'We note that depends on s and as well. We omit them from notations for simplicity, since they are fixed at this point of the argument.
14

---

From the law of total probability we have,
1
Σ ic
1 (
Σ icl i|=b
II
(M (vllu) .2)
(H)
and
(R))())))(
1
E (A)e(R:))((11) ac
PA (Ro (
Σ
II
(
where i [t] denots the allocation of the single element
Using these identities, suffices to prove that for any subset of indexes i, index j E [t]. and input prefix view wJ- we have PAy, (M:((E)))) (wi (w'lou-1, (o(A))((=))) (v 10 ,2) and
PAr,
(w (o (D)
From the definition,
(MR (v" (0- PA 1 ,))
(Mr((e)a)), 1)(i)) jei
PMr((ar.1:::))((()) j j
(Pws-(((()(()))) jei PPw ((((L))
j x
PP(AA)((:)))) o 1- =Pocd, (v)) 10-1, i). i).
In the of the null element, the allocation doesn't 't have any effect so have,
( ('=1) PMr((a).)) (1;)) P PoCA PoCA) (v' w-1
which completes the proof.
Proof. [Proof of Lemma 3.2) Notice that the random allocation of indexes of can be described
two steps process, first randomly splitting into k subsets of size t/k, 8 then running Ae,k,1 (R) on each the & copies of the scheme. Using the same convexity argument as in the proof of
Lemma 3.1 the privacy profile of Ar, (R) is upper bounded by the composition of l copies of A1/k.1 (R)).
We remark that this lemma holds for arbitrary 1-step algorithms (and not just non-adaptive random- izers) but in the adaptive case the usual sequential composition should be replaced by concurrent composition [Vadhan and Wang 2021], which was recently proven to provide the same privacy guarantees Lyu 2022
Vadhan and Zhang 2023
C Missing proofs from Section 4.1
Lemma C.1 (Analytic bound). For any E > 0 and 17 E [1/t, 1] we have (x) S (m))
(A) and (E) < (R) B (1)) where (AI(R)()) PARRR:) (B(r)).
AA (1) = PA(RR ()tt))((BBBi) (B(r)). and B(n) = v E yr-1
max (6 (((0')L, > In(tn))
sE[t-1]
Theorem 4.1
follows from this lemma by identifying the total loss with a sum of the independent losses per step and using maximal Azuma Azuma-Hoeffdiin inequality. Theorem44.ffllowww from this lemma by using a simple relationship between the privacy loss tail bound and the privacy profile.
The proof of this lemma consists of a sequences of reductions.
For simplicity assume that is divisible k.
15

---

Following [Erlingsson et al. 2019], we introduce the posterior sampling scheme (Definition where the sampling probability depends on the previous outputs. Rather than selecting in advance a single step, at each step the scheme chooses to include the element with posterior probability induced by the previously released outputs Au == (A((R=)) (i + E T where I the subset of chosen steps.
Proof.
Though this scheme seems like a variation of the Poisson scheme, we prove (Lemma C.4 that in fact its output is distributed like the output of random allocation, which implies they share the same privacy guarantees. The crucial difference between these two schemes is the fact that unlike random allocation, the distribution over the outputs of any step of the posterior scheme is independent of the distribution over output of previous steps given the view and the dataset, since there no shared randomness (such as the chosen allocation).
We then define truncated variant of the posterior distribution (Definition C.5 where the sampling probability is capped by some threshold, and bound the difference between the privacy profile of the truncated and original posterior distributions, by the probability that the posterior sampling probability will exceed the truncation threshold (Lemma C.6
Finally, we bound the privacy profile of the truncated posterior scheme by the privacy profile of the Poisson scheme with sampling probability corresponding to the truncation threshold, using the fact the privacy loss is monotonically increasing in the sampling probability (Lemma C.8). which completes the proof. Part of these last two lemmas is a special case of the tail bound that recently proved in CChqueete-Choo et al. 2023 Theorem 3.1].
Formally,
(2) (R) (m)()) S (m)) ( (1) S (E)
(3)
where (I) results from Lemma C.4 (2) from Lemma C.6 and (3) from Lemma C.8
The same proof can be repeated as is for the add direction.
Remark C.2. Repeating the previous lemmas while changing the direction of the inequalities and the sign of the lower order terms, we can similarly prove that the random allocation scheme upper bounds the Poisson scheme up to lower order terms, which implies they are asymptotically identical.
Throughout the rest of the section, claims will be stated in terms of R and for simplicity, but can be generalized to M and x. We note that A (R; L) = (LL( where R (L) denotes t sequential calls R(L), an identity which will be used several times throughout the next section
C.1 Posterior scheme
We start by introducing the posterior sampling scheme, where the sampling probability depends on the previous outputs.
Definition C.3 (Posterior probability and scheme). Given subset size k E [t], an index i E [t 1]. a view e² E y", and randomizer R, the + 1 posterior probability of the allocation out of t given of is the probability that the index + 1 was one of the k steps chosen by the random allocation scheme, given that the view o² was produced by the first i rounds of Ae (R; *). Formally, Api,k = PA., (i+ 1 I''' where I the subset of chosen steps.
The posterior scheme a function Tr, (R) : (+, 1} + Y" parametrized by a randomizer R, number of steps I, and number of selected steps k; which given *, sequentially samples
Vi+1 (Awt R(*) (1 > R(1)),
where Amo,a = k/t, and Te, (R; L) A (R: .). As before, we omit l from the notations where
Though this scheme seems like variation of the Poisson scheme, the following lemma shows that in fact output is distributed like the output of random allocation.
Lemma C.4. For any subset size k E [t] and randomized R, A (R; *) and Te, (R; x) are iden- tically distributed, which implies (A))(R)(E) (T,,(R)(()) (8) and 8 (E)(((())) 8T,, for any randomizer and all 2 O.
16

---

Proof. We notice that for all j E [t 1] and v E )d,
(B))(R)))( = (ANe(R==)(OUtt))
(A)W(B(((V)
Σ
PA I=
ig =k
(Ro) (15)
Σ
P (W)) I= -) (ALt(R = i, v²)
2 aC E mk
PACA(RA)(OO)
(AL((R;)) , PR(L)(US+1)
I=
Σ
PAln(Re)((
=k
(v)
Σ
PR(.)(U5+1)
(ALA(Bi)((s))
(R + I(0'). PROCy(U512l0)) (A +1 Il00) PR(1)(U1+1) (1 )wi PR(L)(US+1) Avi l (R())(U+2a) (3) (b)
where (1) denotes the subset of steps selected by the allocation scheme by so I = i denotes the selected subset was (2) results from the definition wJ+1 (v) 4j+1) and Bayes law, (3) from the fact that if j + 1 then 4/+1 depends only on a and if j + 1 I then Uj+1 depends only on L. and (4) a direct result of the posterior scheme definition.
Since ((v[+) x) = [ P(vit1|* v²) for any scheme, this completes the proof.
C.2 Truncated scheme
Next define truncated variant of the posterior distribution and use it to bound its privacy profile.
Definition C.5 (Truncated scheme). The truncated posterior scheme is function Tr,k,n (R) [*. - ) parametrized by a randomized R, number of steps f, number selected steps k and threshold 77 E [0, 1], which given *, sequentially samples
Vs+1 ~ (X R(*) + (1 2 R(L)).
where X3 2 min As m) and Te,k. (R: 1) Te, (R: 1).
Next we relate the privacy profiles of the posterior and truncated schemes.
Lemma C.6. Given a randomizer R, for any 17 E [k/t, 1]: > 0 have
and (T) 8 (R))), +B (A()))))) where (T) and 3 A., (1) were defined in Lemma C.I
(T.)(R(()) S (R)()())(E))) + (A)(R)()))
(
The proof of this lemma relies on the relation between Aue and the privacy loss of the random allocation scheme, stated in the next claim.
Claim C.7. Given i 1), randomizer R, and a view of we have dur te (=(A)c))(0(;1..))
17

---

Proof. From the definition,
Avi PA( (1 1= = 1111
(1) PANCRA)) (0' = -
PAI(RiO) (v))
(2) PAI(RAL) (v')
t PA((Ri)) (v))
where (I) results from Bayes law and (2) from the fact P(I=i+1) = 1 and
PA(R=)) (v' 1 PA((R:L)) (v*).
} for any C C )d we have
Proof of Lemma C.6
Denoting By = y"
max (Nus) > m7.
iE(L-1]
P (V EC)
V~T((R:+)
P V~T((R
(V VEC/BB) + P
(V (VECnB))
V~Ta(H::))
P (RTe((R:t)
(V (VEC/B)) +
P
(V (VECNB))
V~T((R))
es
P (-TTa(R.L)
(V E Her (Ten (Ri*) |l Te. (R; (R;
P
(V BBy))
V~T((R:))
See
P (V EC) + Her (Te, (R; Te. (R: 1))+
F
(V E BB),
(R.I.(
V-T((R:)))
which after reordering the terms implies
(2)
He (R; 11 Te (R: 1)) < Her (Te, (R;*) || Te. (R; 1))
P V~T((R:))
(V E BB)).
and similarly,
He (T & H. (Te, (R: Te,, (R:+))
P
(Ve E Bb) VeBB).
V~TT(R:1))
where (1) results from the definition of the truncated posterior scheme and the set By (2) from the fact that for any couple of distributions P, Q over some domain y
(Y
H (P 1 = sup cey
P. V>P
(Y - é P
V~Q
and (3) from the definition of (A,m Combining this with Claim
C.7 we get
P (V E BB)
P V~T((R:))
max (Nor) > 1)
V~T:(Rea)
(E((-1)
P V~T((Ra))
max
(LA,(1)) (+)) In((n))
[E([-1]
(A)(R)))),
and similarly
(V E TEB (1)
(=..(
We now relate the truncated scheme's privacy profile to Poisson.
18

---

Lemma C.8. Given of E [0,1] and randomizer R. we have (R) & (p.)(R)(E) and O.
(T), S p (e)() for all
The proof makes use of the following result.
Claim C.9 (Theorem 10 in (Zhu al. 2022 If pair of distributions (P.Q) dominates ran- domizer R and (P', Q') dominate R², then (P x P', Q Q') dominate the composition of R and R'.
C.8 We first notice that the the hockey-stick divergence between a mixture dis- tribution AP + f]Q and its second component Q is monotonically increasing in its mixture parameter A. For any < X < X < 1 and two distributions Po. P1 over some domain, denoting X Qx = (1 P + AP1 we have, Qx 1 Qx + 1-X Pr. From the quasi-convexity of the
Proof of Lemma
hockey-stick divergence, for any K 2 0 we have
1-
X Pi IIR
H. P1) = H
1- Qx +
HH (Qx PT),
1- X
and similarly, H (Pi Qx S H (P. Qx)..
Using this fact we get that the privacy profile of single call Poisson subsampling algorithm is monotonically increasing in its sampling probability w.r.t. both v and =, so the privacy profile of every step of Te., (R) is upper bounded by that of Pi.,, (R), and from Claim C.9 its times composition is the dominating pair of Pt., (R), which completes the proof.
C.3 Proof of Lemma C.1
Proof. The proof directly results from combining the previous lemmas.
(2)
(3)
(R) (E) (R), BARR) (1) S (R)) (A)))())
where (I) results from Lemma C.4 from Lemma C.6 and (3) from Lemma C.8
The same proof can be repeated as is for the add direction.
C.4 Proof of the first part of Theorem 4.1
We first reduce the analysis of general approximate-DD algorithms to that of pure-DP ones, paying an additional lôg term in the probability.
Claim C.10. Given Eo > 0; 50 E [0 and a (co, 5o)-DP randomizer R, there exists randomized i which is eo-D,, such that (R) < 3 Ae, (n) + 18g and B AR) (11) < B AA.. (1)))))))))))))))) 100.
where & (TI) was defined in Lemma C.1
Proof of Claim C.10 From Lemma 3.7 in Feldman et al. 2021]. there exists a randomizer å which
e such that R(1) = R(L) and Drv [R(+))[{(+)) S 8n-
For any consider the posterior scheme Tr,,.())
R which Vj returns
Vj+1 ~ (NeS,N R(*) + (1 >vs.k) R(1)),
and Vj= 2 i returns
Mj+1 (Not f((*) (1 (1-Npi,)) ie(1))
Notice that Tr,,,(0) (R) Te. (R) and Tr,s,(t) (R) = Te.k (R). From the definition,
for any E [1] we have DTV (Tek.1t-1) (R;=)) [Te,,e()) (
< dp. which implies
Drv (Te, (R; |[T (R:*))
tōo.
Combining this inequality with the fact that for any two distributions P, Q over domain Ω and subset C C Q we have P(C) < Q(C) + Drv completes the proof.
D
19

---

Next we provide closed form expression for the privacy loss of the random allocation scheme. Claim C.11. Given an index
[t] and a view v² E 3d we have,
(lalusin.)) ))
(A((R) (ot;,, In
t-i+ Σ
JEB
Proof. From the definition,
(m Pm(L)(Us)) P((()((t))
(IIj-i Pr())(S)) isi
(a(mm)(0'11=)) i)
[met Pn(1)(3m)
j }>
which implies,
PRc-)(Me)
jsi
PR(1) (v:)
PA((R.L((O))
j>i
Using this identity we get,
(A.(R) (0);+, PAI(R:))(')
(A(()_L)(oo))
E PAI(Rie)( =
In
(o0
PR(a) (1/ (20-11
In
i
PR(1) (15 (ev--1)
5E(i)
In
1- i + Σ (((rttt,1)
We are now ready to prove the corollary.
Proof of Theorem 4.1
Using Claim C.10 we can limit our analysis to cn-pure DP randomizer. We
have
(A.(R) (1)
P V~de(R:+)
max iE[[-1]
(EA((R) (Vi, In(tn)
P
max sElt]
1-i+ EjEtg cln((sit))) 21)
(R;+(
1+ EsEn (c(x(150o))))) 17 ) > >1|1=1)
1 Σ
P
max KElt
7 LE|t
V-
Σ (1-dd((kst4)) > 2((1_)) mn 1 (1-1)
P (R=x(
max VEM
LET(
JE
where (1) results from Claim C.T. and similarly,
-a-ea0sinn >6 >1
BA.CR) (1) S
P
(m)
(-A.(
xE|d]
We can define the following martingale; Dn 0, V. 1]: Dj 1 cn((),) and
S, == Ee Dj. Notice that this is a sub-uurtingg mortingate since for any j E It - 1]
PR(.
E i En(Y)o)))] =1 Y~R(L)
Y>R(L)
(Y)
20

---

and
[ ((RO)))))) =1 exp [Rg (R(*) [
I YmR((a)
S 00,
where R. is the a- Ré-éé divergence (Definition 2.3
From the fact R is ep-DP we have 1 - e < Dj S 1- - 6 almost surely, so the range of D2 is
bounded by e e E cosh(Eo), and we can invoke the Maximal Azuma-Hoesa Homa-Hoeffdiig inequality and get for any 1 E [t].
Σ (1
> (111111 1 11 11-1)
IP
max iE[t]
(R()(
JEM
(1- >((1-1))
Σ (1
iE((]
> 1 1
tm ))
P
max KE[0]
(C.)
2
tn
exp
2
tn cosh(EE))
1
< exp
2
cosh(Eo)
where the last two steps result from the definition of 17 and
C.5 Proof of the second part of Theorem 4.1
The proof makes use of the following result.
Claim C.12 (Part 2 of lemma 3.3 in Kasiviswanathan and Smith 2014)). Given e > 0; 5 E [0,1] and 8DD algorithu M, for any neighboring datasets have,
IP (Y(;ss,')) 22) 28
Y~M(()
Proof. Consider the following algorithm based the randomizer Ry {x, 1 4r - y which is
(R()) (A.(M) (v';1,*) 1,+) In(tn)
defined by (1; R(L), and (x; (((L) (A,()) (0'; 2 In((r))
Given view denote
arg min (BA((R) (0": (n((t)))
max (LA.(R) (ot: +.) In(tr) (E(t-1
ie[t-1]
i0
(EA.(R) (Dt: < In((n)
max KE(t-1]
the first index where the privacy loss exceeds In(tr) if such index exists and otherwise, and notice that,
(A(()) (v: 1,+) (1) In
In t in + Ere(te) efn(uus.
1 Eiefo cfn(ve=
where (1) results from Claim C.I and (2) from the definition of R. which implies the distribution of R,, (x; vi) R., (1: for all j > ig.
We note the journal version has typo in the ê part of the statement, which does not match the proof. We the corrected version which appears the Arxiv version.
21

---

Using this fact we get.
[A.(R) (1) (1)=
P
max seft-1]
(CAI(R) (o²: +++) In(tn)
v~di(Ii:))
①
F
(RA,(R) (0'o: > In(tn))
V~Ai(R
2
P
t- ΣSE(ho) ( (n( 211
V~Ai(R:;)
(3)
P
V~Ai(RR;s)))
(-io+Eselk)) (l clalusio.1
(4)
P
(CA((R,) (V: In(tn))
(~
(5)
P
(LA.(R,) (Vi > In(tn))
br (~Ai(R
16
2
In((n)
Ae(R.)
tn Vtn
(7)
In(tr)
3 Ac(R)
In Vii
2
A. (E'),
and repeating all steps but (5) we similarly get,
B AA (1) S TE22' 3 AR) (s"),
where (1) results from the definition of ip (2) from Claim C.II (3) from the definition of R,y (4)
from the previous identity, (5) from the definition of the privacy loss, (6) from Claim C.12 (7) from the fact R, is dominated by R, and (8) from the definition of v) and
C.6 Separate directions
For completeness present the results of figure for the add and remove directions separately for single and multiple allocations.
10.00
(LLB)
Alceation (Our-Drect
Mlssalon (Our Decompasber)
130
Ep Locoo
Eo Feisson FLD!
Albcation (Our Direst
Albuaiin (dur Recumiel
(a) Add direction
Remove direction
Figure 3: Upper bounds privacy parameter or the add and remove directions as function of the noise parameter for various schemes, all using the Gaussian mechanism with fixed parameters 8 10 -10 the same setting as Figure]]
10
22

---

Local
C Local
Z-- Polsson IRLD)
6-- Foleson (PDD)
Alecation l0ur Direct
Albcation (Our Dreet)
3.
14
(a) Add direction
(b) Remove direction
Figure 4: Upper bounds on privacy parameter or the add and remove directions as function of the noisc parameter for various schemes, all using the Gaussian mechanism with fixed parameters å = 10 10 10-10, k 10, the same setting as Figure
10
D Asymptotic analysis
We start by recalling the asymptotic bounds for the Poisson scheme due to Abadi al. 2016
Lemma D.1 ([Abadi al. 2016)). There exists constants C1s 02
such that for any E N; then the Poisson scheme with
/im(L/6)
E [0, 1/16); 5 E [0, 11, ift 2 In(1/8) and a max 1,0
Ave
the Gaussian mechanism Pt,x (No) is 8)-P for any 2 02 X X2 At ///t.In(1/// (1(1)))
This is a direct result of the fact the Gaussian mechanism is dominated by the one mi-dimmesionna Gaussian randomizer (Claim D.3) where I((*) = (1, o²) and R(_) NO o²). Combining this Lemma with Corollary 4.2 implies similar result for the random allocation scheme.
Lemma D.2. There exist constants C22 C2 such that for any N; l [t/16]: [0, 1]:
a 2 G1 max Vin(t/5), (T In(e//),
(n In(e/h)
k
then the random allocation scheme with the Gaussian mechanism Ar (No) (),8)-DP for any /1/1//))
(in11/8)
2 02 max
ovi
The second term in the bound is due to the privacy profile of the Poisson scheme, and applics only in the uncommon regime when > t/k. One important difference between the privacy guarantees of the Poisson and random allocation schemes in the bounds a, which are stricter for random allocation in the & > Vt regime (Remark D.4).
The proof of this Lemma is based on the identity of the dominating pair of the Gaussian mechanism.
Claim D.3 (Gaussian randomizer (Abadi al. 20166). Given 0, the Gaussian mechanism N, tightly dominated by the pair of distributions (1,, (0. o2), which induce a Gaussian randomizer where = and 1 = 0. This pair can be realized by datasets of arbitrary size n of n-1 times
vectors in dimension d by the pair (6..... E1). (0.
We note that the dominating pair of the Gaussian is one dimensional, regardless of the dimension of original algorithm.
Ths is variant of Abadi et al. 2016 Theorem I] that is better suited for comparison. We prove this version
in Appendix C
23

---

Proof of Lemma D.2 From Theorem 4.1 each of the schemes has privacy profile 6 ( (E) S oe. (m)(() + t/koo + 8/k. Applying the union bound to the t/kôn and 6/k terms, and using the fact that the composition of Poisson schemes is longer Poisson scheme completes the proof of the first part.
(see e.g., Dwork and Roth (2014) for exact derivation). From the first bound on get Eo s ' and therefore cosh(EE) (E"o e e/2 35o/2. Combining this with the second bound on a we get,
From Lemma A.2 we have Eo
2 In 1.25/6o) /6)
2 (n( (5t//8)
k
2 1n(1 (1.25// 33
k
k
3Vk (n1.2//22))
y 3501
In
I 1/2,
2
0
2t
Vto
which implies S 2 and 8p. (N.. (e) & Sp, aa (E)) since the Poisson scheme's privacy profile
?
is monotonic in the sampling probability as proven in Lemma C.8
Remark D.4. While the asymptotic bound for the Poisson and random allocation schemes is identical up to the additional logarithmic dependence on i, only the third bound on a stated for random allocation is required for Poisson. Notice that vt > k the third term upper bounds the first one, and if additionally (n(1/))= < f the second term is bounded by the third one as well. While the first condition might hold when each element allocated to many steps, the latter does not hold only when < In (1/6) which is uncommon regime of parameters.
fs
E Missing proofs from Section 4.3
Lemma E.1. Given S k k W < and a randomizer dominated by a randomizer we (e). Furthermore, for any sequence of = 1, the privacy
have 8 ( (e) S (R)(( and (R) S (R)
integers ki S Kj <... < Ki S t, and non-negative A...... 2g s.t. A +1++.. +................. profile Ar, (It) is upper-bounded by the privacy profile of As, (R) + Ax (R), where we use convex combinations of algorithums to denote an algorithm that randomly chooses one of the algorithms with probability given in the coefficient.
Proof. To prove this claim, we recall the technique used in the proof of Lemma C.I We proved in Lemma C.4 that Ar, (R;; +) and Tr. (R:; +) are identically distributed. From the non-adaptivity assumption, this just sequence of repeated calls to the mixture algorithm A R(+) + (1 \o",e,)) R()).
Next we recall the fact proven in Lemma C.8 that the hockey-stick divergence between this mixture algorithm and R(L)) is monotonically increasing in X. Since Aui A. 2 Agi k.. for any k' >> k. this means the pair of distributions (N R(*) + (1
...) - H(_)) dominates the pair .. R L) R(L)) for any iteration and view v² (this domination holds in both directions). Using Claim C.9 this implies we can iteratively apply this for all step and get & (e) S (R), (e) for any >> O, thus completing the proof of the first part.
(Xpt,kk.. R(*) (1 >x..)
The proof of the second part is identical, since the posterior sampling probability induced by any mixture Ar, follows.
Ar, (R) is greater than the one induced by Ar, (R) the same reasoning
Lemma E.2. For any E j0, 1). element & E X, and randomizer R we have,
PLA (R; = Bc,(()) Ar, (R;z),
where B is the PDF of the binomial distribution with parameters t, X and Ard (R;x) = (L).
Proof. This results from the fact that flipping / coins with bias À can be modeled as first sampling an integer E {0, 1,....4) from a binomial distribution with parameters (1, A), then uniformly
sampling i,...., is [t], and setting the coins to 1 for those indexes.
24

---

The proof of the next claim is generalization of the advance joint convexity property Balle et al. 2018 Theorem 2].
Claim E.3. Given À E [0, 1]; K > 1 and two distribution P, F.Q over some domain, we have
H ((1 X]Q + XP QQ) = XH (P Q)
H (P || (1 A) + XQ) 3 H RM QP)
K S
K > T-X
1=1 X where K² == 1
R²
k-1 K and B == 1=1-=+M
Proof. The identity for H ((1 X)P + XQ || P) is a direct result of the advanced joint convexity property (Balle et al. 2018
Theorem 2]. For the second part notice that,
H (P 11 (1 - A)P + xQ) = / (P(w) ((1 - (11-))((w)) + (Q(w)) dw
/
[11 x +x))((W) XxQ(W)] du
Sn [P(w) x[]( du as --x
パ>
BH (P Q1)) KS 1
D-X
0
K> 1-X
Lemma E.4. For any E [0, 1]: > 0 and randomizer we have
He
(P; +)
(R; = = oz (PLA (R;+) || Pr. (R; 1)) (R:)();))) = = 3 (PL, (R; 1) PLA (R; (R;
He
(P;
where
P ( Σ Br,(k) Ar, (R;x)
kEI(]
is the Poisson scheme conditioned on allocating the element at least once, and 7, 5, E, and were defined in Theorem 4.3
Proof. First notice that,
PLA (R; (1)
Σ (k.)(k) Ae, (R;x)
k=
= (0) Ar.o (R:x) + Σ Bk,(kk) Ar.k (R;
kE[(]
( (1 21 Ac,0 +
BL. Ar, (R:z)
RE(:]
( (1 (1-1/7) 18 (L) -PA11//-P,,RR:: (R;
where (1) results from Lemma E.2 (2) from the definition of the binomial distribution, X' and P,,,, (R), and (3) from the definition of X' and the fact Arpo (R;x) (L)
Taking the converse of Claim
E.3 we have,
Her (P:t
P. (R: 1)) = HH (R:A(R: I (R;
Similarly, from the previous claim we get,
Her (Pt,(R; (T)((1;))) ) = 2 (Pr, (R;1) Pr, (R;))).
which completes the proof.
25

---

We can now prove the main theorem.
The proof of this theorem consists of several key steps. First, show (Lemmal E. that increasing the number of allocations can only harm the privacy, that is, for any sequence of integers & S 1 <... < k3 S f, and non-negative ..,..., A3 s.t. A1 +..... +y 1, the privacy profile of AI, (R) upper- bounde by the privacy profile of A1 (R)+.. AL. (R), where convex combinations of algorithms to denote algorithm that randomly chooses one of the algorithms with probability given in the coefficient.
Proof. [Proof of Theorem 4.3
Next, we notice (Lemma F.2) that the Poisson scheme can be decomposed into sequence of random allocation schemes, by first sampling the number of steps in which the element will participate from the Binomial distribution and then running the random allocation scheme for the corresponding number steps,
PA,x (R;x)
Σ (k)) Ar, (R;z),
where B is the PDF of the binomial distribution with parameters 1, and Ar,o (R; = (1)
We then define the Poisson scheme conditioned on allocating the element at least once
P (R; 7 (k) Ar, (R;x),
kE
and use generalized version of the advanced joint convexity (Claim E.3 that of the Poisson scheme (Lemma E.4 Formally,
to relate its privacy profile
3 (E)())()) = He (AL, (R:+) Ar, (R:
(1) He
7
(k)( - Ar,1 (R;*) || Ar, (R:1)
kE[t]
(2)
S He
7 Σ Bk)((k) (R;=) || Ar. L)
kE[t]
(3) H. (Pix(R;))
(P:)(R:1))
(1) T (Pr, (R;*) (R;
5. 8 (R)((
where (1) results from the fact Ete Bi, (k) 1/5, (2) from Lemma E.1 (3) from the definition
of P t. and the fact that Pr. (R; 1) R (1) Ar,x (Rt; L), and (4) from the first part of Lemma
E.4
Repeating the same proof using the second part of Lemma E.4 proves the bound on 3 (.)))-
Combining the Poisson decomposition perspective shown in Lemma E.2 with the monotonicity in number allocations shown Lemma E.I additionally implies the following corollary.
Corollary F.5. For any X E (0, 1); E [1], we have 8p (p)))((((E)) S (P.)(R(())) (E), where Pr, (R)
denotes the Poisson scheme where the number of allocations is upper bounded by k.
26

---

Proof Theorem 4.3
The proof directly results from combining the previous lemmas,
3 ()) = He (Ar, (R: Ar, (R;
L H
7
(k:) Ar,1 (R: || Ar, (R;
ke|t]
(2)
S e
7 Σ (k) Ar, (R;+) #) |l Ar, (R:
kEjt]
(3)
H (Pit)
|| (tt((::))
T cr (Pt,) (Ri*) (R:
ア. 8p (1)))))
where (I) results from the fact Eke(1] Bt,2 1/7, (2) from Lemma E.1 (3) from the definition
of Pitx L.x and the fact that Pi, (R: 1) Rot (1) Ar,x (R: 1), and (4) from the first part of Lemma
E.4
Repeating the same proof using the second part of Lemma E.4 proves the bound on δ (.(R))-
Proof. Notice that,
2 )p.)M(R((E)
(P)A)(M)(E)
He (PLAN (Ri+) || PLAN (R;
k-1
(2) He
Σ Bex(1)) (eAl() + Bis0))
Ae, (Ri+) || PLax (R2: (R::
i=
(3)
< Her Σ
Ac, (R;*) Prx (R:11)
8p, (R)
where (1) results from Lemma 3.1 (2) from Lemma from Lemma E.
E.2
and the definition of PL. (R), and (3)
F Missing proofs from Section 4.4
Lemma F.. Given t, E N and two distributions P. Q over some domain Q, we have
R2 (P
1 In ta
Σ
II PEn
(a- 1n-1)
C(IT)
TI
IEIl(())
where P: : (Q)()-1) P. Q0(t-i)), Q0(--1). P. Q denotes the distribution induced by sampling all elements from Q, except the ith one which is sampled from P.
We start by proving a supporting claim.
Claim F.2. Given ax L E N and a list of ininegeer .., 2 O such that in +., .. ... i,
a, denote by P(i ... ie) the integer partition of a associated with this list, e.g. i = 1,12 = 0, 2, is
then P 1, Given an integer partition P of a. we have Brl (c(i)) where,
Bp = (1.. .. 2 2 P(é 4 P).
and C(II) was defined in Theorem
4.4
27

---

Proof. Given partition P with unique counts CIII = (ci,..., Cg), and an assignments i1..... i such that .4 2 0 and P(ii,...,, i)) P. there are (4) ways to assign the first value to ei indexes of the possible i, (t ways to assign the second value to 02 indexes of of the remaining t C1 indexes, and so on. Multiplying these terms completes the proof.
Proof of Lemma F.I
Given a set of integers , 2 0 such that ii +... + it = a we have,
(((w it V~QBi
[ (P(w))
II kE[t]
II E
II PETT
E Y-Q
where P is the integer partition of defined by i1......y, e.g. if = 1n = 0, 13 = 2. 1, then P P= [1, This is a result of the fact Y32 are all identically distributed. Notice that the same partition
corresponds to many assignments, e.g. P= [1, 1.2] corresponds to 1 0, i2 1, 1, 21 2 as well. The number of assignments that correspond to a partition (c(m) Using this fact we get,
Eieto (Q0(i-1), P- P-Q2((-))
(0))))))))) a
cla-1)RaP1(99) (1)
E V~Qa1
Q
1
P(wi)
E VNQui
i
(wii)
sE|d]
(2)
E
Σ
a
II kE
P(ws)
to VnQutt
i1
((wi)
Elai: +42.0
(3)
Σ
a
E II kE(t]
P(wx)
to
V~QQI
Q(wi)
20:
(4)
a
II
E
P(w) P Q(w)
10
(1
20:
pEII(ii....ttt)
(((lL)
(5)
Σ
a II
II PETT W~Q
to
C(II)
(oT
1
Σ
a
1),,
C(TT)
πT
(o)
PENI
where (1) results from the definition of P, (2) is the multinomial theorem, (3) results from the fact wi and Wj are independent for any i A j. (4) from the fact W/ are all identically and independently distributed with P(i,...., defined in Claim F22 and (5) results from Claim F2
Lemma F33. Given X E [o, 1] and two distributions P.Q over some domain Ω denote PA = P*Qi-A
Zx
where Zn is the normalizing factor.
Given L N. for any E R we have H (Q01 1| < (Q
pPtt). where P
Eieto (Q8(i-1). P. Q0(t-i)), Q0(i-1) P. Q'- denotes the distribution induced by sampling all elements from Q, except for the ith one which is sampled from P.
Proof. By definition,
l (w; PA, Q) = In (Palw) In (P((WQ)-)())
Aln P(W)) -In(ZA) = (.)
Q(w))
Q(w)Za
((w)
28

---

Given & E R denote e' - t. In(2 (111))
/
He (Q
|| P)
[Q0*(0) P(o)( dv
Q (v)
c i Σ
(Qu(i-1). P. Qu(0 (w)
do
121
KE|U
/
Q
Q8( (0)
(.))
dv
t sE|(]
Q
R0 (v)
E+ Eicto (.w:P.
dv
2
(2)
Q (b)
e' Eito (wirPa)))))
dv
Pise(we)
(0)
- c='
II
dv
Q(ws)
KE[
(Q8(()) (v) - -e- P1p/
(w)
do
(Q00 p
H
where (1) results from Jensen's 's inequality and (2) from the definition of Piçe and the previous claim.
Proof of Conollary 4.6 From the definition of the Rényi divergence for the Gaussian mechanism,
R2 (Ar (No: 1) A (No; 0)) R. (Ae (No; 1) N (0)) (0))
In 1
a
II pell
(N,
(C()))
TT
(OT
ln
II
p(p-1) 202
a
C(II)
II
[IEll.(a)
1
In
e
20
Σ
a π7
Epen
20
tor
C(TT)
(all
a
(
+ In (t)
In
Σ ILElI
(
Epen 2
-
202
C(II)
11
For the add direction we notice that from the definition, for any ER
PH (x|1))
1
(s=1)²
=1-
[-- 2 X0-
20
26
20
202
2TT
2nT
21
so R*(+) = WA,, 0²) and Z^ = e 20
Setting À 1/1 we get,
(1)
3 (.(())
S H ne' (0, (1
H (N || (
H (N(0,to?) ((1,to))),
29

---

where (1) results from Theorem 4.5
(2) from the fact that the hockey-stick divergence between two Gaussians with the same scale depends only on the ratio of the difference between their means and their scale, and (3) from the fact that the I-composition hockey-stick divergence between two Gaussians with the same scale amounts to dividing their scale by Vt.
We remark that the expression in Corollary 4.6 for the remove direction previously computed in Liew and Takahashi (2022), up to the improvement of using integer partitions. In this (unpublished) work the authors give an incorrect proof that datasets (0,... O. 1) and (0....,0) 0) pair of datasets for the shuffle scheme applied to Gaussian mechanism. Their analysis of the RDP bound for this pair of distributions is correct (even if significantly longer) and the final expression is identical to ours.
a dominating
Figure 5 provides a clear example of the advantage of direct analysis, in regimes where the privacy guarantees of the random allocation scheme are better than those of the Poisson scheme. Even though RDP-based bounds methods that rely on reduction to Poisson. On the other hand, figure iidicates that the gap between RDP- RDP-based bound and Poisson's 's PLD-based one in other regimes, is mainly due to the fact it relies on RDP, and not a property of random allocation. additionally reflects the fact that the gap between PLD and RDP based analysis vanishes the number of epochs grows.
Poisson not as tight, the RDP-based of allocation is superior to other
Poisson (RDP)
Ey Poisson (PLD)
E Allocation (Our Direct)
E4 Allocation (Our Decompasition)
25
20
25
75
125
175
225
275
325
375
425
475
525
t
Figure 5: Upper bounds privacy function of the number of steps for the Poisson and random allocation schemes, for fixed parameters 0.3, 10-4
F11 Implementation details
Computation time of the naive implementation of our RDP calculation ranges between second and minutes on a typical personal computer, depending on the a value and other parameters, but can be improved by several orders of magniude using several programming and analytic steps which briefly discuss here.
On the programming side, we used vectorization and hashing to reduce runtime. To avoid overflow we computed most quantities in log form, and used and the LSE trick. While significantly reducing the runtime, programming improvements cannot escape the inevitable exponential (in a:) nature of this method. Luckily, in most settings, a the a value which induces the tightest bound on is typically in the low 10s. Unfortunately, finding a" requires computing R,, so reducing the range of values for which R, is crucial.
We do so by proving upper bound on a" in terms of known bound on
30

---

Ep (PLD)
Ep Polsson (RDP)
Ex Allocation (Our Direct)
2.0
8
10
1000
Figure 6: Upper bounds on privacy parameter for various schemes using Gaussian mechanism, as a function of the number of "epochs" times the scheme was sequentially computed, for fixed parameters
1, 8 = 1008, 10a.
Claim F.4. Given (0,) 1) and two distributions P, Q and, denote by E(6) inf (8(x) < 8). 2>0
Given e > 0, if( S & and R., (PIIQ) > e, then o² < a.
direct implication of this Lemma is that searching on monotonically increasing values of a and using the best bound on achieved at any point to check the relevancy of a, we don't ton't have to compute many values of a greater than a* before we stop.
Proof. Denote by (a) the bound on achieved using R,, (PIIQ). From Lemma A.I (6(a) R. (PII)) + σ(a) for non negative ø (except for the range >> 1/(20) which provides vacuous bound). Since R. (Pl monotonically non-decreasing
we have for any a' 2 a,
78(a') R& (PI[Q) 2 Rs (PIQ)) 2 2,
so it cannot provide better bound
G Comparison to other techniques
For completeness, state how can directly estimate the hockey-stick divergence of the en- tire random allocation scheme, This technique was first presented in the context of the Gaussian mechanism by Chua et al. 2024a].
We first provide an exact expression for the privacy profile of the random allocation scheme. Lemma G.I. For any randomizer R and >> O have,
(A((R)(E)=
E
V~
KE[d]
Given 0, No is Gaussian mechanism with noise scale have,
22: 20
{A.NN)(()=
E
2~~(0,011)
iE
31

---

We note that to simple algebraic manipulations, this hockey-stick divergence is essentially the expectation the right tail the sum of independent log-normal random variables, which can be approximated as single log-normal random variable (Neelesh B. et al. 2007]. but this approximation typically provide useful guarantees only for large number of steps.
Proof. Denote by 7 the index of the selected allocation. Notice that for any E [d] we have,
(A((R:)(((I =1) [ - PRo (05))
PAL(R PR())(Us) PR(1) (3))
Pr(.) (96)
II PR(P) (R(1)(0)))
= PA((++(()) Σ (o] = = - (A((B_)()) Σ
PR(.)(y))
PR(1)(M))
iE(1)
ic(1]
Using this identity get.
(1 ' (R())(Ui) (oe1)(9)))) = In ( cla(r)s.)) iE|(
(A((R) (03*, 1) 1)) (P.(Bm)(()) (A() = =ln
PRO
iE/t
Plugging this into the definition the hockey-stick divergence completes the proof of the first part.
The second part is direct result of the dominating pair for the random allocation scheme of the Gaussian mechanism (Claim D.3
G.1 Monte Carlo simulation Chua et al. [2024a]
Using Monte Carlo simulation to estimate this quantity, is typically done using the E
[(w.P..) representation of the hockey-stick divergence, so that numerical sta- bility can be achieved by bounding the estimates quantity E [0, 1].
wnP
naive estimation will require an impractical number of experiments, especially in the low d and high confidence level regimes. These challenges can be partially mitigated using importance sampling and order statisties, a new technique recently presented by Chua al. [2024a]] Still, this technique suffers from several limitations. It can only account for the setting of l = I and does not provide a full PLD, and so cannot be composed. can only estimate 8, so plotting e as function some other parameter is computationally prohibitive. Figure illustrates simultaneously the tightness of our bounds, which are within constant from the lower bound in the delta regime, and the limitations regime for the chosen parameters.
of the MC methods which become loose in the d < 10
32

---

t 100, 0.75
100,
10a
10a
10
10-2
6 10
10"
1017
10-1
10
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
t= 10,000, d= 0.75
[= 10,000, d' = 0.5
10-1
10-5
10
10
10
1.5
3.0
1.5
2.5
4.0
Polsson
Allocation (CGHKKLMSZ24
Allocation (Our Combined)
Allocation (CGHKKLM5224 Monte Carto mean)
Figure 7: Comparison of ó bound for Poisson scheme with various bounds for the random allocation scheme, for several and values; our combined methods, the high probability and the average estimations of using Monte Carlo simulation with order statisties, 5- 10s samples and 99% confidence level, by Chua [2024a]
We additionally repeat the analysis using the experimental setting presented in Chua et al. 2024a Figure 2]. both in the form of Figure and Figure 7 The choice of depends on the experimental settings, the dataset (Criteo pCTR Criteo search conversion logs) and the batch size.
PCTR 1024: 35,938
SCL 1024: C 12,500
199
10
10
pCTR 8192: t 4,492
SCL -1192 1.563
19.
10'
100
101
62 Local
Allocation tOur Direct)
6, Allocation (Our Decomposition)
Polsson (PLD)
4A Allocation (Our Recursive)
6 Allocation (CGHIRLMSZ22 Lower Bound!
Figure 8: Upper bounds on privacy parameter as function the noise parameter a various schemes and the local algorithm (no amplification), all using the Gaussian mechanism, with privacy parameters = 10" and various values of i, following the experimental parameters following the experimental settings Chua et al. 2024al Figure 2). In the Poisson scheme À 1/t.
33

---

35,938, 0.3
4,492, 0.4
10"1
10-2
10"4
10-1
10-1
10"
10
10-9
10"5
10-9
10
10
I= 12,500, a= 0.3
1= 1,563, 0 0.4
10
10
10"4
10-1
10-1
10-3
10"
10'1
10-4
10-2
10-1
Polsson
(CGHKKLMSZ24
Allocation (Our Combined)
Allocation (CGHKKLM5224 Monte Carto mean)
Figure 9: Comparison of ó bound for Poisson scheme with various bounds for the random allocation scheme, for several a and values; our combined methods, the high probability and the average estimations of using Monte Carlo simulation with order statistics, 10 samples and 99% confidence level, following experimental settings of Chua et al. 2024a Figure 2].
G.2 RDP-based bound by Dong et al. 2025
recent independent work by Dong et al. [2055] considered the same setting under the name Balanced Iteration Subsampling. In Theorem 3.1 they provide two RDP bounds for the remove Theorem 4.4 our work. Since the bound for
direction and one for add, that are comparable the remove direction always dominated the add direction, we focus it. The first one is tight but computationally expensive even for the case of case of & their expression matches the one proposed by Liew and Takahashi [202] which is mathematically identical to our, but requires O(t") summands rather than our ( ones.). The second bound they propose requires summing only over linear (in k) number of terms which significantly more efficient than our term, but lossy. This gap is more pronounced in some parameter regimes, mainly when the used for inducing the best bound hand, this method allows for direct analysis of the & > 1 case, while our analysis relies on the reduction to composition of k runs of the random allocation process with selection of 1 out of t/k steps.
as sums over O terms (in the
is large. On the other
Figure 10 depicts the spectrum of these effects. For small values of k our RDP based bounds are tighter than loose bound proposed by Dong et al. 2025), while for the large values of when quite large our composition based analysis is looser.
34

---

Gy Poisson (RDP)
Allocation (Our Direct)
Allocation (DC025 RDP)
Figure 10: Upper bounds privacy parameter function of the the number of allocations k: for the Poisson and random allocation schemes, all using the Gaussian mechanism with fixed parameters 10 -2
The y-axis uses logarithmic scale to emphasize the relative performance.
H Privacy-utility tradeoff
The results of Chua et al. (024a] show that in the context of training DP-SGD, random allocation (or balls-and- and-aadddnn bins sampling) has the utility benefits of shuffling while having the privacy benefits of Poisson subsampling. Here we investigate the privacy-utility trade-off in simple-to-analye setting of mean estimation over a Boolean hypercube, that illustrates one possible source of this relative advantage.
We start with the one-dimensional setting. Consider a dataset s {0, 1)"h sampled iid from a Bemouuli distribution with expectation [0, 1]. where p is estimated from the data elements using one of the two schemes. Formally, at each iteration, the algorithm reports a noisy sum the elements in the corresponding subset y/, and the estimated expectation is = Ese{q Vr.
Since ý is averaged over the various steps, in the case of random allocation with the Gaussian mechanism we have -A= = (Erea' x + Eiejaj &: where & is the noise added at step i. From the property of the Gaussian mechanism Eiere & Gaussian random variable with variance la?, and from the definition of the distribution, Eves Bin(n, p). p 1 (Bin(n, NO0 to²)). In particular this implies E]pA] p and Var(δA) p(1-p) + noise and the second is the privacy noise.
n. 2o? nE. where the first term is the sampling
Poisson subsampling adds some complexity to the analysis, but can be well approximated for large sample size. The estimation Pop follows similar distribution to that of P.A. with an additional step. First we sample u ~ Bin Bin(n.p). then following the insight introduced in Lemma E.2 we sample Bin(u 1, 1/2). We note that (1 11--1 +) u. Since w.h.p. x p- n, get E[lrr] p and T.. where the first term is the sampling noise, the second is the Poisson
ia (in 1/t) for all E [u]. which amounts to sampling E|m] and Var(m) Var(pA) ~ p(1-p) + to sampling noise, and the third the privacy noise.
The noise scale required to guarantee some fixed privacy parameters using the random allocation scheme is typically larger than the one required by the Poisson scheme, as shown Figures T But following the asymptotic analysis discussed in Section 4.2 we have to² x In(1/5] for both schemes. with constants differing by 10% in most practical parameter regimes, shown in Figures and 2
which implies the privacy noise to² is typically slightly larger for the random allocation scheme. On
". the other hand, for 1, the Poisson sampling noise is arbitrarily larger than the sampling noise. Since the privacy bound becomes negligible as n increases, we get that random allocation scheme asymptotically (in n) dominates the Poisson scheme, illustrated in Figure II In the 1,
35

---

case, the induced a is sufficiently small, so the gap is dominated by the additional Poisson sampling noise, when 0.1, this effect becomes dominate only for relatively large sample size.
In the high-dimensional setting the privacy noise dominates the sampling noise and therefore the privacy-utility tradeoff is dominated by the difference in the (known) privacy guarantees of the two schemes. In Figure we give an example of this phenomenon for d = 1000.
1.0,
0.1,
0.1, d 1,000
10-4
10-4
10
Square Emror
10t
10-3
10
10"
10
2011
10
10
10"4
10
Lasker dx1.11
10'
10
10
10
30t
30
Sample Size
Sample Size
Sample Size
Poisson
Poisson confidence interval
Poisson (analytic)
Rendom allocetion
Random allocation 3o confidence interval
Random alloce tion (enalytic))
Figure 11: Analytical empirical square error for the Poisson random allocation scheme for the setting discussed in Appendix HI for various values of e and (which corresponds to an increase in sensitivity). We set = 0.9, & = 10a, 10 The experiment was carried 10* times, so the 3-std confidence intervals are barely visible.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims mathematically proven.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss both tightness the results and computation limitations when applied.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
[Yes]
37

---

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

---

Answer: [Yes]
Justification:
The code is provided as supplementary material. No data is involved.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ Sawaaee/dooSSSSeeSeeeeeee
stipaiisssoooooocyyy. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper only contains numerical analysis without any usage of data. All relevant details were provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper mostly contains numerical analysis without any usage sampling. when MC based methods are considered, CI are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
39

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
The paper only contains numerical analysis, the longest of which runs for several minutes on a personal computer.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification: This is purely theoretical work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due laws or regulations in their jurisdiction).
40

---

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

---

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

---

Justification:
No such thing was done in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs only assisted with some of the technical coding tasks.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy http://ae/euuessscc///ooeeeeeeee for what should or should not be described.
43


Reviews:
[{"review_id": "Au9LrlGBEP", "reviewer": "Reviewer_tRz2", "summary": "This paper analyzes the \"random k-out-of-t allocation\" sampling scheme for amplification differentially private guarantees. The authors introduce three novel techniques that provide the first efficiently-computable and nearly-tight theoretical privacy guarantees, showing the scheme's privacy is asymptotically equivalent to the well-studied Poisson subsampling method. Numerical results confirm these new bounds are very close to those for Poisson subsampling, meaning random allocation can be used to improve utility with only a minor loss in privacy, helping to bridge the gap between the theory and practice of algorithms like DP-SGD.", "questions": "1. Can you provide a more concrete threshold or rule of thumb for practitioners to determine when this bound is no longer reliable and they should switch to one of your other analysis techniques, like the Poisson Decomposition or Direct RDP method?\n\n2. In your analysis of the direct RDP bound, the reduction from a general k > 1 to k = 1 is described as \"potentially loose\". Could you provide a heavier discussion on this? For example, can you characterize the factors that influence the magnitude of this looseness or how it compares to other sources of imprecision, such as the RDP-to-DP conversion?\n\n3. Regarding the computational complexity of the direct RDP analysis: what is the practical upper limit on the privacy guarantee that can be reliably calculated with this method?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n+ The paper tackles a crucial issue in DP, the \"random allocation\" scheme is more practical and utility-friendly than the commonly analyzed Poisson subsampling, but its privacy guarantees were not well understood. This work directly addresses the discrepancy between practical implementations of DP-SGD and their theoretical privacy analyses.\n+ Problem of better utility-privacy tradeoff is very well motivated and of relevance to the broader ML/AI community.\n+ Solid theoretical paper. \n\nWeakness:\n- While the paper provides some numerical evaluations, more extensive experiments across a wider range of parameters and tasks would strengthen the claims. \n- Furthermore, while the authors do acknowledge some limitations, a heavier and more detailed discussion of their practical implications would be beneficial. For instance, the authors state that their main asymptotic bound may produce \"suboptimal bounds\" and that the conversion from RDP is \"somewhat lossy\". A more thorough exploration of how suboptimal or lossy these can be, perhaps with targeted experiments, would make the work more complete and provide clearer guidance for practitioners.", "was_revised": true, "final_justification": "Overall, I found this paper interesting and worthy of acceptance. I am satisfied with the response provided by the authors and will maintain my positive score.", "rebuttal": "We thank the reviewer for the detailed feedback and questions. Due to page limitation some of the extended experiments (e.g. Figures 4, 5, and 6) and discussion appear only in the appendix. We intend to use the additional space to clarify the points raised by the reviewer, and extend the discussion in the appendix.\n\n**Replies to the reviewers questions:**\n1. **Threshold between methods:** First, we note that practitioners don't need to determine a-priori which method provides the tightest bound, and instead can simply use the best one per configuration (the bold blue line in Figure 1 and the combined line in Figure 2). As a rule of thumb, the recursive bound is tighter than the others when $k/t \\ll 1$ and the local privacy parameter $\\varepsilon_{0}$ is not too large. We intend to add a detailed discussion of these effects to the final version.\n2. **Looseness of conversion from $k>1$ to $k=1$:** Unfortunately, we don’t have a tight measure of these effects, but can provide some approximations. The looseness stems from the reduced entropy resulting from the public splitting of the t rounds to k subsets, and to a lesser extent from the rounding of $t/k$, which increases as $k/t \\rightarrow 1$. The comparison in Figure 8 to the DCO method which does not use this reduction, seems to indicate the effect is relatively minor, but a formal analysis will require a lower bound for $k>1$ which we currently lack.\n3. **Computational complexity:** We note that while the computational complexity scales with $\\alpha$ this does not directly imply a bound on $\\epsilon$, since the conversion depends on other parameters such as the number of epochs and $\\delta$. On the practical level, increased runtime was experienced around $\\alpha=60$, which typically corresponds to low $\\epsilon$ where other bounds usually provide tighter guarantees. A more detailed discussion of this effect can be found in Section F.1."}, {"review_id": "vKn0BbN4we", "reviewer": "Reviewer_qC1J", "summary": "Privacy amplification by subsampling is one of the most central tools for boosting privacy. \nIn DP-SGD, for example, a privacy boost is achieved because only a small batch is used in each step. The question that this paper studies is how to choose the batches, because there are privacy-utility tradeoffs for different sampling procedures. One option is to use Poission subsampling (parametrized by $\\lambda$), where for each batch of the execution, each data element is chosen to be in the batch w.p. $\\lambda$ (independently from the other batches and the other data elements). The advantage of this technique is that it allows good privacy upper bounds due to full independence, but the downside is that it is not very practical, both in terms of implementation constraints and in terms of accuracy. So, in practice, it is common to choose the batches using some type of shuffling, but the problem is that shuffling induces dependencies between the elements and the batches, which makes it harder to analyze, resulting in worse upper bounds compared to the Poisson subsampling.\n\nIn this paper, the authors analyze a sampling technique called “random allocation” (parametrized by $k$), where each data element appears in exactly $k$ batches (chosen randomly out of the total $t$ batches). This technique induces partial independence (because the locations of the data elements are independent of each other), so it can be seen as a compromise strategy between Poisson sampling and shuffling. From the utility perspective, the authors mention in lines 67-71 the work of Chua et al. [2024a], which shows that in the context of training neural networks via DP-SGD, random allocation with $k=1$ has good utility as shuffling, which is noticeably better than Poisson sampling.\n\nThe main result of this work is to prove that, in terms of privacy, random allocation is upper-bounded by Poisson sampling upper bounds (up to low-order terms), so the message of this paper is that this sampling essentially enjoys the utility benefits of shuffling while also enjoying the privacy benefits of Poisson sampling.\n\nSimilarly to prior works, this paper analyzes the privacy of random allocation using a dominating pair induced by a randomizer and compares the privacy of random allocation with that of Poission when the mechanism is the simple (non-adaptive) randomizer.\nThey also provide general direct upper bounds (i.e., without using Poisson as a baseline), specific upper bounds for the Gaussian mechanism (used in DP-SGD), and present empirical evaluations which show that their upper bounds are better than the ones of the recent work by [Dong et al., 2025].", "questions": "(1) First, it is not clear to me what exactly “shuffling” is in the context of this paper. The authors first mention it in the context of federated data analysis, where, according to my understanding, given n data elements, we have n batches that are shuffled, and each element appears in exactly one of them. But the context of this paper is not about the federated setting, but about amplifying $t$ adaptive steps of a (centralized) algorithm (e.g., DP-SGD) that gets batches with possibly more than 1 element. So, how are the batches exactly defined in shuffling? Do we shuffle all the data elements and then use the first $t \\cdot s$ elements (where $t$ denotes the number of batches, and $s$ denotes the batch size)? Do you assume that $t\\cdot s = n$ (where $n$ is the total number of elements) or that $t \\cdot s \\ll n$?\nPlease also explain the Shuffling setting in the context of Figure 1, and why there are unsmooth jumps in the large sigma values.\n\n(2) Another natural amplification technique that we can think of is to sample a random fixed-size subset from the data elements in each step. This technique also has partial independence because the batches are independent of each other, but I haven’t seen any reference for that. What do we know about this technique compared to random allocation?\n\n\n(3) In lines 201-203, given a mechanism $M$ that expects to get multiple elements as input, you define $P_{t,\\lambda}(M)$ (Poisson) and $A_{t,k}(M)$ (Random allocation). In lines 250-252, you say that these definitions naturally extend to the case that $M$ is a randomizer $R$. But a randomizer doesn’t get multiple elements as input, only a single element or empty set, so I’m not sure I understand what do you mean by  $P_{t,\\lambda}(R), A_{t,\\lambda}(R) \\colon \\\\{\\ast,\\bot\\\\}^\\ast \\rightarrow Y^t$. I interpret $P_{t,\\lambda}(R)$ and $A_{t,\\lambda}(R)$  as the mechanisms that get a single element $\\ast$, choose the locations of that element out of the $t$ (using Poisson or random allocation), and in all places where the elements appear you execute $R(\\ast)$ and in all places where it doesn’t appear then your execute $R(\\bot)$. But I’m not sure that my interpretation is correct (because you define them as mechanisms that get inputs from $\\\\{\\ast,\\bot\\\\}^*$), and this is a very crucial point that has to be clearer because all your theorems use these notations. \n\nMinor comments, questions, and typos:\n\nFigure 1: In the description of the y-axis, what is $\\omega$? Should it be $\\varepsilon$?\n\nLines 170-172: “It was recently shown that ..” Can you elaborate on these works? How do they measure “true privacy”? Do they use (perhaps loose) upper bounds for shuffling, or do they use other (tighter) privacy accounting techniques? I’m trying to understand if the privacy gap from Shuffling to Poisson is just between the known upper bounds (and perhaps just because we don’t have the tools for tighter analysis) or if there is an inherent privacy gap in some cases. (This point is not clear to me).\n\nRandom allocation: When you sample $(i_1,\\ldots,i_t) \\subset [t]$, is it with replacement or without? (i.e., could $i_1$ and $i_2$ be equal?).\n\nLine 255: “number of allocation” -> allocations.\n\nLine 260: “from the fact random…” -> from the fact that random… \n\nLine 277: $\\mathcal{A}(R;\\ast) = R^{\\otimes t}(\\ast)$.\n\nTheorem 4.1: $\\eta$ is undefined for $\\gamma = 1$.\n\nLines 293-295: Should we think about $\\varepsilon’$ as $\\gg 1$? Also, I don’t understand the $O(\\varepsilon^2)$ estimation.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "I think that at a high level, the problem that this paper studies is important, and the contribution is significant. The results also seem to be technically challenging, and indeed, from a brief look at the full version in the supplementary material, the proofs are definitely not straightforward.\n\nI think that the main weakness of this paper is its clarity. Because of missing or unclear definitions, I feel that I don’t fully understand all the models, statements, and implications (see my questions below). \n\nOverall, I think that this paper should be above the acceptance bar of NeurIPS, but because I don’t feel I understand large parts of the details due to clarity issues, I gave it a borderline acceptance score.", "was_revised": true, "final_justification": "My main concerns about this paper were clarity issues in several places. The authors have answered my questions and will address them in the next version, so I'm increasing my score from 4 to 5.", "rebuttal": "We thank the reviewer for the comments and questions. We acknowledge that the submitted version of the work is not sufficiently clear in places, partially due to cuts we made to ensure the page limit. We have edited the body of the paper to clarify some of the missing parts and extended the discussion in the appendixes, and will further incorporate the useful comments we have received into the final version.\n\n**Replies to the reviewers questions:**\n1. **Comparison to shuffling:** By shuffling scheme we refer to a data sampling method in which the data is first shuffled then used to run an algorithm, for example as is the common practice in SGD. In this model, the number of steps ($t$) is equal to the number of elements ($n$), the elements are randomly permuted prior to the training run, and at each step i the response is produced by a local mechanism receiving  data element of (permuted) order i (in addition to previous responses). This model was first proposed in [1] who showed that privacy amplification bounds for this model also imply the privacy amplification for shuffling the responses of identical local randomizers as done in federated learning. We omitted this explanation due to page limitations and intend to include it in the final version.\n2. **Phase transition in shuffling:** The privacy guarantee of shuffling is indeed not smooth, and has a sharp transition in the regime where the local privacy $\\varepsilon_{0}$ is $\\approx 1$, resulting from the fact the total privacy $\\varepsilon$ scales with $(1-e^{\\varepsilon_{0}})e^{\\varepsilon_{0}/2}$ [2]. A similar effect is responsible for the (less) sharp transition of Poisson (and consequently - random allocation) in the $\\sigma \\in [0.4,0.8]$ regime in the same figure.\n3. **Sampling without replacement:** Using a fixed subset size per step is commonly referred to as \"sampling without replacement\", and provides privacy guarantees that closely resemble those of Poisson subsampling [3]. This method can be viewed as the counterpart of random allocation, having the advantage of constant size batches with the disadvantage of varying number of steps in which each user participated. It was briefly mentioned in the introduction, and we intend to elaborate on it in the final version.\n4. **Extension of schemes to a randomizer:** The reviewer is correct, this was indeed a typo. The extension to randomizer holds for input datasets of size $1$, that is, $P_{t, \\lambda}(M), A_{t,k}(M) : \\\\{*, \\bot\\\\} \\rightarrow Y^{t}$. This is the only type of input we need to consider, following the reduction stated in Lemma 3.1.\n\n**Minor comments:**\n1. **Y axis in Figure 1:** The $\\omega$ is simply an $\\varepsilon$ printed in a vertical direction, which we realize might be confusing\n2. **Lower bounds on shuffle:** For example, [4, Figure 1] provided an empirical lower bound on $\\varepsilon$ for shuffling which is significantly higher than the upper bound on the one for Poisson in some parameters regime. By definition, such a gap cannot be remedied via a tighter upper bound.\n3. **Sampling method in random allocation:** The steps are sampled without replacement, so that an element can participate in each step only once.\n4. **Line 277:** While $\\mathcal{A}(R,\\bot) = R^{\\otimes t}(\\bot)$ the same does not hold for $*$. We are not sure we understood the comment.\n5. **Interpretation of $\\varepsilon’$:** $\\varepsilon'$ should be thought of as smaller than 1 but greater than $\\varepsilon$ (e.g. $0.1 \\varepsilon$). In this setting, the privacy profile for $\\varepsilon'$ is negligible and we have $\\eta \\approx (1+2\\varepsilon')/t$. Since the privacy parameter of the Poisson scheme grows $\\approx$ linearly in $\\eta$ for fixed $\\delta$, number of steps, and mechanism parameters (e.g. $\\sigma$), the privacy parameter of the random allocation scheme $\\varepsilon_{A} = O(\\varepsilon_{P} \\cdot \\eta t) = O(\\varepsilon_{P}(1+\\varepsilon') = O(\\varepsilon_{P} + \\varepsilon_{P}^{2})$, where $\\varepsilon_{P}$ is the privacy of the Poisson scheme with $\\eta = 1/t$. \n\n[1] Erlingsson, Úlfar, et al. \"Amplification by shuffling: From local to central differential privacy via anonymity.\" Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019.\n\n[2] Feldman, Vitaly, Audra McMillan, and Kunal Talwar. \"Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling.\" 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022.\n\n[3] Balle, Borja, Gilles Barthe, and Marco Gaboardi. \"Privacy amplification by subsampling: Tight analyses via couplings and divergences.\" Advances in neural information processing systems 31 (2018).\n\n[4] Chua, Lynn, et al. \"How Private are DP-SGD Implementations?.\" International Conference on Machine Learning. PMLR, 2024."}, {"review_id": "LW1ARWYgUW", "reviewer": "Reviewer_L8bh", "summary": "The authors investigate a specific sampling scheme for privacy amplification where each user’s data is involved in k randomly chosen steps out of t total steps. They present the first theoretical guarantees and numerical estimation methods for this scheme. They show that privacy amplification under this scheme can be upper-bounded by Poisson subsampling with a sampling rate of approximately k/t. The paper also introduces two alternative analyses for tighter bounds and demonstrates their effectiveness, particularly with Gaussian mechanisms.", "questions": "- What are the specific experimental setups used to generate the figures?\n- How do the bounds scale in practical deep learning settings compared to existing methods like Poisson subsampling? \n-  Please add a conclusion section and elaborate on the takeaways, future work, and potential limitations?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n+ The theoretical analysis seems technically correct and sound. In terms of novelty, it is the first comprehensive theoretical analysis of the k-out-of-t random allocation scheme. \n+ The proposed bounds are both efficiently computable and nearly tight, which matches the existing results in the literature. \n+ The results address a key gap between theoretical analyses and practical implementations of differentially private SGD, confirming the benefits of random allocation over Poisoning subsampling.\n\nWeaknesses\n\n- More detailed experimental validation and corresponding discussion are encouraged. While the paper provides extensive numerical analysis, it lacks clarity on the specific settings under which the figures were generated. For example, Chua et al. [2024a] evaluated the same sampling scheme in the context of DP-SGD training on real-world datasets. In contrast, this paper does not specify critical experimental parameters or setups. Without this information, it's difficult to assess how well the presented results align with practical privacy analyses. \n\n- The paper is felt incomplete in its current form. Notably, it lacks a conclusion section, which is critical for summarizing the key insights, contextualizing the contributions, and highlighting future directions. There is limited discussion of potential limitations or negative results. Section 5 does not provide enough results to reach the conclusions. \n\n- The presentation needs to be further improved. There are multiple grammar and formatting issues throughout the manuscript: improper article usage (e.g., \"a algorithm\" instead of \"an algorithm\"), awkward phrases (e.g., \"that it\" instead of \"that is\"), and inconsistent spacing around citations and symbols. Definitions 2.2–2.6 include extra spaces before citation parentheses, which should be removed. These seemingly minor errors accumulate and reduce the readability of the paper, and should be carefully addressed in revision.\n\nChua et al. \"Balls-and-Bins Sampling for DP-SGD.\" International Conference on Artificial Intelligence and Statistics,2024.", "was_revised": true, "final_justification": "After checking the rebuttal and the other reviews (together with their rebuttal and responses), I am convinced that this paper makes a significant contribution in the privacy study. I raise my score to 5.", "rebuttal": "We thank the reviewer for the detailed feedback. We intend to polish the presentation before the final version, as it is currently missing some details and includes some typos, and use the additional page to provide a comprehensive discussion.\n\n**Replies to the reviewers questions:**\n1. **Experimental setup:** All figures presented in this work except for 9 consider only the privacy of a sequence of noise applications, and as such - do not depend on the actual algorithm. They are purely numerical evaluations of the upper and lower bounds on the privacy parameters of the various sampling schemes, all using a local Gaussian mechanism. Figure 9 presents the privacy-utility tradeoff for a simple toy example detailed in Section F.\n2. **Practical deep learning setting:** The range of parameters analyzed in the various figures apply to many real world deep learning settings ($t \\in [10^{2}, 10^{6}]$, $\\sigma \\in [0.2, 2]$, and $k \\in [1/t,50/t]$). The experiments conducted in [1] considered two datasets with two expected batch size each, which corresponds to $t \\in [1.5 \\cdot 10^{3}, 3.6 \\cdot 10^{4}]$ and $\\sigma \\in [10^{-5}, 0.5]$, which partially match our numerical analysis. From our quick evaluation our bounds behave similarly in this regime (closely matching the Poisson bounds) and we intend to add a specific analysis for these regimes in the final version.\n3. **Discussion:** Parts of discussion are currently in the evaluation section. We thank the reviewer for the suggestion to expand those to a separate section which we will do in the final version.\n\n[1] Chua, Lynn, et al. \"Balls-and-Bins Sampling for DP-SGD.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2025."}, {"review_id": "uqmby37wmB", "reviewer": "Reviewer_YFTh", "summary": "This paper addresses the theoretical gap between Poisson subsampling--commonly assumed in the analysis of DP-SGD--and the more practical random shuffling approach used in real-world implementations. Unlike Poisson subsampling, which ensures independence across minibatches, shuffling introduces dependencies that complicate theoretical guarantees. While prior work has largely focused on pure differential privacy (i.e., $\\delta = 0$), this work extends the analysis to approximate differential privacy.\n\nTo this end, the authors propose three key contributions:\n1. They show that random allocation achieves nearly the same privacy guarantees as Poisson sampling with rate $k/t$, up to negligible lower-order terms.\n2. They provide a non-asymptotic privacy bound, showing that the privacy loss of random allocation remains within a constant factor of Poisson sampling across various regimes.\n3. By using RDP, they offer tight, computable bounds that are particularly effective in low-privacy regimes.\n\nThe theoretical contributions are supported by numerical evaluations, demonstrating that the privacy bounds under random allocation are very close to those under Poisson sampling. Moreover, the authors argue that random allocation often provides better utility, avoiding the inefficiencies and increased variance associated with Poisson sampling.\n\nThis paper offers **an important step toward reconciling theoretical privacy analyses with the practical implementation of DP-SGD. It is a strong contribution both in terms of theoretical depth and empirical completeness**. That said, the paper would benefit from further discussions on real-world scalability and broader applicability.", "questions": "1. As mentioned in the introduction, random allocation computes exact means (or sums), thus avoiding the extra variance introduced by Poisson sampling. Can the utility-privacy tradeoff observed in Figure 9 be replicated on more realistic datasets or tasks? I suspect the difference may diminish on large-scale datasets.\n2. In Figure 1, the flatness of the RDP curves is attributed to a limited range of $\\alpha \\in [2, 60]$. However, based on the alpha-selection method used in DP-SGD, extending this range only incurs minor computational cost (closed-form iterations). Would expanding this range make the curves tighter?\n3. Is it possible to theoretically characterize the crossover point in Figure 9 where the utility advantage shifts from one method to another?\n4. **Minor Typos:** \n    - (page 40) In the caption of Fig. 9, there is an unclosed parenthesis. Also, it is hard to recognize the x-label of the figures (sample size).\n    - (Line 1275) \"Since The\" --> \"Since the\"", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper has the following strengths:\n1. The paper is the **first to provide a formal privacy analysis for the widely-used random allocation scheme**.\n2. **Random allocation offers improved utility** by reducing variance and making full use of available data, particularly compared to Poisson sampling.\n3. (Extensibility) The results have immediate implications for real-world deployments of DP-SGD and federated learning, helping bridge the gap between theory and implementation.\n\nAlthough this paper is well-written, the reviewer raised the following weaknesses:\n- **Limited Utility Evaluation:** While the paper includes privacy experiments comparing sampling schemes, it lacks empirical results on utility in more complex, realistic settings. The utility claims are mainly based on toy problems such as mean estimation. Demonstrating improvements on neural network training tasks would strengthen the practical impact of the work.", "was_revised": true, "final_justification": "I acknowledge that the authors have adequately addressed my comments and questions. I find this to be an insightful piece of work; however, it is not a groundbreaking one as it does not propose a technically new scheme. \n\nFor these reasons, I am keeping my positive score of '5-Acceptance' and raising my confidence score from 3 to 4.", "rebuttal": "We thank the reviewer for their helpful comments. We would like to clarify that both [1,2] provide an extensive evaluation of the utility of random allocation, [1] also showing that it behaves similarly to shuffling. Our focus is on establishing the formal privacy guarantees for this scheme. All we need for the privacy analysis is the Gaussian noise scale and sampling/number of steps parameters that were used and so we do not need to rerun existing experiments. We will clarify this point in the revision. We added a toy example in Figure 9 and a bit of formal analysis to give the reader some intuition on why, at least in some settings, random allocation has better utility than Poisson sampling. \n\n**Replies to the reviewers questions:**\n1. **Privacy-utility tradeoff in large-scale datasets:** In short, the gap indeed decreases with the sample size at the same rate as the underlying sampling noise, which corresponds to an increase in variance of the underlying distribution by a constant factor. At the same time, as the dimension increases, the effect of the privacy noise becomes dominant relative to the additional sampling gap. A real world example of these effects can be found in the experiments of [1], and a formal asymptotic analysis can be found in the answer to question 3.\n2. **Computational complexity of RDP:** The RDP computation of the random allocation is inherently different from that of the Poisson sampling which is commonly used to analyze DP-SGD. While the computational complexity of moment accounting for the Poisson scheme is $O(1)$, it grows exponentially in $\\alpha$ in the case of random allocation (theorem 4.4), as discussed in Section F.1.\n3. **Cross point in Figure 9:** Since $\\text{Var}(\\hat{p}^{\\mathcal{A}}) = \\frac{p(1-p)}{n} + \\frac{t \\sigma^{\\mathcal{A}}}{n^{2}}$ and $\\text{Var}(\\hat{p}^{\\mathcal{P}}) \\approx \\frac{p(1-p)}{n} + \\frac{p}{n} + \\frac{t \\sigma^{\\mathcal{P}}}{n^{2}}$, where $\\sigma^{\\mathcal{A}}$ and $\\sigma^{\\mathcal{P}}$ are the scales of the noise required to achieve some fixed privacy goal for the random allocation and Poisson schemes respectively, the cross point occurs when $\\sigma^{\\mathcal{A}} - \\sigma^{\\mathcal{P}} = \\frac{n p}{t}$. While the gap between the required scales cannot be analytically derived, in can be approximated asymptotically in the high privacy regime, as discussed in Section 4.1.\n\n[1] Chua, Lynn, et al. \"Balls-and-Bins Sampling for DP-SGD.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2025.\n\n[2] Choquette-Choo, Christopher A., et al. \"Near-Exact Privacy Amplification for Matrix Mechanisms.\" The Thirteenth International Conference on Learning Representations."}]

Author rebuttal:

Meta-review: The paper looks at a classic problem of sampling in differentially private SGD and proposes a sampling where each data element appears in exactly k batches. This technique induces partial independence, so it can be seen as a compromise strategy between Poisson sampling and the classical shuffling. The authors prove that, in terms of privacy, random allocation is upper-bounded by Poisson sampling upper bounds. So this sampling scheme essentially enjoys the utility benefits of shuffling while also enjoying the privacy benefits of Poisson sampling. Thus, the paper is the first to give comprehensive theoretical analysis of the k-out-of-t random allocation scheme.

All reviewers agree that the studied problem is interesting and important, and all reviewers where impressed by the novelty of the work and the analysis. The overall positive feedback from the reviewers makes this paper a clear accept to NeurIPS. Congratulations!
However, the authors ought to pay attention to the comments regarding style and presentation, and make the minor changes accordingly prior to submitting its final version.
Decision: Accept (spotlight)