- 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 -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 -smoothness.
Critical weaknesses
-
The contribution would be easier to assess if the paper reported sample complexity alongside iteration complexity. For example, let denote the total number of samples, the number of iterations, and the batch size, so that . 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 -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 to bound the distance of an arbitrary iterate from the optimum, whereas 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
Part 2/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 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 ,
\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.
Part 1/2
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.
We agree that the comparison should use total oracle complexity rather than iterations alone. Keeping the paper's notation, N denotes iterations and T=NB denotes stochastic-gradient calls. The revised discussions after Theorems 4.1 and 4.3 and Proposition 4.4 now explicitly report T, together with the required batch sizes. In particular, Theorem 4.1 gives, for B≥72(ρ−1), TClipSGD=O(ρF0(L0+L1c)[ε−2+(cε)−1]). The discussion after Theorem 4.3 gives TNSGD=O(ρL0F0ε−2+ρL1F0ε−1) with B≥64(ρ−1), and the discussion after Proposition 4.4 gives the corresponding heavy-tailed complexity with the factor ρ1/(p−1) and B≥2(3p+1)/(p−1)(ρ−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=(ρ), 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)