从零发明数值最优化 2：梯度下降法

在上一篇文章中，我们讲了线搜索是如何确定步长的。能确定步长的前提是已经确定了方向，而如何确定方向则是连续优化算法设计中最重要的一环。从这一篇文章开始，我们将一起从零发明多种经典的连续优化方法，一起理解这些方法是怎么确定方向的。

接上一篇文章，$\phi(\alpha) = f(x_k + \alpha p_k)$。要使 $\phi(\alpha)$ 下降，$p_k$ 方向上必须存在一个点使得 $\phi(\alpha^\star) < \phi(0)$。直觉上看，这个条件可以通过往梯度下降的方向走来解决，也就是使得 $\nabla f(x_k)^\top p_k < 0$。

在 $f(x_k)$ 的附近，$f(x_k + p_k)$ 可以用一阶泰勒展开近似表现为 $f(x_k + p_k) \approx f(x_k) + \nabla f(x_k)^\top p_k$。$f(x_k)$ 和 $\nabla f(x_k)$ 显然都是目前已知的常量，所以，既然我们希望能取到一个 $p_k$ 使 $f(x_k) + \nabla f(x_k)^\top p_k$ 最小，我们就应该让 $\nabla f(x_k)^\top p_k$ 尽可能小，也就是让 $p_k$ 的方向正好与 $\nabla f(x_k)$ 相反。

这里的 $f(x_k + p_k)$ 只是一个简化模型。而实际上，由于我们在 $f(x_k + \alpha_k p_k)$ 中还提供了一个额外的步长变量 $\alpha_k$，所以 $p_k$ 并不一定要满足 $\Vert p_k \Vert = 1$，直接取 $p_k = -\nabla f(x_k)$ 就好。

Lipschitz 连续性约束

Lipschitz 连续条件，又叫 L-光滑，是数学上用来限制函数变化速度的一个光滑性条件。它强于“连续性”，但又弱于“可微性”。数学上，它的定义是

$$\vert\nabla f(x) - \nabla f(y)\vert \le L \vert x - y \vert, \quad \forall x, y \in \mathbb{R}^n \quad (L > 0)$$

这个条件可以约束出一个所谓的“最优步长”。让我们一起来推理一下：

我们有微积分基本定理：

$$f(y) = f(x) + \int_0^1 \nabla f^\top(x + t(y - x)) (y - x) dt$$

改写一下，变成

$$f(y) = f(x) + \nabla^\top f(x) (y - x) + \int_0^1 (\nabla f(x + t(y - x)) - \nabla f(x))^\top (y - x) dt$$

由柯西不等式和 Lipschitz 条件，积分中的

$$\begin{aligned} &(\nabla f(x + t(y - x)) - \nabla f(x))^\top (y - x) \\ \le & \Vert \nabla f(x + t(y - x)) - \nabla f(x) \Vert \cdot \Vert y - x \Vert \\ \le & L t \Vert y-x \Vert^2 \end{aligned}$$

于是得到

$$f(y) \le f(x) + \nabla f^\top(x) (y - x) + \frac{L}{2} \Vert{}y - x\Vert{}^2$$

在我们的语境中，$x = x_k$，$y = x_{k+1} = x_k - \alpha \nabla f(x_k)$，所以带入后就得到

$$f(x_{k+1}) \le f(x_k) - \alpha_k \left( 1 - \frac{\alpha L}{2} \right) \Vert \nabla f(x_k) \Vert^2$$

要让 $f(x_{k+1}) < f(x_k)$，就要让 $\alpha_k \left(1 - \frac{\alpha_k L}{2}\right) > 0$。已知 $\alpha_k > 0$，所以保证单调下降的步长区间就是 $0 < \alpha_k < \frac{2}{L}$。

我们也可以把 $\alpha_k$ 看作自变量，那么单步下降量就是关于 $\alpha_k$ 的二次函数 $g(\alpha_k) = \alpha_k - \frac{L}{2} \alpha_k^2$。所以，理论上来说，$\alpha_k = \frac{1}{L}$ 时，单步理论下降量达到最大。也因此，标准梯度下降算法在具有 $L$-Lipschitz 梯度的目标函数上通常直接选取 $\alpha = \frac{1}{L}$。

Lipschitz 条件看似是一个单纯的“数学游戏”，一个莫名其妙冒出来的奇怪条件，但其实在真实场景中很常见，是现代一阶数值优化与机器学习理论中最核心、最普适的基础假设。Hessian 矩阵有界的函数、二次优化问题 $f(x) = \frac{1}{2} \Vert Ax - b \Vert _2^2$、逻辑回归等都天然满足 Lipschitz 条件。

收敛速度

收敛速度有两种表示方式，一种是收敛 $k$ 步能把误差控制到多少以内，另一种是收敛到 $\epsilon$ 精度以内需要多少步。其实这两种表示方法完全可以通过 $f(k)=\epsilon$、$k=g(\epsilon)$ 的公式相互转换，比如说 $O(\frac{1}{k})$ 就是 $O(\frac{1}{\epsilon})$，$O(\frac{1}{k^2})$ 就是 $O(\frac{1}{\sqrt{\epsilon}})$，等等。

由于凸函数与 Lipschitz 条件都是很常见的条件，我们就在这两个条件下进行分析。步长就取上面提到的理论最优步长 $\alpha_k = \frac{1}{L}$。所以我们有

$$f(x_{k+1}) \le f(x_k) - \frac{1}{2L} \Vert \nabla f(x_k) \Vert^2$$

又因为凸性，我们有

$$f(x^\star) \ge f(x_k) + \nabla f^\top (x_k) (x^\star - x_k)$$

所以

$$f(x_k) - f(x^\star) \le \nabla f^\top (x_k) (x_k - x^\star) \le \Vert \nabla f(x_k) \Vert \cdot \Vert x_k - x^\star \Vert$$

$$\Vert \nabla f(x_k) \Vert \ge \frac{f(x_k) - f(x^\star)}{\Vert x_k - x^\star \Vert}$$

带入 Lipschitz 条件得到的公式，我们就得到

$$f(x_{k+1}) \le f(x_k) - \frac{1}{2L} \left( \frac{f(x_k) - f(x^\star)}{\Vert x_k - x^\star \Vert} \right) ^2$$

变形得

$$f(x_{k+1}) - f(x^\star) \le f(x_k) - f(x^\star) - \frac{1}{2L} \left( \frac{f(x_k) - f(x^\star)}{\Vert x_k - x^\star \Vert} \right) ^2$$

把误差记为 $\Delta_k = f(x_k) - f(x^*)$，则有

$$\Delta_{k+1} \le \Delta_k - \frac{1}{2L \Vert x_k - x^\star \Vert^2} \Delta_k^2$$

利用 $\Delta_{k+1} \le \Delta_k$，

$$\frac{1}{\Delta_{k+1}} - \frac{1}{\Delta_k} \ge \frac{\Delta_k}{\Delta_{k+1} \cdot 2L \Vert x_k - x^\star \Vert^2} \ge \frac{1}{2L \Vert x_k - x^\star \Vert^2}$$

累加，得

$$\frac{1}{\Delta_k} \ge \frac{1}{\Delta_0} + \frac{k}{2L \max \Vert x_k - x^\star \Vert^2} \ge \frac{k}{2L \max \Vert x_k - x^\star \Vert^2}$$

可见 $\Delta_k=O\left( \frac{1}{k} \right)$。用另外一种表示方法，就是 $O\left(\frac{1}{\epsilon}\right)$。这时的收敛阶数属于次线性收敛。

当然，一些时候函数会满足一些更强的条件。比如说，在 $\mu$-强凸且 $L$-光滑时，收敛速度就是 $f(x_k) - f^* \le O\left(\left(1 - \frac{\mu}{L}\right)^k\right)$，或者说 $O\left(\frac{L}{\mu} \log \frac{1}{\epsilon}\right)$ 的，属于线性收敛。而在更弱的非凸但 $L$-光滑条件下，收敛速度就是 $O\left( \frac{1}{\sqrt{k}} \right)$ 或者说 $O \left( \frac{1}{\epsilon^2} \right)$ 的，属于次线性收敛。（这两种条件下的证明见附录）

算法瓶颈分析

高条件数下的缺陷

当目标函数的等高线具有极高条件数时，圆在特征空间中被拉伸为细长椭圆，负梯度方向与通往全局最小值的方向近乎正交。

精确线搜索下的特点

精确线搜索下，步长 $\alpha_k$ 满足 $\phi'(\alpha_k) = 0$，即 $\nabla f(x_{k+1})^\top p_k = 0$。

结合 $p_{k+1} = -\nabla f(x_{k+1})$ 和 $\nabla f(x_{k+1})^\top p_k = 0$，可得 $p_{k+1}^\top p_k = -\nabla f(x_{k+1})^\top p_k = 0$。

由于 $p_{k+1}^\top p_k = 0$，梯度下降轨迹在几何上很容易走出 $90^\circ$ 的直角折线。算法在狭长山谷两侧的峭壁间剧烈横跳，而沿低斜率山谷底部的推进极其缓慢，导致收敛停滞。

附录

梯度下降在两种条件下的收敛速度

设 $f$ 可微，取固定步长 $\alpha_k = \frac{1}{L}$（与正文“收敛速度”一节的取法一致）。由正文的 $L$-光滑性分析已经得到下降引理

$$f(x_{k+1}) \le f(x_k) - \frac{1}{2L} \Vert \nabla f(x_k) \Vert^2. \tag{A}$$

下面分别讨论“$\mu$-强凸且 $L$-光滑”与“非凸但 $L$-光滑”两种情形。记 $f^\star = \min f$（对非凸情形取 $f^\star = \inf f$），$x^\star$ 为任一极小值点，并记误差 $\Delta_k = f(x_k) - f^\star \ge 0$。

非凸且 $L$-光滑：$O\left(\frac{1}{\sqrt{k}}\right)$

把 (A) 从 $i = 0$ 累加到 $i = k$，左端是一个望远镜求和：

$$\frac{1}{2L} \sum_{i=0}^k \Vert \nabla f(x_i) \Vert^2 \le \sum_{i=0}^k \big( f(x_i) - f(x_{i+1}) \big) = f(x_0) - f(x_{k+1}) \le f(x_0) - f^\star.$$

因此

$$\min_{0 \le i \le k} \Vert \nabla f(x_i) \Vert^2 \le \frac{1}{k+1} \sum_{i=0}^k \Vert \nabla f(x_i) \Vert^2 \le \frac{2L \big( f(x_0) - f^\star \big)}{k+1},$$

即

$$\min_{0 \le i \le k} \Vert \nabla f(x_i) \Vert \le \sqrt{\frac{2L \big( f(x_0) - f^\star \big)}{k+1}} = O\left( \frac{1}{\sqrt{k}} \right).$$

要让 $\min_i \Vert \nabla f(x_i) \Vert \le \epsilon$，只需 $k + 1 \ge \frac{2L (f(x_0) - f^\star)}{\epsilon^2}$，故迭代次数为 $O\left( \frac{1}{\epsilon^2} \right)$，属于次线性收敛。这也说明：在非凸情形下，梯度下降只能保证梯度范数的一个子序列趋于零，而无法保证函数值本身收敛到某个特定的 $f^\star$。

$\mu$-强凸且 $L$-光滑：线性收敛

第一步：把函数值误差用梯度范数控制。 $\mu$-强凸性等价于对任意 $x, y$ 有

$$f(y) \ge f(x) + \nabla f(x)^\top (y - x) + \frac{\mu}{2} \Vert y - x \Vert^2.$$

在 $x = x_k$、$y = x^\star$ 处使用，并注意 $\nabla f(x^\star) = 0$：

$$f(x^\star) \ge f(x_k) + \nabla f(x_k)^\top (x^\star - x_k) + \frac{\mu}{2} \Vert x^\star - x_k \Vert^2,$$

移项得

$$f(x_k) - f^\star \le \nabla f(x_k)^\top (x_k - x^\star) - \frac{\mu}{2} \Vert x_k - x^\star \Vert^2.$$

令 $d = x_k - x^\star$，右端是关于 $d$ 的二次函数，其最大值为 $\frac{1}{2\mu} \Vert \nabla f(x_k) \Vert^2$（在 $d = \frac{1}{\mu} \nabla f(x_k)$ 处取得）。于是

$$f(x_k) - f^\star \le \frac{1}{2\mu} \Vert \nabla f(x_k) \Vert^2, \qquad\text{即}\qquad \Vert \nabla f(x_k) \Vert^2 \ge 2\mu \, \Delta_k. \tag{B}$$

第二步：递推收缩。 把 (B) 代入 (A)：

$$\Delta_{k+1} \le \Delta_k - \frac{1}{2L} \Vert \nabla f(x_k) \Vert^2 \le \Delta_k - \frac{\mu}{L} \Delta_k = \left( 1 - \frac{\mu}{L} \right) \Delta_k.$$

由于 $\mu \le L$，收缩因子满足 $1 - \frac{\mu}{L} \in [0, 1)$。递推展开得

$$\Delta_k \le \left( 1 - \frac{\mu}{L} \right)^k \Delta_0, \qquad\text{即}\qquad f(x_k) - f^\star = O\left( \left( 1 - \frac{\mu}{L} \right)^k \right).$$

第三步：迭代复杂度。 要求 $\Delta_k \le \epsilon$，只需

$$\left( 1 - \frac{\mu}{L} \right)^k \Delta_0 \le \epsilon \quad\Longleftrightarrow\quad k \ge \frac{\log (\Delta_0 / \epsilon)}{\log \left( \frac{1}{1 - \mu / L} \right)}.$$

利用 $\log \frac{1}{1 - t} \ge t \ (0 \le t < 1)$，有 $\frac{1}{\log (1 / (1 - \mu / L))} \le \frac{L}{\mu}$，于是

$$k = O\left( \frac{L}{\mu} \log \frac{1}{\epsilon} \right).$$

这正是正文所说的线性收敛。其中比值 $\kappa = \frac{L}{\mu}$ 即条件数：条件数越大，收缩因子 $1 - \frac{1}{\kappa}$ 越接近 $1$，迭代次数越多。

补充： $\mu$-强凸性也蕴含梯度的强单调性，即对任意 $x, y$ 有 $(\nabla f(x) - \nabla f(y))^\top (x - y) \ge \mu \Vert x - y \Vert^2$。取 $y = x^\star$ 并用柯西不等式，可得 $\Vert \nabla f(x) \Vert \ge \mu \Vert x - x^\star \Vert$；它与 $L$-光滑给出的 $\Vert \nabla f(x) \Vert \le L \Vert x - x^\star \Vert$ 一起，把函数值误差、梯度范数与到极小值点的距离三者互相控制起来。