PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping

Eduard Gorbunov, Marina Danilova, Alexander Gasnikov

arXiv:2005.10785v2math.OCcs.LG

TL;DR

Heavy-tailed gradient noise leaves high-probability complexity guarantees for stochastic optimization weaker than their light-tailed counterparts. The paper introduces accelerated clipped-SSTM and establishes high-probability complexity bounds for smooth convex and strongly convex problems, as well as clipped-SGD.

  • Problem

    For heavy-tailed gradient noise, existing high-probability guarantees are weaker than light-tailed counterparts, and expectation rates may not describe method behavior adequately.

    Source: §1 · p. 1

  • Method

    The paper develops clipped-SSTM, combining an accelerated stochastic first-order method with gradient clipping, and extends its proof technique to clipped-SGD.

    Source: §1.4 · p. 4, §5 · p. 9

  • Results

    The paper establishes the first accelerated high-probability complexity bounds for smooth convex optimization without light-tail assumptions, reports improved strongly convex bounds, and derives first high-probability bounds for clipped-SGD.

    Source: §5 · p. 9

  • Takeaways & Limitations

    Clipped-SSTM matches optimal stochastic methods’ oracle-call complexity up to constants and logarithmic factors while allowing heavy-tailed stochastic gradients.

    Source: §2 · p. 6

    The approach significantly relies on defining the optimization problem on R^n and does not address regularized or composite problems.

    Source: §5 · p. 9

Abstract

from arXiv · show

In this paper, we propose a new accelerated stochastic first-order method called clipped-SSTM for smooth convex stochastic optimization with heavy-tailed distributed noise in stochastic gradients and derive the first high-probability complexity bounds for this method closing the gap in the theory of stochastic optimization with heavy-tailed noise. Our method is based on a special variant of accelerated Stochastic Gradient Descent (SGD) and clipping of stochastic gradients. We extend our method to the strongly convex case and prove new complexity bounds that outperform state-of-the-art results in this case. Finally, we extend our proof technique and derive the first non-trivial high-probability complexity bounds for SGD with clipping without light-tails assumption on the noise.

1 Introduction

The paper studies smooth convex stochastic optimization when gradient noise may be heavy-tailed, a setting where expectation guarantees can miss large trajectory oscillations. It proposes clipping-based accelerated methods and derives high-probability guarantees without a light-tailed-noise assumption.

1.1 Preliminaries

  • The setup assumes unbiased stochastic gradients with uniformly bounded variance, while heavy-tailed noise need not satisfy the paper’s stronger light-tailed condition.The stated variance assumptions are standard in stochastic optimization.Source: §1.1 · p. 2

1.2 Simple Motivational Example: Convergence in Expectation and Clipping

  • With equal-variance Gaussian, Weibull, and Burr Type XII noise, SGD has identical expectation guarantees but substantially larger oscillations for the heavy-tailed cases.Clipping limits stochastic-gradient norms and yields less oscillatory trajectories without spoiling the convergence rate in the example.Source: §1.2 · pp. 2–3, Figure 1 · p. 2

1.3.1 Smooth Stochastic Optimization: Light-Tailed Noise

  • In light-tailed settings, high-probability complexity bounds for SGD and AC-SA differ from expectation bounds only by logarithmic factors in 1/β.The cited results extend across convex and strongly convex settings.Source: §1.3.1 · p. 3

1.3.2 Smooth Stochastic Optimization: Heavy-Tailed Noise

  • Without light tails, Markov-based confidence dependence can be O(1/β²) or O(1/β), while classical alternatives trade worse ε-dependence for O(ln(β⁻¹)) dependence.Prior robust mirror-descent and proxBoost approaches address parts of the gap, but impose bounded-domain or auxiliary-optimization limitations.Source: §1.3.2 · p. 3

1.4 Our Contributions

  • For convex L-smooth objectives, clipped-SSTM achieves a heavy-tailed-noise complexity bound that outperforms known bounds and matches AC-SA up to logarithmic factors.The analysis does not require a bounded optimization domain.Source: §1.4 · p. 4, Table 1 · p. 4
  • For strongly convex objectives, restarted clipped-SSTM improves the state-of-the-art dependence on ln L/µ, while clipped-SGD gains first high-probability guarantees in convex and strongly convex cases.The clipped-SGD bounds are described as comparable to their light-tailed counterparts; the restarted strongly convex version is R-clipped-SGD.Source: §1.4 · p. 4, Table 2 · p. 5
  • Experiments show clipped-SSTM can outperform SGD and clipped-SGD without large batches, and clipping reduces oscillations in SGD and SSTM.The experiments also illustrate the robustness effects of clipping under heavy-tailed noise.Source: §1.4 · p. 4

1.4.1 Relation to [71]

  • Compared with Zhang et al. [71], this work gives high-probability convex and strongly convex guarantees under bounded variance and uses smoothness to accelerate clipping.The paper contrasts this with [71]’s expectation-focused clipped-SGD analysis and more restrictive bounded-gradient-moment assumption.Source: §1.4.1 · pp. 4–5

2 Accelerated SGD with Clipping

Clipped-SSTM combines acceleration with clipped stochastic gradients for convex, L-smooth optimization and establishes high-probability convergence under a heavy-tailed gradient-noise assumption. The section also presents a constant-batch variant with the same oracle complexity.

2 Accelerated SGD with Clipping

  • The method combines weighted accelerated updates with clipped mini-batch gradients, formed by averaging m samples and projecting onto the Euclidean ball of radius λ.Source: §2 · pp. 5–6
  • With probability at least 1−β, clipped-SSTM reaches ε accuracy in O(max{LR0/√ε, σ²R0²/ε²} ln(LR0²/(εβ))) oracle calls.The theorem also gives f(yN)−f(x*)=O(aLR0²/N²), with a=Θ(ln²(N/β)).Source: §2 · p. 6
  • Clipped-SSTM matches AC-SA and Stochastic Similar Triangles Method [16] [22] oracle-call rates up to constants and logarithmic factors while allowing gradients satisfying only (2), including heavy-tailed noise.Source: §2 · p. 6
  • When variance is large, iteration-dependent batches can become costly; Corollary 2.2 gives the same oracle complexity with constant batch sizes under a suitable stepsize.The text notes that the large-batch requirement can scale as mk∼k²N for last iterates.Source: §2 · p. 6

3 SGD with Clipping

Clipped-SGD achieves high-probability convergence for smooth convex optimization using clipped stochastic gradients. Its oracle complexity is non-trivial without a light-tailed noise assumption or a bounded optimization domain.

3 SGD with Clipping

  • Each iteration averages fresh i.i.d. sample gradients, clips the resulting gradient at λ, updates by a step of size γ, and outputs the average iterate.The algorithm uses xk+1=xk−γ clip(∇f(xk,ξk),λ).Source: §3 · p. 7
  • O(max{LR0^2/ε, σ^2R0^2/ε^2} ln(LR0^2/(εβ))) oracle calls suffice for f(x̄N)−f(x*)≤ε with probability at least 1−β.Theorem 3.1 assumes convex, L-smooth f and uses λ=Θ(LR0), batch size m=Θ(max{1, Nσ^2/(R0^2L^2) ln(N/β)}), and γ=1/(80L ln(4N/β)).Source: §3 · p. 7
  • The result is the first non-trivial high-probability complexity guarantee for clipped-SGD; up to logarithmic factors it recovers light-tailed SGD and RSMD bounds, without ’s bounded-domain assumption.The authors describe the proof technique as similar to that used for Theorem F.1.Source: §3 · p. 7

4 Numerical Experiments

Logistic-regression experiments on three LIBSVM datasets examine gradient-norm distributions and compare SGD, clipped-SGD, SSTM, and clipped-SSTM. Clipped-SSTM’s observed convergence and oscillation behavior varies by dataset, while clipping can stabilize SGD oscillations.

Gradient distributions

  • The gradient-norm histograms suggest Gaussian-like, non-heavy tails for heart, but outliers and heavier tails for diabetes and australian.The histograms show norms of individual gradients at an approximate solution, with empirically fitted normal densities overlaid.Source: §4 · p. 7, Figure 2 · p. 7

Numerical results

  • Clipped-SSTM converges faster than SGD and clipped-SGD on heart and australian, and faster than SGD on diabetes, where it oscillates more if B is not fine-tuned.On heart and australian it oscillates little; its convergence rate is comparable to SSTM, while it suffers less from SSTM’s oscillations.Source: Figure 3 · p. 8, Figure 4 · p. 8, Figure 5 · p. 8
  • Periodically decreasing clipping stabilizes SGD oscillations even from a high initial clipping level, whereas clipped-SGD with too large a level behaves like SGD.The decreasing schedule multiplies the clipping level by α after every l epochs, or equivalently every ⌈rl/m⌉ iterations.Source: §4 · p. 8
  • With small batch sizes, SSTM oscillates much more than SGD, a typical drawback of accelerated SGD with fast error/noise accumulation [35]; clipped-SSTM suffers less from this drawback.Deterministic accelerated and momentum-based methods can also behave non-monotonically.Source: §4 · p. 8
  • SGD oscillates little on heart but more on diabetes, consistent with the gradient noise being better concentrated near its mean on heart; australian shows no oscillations because SGD does not reach the solution region.Tests with a larger stepsize reach the australian oscillation region, where SGD oscillates more and clipping fixes the issue without spoiling convergence rate.Source: Figure 2 · p. 7, §4 · pp. 8–9, Figure 4 · p. 8

5 Discussion

The discussion presents clipped-SSTM and clipped-SGD high-probability complexity results for heavy-tailed stochastic optimization, while noting limitations in problem scope and directions for extension.

5 Discussion

  • The paper establishes first accelerated high-probability bounds for smooth convex optimization without light-tail assumptions, extends results to strongly convex problems, and derives bounds for clipped-SGD in both cases.The authors also report a numerical study of the considered methods.Source: §5 · p. 9
  • The approach relies on problems over R^n, excludes regularized or composite settings, and leaves general nonsmooth extensions open.The cited analyses require bounded domains or strong convexity [7]; the authors suggest adapting the approach with a technique from.Source: §5 · p. 9

Broader Impact … C Basic Facts

The block says a broader-impact discussion is inapplicable because the contribution is primarily theoretical, then supplies optimization conventions, related-work context, and proof facts.

Broader Impact

  • The authors state that a broader-impact discussion is not applicable because their contribution is primarily theoretical.Source: Broader Impact · p. 9

A Notations and Definitions

A Notations and Definitions; C Basic Facts

  • The paper measures stochastic-oracle complexity as calls needed for ε accuracy with probability at least 1−β, defines R0 from start-to-solution distance, and lists variance decomposition for bounded-second-moment vectors.Source: A Notations and Definitions · p. 15, C Basic Facts · p. 17

B.1 Related Work on Non-Smooth Stochastic Optimization

  • Under light tails, prior high-probability bounds for SGD and restarted-SGD differ from their expected-complexity bounds only by logarithmic factors in 1/β.Source: §B.1 · p. 16
  • For heavy-tailed non-smooth problems, Markov-based bounds worsen confidence dependence, while [15] gives unproved complexity bounds under power-law gradient tails for SGD and restarted-SGD.Source: §B.1 · p. 16

B.2 Related Work on Gradient Clipping

  • Prior work describes clipped-SGD as robust near steep cliffs [56]; Zhang et al. [71] analyze bounded α-moments and report faster convergence in some heavy-tailed real-world tests.Source: §B.2 · p. 16

D Auxiliary Results · D.1 Bernstein Inequality · D.2 About the Sum of i.i.d. Random Variables with Heavy Tails

The appendix gives a Bernstein inequality for martingale differences and reviews classical results for sums of i.i.d. heavy-tailed variables, which feature in the high-probability analysis of clipped methods.

D.1 Bernstein Inequality

  • Lemma D.1 states a Bernstein inequality for martingale differences with zero conditional mean given their predecessors.Source: §D.1 · p. 17
  • The lemma assumes increments are bounded, with ∥Xi∥2 ≤ c almost surely for a deterministic constant c > 0.Source: §D.1 · p. 17

D.2 About the Sum of i.i.d. Random Variables with Heavy Tails

  • The section presents classical results for sums of i.i.d. heavy-tailed variables, which play a central role in high-probability convergence analysis of clipped-SSTM and clipped-SGD.Source: §D.2 · p. 17
  • The variables are assumed i.i.d. with E[ξk] = 0 and variance σ2.Source: §D.2 · p. 17
  • Their upper-tail probability satisfies V(s) = P{ξk ≥ s} = Θ(s^-α), with α > 2.Source: §D.2 · p. 17
  • The section notes that this observation can aid complexity results for nonsmooth convex optimization with heavy-tailed stochastic gradients [15].Source: §D.2 · p. 18

E Technical Results … F.3.2 Proof of Lemma F.5

The appendix states high-probability convergence guarantees for clipped-SSTM and its restarted strongly convex variant, then outlines and supplies proof details based on clipping and concentration arguments.

E Technical Results

F Accelerated SGD with Clipping: Exact Formulations and Missing Proofs

F.1 Convex Case

  • To compute a clipped stochastic gradient, the method averages m i.i.d. stochastic gradients and projects the average onto the Euclidean ball of radius λ centered at the origin.Source: §F.1 · p. 19

F.1.1 Convergence Guarantees for clipped-SSTM

  • With constant batch sizes, clipped-SSTM achieves the ε-accuracy guarantee in O(ε^-2 ln(ε^-1β^-1)) iterations, and this rate is optimal up to logarithmic factors when σ² ≥ Lε.The corollary also states that the batch size can be O(1) throughout.Source: §F.1.1 · p. 20

F.1.2 Sketch of the Proof of Theorem F.1

  • The convex-case proof controls clipping bias by choosing the clipping level relative to gradient norms, then applies Bernstein’s inequality and advanced recurrences to bound the stochastic terms.The analysis establishes a high-probability gradient-norm bound and controls the distance sequence by induction.Source: §F.1.2 · pp. 21–22

F.2 Strongly Convex Case

  • For strongly convex problems, R-clipped-SSTM has the same convergence rate as MS-AC-SA and SSTM_sc [16] [22], without assuming sub-Gaussian stochastic gradients, and improves on [7] in dependence on ln(L/µ).Source: §F.2 · p. 23

F.3.1 Proof of Lemma F.4

  • The proof of Lemma F.4 combines the update for zk+1 with convexity and sums the resulting inequalities over iterations.Source: §F.3.1 · pp. 24–26

F.3.2 Proof of Lemma F.5

  • The proof of Lemma F.5 uses the clipped-gradient norm bound, indicator variables, Markov’s inequality, and an L2 triangle inequality to establish its stated bounds.The supplied proof passages describe these steps but omit the displayed inequalities.Source: §F.3.2 · pp. 26–28

F.3.3 Proof of Theorem F.1

The proof establishes the theorem by induction on simultaneous high-probability inequalities, using concentration bounds to control the error terms. It also shows that the iterates remain within expanding balls centered at the optimum.

F.3.3 Proof of Theorem F.1

  • By induction, each iterate x_{k+1}, z_k, and y_k lies in the ball centered at x* with radius eR_k.The argument uses the nested balls and the fact that y_k and x_{k+1} are convex combinations of points in those balls.Source: §F.3.3 · pp. 28–29
  • The proof bounds the error-term sum x + y + z + { + | by δC^2R_0^2 for some δ < 1, using Bernstein’s inequality and bounds on the summands.The x summands are conditionally unbiased and bounded with probability 1.Source: §F.3.3 · pp. 30–31
  • For every k = 0, 1, . . . , N, the induction establishes P{E_k} ≥ 1 − kβ/N, yielding the final event at k = N.The step from E_{T−1} to E_T uses a union bound after controlling the error terms.Source: §F.3.3 · pp. 29, 34

F.3.4 Proof of Corollary F.2 … G.3.2 Proof of Theorem G.2

This section proves high-probability guarantees for clipped stochastic methods, including clipped-SSTM and clipped-SGD and their restarted variants. It covers ε-accuracy in the convex setting and guarantees in the strongly convex setting.

F.3.4 Proof of Corollary F.2

  • For two options for a, clipped-SSTM returns yN with f(yN) − f(x*) ≤ ε with probability at least 1 − β; each iteration requires O(1) oracle calls.Source: §F.3.4 · pp. 35–36

F.3.5 Proof of Corollary F.3

  • The proof combines the a = a′ case, covered by Theorem F.1, with the Corollary F.2 case to establish Corollary F.3.The two cases are combined using a = max of the relevant thresholds.Source: §F.3.5 · p. 37

F.3.6 Proof of Theorem F.6

  • For R-clipped-SSTM, the proof replaces R₀ by its upper bound R and uses strong convexity to show ε-accuracy with probability at least 1 − β after restarts.It also derives the total iteration count and stochastic first-order oracle-call count for the restarted method.Source: §F.3.6 · pp. 37–38

F.3.7 Proof of Corollary F.7

  • Under Corollary F.7’s assumptions, the proof establishes ε-accuracy with probability at least 1 − β and shows O(1) oracle calls per iteration.The proof also derives the total iteration count from a consistent system of conditions on a and N₀.Source: §F.3.7 · p. 38

G SGD with Clipping: Exact Formulations and Missing Proofs

G.1 Convex Case

  • For convex L-smooth objectives, clipped-SGD has a non-trivial complexity guarantee for convergence with high probability, established as a first result of this kind for the method.The theorem states ε-accuracy with probability at least 1 − β after N iterations under its stated conditions.Source: §G.1 · p. 39

G.2 Strongly Convex Case

  • For strongly convex objectives, R-clipped-SGD achieves ε-accuracy with high probability and matches restarted RSMD’s complexity up to logarithmic factors without requiring a bounded set, but it requires knowing µ.The non-restarted clipped-SGD bound is worse by an extra L/µ factor in one term, though it is the first non-trivial high-probability complexity result for that method in this case.Source: §G.2 · pp. 40–41

G.3.1 Proof of Theorem G.1

  • The convex-case proof uses induction to control the iterates’ error events, applies Bernstein’s inequality to bounded martingale differences, and combines the bounds with a union bound.This yields the theorem’s final high-probability guarantee.Source: §G.3.1 · pp. 41, 43, 45
  • Clipped-SGD achieves f(¯x_N) − f(x*) ≤ ε with probability at least 1 − β after the stated iteration bound.The supplied bound fragment does not expose the complete iteration expression.Source: §G.3.1 · pp. 45–46

G.3.2 Proof of Theorem G.2

  • For the first restart run, the proof applies Theorem G.1 using R in place of R0, then uses strong convexity and induction to establish simultaneous bounds across restarts.The simultaneous inequalities hold with probability at least 1 − β.Source: §G.3.2 · p. 46
  • Restarted clipped-SGD produces a point ˆx_τ with f(ˆx_τ) − f(x*) ≤ ε with probability at least 1 − β, and the proof gives iteration and oracle-call bounds.The supplied passages do not expose the complete expressions for those bounds.Source: §G.3.2 · p. 46

G.3.3 Proof of Theorem G.3 · H Extra Experiments

The proof establishes a high-probability convergence guarantee for clipped-SGD in the strongly convex case. It uses an inductive probability argument and concentration bounds to control the optimization error.

G.3.3 Proof of Theorem G.3

  • By induction, for each k = 0, 1, ..., N, the event E_k, where the inequalities hold simultaneously for t = 0, 1, ..., k, has probability at least 1 − kβ/N.The base case E_0 has probability 1; the induction step uses L-smoothness.Source: §G.3.3 · pp. 47, 52
  • The proof bounds x, y, z, {, and | so their sum is controlled by the decaying term (1 − γµ)^T r0.It summarizes the bounds and uses the assumptions on mk and γ to complete the induction step.Source: §G.3.3 · pp. 48, 51
  • For the z term, the proof uses conditionally independent summands with bounded values and applies Bernstein’s inequality to obtain an upper bound.The broader argument also introduces bounded random variables and prepares a Bernstein inequality for the error decomposition.Source: §G.3.3 · pp. 48, 50
  • A union bound combines the induction-step events to establish the probability guarantee for the final iterate.This closes the proof that P{Ek} ≥ 1 − kβ/N holds through k = N.Source: §G.3.3 · pp. 51–52
  • With probability at least 1 − β, f(xN) − f(x*) ≤ 2 exp(−γµN)(f(x0) − f(x*)).The proof also gives f(xN) − f(x*) ≤ 2(1 − γµ)^N(f(x0) − f(x*)).Source: §G.3.3 · p. 52
  • Clipped-SGD achieves f(xN) − f(x*) ≤ ε with probability at least 1 − β.The supplied passage does not include the iteration count after which this guarantee holds.Source: §G.3.3 · p. 52

H.1 Detailed Description of Experiments from Section 1.2

Experiments compare SGD and clipped-SGD under Gaussian, Weibull, and Burr Type XII gradient noise with matched variance. Across 10 runs, SGD oscillates more under Weibull and Burr noise, while clipped-SGD remains robust across all three distributions.

H.1 Detailed Description of Experiments from Section 1.2

  • The test problem is µ-strongly convex and L-smooth with µ = L = 1, and its random noise has zero mean and bounded variance.Its stochastic gradient is ∇f(x, ξ) = x + ξ.Source: §H.1 · p. 53
  • The experiments compare three noise distributions with the same variance because SGD’s expected-convergence bound alone does not guarantee a non-trivial high-probability bound.The distributions are Gaussian, Weibull [69], and Burr Type XII. The Weibull experiment uses c = 0.2; the Burr experiment uses c = 1 and d = 2.3, with shifts and scales chosen for zero mean and variance matching.Source: §H.1 · pp. 53–54
  • Across 10 runs, SGD has larger oscillations under Weibull and Burr noise than Gaussian noise, while clipped-SGD remains robust across all three distributions.The experiments used n = 100, stepsize γ = 0.001, and clipping threshold λ = 100 for clipped-SGD; Figure 6 shows two independent runs.Source: Figure 6 · p. 54, §H.1 · p. 54

H.2 Additional Details and Experiments with Logistic Regression

The additional logistic-regression experiments compare clipped methods with SGD across datasets and examine stochastic-gradient noise. They report reduced oscillation or noise accumulation with clipping, alongside dataset-dependent performance and noise distributions.

H.2 Additional Details and Experiments with Logistic Regression

  • The experiments treat logistic regression as a convex, L-smooth finite-sum problem, with uniformly sampled instances and datasets from LIBSVM.Here L = λmax(A⊤A)/4r.Source: §H.2 · p. 55, Table 3 · p. 55
  • For the australian dataset, gradient-noise histograms resemble those in Figure 2, supporting its earlier insights, but SGD with γ = 1/L did not reach the suboptimality needed to oscillate.Figure 11 compares the observed gradient-noise histograms with synthetic Gaussian samples.Source: §H.2 · p. 55, Figure 11 · p. 58
  • On australian, clipped-SGD and d-clipped-SGD avoid SGD’s significant oscillations while converging at the same rate; clipped-SSTM performs slightly better.With γ = 1/L, SGD did not reach the suboptimality needed to oscillate; with the larger stepsize, its noise histograms indicate heavy-tailed stochastic gradients.Source: §H.2 · pp. 55–56, Figure 12 · p. 59, Figure 13 · p. 59
  • On larger datasets, clipped-SSTM avoids SSTM’s noise accumulation, matches SGD on a9a, and performs much better on w8a.The accompanying histograms show sub-Gaussian-like stochastic gradients at the a9a optimum but heavy-tailed gradients for w8a.Source: §H.2 · p. 57, Figure 14 · p. 59

Related papers

Loading 2005.10785v2…