- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper analyzes nonconvex optimization of SGD under BG-0 conditions, which extends the uniformly bounded variance. The authors provide bounds for smooth functions and for mean-square smoothness. The authors futher provide a unified framework which achieve minimax optimal complexities across various non-convex regimes. Overall, the paper is clear and well-written, and provide useful insights for the community.
Critical strengths
This paper focuses on an important question of BG-0 analysis, which closely relates to the deep learning regimes. The authors further provide a unified framework, which is interesting. This paper is well-written, and easy-to-follow.
Critical weaknesses
I did not find clear weakness of this paper. But I do suggest the authors providing theoretical challenges on the BG-0 analysis, and how these challenges stop the analysis of non-convex optimization.
Questions for authors
See above, what is the main challenges on the BG-0 analysis under non-convex optimization?
2 comments
I read the reponse and the other reviewers' comments. I keep my score unchanged (3).
Response to Reviewer V54v
W1 & Q1
We thank the reviewer for this valuable suggestion. The main challenges of analyzing non-convex optimization under BG-0 arise both in establishing convergence guarantees and in establishing the fundamental oracle complexity.
Challenges in convergence analysis. Unlike the classical bounded-variance assumption, BG-0 allows the stochastic gradient variance to grow quadratically with the distance from initialization. This introduces an additional term proportional to B2∥xt−x0∥2 in the standard descent analysis. Under bounded variance, this noise contribution is uniformly controlled. However, in general non-convex optimization, a decrease in the objective value does not necessarily control the distance traveled by the iterates. As a result, the standard descent-based arguments cannot directly take care of this additional variance term, particularly over unbounded domains.
Alacaoglu et al. (2025) address BG-0 noise in convex optimization through Halpern anchoring, leveraging convexity to obtain the geometric control needed to stabilize the iterates. Extending this approach to non-convex problems is challenging because the underlying convexity-based contraction is no longer available. Moreover, anchoring the iterates to a fixed reference point can introduce a persistent bias relative to the stationary points of the original objective. Our work addresses these difficulties through dynamic batching and variance reduction for smooth non-convex objectives, and through coupled proximal anchoring with epoch-wise anchor updates for weakly convex objectives.
Challenges in establishing lower bounds. Beyond upper bound convergence guarantees, a more important question is whether these classical non-convex oracle complexities remain optimal under BG-0. The lower-bound constructions of Arjevani et al. (2023) rely on uniformly bounded stochastic gradient variance, where the difficulty of revealing successive coordinates of a stochastic zero-chain is independent of the distance from initialization. Under BG-0, however, the oracle noise can increase substantially as the algorithm moves through the optimization landscape. To capture this additional difficulty, we need a fundamentally different hard-instance construction.
To address this, we introduce a one-dimensional travel function coupled with a smoothly activated and shifted stochastic zero-chain. The construction forces any algorithm seeking an ϵ-stationary point to reach a region at distance Θ(Δ/ϵ) from initialization, where the permitted variance scales as Θ(B2Δ2/ϵ2+G2). This increased variance makes discovering the subsequent zero-chain coordinates significantly harder, while the construction must still preserve global smoothness and the initial function-gap constraint. Under mean-square smoothness, the additional challenge is to maintain the stochastic gradient-difference regularity while exploiting the distance-dependent variance.
Our lower bounds show that these challenges are intrinsic to the BG-0 oracle model, rather than merely limitations of existing convergence analyses. Specifically, the classical bounded-variance lower bounds of Ω(ϵ−4) and Ω(ϵ−3) remain valid but are no longer tight. We establish the stronger bounds of Ω(ϵ−6) under smoothness and Ω(ϵ−4) under mean-square smoothness, and provide matching upper bounds. We expanded the discussion in the revised manuscript to make these theoretical challenges and their distinction from prior work clearer.