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 noise makes stochastic-gradient methods less robust, and expectation guarantees may not capture their behavior. The paper introduces clipped-SSTM, extends it to strongly convex problems, and derives high-probability guarantees without light-tailed assumptions. It also develops high-probability results for clipped-SGD and reports improved strongly convex complexity bounds.

  • Problem

    Heavy-tailed stochastic-gradient noise can make SGD poorly behaved, while existing high-probability results are weaker than light-tailed guarantees.

  • Method

    The paper combines accelerated stochastic gradient descent with stochastic-gradient clipping in clipped-SSTM, then uses restarts for strongly convex objectives.

  • Results

    The paper proves the first accelerated high-probability complexity bounds for smooth convex optimization without light-tailed noise assumptions and extends guarantees to strongly convex clipped-SSTM and clipped-SGD.

  • Takeaways & Limitations

    Clipping provides high-probability complexity guarantees for accelerated and non-accelerated stochastic methods under heavy-tailed gradient noise.

  • Takeaways & Limitations

    The approach relies substantially on optimization problems defined on R^n and does not address regularized, composite, or generally non-smooth problems.

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

Heavy-tailed stochastic-gradient noise can make SGD oscillatory and poorly captured by expectation guarantees. The paper develops clipped accelerated methods with high-probability complexity bounds under heavy tails, extending results to strongly convex optimization and clipped-SGD.

  • Motivation: Heavy-tailed stochastic gradients make SGD less robust, while expectation-based rates may fail to describe its practical behavior.The paper motivates high-probability analysis because heavy-tailed noise can produce large deviations and oscillations near the solution.
  • Motivation: SGD exhibits substantially larger oscillations for Weibull and Burr Type XII noise than for Gaussian noise despite identical variance.The motivational example uses the same starting point, stepsize, batchsize, and variance across the three noise distributions.
  • Clipping: Gradient clipping limits updates caused by stochastic gradients with unusually large norms, producing the clipped-SGD method.The update rescales gradients above clipping level λ while leaving smaller gradients unchanged.
  • Contributions: Restarted clipped-SSTM extends the approach to strongly convex objectives, with bounds outperforming the cited state-of-the-art result in dependence on ln L/µ.The method retains comparable complexity to optimal strongly convex stochastic methods without requiring light-tailed stochastic gradients.
  • Contributions: The paper also establishes the first high-probability complexity guarantees for clipped-SGD in convex and strongly convex settings without light-tailed noise assumptions.The convex guarantee is comparable to the light-tailed SGD bound, and the restarted strongly convex version is comparable to its light-tailed counterpart.

2 Accelerated SGD with Clipping

Clipped-SSTM combines accelerated stochastic optimization with gradient clipping for smooth convex problems, attaining high-probability complexity comparable to optimal stochastic methods under heavy-tailed noise.

  • Method: Clipped-SSTM applies a clipped stochastic gradient within an accelerated Stochastic Similar Triangles Method for convex, L-smooth objectives.The method uses mini-batched gradients, clips them at an iteration-dependent threshold, and updates accelerated iterates.
  • Method: The method forms a mini-batched stochastic gradient, projects it onto an origin-centered Euclidean ball, and uses the clipped result in the accelerated update.Fresh samples are averaged before clipping, after which the clipped gradient updates z and the output sequence y.
  • Convergence guarantee: f(yN) − f(x∗) = O(aLR2_0/N2) holds with probability at least 1 − β after N iterations under the theorem’s parameter choices.The bound uses B = Θ(R0/ln(N/β)) and a = Θ(ln^2(N/β)).
  • Complexity: O(max{LR2_0/ε, σ2R2_0/ε2} ln(LR2_0/εβ)) oracle calls suffice for an ε-solution with probability at least 1 − β.This matches the oracle-call complexity of optimal stochastic methods up to constants and logarithmic factors.
  • Complexity: The complexity matches light-tailed optimal methods up to constants and logarithmic factors while requiring only the paper’s weaker stochastic-gradient assumption.The result applies even when the stochastic gradient has a heavy-tailed distribution.
  • Computational trade-off: When σ2 is large, the basic policy requires batchsizes proportional to ε^-3/2 for the last iterates, making individual iterations potentially expensive.A constant-batchsize stepsize policy is presented separately to remove this drawback while preserving the same oracle complexity.

3 SGD with Clipping

Clipped-SGD provides high-probability convergence for convex smooth optimization with clipped mini-batched gradients, extending non-trivial guarantees to settings without light-tailed noise assumptions.

  • Method: Clipped-SGD averages fresh mini-batched stochastic gradients, clips the average, and performs a standard gradient update before averaging iterates.The algorithm uses constant stepsize and clipping level parameters.
  • Convergence guarantee: With λ = Θ(LR0), constant batchsize m, and γ = 1/(80L ln(4N/β)), the method satisfies a high-probability convergence theorem.The theorem assumes convexity and L-smoothness and requires ln(4N/β) ≥ 2.
  • Convergence guarantee: f(¯xN) − f(x∗) ≤ ε holds with probability at least 1 − β after the theorem’s stated number of iterations or oracle calls.The output is the average iterate ¯xN.
  • Complexity: O(max{LR2_0/ε, σ2R2_0/ε2} ln(LR2_0/εβ)) oracle calls recover the light-tailed SGD and RSMD complexity up to logarithmic factors.The comparison is made for the convex case.
  • Contribution: The result is presented as the first non-trivial high-probability complexity guarantee for clipped-SGD without assuming light-tailed noise.Unlike one cited prior result, it does not assume the optimization problem is defined on a bounded set.

4 Numerical Experiments

Experiments examine gradient-tail behavior and compare SGD, clipped-SGD, SSTM, and clipped-SSTM on three logistic-regression datasets. Clipping stabilizes trajectories, while clipped-SSTM often combines accelerated convergence with reduced oscillations.

  • Experimental setup: The experiments evaluate clipped-SSTM and clipped-SGD on LIBSVM logistic-regression datasets using tuned constant batch sizes, step sizes, and clipping levels.A periodically decreasing clipping level is also tested for clipped-SGD.
  • Gradient distributions: Gradient-norm histograms suggest Gaussian-like tails for heart, whereas diabetes and australian contain outliers indicating heavier-tailed distributions.The histograms use empirically fitted normal-density curves for comparison.
  • Clipping effects: d-clipped-SGD stabilizes SGD oscillations even with a high initial clipping level, while an overly large fixed clipping level behaves similarly to SGD.The decreasing schedule multiplies the clipping level by α ∈ (0, 1) periodically.
  • Accelerated methods: Clipped-SSTM has less fast noise accumulation than SSTM, comparable convergence rate, and smaller oscillations under the tested small-batch regime.SSTM’s large oscillations are attributed to accelerated noise accumulation with small batch sizes.
  • Dataset comparisons: Clipped-SSTM converges faster than SGD and clipped-SGD on heart and australian, and faster than SGD on diabetes but oscillates more when B is not fine-tuned.The reported behavior differs across datasets and depends on parameter tuning.
  • Dataset comparisons: SGD oscillation patterns correlate with the observed gradient distributions, but australian shows no oscillations because SGD does not approach the solution in functional value.Additional larger-step-size tests reportedly reveal stronger oscillations in the relevant region.

5 Discussion

The paper presents accelerated and clipped methods with new high-probability guarantees for heavy-tailed stochastic optimization, while identifying important scope limitations. Its theory covers smooth convex and strongly convex settings without a light-tails assumption, alongside numerical evaluation.

  • Contributions: Clipped-SSTM receives the first accelerated high-probability complexity bounds for smooth convex stochastic optimization without a light-tails assumption.The paper frames this result as closing a gap in the theory.
  • Contributions: The strongly convex extension gives new complexity bounds that outperform state-of-the-art results.The supplied passage does not provide the numerical form of the improvement.
  • Contributions: The paper also derives first high-probability complexity bounds for clipped-SGD in convex and strongly convex cases and conducts numerical experiments.The contribution extends beyond the accelerated method.
  • Limitations: The approach relies substantially on defining the optimization problem on Rn and does not address regularized or composite problems.The discussion also identifies general non-smooth extensions as an open direction.

Broader Impact

The supplied material defines the paper’s smooth and strongly convex optimization setting, stochastic-gradient access, probability notation, and complexity criterion. It also contrasts light-tailed and heavy-tailed regimes and summarizes related bounds and clipping results.

  • Problem setting: The problem uses a smooth convex objective accessible only through unbiased stochastic gradients with uniformly bounded variance.The smoothness and stochastic-gradient assumptions are presented as standard in stochastic optimization.
  • Definitions: Strong convexity is defined on Rn with parameter µ ≥ 0, while complexity counts stochastic first-order oracle calls needed to reach ε accuracy with probability at least 1 − β.R0 denotes the initial distance to a solution in the complexity bounds.
  • Related work: Under heavy-tailed noise, existing high-probability bounds for SGD and restarted-SGD have substantially worse dependence on confidence β than light-tailed bounds.The supplied discussion contrasts logarithmic dependence with β^-2 and β^-1 dependence.
  • Related work: Prior work describes clipped-SGD as robust to stochastic-gradient noise, with expectation guarantees under bounded α-th moments for some α ∈ (1, 2].Numerical tests in that work reportedly found faster clipped-SGD convergence than SGD in some heavy-tailed real-world problems.
  • Auxiliary tools: The paper’s proof toolkit includes variance decomposition and Bernstein’s inequality for bounded martingale differences.These results are listed among the basic facts used repeatedly in the proofs.

D Auxiliary Results

The auxiliary section reviews heavy-tailed sums and explains their role in high-probability convergence analyses for clipped-SSTM and clipped-SGD. It distinguishes central-limit and heavy-tailed regimes for polynomial-tail distributions.

  • Regimes: The resulting bounds contain a Central Limit Theorem regime and a heavy-tailed regime, represented by different terms in the maximum.The two regimes are identified according to the tail behavior of the sum.
  • Heavy-tailed sums: Sums of i.i.d. heavy-tailed random variables play a central role in the high-probability analyses of clipped-SSTM and clipped-SGD.The reviewed variables are centered, have variance σ^2, and satisfy polynomial tail behavior with exponent α > 2.
  • Implication: These distributional facts support complexity analyses for non-smooth convex optimization under heavy-tailed stochastic gradients.The auxiliary discussion connects the observation to prior work on non-smooth convex optimization.

E Technical Results

The paper gives high-probability convergence results for clipped-SSTM in convex and strongly convex settings under heavy-tailed noise, with alternative batchsize policies and restarts.

  • Convex case: Clipped-SSTM achieves ε-accuracy with probability at least 1 −β under the theorem’s stated smooth convex assumptions.The convergence statement is provided through the main theorem and its parameter choices.
  • Practical considerations: The analysis uses large multiplicative constants, and large σ2 can require batchsizes proportional to ε−3/2 at the final iterates.The paper notes that these constants can be tuned in practice and introduces alternative stepsize policies to reduce high per-iteration cost.
  • Batchsize policies: With constant batchsizes, clipped-SSTM attains an ε−2 ln(ε−1β−1) rate and uses O(1) stochastic-gradient samples per iteration.When σ2 ≥Lε, this rate is optimal up to logarithmic factors and recovers the RSMD rate.
  • Batchsize policies: An increasing-batchsize policy recovers the complexity of Robust Stochastic Mirror Descent while applying to unconstrained optimization on Rn.The corresponding analysis does not require a compact feasible set.
  • Proof strategy: The analysis explicitly tracks clipping-induced bias, magnitude, variance, and distortion through bounds used with Bernstein’s inequality.The preliminary accelerated-method inequality isolates stochastic terms involving clipped mini-batched gradients.
  • Strongly convex case: R-clipped-SSTM extends clipped-SSTM to strongly convex objectives by repeatedly running clipped-SSTM from restarted points.The method is specified as a restarted algorithm with τ runs and N0 iterations per run.
  • Strongly convex case: R-clipped-SSTM matches optimal strongly convex stochastic rates without assuming sub-Gaussian stochastic gradients and improves dependence on ln L relative to a cited result.The paper also reports comparable bounds to restarted-RSMD and proxBoost when σ2 is large.

F.3.4 Proof of Corollary F.2

This proof treats two stepsize cases for clipped-SSTM and establishes high-probability ε-convergence, including a constant-batchsize regime with O(1) oracle calls per iteration.

  • Stepsize cases: The proof considers two alternative choices for the stepsize parameter a, selected according to the relation between N, β, and the theorem’s threshold.The cases correspond to medium-batchsize and constant-batchsize regimes.
  • Constant batchsize: In the constant-batchsize regime, clipped-SSTM obtains an ε-solution with probability at least 1 −β after the stated number of stochastic first-order oracle calls.The supplied proof passages state the guarantee but fragment its displayed complexity expression.
  • Constant batchsize: When a0 = σ LR0 under the stated conditions, each iteration uses O(1) oracle calls.The proof identifies this through mk = O(1) for every iteration.
  • Combined guarantee: The proof combines the two parameter cases by choosing a as the maximum of the corresponding admissible values.The resulting guarantee holds with probability at least 1 −β.

F.3.6 Proof of Theorem F.6

The proof of Theorem F.6 analyzes successive restarted runs of clipped-SSTM and combines their high-probability contraction guarantees to reach ε accuracy.

  • Run analysis: The first restarted run applies the convex clipped-SSTM analysis with the initial radius R replacing its tighter bound.Strong convexity supplies the relation between initial suboptimality and the radius used in the analysis.
  • Probability argument: An induction argument establishes the required inequality for every restart, and the inequalities hold simultaneously with probability at least 1 −β.The proof then derives the final restarted guarantee.
  • Final guarantee: After τ restarts, R-clipped-SSTM produces ˆxτ satisfying f(ˆxτ) −f(x∗) ≤ε with probability at least 1 −β.The number of restarts is tied to the logarithmic reduction from the initial error to ε.
  • Complexity accounting: The proof derives the total iteration and stochastic first-order oracle-call counts from the per-run parameters and batchsizes.The supplied passages state that these quantities are obtained after the restart analysis but do not preserve the full displayed formulas.

G SGD with Clipping: Exact Formulations and Missing Proofs

The clipping analysis establishes the first non-trivial high-probability complexity guarantees for clipped-SGD in convex and strongly convex problems, including restarted variants and their proof mechanism.

  • G.1 Convex Case: In the convex case, clipped-SGD achieves f(¯xN) −f(x∗) ≤ε with probability at least 1 −β after the theorem’s stated number of iterations and oracle calls.The result assumes convexity, L-smoothness, and the theorem’s conditions on N and β.
  • G.1 Convex Case: This is presented as the first non-trivial high-probability complexity guarantee for clipped-SGD.The claim is made for the convex clipped-SGD result.
  • G.2 Strongly Convex Case: R-clipped-SGD obtains a strongly convex high-probability guarantee by repeatedly running clipped-SGD with constant batchsizes and a fixed stepsize.Algorithm 4 restarts clipped-SGD from each intermediate output.
  • G.2 Strongly Convex Case: Theorem G.2 gives f(ˆxτ) −f(x∗) ≤ε with probability at least 1 −β after τ restarted runs and the stated total number of iterations.The guarantee follows under the theorem’s parameter conditions.
  • G.2 Strongly Convex Case: R-clipped-SGD matches the restarted-RSMD complexity up to logarithmic factors and does not require the optimization domain to be bounded.The paper contrasts this with the bounded-set assumption in the cited RSMD result.
  • G.2 Strongly Convex Case: Without restarts, Theorem G.3 also gives a high-probability strongly convex guarantee, but its complexity has an extra L/µ factor relative to R-clipped-SGD.The paper identifies this as a potentially large deterioration.
  • G.3.1 Proof of Theorem G.1: The proof bounds clipped-gradient error terms using conditional unbiasedness, almost-sure boundedness, bounded conditional variances, Bernstein’s inequality, induction, and a union bound.The resulting event guarantees the averaged convex iterate reaches ε accuracy.
  • G.3.3 Proof of Theorem G.3: For the strongly convex non-restarted proof, smoothness and strong convexity yield a recurrence that unrolls into geometric decay of the error.The displayed bound is f(xN) −f(x∗) ≤ 2 exp(−γµN)(f(x0) −f(x∗)).

H.1 Detailed Description of Experiments from Section 1.2

The experiments compare SGD and clipped-SGD on a quadratic problem under Gaussian, Weibull, and Burr Type XII noise with matched variance. Heavy-tailed noise produces larger SGD oscillations, while clipping remains more robust across runs.

  • Experimental setup: The quadratic objective is smooth and strongly convex, with stochastic gradients formed by adding a zero-mean random vector with bounded variance.The setup has µ = L = 1 and uses ξ as the stochastic-gradient noise.
  • SGD baseline: The expected SGD convergence bound depends on the stepsize, condition number, initial suboptimality, and noise variance, but not on the noise distribution.For fixed iteration count, the bound is determined by γ, f(x0) − f(x∗), and σ.
  • Noise-distribution effects: Equal-variance Gaussian, Weibull, and Burr Type XII noises generate substantially larger SGD oscillations for the two heavy-tailed distributions.Expectation-based guarantees are identical across the three distributions and therefore do not capture these trajectory differences.
  • Clipping results: Across 10 independent runs, clipped-SGD behaves more robustly than SGD under Gaussian, Weibull, and Burr Type XII noise without significant oscillations.The experiments use dimension n = 100, stepsize γ = 0.001, and clipping level λ = 100.

H.2 Additional Details and Experiments with Logistic Regression

Additional logistic-regression experiments examine stochastic-gradient noise and compare SGD, clipped variants, SSTM, and clipped-SSTM across several datasets. Clipping reduces oscillations and avoids noise accumulation, with the strongest reported improvement on w8a.

  • Problem and datasets: The logistic-regression objective is convex and L-smooth, with L = λmax(A⊤A)/4r, and is represented as stochastic optimization over uniformly sampled data instances.Experiments use datasets from the LIBSVM library.
  • Experimental configuration: The logistic-regression experiments use tuned method parameters, with dataset-specific batchsizes and clipping settings documented in Table 4.The initial suboptimality f(x0) − f(x∗) was of order 10 in these experiments.
  • Australian dataset: On australian, clipped-SGD and d-clipped-SGD avoid significant oscillations while converging at the same rate as SGD, and clipped-SSTM performs slightly better.SGD achieves better suboptimality with the tested stepsize but oscillates significantly more.
  • Noise diagnostics: The australian noise histograms indicate heavy-tailed stochastic-gradient noise and help explain SGD’s unstable behavior.The histograms compare observed gradient-noise norms with synthetic Gaussian samples and fitted normal densities.
  • Larger datasets: On the larger a9a and w8a datasets, clipped-SSTM avoids the noise accumulation affecting SSTM and matches SGD on a9a while performing much better on w8a.The w8a gradient-noise distribution is heavy-tailed, whereas a9a is described as sub-Gaussian-like at the optimum.
Loading 2005.10785v2…