モメンタム — 知識ノート

過去の更新方向を慣性として引き継ぐ仕組み。Polyak が 1964 年に導入した。

v_{k + 1} = β v_{k} + \nabla f (x_{k}), x_{k + 1} = x_{k} - η v_{k + 1}

$β$ は慣性係数で 0.9 前後が標準。

ジグザグを消す#

勾配降下法のジグザグでは、谷を横切る成分が毎回符号を変えるのに対し、谷に沿って下る成分は符号が一定。

移動を足し合わせると、符号が変わる成分は打ち消し合い、一定の成分は積み上がる。結果として谷筋方向だけが加速される。

これはCMA-ES の進化パスとまったく同じ発想で、あちらも移動を累積することで「往復しているか、進み続けているか」を判別している。

先に慣性ぶん進んでから勾配を測る、という変更を加えたもの。

v_{k + 1} = β v_{k} + \nabla f (x_{k} - η β v_{k})

行き先を見てからブレーキをかけるので、行き過ぎが抑えられる。凸で $L$ -平滑な問題では収束率が $𝒪 (1 / k)$ から $𝒪 (1 / k^{2})$ へ改善し、一階の手法として最適であることが知られている。

Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics 4(5), 1964. https://doi.org/10.1016/0041-5553(64)90137-5
Yurii Nesterov. Lectures on Convex Optimization, 2nd ed. Springer, 2018. https://doi.org/10.1007/978-3-319-91578-4
Gabriel Goh. Why Momentum Really Works. Distill, 2017. https://distill.pub/2017/momentum/