acceptodds
Under review as a conference paper at ICLR 2027

Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness

Abstract

We study stochastic convex optimization under asymmetric -generalized smoothness, a model motivated by machine-learning objectives whose local curvature may grow with the gradient norm. We assume an unbiased first-order oracle with additive norm-sub-Gaussian noise. Acceleration is difficult in this setting because momentum may enter regions of much larger curvature, while stochastic gradients cannot reliably certify an unrestricted trajectory. We propose ARC-SG, a two-phase accelerated method: Phase I reduces excessively large gradients using a generalized-smoothness-aware stochastic step, then Phase II solves strongly convex proximal subproblems by a restarted accelerated solver confined to certified smoothness balls. Exact proximal points do not increase the gradient norm, allowing these certificates to propagate through the outer loop. The contribution is a query-by-query certified-localization construction with explicit generalized-smoothness factors and a strongly convex restart extension. ARC-SG achieves, with high probability, an accelerated optimization contribution and smooth-subclass-optimal statistical dependence on accuracy, up to logarithmic and generalized-smoothness factors. Its convex accuracy exponents agree with a contemporaneous public stochastic-acceleration result under a broader smoothness and affine-variance model; our distinction is the certified geometry, explicit parameter accounting, and strongly convex guarantee. The results recover classical accelerated stochastic rates when . Experiments on objectives with unbounded gradients illustrate the two-phase mechanism and its finite-budget advantage.

Primary area:
optimization
Keywords:
convex optimization, stochastic optimization, generalized smoothness, accelerated methods

Reviews

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

The authors study convex optimization under generalized smoothness and light-tailed (sub-Gaussian), unbiased stochastic gradients. The authors provide an algorithm based on two phases.

Critical strengths
  1. The writing is very poor, and reads as if it was mostly AI-written, without much cleanup.
Critical weaknesses
  1. The writing is very poor, and reads as if it was mostly AI-written, without much cleanup.
    • Some of the presentation doesn’t feel that intuitive, e.g. I think the algorithm should be introduced, along with intuition for what the two phases do again before the introduction of Lemmas 1-4. In particular, Lemmas 1-4 seem to be technical results, and should be deferred to after Section 3.
    • The paragraph titles are not constructed in a linear fashion (e.g. describing Phase I)
Questions for authors
  1. I wonder if the paper may be overcomplicating the algorithm for this generalized smoothness setup. Shouldn’t it be possible to use two black-box solvers for the two phases?

I’m not super familiar with optimization under generalized smoothness, so please correct me if I’m wrong.

Reviewer_MNvGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces ARC-SG, an algorithm that couples gradient stabilization with restarted accelerated solvers on localized proximal subproblems to tackle asymmetric generalized smoothness. The authors establish high-probability oracle complexity bounds for both convex and strongly convex regimes, recover standard smooth rates when L1=0L_1=0, and demonstrate the framework on synthetic objectives with unbounded gradients.

Critical strengths
  1. The certified-ball mechanism directly addresses the core technical bottleneck: keeping stochastic momentum iterates inside domains where generalized smoothness yields valid curvature bounds.
  2. The work provides high-probability bounds for convex and strongly convex settings with explicit dependencies on L0L_0 and L1L_1. It recovers classical exponents in the smooth limit.
Critical weaknesses
  1. The incremental contribution is narrower than the introduction implies. In the convex setting, RSAG already achieves high-probability stochastic acceleration under a more general smoothness and affine-variance framework. Consequently, the primary contributions here are the specific geometric certification, explicit parameter tracking, and the extension to strong convexity. Furthermore, the dominant terms include κˉ1/2\bar\kappa^{1/2} and κˉ3\bar\kappa^3 factors that the authors acknowledge are likely loose, and the deterministic reduction is strictly worse than known methods.

  2. There is a pronounced disconnect between the theoretical algorithm and its practical implementation. As noted in the appendix, matching the target accuracy in the convex experiment would theoretically require around 4×1064\times 10^6 localization levels and over 3×10183\times 10^{18} oracle queries. To make it runnable, the empirical evaluation relies on a heavily modified heuristic where late-stage convergence is largely driven by an unanalyzed Polyak–Juditsky averaging step. Neither the theoretical finisher nor several key hop transitions are actually triggered. Thus, while the experiments support the general conceptual design, they do not test the exact algorithm or complexity bounds presented in the theorems.

Questions for authors
  1. Is it possible to establish formal guarantees for the practical variant of ARC-SG, specifically accounting for the Polyak–Juditsky averaging step and relaxed stopping criteria? If not, could you demonstrate a realistic experiment where the exact theoretical schedule and finisher are executed as analyzed?
  2. Could you provide a direct, side-by-side comparison with RSAG under additive noise that retains all L1RL_1R-dependent factors? Specifically, which aspects of Theorem 2 cannot be obtained simply by applying standard restarting or regularization techniques to existing convex bounds?
  3. Does the massive worst-case level schedule stem purely from conservative constants in the proof, or can you construct a problem class where a comparable number of localization stages is genuinely unavoidable?
Reviewer_znhyOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper is concerned with stochastic optimization under generalized smoothness.

Critical strengths

None

Critical weaknesses

Specific comments supporting my review (I stopped where I could not follow anymore):

l042: "and motivates clipped or normalized steps" not clear at this point l053: "our norm-sub-Gaussian oracle is its additive-only specialization": does not make sense l055: "stochastic query" : what does it mean in an optimization context ? l056: "The statistical benchmarks are ": impossible to understand what the \Theta are about

l068 : "A gradient-scale regularization floor contains the exact prox, while proximal monotonicity, transfer bounds, and a travel–halving argument propagate the certificate and ensure termination." : How am I supposed to understand this ?

l09: "not priority for each ingredient in isolation." does not make sense

l105: "hides only absolute constants and polylogarithmic factors in the displayed dimensionless problem ratios" not clear

l120: "Let F contain all randomness observed before an oracle call, " what is F ? what is a measurable point ? the definition of sub-Gaussianity is not classical for me, ref needed.

l145: "the classical descent lemma" : what it is ?

The proof of Lemma 1 is badly written (arguments are not given to justify each steps)

Lemma 2 is badly formulated Same for Lemma 2, the first inequality f^\star \leq .... is not well justified I checked other proofs, the writing is of the same style and not adequate for typical human proof-checking

l237 : "We use it with epoch restarts on shrinking certified balls" does not mean anything at this point

Questions for authors

Can the authors fix their paper ?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.