mlsanityData to 7 Oct 2026

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

arXiv 2604.16620 ↗First posted 17 Apr 2026cs.LG math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

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 Omega(ε-6) stochastic BG-0 oracle queries for smooth functions and Omega(ε-4) queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e., Omega(ε-4) and Omega(ε-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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 48 of its 71 references that are in the map. First posted on arXiv 17 Apr 2026.

Builds on

48 of 71 references.

References · 48

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  3. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  5. 2017How to Escape Saddle Points Efficientlycited by 284
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  7. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  9. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  10. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  11. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  12. 2017Lower Bounds for Finding Stationary Points Icited by 125
36 more
  1. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  2. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  3. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  4. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  5. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  6. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  7. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  8. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 60
  9. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  10. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  11. 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
  12. 2020Faster Non-Convex Federated Learning via Global and Local Momentumcited by 48
  13. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  14. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  15. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  16. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  17. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 34
  18. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 33
  19. 2020Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimizationcited by 32
  20. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  21. 2023Provable convergence guarantees for black-box variational inferencecited by 29
  22. 2016Gradient Descent Converges to Minimizerscited by 25
  23. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  24. 2023High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noisecited by 22
  25. 2017Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuitycited by 18
  26. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  27. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  28. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  29. 2023Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimizationcited by 11
  30. 2023Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailscited by 11
  31. 2018SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithmscited by 10
  32. 2021Communication-Efficient Variance-Reduced Decentralized Stochastic Optimization over Time-Varying Directed Graphscited by 9
  33. 2023Accelerated stochastic approximation with state-dependent noisecited by 8
  34. 2025A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimizationcited by 8
  35. 2016Dimension-Free Iteration Complexity of Finite Sum Optimization Problemscited by 2
  36. 2026FedSGM: A Unified Framework for Constraint Aware, Bidirectionally Compressed, Multi-Step Federated Optimizationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026SGD for Variational Inference: Tackling Unbounded Variance via Preconditioning and Dynamic Batchingcited by 0
  2. 2026Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Boundscited by 0