勾配降下法が極小点にたどり着く話

導入

勾配降下法とは、関数の極小値を見つけるための数理最適化手法の一つである。この方法は、特に機械学習や深層学習の分野で、モデルのパラメータを調整する際によく使われる。

しかし，連続最適化によって，初期値によっては鞍点に収束する可能性があると懸念する人もいる。この記事では、殆どの場合で勾配降下法は極小点に到達することを紹介する。つまり、ほとんど至る初期値に対して、勾配降下法が関数の極値付近に到達したとき、その極値が極小値になることについて解説する。

このテキストでは簡単のため，関数$f \in C^2 (\mathbb{R}^d )$とし，その勾配を$\nabla f$，ヘッシアンを$\nabla^2 f$とする．

準備

極値とその種類

• 点$x^* \in \mathbb{R}^d$が$f$の臨界点であるとは，$\nabla f (x^*) =0$となることである．
• 臨界点$x^* \in \mathbb{R}^d$が極小点であるとは，$x^*$の近傍$U$が存在して，任意の$x \in U$に対して，$f(x^*) \leq f(x)$となることである．
• 臨界点$x^* \in \mathbb{R}^d$が鞍点であるとは，$x^*$の任意の近傍$U$に対して，ある$x, y \in U$が存在して，$f(y) \leq f(x^*) \leq f(x)$となることである．

極小点とは，その点の近傍において$f$が最小値をとる点である．例として，$f(x_1, x_2) := x_1^2 + x_2^2$ の極小点は $x^* = (0, 0)$ である．この点 $x^*$ におけるヘッシアン行列は次のようになる．

$$\begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix}$$

これに対して，鞍点とはその点の近傍において関数の形状が馬の鞍のようになっている点を指す．例として，$f(x_1, x_2) := x_1^2 - x_2^2$の鞍点は $x^* = (0, 0)$である．この点 $x^*$におけるヘッシアン行列は次のようになる．

$$\begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \end{pmatrix}$$

このように，ヘッシアン行列は臨界点が極小点であるか鞍点であるかを判定する際に重要である．これを一般化すると以下の命題が成り立つ．

命題 1.
臨界点$x^*$とする．このとき，$\nabla^2 f(x^*)$の固有値が全て正ならば，極小点になる．また，$\nabla^2 f(x^*)$の固有値の中で，正と負の固有値があるならば，鞍点である．

勾配降下法

次に，勾配降下法について復習する．初期点$x_0 \in \mathbb{R}^d$とし，学習率$\eta >0$, 反復回数$T \in \mathbb{Z}_{\geq 0}$とする．このとき，勾配降下法とは以下のアルゴリズムである．

1. for $t _ 0 , \ldots , T-1$
2.   $x_{t+1} \leftarrow g(x_t) := x_t - \eta \nabla f(x_t)$
3. end while
4. return $x_T$

勾配降下法は，関数$f$の値を反復的に減少させることを目的とする．

主定理

勾配降下法によって値が変わらない，つまり，$g(x^*)=x^*$となる必要十分条件は，極値になること，つまり，$\nabla f (x^*) = 0$である．このことこから，勾配降下法はによって，次のいずれかが起きる：(1)$ | x_t | \to \infty$となるか，(2)$x_t$がある極値$x^*$に収束する．

勾配降下法で，(2)が起きる場合について取り上げる．実は鞍点に収束することが稀であることが，以下の定理からわかる．

定理 2 ([LSJR2016, 定理4, 系9])
関数$f \in C^2 (\mathbb{R}^d)$とし，$L:= \sup_{x\in\mathbb{R}^d} \| \nabla f (x) \|$を$f$のリプシッツ定数点とする．集合$C$を$f$の鞍点集合とする．任意の鞍点$x^* \in C$に対し，$\nabla f(x^*)$は負の固有値を持つとする．学習率を$0 < \eta < 1/L$とする．
このとき，ほとんど至る初期点$x_0 \in \mathbb{R}^d$に対して，勾配降下法で鞍点に収束する，すなわち，以下の集合は測度$0$である：

$$\left\{ x_0 \in \mathbb{R}^d \middle| \lim_{t \to \infty} g^t (x_0) \in C \right\}.$$

この定理は，ほとんど至る初期点$x_0\in \mathbb{R}^d$に対して，勾配降下法によって，いずれの状況を引き起こすことを意味する：すなわち，(1) $\|x_t\| \to \infty$ となるか，(2)$x_t$がある最小点$x^*$に収束する．鞍点に収束する可能性はほとんど生じないことを主張している．

参考文献

[LSJR2016] Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht, Gradient Descent Only Converges to Minimizers, 29th Annual Conference on Learning Theory, PMLR 49:1246-1257, 2016.