Fast privacy accounting method speeds up random allocation sampling
Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT
Machine Learning
Summary
Keeping data private while using it in multiple steps is tricky, especially when users' data is randomly selected for these steps. The authors found a faster way to calculate how much privacy is lost during this process using a new technique combining grids and quick math tools called FFTs. Their method is much faster, especially when high accuracy is needed, and it reduces errors from rounding. This helps improve privacy guarantees for algorithms like DP-SGD used in machine learning.
What this means in practice
- •For machine learning engineers: Compute more accurate and faster privacy loss metrics for training machine learning models with differential privacy using random allocation sampling.
- •For data privacy teams: Improve privacy accounting in systems that aggregate user data with random allocation to enhance confidentiality guarantees efficiently.
Authors
Vitaly Feldman, Moshe Shenfeld
Abstract
In the random allocation sampling scheme each user's data is used in $k$ steps chosen randomly and uniformly from a sequence of $t$ steps. This scheme is known to improve on Poisson sampling in private optimization and in communication-efficient aggregation. The existing privacy loss distribution (PLD) accountant for this scheme runs in time quadratic in the inverse of the accuracy parameter $α$ (Feldman and Shenfeld, 2026). We give an algorithm, \emph{multiscale FFT}, that represents likelihood ratios on a grid that is uniform within each dyadic interval and computes the exact rounding of every pairwise sum using FFTs within each interval. It keeps the guarantees of the accountant and improves the dependence of its running time on $α$ from $O(α^{-2})$ to $O(α^{-1}\log(1/α))$. In addition, we demonstrate that rounding can be performed via the mean-preserving connect-the-dots projection of (Doroshenko et al., 2026). This reduces the errors that rounding introduces in the mean of the privacy loss and in the $χ^2$ divergence of the computed pair from the order of $α$ to $O(α^2/\log(t))$. In our experiments, our algorithm achieves speedups of several orders of magnitude at high accuracy and gives improved privacy bounds for DP-SGD with PREAMBLE.