0x00 Preface

本文着眼于深度学习中的收敛性分析，作为第一部分，首先介绍了深度学习中的优化问题的基本概念以及常见不等式的推导。

笔者并非优化科班出身，因为研究需要所以对这部分内容进行了学习，如本文内容和公式推导有误恳请指出。

在此想总结下自己的学习到的知识，由于完整篇幅过长可能不适合阅读，因此分成了几个部分进行撰写，希望能帮到在阅读的你。

0x01 Fundamental Concepts

Optimization Problem

优化问题是指在一定的约束条件下，求解目标函数的最大值或最小值的问题。优化问题的一般形式如下：

$$ \begin{aligned} \min_{x} \quad & f(x) \\ \text { s.t. } \quad & g_{i}(x) \leq 0, \quad i=1,2, \ldots, m \\ & h_{j}(x)=0, \quad j=1,2, \ldots, p \end{aligned} $$

而在深度学习中，$f(x)$ 一般为损失函数，并且是无约束的，所以本文也将不涉及有约束的优化问题，包括拉格朗日乘子法等方法。

Convex Function

凸函数是指函数的定义域为凸集，且函数的任意两点连线上的函数值都小于等于这两点的函数值之和。凸函数的定义如下：

defination

考虑实值函数 $f: R^d \to R$，如果对任意自变量 $x,y\in R^d$，都有下面不等式成立：

$$ f(y) \geq f(x)+\nabla f(x)^{\top}(y-x) $$

则称函数 $f$ 是凸的。

因此由这个公式，可以推导出凸函数的另一种形式：

$$ f(\lambda x+(1-\lambda) y) \leq \lambda f(x)+(1-\lambda) f(y), \forall \lambda \in[0,1] $$

$\mu$-strongly convex

通常我们会遇到凸函数，但是在实际中，我们更希望函数更加凸，即函数的曲率更大，这样可以加快函数的收敛速度。因此我们引入了 $\mu$-强凸的概念，$\mu$-强凸的定义如下：

defination

考虑实值函数 $f: R^{d}\to R$，和模 $||\cdot||$，如果对任意自变量 $x,y\in R^d$，都有下面不等式成立：

$$ f(y) \geq f(x)+\nabla f(x)^{\top}(y-x)+\frac{\mu}{2}||y-x||^2, \quad \forall x, y \in \mathcal{D} $$

则称函数 $f$ 关于模 $||\cdot||$ 是 $\mu$-强凸的。

可以看到，$\mu$-强凸的定义是在凸函数的基础上，加上了一个模，这个模的系数为 $\mu$，也就是让 $\mu$-强凸的函数的曲率更大。

如果令 $y = x^*$，则 $\nabla f(y) = \nabla f(x^*) = 0$，则有：

$$ \langle \nabla f(x), x-x^{*}\rangle \geq \frac{\mu}{2}||x-x^{*}||^2 $$

同时，也不难验证，函数 $f$ 是 $\mu$-强凸的当且仅当 $f-\frac{\mu}{2}||\cdot||^2$ 是凸的。

Lipschitz continuous

$L$-Lipschitz 连续，要求函数图像的曲线上任意两点连线的斜率一致有界，就是任意的斜率都小于同一个常数，这个常数就是 Lipschitz 常数。

defination

考虑实值函数 $f: R^{d}\to R$，和模 $||\cdot||$，如果存在常数 $L>0$，对任意自变量 $x,y\in R^d$，都有下面不等式成立：

$$ |f(x)-f(y)| \leq L||x-y|| $$

则称函数 $f$ 关于模 $||\cdot||$ 是 $L$-Lipschitz 连续的。

Smoothness

对于可导函数，光滑性质依赖于函数的导数，定义如下：

defination

考虑实值函数 $f: R^{d}\to R$，和模 $||\cdot||$，如果存在常数 $L>0$，对任意自变量 $x,y\in R^d$，都有下面不等式成立：

$$ f(x)-f(y) \leq \nabla f(y)^{\top}(x-y)+\frac{L}{2}||x-y||^2 \tag{1} \label{1} $$

则称函数 $f$ 关于模 $||\cdot||$ 是 $L$-光滑的。

另一种形式是：

$$ |\nabla f(x)-\nabla f(y)| \leq L||x-y|| \tag{2} \label{2} $$

即，凸函数$f$是$L$-光滑的充分必要条件是其导数$\nabla f$是$L$-Lipschitz 连续的。

把 $\eqref{1}$ 和 $\eqref{2}$ 结合起来，可以看出，$L$-Lipschitz 其实是给出了函数的一个上界，而 $\mu$-强凸则给出了函数的一个下界 1。

首先证明一下 $\eqref{1}$ 和 $\eqref{2}$ 的等价性，这里笔者参考了2的证明过程。

Proof:

$$ \begin{align} f(y) &= f(x) + \int_{0}^{1} \nabla f(x + \tau(y - x))^{\top}(y - x) \mathrm{d}\tau \\ &= f(x) + \int_{0}^{1} \nabla f(x)^{\top}(y - x) \mathrm{d}\tau + \int_{0}^{1} (\nabla f(x + \tau(y - x)) - \nabla f(x))^{\top}(y - x) \mathrm{d}\tau \\ \end{align} $$

因此有

$$ \begin{align} |f(y) - f(x) - \nabla f(x)^{\top}(y - x)| &= \left|\int_{0}^{1} (\nabla f(x + \tau(y - x)) - \nabla f(x))^{\top}(y - x) \mathrm{d}\tau\right| \\ &\leq \int_{0}^{1} \|\nabla f(x + \tau(y - x)) - \nabla f(x)\|\|y - x\| \mathrm{d}\tau \tag{3.1} \label{3.1} \\ &\leq \int_{0}^{1} \tau L\|y - x\|^{2} \mathrm{d}\tau \tag{3.2} \label{3.2} \\ &= \frac{L}{2}\|y - x\|^{2} \end{align} $$

证毕。

$\eqref{3.1}$ 处使用了 Cauchy-Schwarz 不等式，$\eqref{3.2}$ 处使用了 $\eqref{1}$ 处 $L$-Lipschitz 连续的定义。也可以看出有了 $|\nabla f(x) - \nabla f(y)| \leq L||x - y||$，我们可以建立起自变量和梯度的关系。

0x02 Optimization Methods

Gradient Descent

梯度下降公式为：

$$ w_{t+1}=w_{t}-\eta_{t} \nabla f(w_{t}) $$

其中，$\eta_t$ 为学习率，$w_t$ 为参数，$f(w_t)$ 为目标函数，且 $\eta_t \leq \eta_{t-1} \leq \cdots \leq \eta_1$ 为递减序列。

有下面任何情况下都成立的等式3：

$$ \begin{align} \| w_{t+1} - w^* \|^2 &= \| w_{t} - \eta_t \nabla f(w_t) - w^* \|^2 \\ &= \| w_{t} - w^* \|^2 - 2\eta_t \langle \nabla f(w_t), w_t - w^* \rangle + \eta_t^2 \| \nabla f(w_t) \|^2 \\ \end{align} $$

Stochastic Gradient Descent

由于梯度下降在数据量大的时候，计算复杂度也相对较大，因此有了随机梯度下降，每次只用一个 sample $(\mathbf{x_i}, y_i)$的梯度来估计总体梯度，随机梯度下降公式为：

$$ w_{t+1}=w_{t}-\eta_{t} \nabla f(w_{t}; \xi_{t}) $$

随机梯度经常用 $g(w_t)=\nabla f(w_t; \xi_t)$ 来表示。

Mini-batch Stochastic Gradient Descent

Mini-batch Stochastic Gradient Descent 是随机梯度下降的一种改进，每次使用 $b$ 个样本来估计总体梯度，即，$g(w_t)=\frac{1}{b}\sum_{i=1}^b \nabla f(w_t; \xi_{t,i})$。Mini-batch Stochastic Gradient Descent 公式为：

$$ w_{t+1}=w_{t}-\frac{\eta_{t}}{b} \sum_{i=1}^{b} \nabla f(w_{t}; \xi_{t,i}) $$

0x03 Common Assumptions

深度学习的相关优化方法的分析中，都会给出下述几个假设条件

Variance Bounded Assumption

变量有界假设，设模型参数为 $w$，则有下式：

$$ \|w_1 - w_2\|^2 \leq D, \quad \forall w_1, w_2 $$

Gradient Bounded Assumption

梯度有界假设，设梯度为 $\nabla f(w)$，则有下式：

$$ ||\nabla f(w)||^2 \leq G^2 $$

Unbiased Estimate

mini-batch SGD 的梯度估计是无偏的，即：

$$ \mathbb{E}_{\xi} [g(w; \xi)] = \nabla f(w) $$

Gradient Bounded Variance Assumption

梯度方差有界假设，设一次 mini-batch sample 出来的梯度为 $\nabla f(w; \xi)$，则有下式：

$$ \mathrm {Var}(\nabla f(w; \xi)) \leq \sigma^2 $$

tip

由以上两个假设（无偏估计和梯度方差有界），我们有：

$$ \mathrm{Var}(g(w; \xi)) = \mathbb{E}_{\xi}[||g(w; \xi)||^2]- ||\mathbb{E}_{\xi}[g(w; \xi)]||^{2} \leq \frac{\sigma^2}{b} $$

即，

$$ \mathbb{E}_{\xi}[||g(w; \xi)||^2] \leq ||\nabla f(w)||^{2} + \frac{\sigma^2}{b} $$

0x04 Common Inequalities

笔者这里只写几个在收敛性分析中非常常见的不等式（甚至有些论文中不会提到这两个不等式直接进行使用，这也是笔者最初阅读时产生困惑的重要原因）。

Cauchy-Schwarz Inequality

$$ \langle x, y\rangle \leq\|x\|\|y\|, \quad \forall x, y \in \mathbb{R}^{n} $$

Jensen Inequality

$$ f\left(\sum_{i=1}^{n} \eta_{i} x_{i}\right) \leq \sum_{i=1}^{n} \eta_{i} f\left(x_{i}\right), \quad \forall x_{i} \in \mathbb{R}, \eta_{i} \geq 0, \sum_{i=1}^{n} \eta_{i}=1 $$

而常见形式则是各个 $\eta_i$ 相等，即：

$$ f\left(\frac{1}{n} \sum_{i=1}^{n} x_{i}\right) \leq \frac{1}{n} \sum_{i=1}^{n} f\left(x_{i}\right) $$

等价于

$$ f\left(n \bar{x}\right) \leq n f\left(\bar{x}\right) $$

Triangle Inequality

$$ \|x+y\| \leq\|x\|+\|y\| $$

Polyak-Lojasiewicz (PL) Inequality

defination

如果一个函数是 $\mu$-强凸的，那么对任意 $x\in R^{d}$它的下界可以写成：

$$ 2\mu(f(x)-f(x^*)) \leq ||\nabla f(x)||_2^2 $$

Proof:

这个公式的证明，是从 $\mu$-强凸的定义出发，来最小化不等式左右两边。

$$ f(x_1) \geq f(x_2) + \nabla f(x_2)^{\top}(x_1 - x_2) + \frac{\mu}{2}||x_1 - x_2||^2 $$

令左边为最小值，即设置 $x_1 = x^*$ 即可。令右边最小值，则对 $x_1$ 求导，令导数为 0。

$$ \begin{align} \nabla_{x_1} [f(x_2) + \nabla f(x_2)^{\top}(x_1 - x_2) + \frac{\mu}{2}||x_1 - x_2||^2] &= \nabla f(x_2) + \mu(x_1 - x_2) \\ &= 0 \\ \end{align} $$

即，$x_1 = x_2 - \frac{1}{\mu}\nabla f(x_2)$，代入原式：

$$ f(x^*) \geq f(x_2) - \frac{1}{\mu}||\nabla f(x_2)||^2 + \frac{\mu}{2}||-\frac{1}{\mu}\nabla f(x_2)||^2 $$

移项后即可得到，证毕。

0x05 Acknowledgement

笔者前前后后断断续续学习优化内容有快 1 年的年头了，也走了不少弯路。在学习的过程中，笔者最先从论文中的推导进行学习，然而很多定义无法看懂或理解，于是选择了专门的优化书进行学习，可能悟性较差，但是很多也是摸不着头脑或者跟自己研究方向有些偏离太多了，变有些浮躁，因此也才会断断续续。在 22 年下半年选修了 牛凌峰 老师开的 《实用最优化算法及其应用》 这门公选课，才对整个领域有所了解和认识，在今年再进行阅读领域相关内容变得轻松很多。在此感谢 牛凌峰 老师开设的课程，让我能够轻松入门和了解优化相关内容，却不用选择像 《最优化理论与方法》 这样的专业课程。

Reference

  1. 非凸优化基石：Lipschitz Condition, https://www.zhihu.com/tardis/bd/art/27554191 ↩︎

  2. 《Introductory Lectures on Convex Programming》，Nesterov ↩︎

  3. 不同条件下梯度方法的收敛性分析 1——(Non)convex+(Non)smooth，https://zhuanlan.zhihu.com/p/92385493 ↩︎