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

• URL: http://arxiv.org/abs/2608.09004v1
• Date: Mon, 10 Aug 2026 01:45:56 GMT
• Title: A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
• Abstract summary: We prove a sharp lower bound for smooth non-adaptive optimization with bounded gradient noise.<n>This matches standard upper bound and resolves the question raised by [Arvani et al.] of whether almost-surely bounded oracle error permits a better than bounded variance.
• Score: 7.7753818665096945
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond [9.865174381229927]
  We focus on the case when suboptimality is measured in terms of the gradient mapping.<n>We bridge this gap to improve the gradient mapping complexity for constrained convex-concave min-max problems.
  arXiv  Detail & Related papers  (2026-09-08T07:51:34Z)
• Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization [12.903796669387809]
  We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses.<n>We establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure, and constraint satisfaction.
  arXiv  Detail & Related papers  (2026-06-06T07:40:55Z)
• Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise [7.692336118507715]
  We study non-smoother optimization under the Blum-Gladyshev ($mathsfBG$-0) noise model.<n>We prove that normalized gradient descent with momentum, using only one parameter per gradient, converges under $mathsfBG$-0 noise with complexity $O(varepsilon-6)$.
  arXiv  Detail & Related papers  (2026-05-14T18:27:49Z)
• Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance [7.788141970705731]
  We address the weakness of the Blum-Glady oracle (Amax-0) condition in gradient analysis and its variants.<n>To match these lower bounds, we consider Prollyxima Anchor (ASTA), a unified algorithmic framework for smooth gradients.
  arXiv  Detail & Related papers  (2026-04-17T18:15:51Z)
• High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
  We show that high-accuracy guarantees for log-concave sampling are achievable using iteration gradients with subexponential tails.<n>Our framework also provides similar high accuracy guarantees under zeroth order (value) queries.
  arXiv  Detail & Related papers  (2026-02-15T23:19:07Z)
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits [53.773695219320125]
  We take a first step toward a theoretical understanding of second-order optimization under heavy-tailed noise.<n>We introduce a novel algorithm based on gradient and Hessian clipping, and prove high-probability upper bounds that nearly match the fundamental limits.
  arXiv  Detail & Related papers  (2025-10-12T16:36:54Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  The Gradient Descent (SGD) algorithm has triggered people's interest due to its good performance in practice but lack of theoretical understanding. It still remains unclear whether the lastiterate convergence can be provably extended to wider composite optimization and non-Euclidean norms.
  arXiv  Detail & Related papers  (2023-12-13T21:41:06Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
  arXiv  Detail & Related papers  (2023-10-27T09:16:58Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  We design step-size schemes that make gradient descent (SGD) adaptive to (i) the noise. We prove that $T$ iterations of SGD with Nesterov iterations can be near optimal. Compared to other step-size schemes, we demonstrate the effectiveness of a novel novel exponential step-size scheme.
  arXiv  Detail & Related papers  (2021-10-21T19:22:14Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.