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

• URL: http://arxiv.org/abs/2604.16620v1
• Date: Fri, 17 Apr 2026 18:15:51 GMT
• Title: Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
• Abstract summary: 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.
• Score: 7.788141970705731
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

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)
• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max optimization has attracted increasing attention due to its applications in modern machine learning.<n>We provide a comprehensive theoretical of gradient descent (SGDA)<n>We develop new clipping-free algorithms, i.e., Stoc-GDAM and Stoc-TRmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
  arXiv  Detail & Related papers  (2026-09-05T12:49:28Z)
• Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size [43.46286813814826]
  Bregman finite proximal ergo gradient (BPSG) methods bring variance-reduced composite size to objectives whose geometry is poorly captured by Euclidean smoothness.<n>Their performance remains sensitive to stepwise: raw curvature estimates can fluctuate, whereas line searches add repeated searches.<n>We introduce AdaBPSG, a line-search method that combines sparse values and a non-negative matrix factorization rate.
  arXiv  Detail & Related papers  (2026-08-12T12:46:05Z)
• A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition [39.146761527401424]
  This work introduces a proximal subgradient method for minimizing the sum of an expected cost.<n>We use the Kurdyka-Lojasiewicz (KL) property to guarantee convergence of the whole trajectory to a single stationary point.
  arXiv  Detail & Related papers  (2026-08-05T23:07:27Z)
• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) is a machine learning project of large-scale optimization, yet its theoretical behavior under heavy-tailed noise is poorly understood.<n>We rigorously investigate whether SGD, can provably succeed under such adverse conditions.
  arXiv  Detail & Related papers  (2025-08-06T20:09:41Z)
• Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
  Adaptive gradient methods are among the most successful neural network training algorithms.<n>These methods are known to achieve better dimensional dependence than over convex SGD-normarity.<n>In this paper we introduce new assumptions on the smoothness of the structure and the gradient noise variance.
  arXiv  Detail & Related papers  (2024-06-07T02:55:57Z)
• A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions [7.972544890243396]
  This paper presents a unified analysis for the proximal subgradient method (Prox-SubGrad) type approach. We are able to relate error-bound conditions, the growth conditions of the subgradients of the objective, and the behavior of the proximal subgradient iterates on some remarkably broad classes of objective functions.
  arXiv  Detail & Related papers  (2023-08-30T23:34:11Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  An analysis of convex and non- optimization methods often requires the Lipsitzness gradient, which limits the analysis by this trajectorys. Recent work generalizes the gradient setting via the non-uniform smoothness condition.
  arXiv  Detail & Related papers  (2023-06-02T04:21:59Z)
• Projective Proximal Gradient Descent for A Class of Nonconvex Nonsmooth Optimization Problems: Fast Convergence Without Kurdyka-Lojasiewicz (KL) Property [19.988762532185884]
  Non and nonsmooth optimization problems are important and challenging for learning. In this paper, we show a new analysis showing fast convergence of PPGD.
  arXiv  Detail & Related papers  (2023-04-20T17:39:24Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective [49.17352150219212]
  Federated AveragingFedAvg, also known as Local SGD, is one of the most popular algorithms in Federated Learning (FL) We show how to analyze this quantity from the Differential Equation (SDE) perspective.
  arXiv  Detail & Related papers  (2021-11-05T22:16:11Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation [17.199023009789308]
  The Expected assumption of SGD (SGD) is being used routinely for non-artisan functions. In this paper, we show a paradigms for convergence to a smooth non-linear setting. We also provide theoretical guarantees for different step-size conditions.
  arXiv  Detail & Related papers  (2020-06-18T07:05:56Z)

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.