Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods

• URL: http://arxiv.org/abs/2511.16587v1
• Date: Thu, 20 Nov 2025 17:42:40 GMT
• Title: Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods
• Authors: Amartya Mukherjee, Jun Liu,
• Abstract summary: Differentially rigorous gradient descent (DP-SGD) has become the standard algorithm for machine learning models with privacy guarantees.<n>We show that despite its widespread expectation of convergence, the algorithm remains in both convex nonwise regimes.
• Score: 7.061954653503474
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Differentially private stochastic gradient descent (DP-SGD) has become the standard algorithm for training machine learning models with rigorous privacy guarantees. Despite its widespread use, the theoretical understanding of its long-run behavior remains limited: existing analyses typically establish convergence in expectation or with high probability, but do not address the almost sure convergence of single trajectories. In this work, we prove that DP-SGD converges almost surely under standard smoothness assumptions, both in nonconvex and strongly convex settings, provided the step sizes satisfy some standard decaying conditions. Our analysis extends to momentum variants such as the stochastic heavy ball (DP-SHB) and Nesterov's accelerated gradient (DP-NAG), where we show that careful energy constructions yield similar guarantees. These results provide stronger theoretical foundations for differentially private optimization and suggest that, despite privacy-induced distortions, the algorithm remains pathwise stable in both convex and nonconvex regimes.

Related papers

• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  We study stopping rules for gradient descent (SGD) for convex optimization.<n>We develop an anytime-valid, data-dependent upper confidence sequence for the weighted average suboptimality of projected SGD.<n>These are the first rigorous, time-uniform performance guarantees and finitetime $varepsilon$-optimality certificates.
  arXiv  Detail & Related papers  (2025-12-15T09:26:45Z)
• On the Convergence of DP-SGD with Adaptive Clipping [56.24689348875711]
  Gradient Descent with gradient clipping is a powerful technique for enabling differentially private optimization.<n>This paper provides the first comprehensive convergence analysis of SGD with quantile clipping (QC-SGD)<n>We show how QC-SGD suffers from a bias problem similar to constant-threshold clipped SGD but can be mitigated through a carefully designed quantile and step size schedule.
  arXiv  Detail & Related papers  (2024-12-27T20:29:47Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  We prove new convergence rates for a generalized version of Nesterov acceleration underrho conditions.<n>Our analysis reduces the dependence on the strong growth constant from $$ to $sqrt$ as compared to prior work.
  arXiv  Detail & Related papers  (2024-04-03T00:41:19Z)
• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence [25.717501580080846]
  This paper revisits the convergence of gradient Forward Mirror (SMD) in the contemporary non optimization setting. For the training, we develop provably convergent algorithms for the problem of linear networks.
  arXiv  Detail & Related papers  (2024-02-27T17:56:49Z)
• Efficient Private SCO for Heavy-Tailed Data via Averaged Clipping [40.69950711262191]
  We consider differentially private convex optimization for heavy-tailed data with the guarantee of being differentially private (DP) We establish new convergence results and improved complexity bounds for the proposed algorithm called AClipped-dpSGD for constrained and unconstrained convex problems.
  arXiv  Detail & Related papers  (2022-06-27T01:39:15Z)
• Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics [2.9477900773805032]
  We show that the privacy loss converges exponentially fast for smooth and strongly convex objectives under constant step size. We propose an implementation and our experiments show the practical utility of our approach compared to classical DP-SGD libraries.
  arXiv  Detail & Related papers  (2022-01-28T08:21:31Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• A High Probability Analysis of Adaptive SGD with Momentum [22.9530287983179]
  Gradient Descent (DSG) and its variants are the most used algorithms in machine learning applications. We show for the first time the probability of the gradients to zero in smooth non setting for DelayedGrad with momentum.
  arXiv  Detail & Related papers  (2020-07-28T15:06:22Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)
• 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)
• Convergence rates and approximation results for SGD and its continuous-time counterpart [16.70533901524849]
  This paper proposes a thorough theoretical analysis of convex Gradient Descent (SGD) with non-increasing step sizes. First, we show that the SGD can be provably approximated by solutions of inhomogeneous Differential Equation (SDE) using coupling. Recent analyses of deterministic and optimization methods by their continuous counterpart, we study the long-time behavior of the continuous processes at hand and non-asymptotic bounds.
  arXiv  Detail & Related papers  (2020-04-08T18:31:34Z)

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.