勾配に基づく最適化

目的関数の勾配を使って、下る方向へ進む手法群。 微分できるなら、これが最も効率的な選択になる。

なぜ速いのか#

勾配は「その点で最も急に増加する方向」を指す。 つまり $-\nabla f$ が最も急に減る方向。 $n$ 次元でも1 回の勾配計算で全方向の情報が得られるのが決定的で、 導関数を使わない手法が 方向を探るのに何度も評価するのと対照的。

系統#

使う情報	手法	収束の速さ
一階（勾配）	勾配降下法	線形
一階 + 慣性	モメンタム、Adam	線形（定数が改善）
二階（ヘッセ行列）	Newton 法	二次
二階の近似	準 Newton 法	超線形

落とし穴#

• 非凸なら局所解や鞍点で止まる
• 悪条件（条件数が大きい）だとジグザグして進まない
• 勾配が数値微分でしか得られないなら、次元数に比例して評価が増える

参考文献#

• Jorge Nocedal, Stephen J. Wright. Numerical Optimization, 2nd ed. Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5
• Ian Goodfellow, Yoshua Bengio, Aaron Courville. Deep Learning, Chapter 8. MIT Press, 2016. https://www.deeplearningbook.org/
• Sebastian Ruder. An overview of gradient descent optimization algorithms. 2016. https://arxiv.org/abs/1609.04747