acceptodds
Under review as a conference paper at ICLR 2027

Avoiding Bias in Clipped SGD for Overparameterized Models under Generalized Smoothness

Abstract

Modern machine learning is dominated by complex, overparameterized architectures capable of interpolating data and achieving zero training loss. For such models, we investigate the convergence properties of two popular modifications to standard SGD: clipped SGD and normalized SGD. We show that under overparameterization and a mild assumption on batch size, both clipped and normalized SGD do not suffer from the bias typically introduced by clipping, converging effectively at the same rate as their deterministic counterparts. This provides a rigorous theoretical justification for the empirical success of gradient clipping methods. In our analysis, we employ the -smoothness condition, under which we obtain convergence rates that improve upon the best known results in prior work. Furthermore, we extend our analysis to specific challenging regimes, including heavy-tailed noise, -smoothness (which is strictly weaker than standard assumptions in optimization literature) and the deterministic regime.

Primary area:
optimization
Keywords:
Clipped SGD, Normalized SGD, Overparameterized Models, Generalized Smoothness

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Ps3XOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper analyzes the convergence of clipped SGD and normalized SGD under (L0,L1)(L_0,L_1)-smoothness and the strong growth condition for convex and non-convex problems. The paper uses a constant batch size and achieves rates comparable to previous work. The paper also provides experiments to support its analysis.

Critical strengths

The introduction is well written and easy to follow. The paper addresses a relevant problem and analyzes practical gradient-clipping methods in both convex and nonconvex settings under general (L0,L1)(L_0, L_1)-smoothness.

Critical weaknesses
  • The contribution would be easier to assess if the paper reported sample complexity alongside iteration complexity. For example, let NN denote the total number of samples, TT the number of iterations, and BB the batch size, so that N=TBN=TB. Could the authors provide a table comparing the completion rates with prior work, including batch sizes and assumptions? In particular, the claim in lines 239-243 compares minibatch ClipSGD with single-sample SGD, although standard SGD also appears to benefit similarly from batching. What advantage remains when both methods use comparable batch sizes? Could the authors also discuss the known rates for standard SGD under (L0,L1)(L_0,L_1)-smoothness and the strong growth condition to clarify the claimed improvement (including the batch-size condition)?

  • Regarding Proposition 4.2, the improvement in batch-size dependence seems straightforward, and it seems that the analysis in Koloskova et al. (2023) could be similarly extended to obtain the same result. Could the authors clarify this?

  • The statement in line 61 that the algorithms "do not suffer from the bias typically introduced by clipping" should be discussed in light of the strong growth condition. Since the prior work being compared does not use this assumption, it is unclear how much of the claimed improvement comes from the stronger assumption. Could the authors clarify the technical novelty of establishing convergence without the bias under this condition?

  • Could the authors clarify the last inequality in lines 2029–2032? It appears to use R0R_0 to bound the distance of an arbitrary iterate from the optimum, whereas R0R_0 is defined as the initial distance.

  • The proof of Proposition 4.8 appears to also rely on Assumption 2.4 (lines 2246–2248).

Questions for authors

Please see the questions in weaknesses above; I am also open to revising my score based on the authors' responses

5 comments

Dear Reviewer Ps3X,

Thank you for your careful and constructive review. We appreciate your positive assessment of the relevance of the problem and of our treatment of practical clipping methods under generalized smoothness. We provide detailed responses to your comments below.

The contribution would be easier to assess if the paper reported sample complexity alongside iteration complexity. For example, let NN denote the total number of samples, TT the number of iterations, and BB the batch size, so that N=TBN=TB. Could the authors provide a table comparing the completion rates with prior work, including batch sizes and assumptions? In particular, the claim in lines 239--243 compares minibatch ClipSGD with single-sample SGD, although standard SGD also appears to benefit similarly from batching. What advantage remains when both methods use comparable batch sizes? Could the authors also discuss the known rates for standard SGD under (L0,L1)(L_0,L_1)-smoothness and the strong growth condition to clarify the claimed improvement (including the batch-size condition)?

We agree that the comparison should use total oracle complexity rather than iterations alone. Keeping the paper's notation, NN denotes iterations and T=NBT=NB denotes stochastic-gradient calls. The revised discussions after Theorems 4.1 and 4.3 and Proposition 4.4 now explicitly report TT, together with the required batch sizes. In particular, Theorem 4.1 gives, for B≥72(ρ−1)B\geq72(\rho-1), TClipSGD=O(ρF0(L0+L1c)[ε−2+(cε)−1]).T_{\rm ClipSGD}=\mathcal O\left(\rho F_0(L_0+L_1c)\left[\varepsilon^{-2}+(c\varepsilon)^{-1}\right]\right). The discussion after Theorem 4.3 gives TNSGD=O(ρL0F0ε−2+ρL1F0ε−1)T_{\rm NSGD}=\mathcal O(\rho L_0F_0\varepsilon^{-2}+\rho L_1F_0\varepsilon^{-1}) with B≥64(ρ−1)B\geq64(\rho-1), and the discussion after Proposition 4.4 gives the corresponding heavy-tailed complexity with the factor ρ1/(p−1)\rho^{1/(p-1)} and B≥2(3p+1)/(p−1)(ρ−1)1/(p−1)B \geq 2^{(3p+1)/(p-1)} (\rho-1)^{1/(p-1)}.

We also replaced the former unmatched comparison. The discussion after Theorem 4.1 now compares total oracle complexity under the same SGC oracle, the same sufficient batch B=(ρ)B=(\rho), and the same expected-gradient-norm criterion:

T_{\rm ClipSGD}=\mathcal O\left(\rho F_0(L_0+L_1c)\left[\varepsilon^{-2}+(c\varepsilon)^{-1}\right]\right).$$ The SGD bound follows from Vaswani et al. (2019, Theorem 3) after applying the standard mini-batch reduction of the effective growth coefficient. We no longer claim universal superiority: the ClipSGD bound improves in the regime $\varepsilon \leq c$ and $L_0+L_1c \lll L$. To the best of our knowledge, there is no result for vanilla mini-batch SGD under exactly our $(L_0,L_1)$-smoothness and SGC assumptions. We would be grateful for a specific reference if the reviewer has one in mind, and we will add an explicit comparison. Because the revised text already states the oracle complexity, batch condition, assumptions, and metric next to each result, we chose these local matched comparisons instead of a separate table. A comprehensive table would have to mix convex and non-convex settings, ClipSGD, NSGD, and SGD, as well as different noise assumptions and convergence criteria, while taking substantial main-text space; we believe this would obscure rather than sharpen the comparison. > **Regarding Proposition 4.2, the improvement in batch-size dependence seems straightforward, and it seems that the analysis in Koloskova et al. (2023) could be similarly extended to obtain the same result. Could the authors clarify this?** We agree that, in the bounded-variance case $\rho = 1$, Theorem 3.3 of Koloskova et al. (2023), when applied to the mini-batch-average oracle, gives the same convergence rate as Proposition 4.2. We have revised the discussion immediately after Proposition 4.2 accordingly. The revised text also distinguishes this setting from their Appendix C.4.1, where individually clipped gradients are averaged. Therefore, we no longer claim an improved batch-size dependence over their Theorem 3.3. The contribution of Proposition 4.2 is that the result holds under the weaker generalized SGC, which allows gradient-dependent variance, whereas bounded variance corresponds to the special case $\rho=1$. (Part 1/2)

The statement in line 61 that the algorithms "do not suffer from the bias typically introduced by clipping" should be discussed in light of the strong growth condition. Since the prior work being compared does not use this assumption, it is unclear how much of the claimed improvement comes from the stronger assumption. Could the authors clarify the technical novelty of establishing convergence without the bias under this condition?

By “avoiding bias,” we mean the absence of a persistent clipping-induced optimization error floor, not that the clipped gradient estimator is unbiased. Our arbitrary-accuracy result relies essentially on SGC. The motivation is given in the second paragraph of the Introduction, which explains that without the strong growth condition, standard ClipSGD analysies predict stagnation at a noise-dependent error floor, and in Section 3, which records the min⁡[σ,σ2/c]\min \left[\sigma,\sigma^2/c \right] floor of Koloskova et al. (2023).

To the best of our knowledge, this is the first analysis of vanilla ClipSGD under SGC. The essential proof step is to use, for σ=0\sigma=0,

\leq \frac{\rho-1}{B}||\nabla f(x)||^2.$$ For $B \geq 72(\rho-1)$, the stochastic-error terms can be absorbed into the descent terms in both clipping regimes, yielding $$\mathbb E[F_{k+1}\mid x^k]-F_k \leq-\frac{\eta}{3}\min \left[||\nabla f(x^k)||^2, c||\nabla f(x^k)||\right].$$ This is the mechanism that removes the clipping-induced floor while keeping both $c$ and the sufficient batch size $B$ independent of the desired accuracy $\varepsilon$; the novelty is therefore the SGC-specific clipped-direction analysis, not an assumption-free improvement over prior bounded-variance results. > **Could the authors clarify the last inequality in lines 2029--2032? It appears to use $R_0$ to bound the distance of an arbitrary iterate from the optimum, whereas $R_0$ is defined as the initial distance.** We clarified this step immediately before the inequality in Appendix C.2.2: “By convexity, the Cauchy--Schwarz inequality, and the monotonicity of the distance to the optimum from Lemma B.4, we have”. Lemma B.4 gives $$||x^k-x^* ||\leq||x^0-x^* ||=R_0,$$ so $$F_k\leq\langle\nabla f(x^k),x^k-x^* \rangle \leq R_0||\nabla f(x^k)||.$$ Thus, $R_0$ bounds the arbitrary-iterate distance here because the preceding lemma establishes its monotonicity. > **The proof of Proposition 4.8 appears to also rely on Assumption 2.4 (lines 2246--2248).** We agree and removed this dependence. The revised proof uses only Assumption 2.5 with $\sigma=0$ and the coefficient $$(2^{p-1}\rho)^{1/p},$$ derived directly from its $p$-moment bound. The corrected population upper model is proved in Appendix B.1, Eq. (12), and Appendix B.2, Eq. (13). Proposition 4.8 and Appendix C.2.3 now use $$\eta\leq\min\left[\frac{\lambda}{\mathcal L_0+(2^{p-1}\rho)^{1/p} \mathcal L_1\lambda},4R_0\right].$$ This changes only the $\mathcal L_1$ coefficient; the dependence on $\varepsilon$ and the accuracy-independent batch scaling remain unchanged. Section 5 has been updated accordingly. ***We hope that our revisions and responses fully address your concerns. If so, we would be grateful if you would consider revising your rating in support of the paper; otherwise, we would be happy to clarify any remaining points or answer further questions.*** Best regards, The Authors (Part 2/2)

Dear Reviewer Ps3X,

As fewer than two days remain in the discussion period, we would be very grateful for any feedback on our response and the revised manuscript. If any questions or concerns remain, we would particularly appreciate it if you could share them at your earliest convenience, so that we have sufficient time to provide a careful response before the discussion closes.

Thank you again for your time and consideration.

Reviewer_UWioOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies clipped and normalized stochastic gradient methods under generalized smoothness and a strong growth condition. Its main finite-variance results show that an accuracy-independent mini-batch size proportional to the growth parameter suffices for convergence guarantees in expected gradient norm or last-iterate function gap. ClipSGD permits an arbitrary positive clipping radius, while the NSGD guarantees depend on a positive normalization parameter selected for the desired accuracy. The paper also develops heavy-tailed and function-gap-dependent smoothness extensions and a deterministic warm-up analysis. Experiments across four datasets illustrate fixed-batch training and compare measured gradient-noise ratios and directional alignment with the sufficient theoretical conditions.

Critical strengths
  • Theorems 4.1, 4.3, 4.6, and 4.7 give a coherent account of how relative gradient noise can be controlled by an accuracy-independent batch under generalized smoothness. The arbitrary clipping radius and standard expected-gradient/function-gap metrics make the guarantees useful for understanding these familiar algorithms, and are the main reason to consider acceptance.

  • The convex analysis handles the stochastic transition between clipping regimes carefully: Lemma B.2 transfers the needed self-bound to mini-batches, and Eqs. (48)–(54) combine history-dependent regimes before deriving the last-iterate rate. These ingredients support the paper's core claims beyond a direct deterministic analogy.

Critical weaknesses
  • Proposition 4.8 retains the step-size coefficient ρL1\sqrt{\rho}\mathcal{L}_1 under only a central pp-moment condition, p<2p<2, but its proof in C.2.3 inherits the expected-objective smoothness conversion in Eq. (12), which uses a second moment. The available bound is E∥∇f(x,ξ)∥≤[1+(ρ−1)1/p]∥∇f(x)∥.\mathbb{E}\lVert \nabla f(x,\xi)\rVert \le \bigl[1+(\rho-1)^{1/p}\bigr]\lVert \nabla f(x)\rVert . The ρ\sqrt{\rho} implication can fail even for convex interpolating samples: let u±=(δ,±1−δ2)u_\pm=(\delta,\pm\sqrt{1-\delta^2}) with δ=0.01\delta=0.01, and f±(x)=cosh⁡(u±⊤x)−1f_\pm(x)=\cosh(u_\pm^\top x)-1 equiprobably. Sample constants (L0,L1)=(2,2)(\mathcal{L}_0,\mathcal{L}_1)=(2,2), p=3/2p=3/2, and ρ=1+(1−δ2/δ)p\rho=1+\bigl(\sqrt{1-\delta^2}/\delta\bigr)^{p} satisfy the assumptions, but at x=(400,0)x=(400,0), ∥∇2f(x)∥≈27.306>2+2ρ∥∇f(x)∥≈19.268.\lVert \nabla^2 f(x)\rVert \approx 27.306 > 2+2\sqrt{\rho}\lVert \nabla f(x)\rVert \approx 19.268 .

  • Proposition D.12 permits σ>0\sigma>0 without interpolation, while its proof reuses Lemmas D.3/D.7 through Eqs. (101) and (69). Those lemmas need interpolation both to transfer smoothness with unchanged constants and to bound the distance to x∗x^\ast. I think the proposition is false under its listed assumptions. The related σ>0\sigma>0 discussions in C.2.2 and D.10 reuse the same interpolation-dependent ingredients. Restricting these extensions could preserve the main σ=0\sigma=0 results, but the present broader claims I believe need correction.

Questions for authors

See weaknesses. In particular:

  • Can you establish Proposition 4.8 with its stated ρ\sqrt{\rho} coefficient without assuming a second moment? Alternatively, does replacing it by κp=1+(ρ−1)1/p\kappa_p=1+(\rho-1)^{1/p} repair the theorem, and how does that change the comparison in §5?
  • Is interpolation intended as an additional assumption in D.12 and the σ>0\sigma>0 convex extensions?
4 comments

Dear Reviewer UWio,

Thank you for your careful and technically precise review. We appreciate your positive assessment of the core finite-variance theorems and the convex regime-switching analysis. We provide detailed responses to your comments below.

Proposition 4.8 retains the step-size coefficient ρL1\sqrt\rho\mathcal L_1 under only a central p-moment condition, p<2p<2, but its proof in C.2.3 inherits the expected-objective smoothness conversion in Eq. (12), which uses a second moment. The available bound is E∣∣∇f(x,ξ)∣∣≤[1+(ρ−1)1/p]∣∣∇f(x)∣∣\mathbb E||\nabla f(x,\xi)||\le[1+(\rho-1)^{1/p}]||\nabla f(x)||. The implication can fail even for convex interpolating samples: let u±=(δ,±1−δ2)u_\pm=(\delta,\pm \sqrt{1-\delta^2}) with δ=0.01\delta=0.01, and f±(x)=cosh⁡(u±Tx)−1f_\pm(x)=\cosh (u^T_\pm x)-1 equiprobably. Sample constants (L0,L1)=(2,2)(\mathcal L_0,\mathcal L_1)=(2,2), p=3/2p=3/2, and p=1+(1−δ2/δ)pp=1+(\sqrt{1-\delta^2}/\delta)^p satisfy the assumptions, but at x=(400,0)x=(400,0), ∣∣∇2f(x)∣∣≈27.306>2+2ρ∣∣∇f(x)∣∣≈19.268||\nabla^2 f(x)||\approx 27.306>2+2\sqrt\rho||\nabla f(x)||\approx19.268.

We agree. Revised Proposition 4.8 uses (2p−1ρ)1/p,(2^{p-1}\rho)^{1/p}, derived directly from Assumption 2.5 with σ=0\sigma = 0; the coefficient 1+(ρ−1)1/p1+(\rho-1)^{1/p} suggested in the review is also valid. The corrected population upper model is given in Appendix B.1, Eq. (12), and Appendix B.2, Eq. (13). Proposition 4.8 and Appendix C.2.3 now use η≤min⁡[λL0+(2p−1ρ)1/pL1λ,4R0].\eta\le\min\left[\frac{\lambda}{\mathcal L_0+ (2^{p-1}\rho)^{1/p} \mathcal L_1\lambda},4R_0\right]. This changes only the L1\mathcal L_1 multiplier; the dependence and the accuracy-independent batch scaling remain unchanged. Section 5 now reports the corrected dependence.

The first question for the authors asks exactly whether this coefficient should be replaced and how the comparison changes; the correction above answers that question.

Proposition D.12 permits σ>0\sigma>0 without interpolation, while its proof reuses Lemmas D.3/D.7 through Eqs. (101) and (69). Those lemmas need interpolation both to transfer smoothness with unchanged constants and to bound the distance to x∗x^*. I think the proposition is false under its listed assumptions. The related σ>0\sigma>0 discussions in C.2.2 and D.10 reuse the same interpolation-dependent ingredients. Restricting these extensions could preserve the main σ=0\sigma=0 results, but the present broader claims I believe need correction.

We agree that these convex proofs require interpolation and corrected their scope. We also note that this restriction affects only the auxiliary convex extensions beyond the main interpolation regime; the principal σ=0\sigma=0 guarantees remain unchanged.

  • Proposition D.12 now assumes Assumption 2.5 with σ=0\sigma=0; the former σ>0\sigma>0 claim was removed.
  • Appendix C.2.2 and Theorem D.10 now treat only SGC with σ=0\sigma=0; the general convex σ>0\sigma>0 case is listed as future work in Section 5.
  • Appendix D now makes interpolation explicit in Lemma D.3, Eqs. (68)--(69), and the monotonic-distance Lemmas D.6--D.7.

In the retained σ=0\sigma=0 setting, the moment condition plus realization-level convexity implies interpolation: at a population minimizer $ x^* $, the moment bound gives $ \nabla f(x^* , \xi)=0 $ almost surely, and convexity makes $ x^* $ a minimizer of every realization.

The second question for the authors asks whether interpolation is intended in D.12 and the σ>0\sigma>0 convex extensions; the restrictions and explicit assumptions above answer that question.

We hope that our revisions and responses fully address your concerns. If so, we would be grateful if you would consider revising your rating in support of the paper; otherwise, we would be happy to clarify any remaining points or answer further questions.

Best regards,
The Authors

Dear Reviewer UWio,

As fewer than two days remain in the discussion period, we would be very grateful for any feedback on our response and the revised manuscript. If any questions or concerns remain, we would particularly appreciate it if you could share them at your earliest convenience, so that we have sufficient time to provide a careful response before the discussion closes.

Thank you again for your time and consideration.

I thank the authors for their response. They have mostly address my concerns. I will increase my score by 1.

Dear Reviewer UWio,

Thank you very much for your time and helpful feedback, which helped us improve the paper. We sincerely appreciate your thoughtful consideration of our responses and your decision to increase the score.

We noticed that the score displayed on OpenReview has not yet been updated; if this is not simply a system delay, we would be grateful if you could update it at your convenience.

Best regards,

The Authors

Reviewer_3f87OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper analyzes clipped stochastic gradient descent (ClipSGD) and normalized stochastic gradient descent (NSGD) under generalized smoothness and the strong growth condition (SGC). Its main result is that, when the stochastic noise is purely multiplicative, a sufficiently large fixed mini-batch with B=O(ρ)B=O(\rho) allows ClipSGD to reach arbitrary accuracy without increasing the batch size as the accuracy requirement becomes more stringent. The guarantees cover both convex and nonconvex objectives and permit any positive clipping threshold.

For NSGD, the batch-size requirement is also accuracy-independent, although the normalization parameter λ\lambda and the step size must be selected based on the target accuracy. The paper additionally studies heavy-tailed noise through a relative pp-th-moment condition and develops extensions under (H0,H1)(H_0, H_1)-smoothness. Experiments on four datasets examine fixed-batch training, gradient-noise diagnostics, and batch-size selection. These experiments primarily document successful behavior outside the sufficient theoretical regime rather than directly validate the convergence bounds.

Critical strengths
  1. A useful arbitrary-accuracy result for vanilla clipping under relative noise. The central ClipSGD guarantees show that, under SGC with σ=0\sigma=0, a fixed batch size proportional to the growth parameter is sufficient to avoid a persistent clipping-induced optimization error floor. Importantly, the clipping threshold can be any fixed c>0c>0, with its effect reflected in the step-size restriction and convergence bound. This identifies a meaningful regime in which clipping remains compatible with accurate optimization without requiring the batch size or clipping threshold to increase as target accuracy increases. That conclusion is the main reason I lean toward acceptance.

  2. Coverage of complementary settings with explicit optimization guarantees. The analysis covers nonconvex stationarity and convex last-iterate expected suboptimality under generalized smoothness. The convex ClipSGD result distinguishes the linear and sublinear components of the bound, while the NSGD analysis makes the trade-off among λ\lambda, the allowable step size, and target accuracy explicit. The nonconvex heavy-tailed extension further shows how relative pp-th-moment control changes the required batch size while preserving accuracy independence. Together, these results provide more useful guidance than a single asymptotic convergence statement.

Critical weaknesses
  1. The proofs of two extensions require additional justification. Proposition 4.8 retains the step-size restriction involving ρL1\sqrt{\rho}\mathcal L_1. However, Appendix B.2 obtains this coefficient from
\leq \bigl(\mathbb E\|\nabla f(x,\xi)\|^2\bigr)^{1/2} \leq \sqrt{\rho}\|\nabla f(x)\|,$$ which uses Assumption 2.4. Proposition 4.8 instead assumes Assumption 2.5 with $p\in(1,2)$. A direct consequence of that assumption is $$\mathbb E\|\nabla f(x,\xi)\| \leq \left[1+(\rho-1)^{1/p}\right]\|\nabla f(x)\|,$$ not the displayed $\sqrt{\rho}$ bound. Appendix C.2.3 replaces the batch-noise estimate but does not revisit this population-smoothness conversion. The authors should either justify the stated coefficient with an alternative argument or revise the step size and the resulting dependence on $\rho$. Separately, the additive-noise proof preceding Eq. (32) combines two cases by asserting that both terms on the right-hand side are nonnegative. In particular, this requires $F_k-\mathbb E[F_{k+1}\mid x^k]\geq0$, which need not hold when $\sigma>0$. This step also needs repair. These concerns are localized to the extensions, but they prevent the acceptance of all stated guarantees as currently justified. 2. **The claimed improvements are not sufficiently separated from changes in assumptions, batching, and the update rule.** Under standard smoothness, the leading accuracy dependence is already available for SGD under SGC. For an i.i.d. batch, the effective growth coefficient is $$\rho_B=1+\frac{\rho-1}{B}.$$ Thus, with the same $B=\Theta(\rho)$, ordinary mini-batch SGD also admits a constant-order effective growth coefficient and an $O(LF_0/\varepsilon^2)$ iteration bound for the expected-gradient-norm criterion, with $O(\rho LF_0/\varepsilon^2)$ gradient evaluations. The contribution should therefore be distinguished from a general improvement over SGD under matched assumptions. There is also a concrete mismatch in the comparison following Proposition 4.2. Algorithm 1 clips the average gradient, whereas Appendix C.4.1 of Koloskova et al. (2023), cited for the batch-independent error floor, averages individually clipped gradients. These operations have different bias properties, so that comparison does not isolate an improvement in analysis for the same algorithm. The experiments do not settle these distinctions: the principal ClipSGD and NSGD runs coincide, strict NSGD uses $\lambda=0$, and the runs lie outside the sufficient batch-size regime. These limitations are acknowledged, but they leave the practical significance of the additional guarantees less clear than the broad claims of improvement suggest.
Questions for authors
  1. Population smoothness in Proposition 4.8. Can you provide the population descent inequality used in the convex heavy-tailed proof directly under Assumptions 4.5 and 2.5, without invoking second-moment SGC? In particular, what justifies the coefficient $\sqrt{\rho}\mathcal {L} _ {1} $? Would replacing it with a coefficient such as [1+(ρ−1)1/p]L1\left[1+(\rho-1)^{1/p}\right]\mathcal L_1 change the stated iteration or oracle complexity? This concerns the validity of an existing result, not a request for a new extension.

  2. Combining the additive-noise cases. In Appendix C.1.1, what justifies the nonnegativity assertion used immediately before Eq. (32)? For example, for f(x)=x2/2f(x)=x^2/2, the unbiased oracle g(x,ξ)=x+ξg(x,\xi)=x+\xi with ξ=±σ\xi=\pm\sigma equiprobably, B=1B=1, and xk=0x^k=0, a clipped step with 0<c≤σ0<c\leq\sigma gives Fk−E[Fk+1∣xk]=−η2c22<0.F_k-\mathbb E[F_{k+1}\mid x^k] = -\frac{\eta^2c^2}{2}<0. This example does not disprove Proposition 4.2, but it invalidates the stated nonnegativity justification. Can you provide a uniform one-step estimate or another argument that establishes the claimed bound?

  3. Matched complexity and novelty comparison. Which advantages remain when ClipSGD, NSGD, and ordinary mini-batch SGD are compared using the same SGC assumption, batch size, convergence criterion, and total number of gradient evaluations? Please also distinguish between averaging before clipping and clipping before averaging in the comparison with Koloskova et al. (2023). Identifying the essential additional proof step and the parameter regimes with a genuine advantage would materially clarify the significance of the contribution.

  4. A controlled validation of the theoretical mechanism. Can you provide a focused experiment on a problem with a known SGC constant, using parameters covered by the theorems, including λ>0\lambda>0 for NSGD? Tracking training suboptimality or gradient norm across increasingly stringent target accuracies with the same batch size would be more directly informative than test accuracy alone. It would also help to distinguish ClipSGD from NSGD in a setting where their updates are not identical. This is a request to validate the existing mechanism, not to prove SGC for an entire neural-network architecture.

5 comments

Dear Reviewer 3f87,

Thank you for your careful and constructive review. We appreciate your positive assessment of the arbitrary-accuracy result for vanilla ClipSGD and the complementary convex/non-convex guarantees. We provide detailed responses to your comments below.

The proofs of two extensions require additional justification. Proposition 4.8 retains the step-size restriction involving ρL1\sqrt{\rho}\mathcal L_1. However, Appendix B.2 obtains this coefficient from E∣∣∇f(x,ξ)∣∣≤(E∣∣∇f(x,ξ)∣∣2)1/2≤ρ∣∣∇f(x)∣∣\mathbb E||\nabla f(x,\xi)||\le(\mathbb E||\nabla f(x,\xi)||^2)^{1/2}\le\sqrt\rho||\nabla f(x)||, which uses Assumption 2.4. Proposition 4.8 instead assumes Assumption 2.5 with p(1,2). A direct consequence of that assumption is E∣∣∇f(x,ξ)∣∣≤[1+(ρ−1)1/p]∣∣∇f(x)∣∣\mathbb E||\nabla f(x,\xi)||\le[1+(\rho-1)^{1/p}]||\nabla f(x)||, not the displayed bound. Appendix C.2.3 replaces the batch-noise estimate but does not revisit this population-smoothness conversion. The authors should either justify the stated coefficient with an alternative argument or revise the step size and the resulting dependence on . Separately, the additive-noise proof preceding Eq. (32) combines two cases by asserting that both terms on the right-hand side are nonnegative. In particular, this requires Fk−E[Fk+1∣xk]≥0F_k-\mathbb E[F_{k+1}\mid x^k]\ge0, which need not hold when >0. This step also needs repair. These concerns are localized to the extensions, but they prevent the acceptance of all stated guarantees as currently justified.

We agree and corrected both extensions.

  • For Proposition 4.8, we replaced the unjustified coefficient by (2p−1ρ)1/p,(2^{p-1}\rho)^{1/p}, derived directly from Assumption 2.5 with σ=0\sigma = 0. The corrected population upper model is proved in Appendix B.1, Eq. (12), and Appendix B.2, Eq. (13). Proposition 4.8 and Appendix C.2.3 now use η≤min⁡[λL0+(2p−1ρ)1/pL1λ,4R0].\eta\le\min\left[\frac{\lambda}{\mathcal L_0+ (2^{p-1}\rho)^{1/p} \mathcal L_1\lambda},4R_0\right]. This changes only the L1\mathcal L_1 coefficient; the dependence on and the accuracy-independent batch scaling remain unchanged. Section 5 has been updated accordingly.

  • For Proposition 4.2, we removed the invalid nonnegativity argument. Appendix C.1.1 now proves the uniform estimate

\le-\frac{\eta}{3}\min\left[||\nabla f(x^k)||^2,c||\nabla f(x^k)||\right] +\frac{3\eta\sigma^2}{B}, \tag{32}$$ and obtains the claimed bound by summing it directly; see Eqs. (30)--(35). **Questions 1 and 2 restate these two parts of the weakness, respectively; the corrections above answer them jointly.** (Part 1/2)

The claimed improvements are not sufficiently separated from changes in assumptions, batching, and the update rule. Under standard smoothness, the leading accuracy dependence is already available for SGD under SGC. For an i.i.d. batch, the effective growth coefficient is ρB=1+(ρ−1)/B\rho_B=1+(\rho-1)/B. Thus, with the same B=(ρ)B=(\rho), ordinary mini-batch SGD also admits a constant-order effective growth coefficient and an O(LF0/ε2)\mathcal O(LF_0/\varepsilon^2) iteration bound for the expected-gradient-norm criterion, with O(ρLF0/ε2)\mathcal O(\rho LF_0/\varepsilon^2) gradient evaluations. The contribution should therefore be distinguished from a general improvement over SGD under matched assumptions. There is also a concrete mismatch in the comparison following Proposition 4.2. Algorithm 1 clips the average gradient, whereas Appendix C.4.1 of Koloskova et al. (2023), cited for the batch-independent error floor, averages individually clipped gradients. These operations have different bias properties, so that comparison does not isolate an improvement in analysis for the same algorithm. The experiments do not settle these distinctions: the principal ClipSGD and NSGD runs coincide, strict NSGD uses λ=0\lambda=0, and the runs lie outside the sufficient batch-size regime. These limitations are acknowledged, but they leave the practical significance of the additional guarantees less clear than the broad claims of improvement suggest.

We agree and narrowed the claims. Section 4.1 now compares total oracle complexity under the same SGC oracle, B=(ρ)B=(\rho), and the same convergence criterion:

T_{\rm ClipSGD}=\mathcal O\left(\rho F_0(L_0+L_1c)[\varepsilon^{-2}+(c\varepsilon)^{-1}]\right).$$ We no longer claim universal superiority: the ClipSGD bound improves in the regime $\varepsilon \leq c$ and $L_0+L_1c \lll L$. The essential proof step is to exploit the scale-sensitive SGC bound $$\mathbb{E}\left[\left||g_B-\nabla f(x)\right||^2 \mid x\right] \leq \frac{\rho-1}{B}\left||\nabla f(x)\right||^2 \qquad (\sigma=0).$$ For $B \geq 72(\rho-1)$, this allows the stochastic-error terms in both clipping regimes to be absorbed into the corresponding descent terms. Consequently, both the clipping radius $c$ and the sufficient batch size $B$ remain independent of the desired accuracy $\varepsilon$. We also corrected the comparison with Koloskova et al. (2023) immediately after Proposition 4.2. Namely, in the case $\rho =1$, Proposition 4.2 establishes the same convergence rate as Theorem 3.3 of Koloskova et al. (2023) when the mini-batch average is clipped, rather than individual gradients being clipped before averaging as in their Appendix C.4.1. However, Proposition 4.2 holds under the weaker generalized SGC, whereas Koloskova et al. (2023) assume bounded variance. Thus, we no longer present the batch-size dependence itself as an improvement over their Theorem 3.3; the extension is to a more general noise assumption. Finally, we added Appendix A.4, *“Controlled optimization with exact SGC and smoothness constants.”* It uses analytic interpolation problems with known SGC constants, theorem-compatible parameters, and NSGD with $\lambda>0$. The principal comparison fixes $\rho=2$ and $B=72$; the additional 32-run ablations vary the exact SGC coefficient and the target accuracy. Table 7 gives the constants and protocol, Figure 4 and Table 8 give the main comparison, and Figure 5 gives the curvature, SGC, and fixed-batch target-accuracy ablations. **Questions 3 and 4 restate the matched-comparison and controlled-validation parts of this weakness; the revisions above answer them jointly.** ***We hope that our revisions and responses fully address your concerns. If so, we would be grateful if you would consider revising your rating in support of the paper; otherwise, we would be happy to clarify any remaining points or answer further questions.*** Best regards, The Authors (Part 2/2)

Dear Reviewer 3f87,

As fewer than two days remain in the discussion period, we would be very grateful for any feedback on our response and the revised manuscript. If any questions or concerns remain, we would particularly appreciate it if you could share them at your earliest convenience, so that we have sufficient time to provide a careful response before the discussion closes.

Thank you again for your time and consideration.

Comments on the paper

1 comment

We sincerely thank all Reviewers for their careful reading and constructive feedback. We particularly appreciate that the reviewers recognized the significance of the core arbitrary-accuracy guarantees and the relevance of analyzing practical clipping methods under generalized smoothness.

Reviewer 3f87 highlighted

“A useful arbitrary-accuracy result for vanilla clipping under relative noise. The central ClipSGD guarantees show that, under SGC with σ=0\sigma=0, a fixed batch size proportional to the growth parameter is sufficient to avoid a persistent clipping-induced optimization error floor. Importantly, the clipping threshold can be any fixed c>0c>0.”

and noted that

“That conclusion is the main reason I lean toward acceptance.”

Reviewer UWio emphasized that

“Theorems 4.1, 4.3, 4.6, and 4.7 give a coherent account of how relative gradient noise can be controlled by an accuracy-independent batch under generalized smoothness. The arbitrary clipping radius and standard expected-gradient/function-gap metrics make the guarantees useful for understanding these familiar algorithms, and are the main reason to consider acceptance.”

and further noted that

“The convex analysis handles the stochastic transition between clipping regimes carefully: Lemma B.2 transfers the needed self-bound to mini-batches, and Eqs. (48)–(54) combine history-dependent regimes before deriving the last-iterate rate. These ingredients support the paper's core claims beyond a direct deterministic analogy.”

Reviewer Ps3X noted that

“The introduction is well written and easy to follow. The paper addresses a relevant problem and analyzes practical gradient-clipping methods in both convex and nonconvex settings under general (L0,L1)(L_0,L_1)-smoothness.”

Motivated by the Reviewers’ comments, we have strengthened the theoretical justification, comparisons, and experimental validation while preserving the original problem setting and main results.

We emphasize that the proof corrections and scope restrictions concern the additive-noise, convex heavy-tailed, and auxiliary convex σ>0\sigma>0 extensions. The core σ=0\sigma=0 convergence mechanism and rates in Theorems 4.1, 4.3, 4.6, and 4.7 remain valid and unchanged. The overall structure and central objective of the paper are also unchanged, and all modifications are highlighted in the revised manuscript for ease of review.

We again thank all Reviewers for their valuable comments, which helped us substantially strengthen the precision, positioning, and empirical validation of the paper.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.