Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise

# Almost Sure Convergence Analysis of Stochastic Gradient Methodswith Clipping and Additive Noise
Source: [https://arxiv.org/html/2609.12119](https://arxiv.org/html/2609.12119)
Jun Liu††thanks:Amartya Mukherjee and Jun Liu are with the Department of Applied Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 \(email:\(a29mukhe,j\.liu\)@uwaterloo\.ca\)\.

###### Abstract

Stochastic gradient descent \(SGD\) with gradient clipping and additive noise has become a standard technique for training machine learning models, particularly in applications requiring robustness or privacy guarantees\. However, clipping introduces a bias in stochastic gradients, while additive noise introduces additional variance, making the long\-run behaviour of individual optimization trajectories difficult to characterize\. In this work, we prove that SGD with clipping and additive Gaussian noise \(SGD\-CN\) converges almost surely \(a\.s\.\) under smoothness and uniformly bounded stochastic\-gradient noise assumptions, provided the step sizes satisfy some standard decaying conditions\. Our analysis extends to momentum variants such as the stochastic heavy ball and Nesterov’s accelerated gradient, where we show that careful energy constructions yield similar guarantees\. These results provide stronger theoretical foundations for understanding the pathwise behaviour of clipped stochastic gradient methods and suggest that, despite the bias and noise introduced by clipping and perturbation, the algorithm remains stable in both convex and nonconvex regimes\.

## IIntroduction

Gradient clipping is widely used in the training of machine learning models to control large stochastic gradients and improve numerical stability\. It also plays an important role in privacy\-preserving optimization, where clipping bounds the sensitivity of individual gradient contributions before random noise is added\[[5](https://arxiv.org/html/2609.12119#bib.bib4),[1](https://arxiv.org/html/2609.12119#bib.bib5)\]\. These considerations motivate stochastic gradient methods that combine gradient clipping with additive noise\. We refer to this class of methods as stochastic gradient descent with clipping and additive noise \(SGD\-CN\)\.

Despite its practical importance, clipping substantially changes the behaviour of stochastic gradient methods\. In particular, even when a stochastic gradient is an unbiased estimator of the true gradient, its clipped version need not remain unbiased\. The resulting bias can alter both the magnitude and direction of the expected update\. Additive Gaussian perturbations introduce a second difficulty, since individual iterates continue to receive random disturbances throughout training\. Correspondingly, standard convergence arguments for unbiased SGD do not directly apply to SGD\-CN\.

The convergence behaviour of gradient clipping has received significant attention in recent years\. Several works analyze clipped stochastic gradient methods under assumptions on the stochastic\-gradient noise or on the geometry of the clipping operation\. Of particular relevance,\[[9](https://arxiv.org/html/2609.12119#bib.bib10)\]characterizes the stochastic bias introduced by gradient clipping and shows that, under a standard bounded\-variance assumption alone, clipped SGD need not converge to an exact stationary point\. Instead, the clipping bias can produce a nonvanishing neighborhood whose size depends on the stochastic\-gradient variance and the clipping threshold\. This observation highlights that additional structure on the stochastic\-gradient oracle is required for exact convergence with a fixed clipping threshold\. Related analyses of gradient clipping and privacy\-preserving stochastic optimization include\[[6](https://arxiv.org/html/2609.12119#bib.bib9),[15](https://arxiv.org/html/2609.12119#bib.bib11)\], while differentially private optimization has also been studied in distributed and multi\-agent settings\[[7](https://arxiv.org/html/2609.12119#bib.bib13),[3](https://arxiv.org/html/2609.12119#bib.bib14),[8](https://arxiv.org/html/2609.12119#bib.bib15)\]\.

In this work, we study the almost sure convergence of SGD\-CN under a uniformly bounded stochastic\-gradient noise assumption\. Specifically, we assume that the objective is smooth and that the stochastic\-gradient noise is uniformly bounded\. We show that, although clipping biases the stochastic gradient, its conditional mean remains a descent direction provided that the clipping threshold is sufficiently large relative to the stochastic\-gradient noise\. Our convergence analysis builds on this observation\. For SGD\-CN and its momentum variants, we establish almost sure weighted summability of a clipping\-aware stationarity measure, from which best\-iterate convergence rates follow\. We then strengthen these results to last\-iterate convergence by controlling the oscillations of the gradient norm\.

## IIPreliminaries and Assumptions

We provide formal definitions and introduce some assumptions commonly used in the convergence analysis of SGD\[[10](https://arxiv.org/html/2609.12119#bib.bib1),[4](https://arxiv.org/html/2609.12119#bib.bib12)\]\.

Problem statement:We are interested in solving the following unconstrained minimization problem

min𝐱∈ℝd⁡f⁡\(𝐱\),\\min\_\{\\mathbf\{x\}\\in\\mathbb\{R\}^\{d\}\}f\(\\mathbf\{x\}\),\(1\)wheref:ℝd→ℝf:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}, using stochastic gradient methods with clipping and additive noise\. Letf∗f^\{\*\}be the true minimum\. In convex settings, we want to prove thatf⁡\(𝐱t\)−f∗→0f\(\\mathbf\{x\}\_\{t\}\)\-f^\{\*\}\\to 0ast→∞t\\to\\infty\. In nonconvex settings, we want to prove that∇f​\(𝐱t\)→0\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\to 0ast→∞t\\to\\infty\.

###### Definition 1\(Stochastic Gradient Descent \(SGD\)\)

The iteration of SGD is given by

𝐱t\+1=𝐱t−αt​𝐠t,\\mathbf\{x\}\_\{t\+1\}=\\mathbf\{x\}\_\{t\}\-\\alpha\_\{t\}\\mathbf\{g\}\_\{t\},\(2\)where𝐠t=∇f​\(𝐱t,ξt\)\\mathbf\{g\}\_\{t\}=\\nabla f\(\\mathbf\{x\}\_\{t\};\\xi\_\{t\}\)is the stochastic gradient at𝐱t\\mathbf\{x\}\_\{t\}with a random processξt\\xi\_\{t\}andαt\\alpha\_\{t\}is a step size\. Throughout this paper, we assume the stochastic gradient is unbiased and denote𝔼t​\[𝐠t\]=∇f​\(𝐱t\)\\mathbb\{E\}\_\{t\}\[\\mathbf\{g\}\_\{t\}\]=\\nabla f\(\\mathbf\{x\}\_\{t\}\)as the true gradient\.

###### Definition 2\(SGD with Clipping and Additive Noise\[[1](https://arxiv.org/html/2609.12119#bib.bib5)\]\)

SGD\-CN is a modification of SGD, where gradients are clipped and noise is added to the clipped gradients\.

𝐱t\+1=𝐱t−αt​𝐠tC​N,\\mathbf\{x\}\_\{t\+1\}=\\mathbf\{x\}\_\{t\}\-\\alpha\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\},\(3\)where the clipped noisy stochastic gradient𝐠tC​N\\mathbf\{g\}\_\{t\}^\{CN\}is given by

𝐠tC​N=clipq​\(∇f​\(𝐱t,ξt\)\)\+q​ζt,\\mathbf\{g\}\_\{t\}^\{CN\}=\\text\{clip\}\_\{q\}\(\\nabla f\(\\mathbf\{x\}\_\{t\};\\xi\_\{t\}\)\)\+q\\zeta\_\{t\},\(4\)where theclipq\\text\{clip\}\_\{q\}function is defined forq\>0q\>0by

clipq\(∇f\(𝐱t;ξt\)\)=min\(1,q‖∇f​\(𝐱t,ξt\)‖\)∇f\(𝐱t;ξt\),\\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\}\),\(5\)whereζt∼𝒩⁡\(0,σC​N2​I\)\\zeta\_\{t\}\\sim\\mathcal\{N\}\(0,\\sigma\_\{CN\}^\{2\}I\)is independent zero\-mean Gaussian noise with varianceσC​N2\\sigma\_\{CN\}^\{2\}

We make the following assumptions that are commonly used in the SGD literature\[[12](https://arxiv.org/html/2609.12119#bib.bib2)\]\.

###### Assumption 1\(LL\-smoothness\)

ffis bounded from below byf∗:=min𝐱∈ℝd⁡f⁡\(𝐱\)f^\{\*\}:=\\min\_\{\\mathbf\{x\}\\in\\mathbb\{R\}^\{d\}\}f\(\\mathbf\{x\}\)and its gradient∇f\\nabla fisLL\-Lipschitz i\.e\.

‖∇f​\(𝐱\)−∇f​\(𝐲\)‖≤L​‖𝐱−𝐲‖,\\\|\\nabla f\(\\mathbf\{x\}\)\-\\nabla f\(\\mathbf\{y\}\)\\\|\\leq L\\\|\\mathbf\{x\}\-\\mathbf\{y\}\\\|,\(6\)for all𝐱,𝐲∈ℝd\\mathbf\{x\},\\mathbf\{y\}\\in\\mathbb\{R\}^\{d\}\.

###### Assumption 2\(μ\\mu\-strongly convex\)

There exists a positive constantμ\>0\\mu\>0such that

f⁡\(𝐲\)≥f⁡\(𝐱\)\+⟨∇f​\(𝐱\),𝐲−𝐱⟩\+μ2​‖𝐲−𝐱‖2,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\},\(7\)for all𝐱,𝐲∈ℝd\\mathbf\{x\},\\mathbf\{y\}\\in\\mathbb\{R\}^\{d\}A consequence offfbeingμ\\mu\-strongly convex is that

12​μ​‖∇f​\(𝐱\)‖2≥f⁡\(𝐱\)−f∗\.\\frac\{1\}\{2\\mu\}\\\|\\nabla f\(\\mathbf\{x\}\)\\\|^\{2\}\\geq f\(\\mathbf\{x\}\)\-f^\{\*\}\.\(8\)

We impose the following standard bounded\-noise assumption on the stochastic gradient oracle\.

###### Assumption 3\(Uniformly Bounded Stochastic Gradient Noise\)

There exists a constantσg≥0\\sigma\_\{g\}\\geq 0such that

‖∇f​\(𝐱,ξ\)−∇f​\(𝐱\)‖≤σga\.s\.\\left\\\|\\nabla f\(\\mathbf\{x\};\\xi\)\-\\nabla f\(\\mathbf\{x\}\)\\right\\\|\\leq\\sigma\_\{g\}\\quad\\text\{a\.s\.\}\(9\)for every𝐱∈ℝd\\mathbf\{x\}\\in\\mathbb\{R\}^\{d\}\.

## IIIBackground and Lemmas on Supermartingales

The analysis in this paper follows from the following result derived in\[[14](https://arxiv.org/html/2609.12119#bib.bib3)\]\. Throughout the remainder of the paper, we use the shorthand notation𝔼t\[⋅\]:=𝔼t\[⋅\|ℱt\]\\mathbb\{E\}\_\{t\}\[\\cdot\]:=\\mathbb\{E\}\_\{t\}\[\\cdot\|\\mathcal\{F\}\_\{t\}\], whereℱt\\mathcal\{F\}\_\{t\}is the natural filtration\.

###### Proposition 1

Let\{Xt\}\\\{X\_\{t\}\\\},\{Yt\}\\\{Y\_\{t\}\\\}, and\{Zt\}\\\{Z\_\{t\}\\\}be three sequences of random variables that are adapted to a filtration\{ℱt\}\\\{\\mathcal\{F\}\_\{t\}\\\}\. Let\{γt\}\\\{\\gamma\_\{t\}\\\}be a sequence of nonnegative real numbers such that∏t=1∞\(1\+γt\)<∞\\prod\_\{t=1\}^\{\\infty\}\(1\+\\gamma\_\{t\}\)<\\infty\. Suppose that the following conditions hold:

1. 1\.Xt,Yt,ZtX\_\{t\},Y\_\{t\},Z\_\{t\}are nonnegative for allt≥1t\\geq 1\.
2. 2\.𝔼⁡\[Yt\+1\|ℱt\]≤\(1\+γt\)​Yt−Xt\+Zt\\mathbb\{E\}\[Y\_\{t\+1\}\|\\mathcal\{F\}\_\{t\}\]\\leq\(1\+\\gamma\_\{t\}\)Y\_\{t\}\-X\_\{t\}\+Z\_\{t\}for allt≥1t\\geq 1\.
3. 3\.∑t=1∞Zt<∞\\sum\_\{t=1\}^\{\\infty\}Z\_\{t\}<\\inftyholds a\.s\.

Then, we have

∑t=1∞Xt<∞a\.s\.,\\sum\_\{t=1\}^\{\\infty\}X\_\{t\}<\\infty\\quad\\text\{a\.s\.,\}\(10\)andYtY\_\{t\}converges a\.s\.

The following result from\[[10](https://arxiv.org/html/2609.12119#bib.bib1)\]is used for convergence results in nonconvex settings\.

###### Lemma 1\(Lemma 2 of\[[10](https://arxiv.org/html/2609.12119#bib.bib1)\]\)

Let\{Xt\}\\\{X\_\{t\}\\\}be a sequence of nonnegative real numbers and\{αt\}\\\{\\alpha\_\{t\}\\\}be a decreasing sequence of positive real numbers such that the following conditions hold:

∑t=1∞αt​Xt<∞,∑t=1∞αt∑i=1t−1αi=∞\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}X\_\{t\}<\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\frac\{\\alpha\_\{t\}\}\{\\sum\_\{i=1\}^\{t\-1\}\\alpha\_\{i\}\}=\\infty\.\(11\)Then,

min1≤i≤t⁡Xi=o⁡\(1∑i=1t−1αi\)\.\\min\_\{1\\leq i\\leq t\}X\_\{i\}=o\\left\(\\frac\{1\}\{\\sum\_\{i=1\}^\{t\-1\}\\alpha\_\{i\}\}\\right\)\.\(12\)

We derive some properties of the clipped noisy stochastic gradient that aid our analysis\.

###### Proposition 2\(Expected Clipped\-Gradient Alignment\)

Suppose Assumption[3](https://arxiv.org/html/2609.12119#Thmassumption3)holds and define

Ψq​\(r\):=min⁡\{r2,q​r\},r≥0\.\\Psi\_\{q\}\(r\):=\\min\\\{r^\{2\},qr\\\},\\quad r\\geq 0\.\(13\)Then, for every𝐱∈ℝd\\mathbf\{x\}\\in\\mathbb\{R\}^\{d\},

⟨∇f​\(𝐱\),𝔼t​\[clipq⁡\(∇f​\(𝐱,ξ\)\)\|𝐱\]⟩\\displaystyle\\left\\langle\\nabla f\(\\mathbf\{x\}\),\\mathbb\{E\}\_\{t\}\\left\[\\operatorname\{clip\}\_\{q\}\(\\nabla f\(\\mathbf\{x\};\\xi\)\)\|\\mathbf\{x\}\\right\]\\right\\rangle≥‖∇f​\(𝐱\)‖2−‖∇f​\(𝐱\)‖​\(‖∇f​\(𝐱\)‖\+σg−q\)\+\.\\displaystyle\\quad\\geq\\\|\\nabla f\(\\mathbf\{x\}\)\\\|^\{2\}\-\\\|\\nabla f\(\\mathbf\{x\}\)\\\|\\left\(\\\|\\nabla f\(\\mathbf\{x\}\)\\\|\+\\sigma\_\{g\}\-q\\right\)\_\{\+\}\.\(14\)In particular, ifq\>σgq\>\\sigma\_\{g\}, then

⟨∇f​\(𝐱\),𝔼t​\[clipq⁡\(∇f​\(𝐱,ξ\)\)\|𝐱\]⟩≥\(1−σgq\)​Ψq​\(‖∇f​\(𝐱\)‖\)\.\\left\\langle\\nabla f\(\\mathbf\{x\}\),\\mathbb\{E\}\_\{t\}\\left\[\\operatorname\{clip\}\_\{q\}\(\\nabla f\(\\mathbf\{x\};\\xi\)\)\|\\mathbf\{x\}\\right\]\\right\\rangle\\geq\\left\(1\-\\frac\{\\sigma\_\{g\}\}\{q\}\\right\)\\Psi\_\{q\}\\left\(\\\|\\nabla f\(\\mathbf\{x\}\)\\\|\\right\)\.\(15\)

###### Proof:

Fix𝐱∈ℝd\\mathbf\{x\}\\in\\mathbb\{R\}^\{d\}and write

𝐠:=∇f​\(𝐱\),𝐠ξ:=∇f​\(𝐱,ξ\),r:=‖𝐠‖\.\\mathbf\{g\}:=\\nabla f\(\\mathbf\{x\}\),\\quad\\mathbf\{g\}\_\{\\xi\}:=\\nabla f\(\\mathbf\{x\};\\xi\),\\quad r:=\\\|\\mathbf\{g\}\\\|\.Define𝐡ξ:=clipq⁡\(𝐠ξ\)\\mathbf\{h\}\_\{\\xi\}:=\\operatorname\{clip\}\_\{q\}\(\\mathbf\{g\}\_\{\\xi\}\)\. By conditional unbiasedness,𝔼t​\[𝐠ξ\|𝐱\]=𝐠\\mathbb\{E\}\_\{t\}\[\\mathbf\{g\}\_\{\\xi\}\|\\mathbf\{x\}\]=\\mathbf\{g\}, and hence

⟨𝐠,𝔼t​\[𝐡ξ\|𝐱\]⟩\\displaystyle\\left\\langle\\mathbf\{g\},\\mathbb\{E\}\_\{t\}\[\\mathbf\{h\}\_\{\\xi\}\|\\mathbf\{x\}\]\\right\\rangle=⟨𝐠,𝔼t​\[𝐠ξ\|𝐱\]⟩−⟨𝐠,𝔼t​\[𝐠ξ−𝐡ξ\|𝐱\]⟩\\displaystyle=\\left\\langle\\mathbf\{g\},\\mathbb\{E\}\_\{t\}\[\\mathbf\{g\}\_\{\\xi\}\|\\mathbf\{x\}\]\\right\\rangle\-\\left\\langle\\mathbf\{g\},\\mathbb\{E\}\_\{t\}\[\\mathbf\{g\}\_\{\\xi\}\-\\mathbf\{h\}\_\{\\xi\}\|\\mathbf\{x\}\]\\right\\rangle=r2−⟨𝐠,𝔼t​\[𝐠ξ−𝐡ξ\|𝐱\]⟩\\displaystyle=r^\{2\}\-\\left\\langle\\mathbf\{g\},\\mathbb\{E\}\_\{t\}\[\\mathbf\{g\}\_\{\\xi\}\-\\mathbf\{h\}\_\{\\xi\}\|\\mathbf\{x\}\]\\right\\rangle≥r2−r​𝔼t​\[‖𝐠ξ−𝐡ξ‖\|𝐱\]\.\\displaystyle\\geq r^\{2\}\-r\\,\\mathbb\{E\}\_\{t\}\[\\\|\\mathbf\{g\}\_\{\\xi\}\-\\mathbf\{h\}\_\{\\xi\}\\\|\|\\mathbf\{x\}\]\.\(16\)By the definition of the clipping operator,

‖𝐠ξ−𝐡ξ‖=\(‖𝐠ξ‖−q\)\+\.\\\|\\mathbf\{g\}\_\{\\xi\}\-\\mathbf\{h\}\_\{\\xi\}\\\|=\\left\(\\\|\\mathbf\{g\}\_\{\\xi\}\\\|\-q\\right\)\_\{\+\}\.Assumption[3](https://arxiv.org/html/2609.12119#Thmassumption3)further gives

‖𝐠ξ‖≤‖𝐠‖\+‖𝐠ξ−𝐠‖≤r\+σga\.s\.\\\|\\mathbf\{g\}\_\{\\xi\}\\\|\\leq\\\|\\mathbf\{g\}\\\|\+\\\|\\mathbf\{g\}\_\{\\xi\}\-\\mathbf\{g\}\\\|\\leq r\+\\sigma\_\{g\}\\quad\\text\{a\.s\.\}Therefore,

‖𝐠ξ−𝐡ξ‖≤\(r\+σg−q\)\+a\.s\.\\\|\\mathbf\{g\}\_\{\\xi\}\-\\mathbf\{h\}\_\{\\xi\}\\\|\\leq\(r\+\\sigma\_\{g\}\-q\)\_\{\+\}\\quad\\text\{a\.s\.\}Substituting this into \([16](https://arxiv.org/html/2609.12119#S3.E16)\) yields

⟨𝐠,𝔼t​\[𝐡ξ\|𝐱\]⟩≥r2−r​\(r\+σg−q\)\+,\\left\\langle\\mathbf\{g\},\\mathbb\{E\}\_\{t\}\[\\mathbf\{h\}\_\{\\xi\}\|\\mathbf\{x\}\]\\right\\rangle\\geq r^\{2\}\-r\(r\+\\sigma\_\{g\}\-q\)\_\{\+\},proving \([14](https://arxiv.org/html/2609.12119#S3.E14)\)\. Now supposeq\>σgq\>\\sigma\_\{g\}\. Ifr\+σg≤qr\+\\sigma\_\{g\}\\leq q, then

⟨𝐠,𝔼t​\[𝐡ξ\|𝐱\]⟩≥r2≥\(1−σgq\)​Ψq​\(r\)\.\\left\\langle\\mathbf\{g\},\\mathbb\{E\}\_\{t\}\[\\mathbf\{h\}\_\{\\xi\}\|\\mathbf\{x\}\]\\right\\rangle\\geq r^\{2\}\\geq\\left\(1\-\\frac\{\\sigma\_\{g\}\}\{q\}\\right\)\\Psi\_\{q\}\(r\)\.Otherwise,r\+σg\>qr\+\\sigma\_\{g\}\>q, and

r2−r⁡\(r\+σg−q\)=r⁡\(q−σg\)\.r^\{2\}\-r\(r\+\\sigma\_\{g\}\-q\)=r\(q\-\\sigma\_\{g\}\)\.Ifr≤qr\\leq q, then

r⁡\(q−σg\)≥\(1−σgq\)​r2,r\(q\-\\sigma\_\{g\}\)\\geq\\left\(1\-\\frac\{\\sigma\_\{g\}\}\{q\}\\right\)r^\{2\},whereas ifr\>qr\>q, then

r⁡\(q−σg\)=\(1−σgq\)​q​r\.r\(q\-\\sigma\_\{g\}\)=\\left\(1\-\\frac\{\\sigma\_\{g\}\}\{q\}\\right\)qr\.SinceΨq​\(r\)=min⁡\{r2,q​r\}\\Psi\_\{q\}\(r\)=\\min\\\{r^\{2\},qr\\\}, the desired result follows\. ∎

## IVAlmost Sure Convergence Rate Analysis

In this section, we establish almost sure convergence rates for SGD\-CN and its stochastic heavy\-ball extension\. Our analysis is based on the expected clipped\-gradient alignment derived in Proposition[2](https://arxiv.org/html/2609.12119#Thmproposition2)\.

Throughout this section, defineΨq​\(⋅\)\\Psi\_\{q\}\(\\cdot\)as in \([13](https://arxiv.org/html/2609.12119#S3.E13)\)\. Under Assumption[3](https://arxiv.org/html/2609.12119#Thmassumption3), ifq\>σgq\>\\sigma\_\{g\}, Proposition[2](https://arxiv.org/html/2609.12119#Thmproposition2)gives

⟨∇f​\(𝐱\),𝔼⁡\[clipq⁡\(∇f​\(𝐱,ξ\)\)∣𝐱\]⟩≥κq​Ψq​\(‖∇f​\(𝐱\)‖\),\\left\\langle\\nabla f\(\\mathbf\{x\}\),\\mathbb\{E\}\\left\[\\operatorname\{clip\}\_\{q\}\(\\nabla f\(\\mathbf\{x\};\\xi\)\)\\mid\\mathbf\{x\}\\right\]\\right\\rangle\\geq\\kappa\_\{q\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\)\\\|\),\(18\)whereκq:=1−σgq\>0\\kappa\_\{q\}:=1\-\\frac\{\\sigma\_\{g\}\}\{q\}\>0\. Since𝔼t​\[ζt\]=0\\mathbb\{E\}\_\{t\}\[\\zeta\_\{t\}\]=0, \([18](https://arxiv.org/html/2609.12119#S4.E18)\) implies

𝔼t​\[⟨∇f​\(𝐱t\),𝐠tC​N⟩\]≥κq​Ψq​\(‖∇f​\(𝐱t\)‖\)\.\\mathbb\{E\}\_\{t\}\\left\[\\langle\\nabla f\(\\mathbf\{x\}\_\{t\}\),\\mathbf\{g\}\_\{t\}^\{CN\}\\rangle\\right\]\\geq\\kappa\_\{q\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\.\(19\)Moreover,

𝔼t​‖𝐠tC​N‖2\\displaystyle\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{g\}\_\{t\}^\{CN\}\\\|^\{2\}=𝔼t​‖clipq⁡\(∇f​\(𝐱t,ξt\)\)‖2\+q2​𝔼t​‖ζt‖2\\displaystyle=\\mathbb\{E\}\_\{t\}\\left\\\|\\operatorname\{clip\}\_\{q\}\(\\nabla f\(\\mathbf\{x\}\_\{t\};\\xi\_\{t\}\)\)\\right\\\|^\{2\}\+q^\{2\}\\mathbb\{E\}\_\{t\}\\\|\\zeta\_\{t\}\\\|^\{2\}≤q2\+q2​d​σC​N2=:Q2\.\\displaystyle\\leq q^\{2\}\+q^\{2\}d\\sigma\_\{CN\}^\{2\}=:Q^\{2\}\.\(20\)
We consider positive, nonincreasing step sizes satisfying

αt=Θ⁡\(1t1−θ\),θ∈\(0,12\)\.\\alpha\_\{t\}=\\Theta\\left\(\\frac\{1\}\{t^\{1\-\\theta\}\}\\right\),\\quad\\theta\\in\\left\(0,\\frac\{1\}\{2\}\\right\)\.\(21\)In particular,

∑t=1∞αt=∞,∑t=1∞αt2<∞,∑i=1tαi=Θ⁡\(tθ\)\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}=\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{2\}<\\infty,\\quad\\sum\_\{i=1\}^\{t\}\\alpha\_\{i\}=\\Theta\(t^\{\\theta\}\)\.
### IV\-AStochastic Gradient Descent

We prove that, under smoothness and bounded noise assumptions, SGD\-CN can achieve almost sure convergence\.

###### Theorem 1\(Convergence of SGD\-CN\)

Consider the iterates of SGD\-CN in \([3](https://arxiv.org/html/2609.12119#S2.E3)\)\. Suppose Assumptions[1](https://arxiv.org/html/2609.12119#Thmassumption1)and[3](https://arxiv.org/html/2609.12119#Thmassumption3)hold, letq\>σgq\>\\sigma\_\{g\}, and suppose that the step sizes satisfy \([21](https://arxiv.org/html/2609.12119#S4.E21)\)\. Then

∑t=1∞αt​Ψq​\(‖∇f​\(𝐱t\)‖\)<∞a\.s\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)<\\infty\\quad\\text\{a\.s\.\}\(22\)andf⁡\(𝐱t\)f\(\\mathbf\{x\}\_\{t\}\)converges almost surely to a finite random variable\. Furthermore,

min1≤i≤t⁡Ψq​\(‖∇f​\(𝐱i\)‖\)=o⁡\(\(∑i=1t−1αi\)−1\)=o⁡\(t−θ\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|\)=o\\left\(\\left\(\\sum\_\{i=1\}^\{t\-1\}\\alpha\_\{i\}\\right\)^\{\-1\}\\right\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\}\(23\)and hence,

min1≤i≤t∥∇f\(𝐱i\)∥=o\(t−θ/2\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|=o\(t^\{\-\\theta/2\}\)\\quad\\text\{a\.s\.\}\(24\)If, in addition, Assumption[2](https://arxiv.org/html/2609.12119#Thmassumption2)holds, then

min1≤i≤t⁡\(f⁡\(𝐱i\)−f∗\)=o⁡\(t−θ\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\bigl\(f\(\\mathbf\{x\}\_\{i\}\)\-f^\{\*\}\\bigr\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\}\(25\)

###### Proof:

ByLL\-smoothness,

f⁡\(𝐱t\+1\)≤\\displaystyle f\(\\mathbf\{x\}\_\{t\+1\}\)\\leq\\;f⁡\(𝐱t\)−αt​⟨∇f​\(𝐱t\),𝐠tC​N⟩\+L​αt22​‖𝐠tC​N‖2\.\\displaystyle f\(\\mathbf\{x\}\_\{t\}\)\-\\alpha\_\{t\}\\langle\\nabla f\(\\mathbf\{x\}\_\{t\}\),\\mathbf\{g\}\_\{t\}^\{CN\}\\rangle\+\\frac\{L\\alpha\_\{t\}^\{2\}\}\{2\}\\\|\\mathbf\{g\}\_\{t\}^\{CN\}\\\|^\{2\}\.Taking conditional expectation and applying \([19](https://arxiv.org/html/2609.12119#S4.E19)\) and \([20](https://arxiv.org/html/2609.12119#S4.E20)\) yields

𝔼t​\[f⁡\(𝐱t\+1\)−f∗\]≤\\displaystyle\\mathbb\{E\}\_\{t\}\[f\(\\mathbf\{x\}\_\{t\+1\}\)\-f^\{\*\}\]\\leq\\;f⁡\(𝐱t\)−f∗\\displaystyle f\(\\mathbf\{x\}\_\{t\}\)\-f^\{\*\}−κq​αt​Ψq​\(‖∇f​\(𝐱t\)‖\)\+L​Q22​αt2\.\\displaystyle\-\\kappa\_\{q\}\\alpha\_\{t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\+\\frac\{LQ^\{2\}\}\{2\}\\alpha\_\{t\}^\{2\}\.
We apply Proposition[1](https://arxiv.org/html/2609.12119#Thmproposition1)with

Yt:=f⁡\(𝐱t\)−f∗,Xt:=κq​αt​Ψq​\(‖∇f​\(𝐱t\)‖\),Zt:=L​Q22​αt2\.Y\_\{t\}:=f\(\\mathbf\{x\}\_\{t\}\)\-f^\{\*\},\\quad X\_\{t\}:=\\kappa\_\{q\}\\alpha\_\{t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\),\\quad Z\_\{t\}:=\\frac\{LQ^\{2\}\}\{2\}\\alpha\_\{t\}^\{2\}\.SinceYt,Xt,Zt≥0Y\_\{t\},X\_\{t\},Z\_\{t\}\\geq 0and∑tαt2<∞\\sum\_\{t\}\\alpha\_\{t\}^\{2\}<\\infty, Proposition[1](https://arxiv.org/html/2609.12119#Thmproposition1)implies thatf⁡\(𝐱t\)−f∗f\(\\mathbf\{x\}\_\{t\}\)\-f^\{\*\}converges almost surely and

∑t=1∞αt​Ψq​\(‖∇f​\(𝐱t\)‖\)<∞a\.s\.,\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)<\\infty\\quad\\text\{a\.s\.\},proving \([22](https://arxiv.org/html/2609.12119#S4.E22)\)\. We next apply Lemma[1](https://arxiv.org/html/2609.12119#Thmlemma1)pathwise with

Xt=Ψq​\(‖∇f​\(𝐱t\)‖\)\.X\_\{t\}=\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\.The step\-size conditions required by the lemma hold because\{αt\}\\\{\\alpha\_\{t\}\\\}is positive and nonincreasing, and

αt​∑i=1t−1αi=Θ⁡\(t−1\+2​θ\),\\alpha\_\{t\}\\sum\_\{i=1\}^\{t\-1\}\\alpha\_\{i\}=\\Theta\(t^\{\-1\+2\\theta\}\),whose sum diverges for everyθ\>0\\theta\>0\. Therefore,

min1≤i≤t⁡Ψq​\(‖∇f​\(𝐱i\)‖\)=o⁡\(\(∑i=1t−1αi\)−1\)=o⁡\(t−θ\),\\min\_\{1\\leq i\\leq t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|\)=o\\left\(\\left\(\\sum\_\{i=1\}^\{t\-1\}\\alpha\_\{i\}\\right\)^\{\-1\}\\right\)=o\(t^\{\-\\theta\}\),almost surely\.

To obtain the gradient\-norm rate, define

rt∗:=min1≤i≤t⁡‖∇f​\(𝐱i\)‖\.r\_\{t\}^\{\*\}:=\\min\_\{1\\leq i\\leq t\}\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|\.SinceΨq\\Psi\_\{q\}is nondecreasing,

Ψq​\(rt∗\)=min1≤i≤t⁡Ψq​\(‖∇f​\(𝐱i\)‖\)→0\.\\Psi\_\{q\}\(r\_\{t\}^\{\*\}\)=\\min\_\{1\\leq i\\leq t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|\)\\to 0\.Hencert∗→0r\_\{t\}^\{\*\}\\to 0, and for all sufficiently largett,rt∗≤qr\_\{t\}^\{\*\}\\leq q\. ThereforeΨq​\(rt∗\)=\(rt∗\)2\\Psi\_\{q\}\(r\_\{t\}^\{\*\}\)=\(r\_\{t\}^\{\*\}\)^\{2\}, which together with \([23](https://arxiv.org/html/2609.12119#S4.E23)\) gives

rt∗=o\(t−θ/2\)a\.s\.r\_\{t\}^\{\*\}=o\(t^\{\-\\theta/2\}\)\\quad\\text\{a\.s\.\}
Finally, supposeffisμ\\mu\-strongly convex\. Then, as a result of Assumption[2](https://arxiv.org/html/2609.12119#Thmassumption2),

Ψq​\(‖∇f​\(𝐱t\)‖\)\\displaystyle\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)≥Ψq​\(2​μ​\(f⁡\(𝐱t\)−f∗\)\)\\displaystyle\\geq\\Psi\_\{q\}\\left\(\\sqrt\{2\\mu\(f\(\\mathbf\{x\}\_\{t\}\)\-f^\{\*\}\)\}\\right\)=min⁡\{2​μ​\(f⁡\(𝐱t\)−f∗\),q​2​μ​\(f⁡\(𝐱t\)−f∗\)\}\.\\displaystyle=\\min\\left\\\{2\\mu\(f\(\\mathbf\{x\}\_\{t\}\)\-f^\{\*\}\),q\\sqrt\{2\\mu\(f\(\\mathbf\{x\}\_\{t\}\)\-f^\{\*\}\)\}\\right\\\}\.Applying Lemma[1](https://arxiv.org/html/2609.12119#Thmlemma1)to the right\-hand side shows that its best\-iterate value iso⁡\(t−θ\)o\(t^\{\-\\theta\}\)almost surely\. Since this quantity converges to zero, its first branch eventually applies to the best iterate, and hence

min1≤i≤t⁡\(f⁡\(𝐱i\)−f∗\)=o⁡\(t−θ\)a\.s\.\\min\_\{1\\leq i\\leq t\}\(f\(\\mathbf\{x\}\_\{i\}\)\-f^\{\*\}\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\}This completes the proof\. ∎

### IV\-BStochastic Heavy\-Ball Method

The clipped noisy stochastic heavy\-ball method is given by

𝐱t\+1=𝐱t−αt​𝐠tC​N\+β⁡\(𝐱t−𝐱t−1\),β∈\[0,1\)\.\\mathbf\{x\}\_\{t\+1\}=\\mathbf\{x\}\_\{t\}\-\\alpha\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\+\\beta\(\\mathbf\{x\}\_\{t\}\-\\mathbf\{x\}\_\{t\-1\}\),\\quad\\beta\\in\[0,1\)\.\(26\)Define

𝐯t:=𝐱t−𝐱t−1,𝐳t:=𝐱t\+β1−β​𝐯t\.\\mathbf\{v\}\_\{t\}:=\\mathbf\{x\}\_\{t\}\-\\mathbf\{x\}\_\{t\-1\},\\quad\\mathbf\{z\}\_\{t\}:=\\mathbf\{x\}\_\{t\}\+\\frac\{\\beta\}\{1\-\\beta\}\\mathbf\{v\}\_\{t\}\.\(27\)Then the SHB\-CN iteration can be equivalently written as

𝐯t\+1=β​𝐯t−αt​𝐠tC​N,𝐳t\+1=𝐳t−αt′𝐠tC​N,αt′:=αt1−β\.\\begin\{split\}\\mathbf\{v\}\_\{t\+1\}&=\\beta\\mathbf\{v\}\_\{t\}\-\\alpha\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\},\\\\ \\mathbf\{z\}\_\{t\+1\}&=\\mathbf\{z\}\_\{t\}\-\\alpha\_\{t\}^\{\\prime\}\\mathbf\{g\}\_\{t\}^\{CN\},\\quad\\alpha\_\{t\}^\{\\prime\}:=\\frac\{\\alpha\_\{t\}\}\{1\-\\beta\}\.\\end\{split\}\(28\)This transformation is standard in the analysis of stochastic heavy\-ball methods\[[11](https://arxiv.org/html/2609.12119#bib.bib8)\]\.

###### Theorem 2\(Convergence of SHB\-CN\)

Consider the iterates of SHB\-CN in \([26](https://arxiv.org/html/2609.12119#S4.E26)\), withβ∈\[0,1\)\\beta\\in\[0,1\)\. Suppose Assumptions[1](https://arxiv.org/html/2609.12119#Thmassumption1)and[3](https://arxiv.org/html/2609.12119#Thmassumption3)hold, letq\>σgq\>\\sigma\_\{g\}, and suppose that the step sizes satisfy \([21](https://arxiv.org/html/2609.12119#S4.E21)\)\. Then

∑t=1∞αt​Ψq​\(‖∇f​\(𝐱t\)‖\)\\displaystyle\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)<∞,∑t=1∞‖𝐯t‖2<∞\\displaystyle<\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}<\\infty\(29\)almost surely\. In particular,

∥𝐯t∥→0,∥𝐳t−𝐱t∥→0a\.s\.\\\|\\mathbf\{v\}\_\{t\}\\\|\\to 0,\\quad\\\|\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\\|\\to 0\\quad\\text\{a\.s\.\}\(30\)Moreover,

min1≤i≤t⁡Ψq​\(‖∇f​\(𝐱i\)‖\)=o⁡\(t−θ\)a\.s\.,\\min\_\{1\\leq i\\leq t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\},\(31\)and thus,

min1≤i≤t∥∇f\(𝐱i\)∥=o\(t−θ/2\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|=o\(t^\{\-\\theta/2\}\)\\quad\\text\{a\.s\.\}\(32\)
If, in addition, Assumption[2](https://arxiv.org/html/2609.12119#Thmassumption2)holds, then

min1≤i≤t⁡\(f⁡\(𝐱i\)−f∗\)=o⁡\(t−θ\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\bigl\(f\(\\mathbf\{x\}\_\{i\}\)\-f^\{\*\}\\bigr\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\}\(33\)

###### Proof:

We first control the momentum variable\. From \([28](https://arxiv.org/html/2609.12119#S4.E28)\),

𝔼t​‖𝐯t\+1‖2=β2​‖𝐯t‖2−2​αt​β​⟨𝐯t,𝔼t​𝐠tC​N⟩\+αt2​𝔼t​‖𝐠tC​N‖2\.\\displaystyle\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{v\}\_\{t\+1\}\\\|^\{2\}=\\beta^\{2\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\-2\\alpha\_\{t\}\\beta\\langle\\mathbf\{v\}\_\{t\},\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\rangle\+\\alpha\_\{t\}^\{2\}\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{g\}\_\{t\}^\{CN\}\\\|^\{2\}\.\(34\)Since the additive Gaussian noise has zero conditional mean,

𝔼t​𝐠tC​N=𝔼t​\[clipq⁡\(∇f​\(𝐱t,ξt\)\)\],\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}=\\mathbb\{E\}\_\{t\}\[\\operatorname\{clip\}\_\{q\}\(\\nabla f\(\\mathbf\{x\}\_\{t\};\\xi\_\{t\}\)\)\],and hence,‖𝔼t​𝐠tC​N‖≤q\\\|\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\\|\\leq q\. Letρ:=1−β22\>0\.\\rho:=\\frac\{1\-\\beta^\{2\}\}\{2\}\>0\.Applying Young’s inequality to the cross term in \([34](https://arxiv.org/html/2609.12119#S4.E34)\) and using \([20](https://arxiv.org/html/2609.12119#S4.E20)\) gives

𝔼t​‖𝐯t\+1‖2\\displaystyle\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{v\}\_\{t\+1\}\\\|^\{2\}≤\(β2\+ρ\)​‖𝐯t‖2\+αt2​\(Q2\+β2​q2ρ\)\\displaystyle\\leq\(\\beta^\{2\}\+\\rho\)\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+\\alpha\_\{t\}^\{2\}\\left\(Q^\{2\}\+\\frac\{\\beta^\{2\}q^\{2\}\}\{\\rho\}\\right\)=\(1−ρ\)​‖𝐯t‖2\+Cv​αt2,\\displaystyle=\(1\-\\rho\)\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+C\_\{v\}\\alpha\_\{t\}^\{2\},\(35\)whereCv:=Q2\+β2​q2ρC\_\{v\}:=Q^\{2\}\+\\frac\{\\beta^\{2\}q^\{2\}\}\{\\rho\}\. We next derive a descent inequality forf⁡\(𝐳t\)f\(\\mathbf\{z\}\_\{t\}\)\. ByLL\-smoothness and \([28](https://arxiv.org/html/2609.12119#S4.E28)\),

𝔼t​\[f⁡\(𝐳t\+1\)\]≤\\displaystyle\\mathbb\{E\}\_\{t\}\[f\(\\mathbf\{z\}\_\{t\+1\}\)\]\\leq\\;f⁡\(𝐳t\)−αt′​⟨∇f​\(𝐳t\),𝔼t​𝐠tC​N⟩\+L​Q22​\(αt′\)2\.\\displaystyle f\(\\mathbf\{z\}\_\{t\}\)\-\\alpha\_\{t\}^\{\\prime\}\\langle\\nabla f\(\\mathbf\{z\}\_\{t\}\),\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\rangle\+\\frac\{LQ^\{2\}\}\{2\}\(\\alpha\_\{t\}^\{\\prime\}\)^\{2\}\.\(36\)Decomposing the inner product gives

⟨∇f​\(𝐳t\),𝔼t​𝐠tC​N⟩=\\displaystyle\\left\\langle\\nabla f\(\\mathbf\{z\}\_\{t\}\),\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\right\\rangle=\\;⟨∇f​\(𝐱t\),𝔼t​𝐠tC​N⟩\\displaystyle\\left\\langle\\nabla f\(\\mathbf\{x\}\_\{t\}\),\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\right\\rangle\+⟨∇f​\(𝐳t\)−∇f​\(𝐱t\),𝔼t​𝐠tC​N⟩\.\\displaystyle\+\\left\\langle\\nabla f\(\\mathbf\{z\}\_\{t\}\)\-\\nabla f\(\\mathbf\{x\}\_\{t\}\),\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\right\\rangle\.The first term is bounded using \([19](https://arxiv.org/html/2609.12119#S4.E19)\), while the second satisfies

⟨∇f​\(𝐳t\)−∇f​\(𝐱t\),𝔼t​𝐠tC​N⟩\\displaystyle\\left\\langle\\nabla f\(\\mathbf\{z\}\_\{t\}\)\-\\nabla f\(\\mathbf\{x\}\_\{t\}\),\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\right\\rangle≥−L​q​‖𝐳t−𝐱t‖=−L​q​β1−β​‖𝐯t‖\.\\displaystyle\\geq\-Lq\\\|\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\\|=\-\\frac\{Lq\\beta\}\{1\-\\beta\}\\\|\\mathbf\{v\}\_\{t\}\\\|\.Hence,

⟨∇f​\(𝐳t\),𝔼t​𝐠tC​N⟩≥κq​Ψq​\(‖∇f​\(𝐱t\)‖\)−K​‖𝐯t‖,\\left\\langle\\nabla f\(\\mathbf\{z\}\_\{t\}\),\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\right\\rangle\\geq\\kappa\_\{q\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\-K\\\|\\mathbf\{v\}\_\{t\}\\\|,whereK:=L​q​β1−βK:=\\frac\{Lq\\beta\}\{1\-\\beta\}\. Substitution into \([36](https://arxiv.org/html/2609.12119#S4.E36)\) yields

𝔼t​\[f⁡\(𝐳t\+1\)−f∗\]≤\\displaystyle\\mathbb\{E\}\_\{t\}\[f\(\\mathbf\{z\}\_\{t\+1\}\)\-f^\{\*\}\]\\leq\\;f⁡\(𝐳t\)−f∗−κq​αt′​Ψq​\(‖∇f​\(𝐱t\)‖\)\\displaystyle f\(\\mathbf\{z\}\_\{t\}\)\-f^\{\*\}\-\\kappa\_\{q\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\+K​αt′​‖𝐯t‖\+L​Q22​\(αt′\)2\.\\displaystyle\+K\\alpha\_\{t\}^\{\\prime\}\\\|\\mathbf\{v\}\_\{t\}\\\|\+\\frac\{LQ^\{2\}\}\{2\}\(\\alpha\_\{t\}^\{\\prime\}\)^\{2\}\.\(37\)
Define the energy

Yt:=f⁡\(𝐳t\)−f∗\+‖𝐯t‖2\.Y\_\{t\}:=f\(\\mathbf\{z\}\_\{t\}\)\-f^\{\*\}\+\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\.\(38\)Combining \([35](https://arxiv.org/html/2609.12119#S4.E35)\) and \([37](https://arxiv.org/html/2609.12119#S4.E37)\) gives

𝔼t​\[Yt\+1\]≤\\displaystyle\\mathbb\{E\}\_\{t\}\[Y\_\{t\+1\}\]\\leq\\;Yt−κq​αt′​Ψq​\(‖∇f​\(𝐱t\)‖\)−ρ​‖𝐯t‖2\\displaystyle Y\_\{t\}\-\\kappa\_\{q\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\-\\rho\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+K​αt′​‖𝐯t‖\+C0​αt2,\\displaystyle\+K\\alpha\_\{t\}^\{\\prime\}\\\|\\mathbf\{v\}\_\{t\}\\\|\+C\_\{0\}\\alpha\_\{t\}^\{2\},where

C0:=Cv\+L​Q22​\(1−β\)2\.C\_\{0\}:=C\_\{v\}\+\\frac\{LQ^\{2\}\}\{2\(1\-\\beta\)^\{2\}\}\.Applying Young’s inequality once more,

K​αt′​‖𝐯t‖≤ρ2​‖𝐯t‖2\+K22​ρ​\(αt′\)2\.K\\alpha\_\{t\}^\{\\prime\}\\\|\\mathbf\{v\}\_\{t\}\\\|\\leq\\frac\{\\rho\}\{2\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+\\frac\{K^\{2\}\}\{2\\rho\}\(\\alpha\_\{t\}^\{\\prime\}\)^\{2\}\.Thus, for some constantC\>0C\>0independent oftt,

𝔼t​\[Yt\+1\]≤\\displaystyle\\mathbb\{E\}\_\{t\}\[Y\_\{t\+1\}\]\\leq\\;Yt−κq​αt′​Ψq​\(‖∇f​\(𝐱t\)‖\)−ρ2​‖𝐯t‖2\+C​αt2\.\\displaystyle Y\_\{t\}\-\\kappa\_\{q\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\-\\frac\{\\rho\}\{2\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+C\\alpha\_\{t\}^\{2\}\.\(39\)
We now apply Proposition[1](https://arxiv.org/html/2609.12119#Thmproposition1)with

Xt:=κq​αt′​Ψq​\(‖∇f​\(𝐱t\)‖\)\+ρ2​‖𝐯t‖2,Zt:=C​αt2\.\\begin\{split\}X\_\{t\}&:=\\kappa\_\{q\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\+\\frac\{\\rho\}\{2\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\},\\\\ Z\_\{t\}&:=C\\alpha\_\{t\}^\{2\}\.\\end\{split\}\(40\)Since∑tαt2<∞\\sum\_\{t\}\\alpha\_\{t\}^\{2\}<\\infty, Proposition[1](https://arxiv.org/html/2609.12119#Thmproposition1)implies

∑t=1∞αt′​Ψq​\(‖∇f​\(𝐱t\)‖\)<∞and∑t=1∞‖𝐯t‖2<∞a\.s\.\\begin\{split\}\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)<\\infty\\quad\\text\{and\}\\quad\\sum\_\{t=1\}^\{\\infty\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}<\\infty\\quad\\text\{a\.s\.\}\\end\{split\}Sinceαt′=αt/\(1−β\)\\alpha\_\{t\}^\{\\prime\}=\\alpha\_\{t\}/\(1\-\\beta\), the summation relation above is equivalent to \([29](https://arxiv.org/html/2609.12119#S4.E29)\)\. Furthermore,‖𝐯t‖→0\\\|\\mathbf\{v\}\_\{t\}\\\|\\to 0a\.s\. And by \([27](https://arxiv.org/html/2609.12119#S4.E27)\),

‖𝐳t−𝐱t‖=β1−β​‖𝐯t‖→0a\.s\.\\\|\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\\|=\\frac\{\\beta\}\{1\-\\beta\}\\\|\\mathbf\{v\}\_\{t\}\\\|\\to 0\\quad\\text\{a\.s\.\}
The rate now follows exactly as in Theorem[1](https://arxiv.org/html/2609.12119#Thmtheorem1)\. Applying Lemma[1](https://arxiv.org/html/2609.12119#Thmlemma1)to \([29](https://arxiv.org/html/2609.12119#S4.E29)\) gives

min1≤i≤t⁡Ψq​\(‖∇f​\(𝐱i\)‖\)=o⁡\(\(∑i=1t−1αi\)−1\)=o⁡\(t−θ\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|\)=o\\left\(\\left\(\\sum\_\{i=1\}^\{t\-1\}\\alpha\_\{i\}\\right\)^\{\-1\}\\right\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\}SinceΨq​\(r\)=r2\\Psi\_\{q\}\(r\)=r^\{2\}forr≤qr\\leq q, this implies

min1≤i≤t∥∇f\(𝐱i\)∥=o\(t−θ/2\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|=o\(t^\{\-\\theta/2\}\)\\quad\\text\{a\.s\.\}
Ifffis additionallyμ\\mu\-strongly convex, then \([8](https://arxiv.org/html/2609.12119#S2.E8)\) and the same argument used in Theorem[1](https://arxiv.org/html/2609.12119#Thmtheorem1)give

min1≤i≤t⁡\(f⁡\(𝐱i\)−f∗\)=o⁡\(t−θ\)a\.s\.\\min\_\{1\\leq i\\leq t\}\(f\(\\mathbf\{x\}\_\{i\}\)\-f^\{\*\}\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\}This completes the proof\. ∎

### IV\-CStochastic Nesterov’s Accelerated Gradient

The iteration of the clipped noisy stochastic Nesterov’s accelerated gradient \(SNAG\-CN\) method is given by

𝐲t\+1=𝐱t−αt​𝐠tC​N,𝐱t\+1=𝐲t\+1\+β⁡\(𝐲t\+1−𝐲t\),\\begin\{split\}\\mathbf\{y\}\_\{t\+1\}&=\\mathbf\{x\}\_\{t\}\-\\alpha\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\},\\\\ \\mathbf\{x\}\_\{t\+1\}&=\\mathbf\{y\}\_\{t\+1\}\+\\beta\(\\mathbf\{y\}\_\{t\+1\}\-\\mathbf\{y\}\_\{t\}\),\\end\{split\}\(41\)whereβ∈\[0,1\)\\beta\\in\[0,1\)\.

Following\[[10](https://arxiv.org/html/2609.12119#bib.bib1)\], define

𝐯t:=β⁡\(𝐲t−𝐲t−1\),𝐳t:=𝐱t\+β1−β​𝐯t\.\\mathbf\{v\}\_\{t\}:=\\beta\(\\mathbf\{y\}\_\{t\}\-\\mathbf\{y\}\_\{t\-1\}\),\\quad\\mathbf\{z\}\_\{t\}:=\\mathbf\{x\}\_\{t\}\+\\frac\{\\beta\}\{1\-\\beta\}\\mathbf\{v\}\_\{t\}\.\(42\)Then the SNAG\-CN iteration can be equivalently written as

𝐯t\+1=β​𝐯t−β​αt​𝐠tC​N,𝐳t\+1=𝐳t−αt′𝐠tC​N,αt′:=αt1−β\.\\begin\{split\}\\mathbf\{v\}\_\{t\+1\}&=\\beta\\mathbf\{v\}\_\{t\}\-\\beta\\alpha\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\},\\\\ \\mathbf\{z\}\_\{t\+1\}&=\\mathbf\{z\}\_\{t\}\-\\alpha\_\{t\}^\{\\prime\}\\mathbf\{g\}\_\{t\}^\{CN\},\\quad\\alpha\_\{t\}^\{\\prime\}:=\\frac\{\\alpha\_\{t\}\}\{1\-\\beta\}\.\\end\{split\}\(43\)Thus, the transformed SNAG\-CN iteration differs from the corresponding SHB\-CN iteration only through the additional factorβ\\betamultiplying the stochastic\-gradient term in the velocity recursion\.

###### Theorem 3\(Convergence of SNAG\-CN\)

Consider the iterates of SNAG\-CN in \([41](https://arxiv.org/html/2609.12119#S4.E41)\), withβ∈\[0,1\)\\beta\\in\[0,1\)\. Suppose Assumptions[1](https://arxiv.org/html/2609.12119#Thmassumption1)and[3](https://arxiv.org/html/2609.12119#Thmassumption3)hold, letq\>σgq\>\\sigma\_\{g\}, and suppose that the step sizes satisfy \([21](https://arxiv.org/html/2609.12119#S4.E21)\)\. Then

∑t=1∞αt​Ψq​\(‖∇f​\(𝐱t\)‖\)\\displaystyle\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)<∞,∑t=1∞‖𝐯t‖2<∞\\displaystyle<\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}<\\infty\(44\)almost surely\. In particular,

∥𝐯t∥→0,∥𝐳t−𝐱t∥→0a\.s\.\\\|\\mathbf\{v\}\_\{t\}\\\|\\to 0,\\quad\\\|\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\\|\\to 0\\quad\\text\{a\.s\.\}\(45\)Moreover,

min1≤i≤t⁡Ψq​\(‖∇f​\(𝐱i\)‖\)=o⁡\(t−θ\)a\.s\.,\\min\_\{1\\leq i\\leq t\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\},\(46\)and thus

min1≤i≤t∥∇f\(𝐱i\)∥=o\(t−θ/2\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\\|\\nabla f\(\\mathbf\{x\}\_\{i\}\)\\\|=o\(t^\{\-\\theta/2\}\)\\quad\\text\{a\.s\.\}\(47\)
If, in addition, Assumption[2](https://arxiv.org/html/2609.12119#Thmassumption2)holds, then

min1≤i≤t⁡\(f⁡\(𝐱i\)−f∗\)=o⁡\(t−θ\)a\.s\.\\min\_\{1\\leq i\\leq t\}\\bigl\(f\(\\mathbf\{x\}\_\{i\}\)\-f^\{\*\}\\bigr\)=o\(t^\{\-\\theta\}\)\\quad\\text\{a\.s\.\}\(48\)

###### Proof:

The proof follows the same argument as Theorem[2](https://arxiv.org/html/2609.12119#Thmtheorem2)\. The only difference is the velocity recursion \([43](https://arxiv.org/html/2609.12119#S4.E43)\)\. In particular,

𝔼t​‖𝐯t\+1‖2\\displaystyle\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{v\}\_\{t\+1\}\\\|^\{2\}=β2​𝔼t​‖𝐯t−αt​𝐠tC​N‖2\\displaystyle=\\beta^\{2\}\\mathbb\{E\}\_\{t\}\\left\\\|\\mathbf\{v\}\_\{t\}\-\\alpha\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\right\\\|^\{2\}=β2​‖𝐯t‖2−2​β2​αt​⟨𝐯t,𝔼t​𝐠tC​N⟩\+β2​αt2​𝔼t​‖𝐠tC​N‖2\.\\displaystyle=\\beta^\{2\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\-2\\beta^\{2\}\\alpha\_\{t\}\\left\\langle\\mathbf\{v\}\_\{t\},\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\right\\rangle\+\\beta^\{2\}\\alpha\_\{t\}^\{2\}\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{g\}\_\{t\}^\{CN\}\\\|^\{2\}\.\(49\)Recall that

‖𝔼t​𝐠tC​N‖≤q,𝔼t​‖𝐠tC​N‖2≤Q2\.\\\|\\mathbb\{E\}\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\}\\\|\\leq q,\\quad\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{g\}\_\{t\}^\{CN\}\\\|^\{2\}\\leq Q^\{2\}\.Let

ρ:=1−β22\>0\.\\rho:=\\frac\{1\-\\beta^\{2\}\}\{2\}\>0\.Applying Young’s inequality to \([49](https://arxiv.org/html/2609.12119#S4.E49)\) gives

𝔼t​‖𝐯t\+1‖2\\displaystyle\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{v\}\_\{t\+1\}\\\|^\{2\}≤\(β2\+ρ\)​‖𝐯t‖2\+αt2​\(β2​Q2\+β4​q2ρ\)\\displaystyle\\leq\(\\beta^\{2\}\+\\rho\)\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+\\alpha\_\{t\}^\{2\}\\left\(\\beta^\{2\}Q^\{2\}\+\\frac\{\\beta^\{4\}q^\{2\}\}\{\\rho\}\\right\)=\(1−ρ\)​‖𝐯t‖2\+CvN​αt2,\\displaystyle=\(1\-\\rho\)\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+C\_\{v\}^\{N\}\\alpha\_\{t\}^\{2\},\(50\)where

CvN:=β2​Q2\+β4​q2ρ\.C\_\{v\}^\{N\}:=\\beta^\{2\}Q^\{2\}\+\\frac\{\\beta^\{4\}q^\{2\}\}\{\\rho\}\.The recursion for𝐳t\\mathbf\{z\}\_\{t\}in \([43](https://arxiv.org/html/2609.12119#S4.E43)\) is identical to that of SHB\-CN\. Therefore, the sameLL\-smoothness and expected clipped\-gradient alignment arguments used in Theorem[2](https://arxiv.org/html/2609.12119#Thmtheorem2)yield

𝔼t​\[f⁡\(𝐳t\+1\)−f∗\]≤\\displaystyle\\mathbb\{E\}\_\{t\}\[f\(\\mathbf\{z\}\_\{t\+1\}\)\-f^\{\*\}\]\\leq\\;f⁡\(𝐳t\)−f∗−κq​αt′​Ψq​\(‖∇f​\(𝐱t\)‖\)\\displaystyle f\(\\mathbf\{z\}\_\{t\}\)\-f^\{\*\}\-\\kappa\_\{q\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\+K​αt′​‖𝐯t‖\+L​Q22​\(αt′\)2,\\displaystyle\+K\\alpha\_\{t\}^\{\\prime\}\\\|\\mathbf\{v\}\_\{t\}\\\|\+\\frac\{LQ^\{2\}\}\{2\}\(\\alpha\_\{t\}^\{\\prime\}\)^\{2\},whereK:=L​q​β1−βK:=\\frac\{Lq\\beta\}\{1\-\\beta\}\. Combining this inequality with \([50](https://arxiv.org/html/2609.12119#S4.E50)\) and defining

Yt:=f⁡\(𝐳t\)−f∗\+‖𝐯t‖2,Y\_\{t\}:=f\(\\mathbf\{z\}\_\{t\}\)\-f^\{\*\}\+\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\},gives, after another application of Young’s inequality,

𝔼t​\[Yt\+1\]≤Yt−κq​αt′​Ψq​\(‖∇f​\(𝐱t\)‖\)−ρ2​‖𝐯t‖2\+CN​αt2\\mathbb\{E\}\_\{t\}\[Y\_\{t\+1\}\]\\leq Y\_\{t\}\-\\kappa\_\{q\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\-\\frac\{\\rho\}\{2\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\+C\_\{N\}\\alpha\_\{t\}^\{2\}\(51\)for some constantCN\>0C\_\{N\}\>0independent oftt\. Proposition[1](https://arxiv.org/html/2609.12119#Thmproposition1)therefore implies

∑t=1∞αt′Ψq\(∥∇f\(𝐱t\)∥\)<∞,∑t=1∞∥𝐯t∥2<∞a\.s\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)<\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}<\\infty\\quad\\text\{a\.s\.\}Sinceαt′=αt/\(1−β\)\\alpha\_\{t\}^\{\\prime\}=\\alpha\_\{t\}/\(1\-\\beta\), \([44](https://arxiv.org/html/2609.12119#S4.E44)\) follows, while∑t‖𝐯t‖2<∞\\sum\_\{t\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}<\\inftyimplies𝐯t→0\\mathbf\{v\}\_\{t\}\\to 0and hence‖𝐳t−𝐱t‖→0\\\|\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\\|\\to 0almost surely\.

The best\-iterate and strongly convex rates now follow identically to Theorem[2](https://arxiv.org/html/2609.12119#Thmtheorem2)by applying Lemma[1](https://arxiv.org/html/2609.12119#Thmlemma1)\. This proves \([46](https://arxiv.org/html/2609.12119#S4.E46)\)–\([48](https://arxiv.org/html/2609.12119#S4.E48)\)\. ∎

## VLast\-Iterate Convergence Analysis

The results of Section[IV](https://arxiv.org/html/2609.12119#S4)establish almost sure weighted summability of the gradient measureΨq​\(r\)=min⁡\{r2,q​r\}\\Psi\_\{q\}\(r\)=\\min\\\{r^\{2\},qr\\\}\. Weighted summability alone does not imply last\-iterate convergence, since the gradient norm may oscillate\. We use the following result of\[[13](https://arxiv.org/html/2609.12119#bib.bib6)\], simplified from\[[2](https://arxiv.org/html/2609.12119#bib.bib16)\], to rule out such behaviour\.

###### Lemma 2\(Lemma 1 of\[[13](https://arxiv.org/html/2609.12119#bib.bib6)\]\)

Let\{bt\}\\\{b\_\{t\}\\\}and\{αt\}\\\{\\alpha\_\{t\}\\\}be nonnegative sequences and let\{𝐰t\}\\\{\\mathbf\{w\}\_\{t\}\\\}be a sequence of vectors\. Suppose that, for somep≥1p\\geq 1,

∑t=1∞αt​btp<∞,∑t=1∞αt=∞\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}b\_\{t\}^\{p\}<\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}=\\infty\.\(52\)Furthermore, suppose that there existsC\>0C\>0such that, for everyτ≥1\\tau\\geq 1,

\|bt\+τ−bt\|≤C⁡\(∑i=tt\+τ−1αi​bi\+‖∑i=tt\+τ−1αi​𝐰i‖\),\\displaystyle\|b\_\{t\+\\tau\}\-b\_\{t\}\|\\leq C\\left\(\\sum\_\{i=t\}^\{t\+\\tau\-1\}\\alpha\_\{i\}b\_\{i\}\+\\left\\\|\\sum\_\{i=t\}^\{t\+\\tau\-1\}\\alpha\_\{i\}\\mathbf\{w\}\_\{i\}\\right\\\|\\right\),\(53\)where∑t=1∞αt​𝐰t\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}\\mathbf\{w\}\_\{t\}converges\. Thenbt→0b\_\{t\}\\to 0\. See also Lemma 10 of\[[11](https://arxiv.org/html/2609.12119#bib.bib8)\]for the casep\>0p\>0\.

###### Theorem 4\(Last\-iterate convergence\)

Consider the iterates of SGD\-CN, SHB\-CN and SNAG\-CN, withq\>σgq\>\\sigma\_\{g\}andβ∈\[0,1\)\\beta\\in\[0,1\)\. Suppose Assumptions[1](https://arxiv.org/html/2609.12119#Thmassumption1)and[3](https://arxiv.org/html/2609.12119#Thmassumption3)hold and

∑t=1∞αt=∞,∑t=1∞αt2<∞\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}=\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{2\}<\\infty\.\(54\)Then

‖∇f​\(𝐱t\)‖→0a\.s\.\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\\to 0\\quad\\text\{a\.s\.\}\(55\)

###### Proof:

It suffices to prove the result for SHB\-CN, since SGD\-CN is recovered by settingβ=0\\beta=0\. Recall

𝐯t\+1=β​𝐯t−αt​𝐠tC​N,𝐳t\+1=𝐳t−αt′​𝐠tC​N,αt′:=αt1−β,\\mathbf\{v\}\_\{t\+1\}=\\beta\\mathbf\{v\}\_\{t\}\-\\alpha\_\{t\}\\mathbf\{g\}\_\{t\}^\{CN\},\\quad\\mathbf\{z\}\_\{t\+1\}=\\mathbf\{z\}\_\{t\}\-\\alpha\_\{t\}^\{\\prime\}\\mathbf\{g\}\_\{t\}^\{CN\},\\quad\\alpha\_\{t\}^\{\\prime\}:=\\frac\{\\alpha\_\{t\}\}\{1\-\\beta\},where

𝐳t−𝐱t=β1−β​𝐯t\.\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}=\\frac\{\\beta\}\{1\-\\beta\}\\mathbf\{v\}\_\{t\}\.\(56\)The supermartingale recursion \([39](https://arxiv.org/html/2609.12119#S4.E39)\) derived in Theorem[2](https://arxiv.org/html/2609.12119#Thmtheorem2)remains valid under \([54](https://arxiv.org/html/2609.12119#S5.E54)\); the particular power\-law form of the step sizes is only required for the rate result\. Proposition[1](https://arxiv.org/html/2609.12119#Thmproposition1)therefore gives

∑t=1∞αt′Ψq\(∥∇f\(𝐱t\)∥\)<∞,∑t=1∞∥𝐯t∥2<∞a\.s\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)<\\infty,\\quad\\sum\_\{t=1\}^\{\\infty\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}<\\infty\\quad\\text\{a\.s\.\}\(57\)Moreover, the energy

Yt=f⁡\(𝐳t\)−f∗\+‖𝐯t‖2Y\_\{t\}=f\(\\mathbf\{z\}\_\{t\}\)\-f^\{\*\}\+\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}converges almost surely\. We work henceforth on an event of probability one on which these properties hold\. SinceYtY\_\{t\}is bounded,f⁡\(𝐳t\)−f∗f\(\\mathbf\{z\}\_\{t\}\)\-f^\{\*\}is bounded\. ByLL\-smoothness and the lower boundedness offf,

‖∇f​\(𝐳t\)‖2≤2​L​\(f⁡\(𝐳t\)−f∗\),\\\|\\nabla f\(\\mathbf\{z\}\_\{t\}\)\\\|^\{2\}\\leq 2L\\bigl\(f\(\\mathbf\{z\}\_\{t\}\)\-f^\{\*\}\\bigr\),so\{‖∇f​\(𝐳t\)‖\}\\\{\\\|\\nabla f\(\\mathbf\{z\}\_\{t\}\)\\\|\\\}is bounded\. Since \([57](https://arxiv.org/html/2609.12119#S5.E57)\) implies𝐯t→0\\mathbf\{v\}\_\{t\}\\to 0, \([56](https://arxiv.org/html/2609.12119#S5.E56)\) andLL\-smoothness show that\{‖∇f​\(𝐱t\)‖\}\\\{\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\\\}is also bounded\. Thus, for some finiteM\>0M\>0,

Ψq​\(‖∇f​\(𝐱t\)‖\)≥min⁡\{1,qM\}​‖∇f​\(𝐱t\)‖2\.\\Psi\_\{q\}\(\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\)\\geq\\min\\left\\\{1,\\frac\{q\}\{M\}\\right\\\}\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|^\{2\}\.Hence \([57](https://arxiv.org/html/2609.12119#S5.E57)\) gives

∑t=1∞αt′​‖∇f​\(𝐱t\)‖2<∞\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|^\{2\}<\\infty\.\(58\)Using \([56](https://arxiv.org/html/2609.12119#S5.E56)\),

‖∇f​\(𝐳t\)‖2\\displaystyle\\\|\\nabla f\(\\mathbf\{z\}\_\{t\}\)\\\|^\{2\}≤2​‖∇f​\(𝐱t\)‖2\+2​L2​‖𝐳t−𝐱t‖2\\displaystyle\\leq 2\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|^\{2\}\+2L^\{2\}\\\|\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\\|^\{2\}=2​‖∇f​\(𝐱t\)‖2\+2​L2​β2\(1−β\)2​‖𝐯t‖2\.\\displaystyle=2\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|^\{2\}\+\\frac\{2L^\{2\}\\beta^\{2\}\}\{\(1\-\\beta\)^\{2\}\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\.Since\{αt′\}\\\{\\alpha\_\{t\}^\{\\prime\}\\\}is bounded, \([57](https://arxiv.org/html/2609.12119#S5.E57)\) and \([58](https://arxiv.org/html/2609.12119#S5.E58)\) imply

∑t=1∞αt′​‖∇f​\(𝐳t\)‖2<∞\.\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\\\|\\nabla f\(\\mathbf\{z\}\_\{t\}\)\\\|^\{2\}<\\infty\.\(59\)It remains to verify the oscillation condition in Lemma[2](https://arxiv.org/html/2609.12119#Thmlemma2)\. Define

𝐡t:=clipq​\(∇f​\(𝐱t,ξt\)\),𝐡¯t:=𝔼t​\[𝐡t\],𝐮t:=𝐡t−𝐡¯t\.\\mathbf\{h\}\_\{t\}:=\\text\{clip\}\_\{q\}\(\\nabla f\(\\mathbf\{x\}\_\{t\};\\xi\_\{t\}\)\),\\quad\\bar\{\\mathbf\{h\}\}\_\{t\}:=\\mathbb\{E\}\_\{t\}\[\\mathbf\{h\}\_\{t\}\],\\quad\\mathbf\{u\}\_\{t\}:=\\mathbf\{h\}\_\{t\}\-\\bar\{\\mathbf\{h\}\}\_\{t\}\.We first note that

‖𝐡¯t‖≤cq​‖∇f​\(𝐱t\)‖,cq:=qq−σg\.\\\|\\bar\{\\mathbf\{h\}\}\_\{t\}\\\|\\leq c\_\{q\}\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|,\\quad c\_\{q\}:=\\frac\{q\}\{q\-\\sigma\_\{g\}\}\.\(60\)Indeed, if‖∇f​\(𝐱t\)‖≤q−σg\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\\leq q\-\\sigma\_\{g\}, then Assumption[3](https://arxiv.org/html/2609.12119#Thmassumption3)implies that clipping is inactive almost surely and𝐡¯t=∇f​\(𝐱t\)\\bar\{\\mathbf\{h\}\}\_\{t\}=\\nabla f\(\\mathbf\{x\}\_\{t\}\)\. Otherwise,‖𝐡¯t‖≤q≤cq​‖∇f​\(𝐱t\)‖\\\|\\bar\{\\mathbf\{h\}\}\_\{t\}\\\|\\leq q\\leq c\_\{q\}\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\. Let

bt:=‖∇f​\(𝐳t\)‖,cβ:=β1−β\.b\_\{t\}:=\\\|\\nabla f\(\\mathbf\{z\}\_\{t\}\)\\\|,\\quad c\_\{\\beta\}:=\\frac\{\\beta\}\{1\-\\beta\}\.ByLL\-smoothness and \([56](https://arxiv.org/html/2609.12119#S5.E56)\),

‖𝐡¯t‖≤cq​bt\+cq​L​cβ​‖𝐯t‖\.\\\|\\bar\{\\mathbf\{h\}\}\_\{t\}\\\|\\leq c\_\{q\}b\_\{t\}\+c\_\{q\}Lc\_\{\\beta\}\\\|\\mathbf\{v\}\_\{t\}\\\|\.Moreover,

𝐠tC​N=𝐡¯t\+𝐮t\+q​ζt\.\\mathbf\{g\}\_\{t\}^\{CN\}=\\bar\{\\mathbf\{h\}\}\_\{t\}\+\\mathbf\{u\}\_\{t\}\+q\\zeta\_\{t\}\.Therefore, for everyτ≥1\\tau\\geq 1,

\|bt\+τ−bt\|\\displaystyle\|b\_\{t\+\\tau\}\-b\_\{t\}\|≤L​‖𝐳t\+τ−𝐳t‖\\displaystyle\\leq L\\\|\\mathbf\{z\}\_\{t\+\\tau\}\-\\mathbf\{z\}\_\{t\}\\\|≤L​cq​∑i=tt\+τ−1αi′​bi\+L​cq​L​cβ​∑i=tt\+τ−1αi′​‖𝐯i‖\\displaystyle\\leq Lc\_\{q\}\\sum\_\{i=t\}^\{t\+\\tau\-1\}\\alpha\_\{i\}^\{\\prime\}b\_\{i\}\+Lc\_\{q\}Lc\_\{\\beta\}\\sum\_\{i=t\}^\{t\+\\tau\-1\}\\alpha\_\{i\}^\{\\prime\}\\\|\\mathbf\{v\}\_\{i\}\\\|\+L⁡‖∑i=tt\+τ−1αi′​\(𝐮i\+q​ζi\)‖\.\\displaystyle\\quad\+L\\left\\\|\\sum\_\{i=t\}^\{t\+\\tau\-1\}\\alpha\_\{i\}^\{\\prime\}\(\\mathbf\{u\}\_\{i\}\+q\\zeta\_\{i\}\)\\right\\\|\.\(61\)Now define the augmented random vector

𝐰t:=\[𝐮t\+q​ζtcq​L​cβ​‖𝐯t‖\]\.\\mathbf\{w\}\_\{t\}:=\\begin\{bmatrix\}\\mathbf\{u\}\_\{t\}\+q\\zeta\_\{t\}\\\\ c\_\{q\}Lc\_\{\\beta\}\\\|\\mathbf\{v\}\_\{t\}\\\|\\end\{bmatrix\}\.\(62\)Since𝐮t\\mathbf\{u\}\_\{t\}is a martingale difference and𝔼t​‖𝐮t‖2≤q2\\mathbb\{E\}\_\{t\}\\\|\\mathbf\{u\}\_\{t\}\\\|^\{2\}\\leq q^\{2\}, whileζt\\zeta\_\{t\}is an independent zero\-mean Gaussian vector,

∑t=1∞αt′​\(𝐮t\+q​ζt\)\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\(\\mathbf\{u\}\_\{t\}\+q\\zeta\_\{t\}\)converges almost surely by the martingale convergence theorem\[[16](https://arxiv.org/html/2609.12119#bib.bib7)\], since∑t\(αt′\)2<∞\\sum\_\{t\}\(\\alpha\_\{t\}^\{\\prime\}\)^\{2\}<\\infty\. Furthermore, by Cauchy–Schwarz and \([57](https://arxiv.org/html/2609.12119#S5.E57)\),

∑t=1∞αt′​‖𝐯t‖\\displaystyle\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\\\|\\mathbf\{v\}\_\{t\}\\\|≤\(∑t=1∞\(αt′\)2\)1/2​\(∑t=1∞‖𝐯t‖2\)1/2<∞\.\\displaystyle\\leq\\left\(\\sum\_\{t=1\}^\{\\infty\}\(\\alpha\_\{t\}^\{\\prime\}\)^\{2\}\\right\)^\{1/2\}\\left\(\\sum\_\{t=1\}^\{\\infty\}\\\|\\mathbf\{v\}\_\{t\}\\\|^\{2\}\\right\)^\{1/2\}<\\infty\.Hence

∑t=1∞αt′​𝐰t\\sum\_\{t=1\}^\{\\infty\}\\alpha\_\{t\}^\{\\prime\}\\mathbf\{w\}\_\{t\}converges almost surely\. Finally, usinga\+b≤2​\(a2\+b2\)a\+b\\leq\\sqrt\{2\(a^\{2\}\+b^\{2\}\)\}in \([61](https://arxiv.org/html/2609.12119#S5.E61)\), there exists a constantC\>0C\>0such that

\|bt\+τ−bt\|≤C⁡\(∑i=tt\+τ−1αi′​bi\+‖∑i=tt\+τ−1αi′​𝐰i‖\)\.\|b\_\{t\+\\tau\}\-b\_\{t\}\|\\leq C\\left\(\\sum\_\{i=t\}^\{t\+\\tau\-1\}\\alpha\_\{i\}^\{\\prime\}b\_\{i\}\+\\left\\\|\\sum\_\{i=t\}^\{t\+\\tau\-1\}\\alpha\_\{i\}^\{\\prime\}\\mathbf\{w\}\_\{i\}\\right\\\|\\right\)\.\(63\)Together with \([59](https://arxiv.org/html/2609.12119#S5.E59)\),∑tαt′=∞\\sum\_\{t\}\\alpha\_\{t\}^\{\\prime\}=\\infty, and Lemma[2](https://arxiv.org/html/2609.12119#Thmlemma2)withp=2p=2, this yields

‖∇f​\(𝐳t\)‖→0a\.s\.\\\|\\nabla f\(\\mathbf\{z\}\_\{t\}\)\\\|\\to 0\\quad\\text\{a\.s\.\}Finally,𝐯t→0\\mathbf\{v\}\_\{t\}\\to 0and \([56](https://arxiv.org/html/2609.12119#S5.E56)\) imply‖𝐳t−𝐱t‖→0\\\|\\mathbf\{z\}\_\{t\}\-\\mathbf\{x\}\_\{t\}\\\|\\to 0, and therefore

‖∇f​\(𝐱t\)‖≤‖∇f​\(𝐳t\)‖\+L​‖𝐱t−𝐳t‖→0a\.s\.\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\\leq\\\|\\nabla f\(\\mathbf\{z\}\_\{t\}\)\\\|\+L\\\|\\mathbf\{x\}\_\{t\}\-\\mathbf\{z\}\_\{t\}\\\|\\to 0\\quad\\text\{a\.s\.\}Settingβ=0\\beta=0recovers the SGD\-CN result\. The proof of convergence for SNAG\-CN is similar, following \([49](https://arxiv.org/html/2609.12119#S4.E49)\)\. ∎

## VIConclusion

In this paper, we established almost sure convergence guarantees for stochastic gradient methods with gradient clipping and additive Gaussian noise\. In particular, we analyzed SGD\-CN and its momentum extensions, SHB\-CN and SNAG\-CN\. Under smoothness and uniformly bounded stochastic\-gradient noise, we showed that when the clipping threshold satisfiesq\>σgq\>\\sigma\_\{g\}, the expected clipped stochastic gradient remains positively aligned with the true gradient\. This property allows the bias introduced by clipping to be incorporated directly into a supermartingale\-based convergence analysis\. For all three methods, we established almost sure weighted summability of the clipping\-aware stationarity measureΨq​\(r\)\\Psi\_\{q\}\(r\)from which almost sure best\-iterate convergence rates follow\. For SHB\-CN and SNAG\-CN, suitable energy functions additionally control the momentum terms\. We further strengthened these results to last\-iterate convergence, showing that‖∇f​\(𝐱t\)‖→0,\\\|\\nabla f\(\\mathbf\{x\}\_\{t\}\)\\\|\\to 0,almost surely, for SGD\-CN and its momentum variants\. Thus, the results establish almost sure asymptotic stationarity of individual optimization trajectories despite the combined effects of clipping bias and persistent Gaussian perturbations\.

Several questions remain open\. The uniformly bounded stochastic\-gradient noise assumption enables exact convergence with a fixed clipping threshold, but is stronger than commonly used bounded\-variance conditions\. It would therefore be interesting to determine whether the analysis can be extended to weaker stochastic\-gradient assumptions, possibly by imposing alternative structural conditions on the clipping bias\. Another direction is to sharpen the dependence of the convergence guarantees on the clipping thresholdqq, the stochastic\-gradient noise levelσg\\sigma\_\{g\}, and the varianceσC​N2\\sigma\_\{CN\}^\{2\}of the injected Gaussian noise\. Such results could provide a more quantitative understanding of the trade\-off between aggressive clipping, noise injection, and optimization performance\.

## References

- \[1\]M\. Abadi, A\. Chu, I\. Goodfellow, H\. B\. McMahan, I\. Mironov, K\. Talwar, and L\. Zhang\(2016\)Deep learning with differential privacy\.InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,pp\. 308–318\.Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p1.1),[Definition 2](https://arxiv.org/html/2609.12119#Thmdefinition2.3)\.
- \[2\]D\. P\. Bertsekas and J\. N\. Tsitsiklis\(2000\)Gradient convergence in gradient methods with errors\.SIAM Journal on Optimization10\(3\),pp\. 627–642\.Cited by:[§V](https://arxiv.org/html/2609.12119#S5.p1.1)\.
- \[3\]B\. Chen, K\. Leahy, A\. Jones, and M\. Hale\(2023\)Differential privacy for symbolic systems with application to markov chains\.Automatica152,pp\. 110908\.Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p3.1)\.
- \[4\]T\. T\. Doan\(2022\)Finite\-time analysis of markov gradient descent\.IEEE Transactions on Automatic Control68\(4\),pp\. 2140–2153\.Cited by:[§II](https://arxiv.org/html/2609.12119#S2.p1.1)\.
- \[5\]C\. Dwork, F\. McSherry, K\. Nissim, and A\. Smith\(2006\)Calibrating noise to sensitivity in private data analysis\.InTheory of Cryptography: Third Theory of Cryptography Conference,pp\. 265–284\.Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p1.1),[Remark 1](https://arxiv.org/html/2609.12119#Thmremark1.p1.1.1)\.
- \[6\]H\. Fang, X\. Li, C\. Fan, and P\. Li\(2023\)Improved convergence of differential private sgd with gradient clipping\.InThe Eleventh International Conference on Learning Representations,Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p3.1)\.
- \[7\]L\. Huang, J\. Wu, D\. Shi, S\. Dey, and L\. Shi\(2024\)Differential privacy in distributed optimization with gradient tracking\.IEEE Transactions on Automatic Control69\(9\),pp\. 5727–5742\.Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p3.1)\.
- \[8\]V\. Katewa, A\. Chakrabortty, and V\. Gupta\(2019\)Differential privacy for network identification\.IEEE Transactions on Control of Network Systems7\(1\),pp\. 266–277\.Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p3.1)\.
- \[9\]A\. Koloskova, H\. Hendrikx, and S\. U\. Stich\(2023\)Revisiting gradient clipping: stochastic bias and tight convergence guarantees\.InInternational Conference on Machine Learning,Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p3.1),[Remark 2](https://arxiv.org/html/2609.12119#Thmremark2.p1.1.1)\.
- \[10\]J\. Liu and Y\. Yuan\(2022\)On almost sure convergence rates of stochastic gradient methods\.InConference on Learning Theory,Cited by:[§II](https://arxiv.org/html/2609.12119#S2.p1.1),[§III](https://arxiv.org/html/2609.12119#S3.p2.1),[§IV\-C](https://arxiv.org/html/2609.12119#S4.SS3.p2.1),[Lemma 1](https://arxiv.org/html/2609.12119#Thmlemma1.3)\.
- \[11\]J\. Liu and Y\. Yuan\(2024\)Almost sure convergence rates analysis and saddle avoidance of stochastic gradient methods\.Journal of Machine Learning Research25\(271\),pp\. 1–40\.Cited by:[§IV\-B](https://arxiv.org/html/2609.12119#S4.SS2.p1.4),[Lemma 2](https://arxiv.org/html/2609.12119#Thmlemma2.p1.3.1)\.
- \[12\]Y\. Nesterov\(2004\)Introductory Lectures on Convex Optimization\.Applied Optimization87\.Cited by:[§II](https://arxiv.org/html/2609.12119#S2.p3.1)\.
- \[13\]F\. Orabona\(2020\)Almost sure convergence of SGD on smooth nonconvex functions\.Blogpost at https://parameterfree\.com/2020/10/05/almost\-sure\-convergence\-of\-sgd\-on\-smooth\-non\-convex\-functions\.Cited by:[§V](https://arxiv.org/html/2609.12119#S5.p1.1),[Lemma 2](https://arxiv.org/html/2609.12119#Thmlemma2.3)\.
- \[14\]H\. Robbins and D\. Siegmund\(1971\)A convergence theorem for non negative almost supermartingales and some applications\.InOptimizing methods in statistics,pp\. 233–257\.Cited by:[§III](https://arxiv.org/html/2609.12119#S3.p1.1)\.
- \[15\]Q\. Tang, F\. Shpilevskiy, and M\. Lécuyer\(2024\)DP\-AdamBC: your DP\-Adam is actually DP\-SGD \(unless you apply bias correction\)\.InProceedings of the AAAI Conference on Artificial Intelligence,Cited by:[§I](https://arxiv.org/html/2609.12119#S1.p3.1)\.
- \[16\]D\. Williams\(1991\)Probability with Martingales\.Cambridge University Press\.Cited by:[§V](https://arxiv.org/html/2609.12119#S5.p2.18.1)\.