Privacy Amplification by Random Allocation
AuthorsVitaly Feldman, Moshe Shenfeld†
AuthorsVitaly Feldman, Moshe Shenfeld†
We consider the privacy amplification properties of a sampling scheme in which a user's data is used in steps chosen randomly and uniformly from a sequence (or set) of steps. This sampling scheme has been recently applied in the context of differentially private optimization(Chua et al., 2024; Choquette-Choo et al., 2024) and is also motivated by communication-efficient high-dimensional private aggregation (Asi et al., 2025). Existing analyses of this scheme either rely on privacy amplification by shuffling which leads to overly conservative bounds or require Monte Carlo simulations that are computationally prohibitive in most practical scenarios.
We give the first theoretical guarantees and numerical estimation algorithms for this sampling scheme. In particular, we demonstrate that the privacy guarantees of random -out-of- allocation can be upper bounded by the privacy guarantees of the well-studied independent (or Poisson) subsampling in which each step uses the user's data with probability . Further, we provide two additional analysis techniques that lead to numerical improvements in several parameter regimes. Altogether, our bounds give efficiently-computable and nearly tight numerical results for random allocation applied to Gaussian noise addition.
October 2, 2022research area Methods and Algorithms, research area Privacyconference NeurIPS
A central issue in machine learning is how to train models on sensitive user data. Industry has widely adopted a simple algorithm: Stochastic Gradient Descent with noise (a.k.a. Stochastic Gradient Langevin Dynamics). However, foundational theoretical questions about this algorithm's privacy loss remain open -- even in the seemingly simple setting of smooth convex losses over a bounded domain. Our main result resolves these questions: for a large...
July 13, 2021research area Methods and Algorithms, research area Privacyconference FOCS
Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta demonstrates that random shuffling amplifies differential privacy guarantees of locally randomized data. Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously and has lead to significant interest in the shuffle model of privacy
We show that random shuffling of data records that are input to...