0x00 Preface

这一系列整理优化方法的收敛性分析。本篇统一符号，介绍凸性、强凸性、光滑性、随机梯度假设和后续证明中常用的不等式。笔者并非优化科班出身，因为研究需要学习这些内容；如有疏漏，欢迎指出。

全文默认使用欧氏范数 $\Vert\cdot\Vert_2$，简写为 $\Vert\cdot\Vert$。除特别说明外，讨论无约束问题 $\min_{w\in\mathbb R^d}f(w)$。$w^{\ast}$ 表示存在的最优解，$f^{\ast}=f(w^{\ast})$；当最小值不一定取得时，使用有限下界 $f_{\inf}$。

深度神经网络的目标通常非凸。凸或强凸条件下的定理是理解优化的理论模型，不能直接当作一般神经网络训练的保证。

0x01 Fundamental Concepts

Convex Function

函数 $f$ 在凸集 $\mathcal D$ 上凸，是指对任意 $x,y\in\mathcal D$ 和 $\theta\in[0,1]$，有

$$ f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y). $$

当 $f$ 可微时，等价的一阶条件为

$$ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle. $$

非光滑凸函数不一定有梯度。此时使用次梯度 $g\in\partial f(x)$，它满足对所有 $y$ 有 $f(y)\ge f(x)+\langle g,y-x\rangle$。

$\mu$-strongly Convex

defination

对可微函数，$\mu$-强凸（$\mu>0$）是指
$$ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|^2. $$
非光滑情况下，将 $\nabla f(x)$ 换成 $g\in\partial f(x)$。

在欧氏范数下，$f$ 为 $\mu$-强凸，等价于 $f(x)-\mu\Vert x\Vert^2/2$ 为凸函数。这里不把这个等价关系推广到任意范数。

若 $w^{\ast}$ 是可微函数的无约束最优解，则 $\nabla f(w^{\ast})=0$。分别应用强凸不等式可得

$$ f(w)-f^*\ge\frac{\mu}{2}\|w-w^*\|^2, \qquad \langle\nabla f(w),w-w^*\rangle \ge f(w)-f^*+\frac{\mu}{2}\|w-w^*\|^2. $$

Lipschitz Continuous

函数值 $G$-Lipschitz 连续是指

$$ |f(x)-f(y)|\le G\|x-y\|. $$

在全空间上，对于可微函数，这与梯度范数一致有界 $\Vert\nabla f(x)\Vert\le G$ 等价。对于非光滑凸函数，对应的是次梯度有界；在受限定义域上，需要明确选用哪些次梯度以及边界条件。

Smoothness

defination

可微函数 $f$ 为 $L$-光滑，是指梯度 $L$-Lipschitz 连续：
$$ \|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|. $$

这里约束的是梯度的变化，与函数值 Lipschitz 是两个不同的性质。光滑性推出下降引理：

$$ \left|f(y)-f(x)-\langle\nabla f(x),y-x\rangle\right| \le\frac{L}{2}\|y-x\|^2. $$

证明来自线段积分：

$$ \begin{aligned} f(y)-f(x)-\langle\nabla f(x),y-x\rangle &=\int_0^1\langle\nabla f(x+s(y-x))-\nabla f(x),y-x\rangle\,ds,\\ \left|f(y)-f(x)-\langle\nabla f(x),y-x\rangle\right| &\le\int_0^1 Ls\|y-x\|^2\,ds =\frac L2\|y-x\|^2. \end{aligned} $$

可微凸函数的单侧二次上界与梯度 Lipschitz 等价，但对一般非凸函数，不能用单侧上界作为这个等价关系。例如 $f(x)=-x^4$ 是凹函数，满足任意正 $L$ 的单侧上界，但梯度不在全空间 Lipschitz。后续非凸分析采用上面的梯度定义。

0x02 Optimization Methods

Gradient Descent

$$ w_{t+1}=w_t-\eta_t\nabla f(w_t),\qquad\eta_t>0. $$

步长可以固定，也可以变化；梯度下降的定义本身不要求步长单调递减。下面的恒等式是距离分析的起点：

$$ \|w_{t+1}-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. $$

Stochastic and Mini-batch Gradient Descent

设单个样本的损失为 $\ell(w;\xi)$，总体目标为 $f(w)=\mathbb E_\xi[\ell(w;\xi)]$。在允许交换求导与期望的条件下，独立采样得到

$$ g_t=\frac1b\sum_{r=1}^b\nabla\ell(w_t;\xi_{t,r}),\qquad w_{t+1}=w_t-\eta_tg_t. $$

$b=1$ 时为单样本 SGD；$b>1$ 时为 mini-batch SGD。用 $\ell$ 区分样本损失与目标函数，避免把单样本梯度和 batch 平均混为一谈。

0x03 Common Assumptions

这些条件由具体定理按需使用，并非所有分析都要求同时成立。

Bounded Domain and Bounded Subgradients

若需要受限优化，可以假设闭凸可行集 $\mathcal C$ 的直径不超过 $D$，即 $\Vert x-y\Vert\le D$。这是定义域有界，不是方差有界。

非光滑分析常假设所选次梯度满足 $\Vert g_t\Vert\le G$。全空间上的强凸函数不能同时具有全局有界梯度：强凸带来至少二次增长，函数值 Lipschitz 却只允许至多线性增长。因此相关定理必须限定可行集或迭代轨迹，并说明约束如何保持。

Conditional Unbiasedness and Bounded Variance

令 $\mathcal F_t$ 表示采样前的历史信息，$w_t$ 对 $\mathcal F_t$ 可测。假设每轮的新样本在给定历史后相互独立，且

$$ \mathbb E[\nabla\ell(w_t;\xi_{t,r})\mid\mathcal F_t]=\nabla f(w_t), \qquad \mathbb E[\|\nabla\ell(w_t;\xi_{t,r})-\nabla f(w_t)\|^2\mid\mathcal F_t]\le\sigma^2. $$

则 mini-batch 平均满足

$$ \mathbb E[g_t\mid\mathcal F_t]=\nabla f(w_t),\qquad \mathbb E[\|g_t-\nabla f(w_t)\|^2\mid\mathcal F_t]\le\frac{\sigma^2}{b}, $$ $$ \mathbb E[\|g_t\|^2\mid\mathcal F_t] \le\|\nabla f(w_t)\|^2+\frac{\sigma^2}{b}. $$

方差缩减来自平均中噪声交叉项的条件期望为零。如果样本重复或噪声相关，不能只凭“无偏”就断言方差按 $1/b$ 缩减。这里向量方差用平方范数的期望表示。

0x04 Common Inequalities

Cauchy-Schwarz and Triangle Inequalities

$$ |\langle x,y\rangle|\le\|x\|\|y\|,\qquad \|x+y\|\le\|x\|+\|y\|. $$

Jensen Inequality

若 $f$ 为凸函数，$\theta_i\ge0$ 且 $\sum_i\theta_i=1$，则

$$ f\left(\sum_i\theta_ix_i\right)\le\sum_i\theta_if(x_i). $$

等权情形为 $f(\bar x)\le n^{-1}\sum_i f(x_i)$，其中 $\bar x=n^{-1}\sum_i x_i$。它不意味着 $f(n\bar x)\le nf(\bar x)$；取 $f(x)=x^2$ 即可构造反例。

Polyak–Łojasiewicz (PL) Inequality

defination

PL 条件为
$$ \|\nabla f(x)\|^2\ge2\mu(f(x)-f^*). $$
可微、无约束的 $\mu$-强凸函数满足该条件；PL 条件本身不要求函数强凸，也不要求凸。

证明强凸推出 PL：固定 $x$，强凸性给出对任意 $y$ 有

$$ f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\frac\mu2\|y-x\|^2. $$

右侧关于 $y$ 的最小值为 $f(x)-\Vert\nabla f(x)\Vert^2/(2\mu)$。取两侧下确界，可得 $f^{\ast}\ge f(x)-\Vert\nabla f(x)\Vert^2/(2\mu)$，移项即得结论。

0x05 Acknowledgement

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

Reference

Sources: 1 2 3.

  1. Boyd, S. and Vandenberghe, L., Convex Optimization, Chapters 3 and 9. ↩︎

  2. Bottou, L., Curtis, F. E. and Nocedal, J., Optimization Methods for Large-Scale Machine Learning, Section 4. ↩︎

  3. Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course. ↩︎