Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss

• URL: http://arxiv.org/abs/2205.13710v1
• Date: Fri, 27 May 2022 02:09:55 GMT
• Title: Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
• Authors: Jason M. Altschuler and Kunal Talwar
• Abstract summary: Industry has widely adopted a simple algorithm: Gradient Descent with noise (a.k.a. Gradient Langevin Dynamics) Questions about this algorithm's privacy loss remain open -- even in the seemingly simple setting of smooth convex losses over a bounded domain. We characterize the differential privacy up to a constant factor and show that after a small burn-in period, running SGD longer leaks no further privacy.
• Score: 34.66940399825547
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 range of parameters, we characterize the differential privacy up to a constant factor. This result reveals that all previous analyses for this setting have the wrong qualitative behavior. Specifically, while previous privacy analyses increase ad infinitum in the number of iterations, we show that after a small burn-in period, running SGD longer leaks no further privacy. Our analysis departs completely from previous approaches based on fast mixing, instead using techniques based on optimal transport (namely, Privacy Amplification by Iteration) and the Sampled Gaussian Mechanism (namely, Privacy Amplification by Sampling). Our techniques readily extend to other settings, e.g., strongly convex losses, non-uniform stepsizes, arbitrary batch sizes, and random or cyclic choice of batches.

Related papers

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications. Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility. We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines. We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Shifted Interpolation for Differential Privacy [6.1836947007564085]
  Noisy gradient descent and its variants are the predominant algorithms for differentially private machine learning. This paper establishes the "privacy amplification by corollary" phenomenon in the unifying framework of $f$-differential privacy. Notably, this leads to the first exact privacy analysis in the foundational setting of strongly convex optimization.
  arXiv  Detail & Related papers  (2024-03-01T04:50:04Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints [53.01656650117495]
  There is a disconnect between how researchers and practitioners handle privacy-utility tradeoffs. Brownian mechanism works by first adding Gaussian noise of high variance corresponding to the final point of a simulated Brownian motion. We complement our Brownian mechanism with ReducedAboveThreshold, a generalization of the classical AboveThreshold algorithm.
  arXiv  Detail & Related papers  (2022-06-15T01:43:37Z)
• Differentially Private Learning Needs Hidden State (Or Much Faster Convergence) [9.429448411561541]
  We show that differentially private learning, with a tight bound, needs hidden state privacy analysis or a fast convergence. Our converging privacy analysis, thus, shows that differentially private learning, with a tight bound, needs hidden state privacy analysis or a fast convergence.
  arXiv  Detail & Related papers  (2022-03-10T13:31:08Z)
• Privacy Amplification Via Bernoulli Sampling [24.23990103106668]
  We analyze privacy amplification properties of a new operation, sampling from the posterior, that is used in Bayesian inference. We provide an algorithm to compute the amplification factor in this setting, and establish upper and lower bounds on this factor.
  arXiv  Detail & Related papers  (2021-05-21T22:34:32Z)
• 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)
• Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent [10.409652277630132]
  We model the dynamics of privacy loss in Langevin diffusion and extend it to the noisy gradient descent algorithm. We prove that the privacy loss converges exponentially fast.
  arXiv  Detail & Related papers  (2021-02-11T05:49:37Z)
• 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)
• The Discrete Gaussian for Differential Privacy [26.179150185540514]
  A key tool for building differentially private systems is adding Gaussian noise to the output of a function evaluated on a sensitive dataset. Previous work has demonstrated that seemingly innocuous numerical errors can entirely destroy privacy. We introduce and analyze the discrete Gaussian in the context of differential privacy.
  arXiv  Detail & Related papers  (2020-03-31T18:00:00Z)

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.