- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies finite-sample properties of Polyak-Ruppert averaged SGD under heavy-tailed noise, systematically comparing unclipped SGD (U-SGD), whole-gradient clipping SGD (WG-Clip), and noise-centered clipping SGD (NC, oracle baseline). Under a conditional -th moment assumption (), the paper decomposes the averaged error of unclipped SGD into a Gaussian term (variance control) and a heavy-tail correction (control of rare large increments). It proves that when , for a fixed confidence , the decay rate of the heavy-tail correction is , which is faster than the Gaussian term ; hence clipping does not necessarily improve the leading-order error. The main theoretical benefit of clipping is to improve the dependence of the heavy-tail correction on the confidence from polynomial order to logarithmic order (); at this improvement directly affects the leading-order statistical term. The paper further gives finite-sample upper bounds for projected SGD and Clip-SGD on convex optimization, epoch-restart complexity on strongly convex quadratics, Polyak-Ruppert asymptotic limits under fixed-threshold clipping, conditions under which noise-centered clipping with growing thresholds recovers the standard limit, and experiments on the Open Bandit Dataset via off-policy click prediction verifying the crossover phenomenon of "effective at finite budget, ineffective at long budget."
Critical strengths
1.The paper decomposes the averaged SGD error into a variance-controlled Gaussian term and a heavy-tail correction arising from rare large increments, and gives explicit conditions (e.g., (13) and Proposition 5.1) that clearly characterize in which accuracy/confidence regimes clipping is beneficial. This framework is of significant reference value for future work.
2.Noise-centered clipping depends only on the centered moment , whole-gradient clipping depends on the full-gradient moment , and difference clipping has independent anchor-error control. This distinction lets readers accurately identify the source of clipping bias and explains why WG may in practice have smaller benefit than the theoretical NC baseline.
3.In the OBD experiments, clipping has a significant gain near the threshold-selection budget (ratio 0.63), and as the budget grows the curves cross, eventually clipping is clearly worse (ratio 1.89), consistent with the mechanism of fixed-threshold causing a mean-field target shift and long-run domination.
Critical weaknesses
1.In Theorem 3.1 the heavy-tail correction for U-SGD uses the centered moment , while in Theorem 3.2 the correction for WG-Clip uses the full-gradient moment . Since also contains a signal term (), in scenarios where the full-gradient moment is much larger than , the correction term for WG-Clip can be larger even though the confidence dependence is better. Although the paper gives an NC oracle baseline, the convex optimization section does not provide an explicit theorem for NC, so a fair comparison under the same moment scale cannot be made directly in the main text. We suggest adding a complete theorem for NC in convex optimization or an equivalent oracle derivation.
2.These conditions in (12) contain several -dependent constants (, ) and cross terms. The paper gives no numerical values or asymptotic characterizations, making it difficult for readers to judge in practice whether the conditions hold. For example, the second clause of condition (12) for requires comparing with ; in common high-confidence regimes this may require very large sample sizes.
3.The balanced threshold depends on unknown constants . In experiments thresholds are chosen on a separate validation set. The inconsistency between theory and practice limits the translation of theory into algorithms.
4.The OBD experiment only compares U-SGD and WG; there is no experimental counterpart for the NC oracle or difference clipping.
Questions for authors
1.Regarding the comparison between whole-gradient clipping and noise-centered clipping: if in Theorem 3.2 were replaced by (i.e., using NC), would one obtain a direct comparison with Theorem 3.1 at the same moment scale?
2.The paper claims that for the heavy-tail correction decays faster than the Gaussian term, but this relies on a fixed . Can the authors provide a concrete heavy-tailed distribution example showing that for finite sample sizes, the actual error of U-SGD is indeed dominated by the Gaussian term and clipping offers no benefit? Or are there real settings where but N is not large enough to enter the Gaussian-dominated regime?
3.In Figure 1(b), threshold still helps at (), but crosses after . At , is also optimal among all scanned thresholds? In Figure 1(c), at the optimal has ratio , while in Figure 1(b) at that point has ratio , indicating that conclusions are sensitive to . Could the authors report a complete error table for different and different budgets so readers can understand the sensitivity of threshold selection?
4.The theory suggests that the optimal clipping threshold should grow as . Did the authors conduct any experiments comparing a growing threshold schedule against a fixed threshold? If not, can the theoretical advantage of a growing threshold be demonstrated empirically at least in a simple synthetic setting?
5.The “moderate N” regime in which a fixed threshold helps is clearly dataset-dependent. Is there any practical guidance or quantitative criterion for identifying this regime before running the full experiment, or must it be diagnosed a posteriori from crossover curves?
2 comments
Thanks for the authors' detailed response. It addresses my concern. I will hold my score.
Weakness 1
We have added the complete convex NC bound as Corollary 3.3 in the main text. Its clipping correction and squared-gradient remainder use the centered-noise moment σp, allowing a direct comparison with U-SGD. Also the common full-gradient second-moment bound G2 is retained. The proof separately controls the unclipped signal–clipped-noise cross term.
See Corollary 3.3, Eq. (10) (p. 5); Appendix B.7 (pp. 23–24); and the explicit constants in Appendix B.8 (pp. 24–26).
Weakness 2
Appendix B.8 now gives numerical constants for the full U-SGD, WG and NC bounds, explicit remainder conditions, and sample sizes for a target error, with values illustrated at p=3, 4 and 6. We also clarify that the additional p>4 condition becomes weaker as δ tends to zero. The large sufficient budgets instead arise from the main Gaussian-dominance condition, especially near p=2.
See Appendix B.8, Eqs. (50)–(52) and the following budget formulas (pp. 24–26), and the discussion after Remark 5.2 (p. 9).
Weakness 3
We now distinguish moment-based certification from validation-based calibration. Section 2.2 quantifies constant-factor errors in the threshold scale. Appendix F.6 tests past-gradient quantile thresholds, with and without a prescribed growing factor, without supplying moment bounds or a tail exponent.
See Section 2.2 (p. 4), Remark 5.2 (pp. 8–9), and Appendix F.6, Table 6 (pp. 46–47).
Weakness 4
We have added both counterparts: the NC oracle in the nonconvex experiment and difference clipping under state-dependent noise. The corrected DC experiment charges every sampled anchor and both evaluations in each gradient difference, giving all methods the same gradient-evaluation budget. DC improves the matched unclipped-difference estimator but has higher error than U-SGD at every tested budget.
See Appendix F.4, Table 3 (p. 44), and the corrected protocol in Appendix F.5, Table 5 (pp. 45–46).
Question 1
Yes. Corollary 3.3 gives the direct comparison with Theorem 3.1 using the same centered-noise scales σ2 and σp. The leading variance term has the same order, while the linear heavy-tail correction changes from polynomial to logarithmic confidence dependence. The NC proof includes the full squared-gradient remainder and the signal–noise cross term.
See Theorem 3.1 and Corollary 3.3, Eqs. (8) and (10) (p. 5), and Appendix B.7 (pp. 23–24).
Question 2
Appendix F.4 gives a Pareto-tailed example with a finite third and infinite fourth moment. At N=65,536, the local Gaussian reference lies within the confidence interval for U-SGD's measured error quantile, while fixed WG with threshold 5 is worse. At N=256, that same threshold improves the error. Appendix A.3 also allows δ to decrease with N.
See Appendix F.4, Table 3 and the Gaussian comparison (p. 44), and Proposition A.5 and its discussion (p. 16).
Question 3
At N=222, threshold 5 is not the empirical grid minimizer: its ratio is 0.790, versus 0.675 for threshold 10. Panel (b) keeps the source-validation-selected threshold fixed. We now report the complete 11-threshold by 11-budget grid through 222, with absolute U-SGD errors and the supplementary CSV provides unrounded errors and intervals. Only U-SGD and threshold 5 were evaluated beyond 222.
See Appendices F.1–F.2 and Table 2 (p. 43); supplementary iclr_obd_learning_curves.csv.
Question 4
Yes. Appendix F.4 directly compares fixed WG, horizon-dependent WG and NC, and an online growing WG threshold on the same heavy-tailed nonconvex problem. At N=65,536, fixed WG has 13.785 times U-SGD's error quantile, whereas the three growing-threshold ratios are near one and their intervals contain one. This demonstrates the effect for the tested schedules.
See Appendix F.4, Table 3 (p. 44).
Question 5
Remark 5.2 provides a criterion before a full run: with known moment bounds, check the Gaussian-dominance budget together with the optimization remainder conditions. With unknown moments, use a short pilot over several budgets and a small threshold grid, select on independent validation, and recheck as the budget grows. Ofc this is just a heuristic, but it usually works.
See Remark 5.2, Eq. (19) (pp. 8–9), Appendix B.8 (pp. 24–26), and the OBD selection protocol in Appendix F.1 (p. 43).