提出新算法与理论下界，解决无界方差下的非凸优化难题
Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
- 引入动态正则化机制缓解方差爆炸问题
- 证明找到ε-驻点至少需Ω(ε⁻⁶)次查询（光滑函数）
- 适合研究非凸优化理论或训练深层神经网络的读者
Stochastic Gradient Descent (SGD) 及其变体通常依赖于方差有界的假设，该假设在实际非凸场景（如神经网络训练）中常不成立。近期研究指出，允许方差随距离平方增长的 Blum-Gladyshev (BG-0) 条件是最弱的放宽条件。然而，基于 BG-0 条件的随机一阶非凸优化的最优复杂度仍未被充分研究。本文填补这一空白，建立信息论下界：对光滑函数，找到 ε-驻点至少需 Ω(ε⁻⁶) 次随机 BG-0 查询；在均方光滑条件下，需 Ω(ε⁻⁴) 次查询。这表明相比经典有界方差情形（分别为 Ω(ε⁻⁴) 与 Ω(ε⁻³)），复杂度不可避免恶化。为匹配此下界，本文提出统一算法框架 PASTA，结合 Halpern 锚定与 Tikhonov 正则化，动态抑制由 BG-0 允许的额外方差爆炸项。我们证明 PASTA 在多种非凸情形（包括标准光滑、均方光滑、弱凸、星凸及 Polyak-Lojasiewicz 函数）下达到极小极大最优复杂度，且完全适用于无界域与无界随机梯度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。