勾配降下法

勾配と逆向きに一定量進む、最も基本的な最適化。

$$x_{k+1}=x_k-\eta \nabla f(x_k)$$

$\eta$ が学習率（ステップサイズ）。

学習率がすべて#

$\eta$	起きること
小さすぎ	進まない。反復回数が膨大になる
適切	単調に減少して収束
大きすぎ	谷を飛び越えて振動、あるいは発散

$L$-平滑な凸関数では $\eta \le 1/L$ が収束の十分条件になる。 $L$ はヘッセ行列の最大固有値の上界。

ジグザグ問題#

等高線が細長い楕円のとき、勾配は谷の軸方向ではなく壁を向く。 結果として谷を横切る往復運動が起き、進みが極端に遅くなる。 収束速度は条件数 $\kappa$ に依存し、 $\kappa$ が大きいほど悪化する。

対処は 3 通り。慣性を持たせる、 二階の情報で座標系を直す、 問題側で正規化・前処理する。

直線探索#

$\eta$ を固定せず、各反復で適切な値を探す方法もある。 Armijo 条件（十分な減少）と Wolfe 条件（曲率）を満たす $\eta$ を 後退探索で見つけるのが標準で、準 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/