Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods

Amartya Mukherjee, Jun Liu · 2025

Read Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods by Amartya Mukherjee, Jun Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-16587.txt.

Introduction

Amartya Mukherjee and Jun Liu strengthen the theory of differentially private stochastic gradient descent, the standard algorithm for training models with formal privacy guarantees. Most analyses show convergence on average or with high probability; what a single training run does in the long run was less clear.

The authors prove almost sure convergence of the method along individual trajectories, in both nonconvex and strongly convex settings, under standard smoothness assumptions and decaying step sizes. The analysis extends to private momentum methods, the stochastic heavy ball and Nesterov acceleration, using careful energy constructions. The results show that, despite the noise privacy injects, private training remains pathwise stable, giving practitioners a firmer foundation for relying on it.

Catalog record

CREATORAmartya Mukherjee, Jun Liu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-16587

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods Amartya Mukherjee, Jun Liu 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. I Introduction In the training of machine learning models, maintaining the privacy of training data is of paramount importance. Particularly in domains such as health and finance, it is important that an adversary cannot reconstruct training data from the trained models. Unfortunately, generative models risk overfitting to their training data, thus generating data indistinguishable from the training set and compromising the privacy of users. For example, the work of [ 3 ] reviews risks of leaking training data in image and text generation models. To protect the privacy of training data, a mathematically rigorous framework for privacy titled differential privacy (DP [ 5 ] ) has gained interest in recent years. Differentially private stochastic gradient descent (DP-SGD [ 1 ] ) is a modification of stochastic gradient descent (SGD) that offers privacy guarantees by introducing gradient clipping and noise injection. While DP guarantees strong privacy protection, it often comes at the cost of slower convergence and degraded model utility due to the bias induced by clipping and the noise injection. This paper will analyze the convergence rates of various DP-SGD methods under different noise injection schemes and dataset conditions. We explore how gradient clipping and noise scaling affect model performance. Since the advent of DP-SGD, its convergence analysis has been of interest to both the machine learning and control communities. Recent literature has focused on the optimization and generalization trade-offs introduced by differential privacy, but not on its almost-sure stability. For example, the work of [ 6 ] provides convergence analysis on a modified DP-SGD that replaces gradient clipping with an affine function of the gradient of the objective function. The authors of [ 15 ] extend the analysis to momentum-based variants and show that the additive Gaussian noise used for privacy can dominate the second-moment estimates in adaptive methods like Adam, effectively neutralizing their curvature adaptation and creating severe ill-conditioning under heavy-tailed data distributions. They demonstrate that bias-corrected DP-Adam (DP-AdamBC) mitigates this issue by subtracting the variance of the DP noise, improving convergence on imbalanced datasets. The comprehensive work of [ 9 ] derives convergence rates of SGD with clipping in deterministic and stochastic settings. Lastly, DP has also been studied in distributed optimization settings [ 7 ] , symbolic systems [ 2 ] , and multi-agent systems [ 8 ] . Overall, most existing analyses provide convergence guarantees only in expectation or with high probability, leaving open the question of whether individual trajectories stabilize. This gap is critical, since practical deployments of DP-SGD often train for many epochs under noisy, biased gradient updates introduced by clipping and Gaussian perturbation. Our paper builds upon these works by providing almost sure convergence guarantees for DP-SGD in convex and non-convex settings. We approach this by proving that a weighted average of the norm of the gradient of the objective function converges almost surely, and therefore that the best iterate converges. We extend our analysis further to variants of SGD that include momentum, where we also provide almost sure convergence guarantees of the last iterates. II Preliminaries and Assumptions We provide a formal definitions of DP and SGD, and introduce some assumptions commonly used in the convergence analysis of SGD [ 10 , 4 ] . Definition 1 (Differential Privacy (DP) [ 5 ] ) A randomized mechanism \mathcal{M}:\mathcal{D}\to\mathcal{R} with domain \mathcal{D} and range \mathcal{R} satisfies (\epsilon,\delta) differential privacy, where \epsilon>0,\delta>0 , if for any datasets d,d^{\prime}\subset\mathcal{D} differing by at most one entry, and for any subset of outputs S\subset\mathcal{R} , it holds that P(\mathcal{M}(d)\in S)\leq e^{\epsilon}P(\mathcal{M}(d^{\prime})\in S)+\delta. (1) Problem statement: We are interested in solving the following unconstrained minimization problem \min_{\mathbf{x}\in\mathbb{R}^{d}}f(\mathbf{x}), (2) where f:\mathbb{R}^{d}\to\mathbb{R} , using stochastic gradient methods that satisfy (\epsilon,\delta) -DP. Let f^{*} be the true minimum. In convex settings, we want to prove that f(\mathbf{x}_{t})-f^{*}\to 0 as t\to\infty . In non-convex settings, we want to prove that \nabla f(\mathbf{x}_{t})\to 0 as t\to\infty . Definition 2 (Stochastic Gradient Descent (SGD)) The iteration of SGD is given by \mathbf{x}_{t+1}=\mathbf{x}_{t}-\alpha_{t}\mathbf{g}_{t}, (3) where \mathbf{g}_{t}=\nabla f(\mathbf{x};\xi_{t}) is the stochastic gradient at \mathbf{x}_{t} with a random process \xi_{t} and \alpha_{t} is a step size. Throughout this paper, we denote \nabla f(\mathbf{x}_{t}):=\mathbb{E}[\mathbf{g}_{t}] as the expectation of the stochastic gradient over all \xi_{t} . Definition 3 (Differentially Private SGD (DP-SGD) [ 1 ] ) DP-SGD is a modification of SGD, where gradients are clipped and noise is added to the clipped gradients. \mathbf{x}_{t+1}=\mathbf{x}_{t}-\alpha_{t}\mathbf{g}_{t}^{DP}, (4) where the differentially private stochastic gradient \mathbf{g}_{t}^{DP} is given by \mathbf{g}_{t}^{DP}=\text{clip}_{q}(\nabla f(\mathbf{x}_{t};\xi_{t}))+q\zeta_{t}, (5) where the \text{clip}_{q} function is defined for q>0 by \text{clip}_{q}(\nabla f(\mathbf{x}_{t};\xi_{t}))=\min\left(1,\frac{q}{\|\nabla f(\mathbf{x}_{t};\xi_{t})\|}\right)\nabla f(\mathbf{x}_{t};\xi_{t}), (6) where \zeta_{t}\sim\mathcal{N}(0,\sigma_{DP}^{2}I) , and \|\cdot\| denotes the 2-norm. Remark 1 DP-SGD can be adapted to other stochastic gradient methods such as stochastic heavy ball and stochastic Nesterov accelerated gradient. A DP-SGD update satisfies (\epsilon,\delta) -DP if \sigma_{DP}^{2} and q satisfy \sigma_{DP}^{2}>2\log(1.25/\delta)q^{2}/\epsilon^{2} . Based on the formulation of DP-SGD, we also introduce the notion of clipping probability. Definition 4 (Clipping Probability) Define the process \eta_{t} as the clipping probability \eta_{t}=P(\|\nabla f(\mathbf{x}_{t},\xi_{t})\|>q|\mathbf{x}_{t}). (7) We make the following assumptions that are commonly used in the SGD literature [ 12 ] . Assumption 1 ( L -smoothness) f is bounded from below by f^{*}:=\inf_{\mathbf{x}\in\mathbb{R}^{d}}f(\mathbf{x}) and its gradient \nabla f is L -Lipschitz i.e. \|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\|\leq L\|\mathbf{x}-\mathbf{y}\| , for all \mathbf{x},\mathbf{y}\in\mathbb{R}^{d} . Assumption 2 ( \mu -strongly convex) There exists a positive constant \mu>0 such that f(\mathbf{y})\geq f(\mathbf{x})+\langle\nabla f(\mathbf{x}),\mathbf{y}-\mathbf{x}\rangle+\frac{\mu}{2}\|\mathbf{y}-\mathbf{x}\|^{2}, (8) for all \mathbf{x},\mathbf{y}\in\mathbb{R}^{d} A consequence of f being \mu -strongly convex is that \frac{1}{2\mu}\|\nabla f(\mathbf{x})\|^{2}\geq f(\mathbf{x})-f^{*}. (9) Assumption 3 (Directional Invariance) There exists a constant D>0 such that \mathbb{E}\left[\langle\nabla f(\mathbf{x}_{t}),\frac{\nabla f(\mathbf{x}_{t};\xi)}{\|\nabla f(\mathbf{x}_{t};\xi)\|}\rangle\mid\mathbf{x}_{t}\right]\geq D\|\nabla f(\mathbf{x}_{t})\| (10) holds whenever \nabla f(\mathbf{x}_{t})\neq 0 . Remark 2 This assumption essentially states that the direction of \nabla f(\mathbf{x};\xi) is preserved if we normalize it, and that the distribution of \nabla f(\mathbf{x};\xi) is not extremely skewed. III Background and Lemmas on Supermartingales The analysis in this paper follows from the following result derived in [ 14 ] . From this section onward, we use the shorthand notation \mathbb{E}_{t}[\cdot]:=\mathbb{E}[\cdot|\mathbf{x}_{t}] . Proposition 1 Let \{X_{t}\} , \{Y_{t}\} , and \{Z_{t}\} be three sequences of random variables that are adapted to a filtration \{\mathcal{F}_{t}\} . Let \{\gamma_{t}\} be a sequence of nonnegative real numbers such that \prod_{t=1}^{\infty}(1+\gamma_{t})<\infty . Suppose that the following conditions hold: 1. X_{t},Y_{t},Z_{t} are nonnegative for all t\geq 1 .

Read the complete text