勾配降下法の収束

μ強凸

ある関数 $f:{\mathbb{R}}^D\to \mathbb{R}$ が以下を満たすとき、$f$ はμ強凸であるという。

$$f(\mathbf{y})>f(\mathbf{x})+(\mathbf{y}-\mathbf{x}{)}^T\nabla f(\mathbf{x})+\frac{\mu }{2}||\mathbf{x}-\mathbf{y}|{|}_2^2$$

ここで、$\mu$は凸性の強さを表している。

L平滑

ある関数 $f:{\mathbb{R}}^D\to \mathbb{R}$ が以下を満たすとき、$f$ はL平滑であるという。

$$||\nabla f(\mathbf{x})-\nabla f(\mathbf{y})|{|}_2<L||\mathbf{x}-\mathbf{y}|{|}_2$$

勾配の変化が入力の変化の変化の定数倍で抑えられる性質を持つ。 近接した点の勾配は互いに近接している。

勾配降下法の収束

${\mathbf{w}}^{\ast }={\mathrm{argmin}}_{\mathbf{w}}E(\mathbf{w})$ とする。 また関数 $E$ は微分可能な凸関数とする。 関数 $E$ がL平滑で、ステップサイズが $\eta <\frac{1}{L}$ であるとき、以下が成立する。

$$E({\mathbf{w}}^{(t)})-E({\mathbf{w}}^{\ast })<\frac{2L||{\mathbf{w}}^{(0)}-{\mathbf{w}}^{\ast }|{|}_2^2}{t+4}$$

収束速度がステップ数$t$について$\mathrm{O}(\frac{1}{t})$となる。 また、誤差を$ϵ$以下にするためには、$\mathrm{O}(\frac{1}{ϵ})$回の更新が必要となる。

μ強凸な誤差関数に対する勾配降下法の収束

${\mathbf{w}}^{\ast }={\mathrm{argmin}}_{\mathbf{w}}E(\mathbf{w})$ とする。 また関数 $E$ は微分可能な凸関数とする。 関数 $E$ がμ強凸（$\mu >0$）かつL平滑（$L>0$）で、$\eta =\frac{1}{L}$ であるとき、以下が成立する。

$$E({\mathbf{w}}^{(t)})-E({\mathbf{w}}^{\ast })<(1-\frac{\mu }{L}{)}^t[E((w{)}^{(0)}-E({\mathbf{w}}^{\ast })]$$

収束速度はステップ数 $t$、収束係数 $c=1-\frac{\mu }{L}$ に対して、$\mathrm{O}(c^t)$。 誤差を $ϵ$ 以下にするには、$\mathrm{O}(\log (\frac{1}{ϵ}))$ 回の更新で良い。

つまり、μ強凸である方が収束が高速。 回帰やridge回帰は強凸かつL平滑で、ロジスティック回帰はL平滑だが強凸ではない。 また、LassoやSVMはL平滑ではない。

学習率

学習率は小さすぎると収束が遅くなり、大きすぎると収束は早いが最適解周辺で振動する。 また、非常に大きいと発散してしまう。

更新回数が増加するにつれて学習率を小さくしたり、更新量が減少するにつれて学習率を小さくさせるようなスケジューリングができる。 しかし、適切な学習率を理論的に決定することは困難で、問題ごとにチューニングしなければならない。