勾配降下法

坂を下る

勾配降下法は、勾配と逆向きに進むという1つの動きを繰り返します：$\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$。$\eta>0$ はステップ幅で、学習率とも呼ばれます。$\eta$ が小さいと安全ですが遅く、大きいと谷を飛び越え、反復のたびに遠ざかることがあります。

最も単純なお椀型では、更新のたびに $w$ が $1-\eta a$ 倍されるので、$|1-\eta a|<1$ すなわち $\eta<2/a$ のときに限り反復はゼロへ縮みます。$\eta=1/a$ なら1ステップで最小値に着地し、$1/a$ と $2/a$ の間なら収束はしますが符号が交互に変わります。$2/a$ を超えると係数の絶対値が1を超え、反復は発散します。

多変数では曲率が方向ごとに違います。ヘッセ行列の最大固有値 $L$ が使えるステップ幅の上限（$\eta<2/L$）を決め、最小固有値 $\mu$ が最も平らな方向を渡る遅さを決めます。その比 $\kappa=L/\mu$ が条件数です。最良の固定ステップ $\eta=2/(L+\mu)$ では、誤差は1ステップごとにおよそ $(\kappa-1)/(\kappa+1)$ 倍になるので、$\kappa$ が大きいと係数は1に近く、細長い谷をゆっくりジグザグに下ることになります。2010年以降の米国大型株12銘柄の共分散行列では $\kappa$ は約 $33$ で、係数は $0.941$、誤差を100分の1にするのに約76ステップかかります。

• 安全なステップ：$\eta<2/L$（$L$ はヘッセ行列の最大固有値）。超えると発散します。
• 速さ：条件数 $\kappa=L/\mu$ で決まり、大きいほど遅くなります。
• 停止条件：$\lVert\nabla f\rVert$ が許容値を下回ったら止め、反復回数に上限も設けます。

ラボ：採点される内容

• 最初のステップ15点
• 2番目のステップ10点
• 安定な最大ステップ幅15点
• 大きすぎるステップ15点
• 条件数15点
• 最良の縮小係数15点
• 悪条件がなぜ遅いのか15点