Better Batches, Better Privacy: Random Allocation for DP-BandMF

The current state of the art for batch selection and noise addition in differentially private training is a combination of BandMF (informally, DP-SGD where the noise added in two different steps can be correlated if the steps are within $b$ of each other) and privacy amplification by sampling with privacy accounting using Monte Carlo accounting. We identify and improve on some gaps in the past work on the combination of these techniques. First, the prior work for BandMF proposed batch selection strategies that were inspired by Poisson sampling, whereas for DP-SGD random allocation is known to outperform Poisson sampling. We address this by proposing and giving privacy analyses for new batch selection strategies for BandMF inspired instead by random allocation, which empirically outperform previous work. Second, Monte Carlo accounting typically requires drawing $O(1/\delta )$ samples from a privacy loss distribution, introducing a large up-front cost for accounting. We demonstrate how to increase the throughput of sampling by making the sampling algorithm more amenable to GPU acceleration. Finally, previous work chose the correlation matrix for the noise and the batch selection strategy independently. We give a simple framework for choosing these parameters jointly, and demonstrate utility gains by accounting for privacy amplification in our choice of correlation matrix.