普通SGD仅靠二阶矩就达到极小极大最优复杂度，无需裁剪或动量！
Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
📖 AI 总结
该研究探讨了在距离依赖条件矩假设下，普通单样本随机梯度下降（SGD）用于光滑、有下界且可能非凸目标函数时的收敛性质。传统分析通常要求噪声矩一致有界，从而排除了梯度变异性随迭代点远离最优解而增大的情形。作者仅依赖二阶矩条件，通过直接的下降—位移论证，证明了采用与时间跨度相关的步长时，期望平均平方梯度可达到T的负三分之一次方量级的平稳性。其显式复杂度推论与已知的光滑Blum-Gladyshev下界相匹配，表明未作任何修改的SGD在该二阶矩类中即达到极小极大随机复杂度。对于p大于2的情形，作者利用可预测局部化与Hilbert空间Fuk-Nagaev不等式，给出了高概率界，将方差的对数贡献与稀有冲击的多项式贡献分离，且局部化半径由递推关系直接导出，无需有界迭代、裁剪、归一化、动量或增大批量等假设。论文还提供了置信度递增速率、恢复根号T平稳性的目标间隙增长改进，以及随机Lipschitz示例，并区分了广泛的BG-0最优性与更小的均方光滑类。
🔑 关键词速览
| 随机梯度下降 (SGD) | 一种迭代优化算法，每次使用单个或小批量样本估计梯度进行参数更新。 |
| 距离依赖矩 (Distance-Dependent Moments) | 随机梯度噪声的矩（如方差）依赖于当前迭代点与初始点或最优点的距离。 |
| 平稳性 (Stationarity) | 在非凸优化中，指梯度范数趋于零的性质，常用作收敛度量。 |
| Blum--Gladyshev (BG-0) 下界 | 光滑非凸随机优化中，针对一类算法（如SGD）的极小极大下界，刻画了最优收敛速率。 |
| Fuk--Nagaev 不等式 | 一种用于鞅差序列的集中不等式，给出尾部概率的指数型上界，常用于高概率分析。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅