不加剪裁的随机算法也能在重尾噪声下最优求解凸优化问题。
Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
- 用原始随机近端次梯度法，无需剪裁或归一化。
- 在平滑、弱平滑、非平滑情况下均达最优复杂度。
- 适合研究鲁棒优化与理论分析的学者参考。
我们研究凸复合优化问题，目标函数由一个可近端处理的函数与一个子梯度受重尾噪声估计的凸函数组成。现有方法常使用梯度剪裁或归一化应对重尾噪声。本文证明，无需额外修改（如剪裁或归一化）的原始随机算法即可达到该类问题的最优复杂度。具体而言，加速的随机近端次梯度法在光滑、弱光滑和非光滑凸优化，以及重尾噪声下的随机凸优化中，均实现通用最优的一阶黑箱复杂度。数值实验验证了理论结果。
原文摘要 · Abstract (English)
We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. In this paper, we demonstrate that a vanilla stochastic algorithm -- without additional modifications such as clipping or normalization -- can achieve optimal complexity for these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Numerical experiments are further provided to validate our theoretical results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。