Metraipolis › archive › dc_ea4b6941ea19
Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT — arXiv:2610.42117
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.42117
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:12:40.648Z
- SHA-256 of the archived text
9dc6e034657f009fe4ce29029a703a7a082c4c113b1e40210f25eff17ccae73b- Stable URL of this page
https://metraipolis.com/documento/dc_ea4b6941ea19
How to cite
Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT — arXiv:2610.42117 — arXiv (en), https://arxiv.org/abs/2610.42117 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ea4b6941ea19 (Metraipolis archive dc_ea4b6941ea19, sha256 9dc6e034657f009fe4ce29029a703a7a082c4c113b1e40210f25eff17ccae73b)
BibTeX
@misc{dcea4b6941ea19,
title = {Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT — arXiv:2610.42117},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.42117},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ea4b6941ea19; sha256 9dc6e034657f009fe4ce29029a703a7a082c4c113b1e40210f25eff17ccae73b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42117. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.42117 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T08:02:38.955Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).