Balls-and-Bins Sampling for DP-SGD

• URL: http://arxiv.org/abs/2412.16802v1
• Date: Sat, 21 Dec 2024 23:09:14 GMT
• Title: Balls-and-Bins Sampling for DP-SGD
• Authors: Lynn Chua, Badih Ghazi, Charlie Harrison, Ethan Leeman, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang,
• Abstract summary: We introduce the Balls-and-Bins sampling for differentially private (DP) optimization methods such as DP-SGD. We show that Balls-and-Bins sampling achieves the "best-of-both" samplers, namely, the implementation of Balls-and-Bins sampling is similar to that of Shuffling.
• Score: 56.959167524617456
• License:
• Abstract: We introduce the Balls-and-Bins sampling for differentially private (DP) optimization methods such as DP-SGD. While it has been common practice to use some form of shuffling in DP-SGD implementations, privacy accounting algorithms have typically assumed that Poisson subsampling is used instead. Recent work by Chua et al. (ICML 2024) however pointed out that shuffling based DP-SGD can have a much larger privacy cost in practical regimes of parameters. We show that the Balls-and-Bins sampling achieves the "best-of-both" samplers, namely, the implementation of Balls-and-Bins sampling is similar to that of Shuffling and models trained using DP-SGD with Balls-and-Bins sampling achieve utility comparable to those trained using DP-SGD with Shuffling at the same noise multiplier, and yet, Balls-and-Bins sampling enjoys similar-or-better privacy amplification as compared to Poisson subsampling in practical regimes.

Related papers

• To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling [25.669347036509134]
  We analyze Differentially Private Gradient Descent (DP-SGD) with shuffling. We show that state-of-the-art DP models trained with shuffling appreciably overestimated privacy guarantees (up to 4x) Our work empirically attests to the risk of using shuffling instead of Poisson sub-sampling vis-a-vis the actual privacy leakage of DP-SGD.
  arXiv  Detail & Related papers  (2024-11-15T22:34:28Z)
• Scalable DP-SGD: Shuffling vs. Poisson Subsampling [61.19794019914523]
  We provide new lower bounds on the privacy guarantee of the multi-epoch Adaptive Linear Queries (ABLQ) mechanism with shuffled batch sampling. We show substantial gaps when compared to Poisson subsampling; prior analysis was limited to a single epoch. We introduce a practical approach to implement Poisson subsampling at scale using massively parallel computation.
  arXiv  Detail & Related papers  (2024-11-06T19:06:16Z)
• Towards Efficient and Scalable Training of Differentially Private Deep Learning [5.825410941577592]
  Differentially private gradient descent (DP-SGD) is the standard algorithm for training machine learning models under differential privacy (DP) Implementing computationally efficient DP-SGD with Poisson subsampling is not trivial, which leads to many implementations ignoring this requirement. We conduct a comprehensive empirical study to quantify the computational cost of training deep learning models under DP. We find that using the naive implementation DP-SGD with Opacus in PyTorch has between 2.6 and 8 times lower throughput of processed training examples per second than SGD.
  arXiv  Detail & Related papers  (2024-06-25T06:04:58Z)
• How Private are DP-SGD Implementations? [61.19794019914523]
  We show that there can be a substantial gap between the privacy analysis when using the two types of batch sampling. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling.
  arXiv  Detail & Related papers  (2024-03-26T13:02:43Z)
• Preconditioned Score-based Generative Models [49.88840603798831]
  An intuitive acceleration method is to reduce the sampling iterations which however causes severe performance degradation. We propose a model-agnostic bfem preconditioned diffusion sampling (PDS) method that leverages matrix preconditioning to alleviate the aforementioned problem. PDS alters the sampling process of a vanilla SGM at marginal extra computation cost, and without model retraining.
  arXiv  Detail & Related papers  (2023-02-13T16:30:53Z)
• Smoothed Differential Privacy [55.415581832037084]
  Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP.
  arXiv  Detail & Related papers  (2021-07-04T06:55:45Z)
• Practical and Private (Deep) Learning without Sampling or Shuffling [24.29228578925639]
  We consider training models with differential privacy using mini-batch gradients. We analyze a DP variant of Follow-The-Regularized-Leader (DP-FTRL) that compares favorably to amplified DP-SGD.
  arXiv  Detail & Related papers  (2021-02-26T20:16:26Z)
• On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times [51.61278695776151]
  Federated Learning (FL) is well known for its privacy protection when training machine learning models among distributed clients collaboratively. Recent studies have pointed out that the naive FL is susceptible to gradient leakage attacks. Differential Privacy (DP) emerges as a promising countermeasure to defend against gradient leakage attacks.
  arXiv  Detail & Related papers  (2021-01-11T19:43:12Z)

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.