Soptq

收斂率是什麼？#

我們小學三年級學的數值分析告訴我們，如果函數 $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$-Lipschitz 和 $\mu$-Strongly Convex#

在深度學習領域，我們看 10,000 篇跟優化沾邊的論文，9,900 篇都要在證明前加一句：

... Let $f$ be $L$-smooth and $\mu$-strongly convex …

一切都是那麼的理所當然，就只有一個問題 —— ** 這兩個東西到底是什麼呢？** 還有很多辣雞養成了看到這兩個詞就跳過這段文字的條件反射（比如我）。是時候來直面恐懼了！

$\mu$-Strongly Convex#

首先，$\mu$-Strongly Convex 表示的是函數 $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$-Lipschitz#

對於 $L$-Lipschitz，有一篇知乎專欄我覺得講的很好，大家有時間可以去看一下。沒有時間的話我在下面也會把我的理解大概說一下。

Lipschitz Continus 是說，如果對於函數 $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)$ 的函數取值是被限定到一個範圍內的。

除了 Lipschitz Continus 以外，還有 Lipschitz Continus Gradient 和 Lipschitz Continus Hessian。 Lipschitz Continus Gradient 是對於函數 $f(x)$ 的梯度 / 導數來說的。換句話說，如果 $f^{'}(x)$ 滿足 Lipschitz Continus，則 $f(x)$ 滿足 Lipschitz Continus Gradient。 Lipschitz Continus Hessian 同理，若 $f^{''}(x)$ 滿足 Lipschitz Continus，則 $f(x)$ 滿足 Lipschitz Continus Hessian。

我們在深度學習中常用的是 Lipschitz Continus Gradient ($L$-Smooth)。所以我們主要要理解它的數學表達：

$\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$-Smooth 的條件先擺出來：

$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$

可以看到我們有四個期望，第一个和第二个期望我們暫時不動，第三個期望 $\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}$

第四項期望 $\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$

於是，我們把上面算出的兩個單項期望帶入整體有：

$\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$-Strong Convex （這裡用 $\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 帶來的干擾。