PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees

Anastasia Koloskova, Hadrien Hendrikx, Sebastian U. Stich

arXiv:2305.01588v2cs.LGcs.DCmath.OCstat.ML

TL;DR

Clipped-gradient convergence guarantees have often depended on specific thresholds and strong noise assumptions. This paper analyzes deterministic and stochastic settings for arbitrary thresholds, finding that deterministic clipping generally affects only higher-order terms while stochastic clipping yields a tight gradient-norm neighborhood.

  • Problem

    Existing clipping guarantees often require specific threshold values and strong assumptions about stochastic gradient noise.

    Source: §1 · p. 1

  • Method

    The paper separately analyzes deterministic and stochastic clipped-gradient methods and characterizes convergence for arbitrary clipping thresholds.

    Source: §1 · p. 1

  • Results

    Clipped SGD reaches a tight gradient-norm neighborhood of size min{σ, σ2/c}, while deterministic clipping leaves leading convergence terms unchanged except for a substantial slowdown in the strongly convex case.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bounds characterize clipping-induced bias for arbitrary thresholds, rather than requiring convergence to exact critical points under stronger assumptions.

    Source: §5 · p. 9

    Uniform boundedness of stochastic noise is a strong assumption.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

Gradient clipping is a popular modification to standard (stochastic) gradient descent, at every iteration limiting the gradient norm to a certain value $c >0$. It is widely used for example for stabilizing the training of deep learning models (Goodfellow et al., 2016), or for enforcing differential privacy (Abadi et al., 2016). Despite popularity and simplicity of the clipping mechanism, its convergence guarantees often require specific values of $c$ and strong noise assumptions. In this paper, we give convergence guarantees that show precise dependence on arbitrary clipping thresholds $c$ and show that our guarantees are tight with both deterministic and stochastic gradients. In particular, we show that (i) for deterministic gradient descent, the clipping threshold only affects the higher-order terms of convergence, (ii) in the stochastic setting convergence to the true optimum cannot be guaranteed under the standard noise assumption, even under arbitrary small step-sizes. We give matching upper and lower bounds for convergence of the gradient norm when running clipped SGD, and illustrate these results with experiments.

1. Introduction

The paper characterizes how arbitrary clipping thresholds affect deterministic and stochastic convergence. It shows that deterministic clipping generally changes higher-order terms, while stochastic clipping introduces a bias that limits convergence to a neighborhood.

1. Introduction

  • Earlier guarantees often require specific clipping thresholds or strong noise assumptions, although the threshold may be dictated by application constraints such as privacy.The paper aims to let bounds be optimized for c to trade off convergence speed or precision against application-specific requirements.Source: §1 · pp. 1–2
  • Clipping leaves the leading convergence term unchanged in convex and non-convex settings, but the strongly convex transient prevents linear forgetting and causes substantial slowdown.After a transient regime, clipping does not affect the convergence rate.Source: §1 · p. 2
  • Under the heavy-tailed noise assumption, clipped SGD reaches a gradient-norm neighborhood of size min{σ, σ2/c}, and this bound is tight for sufficiently small step-sizes.The analysis quantifies the clipping bias without additional assumptions on the stochastic gradients.Source: §1 · p. 2

1.1. Main assumptions

  • The paper uses (L0, L1)-smoothness, which recovers standard smoothness when L1 = 0 and can cover functions that are not classically smooth when L1 > 0.The authors note that classical smoothness can be restrictive because its constant must capture worst-case smoothness.Source: §1.1 · p. 2

1.2. Related work

  • Prior clipping analyses often combine uniform noise bounds with large thresholds or impose other strong noise conditions, including angle, symmetry, or growing-batch assumptions.The paper instead quantifies clipping-induced drift under bounded variance.Source: §1.2 · pp. 3–4

1.1. Main assumptions

  • The analysis uses bounded variance, a weaker and more standard noise assumption than uniform boundedness, and provides guarantees for any batch size and clipping threshold.Uniform boundedness is described as strong and potentially unrepresentative of real-world settings.Source: §1.1 · p. 3, §1.2 · p. 4

1.2. Related work

  • In the deterministic setting, the paper gives sharper guarantees than prior work by showing that clipping does not affect the leading convergence terms.The related-work discussion contrasts these guarantees with analyses that use specific, sufficiently large clipping thresholds.Source: §1.2 · p. 4

2. Deterministic Setting

With deterministic gradients, clipping changes gradient magnitude but not direction, and its threshold generally changes only higher-order convergence terms. The analysis separates non-convex, convex, and strongly convex behavior, where an initial clipping overhead remains.

2. Deterministic Setting

  • Clipping preserves gradient direction and leaves leading convergence terms unchanged for convex and non-convex objectives, though strongly convex convergence has an initial-condition-dependent slowdown.Source: §2 · p. 4

2.1. Non-convex functions

  • For non-convex objectives, clipped GD permits η ≤ [9(L0+cL1)]^-1; when c exceeds target accuracy ϵ, clipping affects speed only by a constant factor.The c-dependent term is order 1/T, while the leading term is order 1/√T; small c can slow convergence.Source: §2.1 · pp. 4–5

2.2. Convex functions

  • For convex objectives, clipping adds a higher-order slowdown term, avoided by choosing c above Lϵ; clipped GD also allows larger stepsizes.Source: §2.2 · p. 5

2.3. Strongly convex functions

  • Strongly convex objectives incur an initial clipping overhead: steps move at most ηc toward the optimum, then convergence becomes linear after a constant number of iterations.The overhead does not shrink with ϵ; avoiding an effect on convergence speed requires c = O(1/log(1/ϵ)).Source: §2.3 · p. 6

3. Stochastic Functions

Clipping can bias stochastic gradients away from the true gradient, so clipped SGD may not reach the objective’s exact critical points. The paper establishes lower bounds on this error and matching convergence guarantees, including an extension to differentially private SGD.

3. Stochastic Functions

  • Clipped stochastic gradients can have nonzero expected updates even at critical points, and some fixed points of clipped SGD remain at least σ/12 from critical points of f.The paper also establishes that such fixed points can be σ far away for some noise distributions.Source: §3 · p. 6, §3.1 · p. 6

3.1. Unavoidable bias introduced by clipping

  • For small clipping radii, clipped-SGD fixed points can remain at least σ/12 from critical points of f.The lower bound holds for a fixed class with variance at most σ² and specified smoothness parameters.Source: §3.1 · p. 6
  • Increasing the clipping radius can shrink the neighborhood from σ to σ²/c, but cannot eliminate it.Source: §3.1 · p. 6

3.2. Convergence results

  • Clipped SGD’s gradient norm reaches a tight neighborhood of size min{σ, σ²/c} for sufficiently small step sizes, while its unavoidable bias term does not decrease with step size or iteration count.Under expected bounded noise, exact convergence to critical points is not guaranteed.Source: §3.2 · p. 7

3.3. Extension to differentially private SGD

  • The analysis extends to DP-SGD, whose bias is also tight and unavoidable; mini-batching reduces its stochastic-noise term by a factor of B.Source: §3.3 · p. 8

4. Experiments

The experiments examine how clipping thresholds and step sizes affect deterministic and stochastic optimization. Their results show that clipping can preserve or stabilize learning, though very small thresholds can limit stochastic performance.

Experimental setup

  • The experiments use logistic regression on w1a and an artificial quadratic function; the quadratic setup uses L = 0.1 and coordinate-wise χ2(1) noise.The stated goal is to highlight the theoretical results.Source: §4 · p. 9

Deterministic setting

  • At target accuracy 10^-3, all tested clipping thresholds except c = 10^-4 perform relatively well; for error ϵ = 10^-2, c = 10^-3 is inadvisable.These comparisons are for logistic regression on w1a.Source: §4 · p. 9
  • Smaller clipping radii allow larger step sizes, which speeds up deterministic convergence overall.The step size was tuned separately for each clipping radius.Source: §4 · p. 9
  • In the deterministic experiments, clipping does not harm learning when its threshold is not too small relative to target accuracy, and it stabilizes learning.The stabilization allows larger step sizes and faster convergence.Source: §4 · p. 9

Stochastic setting

  • For stochastic clipped SGD, larger learning rates outperform unclipped SGD, but very small clipping thresholds do not match vanilla SGD’s performance.The tested curves are determined by cη, the step size when clipping occurs.Source: §4 · p. 9

5. Conclusion

The conclusion gives tight upper and lower bounds on clipped-SGD bias for arbitrary clipping thresholds and contrasts this analysis with prior work using stronger assumptions. It also points to extensions involving other algorithms and privacy applications.

5. Conclusion

  • The paper tightly characterizes clipped-SGD bias with matching upper and lower bounds for any clipping threshold.The conclusion contrasts this with prior work focused on exact convergence under strong assumptions, often for a fixed threshold.Source: §5 · p. 9
  • The paper identifies extensions to accelerated or momentum methods and FedAvg, and potential applications to privacy-guarantee analysis using clipped SGD.The conclusion frames these as directions the work can support.Source: §5 · p. 9

B. Deterministic proofs

  • The deterministic proofs section skips the non-convex proof, stating that it follows directly from the stochastic result.Source: B. Deterministic proofs · p. 12

B.1. Convex case (Theorem 2.3)

The convex-case proof separates iterations where clipping occurs from those where it does not, then uses smoothness and convexity to bound convergence. It derives a function-suboptimality bound with a threshold-dependent higher-order term.

B.1. Convex case (Theorem 2.3)

  • The proof handles clipped and unclipped iterations as separate cases, using α_t = min{1, c∥∇f(x_t)∥} to distinguish the regimes.Source: §B.1 · p. 12
  • Smoothness and convexity bound the gradient norm by function suboptimality, while the stepsize condition controls descent in the clipped case.The proof uses ∥∇f(x_t)∥² ≤ 2(L0 + L1c)(f(x_t) − f⋆) and a sufficient stepsize condition.Source: §B.1 · pp. 12–13
  • The cited passage states the function-suboptimality bound as f(x_T) − f⋆ ≤ 2R0²/(η(T + 1)) + 4LR0⁴/(η²c²(T + 1)²), without specifying a case classification.Source: §B.1 · p. 13

B.2. Strongly convex case (Theorem 2.5)

The strongly convex proof compares a transient bound with a later regime in which clipping stops and standard linear convergence applies. The relative clipping threshold and problem parameters determine which rate is preferable.

B.2. Strongly convex case (Theorem 2.5)

  • The recursive argument first applies the convex result, then separately considers the small-gradient regime before establishing the later no-clipping phase.Source: §B.2 · p. 14
  • Once clipping stops after t0, the proof obtains the standard linear convergence rate and a final convergence-time bound.Source: §B.2 · p. 14
  • Neither of the two rates is always better; the proof selects between them based on c relative to √(L/µ)R0.Source: §B.2 · p. 14

C. Stochastic proofs.

The proof first establishes convergence up to σ, then refines the argument for large c. A simple lemma is identified as the core of the decomposition.

C. Stochastic proofs.

C.1. Preliminaries

  • Lemma C.1 is presented as a simple result at the core of the proof’s decomposition.Source: §C.1 · p. 14
  • Lemma C.1 states a relation for any α > 0 and u ∈ R^d, involving ∇f(x), α, and u.Source: §C.1 · p. 14

C.2. First part of the proof: convergence up to σ (small c)

For small clipping thresholds, the proof targets convergence of the gradient norm to a level σ. It treats both almost-sure bounded noise and variance bounded in expectation.

C.2. First part of the proof: convergence up to σ (small c)

  • For c < 4σ, the proof establishes convergence of the gradient norm up to level σ.Source: §C.2 · p. 15
  • Under strong variance, the stochastic-gradient deviation is bounded by 3σ with probability one.Source: §C.2 · p. 15
  • The supplied passage specifies choosing step-size η ≤ (4[L0 + cL1])^-1, but states no strong-variance condition.Source: §C.2 · p. 15
  • For bounded variance in expectation, the proof uses an indicator for deviations above 3σ and conditional expectations.Source: §C.2 · p. 15
  • The passage gives the step-size condition η ≤ (9[L0 + cL1])^-1, stating that with this bound, the ensuing result is obtained.Source: §C.2 · p. 16

C.3. Second part of the proof: convergence up to σ2/c (large c).

For c ≥ 4σ, the proof divides the analysis by the full gradient’s size relative to c. In the small-gradient case, the bound retains a bias term even as the step-size shrinks.

C.3. Second part of the proof: convergence up to σ2/c (large c).

  • For c ≥ 4σ, the proof handles cases according to whether the full gradient is clipped or lies below c.Source: §C.3 · pp. 16, 19
  • When the full gradient exceeds c, the proof uses α = c / ∥∇f(xt)∥ so that α∇f(xt) equals its clipped value.Source: §C.3 · p. 16
  • In the case ∥∇f(xt)∥ < c/2, the proof does not obtain convergence to the exact optimum.Source: §C.3 · p. 17
  • 1/8 ∥∇f(xt)∥² is bounded by the one-step expected decrease divided by η, plus η(L0 + cL1)σ² and 4σ⁴.Source: §C.3 · p. 18
  • The resulting bound has a variance term that fades with the step-size and a bias term that remains even for very small step-sizes.Source: §C.3 · p. 19

C.4.1. MODIFICATION TO THE PROOF TO INCLUDE MINI-BATCHES

The mini-batch proof tightens the variance term to reflect batch size B. It substitutes σ²/B for σ² in the preceding argument to obtain a convergence rate.

C.4.1. MODIFICATION TO THE PROOF TO INCLUDE MINI-BATCHES

  • The proof tightens the variance term to capture variance reduction from batch size B.Source: §C.4.1 · p. 20
  • The modification substitutes σ²/B for the σ² term in the preceding proof.Source: §C.4.1 · p. 20
  • After this substitution, the proof obtains a convergence rate for mini-batches.Source: §C.4.1 · p. 20

C.4.2. MODIFICATION TO THE PROOF TO INCLUDE STOCHASTIC NOISES

The appendix modifies the proof’s first step to account for Gaussian noise in DP-SGD, while keeping the rest of the proof structure. It also begins a Bernoulli-noise construction for a lower bound.

C.4.2. MODIFICATION TO THE PROOF TO INCLUDE STOCHASTIC NOISES

  • Adding Gaussian noise to DP-SGD gradients requires changing the first proof step to use (L0, L1) smoothness; the rest of the proof remains the same, with an additional σ_DP^2 term in the convergence rate.The passage defines L = L0 + max_t ||∇f(x_t)||_L1 for that rate.Source: §C.4.2 · p. 20

C.5. Lower bound

  • The lower-bound proof introduces noise aB(p), where a > 0 and B(p) is Bernoulli with mean p ≤ 1/2.It uses a function whose stochastic gradients are then specified in the proof.Source: §C.5 · p. 20
  • At x = −pc/(1−p), one Bernoulli outcome is not clipped, and the expected clipped stochastic gradient is zero.For the zero outcome, |x| = pc/(1−p) ≤ c; the passage gives E[clip_c(∇f_ξ(x))] = 0.Source: §C.5 · p. 20
  • The proof treats c ≤ 2σ and σ ≤ c ≤ a/2 regimes, then chooses a = 2c to satisfy the previous conditions.In the large-c regime, it also derives p ≤ 1/4 from p < 1/2 and c ≤ a/2.Source: §C.5 · p. 21
Loading 2305.01588v2…