On the Last-Iterate Convergence of Clipped Gradient Methods

1 Introduction1

• Existing last-iterate SGD guarantees often rely on strong gradient-noise conditions, while the paper frames heavy-tailed noise as a more realistic alternative.The introduction asks whether Clipped-SGD can achieve high-probability last-iterate rates matching its best-known average-iterate bounds.Source: §1 · pp. 1–2
• Clipped-SGD addresses heavy-tailed noise by clipping stochastic gradients before applying the update.Under heavy-tailed noise, SGD may incur poly(1/δ) dependence in high-probability convergence or fail to converge in expectation.Source: §1 · p. 2

1.2 Related Work

• The cited prior last-iterate results comprise an in-expectation rate for Lipschitz convex objectives [34] and a high-probability rate for smooth convex objectives, which the paper describes as suboptimal.The latter is worse than the best-known average-iterate rate for the same setting.Source: §1 · p. 2

1.1 Our Contributions

• For convex problems, Clipped-SGD's high-probability last-iterate rates match the best-known average-iterate results for Lipschitz and smooth objectives.The paper cites for Lipschitz functions and for smooth functions.Source: §1.1 · p. 2
• For strongly convex problems, the high-probability last-iterate rates match the best-known average-iterate result for Lipschitz functions and improve the smooth-objective result by removing extra logarithmic factors.The comparisons are with for Lipschitz functions and for smooth functions.Source: §1.1 · p. 2
• The paper describes its Lipschitz-objective rates as optimal in all parameters under classical heavy-tailed noise, while smooth-objective optimality remains unproved.The authors also report refined noise-parameter dependence under the fine-grained condition.Source: §1.1 · p. 2

2 Preliminary

• The paper studies composite optimization over a nonempty closed convex set.The objective is presented in composite form, with component functions f and r.Source: §2 · p. 3
• The analysis assumes convex component functions and a strongly star-convex objective, a condition stated to be weaker than strong convexity.It also treats smooth objectives through an L-smoothness assumption on f.Source: §2 · p. 4
• The fine-grained heavy-tailed noise condition assumes an unbiased stochastic gradient and uses a tail index p in (1, 2].Setting σs and σl equal recovers the classical heavy-tailed noise assumption.Source: §2 · p. 4

3 Last-Iterate Convergence of Clipped Stochastic Gradient Descent

• Clipped-SGD clips each stochastic gradient before applying the update, and this work establishes its first optimal high-probability last-iterate convergence rates under heavy-tailed noise.The algorithm takes the initial point and time horizon as input and chooses a clipping threshold and stepsize at each iteration.Source: §3 · pp. 4–5

3.1.1 Lipschitz Objectives

• For Lipschitz objectives, the general-convex rate matches the best-known high-probability average-iterate rate; under classical heavy-tailed noise, its rate is described as fully optimal in T.Under the fine-grained noise assumption, the rate is optimal in T but may be suboptimal in its noise parameters.Source: §3.1.1 · p. 5

3.1.2 Smooth Objectives

• For smooth objectives, the general-convex result applies under the fine-grained noise assumption and substantially improves over; the leading term is believed optimal, while the noise-parameter dependence may not be.No high-probability lower bound exists in this setting, and the authors conjecture the optimal dependence should be σs.Source: §3.1.2 · p. 6

3.2.1 Lipschitz Objectives

• For strongly star-convex Lipschitz objectives, Theorem 3 gives the first heavy-tailed-noise last-iterate rate, including the previously untreated finite-variance case p = 2.The result fills a gap even when the classical finite-variance noise levels are equal.Source: §3.2.1 · p. 7

3.2.2 Smooth Objectives

• For strongly star-convex smooth objectives, Theorem 4 gives the first and only high-probability function-value last-iterate result and the first bound under the fine-grained noise assumption.Its higher-order term decays polynomially, whereas the corresponding term in decays exponentially.Source: §3.2.2 · p. 8

• The new argument goes beyond standard induction while preserving the optimal poly(ln(1/δ)) dependence on δ.Source: §4 · pp. 8–9
• Standard induction introduces a suboptimal poly(ln(T/δ)) factor into the stepsize and clipping-threshold choices, and consequently into the convergence rate.Source: §4 · p. 9
• The refined argument uses Freedman’s inequality to maintain the event across iterations, yielding Pr[ET+1] ≥ 1 − δ.The passage refers to Lemma 7 for the formal application.Source: §4 · p. 9

• The work proves time-horizon-optimal high-probability last-iterate rates for Clipped-SGD across convex and strongly star-convex objectives, including smooth and nonsmooth settings.The analysis also accommodates composite objectives and constrained optimization, with refined noise-parameter dependence under fine-grained Assumption 5.Source: §5 · p. 9
• Under classical heavy-tailed noise, the bounds are minimax-optimal for Lipschitz objectives, while matching lower bounds for smooth objectives remain open.Source: §5 · p. 9
• The stepsize and clipping threshold require the tail index p, and the current guarantees assume the time horizon T is known in advance.The authors identify adaptation to an unknown tail index and anytime guarantees as future directions.Source: §5 · p. 9

• When µ = 0, the inequality holds automatically, so the proof focuses on µ > 0.Source: A Proof of Lemma 1 · p. 14
• For µ-strongly convex F, the function-value gap bounds the squared distance to the optimum as µ/2 ∥x − x⋆∥² ≤ F(x) − F⋆.Source: A Proof of Lemma 1 · p. 14
• The proof combines the convexity inequality with (4) and then uses (5) and (6) to finish.Source: A Proof of Lemma 1 · p. 14

B Missing Proofs for Theorems

• This appendix section provides missing theorem proofs, with intermediate lemmas proved in Appendix C.Source: B Missing Proofs for Theorems · p. 14
• The notation review identifies δ as the failure probability, p as the tail index, and D as the distance from the initial point to the optimum.Source: B Missing Proofs for Theorems · p. 14

B.1 General Convex Optimization

• The general-convex subsection considers the case µ = 0 in Assumption 2.Source: §B.1 · p. 15

B.1.1 Lipschitz Objectives

• Theorem 5 gives a Clipped-SGD guarantee with probability at least 1 − δ under Assumptions 1, 2 (with µ = 0), 3, and 5, subject to the stated parameter conditions.The supplied statement also specifies a time-dependent stepsize and clipping-threshold choices, but its bound is incomplete here.Source: §B.1.1 · p. 15
• The proof simplifies intermediate bounds using a stepsize proportional to T − t + 1 and a clipping threshold based on max {2G, τ}, then substitutes τ = τ⋆.The displayed passages refer to simplifications of (14)–(17).Source: §B.1.1 · p. 16
• The final derivation combines an earlier result with equation (16) before applying the theorem’s stated constants and conditions.Source: §B.1.1 · pp. 15–16

B.1.2 Smooth Objectives

• Under Assumptions 1, 2 (with µ = 0), 4, 5, and 6, the smooth-objective theorem states a Clipped-SGD guarantee with probability at least 1 − 2δ.The supplied theorem statement includes a condition involving φ_smo and φ⋆, but the complete bound is not present.Source: §B.1.2 · pp. 16, 18
• The smooth-objective proof verifies that its chosen bound parameter satisfies the required inequality by direct verification.Source: §B.1.2 · p. 17

B.2 Strongly Star-Convex Optimization

• The following section considers strongly star-convex optimization, corresponding to µ > 0 in Assumption 2.Source: §B.2 · p. 18

B.2.1 Lipschitz Objectives

• Theorem 7 gives a Clipped-SGD guarantee with probability at least 1 − 2δ under the stated strongly star-convex assumptions.The supplied theorem passages do not include the complete bound.Source: §B.2.1 · p. 18
• For T ≥ 2, the proof views x_T+1 as the output after T − S iterations of Algorithm 1, initialized at x_S+1.Source: §B.2.1 · p. 19
• The proof sets η⋆ = 1/(µT^2) before applying the choices of parameters and the proof of Theorem 5.Source: §B.2.1 · p. 19

B.2.2 Smooth Objectives

• The proof uses a piecewise clipping-threshold schedule that changes at S, with the two branches depending on whether t ≤ S or t > S.Source: §B.2.2 · p. 20
• The proof’s displayed bound restricts D to 0 ≤ D ≤ D̄ = 2G₁/µ and gives Ḡ = L(D̄ + D) + G₁.Source: §B.2.2 · p. 20
• With probability at least 1 − δ, the proof obtains a bound using Ḡ = (1 + 2κ)G₁ and then combines equations (39) and (40).The supplied passages identify Assumption 7 as supporting the derivation.Source: §B.2.2 · p. 22

C Theoretical Analysis

• The theoretical analysis separates the clipped-gradient error into unbiased and biased parts.It also specifies the natural filtration and the information available for the iterates and gradients.Source: C Theoretical Analysis · p. 22

C.1 General Lemmas

• Under Assumption 5, a lemma gives clipping-error bounds for a threshold event defined by τ_t ≥ 2∥∇f(x_t)∥.The paper uses a simplified version of the result proved in, retaining only the inequalities needed here.Source: §C.1 · p. 22
• A one-step descent inequality for Clipped-SGD holds under Assumptions 2 and 3, or Assumption 4 with 0 < η_t ≤ 1/(2L).The lemma is stated for any y in X and t in N; its proof is omitted as standard.Source: §C.1 · pp. 22–23

C.2 Lemmas for General Convex Optimization

• Lemma 4 characterizes last-iterate progress and bounds the squared distance to the optimum at every iterate in the general convex case.It applies under Assumptions 1, 2 with μ = 0, and either Assumption 3 or 4, for positive step sizes.Source: §C.2 · p. 23

C.2.1 Lipschitz Objectives

• For Lipschitz objectives, Lemma 5 bounds the residual term in Lemma 4 with probability at least 1 − δ under Assumptions 3 and 5 and two conditions.The resulting residual bound is used to establish the last-iterate rate.Source: §C.2.1 · p. 26

C.2.2 Smooth Objectives

• For smooth objectives, Lemma 6 bounds a variant of the residual term assuming uniformly bounded distance to the optimum, while Lemma 7 gives a sufficient condition for that boundedness.The analysis addresses the challenge of controlling gradient norms to bound the martingale conditional variance for Freedman’s inequality.Source: §C.2.2 · pp. 28, 31

C.3 Lemmas for Strongly Star-Convex Optimization

• Lemma 8 provides a squared-distance bound for Clipped-SGD in strongly star-convex optimization, under either Lipschitz or smooth objective assumptions.The bound supports the later analysis of last-iterate convergence in function-value gap.Source: §C.3 · pp. 32–33

C.3.1 Lipschitz Objectives

• For Lipschitz objectives, Lemma 9 of bounds the residual term in Lemma 8 with probability at least 1 − δ.The paper specializes a condition from by setting α = 1/2.Source: §C.3.1 · p. 33

C.3.2 Smooth Objectives

• For smooth objectives, the analysis targets control of gradient norms and introduces Lemma 10 using a method analogous to the general-convex smooth case under the weaker Assumption 6.The subsection states Lemma 10’s applicability under Assumptions 1, 4, 5, and 6, but the supplied passage does not include its conclusion.Source: §C.3.2 · p. 34
• The smooth-objective proof combines three inequalities to bound I_str with probability at least 1 − δ.The supplied passages do not include the bound’s full expression.Source: §C.3.2 · pp. 34–35

D Technical Lemmas

• The concentration lemma is stronger than prior inequalities in [25] because it allows σ_t^2 to be random rather than constant.Source: D Technical Lemmas · p. 36

NeurIPS Paper Checklist

• The checklist affirms that theoretical results have complete assumptions and proofs, limitations are discussed, and the paper includes no experiments.Source: NeurIPS Paper Checklist · pp. 38–39
• The paper reports that it releases no new assets.The new-asset documentation question is marked N/A because no new assets are released.Source: NeurIPS Paper Checklist · p. 43
• The paper reports no crowdsourcing or research with human subjects, and marks the related IRB question N/A.The checklist gives the same justification for both declarations.Source: NeurIPS Paper Checklist · p. 43
• The paper reports that LLMs are not an important, original, or non-standard component of its core method development.The LLM-usage declaration is marked N/A on that basis.Source: NeurIPS Paper Checklist · p. 44