- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies high-probability convergence of standard clipped SGD under heavy-tailed stochastic gradient noise and ((L_0,L_1))-smoothness. Its main contribution is a convex convergence guarantee that avoids exponential dependence on (L_1R_0), assuming unbiased gradients with a bounded central (\alpha)-th moment for (\alpha\in(1,2]). A directional clipping-bias bound allows part of the bias to be absorbed into the optimization progress. The paper also provides a computable output obtained by averaging iterates whose observed gradients are not clipped, and a lower bound matching the convex stochastic rate up to logarithmic factors for fixed-parameter Clip-SGD. An additional nonconvex analysis recovers known deterministic and classical-smooth iteration rates. Validation is entirely theoretical, through upper bounds, lower-bound constructions, and comparisons with existing guarantees; no numerical experiments are provided.
Critical strengths
1.The convex result addresses a meaningful gap for the standard algorithm. Existing guarantees under generalized smoothness either impose stronger noise assumptions, change the sampling scheme, or risk exponentially large constants when reduced to classical smoothness. Analyzing the same stochastic gradient for both clipping and updating under only a bounded central moment is a substantive extension. The directional bias bound explains how this difficulty can be handled without uniformly bounding the population gradient over the localization region.
2.The paper goes beyond an unobservable best-iterate bound. The gradient-based selection rule produces an implementable output without function evaluations or additional oracle calls. The complementary lower bound strengthens the contribution by showing that the stochastic dependence is nearly tight within the fixed-parameter Clip-SGD class, even when arbitrary transcript-based output rules are allowed.
Critical weaknesses
1.The optimality result has a restricted algorithmic scope. Theorem 3 establishes near-optimality for Clip-SGD with a fixed stepsize and clipping level, rather than for stochastic first-order optimization generally. It therefore does not establish whether the leading (L_1R_0) dependence is intrinsic to the oracle model or can be avoided by adaptive methods. The paper acknowledges this restriction, but it limits the broader significance of the optimality conclusion.
2.The practical implications of the prescribed tuning remain uncertain. The clipping threshold and stepsize depend on problem quantities including the noise moment parameters, smoothness constants, and an initial-distance bound. The computable output removes the need for function evaluations, but does not resolve access to these tuning quantities. Without a robustness analysis or numerical illustration, it is difficult to judge how informative these prescriptions are when only conservative estimates are available. This is a limitation of applicability rather than a reason to dismiss the theoretical contribution.
Questions for authors
1.Clarification: Can Theorem 2 be stated using conservative upper bounds on (L_0,L_1,R_0,\sigma)? What rate and iteration requirement result when these bounds substantially overestimate the actual quantities?
2.Clarification: Is selection by the observed clipping test essential to the guarantee, or is it primarily needed by the proof? Is there an example under the stated assumptions where averaging all iterates fails to achieve the same rate?
3.Clarification: In the nonconvex guarantee, at what iteration scale does the term without explicit (L_1) or confidence dependence dominate the other terms? An explicit crossover condition would help assess the finite-budget significance of this improvement.
Rebuttal
We thank the reviewer for the careful review and the constructive questions. We address the points raised by the reviewer below.
W1. Algorithmic scope of the optimality result.
We agree that Theorem 3 is a lower bound for Clip-SGD with a fixed stepsize and clipping level, not for all stochastic first-order methods, and that it does not decide whether the (L1R0)(α−1)/α factor is intrinsic to the oracle model. The purpose of Theorem 3 is to show that this factor is a worst-case limitation of fixed-parameter Clip-SGD, not an artifact of our analysis.
Theorem 3 holds for every fixed (γ,λ), even when chosen with knowledge of L0, L1, R0, σ, α, K and δ, and for every output computed from the observed iterates and stochastic gradients, including the last iterate and any average. Hence, under the conditions of Theorem 3 and up to logarithmic factors in K, the factor cannot be removed for Clip-SGD with a constant stepsize and clipping level by a sharper analysis, a better tuning or a different output. This remains relevant even if a method with adaptive parameters were shown to avoid the factor: the factor would then be a limitation of fixed-parameter Clip-SGD that can be bypassed only by changing the algorithm. We believe this is useful to the community, as it separates the limitations of the method from those of its analysis. Designing an adaptive method that avoids the factor without introducing additional hyperparameters or other drawbacks that Clip-SGD does not have remains an open question.
W2 & Q1. Tuning with conservative estimates.
We thank the reviewer for this point. Please see our answer to Reviewer 1KFv (W1) for details. In short, yes: Theorem 2 holds with any upper bounds Lˉ0≥L0, Lˉ1≥L1, σˉ≥σ, any bound R0≥∥x0−x⋆∥, and any αˉ∈(1,α], used both in the parameter choices and in the iteration condition. For fixed α, K and δ, if these bounds overestimate the true quantities by factors of at most κ≥1 and K satisfies the corresponding iteration condition, the error bound grows by at most κ3 and the L1R0 part of the iteration requirement by at most κ2; a smaller αˉ preserves the guarantee, with the slower stochastic rate K−(αˉ−1)/αˉ. Our answer to Reviewer 6t1x (W2) describes how L0 and L1 can be estimated in practice.
Q2. Is selection by the observed clipping test essential?
Please see our answer to Reviewer xCzV (Q2) for details. In short, selection is needed in our analysis only for the iteration condition, not for the rate: with the parameters of Theorem 2, the uniform average of all iterates achieves the same rate if, in addition, K≥4096Mδ4, where Mδ=max(L1R0,log(12/δ)). We do not claim that this stronger condition is necessary.
Q3. Crossover in the nonconvex bound.
Up to the constant 47042, Theorem 4 bounds the averaged gradient norm by the largest of four terms: T1=KL0Δ0,T2=KcG0ℓδ,T3=(Kα−1(cG0ℓδ)α−1σα)2α−11,T4=(Kα−1(L0Δ0)α−1σα)3α−21,
where c=4/ν (ν≈0.567), G0=L1Δ0+L0Δ0 and ℓδ=log(e/δ). For large K, the largest term is T4, which has no explicit dependence on L1 or δ.
To see when this happens (assuming L0Δ0>0 and σ>0), let z=L0Δ0σ and g=ν4(1+L1Δ0/L0)logδe, so that z measures the noise level and g collects the dependence on L1 and δ. A direct computation shows that T4 is the largest term exactly when K≥max{z−2, gα−13α−2zα−1α}.
The first condition means T4≥T1, the second means T4≥T3, and together they also give T4≥T2. For α=2, the condition is simply K≥max{z−2,g4z2}.
In words: L1 and δ only affect how large K must be before this regime starts. After that, the bound is 47042T4, which has no explicit dependence on L1 or δ, although they still appear in the choice of the parameters.