勾配降下法の収束性
abstract 凸関数のうち勾配がある程度良い振る舞いをするような関数の場合に、十分に小さな学習率を用いれば勾配降下法が最適解に収束することを証明します。また証明に必要な知識を補足説明します。
Remark 記事が長い関係で目次が折りたたまれています。目次全体を確認したい方は「すべて表示」をクリックしてください。
1 Introduction
勾配降下法（gradient descent）は、微分可能な関数 $${f(x)}$$ に対して最小値を与える解、いわゆる最適解 $${x^*}$$ を探索するために用いられるアルゴリズムです。初期値 $${x^{(0)}}$$ と正の実数 $${\eta>0}$$ を決めたら、以下の式に基づいて解を更新します。
$$
\begin{align*}
x^{(k+1)} &= x^{(k)} - \eta\nabla f(x^{(k)})
\end{align*}
$$
$${\eta}$$ は学習率（learning rate）とよばれています。
負の勾配 $${-\nabla f(x^{(k)})}$$ は直感的に解釈することができ、$${x=x^{(k)}}$$ の地点で関数 $${f(x)}$$ の値が最も減少する方向を表すことが知られています。従って勾配降下法は、関数が最も減少する方向に、大きな関数の値の変化が見込めるほど大きく解を更新していくようなイメージのアルゴリズムです。
しかし、勾配降下法で本当に最適解を得ることはできるのでしょうか。これはグラフが比較的簡単な形をしている凸関数の場合でさえ、簡単な問題ではありません。実際、
・更新後の関数の値がむしろ大きくなってしまう: $${f(x^{(k+1)})\geq f(x^{(k)})}$$
・収束した結果が最適解でない: $${\displaystyle\lim_{k\rightarrow\infty}x^{(k)}\neq x^{*}}$$
ようなことが起こらないのか、定義から直ちにはわからないでしょう。
そこでこのnoteでは、凸関数のなかでも勾配にある程度良い性質を仮定した関数 $${f(x)}$$ に対して、十分に小さな学習率 $${\eta}$$ を設定した勾配降下法は、このような問題を起こさないことを示します。つまり勾配降下法では、更新するごとに関数の値が減少し、特に解 $${x^{(k)}}$$ は最適解 $${x^{*}}$$ に収束します。
Remark 勾配降下法のイメージは講義[U]で解説しているので、もし興味がある方はご覧ください。■
2 最適化する関数に課す条件
一般の関数に対して勾配降下法の収束性を議論することは難しいため、ある程度良い振る舞いをするような関数に絞って考えてみましょう。今回は、関数 $${f(x)}$$ が二回微分可能な凸関数、さらに勾配 $${\nabla f}$$ が$${L}$$-Lipschitzな関数であることを仮定します。ここで、$${L}$$-Lipschitzについては以下に補足説明を与えます。
2.1 勾配のLipschitz性
勾配 $${\nabla f}$$ が$${L}$$-Lipschitzであるとは、どんな二点 $${x,y}$$ をとっても以下の不等式が成り立つように、正の定数 $${L}$$ が取れることです。
$$
\begin{align*}
\|\nabla f(x)-\nabla f(y)\|_{2} \leq L\|x-y\|_{2}
\end{align*}
$$
ただし、$${L}$$ は $${x,y}$$ に依存しないように取ります。つまり勾配の$${L}$$-Lipschitz性は、関数 $${f(x)}$$ の傾き $${\nabla f}$$ が急激に変化したりしないことを保証しています。
勾配降下法の解の更新 $${\displaystyle x^{(k+1)}=x^{(k)}-\eta\nabla f(x^{(k)})}$$ には、勾配 $${\nabla f(x^{(k)})}$$ の大きさが関わっています。つまり、傾きが急に大きくなるような点が存在すると、勾配降下法の解 $${x^{(k)}}$$ が最適解から大きく離れたところへ更新され、更新後の関数の値が更新前より大きくなってしまったりする可能性があるのです。勾配の$${L}$$-Lipschitz性は、このような難しい場合を考察対象から除くための条件になっていることがわかります。
Remark 定数 $${L}$$ のことをLipschitz定数（Lipschitz constant）といいます。また、勾配 $${\nabla f}$$ が$${L}$$-Lipschitzであるような関数を $${L}$$-平滑関数（$${L}$$-smooth function）ということがあります。■
2.2 例
一変数の場合で二回微分可能な凸関数で、特に勾配のLipschitz性を持つ例を挙げます。
最も基本的な例は二次関数 $${f_{1}(x)=ax^2+bx+c}$$, $${a>0}$$ です。二次関数は二回微分可能で、二階導関数が $${f''_{1}(x)=2a>0}$$ なので凸関数です。特に一階導関数は $${f'_{1}(x)=2ax+b}$$ なので、以下に示すように勾配が $${2a}$$-Lipschitzな関数になっています。
$$
\begin{align*}
|f'_{1}(x)-f'_{1}(y)| = 2a|x-y|
\end{align*}
$$
もう一つの例は $${f_{2}(x)=x^2-\cos x}$$ です。二回微分可能で、二階導関数は $${f''_{1}(x)=2+\cos x>0}$$ なので凸関数です。特に一階導関数は $${f'_{1}(x)=2x+\sin x}$$ なので、以下に示すように勾配が $${3}$$-Lipschitzな関数になっています。
$$
\begin{align*}
|f'_{2}(x)-f'_{2}(y)| &\leq 2|x-y| + |\sin x-\sin y|\\
&= 2|x-y| + 2\left|\cos\frac{x+y}{2}\sin\frac{x-y}{2}\right|\\
&\leq 2|x-y| + |x-y|\\
&= 3|x-y|
\end{align*}
$$
反例も挙げておきます。四次関数 $${f_{3}(x)=x^4}$$ や指数関数 $${f_{4}(x)=\exp x}$$ は二回微分可能かつ凸関数ですが、勾配がLipschitz連続ではありません。この反例からも勾配の$${L}$$-Lipschitz性が関数 $${f(x)}$$ の傾き $${f'(x)}$$ が急激に変化したりしないことを意味していることがわかります。
2.3 勾配のLipschitz性とHesse行列
また、関数 $${f(x)}$$ の二階導関数（Hesse行列）$${\nabla^2f}$$ について以下の事実が成り立ちます。証明はAppendixに掲げます。
定理 $${\nabla^2f \leq LI}$$、すなわち $${LI-\nabla^2 f}$$ は半正定値行列です。
この定理は、半正定値行列の定義から、どんな点 $${x}$$ における関数のHesse行列に対しても以下の不等式が成り立つことだと言い換えることができます。
$$
\begin{align*}
v^T\nabla^2f(x)v \leq L\|v\|_{2}^2
\end{align*}
$$
2.4 勾配のLipschitz性から来る不等式
勾配 $${\nabla f}$$ に$${L}$$-Lipschitz性が満たされると、以下の不等式が成り立ちます。この不等式は、第3節で紹介する定理を証明するときに、技術的な意味で大切な役割を果たします。
定理 どんな二点 $${x,y}$$ に対しても、以下の不等式が成り立ちます。
$$
\begin{align*}
f(y)&\leq f(x) + \nabla f(x)^T(y-x) + \frac{1}{2}L\|y-x\|_{2}^2\\
\end{align*}
$$
証明 Taylorの定理から、以下の等式が成り立つような $${a}$$ の値を見つけることができます。
$$
\begin{align*}
f(y) &= f(x) + \nabla f(x)^T(y-x) + \frac{1}{2}(y-x)^T\nabla^2f(a)(y-x)
\end{align*}
$$
この右辺の第三項に2.2節で紹介した定理 $${v^T\nabla^2f(a)v \leq L\|v\|_{2}^2}$$ を適用すると、
$$
\begin{align*}
f(y)&\leq f(x) + \nabla f(x)^T(y-x) + \frac{1}{2}L\|y-x\|_{2}^2\\
\end{align*}
$$
となり、示したかった不等式が得られます。■
Remark Hesse行列の性質を用いない代わりに、微分積分学の基本定理とCauchy-Schwarzの不等式を用いて直接示すこともできます。ここでは省略します。■
3 勾配降下法の収束性
以下に掲げるように勾配降下法は、ある程度良い振る舞いをするような関数の場合には、十分に小さな学習率を用いることで最適解に収束します。
定理 関数 $${f(x)}$$ が二回微分可能かつ勾配が $${L}$$-Lipschitzだとします。学習率を $${\displaystyle\eta\leq\frac{1}{L}}$$ を満たす正の実数に設定したときとき、以下の二つのことが成立します。
(1) $${\displaystyle f(x^{(k+1)})\leq f(x^{(k)})-\frac{1}{2}\eta||\nabla f(x^{(k)})||_{2}^2}$$
(2) 特に関数 $${f(x)}$$ が凸関数ならば、以下の不等式が成り立ちます。
$$
\begin{align*}
\displaystyle f(x^{(k)})-f(x^{*})\leq \frac{\|x^{(0)}-x^{*}\|_{2}^2}{2\eta k}
\end{align*}
$$
(1)は勾配降下法で解を更新するごとに関数の値が小さくなることを保証しています。(2)では、$${x^*}$$ は最適解なので左辺は必ず0以上です。従って、右辺に対して $${k\rightarrow\infty}$$ とすれば勾配降下法の解が最適解に収束することを示しています。
4 証明
(1)の証明
2.4節の定理を用いることで、以下の不等式が得られます。
$$
\begin{align*}
f(x^{(k+1)})&\leq f(x^{(k)}) + \nabla f(x^{(k)})^T(x^{(k+1)}-x^{(k)}) + \frac{1}{2}L\|x^{(k+1)}-x^{(k)}\|_{2}^2\\
\end{align*}
$$
あとは、右辺に勾配降下法の更新式 $${\displaystyle x^{(k+1)}=x^{(k)}-\eta\nabla f(x^{(k)})}$$ と学習率の設定から従う $${\displaystyle L\leq\frac{1}{\eta}}$$ を代入すれば、(1)が証明できます。
$$
\begin{align*}
f(x^{(k+1)}) &\leq f(x^{(k)}) - \eta\|\nabla f(x^{(k)})\|_2^2 + \frac{1}{2}L\eta^2\|\nabla f(x^{(k)})\|_2^2\\
&\leq f(x^{(k)}) - \frac{1}{2}\eta\|\nabla f(x^{(k)})\|_2^2
\end{align*}
$$
(2)の証明
以下の補題を示せば十分であることから確認します。
補題 $${\displaystyle f(x^{(i)})-f(x^{*})\leq\frac{1}{2\eta}\left(\|x^{(i-1)}-x^{*}\|_2^2-\|x^{(i)}-x^{*}\|_2^2\right)}$$
(1)の結果から $${f(x^{(1)}),\cdots,f(x^{(k)})}$$ の値は単調減少することがわかり、特に $${i=1,\cdots,k}$$ に対して $${f(x^{(k)})-f(x^*)\leq f(x^{(i)})-f(x^*)}$$ が成り立ちます。このことから
$$
\begin{align*}
f(x^{(k)})-f(x^*) &\leq \frac{1}{k}\sum_{i=1}^{k}\left(f(x^{(i)})-f(x^*)\right)
\end{align*}
$$
が従うので、補題が成り立つなら
$$
\begin{align*}
f(x^{(k)})-f(x^*) &\leq \frac{1}{k}\sum_{i=1}^{k}\left(f(x^{(i)})-f(x^*)\right)\\
&\leq \frac{1}{2\eta k}\left(\|x^{(0)}-x^{*}\|_2^2-\|x^{(k)}-x^{*}\|_2^2\right)\\
&\leq\frac{\|x^{(0)}-x^{*}\|_2^2}{2\eta k}
\end{align*}
$$
が従います。
補題の証明 (1)で得られた不等式を思い出します。
$$
\begin{align*}
f(x^{(i)}) \leq f(x^{(i-1)}) - \frac{1}{2}\eta\|\nabla f(x^{(i-1)})\|_2^2\\
\end{align*}
$$
両辺から $${f(x^{*})}$$ を引いた後、追加で課した関数 $${f(x)}$$ の凸性の定義を用いて式変形します。
$$
\begin{align*}
f(x^{(i)}) - f(x^{*}) &\leq f(x^{(i-1)}) - f(x^{*}) - \frac{1}{2}\eta\|\nabla f(x^{(i-1)})\|_2^2\\
&\leq \nabla f(x^{(i-1)})^T(x^{(i-1)}-x^*) - \frac{1}{2}\eta\|\nabla f(x^{(i-1)})\|_2^2
\end{align*}
$$
あとは右辺を平方完成すれば、所望の不等式を得ます。
$$
\begin{align*}
f(x^{(i)}) - f(x^{*}) &\leq \nabla f(x^{(i-1)})^T(x^{(i-1)}-x^*) - \frac{1}{2}\eta\|\nabla f(x^{(i-1)})\|_2^2\\
&= \frac{1}{2\eta}\left(\|x^{(i-1)}-x^{*}\|_2^2-\|x^{(i-1)}-x^{*}-\eta\nabla f(x^{(i-1)})\|_2^2\right)\\
&= \frac{1}{2\eta}\left(\|x^{(i-1)}-x^{*}\|_2^2-\|x^{(i)}-x^{*}\|_2^2\right)\\
\end{align*}
$$
ここで3式めには勾配降下法の更新式 $${\displaystyle x^{(i)}=x^{(i-1)}-\nabla f(x^{(i-1)})}$$ を用いました。■
Appendix 2.3節の定理の証明
2.3節で紹介した以下の定理を証明します。
定理 $${\nabla^2f \leq LI}$$、すなわち $${LI-\nabla^2 f}$$ は半正定値行列です。
これは以下の補題を示せば十分です。
補題 関数 $${\displaystyle g(x)=\frac{1}{2}Lx^Tx-f(x)}$$ は凸関数です。
実際、関数 $${g(x)}$$ が凸関数であれば、Hesse行列 $${\nabla^2 g(x)=LI - \nabla f(x)}$$ は半正定値だとわかるので、定理が成り立つことがわかります。
補題の証明 関数 $${g(x)}$$ が凸関数であることを確認するには、どんな二点 $${x,y}$$ に対しても以下の不等式が成り立つことを示せば良いです。
$$
\begin{align*}
(\nabla g(x)-\nabla g(y))^T(x-y) &\geq 0
\end{align*}
$$
勾配の$${L}$$-Lipschitz性を表す不等式の両辺に $${\|x-y\|}$$ をかけた後で、左辺にCauchy-Schwarzの不等式を使うと、以下のような式を得ます。
$$
\begin{align*}
\left(\nabla f(x)-\nabla f(y)\right)^T(x-y) \leq \|\nabla f(x)-\nabla f(y)\|_2\|x-y\|_2 \leq L\|x-y\|_2^2
\end{align*}
$$
第一項を第三項に移項すると、$${\|x-y\|_2^2=(x-y)^T(x-y)}$$ に注意すれば以下のような不等式が得られます。
$$
\begin{align*}
\left\{(Lx - \nabla f(x))-(Ly-\nabla f(y))\right\}^T(x-y) &\geq 0
\end{align*}
$$
関数 $${g(x)}$$ の勾配は $${\nabla g(x)=Lx-\nabla f(x)}$$ なので、これは示したい不等式そのものだとわかります。■
Acknowledgement
日頃からサポートしていただいている方々、株式会社すうがくぶんかの皆さんに感謝申し上げます。また匿名の方からAppendixの証明の誤りをご指摘いただきました。大変ありがとうございます。
References
[U] Uchiba, Takayuki. "統計・機械学習のための線形代数と微分積分." すうがくぶんか, 2023.
サポートをいただいた場合、新たに記事を書く際に勉強する書籍や筆記用具などを買うお金に使おうと思いますm(_ _)m