重球法破灭了!任意调参也无法达到Nesterov速率,最后迭代慢到黄金分割指数1.618倍对数惩罚!
A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions
arXiv ML (stat.ML) 重要 #优化#收敛率#凸优化 🕐 09-08 12:00

📖 摘要

证明重球法在光滑凸优化中无法达到Nesterov最优收敛率,给出下界。

🔑 关键词速览

Heavy-Ball method一种带有动量的梯度下降优化方法,通过引入动量项加速收敛。
Nesterov's $O(T^{-2})$ last-iterate rateNesterov 加速方法在光滑凸优化中达到的关于迭代次数 T 的 O(1/T^2) 收敛速率,指最后一步迭代的误差。
smooth convex objective具有 Lipschitz 连续梯度的凸函数,是优化理论中的标准函数类别。
horizon-dependent parameters依赖于总迭代次数 T 的参数设置,允许在知道迭代预算的情况下调整步长和动量。
last iterate优化算法在迭代结束后输出的最终点,其函数值与最优值的差距用于衡量收敛性能。
infoAI 公众号二维码

📱 每天一份 AI 前沿日报

关注公众号,每天 09:00 推送 · 不错过任何重磅