Privacy amplification by random allocation

• URL: http://arxiv.org/abs/2502.08202v3
• Date: Mon, 02 Jun 2025 02:39:42 GMT
• Title: Privacy amplification by random allocation
• Authors: Vitaly Feldman, Moshe Shenfeld,
• Abstract summary: We consider the privacy amplification properties of a sampling scheme in which a user's data is used in $k$ steps chosen randomly and uniformly from a sequence (or set) of $t$ steps.<n>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.<n>In particular, we demonstrate that the privacy guarantees of random $k$-out-of-$t$ allocation can be upper bounded by the privacy guarantees of the well-studied independent (or Poisson) subsampling.
• Score: 18.231854497751137
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider the privacy amplification properties of a sampling scheme in which a user's data is used in $k$ steps chosen randomly and uniformly from a sequence (or set) of $t$ steps. This sampling scheme has been recently applied in the context of differentially private optimization [Chua et al., 2024a, 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 $k$-out-of-$t$ 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 $(1+o(1))k/t$. 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.

Related papers

• Efficient privacy loss accounting for subsampling and random allocation [13.186391867041394]
  We consider the privacy amplification properties of a sampling scheme in which a user's data is used in random steps.<n>We show that the privacy-utility trade-off for random allocation is at least as good as that of Poisson subsampling.
  arXiv  Detail & Related papers  (2026-02-19T11:44:25Z)
• LoRA and Privacy: When Random Projections Help (and When They Don't) [55.65932772290123]
  We introduce the (Wishart) projection mechanism, a randomized map of the form $S mapsto M f(S)$ with $M sim W_d (1/r I_d, r)$ and study its differential privacy properties.<n>For vector-valued queries $f$, we prove non-asymptotic DP guarantees without any additive noise, showing that Wishart randomness alone can suffice.<n>For matrix-valued queries, however, we establish a sharp negative result: in the noise-free setting, the mechanism is not DP, and we demonstrate its vulnerability.
  arXiv  Detail & Related papers  (2026-01-29T13:43:37Z)
• Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation [6.087515951830486]
  We study privacy amplification for differentially private model training with matrix factorization under random allocation.<n>Our framework applies to arbitrary banded and non-banded matrices.
  arXiv  Detail & Related papers  (2026-01-29T12:40:29Z)
• Private Hyperparameter Tuning with Ex-Post Guarantee [98.43027866582979]
  " Utility-first" privacy mechanisms prioritize a desired level of utility and then determine the corresponding privacy cost.<n>We extend the work of Wu et al. [ 2019] and Liu and Talwar [ 2019] to support any sequence of private estimators.<n>We demonstrate that hyper parameter tuning for these estimators, including the selection of an optimal privacy budget, can be performed without additional privacy cost.
  arXiv  Detail & Related papers  (2025-08-21T02:42:23Z)
• Debiasing Functions of Private Statistics in Postprocessing [6.22153888560487]
  We derive an unbiased estimator for private means when the size $n$ of the dataset is not publicly known. We also apply our estimators to develop unbiased transformation mechanisms for per-record differential privacy.
  arXiv  Detail & Related papers  (2025-02-18T22:16:37Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm. DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms. We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation. We obtain several improved algorithms for private optimization problems, including decomposable submodular and set algorithm cover.
  arXiv  Detail & Related papers  (2024-05-28T19:02:30Z)
• Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition [13.192083588571384]
  We consider the problem of computing tight privacy guarantees for the composition of subsampled differentially private mechanisms. Recent algorithms can numerically compute the privacy parameters to arbitrary precision but must be carefully applied.
  arXiv  Detail & Related papers  (2024-05-27T20:30:12Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Privacy Profiles for Private Selection [21.162924003105484]
  We work out an easy-to-use recipe that bounds privacy profiles of ReportNoisyMax and PrivateTuning using the privacy profiles of the base algorithms they corral. Our approach improves over all regimes of interest and leads to substantial benefits in end-to-end private learning experiments.
  arXiv  Detail & Related papers  (2024-02-09T08:31:46Z)
• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  We show how to shuffle $(epsilon_i,delta_i)$-PLDP setting with personalized privacy parameters. We prove that shuffled $(epsilon_i,delta_i)$-PLDP process approximately preserves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  arXiv  Detail & Related papers  (2023-12-22T02:31:46Z)
• Enhancing Trade-offs in Privacy, Utility, and Computational Efficiency through MUltistage Sampling Technique (MUST) [3.0939420223851446]
  We propose a class of subsampling methods for privacy amplification (PA) We conduct comprehensive analyses of the PA effects and utility for several 2-stage MUST procedures. We provide the privacy loss composition analysis over repeated applications of MUST.
  arXiv  Detail & Related papers  (2023-12-20T19:38:29Z)
• Privacy Amplification via Shuffling: Unified, Simplified, and Tightened [20.10078781197001]
  We propose a comprehensive framework for privacy amplification in both single-message and multi-message shuffle protocols. Our theoretical results demonstrate that our framework provides tighter bounds, especially for local randomizers with extremal probability design. Our bounds also result in a remarkably efficient $tildeO(n)$ algorithm that numerically amplifies privacy in less than $10$ seconds for $n=108$ users.
  arXiv  Detail & Related papers  (2023-04-11T06:27:25Z)
• Individual Privacy Accounting with Gaussian Differential Privacy [8.81666701090743]
  Individual privacy accounting enables bounding differential privacy (DP) loss individually for each participant involved in the analysis. In order to account for the individual privacy losses in a principled manner, we need a privacy accountant for adaptive compositions of randomised mechanisms.
  arXiv  Detail & Related papers  (2022-09-30T17:19:40Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
  This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP) We present confidence intervals (CI) and time-uniform confidence sequences (CS) for $mustar$ when only given access to the privatized data.
  arXiv  Detail & Related papers  (2022-02-17T16:04:49Z)
• Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates [34.023599653814415]
  We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method.
  arXiv  Detail & Related papers  (2021-07-20T23:19:11Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.