acceptodds
Under review as a conference paper at ICLR 2027

Accelerated Stochastic Method under -Smoothness and Heavy-Tailed Noise

Abstract

We develop an accelerated stochastic method for convex -smooth optimization under heavy-tailed noise. The unbiased oracle has a finite -th noise moment, , with constant, gradient-dependent, and gap-dependent terms. Our method combines accelerated updates with clipping, projection, and phase restarts. Each iteration uses a single stochastic-gradient sample, without minibatching. We prove high-probability convergence to any desired accuracy despite clipping bias. The deterministic terms retain square-root dependence on both and . In our three-component noise model, strong convexity leaves a polynomial accuracy cost only for the constant component; without it, the dependence is logarithmic even for . More generally, for noise moments scaling as , the stochastic cost becomes logarithmic at for convex objectives and under strong convexity.

Primary area:
optimization
Keywords:
stochastic optimization, heavy-tailed noise, gradient clipping, accelerated methods, high-probability convergence

Reviews

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

This paper investigates an accelerated stochastic first-order method that adopts restarting and gradient clipping for (H0,H1)(H_0,H_1)-smooth, convex stochastic optimization. The underlying randomness is assumed to admit a finite ppth moment for some p: 1<p≤2p:\,1<p\leq 2. The results match with best known bounds under similar but stronger conditions.

Critical strengths
  • The extensions to weaker conditions.
  • Seems to have achieved best known bounds.
Critical weaknesses

W1. Several theoretical statements and their proofs are not rigorous or presents what seems to be AI artifacts that have not been carefully audited/verified by human author. Below are a few examples of possible multiple occurrences of similar issues: (a) significant parts of them are in high-level language without explicit math descriptions (e.g., Lemma 16). (b) Statements like "no claim is made that all upper and lower confidence logarithms coincide" is in the statement of Theorem 17. (c) Theorem 17 makes claim on stochastic methods but the proof only verifies deterministic methods.

W2. The synthetic experiment lacks essential reproduction details.

Questions for authors

Can the reviewers provide initial solutions, data generating process, parameters/ways to tuning parameters, and how the baselines are implemented/tuned, etc?

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

The paper presents an accelerated stochastic method for convex objectives satisfying (H_0, H_1)-smoothness, where the local quadratic model depends on the objective gap. The oracle is unbiased with a finite pp-th noise moment, 1<p≤21<p\le 2 and allows constant, gradient-dependent, and gap-dependent terms. The method (RCSAG) combines a three-sequence accelerated update with clipping, projection and gap-halving restarts, uses one sample per iteration, and proves high-probability convergence to any target accuracy with no clipping-induced error floor. The paper also gives strongly convex lower bounds and experiments on a binary real-data task and a heavy-tailed synthetic oracle.

Critical strengths
  1. Localization is handled where momentum makes it hard. Especially, Lemmas 4-5 check both displacements the local model needs, and A0=D2/ΔA_0 = D^2/\Delta keeps early mixing under control.
  2. The stopped-process argument is clean. The predictable indicator keeps both channels martingales, and the clipping estimates and recursion hold up.
Critical weaknesses
  1. Theorem 17 does not establish its lower bound for arbitrary stochastic first-order methods. Lemma 16 requires a common hard distribution under which every admissible exact-gradient method using fewer than KK queries fails with constant probability. The deterministic zero-chain construction cited in Theorem 17 does not by itself establish this premise. The authors should supply a distributional lower bound valid for the claimed algorithm class, or explicitly restrict the theorem to a class for which the zero-chain argument applies.
  2. The empirical comparison needs a tuning-robustness check. In two real-data weight regimes, both SSTM variants select the smallest tested weight parameter and largest clipping parameter, suggesting that the grids should be expanded. In the synthetic experiment, configurations are selected by mean log gap across checkpoints, whereas the conclusions emphasize terminal accuracy and attainment of relative gap 10−610^{-6}. A comparison selecting for terminal gap would settle this.
Questions for authors
  1. Which distributional lower bound supplies Lemma 16's premise?
  2. Do the SSTM comparisons still hold across wider grids and a terminal-gap selection rule?
Reviewer_wBvuOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes RCSAG (Restarted Clipped Stochastic Accelerated Gradient), an accelerated method for convex and strongly convex objectives satisfying a first-order (H0,H1)−(H_0, H_1)-smoothness condition (local upper model valid only within radius rHr_H, with curvature scale $H_0+H_1F(x)) and a mixed heavy-tailed noise model with 1<p≤21<p \le 2. Experiments on a kernelized linear head with frozen DINOv2 features compare against Clipped SGD, Clipped-SSTM, and R-clipped-SSTM.

Critical strengths

The paper is clearly written and well structured, with a logical progression from problem setup through the one-phase analysis to the end-to-end convergence results, making it easy to follow despite the technical density.

  1. The one-phase analysis is carefully structured, and it seems to me that the single-sample clipping without mini-batching or an error floor is the headline algorithmic contribution.
Critical weaknesses

The one-phase guarantee requires the auxiliary set QQ to contain x∗x^*, which is a strong requirement.

  1. The convex setting is of relatively limited interest in the community, as many practical applications are non-convex.

  2. In Appendix G, the requirement of κσ1\kappa \sigma_1 is too strong in practice.

  3. The p=2p=2 specialization is given in Appendix H.1, but the main text's claims are for general p∈(1,2]p\in (1,2].

Questions for authors

Is the JH3J_H^3 factor in Theorem 9's σ1\sigma_1 term necessary, or an artifact of the r=q/2r=q/2 application of Lemma 12? Can it be reduced to JHJ_H or JH1+o(1)J_H^{1+o(1)} with a sharper accounting?

  1. In the convex case, can the requirement x∗∈Qx^* \in Q be removed (e.g., by an expanding-domain scheme) without losing the accelerated rate? If not, the convex result should be stated as requiring a known bounded set containing a minimizer, and the abstract should reflect this.

  2. For p=2p=2, does the bound match the known accelerated results?

  3. In the experiments, how sensitive is the result to the Pareto shape parameter? Does RCSAG's advantage persist for shape 1.1 (heavier tails) or 1.9 (lighter tails)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.