PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Amartya Mukherjee, Jun Liu

arXiv:2609.12119v2cs.LGmath.OCmath.PR

TL;DR

Clipping can bias stochastic-gradient updates, and additive Gaussian noise continues to perturb iterates, complicating convergence analysis. The paper analyzes SGD-CN and momentum variants under smoothness and uniformly bounded stochastic-gradient noise assumptions. It establishes almost-sure best-iterate rates and last-iterate asymptotic stationarity for these methods.

  • Problem

    Clipping can bias stochastic gradients, and additive Gaussian perturbations continue to disturb iterates, so standard convergence arguments for unbiased SGD do not directly apply to SGD-CN.

    Source: §I · p. 1

  • Method

    The analysis combines clipping-aware gradient alignment for q > σ_g with supermartingale arguments for SGD-CN and its stochastic heavy-ball and Nesterov variants.

    Source: §I · p. 1, §III · p. 3, §VI · p. 7

  • Results

    Under smoothness, uniformly bounded stochastic-gradient noise, and q > σ_g, all three methods have almost-sure best-iterate convergence rates and last-iterate asymptotic stationarity.

    Source: §VI · p. 7

  • Takeaways & Limitations

    When the clipping threshold exceeds the stochastic-gradient noise bound, the expected clipped gradient remains positively aligned with the true gradient.

    Source: §VI · p. 7

    The uniformly bounded stochastic-gradient noise assumption is stronger than standard bounded-variance conditions.

    Source: §VI · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Clipping and additive noise motivate SGD-CN, but together they complicate convergence: clipping can bias updates, while noise continues to disturb iterates. This work establishes almost-sure convergence guarantees under uniformly bounded stochastic-gradient noise.

I. INTRODUCTION

  • Clipping is used to control large stochastic gradients and improve numerical stability, and in privacy-preserving optimization it bounds individual gradient contributions before noise is added.Related work also studies clipping and privacy-preserving stochastic optimization,.Source: §I · p. 1
  • Clipping can bias even an unbiased stochastic gradient, changing the magnitude and direction of expected updates, while additive Gaussian noise continually perturbs iterates.These effects mean standard convergence arguments for unbiased SGD do not directly apply to SGD-CN.Source: §I · p. 1
  • Under bounded variance alone, clipped SGD may fail to converge to an exact stationary point and instead approach a neighborhood dependent on variance and clipping threshold.The cited work motivates requiring additional structure on the stochastic-gradient oracle for exact convergence with a fixed threshold.Source: §I · p. 1
  • The paper studies almost-sure convergence of SGD-CN assuming a smooth objective and uniformly bounded stochastic-gradient noise.It reports weighted summability of a clipping-aware stationarity measure, best-iterate rates, and last-iterate convergence by controlling gradient-norm oscillations.Source: §I · p. 1

II. PRELIMINARIES AND ASSUMPTIONS

The section frames unconstrained minimization with clipped, noisy stochastic-gradient methods and states the assumptions and terminology used in the analysis.

II. PRELIMINARIES AND ASSUMPTIONS

  • The stated objectives are convergence in function value for convex settings and convergence of the gradient to zero for nonconvex settings.The problem is posed as unconstrained minimization of f.Source: §II · p. 1
  • SGD-CN modifies SGD by clipping gradients and adding noise to the clipped gradients.The section also assumes the stochastic gradient is unbiased, with conditional expectation equal to the true gradient.Source: §II · p. 2
  • Stochastic heavy-ball and Nesterov variants are possible, and the analysis does not rely on the differential-privacy connection used to choose q and σ_CN in DP settings.Source: §II · p. 2
  • The assumptions listed include L-smoothness, strong convexity, and uniformly bounded stochastic-gradient noise.The passage identifies these as assumptions commonly used in SGD analysis; the displayed formal conditions are not included in the supplied excerpts.Source: §II · p. 2

III. BACKGROUND AND LEMMAS ON SUPERMARTINGALES

This section sets up conditional-expectation and supermartingale tools, then establishes how the clipping threshold controls alignment between the expected clipped gradient and the true gradient.

III. BACKGROUND AND LEMMAS ON SUPERMARTINGALES

  • A supermartingale proposition supplies a convergence tool, and a separate lemma is identified for convergence results in nonconvex settings.The analysis uses conditional expectations with respect to the natural filtration.Source: §III · p. 2
  • The clipping-aware measure is Ψ_q(r) = min{r^2, qr}, capturing a quadratic regime for smaller gradients and a linear regime for larger ones.Source: §III · p. 3
  • When q > σ_g, the expected clipped stochastic gradient is uniformly aligned with the true gradient; the alignment coefficient is 1−σ_g/q.The section derives properties of the clipped gradient under the uniformly bounded noise assumption.Source: §III · pp. 2–3

IV. ALMOST SURE CONVERGENCE RATE ANALYSIS

The section develops almost-sure convergence-rate analysis for SGD-CN and stochastic heavy ball using the expected clipped-gradient alignment result.

IV. ALMOST SURE CONVERGENCE RATE ANALYSIS

  • The analysis targets almost-sure convergence rates for SGD-CN and its stochastic heavy-ball extension.Source: §IV · p. 3
  • For q > σ_g, the expected update has inner product with the true gradient at least κ_q Ψ_q(∥∇f(x_t)∥), where κ_q = 1−σ_g/q.This alignment result is the stated basis for the section's analysis.Source: §IV · p. 3
  • The analysis considers positive, nonincreasing step sizes satisfying the section's stated conditions.Source: §IV · p. 3

A. Stochastic Gradient Descent

Under smoothness and bounded stochastic-gradient noise, SGD-CN has almost-sure convergence guarantees when its clipping threshold and step sizes meet the stated conditions. With strong convexity, its best-iterate objective gap also has an almost-sure rate.

A. Stochastic Gradient Descent

  • Under Assumptions 1 and 3, q > σg, and step-size condition (21), SGD-CN’s objective value converges almost surely to a finite random variable.The paper states almost-sure convergence for SGD-CN under smoothness and bounded-noise assumptions.Source: A. Stochastic Gradient Descent · p. 3
  • The clipping threshold must satisfy q > σg for the stated SGD-CN convergence result.The result also requires Assumptions 1 and 3 and step sizes satisfying (21).Source: A. Stochastic Gradient Descent · p. 3
  • With the additional strong-convexity assumption, the best-iterate objective gap is o(t^-θ) almost surely.This rate follows from the strong-convexity case and the argument leading to the best-iterate bound.Source: A. Stochastic Gradient Descent · p. 4

B. Stochastic Heavy-Ball Method

The stochastic heavy-ball extension is analyzed through a transformed iterate and momentum control. Under the stated assumptions, it has almost-sure convergence guarantees, including best-iterate rates for gradient norm and, with strong convexity, objective gap.

B. Stochastic Heavy-Ball Method

  • The analysis rewrites SHB-CN using zt = xt + β/(1−β) vt, where vt = xt − xt−1.The transformation is used to analyze the momentum iteration through a related iterate.Source: B. Stochastic Heavy-Ball Method · p. 4
  • Under Assumptions 1 and 3, q > σg, and step-size condition (21), SHB-CN has the theorem’s stated almost-sure convergence guarantee.The theorem covers β ∈ [0,1).Source: B. Stochastic Heavy-Ball Method · p. 4
  • The transformed iterate approaches the original iterate almost surely because the momentum increments vanish.The analysis states ∥zt − xt∥ → 0 almost surely.Source: B. Stochastic Heavy-Ball Method · p. 5
  • The best-iterate gradient norm is o(t^-θ/2) almost surely.The rate follows from the summability argument for the transformed heavy-ball iteration.Source: B. Stochastic Heavy-Ball Method · p. 5
  • With additional strong convexity, the best-iterate objective gap is o(t^-θ) almost surely.The result uses the same argument as the strongly convex SGD-CN case.Source: B. Stochastic Heavy-Ball Method · p. 5

C. Stochastic Nesterov’s Accelerated Gradient

SNAG-CN is rewritten in terms of a velocity and transformed iterate, allowing its analysis to follow the SHB-CN argument. The section reports almost-sure convergence results and rates under stated conditions.

C. Stochastic Nesterov’s Accelerated Gradient

V. LAST-ITERATE CONVERGENCE ANALYSIS

The section addresses why weighted gradient summability does not by itself establish last-iterate convergence, then gives a last-iterate result for SGD-CN and its momentum variants. Its argument controls oscillation and uses the clipped-gradient alignment and supermartingale properties.

V. LAST-ITERATE CONVERGENCE ANALYSIS

  • Weighted summability of Ψ_q(∇f(x_t)) alone does not rule out gradient-norm oscillation, so the analysis uses a lemma to exclude it.Source: §V · p. 6
  • Theorem 4 presents a last-iterate convergence result for SGD-CN, SHB-CN, and SNAG-CN when q > σg, β ∈ [0,1), and Assumptions 1 and 3 hold.SGD-CN is recovered from SHB-CN by setting β = 0.Source: §V · p. 6
  • The supermartingale recursion remains valid under (54); the power-law step-size form is required only for the rate result.Source: §V · p. 6
  • When ||∇f(x_t)|| ≤ q − σ_g, clipping is inactive almost surely; otherwise, the expected clipped-gradient norm is bounded by q and by c_q||∇f(x_t)||.Source: §V · p. 7
  • The clipped-gradient fluctuation u_t is a martingale difference with conditional second moment at most q², while the added Gaussian vector is independent and zero-mean.The section defines u_t as the clipped stochastic gradient minus its conditional mean.Source: §V · pp. 6–7

VI. CONCLUSION

The paper establishes almost-sure convergence guarantees for clipped noisy SGD and its stochastic heavy-ball and Nesterov variants under smoothness and uniformly bounded stochastic-gradient noise. It identifies relaxing that noise assumption and sharpening the parameter dependence as directions for future work.

VI. CONCLUSION

  • Under smoothness and uniformly bounded stochastic-gradient noise, q > σ_g gives positive alignment between the expected clipped gradient and the true gradient, supporting almost-sure guarantees for SGD-CN, SHB-CN, and SNAG-CN.The results include best-iterate rates and last-iterate asymptotic stationarity.Source: §VI · p. 7
  • The authors identify relaxing the uniformly bounded stochastic-gradient noise assumption as future work because it is stronger than standard bounded-variance conditions.Source: §VI · p. 7
  • Sharper dependence on q, σ_g, and σ² is proposed as a way to characterize the trade-off between clipping, noise injection, and optimization performance more quantitatively.Source: §VI · p. 7
Loading 2609.12119v2…