收敛率是什么？
我们小学三年级学的数值分析告诉我们，如果函数 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) 的变化趋势做了一个限制。我们把绝对值打开这个限制会体现德更清楚一点：
% <![CDATA[ \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 带入上式有：
% <![CDATA[ \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)) 有：
% <![CDATA[ \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 ，我们把这个方差展开有：
% <![CDATA[ \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
于是，我们吧上面算出的两个单项期望带入整体有：
% <![CDATA[ \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 有，把加减组合成一个和的平方有：
% <![CDATA[ \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 带来的干扰。
发现存在错别字 或者事实错误 ？请麻烦您点击
汇报。谢谢您！
