Soptq

収束率とは？#

私たちが小学 3 年生の時に学んだ数値解析によれば、もし関数 $f(x)$ が収束するならば、すなわち $\lim_{k \rightarrow\infty}\vert\vert x_k - x^* \vert\vert = 0$ であり、$\lim_{k \rightarrow\infty}f(x_k) = x^*$ であるならば、次のようになります：

$\lim_{k \rightarrow\infty} \frac{\vert\vert x_{k+1} - x^*\vert\vert}{\vert\vert x_k-x^*\vert\vert} = a$

ここで、 $a$ は $f(x)$ の収束率です。

基本理論#

SGD 基礎#

深層学習の問題において、私たちは一般的に次のような問題を解決しようとします：

$\min_{x}f(x) = \sum_{i=1}^{n}f_i(x)$

ここで、$f(x)$ はモデル、$i$ は各サンプル、$x$ は最適化するパラメータ、$n$ は全サンプルの数です。

そして、SGD を使用してモデルを更新する際は、一般的に次のように更新します：

$x_{t+1} = x_{t} - \mu \nabla f_i{x_t}$

これは皆さんも理解できると思いますが、これは勾配更新の公式です。

$L$- リプシッツと $\mu$- 強凸#

深層学習の分野では、10,000 本の最適化に関する論文を見て、9,900 本は証明の前に次の一文を加えます：

... $f$ は $L$- 滑らかで $\mu$- 強凸である...

すべてが非常に当然のことのように思えますが、ただ一つの疑問があります —— この 2 つの概念は一体何なのでしょうか？ まだ多くの人がこの 2 つの言葉を見るとこの部分を飛ばす条件反射を持っています（私のように）。恐れに直面する時が来ました！

$\mu$- 強凸#

まず、$\mu$- 強凸は関数 $f(x)$ が強凸であることを示し、数学的には次のように表現されます：

$f(x_2) \ge f(x_1) + \nabla f(x_1)^{T}(x_2 - x_1) + \frac{\mu}{2}\vert\vert x_2 - x_1 \vert\vert ^2$

ここで $x_1, x_2 \in Q$、$Q$ は $f(x)$ の定義域です。私たちは、凸関数の定義は次のようになります：

$f(x_2) \ge f(x_1) + \nabla f(x_1)^{T}(x_2 - x_1)$

この式の直感的な意味は、任意の $x_1$ に対して $f(x)$ の接線 $f^{'}(x_1)$ が存在し、$f(x) \le f^{'}(x_1)$ であることです。

強凸の数学的表現は、実際には凸の条件に二項式 $\frac{\mu}{2}\vert\vert x_2 - x_1 \vert\vert ^2$ が追加されているだけです。なぜなら、凸関数では、私たちは関数が接線の上にあることを制限していますが、どれだけ上にあるかは言及していません。つまり、関数は接線に無限に近づくことができ、そのような関数は最適化において実行不可能です。したがって、私たちは凸の「度」を下限で制限し、最適化を定量化可能にしています。

詳細な証明については、こちらの文章を参照してください。

$L$- リプシッツ#

$L$- リプシッツについては、非常に良い知乎のコラムがありますので、時間がある方はぜひご覧ください。時間がない方のために、私の理解を簡単に説明します。

リプシッツ連続とは、関数 $f(x)$ に対して、すべての $x_1, x_2 \in Q$（$Q$ は $f(x)$ の定義域）に対して次の条件を満たすことを指します：

$\vert\vert f(x_1) - f(x_2)\vert\vert \le L\vert\vert x_1-x_2 \vert\vert$

非常に直感的に、この式が表す意味は $\vert\vert f^{'}(x) \vert\vert \le L$ であり、したがって $f(x)$ の関数値はある範囲に制限されているということです。

リプシッツ連続の他にも、リプシッツ連続勾配やリプシッツ連続ヘッセ行列があります。リプシッツ連続勾配は関数 $f(x)$ の勾配 / 導関数に関するものです。言い換えれば、もし $f^{'}(x)$ がリプシッツ連続であれば、$f(x)$ はリプシッツ連続勾配を満たします。リプシッツ連続ヘッセ行列も同様で、$f^{''}(x)$ がリプシッツ連続であれば、$f(x)$ はリプシッツ連続ヘッセ行列を満たします。

私たちが深層学習でよく使うのはリプシッツ連続勾配 ($L$- 滑らか) です。したがって、私たちはその数学的表現を理解する必要があります：

$\vert f(x_2) - f(x_1) - \langle f^{'}(x_2), x_2-x_1 \rangle \le \frac{L}{2}\vert\vert x_2-x_1 \vert\vert ^2$

直感的には、これは私たちが $f(x)$ の変化の傾向に制限を加えたことを示しています。絶対値を開くと、この制限がより明確に現れます：

$\left\{\begin{array}{lr} f(x_2) \le f(x_1) + \langle f^{'}(x_2), x_2-x_1 \rangle + \frac{L}{2}\vert\vert x_2-x_1 \vert\vert ^2&\\f(x_2) \ge f(x_1) + \langle f^{'}(x_2), x_2-x_1 \rangle + \frac{L}{2}\vert\vert x_2-x_1 \vert\vert ^2&\end{array}\right.$

詳細な証明については、こちらの文章を参照してください。

SGD の収束率#

それでは、少し試してみて、SGD の収束率を計算してみましょう。

まず、$L$- 滑らかの条件を示します：

$f(x_{t}+\sigma) \le f(x_{t}) + \nabla f(x_{t})^{T}\sigma + \frac{L}{2}\vert\vert\sigma\vert\vert ^2$

ここで $\sigma = x_{t+1} - x_{t} = - \mu \nabla f_i{x_t}$ です。$\sigma$ を上式に代入すると：

$\begin{aligned}f(x_t + \sigma) &= f(x_t - \mu \nabla f_i{x_t}) \\ &= f(x_{t+1})\\&\le f(x_{t}) - \mu \nabla f(x_t)^{T} \nabla f_{i}(x_t) + \frac{\mu ^2 L}{2} \vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2\end{aligned}$

次に、上式の両辺に対して $i$ の期待値を取ります：

$\mathbb{E}_{i}(f(x_{t+1})) \le f(x_{t}) - \mu \nabla f(x_t)^{T} \mathbb{E}_{i}(\nabla f_{i}(x_t)) + \frac{\mu ^2 L}{2} \mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2$

ここで、4 つの期待値があります。最初の 2 つの期待値はそのままにしておき、3 つ目の期待値 $\mathbb{E}_{i}(\nabla f_{i}(x_t))$ は次のようになります：

$\begin{aligned}\mathbb{E}_{i}(\nabla f_{i}(x_t)) &= \frac{1}{n}\sum_{i=1}^{n}\nabla f_i(x_t) \\ &= \nabla f(x_i)\end{aligned}$

4 つ目の期待値 $\mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2$ は少し複雑で、分散を定義して求める必要があります。

私たちは勾配の分散 $Var = \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f_i(x_t) - \nabla f(x_t) \vert\vert ^2$ と仮定し、この分散を展開すると：

$\begin{aligned}Var &= \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f_i(x_t) - \nabla f(x_t) \vert\vert ^2 \\ &= \frac{1}{n}[\sum_{i=1}^{n}\vert\vert \nabla f_i(x_t)\vert\vert ^2] + \frac{1}{n}[\sum_{i=1}^{n}\vert\vert\nabla f(x_t)\vert\vert ^2] - \frac{2}{n}[\sum_{i=1}^n\langle\nabla f_i(x_t), \nabla f(x_t)\rangle] \\ &=\vert\vert \nabla f(x_t)\vert\vert ^2 + \frac{1}{n}[\sum_{i=1}^{n}\vert\vert\nabla f(x_t)\vert\vert ^2] - 2\vert\vert \nabla f(x_t)\vert\vert ^2 \\ &= \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f(x_t)\vert\vert ^2 - \vert\vert \nabla f(x_t)\vert\vert ^2\end{aligned}$

したがって、$\mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2$ は次のようになります：

$\mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2 = \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f_{i}(x_{t})\vert\vert ^2 = Var + \vert\vert \nabla f(x_t)\vert\vert ^2$

したがって、上で計算した 2 つの単項期待値を全体に代入すると：

$\begin{aligned}\mathbb{E}(f(x_{t+1})) &\le \mathbb{E}(f(x_{t})) - \mu \nabla f(x_t)^{T} \nabla f(x_i) + \frac{\mu ^2 L}{2}(Var + \vert\vert \nabla f(x_t)\vert\vert ^2)\\&=\mathbb{E}(f(x_t))-(\mu-\frac{\mu^2L}{2})\vert\vert \nabla f(x_t)\vert\vert ^2 + \frac{\mu^2L}{2}Var\end{aligned}$

次に、私たちは $\lambda$- 強凸（ここで $\lambda$ を使用しているのは、例の学習率と混同しないためです）の数学的表現は次のようになります：

$f(x) \ge f(x_0) + \nabla f(x_0)^T (x-x_0) + \frac{\lambda}{2}\vert\vert x - x_0 \vert\vert ^2$

私たちは $x = x^*, x_0 = x$ と置くと、加減を組み合わせて平方和にすると：

$\begin{aligned}f(x^*) &\ge f(x) + \nabla f(x)^T (x^*-x) + \frac{\lambda}{2}\vert\vert x^* - x \vert\vert ^2\\ &=f(x) + \frac{1}{2\lambda}\vert\vert\nabla f(x) + \lambda (x^*-x)\vert\vert ^2 - \frac{1}{2\lambda}\vert\vert\nabla f(x)\vert\vert ^2\\ &\ge f(x) - \frac{1}{2\lambda}\vert\vert\nabla f(x)\vert\vert ^2\end{aligned}$

したがって、次のようになります：

$\vert\vert\nabla f(x)\vert\vert ^2 \ge 2\lambda (f(x) - f(x^*))$

上式を期待値の不等式に代入すると：

$\mathbb{E}(f(x_{t+1})) \le \mathbb{E}(f(x_t))-2\lambda(\mu-\frac{\mu^2L}{2})(f(x_t) - f(x^*)) + \frac{\mu^2L}{2}Var$

最後に、$\mu = \frac{1}{L}$ とすると：

$\mathbb{E}[\frac{f(x_{t+1}) - f(x^*)}{f(x_{t}) - f(x^*)}] = (1-\frac{\sigma}{L}) + H$

ここで $H$ は SGD が GD に対してもたらす干渉です。