Scalable DP-SGD: Shuffling vs. Poisson Subsampling

We thank the reviewer for their thoughtful comments.

add a comparison of the the various privacy analyses to the upper bounds provided by existing literature on general shuffle model

While the amplification bounds for shuffling such as by Feldman et al. provide upper bounds, we did not consider it because

• our focus in this work was primarily to compare lower bounds for Shuffle DP-SGD with upper bounds for Poisson DP-SGD, and
• in the regime of small noise multipliers, where we see that our lower bound on the noise multiplier of Shuffle DP-SGD is quite close to that of Deterministic (no amplification), these upper bounds on amplification by shuffling have to necessarily be near-vacuous (cannot be much better than deterministic).

Nevertheless, this is a valuable point, and we will include at least the noise multipliers obtained via these amplification upper bounds for comparison in a future revision.

sampling without replacement (Similar point raised by Reviewer 1Uvo)

Indeed, sampling without replacement (i.e., sampling fixed-sizes batches uniformly and independently at random) can also be implemented using the massively parallel computation approach we propose. We did not however consider it in our evaluation however since the privacy guarantees of that are worse than that of Poisson subsampling. Similar to your point, as noted in this recent work of Lebeda et al., the noise scale required for this method is twice that required for Poisson subsampling. We will revise the paper to include a discussion of this alternative approach.

We thank the reviewer for their thoughtful comments.

quantify the gap between Poisson sampling and Truncated Poisson sampling

While it is likely that our analysis for truncated Poisson sampling is not optimal, it is reasonable enough in practice. The loss due to truncation is very minimal to the privacy accounting as we allocate only $0.1 \delta$ for the truncation part, as seen by how the noise multiplier for Poisson subsampling with and without truncation are quite similar (seen in Fig. 2, 3). Note that the trade-off here is only between privacy and computation: larger maximum batch size means accounting is closer to (untruncated) Poisson subsampling, at the cost of increased computation during model training. Thus, the optimal accounting for truncated Poisson subsampling would at best allow us to use a slightly smaller maximum batch size, which would only slightly reduce the computational cost of training. Since this was not central to our work, we did not optimize the analysis to the best possible. Thanks for raising this, and we will consider adding this to the discussion.

find the best sampling probability to use in terms of the expected signal to noise ratio

While we do not optimize this theoretically, this was indeed our motivation for considering different batch sizes in Figure 2.

include a comparison where Epochs is varied on the x-axis and sigma is varied on the y-axis

We provide $\sigma$ values for different accounting methods in the table below, as well as in a plot in Figure 1 of the attached pdf. Note that the values for the $\cal P$ sampler are upper bounds, whereas the values for $\cal S$ samplers are lower bounds. Again observe that the values for $\cal P$ (truncated Poisson subsampling) are very close to ${\cal S}^{\circlearrowright}$ ($\cal P$ accounting), the latter corresponding to untruncated Poisson subsampling.

Observe that the values of Poisson subsampling with truncation are slightly larger than that without truncation.

evenly space out the independent variables

Thanks for the suggestion. We will modify the plots accordingly.

Why do these lines line up in the middle plots

As argued above, the additional privacy loss due to truncation of the batch in Poisson subsampling is minimal even with our sub-optimal analysis, and so while the values with and without truncation are not exactly the same, the difference is negligible compared to the scale of the rest of the plot.

We would like to clarify that for the table we shared, the expected batch sizes for Poisson subsampling are the same as the physical batch size for Shuffle and Deterministic; by "${\cal S}^{\circlearrowright}$ (with $\cal P$ accounting)", we mean the same method as ${\cal S}^{\circlearrowright}$, but using the noise multiplier assuming Poisson subsampling (without any truncation). While truncation in Poisson subsampling does reduce the expected batch size by a small amount, this is quite negligible and hence the normalization would be by approximately the same quantity. In particular, we use the values of $\varepsilon = 5$, $\delta = 2.7 \cdot 10^{-8}$ and (expected) batch size $b = 200000$. Please let us know if there are still any further questions.

For truncated Poisson subsampling, we use a maximum batch size as specified below, which includes the dummy examples added to ensure that all batches have the same size. The normalization is still by expected batch size (before truncation), which is $b = 200,000$.

We thank the reviewer for their thoughtful comments.

novelty over prior work [Similar to Reviewer vHjL]

While it may seem that our privacy analysis used some standard techniques (discretization, post-processing and PLD accounting), it was a priori unclear if such a simple method would be effective at providing strong lower bounds, let alone what such a method (e.g. the choice of discretization sets) would be. We would like to note that the prior work of Chua et al explicitly notes in Section 5, that [their] approach is limited to a “single epoch” mechanism ... Extending [their] approach to multiple epochs will be interesting. Moreover, while they are primarily focused on theoretical analysis, we also study practical implementations and evaluations on real world problems to verify the empirical feasibility of the proposed methods.

privacy amplification by iteration is not mentioned.

Understanding when privacy amplification by iteration applies remains an interesting direction, but as of now there is no evidence that it can provide any improvements in the general (non-convex) setting. In fact, a recent work suggests that such an improvement might not be possible for general non-convex losses. We will include a discussion on the same in a revision.

Importance of upper bounds for the shuffled DP-SGD?

This would be relevant in a regime where Shuffle-DP-SGD performs better than Poisson subsampling. In this case, we would need an “upper-bound” accounting method to report a correct DP guarantee. But we agree that it is less relevant in regimes where Shuffle DP-SGD has worse model utility.

subsampling without replacement (Similar point raised by Reviewer k7t2)

Sampling without replacement (i.e., sampling fixed-sizes batches uniformly and independently at random) can also be implemented using a variant of the massively parallel computation approach we propose. We did not consider it in our evaluation however since the privacy guarantees of that are worse than that of Poisson subsampling. In particular, as noted in this recent work of Lebeda et al., the noise scale required for this method is twice that required for Poisson subsampling. We will revise the paper to include a discussion of this alternative approach.

We thank the reviewer for their thoughtful comments.

techniques for extending to multi-epoch are straightforward. [Similar to Reviewer 1Uvo]

While it may seem that our privacy analysis used some standard techniques (discretization, post-processing and PLD accounting), it was a priori unclear if such a simple method would be effective at providing strong lower bounds, let alone what such a method (e.g. the choice of discretization sets) would be. We would like to note that the prior work of Chua et al explicitly notes in Section 5, that [their] approach is limited to a “single epoch” mechanism ... Extending [their] approach to multiple epochs will be interesting. Moreover, while they are primarily focused on theoretical analysis, we also study practical implementations and evaluations on real world problems to verify the empirical feasibility of the proposed methods.

material overlap in Sec. 2 and 3.

Section 2 consists mainly of definitions (some standard and some from Chua et al), resulting in the overlap; please note that we have cited them in all relevant places. Nevertheless, thank you for bringing this to our attention and we will keep this in mind as we revise the paper to highlight our contributions better.

Different types of batch sampling with different privacy accounting are evaluated ... all of them underestimate the privacy loss and cannot rigorously reflect the model utility under the claimed $(\epsilon, \delta)$.

We would like to clarify a possible misunderstanding here, that for Poisson subsampling based DP-SGD, we use the dp_accounting library that overestimates the privacy loss, and for Shuffle based DP-SGD, our method underestimates the privacy loss. So the way to interpret our results is that: whenever Poisson subsampling based DP-SGD out-performs Shuffle-based DP-SGD, this would hold even if we use the optimal accounting for each method.

Have the authors tested the implementation from Opacus on the Criteo dataset?

Using the implementation from Opacus requires efficient random access to all the data points (e.g. loading the entire dataset in memory), which is not always feasible depending on the machine and configuration, given that the Criteo dataset takes 49GB of storage. We believe such a comparison does not provide too much scientific value, because for small datasets that can fit in memory, the Opacus solution and our method would perform similarly because they are mathematically equivalent. But in contrast to our methods, to the best of our knowledge, it is not straightforward how to scale Opacus to larger datasets.

Is the target batch size b still used to average the summed noisy gradients for the truncated Poisson Batch sampler? Could the authors elaborate on how the size of truncated batches would affect the tracking of privacy loss, especially in Theorem 3.3?

We average the summed noisy gradients using the expected batch size; in any case, this is simply a scaling factor that can be assimilated in the learning rate, hence it is not important whether we normalize by the expected or maximum batch size. There is a privacy-vs-computation tradeoff in the choice of maximum batch size $B$ in the Poisson sampler: Taking $B$ to be large gets us closer to the privacy guarantee of the (untruncated) Poisson sampler, but increases the computation cost, since the batches are now larger (even if they contain dummy values with zero weight).

Line 254 -255, could the authors provide more details on selecting Ci in practice? And what is the computation complexity regarding this part?

Indeed, while any choice of $C_i$’s are valid, there is an accuracy-vs-computation trade-off, in that, making $C_1$ smaller, $C_m$ larger and adding large number of intermediate $C_i$’s improves the accuracy of the lower bound at the cost of increased computational complexity.

• As we note in the paper, we choose $C_1$ to be small enough, and $C_m$ to be large enough so that $P_{\cal S}(G_0)$ and $P_{\cal S}(G_{m+1})$ to be small enough. In particular, we chose the values to ensure $P_{\cal S}(G_0) + P_{\cal S}(G_{m+1}) \le e^{-40}$.
• We chose $C_i$’s to be equally spaced in between $C_1$ and $C_m$ with a gap of $\Delta * \sigma^2$, where $\Delta$ is the desired discretization of the PLD. This is a heuristic choice guided by the intuition that we would like to discretize in buckets such that the privacy loss changes by $\Delta$, and since the privacy loss is approximately given as $\max_t x_t / \sigma^2$, the chosen gap means that this approximate privacy loss varies by $\Delta$ between buckets.

These details are present in the implementation provided in the Colab link in the paper. But we will highlight these details more prominently in a revision.

Please let us know if there are any further questions we can clarify, and if we have satisfactorily addressed the concerns of the reviewer, we kindly ask the reviewer to revisit the rating.

Opacus supports (distributed) Poisson sampling without the need to load the entire dataset (e.g., simply by indexing). I suggest the authors do their due diligence and check the implementation at https://opacus.ai/api/_modules/opacus/utils/uniform_sampler.html

Thanks to the reviewer for the pointer. We apologize that our original text in lines 47-49 could be misinterpreted as “Opacus solution requires loading the dataset into the memory”. We meant to say that “loading into memory” is one way to facilitate this feature for small datasets. We will revise the text to make it more precise.

To avoid any further misunderstanding between us and the reviewer on this matter, we summarize our view of the Opacus solution here: Opacus Poisson Subsampling works by using a unique identifier to index each example, and sampling the indices. They also provide a distributed sampler where each worker samples from a random subset of indices. This approach relies on a DataLoader that can provide efficient random access --- given an arbitrary index, read the corresponding data point efficiently. If random access is slow, the data pipeline will be slow, even though the (index) sampler is not the bottleneck.

For small datasets, this can be easily supported by loading the data into memory. For large datasets that do not fit in the memory, various technical challenges need to be addressed to make it work. For example, many formats for raw data (e.g. csv, typically used for tabular or text data) or serialized data (e.g. tfrecords files, commonly used by the Tensorflow Datasets Catalog) do not naturally support random indexing; moreover, random access can be much slower than sequential bulk reading in cases such as when the dataset is stored in a distributed file system. Various workarounds do exist depending on the resources and constraints, for example, by storing each example as an individual file in a fast SSD attached to the trainer machine. But those solutions usually need to be tailored to specific hardware and cluster infrastructures. On the contrary, we provide a generic solution that works for a large range of scales of dataset sizes and with minimal assumption / requirement on the underlying IO infrastructure.

We agree that an empirical comparison of different technical solutions could be interesting but it is quite difficult to get right and useful as everyone has different configurations of (distributed) file systems, file format of preference, cluster configuration with communication channels of different properties, etc. Therefore it is quite far from the scope of our paper.

Finally, regardless of the underlying technical solution, please note that ours is the first large-scale DP training experiment with Poisson subsampling, comparing its feasibility with other solutions from multiple angles, including accounting, efficiency, and model utility.

truncated Poisson sampling distorts the probability of each sample being included in a batch

It is true that due to truncation in Poisson subsampling, the probability that an example lands in a batch is reduced slightly. This is handled in the privacy analysis (Theorem 3.3).

Please let us know if there are any further questions.