Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

Arda Fazla; Ege C. Kaya; Antesh Upadhyay; Abolfazl Hashemi

cs.LGApr 17, 2026

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

Authors: Arda Fazla, Ege C. Kaya, Antesh Upadhyay, Abolfazl Hashemi

Organizations: School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

Abstract

Analysis of Stochastic Gradient Descent (SGD) and its variants typically relies on the assumption of uniformly bounded variance, a condition that frequently fails in practical non-convex settings, such as neural network training, as well as in several elementary optimization settings. While several relaxations are explored in the literature, the Blum-Gladyshev (BG-0) condition, which permits the variance to grow quadratically with distance has recently been shown to be the weakest condition. However, the study of the oracle complexity of stochastic first-order non-convex optimization under BG-0 has remained underexplored. In this paper, we address this gap and establish information-theoretic lower bounds, proving that finding an $ε$ -stationary point requires $Ω(ε^{-6})$ stochastic BG-0 oracle queries for smooth functions and $Ω(ε^{-4})$ queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e., $Ω(ε^{-4})$ and $Ω(ε^{-3})$ for smooth and mean-square smooth cases, respectively. To match these lower bounds, we consider Proximally Anchored STochastic Approximation (PASTA), a unified algorithmic framework that couples Halpern anchoring with Tikhonov regularization to dynamically mitigate the extra variance explosion term permitted by the BG-0 oracle. We prove that PASTA achieves minimax optimal complexities across numerous non-convex regimes, including standard smooth, mean-square smooth, weakly convex, star-convex, and Polyak-Lojasiewicz functions, entirely under an unbounded domain and unbounded stochastic gradients.

Explore similar work

May 14, 2026cs.LG

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

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, 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

O(\varepsilon^{-6})

. This rate holds both for standard smoothness and for

α

-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

O(\varepsilon^{-4})

complexity, matching the lower bound. Under expected

α

-symmetric generalized smoothness, the STORM recursion couples gradient-dependent smoothness with distance-dependent noise, leading to complexity

O(\varepsilon^{-(4+α)})

for

α\in(0,1)

and

O(\varepsilon^{-5})

for

α=1

. When the distance-growth parameter in the noise model vanishes, our guarantees recover the standard bounded-variance rates:

O(\varepsilon^{-4})

for momentum,

O(\varepsilon^{-3})

for variance reduction, and

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.

Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi

Stochastic Smooth Convex Optimization Convex Optimization Stochastic Gradient Descent Nonconvex Smoothing Gaussian Noise+1

Ask PDF

Aug 10, 2026math.OC

A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise

We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the

K=1

fresh-sample model, every randomized adaptive algorithm requires

Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)

queries to find a point with expected gradient norm at most

ε

. This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.

Jikai Jin

Stochastic Smooth Convex Optimization Stochastic Optimization Convex Optimization Optimal Sample Complexity Lower Bounds

Ask PDF

May 8, 2026cs.LG

SGD for Variational Inference: Tackling Unbounded Variance via Preconditioning and Dynamic Batching

Black-Box Variational Inference (BBVI) typically relies on Stochastic Gradient Descent (SGD) to optimize the Evidence Lower Bound (ELBO). However, the stochastic gradients in BBVI inherently exhibit unbounded variance, violating standard assumptions and instead satisfying the weaker Blum-Gladyshev (BG) condition, where variance grows quadratically with distance from the optimum. In this paper, we bridge the gap between stochastic optimization theory and the practical instances of BBVI. Focusing on the broad elliptic location-scale family of parameterized distributions, we offer two main contributions. First, we prove the existence of an ELBO solution, a foundational property usually assumed a priori in the literature. Second, we establish comprehensive convergence guarantees spanning finite-time and asymptotic regimes for Minibatch Projected SGD (PSGD) equipped with dynamic batching and preconditioning under the BG condition. Our theoretical framework demonstrates that dynamic batching combined with preconditioning systematically enables rigorous guarantees even in complex settings. We illustrate our theoretical findings with numerical results, highlighting the efficacy of our approach for modern inference tasks.

Hippolyte Labarrière, Cesare Molinari, Silvia Villa +1

Variational Inference Mini-Batch Stochastic Gradient Descent Stochastic Gradient Descent Stochastic Optimization Well-Tuned Static Batching Policy

Ask PDF