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 带来的干扰。