揭示非凸随机优化的理论极限，给出更精确的梯度查询下界。
New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
- 将优化问题转化为函数识别，用散度分解构造难题子类。
- 在L-光滑、准凸等三类函数上给出紧致下界（对数因子内）。
- 一维场景下设计新算法，暗示维度影响复杂性本质。
我们研究了在多种非凸设置下的随机一阶优化基本极限，包括满足拟凸性（QC）、二次增长（QG）和受限割线不等式（RSI）的L-光滑函数。尽管确定性环境下标准算法的收敛性已广为人知，但关于仅能获取无偏噪声梯度的随机情形，现有结果仍有限。本文建立了最小化这类函数所需的噪声梯度查询次数的新下界，并证明这些下界在刻画每类函数的关键参数上均是紧致的（至多对数因子差距）。方法上，将优化任务重构为函数识别问题，利用散度分解构造困难子类以导出紧下界。此外，在一维情形提出专用算法，实现更快收敛率，提示某些维度阈值可能内在决定非凸随机优化的复杂性。
原文摘要 · Abstract (English)
We study fundamental limits of first-order stochastic optimization in a range of nonconvex settings, including L-smooth functions satisfying Quasar-Convexity (QC), Quadratic Growth (QG), and Restricted Secant Inequalities (RSI). While the convergence properties of standard algorithms are well-understood in deterministic regimes, significantly fewer results address the stochastic case, where only unbiased and noisy gradients are available. We establish new lower bounds on the number of noisy gradient queries to minimize these classes of functions, also showing that they are tight (up to a logarithmic factor) in all the relevant quantities characterizing each class. Our approach reformulates the optimization task as a function identification problem, leveraging divergence decomposition arguments to construct a challenging subclass that leads to sharp lower bounds. Furthermore, we present a specialized algorithm in the one-dimensional setting that achieves faster rates, suggesting that certain dimensional thresholds are intrinsic to the complexity of non-convex stochastic optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。