Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness

• URL: http://arxiv.org/abs/2410.01068v1
• Date: Tue, 1 Oct 2024 20:52:08 GMT
• Title: Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness
• Authors: Eli Chien, Pan Li,
• Abstract summary: We study the Differential Privacy (DP) guarantee of hidden-state Noisy-SGD algorithms over a bounded domain. We prove convergent R'enyi DP bound for non-smooth non-smooth losses. We also provide a strictly better privacy bound compared to state-of-the-art results for smooth convex losses.
• Score: 16.303040664382138
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the Differential Privacy (DP) guarantee of hidden-state Noisy-SGD algorithms over a bounded domain. Standard privacy analysis for Noisy-SGD assumes all internal states are revealed, which leads to a divergent R'enyi DP bound with respect to the number of iterations. Ye & Shokri (2022) and Altschuler & Talwar (2022) proved convergent bounds for smooth (strongly) convex losses, and raise open questions about whether these assumptions can be relaxed. We provide positive answers by proving convergent R'enyi DP bound for non-convex non-smooth losses, where we show that requiring losses to have H\"older continuous gradient is sufficient. We also provide a strictly better privacy bound compared to state-of-the-art results for smooth strongly convex losses. Our analysis relies on the improvement of shifted divergence analysis in multiple aspects, including forward Wasserstein distance tracking, identifying the optimal shifts allocation, and the H"older reduction lemma. Our results further elucidate the benefit of hidden-state analysis for DP and its applicability.

Related papers

• Noise is All You Need: Private Second-Order Convergence of Noisy SGD [15.31952197599396]
  We show that noise necessary for privacy already implies second-order convergence under the standard smoothness assumptions. We get second-order convergence essentially for free: DP-SGD, the workhorse of modern private optimization, under minimal assumptions can be used to find a second-order stationary point.
  arXiv  Detail & Related papers  (2024-10-09T13:43:17Z)
• Differential Privacy of Noisy (S)GD under Heavy-Tailed Perturbations [6.220757855114254]
  Injecting heavy-tailed noise to the iterates of descent (SGD) has received increasing attention over the past few years. We show that SGD with heavy-tailed perturbations achieves $(0, tildemathcalO (1/n)$ DP guarantees. We illustrate that the heavy-tailed noising mechanism achieves similar DP guarantees compared to the Gaussian case, which suggests that it can be a viable alternative to its light-tailed counterparts.
  arXiv  Detail & Related papers  (2024-03-04T13:53:41Z)
• 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)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Using Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) to ensure Differential Privacy (DP) comes at the cost of model performance degradation. We propose a new error-feedback (EF) DP algorithm as an alternative to DPSGD-GC. We establish an algorithm-specific DP analysis for our proposed algorithm, providing privacy guarantees based on R'enyi DP.
  arXiv  Detail & Related papers  (2023-11-24T17:56:44Z)
• Privacy Loss of Noisy Stochastic Gradient Descent Might Converge Even for Non-Convex Losses [4.68299658663016]
  The Noisy-SGD algorithm is widely used for privately training machine learning models. Recent findings have shown that if the internal state remains hidden, then the privacy loss might remain bounded. We address this problem for DP-SGD, a popular variant of Noisy-SGD that incorporates gradient clipping to limit the impact of individual samples on the training process.
  arXiv  Detail & Related papers  (2023-05-17T02:25:56Z)
• Generalised Likelihood Ratio Testing Adversaries through the Differential Privacy Lens [69.10072367807095]
  Differential Privacy (DP) provides tight upper bounds on the capabilities of optimal adversaries. We relax the assumption of a Neyman--Pearson (NPO) adversary to a Generalized Likelihood Test (GLRT) adversary. This mild relaxation leads to improved privacy guarantees.
  arXiv  Detail & Related papers  (2022-10-24T08:24:10Z)
• 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)
• 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)
• Differentially Private SGDA for Minimax Problems [83.57322009102973]
  We prove that gradient descent ascent (SGDA) can achieve optimal utility in terms of weak primal-dual population risk. This is the first-ever-known result for non-smoothly-strongly-concave setting.
  arXiv  Detail & Related papers  (2022-01-22T13:05:39Z)
• 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)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  We provide sharp upper and lower bounds for several forms of gradient descent (SGD) on arbitrary Lipschitz nonsmooth convex losses. Our bounds allow us to derive a new algorithm for differentially private nonsmooth convex optimization with optimal excess population risk.
  arXiv  Detail & Related papers  (2020-06-12T02:45:21Z)

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.