aiqbench analysis
This paper speeds up privacy-loss accounting for random-allocation sampling, a scheme that can improve on Poisson sampling in differentially private training. Its main result is a reduction in running time from quadratic to near-linear in the inverse accuracy parameter, along with tighter privacy bounds for DP-SGD. For ML practitioners, the practical gain is more precise privacy budgets for private training at lower compute cost. The reported speedups come from the authors' experiments and have not been independently validated.
Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT
arXiv:2610.42117v1 Announce Type: new 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 $\alpha$ (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 $\alpha$ from $O(\alpha^{-2})$ to $O(\alpha^{-1}\log(1/\alpha))$. 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 $\chi^2$ divergence of the computed pair from the order of $\alpha$ to $O(\alpha^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.
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 $\alpha$ (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 $\alpha$ from $O(\alpha^{-2})$ to $O(\alpha^{-1}\log(1/\alpha))$. 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 $\chi^2$ divergence of the computed pair from the order of $\alpha$ to $O(\alpha^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.
Machine Learning (cs.LG)
arXiv:2610.42117 [cs.LG]
(or arXiv:2610.42117v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.42117 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 288 words
Related coverage
Falsification-proof non-market allocation mechanisms
arXiv · Oct 15, 2026
Tradeoff-Aware Territory Design: A Multi-Objective Decision System for Enterprise Customer-to-Seller Allocation
arXiv · Oct 27, 2026
End-to-End Fairness Optimization with Fair Decision-Focused Learning
arXiv · Aug 3, 2026
Counterfactual Reasoning for Causal Responsibility Attribution in Probabilistic Multi-Agent Systems
arXiv · Aug 5, 2026