acceptodds
Under review as a conference paper at ICLR 2027

Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise

Abstract

Gradient clipping is widely used to stabilize training, but it need not improve the statistical accuracy of averaged SGD, even under heavy-tailed noise. We derive a finite-sample comparison of clipped and unclipped Polyak-Ruppert averaged SGD under finite conditional -th moments, . Our main result gives explicit accuracy and confidence conditions under which, for , the Gaussian term dominates the unclipped deviation bound, so clipping need not improve its leading order. By balancing clipping bias and concentration, we obtain a bound in which the heavy-tail correction depends logarithmically rather than polynomially on the inverse failure probability. At , this improves the confidence dependence of the leading bound. We establish sharpness of the unclipped heavy-tail term through an exact one-dimensional quadratic recursion and extend the comparison to projected convex SGD. We also prove concrete costs of clipping: every fixed finite threshold increases asymptotic variance on a scalar Gaussian quadratic, while whole-gradient clipping can shift the limiting point under asymmetric noise.

Primary area:
optimization
Keywords:
stochastic optimization, stochastic gradient descent, gradient clipping, Polyak-Ruppert averaging, stochastic approximation, high-probability guarantees, heavy-tailed noise.

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_fmzXOpenReview ↗
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 pp-th moment assumption (p≥2p≥2), 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 p>2p>2, for a fixed confidence δ\delta, the decay rate of the heavy-tail correction is N−(1−1/p)N^{-(1-1/p)}, which is faster than the Gaussian term N−1/2N^{-1/2}; 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 δ\delta from polynomial order δ−1/p\delta^{-1/p} to logarithmic order (log⁡(1/δ)1−1/p\log(1/\delta)^{1-1/p}); at p=2p=2 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 σp\sigma_p, whole-gradient clipping depends on the full-gradient moment GpG_p, 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 σp\sigma_p, while in Theorem 3.2 the correction for WG-Clip uses the full-gradient moment GpG_p. Since GpG_p also contains a signal term (∣∣∇F(x∗)∣∣+Lr||\nabla F(x^*)|| + Lr), in scenarios where the full-gradient moment is much larger than σp\sigma_p, 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 pp-dependent constants (KpK_p, CpC_p) 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 p>4p>4 requires comparing N1/pN^{1/p} with δ1/pℓ1/2\delta^{1/p} \ell^{1/2}; in common high-confidence regimes this may require very large sample sizes.

3.The balanced threshold λ=Mp(N/ℓδ)1/p\lambda=M_p(N/\ell_{\delta})^{1/p} depends on unknown constants MpM_p. 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 GpG_p in Theorem 3.2 were replaced by σp\sigma_p (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 p>2p>2 the heavy-tail correction decays faster than the Gaussian term, but this relies on a fixed δ\delta. 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 p>2p>2 but N is not large enough to enter the Gaussian-dominated regime?

3.In Figure 1(b), threshold λ=5\lambda=5 still helps at N=4194304N=4194304 (RClip=0.79R_Clip=0.79), but crosses after N=8388608N=8388608. At N=4194304N=4194304, is λ=5\lambda=5 also optimal among all scanned thresholds? In Figure 1(c), at N=4194304N=4194304 the optimal λ=10\lambda=10 has ratio 0.670.67, while in Figure 1(b) λ=5\lambda=5 at that point has ratio 0.790.79, indicating that conclusions are sensitive to λ\lambda. Could the authors report a complete error table for different λ\lambda and different budgets so readers can understand the sensitivity of threshold selection?

4.The theory suggests that the optimal clipping threshold should grow as N1/pN^{1/p}. 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

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\sigma_p, allowing a direct comparison with U-SGD. Also the common full-gradient second-moment bound G2G_2 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=3p = 3, 44 and 66. We also clarify that the additional p>4p > 4 condition becomes weaker as δ\delta tends to zero. The large sufficient budgets instead arise from the main Gaussian-dominance condition, especially near p=2p = 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\sigma_2 and σp\sigma_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,536N = 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=256N = 256, that same threshold improves the error. Appendix A.3 also allows δ\delta to decrease with NN.

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=222N = 2^{22}, 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 2222^{22}, with absolute U-SGD errors and the supplementary CSV provides unrounded errors and intervals. Only U-SGD and threshold 5 were evaluated beyond 2222^{22}.

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,536N = 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).

Thanks for the authors' detailed response. It addresses my concern. I will hold my score.

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

This paper studies the statistical trade-offs between clipped and unclipped averaged SGD under finite conditional p-th moments, distinguishing when clipping improves the leading high-probability guarantee from when it only improves a lower-order correction, and examining the bias and asymptotic-efficiency costs of fixed-threshold clipping

Critical strengths
  1. A meaningful theoretical contribution through explicit comparison. The accuracy–confidence conditions in Proposition 5.1 quantify when unclipped averaging becomes Gaussian-dominated, making the distinction between p=2 and p>2 precise rather than merely asymptotic or qualitative.
  2. A clear connection between finite sample benefits and asymptotic costs. Section 4 provides concrete examples showing that reducing update variance need not improve the averaged estimator’s efficiency, and that fixed whole-gradient clipping can shift the limiting target under asymmetric noise.
Critical weaknesses

The practical guidance remains conditional. The experiment is restricted to a quadratic prediction task with fixed-threshold clipping, and therefore does not establish how broadly the conclusions extend to adaptive thresholds or more general learning problems.

Questions for authors

For Corollary A.2, the Theorem A.1 requires deterministic almost-sure upper bounds on the conditional moment budgets. However, Corollary A.2 allows arbitrary predictable random weights, while the right-hand side of (19) uses the realized quantities ∑kwk2\sum_k w_k^2 and ∑k∣wk∣p\sum_k |w_k|^p, which can themselves be random. Predictability ensures that wkζkw_k \zeta_k remains a martingale difference, but does not appear sufficient to justify substituting these random quantities for the deterministic budgets in Theorem A.1. Could the authors clarify whether additional assumptions on the weights are intended, or provide a separate argument establishing (19) as stated?

2 comments

Weakness 1

We have made the distinction explicit: known moment bounds provide a sufficient budget criterion, while unknown moments call for empirical calibration using a short pilot and independent validation across several budgets. Appendix B.8 supplies numerical constants and full optimization conditions. Appendix F.6 tests thresholds based on past gradients.

See Remark 5.2 (pp. 8–9), Appendix B.8 (pp. 24–26), and Appendix F.6 (pp. 46–47).

Weakness 2

We have added a nonconvex heavy-tailed experiment with fixed, horizon-dependent and online growing thresholds, plus an experiment from x0=2x_0 = 2 using thresholds computed from past gradients. Appendix H adds two analytical nonconvex results under explicit assumptions.

See Appendix F.4, Table 3 (p. 44); Appendix F.6, Table 6 (pp. 46–47); and Propositions H.1–H.2 (pp. 49–52).

Question 1

You are correct: predictability alone does not justify substituting realized random moment budgets. We have corrected Corollary A.2 to require deterministic almost-sure upper bounds B2B_2 and BpB_p on the sums of squared and ppth-power weights. Appendix G.1 uses the same corrected condition. The convex and quadratic proofs already use deterministic upper bounds on these budgets.

See Corollary A.2, Eqs. (21)–(22) (p. 14), and Appendix G.1 (p. 47).

Thanks for the authors' detailed response. It addresses my concern. I will hold my score.

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

The paper analyzes finite sample tradeoffs for averaged SGD, and examines comparisons between a non-clipped and a clipped version of the method.

Critical strengths

The paper provides interesting high probability bounds on finite sample complexity of projected SGD and clipped SGD for convex problems and noise moment conditions when moments of order p>=2 exist.

The paper seems to provide novel guidelines on the studied setting in Table 1. It would be good to move it to the main text, I believe.

Critical weaknesses

Comparisons with existing works are not sufficiently clearly articulated. Existing work should be discussed in greater detail so that novelty of the paper can be better assessed. For example, clarify the novelty in the high probability bounds derived in Theorems 3.1 and 3.2 when compared with existing works; does the novelty arise due to the different assumptions made. If so, why is the assumed setting useful when compared with standard settings. Or the novelty arises under equivalent assumptions but due to a different analytical technique. If so, what novel analytical techniques are used. How do the achieved bounds compare with state of the art non-smooth stochastic convex optimization results? How does the higher order terms characterization derived here compare with existing results of this type, if any? What would happen if a different function/problem class is assumed for clipped versus non-clipped comparison? Any further hints for non-convex regimes that are of most interest in the learning community would be useful.

Questions for authors

N/A.

2 comments

Weakness 1

We have expanded the related-work discussion to distinguish our setting and contribution. The contribution is a joint U-SGD/WG/NC comparison that keeps noise and full-gradient moments separate and identifies accuracy–confidence regimes where clipping changes the leading guarantee. We explicitly acknowledge earlier Gaussian-plus-polynomial bounds for linear regression and stochastic mirror descent.

See Section 1, Related work (p. 2); Theorems 3.1–3.2 and Corollary 3.3 (p. 5); Proposition 5.1 (p. 8).

Weakness 2

Theorems 3.1–3.2 give a variance-sensitive comparison for bounded-domain, possibly nonsmooth convex problems for every p>2p > 2, including noise with an infinite fourth moment. The proof combines known Fuk–Nagaev, Bernstein–Freedman and martingale von Bahr–Esseen inequalities. Controlling the squared-noise term through its p/2p/2 moment retains the centered variance scale in the leading term and the full-gradient moment in the WG bias.

See Section 3 (pp. 4–5) and Appendices B.2–B.3 (pp. 19–21).

Weakness 3

Section 3.1 now compares our nonsmooth convex bounds with Liu–Zhou (2023) and Liu (2026). At p=2p = 2, the clipped calibration has the same square-root dependence on log⁡(1/δ)/N\log(1/\delta)/N. For p>2p > 2, our comparison separates the variance term from the faster-decaying moment and clipping corrections at fixed confidence, and states when U-SGD matches the leading clipped guarantee.

See Section 3.1, Eqs. (11)–(12) (p. 6), and Theorems 3.1–3.2 (p. 5).

Weakness 4

We have clarified the comparison with the Gaussian-plus-polynomial bounds of Lou–Zhu–Wu (2022) and Eldowa–Paudice (2024) in Related Work. Our joint clipped–unclipped optimization bounds explicitly control squared-gradient remainders for every p>2p>2, including without a finite fourth moment, and give conditions for absorbing them into the heavy-tail corrections.

Weakness 5

We now give results for two further classes. Appendix C treats strongly convex quadratics using epoch averaging and restarts. Proposition H.1 treats smooth nonconvex objectives using average squared-gradient stationarity under uniform moment bounds, while Proposition H.2 shows that fixed WG can converge to a nonstationary point although U-SGD converges to the minimizer.

See Section 3.3 (p. 7), Theorem C.9 and Corollary C.10 (p. 31), and Propositions H.1–H.2 (pp. 49–52).

Weakness 6

We have added two nonconvex results with complete proofs. Proposition H.1 compares U-SGD, WG and NC for average squared-gradient stationarity under uniform conditional moment bounds. Proposition H.2 gives an explicit heavy-tailed example where fixed WG and its arithmetic averages converge to a nonstationary point, whereas U-SGD and its averages converge to the minimizer.

See Appendix H, Propositions H.1–H.2 (pp. 49–52).

Recommendation

Thank you for the suggestion. We have moved Table 1 to the main text, immediately after Proposition 5.1.

See Section 5, Table 1 (p. 8).

Thank you for the responses, much appreciated. I will maintain the score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.