Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum–Gladyshev Noise

Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi · 2026

Read Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum–Gladyshev Noise by Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15314.txt.

Introduction

Antesh Upadhyay, Arda Fazla, and Abolfazl Hashemi study nonconvex stochastic optimization when gradient noise grows with distance from the starting point, the Blum-Gladyshev model. They prove that normalized gradient descent with momentum converges with a single gradient sample per step, and that a variance-reduced variant reaches the best possible rate under mean-square smoothness. The guarantees cover both standard smoothness and a generalized form where curvature scales with gradient size.

Catalog record

CREATORAntesh Upadhyay, Arda Fazla, Abolfazl Hashemi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124512
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15314

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum–Gladyshev Noise Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi Abstract We study nonconvex stochastic optimization under the Blum–Gladyshev ( 𝖡𝖦 \mathsf{BG} -0) noise model, where the stochastic gradient variance grows quadratically with the distance from the initialization. We consider this problem under both standard smoothness and the symmetric generalized-smoothness framework [ 7 ] , which captures objectives whose local curvature can scale with the gradient norm. We prove that normalized stochastic gradient descent with momentum, using only one stochastic gradient per iteration, converges under 𝖡𝖦 \mathsf{BG} -0 noise with oracle complexity 𝒪 ⁡ ( ε − 6 ) \mathcal{O}(\varepsilon^{-6}) . This rate holds both for standard smoothness and for α \alpha -symmetric generalized smoothness, showing that generalized smoothness is rate-neutral for normalized momentum in this setting. We then study a variance-reduced normalized STORM method. Under mean-square smoothness and sharp initialization, the method achieves the minimax optimal 𝒪 ⁡ ( ε − 4 ) \mathcal{O}(\varepsilon^{-4}) complexity, matching the lower bound [ 13 ] . Under expected α \alpha -symmetric generalized smoothness, the STORM recursion couples gradient-dependent smoothness with distance-dependent noise, leading to complexity 𝒪 ⁡ ( ε − ( 4 + α ) ) \mathcal{O}(\varepsilon^{-(4+\alpha)}) for α ∈ ( 0 , 1 ) \alpha\in(0,1) and 𝒪 ⁡ ( ε − 5 ) \mathcal{O}(\varepsilon^{-5}) for α = 1 \alpha=1 . When the distance-growth parameter in the noise model vanishes, our guarantees recover the standard bounded-variance rates: 𝒪 ⁡ ( ε − 4 ) \mathcal{O}(\varepsilon^{-4}) for momentum, 𝒪 ⁡ ( ε − 3 ) \mathcal{O}(\varepsilon^{-3}) for variance reduction, and 𝒪 ⁡ ( ε − 2 ) \mathcal{O}(\varepsilon^{-2}) in the deterministic case. To our knowledge, these are the first convergence guarantees for normalized methods in non-convex stochastic optimization under 𝖡𝖦 \mathsf{BG} -0 noise without bounded domains, increasing batch sizes, or explicit anchoring, covering both standard and generalized smoothness regimes. 1 Introduction Large-scale nonconvex learning is typically formulated as the stochastic optimization problem \min_{x\in\mathbb{R}^{d}}f(x),\qquad f(x):=\mathbb{E}_{\xi}[f(x;\xi)], (1) where f:\mathbb{R}^{d}\to\mathbb{R} is generally nonconvex. The goal is to find an \varepsilon -stationary point, i.e., a point x satisfying \mathbb{E}\|\nabla f(x)\|\leq\varepsilon . Under standard smoothness and uniformly bounded stochastic noise, the complexity theory for this problem is well developed. In the deterministic setting, gradient descent achieves the optimal \mathcal{O}(\varepsilon^{-2}) iteration complexity for smooth nonconvex optimization [ 34 , 35 ] . In the stochastic setting, SGD achieves the classical \mathcal{O}(\varepsilon^{-4}) sample complexity under bounded variance \mathbb{E}_{\xi}\bigl\|\nabla f(x;\xi)-\nabla f(x)\bigr\|^{2}\leq\sigma^{2}, and this rate is unimprovable for general smooth nonconvex stochastic optimization [ 14 , 2 ] . Under stronger mean-square smoothness or average-smoothness conditions, variance-reduced methods such as SVRG, SAGA, SARAH, SPIDER, SpiderBoost, SNVRG, PAGE, and STORM improve the complexity to the optimal \mathcal{O}(\varepsilon^{-3}) [ 23 , 11 , 36 , 12 , 42 , 46 , 31 , 10 ] . These classical stochastic guarantees typically rely on a uniform bounded-noise model. While mathematically convenient, this assumption can fail even in elementary unconstrained stochastic optimization problems, such as least squares, and in modern deep learning, where the stochastic gradient variance is not uniformly constant but can grow as the iterate moves farther from a reference point. This motivates the \mathsf{BG} -0 noise model [ 4 , 15 ] , which has recently been identified as one of the weakest viable variance assumptions for theoretical analysis [ 1 ] . Under \mathsf{BG} -0, the variance is allowed to grow quadratically with the distance from the initialization \mathbb{E}_{\xi}\bigl\|\nabla f(x;\xi)-\nabla f(x)\bigr\|^{2}\leq B^{2}\|x-x^{0}\|^{2}+G^{2}. The classical bounded variance setting is recovered by taking B=0 , while the deterministic case corresponds to B=G=0 . Although \mathsf{BG} -0 is more permissive than bounded variance, it creates an inherent feedback mechanism. If the iterates move far from x^{0} , then the oracle becomes noisier; the larger stochastic noise can then perturb future directions and push the trajectory even farther from x^{0} . Thus, over unbounded domains, the variance scale B^{2}\|x^{k}-x^{0}\|^{2}+G^{2} cannot be treated as a harmless constant. Recently 13 show that this difficulty is intrinsic: under \mathsf{BG} -0 noise, the lower bound for smooth nonconvex optimization worsens from the classical \Omega(\varepsilon^{-4}) to \Omega(\varepsilon^{-6}) , and even under mean-square smoothness, the best possible rate is \Omega(\varepsilon^{-4}) rather than the bounded variance \Omega(\varepsilon^{-3}) rate [ 2 ] . They also proposed PASTA, which matches these limits by combining Halpern-style anchoring [ 18 ] , Tikhonov regularization, and dynamic batching, connecting \mathsf{BG} -0 stochastic approximation with classical fixed-point schemes such as Halpern and Krasnoselskii–Mann iterations [ 32 , 28 , 18 , 13 ] . In this paper, we take a complementary viewpoint. Rather than adding an explicit stabilizing anchor or increasing per-iteration batch sizes, we ask whether normalized stochastic methods with momentum or recursive variance reduction can handle \mathsf{BG} -0 noise without bounded domains. Why Normalization? The key observation is that normalization decouples the length of the update from the magnitude of the stochastic gradient estimator. Given an estimator v^{k} , define d^{k}=\frac{v^{k}}{\|v^{k}\|},\qquad x^{k+1}=x^{k}-\gamma d^{k}. Then, \|x^{k+1}-x^{k}\|=\gamma\|d^{k}\|\leq\gamma, regardless of the size of \|v^{k}\| . Consequently, \|x^{k}-x^{0}\|\leq\sum_{t=0}^{k-1}\|x^{t+1}-x^{t}\|\leq k\gamma. Thus, along a normalized trajectory, the \mathsf{BG} -0 variance scale satisfies \left(B^{2}\|x^{k}-x^{0}\|^{2}+G^{2}\right)^{1/2}\leq G+Bk\gamma. Normalization, therefore, transforms the potentially uncontrolled effect of large stochastic gradient magnitudes into controlled trajectory growth. In contrast, PASTA [ 13 ] controls the \mathsf{BG} -0 variance via dynamic batching. There, the batch size must scale with the upper bound on the local variance, i.e., N_{k}\ \propto\ \tfrac{B^{2}\|x^{k}-x^{0}\|^{2}+G^{2}}{\sigma^{2}} , up to problem-dependent accuracy and step-size factors. Such a rule requires knowledge, or at least reliable estimates, of the variance-growth constants B and G , which may be difficult to obtain in practice. Generalized Smoothness. A second challenge is that many learning objectives are not globally smooth, i.e., their local smoothness can grow with the gradient norm [ 22 , 44 ] . This is a natural setting for normalized updates [ 7 ] . We therefore study \mathsf{BG} -0 noise under the deterministic class \mathcal{L}_{\rm sym}^{*}(\alpha) and its stochastic analogue \mathbb{E}\mathcal{L}_{\rm sym}^{*}(\alpha) from 7 , for \alpha\in(0,1] . The class \mathcal{L}^{*}_{\rm sym}(\alpha) contains standard smooth functions (\mathcal{L}) , asymmetric generalized smooth functions (\mathcal{L}_{\rm asym}^{*}) , and Hessian-based generalized smooth functions (\mathcal{L}_{\rm H}^{*}) , and also includes high-order polynomial and exponential-type objectives [ 7 , 44 , 29 ] . Appendix A summarizes these definitions. Prior work shows that, under suitable bounded or relative variance assumptions, generalized smooth nonconvex optimization can be as efficient as smooth nonconvex optimization: normalized gradient methods recover the deterministic \mathcal{O}(\varepsilon^{-2}) rate, while SPIDER-type variance reduction recovers the stochastic \mathcal{O}(\varepsilon^{-3} ) rate under expected generalized smoothness [ 7 , 12 ] . These results, however, do not address \mathsf{BG} -0 noise. In this setting, the noise level is distance-dependent, while under generalized smoothness, the local curvature is gradient-dependent. This creates a new interplay between trajectory growth and gradient growth that is absent from the bounded variance setting. It is therefore unclear a priori whether the principle that generalized smooth optimization is “as efficient as” smooth optimization continues to hold under \mathsf{BG} -0 noise. This paper studies exactly this interaction. 1.1 Contributions To this end, we develop a convergence theory for normalized stochastic methods under \mathsf{BG} -0 noise across standard and generalized smoothness regimes. The results answer four questions.

Read the complete text