Privacy amplification by random allocation

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.

Replies to the reviewers questions:

1. 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.
2. 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.
3. 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.

[1] Chua, Lynn, et al. "Balls-and-Bins Sampling for DP-SGD." International Conference on Artificial Intelligence and Statistics. PMLR, 2025.

[2] Choquette-Choo, Christopher A., et al. "Near-Exact Privacy Amplification for Matrix Mechanisms." The Thirteenth International Conference on Learning Representations.

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.

Replies to the reviewers questions:

1. 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.
2. 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.
3. 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.

[1] Chua, Lynn, et al. "Balls-and-Bins Sampling for DP-SGD." International Conference on Artificial Intelligence and Statistics. PMLR, 2025.

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.

Replies to the reviewers questions:

1. 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.
2. 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.
3. 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.
4. 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.

Minor comments:

1. Y axis in Figure 1: The $\omega$ is simply an $\varepsilon$ printed in a vertical direction, which we realize might be confusing
2. 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.
3. Sampling method in random allocation: The steps are sampled without replacement, so that an element can participate in each step only once.
4. 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.
5. 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$.

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

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

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

[4] Chua, Lynn, et al. "How Private are DP-SGD Implementations?." International Conference on Machine Learning. PMLR, 2024.

Thank you for your response. I understand that not everything could be included in the main body due to page limitations. Still, everything should be defined and explained in the supplementary material. Because this wasn't the case with your submission, I found it hard to read. Please address all my comments for the next version.

Regarding the small comment in line 277, I was confused and thought that $\mathcal{A}(R,\ast) = R^{\otimes t}(\ast)$, and so I didn't understand why it was not written. Ignore this comment.

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.

Replies to the reviewers questions:

1. 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.
2. 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.
3. 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.