证明了非凸优化在梯度噪声有界时的最优查询下界。
A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
- 构建了带噪声梯度的随机优化下界模型，采用自适应算法分析。
- 证明所需查询次数为 Ω(ΔL/ε² + ΔLσ²/ε⁴)，与上界一致。
- 解决了一个长期开放问题，适合优化理论研究者阅读。
我们证明了在均匀有界梯度噪声条件下，平滑非凸随机优化的紧下界。在 K=1 的新样本模型中，所有随机自适应算法为找到期望梯度范数不超过 ε 的点，至少需要 Ω(ΔL/ε² + ΔLσ²/ε⁴) 次查询。该下界与标准上界相匹配，据我们所知，解决了 Arjevani 等人（2023）提出的疑问：是否几乎必然有界的预言机误差可带来优于有界方差的收敛率。证明由 GPT-5.6 Sol 在 Codex Ultra 模式下独立生成，人类作者仅负责提示输入及验证、润色论文。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。