High-Dimensional Privacy-Utility Dynamics of Noisy Stochastic Gradient Descent on Least Squares

• URL: http://arxiv.org/abs/2510.16687v1
• Date: Sun, 19 Oct 2025 02:28:27 GMT
• Title: High-Dimensional Privacy-Utility Dynamics of Noisy Stochastic Gradient Descent on Least Squares
• Authors: Shurong Lin, Eric D. Kolaczyk, Adam Smith, Elliot Paquette,
• Abstract summary: Noisy descent gradient (SGD) has emerged as a cornerstone algorithm, particularly in large-scale settings.<n>This work leverages a diffusion approach to analyze noisy SGD precisely.<n>We focus on the least squares problem with $ell$ regularization.
• Score: 7.440141144728147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The interplay between optimization and privacy has become a central theme in privacy-preserving machine learning. Noisy stochastic gradient descent (SGD) has emerged as a cornerstone algorithm, particularly in large-scale settings. These variants of gradient methods inject carefully calibrated noise into each update to achieve differential privacy, the gold standard notion of rigorous privacy guarantees. Prior work primarily provides various bounds on statistical risk and privacy loss for noisy SGD, yet the \textit{exact} behavior of the process remains unclear, particularly in high-dimensional settings. This work leverages a diffusion approach to analyze noisy SGD precisely, providing a continuous-time perspective that captures both statistical risk evolution and privacy loss dynamics in high dimensions. Moreover, we study a variant of noisy SGD that does not require explicit knowledge of gradient sensitivity, unlike existing work that assumes or enforces sensitivity through gradient clipping. Specifically, we focus on the least squares problem with $\ell_2$ regularization.

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.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>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)
• DP-SGD with weight clipping [0.9208007322096533]
  We present a novel approach that mitigates the bias arising from traditional gradient clipping.<n>By leveraging a public upper bound of the Lipschitz value of the current model and its current location within the search domain, we can achieve refined noise level adjustments.
  arXiv  Detail & Related papers  (2023-10-27T09:17:15Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  Modern machine learning algorithms aim to extract fine-grained information from data to provide accurate predictions, which often conflicts with the goal of privacy protection. This paper addresses the practical and theoretical importance of developing privacy-preserving machine learning algorithms that ensure good performance while preserving privacy.
  arXiv  Detail & Related papers  (2022-09-09T08:54:13Z)
• 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)
• Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss [34.66940399825547]
  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.
  arXiv  Detail & Related papers  (2022-05-27T02:09:55Z)
• A Differentially Private Framework for Deep Learning with Convexified Loss Functions [4.059849656394191]
  Differential privacy (DP) has been applied in deep learning for preserving privacy of the underlying training sets. Existing DP practice falls into three categories - objective perturbation, gradient perturbation and output perturbation. We propose a novel output perturbation framework by injecting DP noise into a randomly sampled neuron.
  arXiv  Detail & Related papers  (2022-04-03T11:10:05Z)
• Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning [74.73901662374921]
  A differentially private model degrades the utility drastically when the model comprises a large number of trainable parameters. We propose an algorithm emphGradient Embedding Perturbation (GEP) towards training differentially private deep models with decent accuracy.
  arXiv  Detail & Related papers  (2021-02-25T04:29:58Z)
• 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)
• Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification [47.23063195722975]
  Differentially private SGD (DP-SGD) is one of the most popular methods for solving differentially private empirical risk minimization (ERM) Due to its noisy perturbation on each gradient update, the error rate of DP-SGD scales with the ambient dimension $p$, the number of parameters in the model. We propose Projected DP-SGD that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace.
  arXiv  Detail & Related papers  (2020-07-07T22:31:01Z)
• Understanding Gradient Clipping in Private SGD: A Geometric Perspective [68.61254575987013]
  Deep learning models are increasingly popular in many machine learning applications where the training data may contain sensitive information. Many learning systems now incorporate differential privacy by training their models with (differentially) private SGD. A key step in each private SGD update is gradient clipping that shrinks the gradient of an individual example whenever its L2 norm exceeds some threshold.
  arXiv  Detail & Related papers  (2020-06-27T19:08: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.