重新审视 Gradient Descent 算法：原问题的逐次逼近求解
本文尝试换一个视角重新审视 GD 。➡️
梯度下降（Gradient Descent, GD）通常被解释为沿负梯度方向走一步，是一种最基本也最常用的一阶优化算法。
但如果只停留在负梯度是最陡下降方向的直觉上，很多关键问题并不容易回答：
- 步长为什么不能随便取？
- 为什么某些步长能保证函数值下降？
- 以及 GD 与二阶泰勒近似、上界函数、近端方法之间到底有什么关系？
1. 梯度下降算法的逐次逼近视角
考虑优化问题 \[ \min_x f(x) \] 其中，\(f: \mathbb{R}^n \to \mathbb{R}\)。 设 \(f(\cdot)\) 在给定点 \(x \in \mathbb{R}^n\) 处具有二阶偏导数， 则对任意 \(z\) （足够靠近 \(x\)）的二阶泰勒展开可以写为： \[ {f}(z;x) = f(x) + \nabla f(x)^\top (z - x) + \frac{1}{2} (z - x)^\top \nabla^2 f(x) (z - x) + o(||z - x||^2). \]
如果用 \(\frac{1}{t}I\) 替代\(\nabla^2f(x)\)，则 \(f(\cdot)\) 在给定点 \(x\) 处的二阶近似可以表示为： \[ \hat{f}(z;x,t) = f(x) + \nabla f(x)^\top (z - x) + \frac{1}{2t} ||z - x||^2. \] 所以，当迭代至 \(x_k\) 时，可以通过优化 \(\hat{f}(\cdot;x_k,t)\) 来得到 \(x_{k+1}\)： \[ \begin{align} x_{k+1} =& \arg\min_{z} \hat{f}(z;x_k,t) \nonumber\\ =& \arg\min_{z} \left[f(x_k) + \nabla f(x_k)^\top (z - x_k) + \frac{1}{2t} ||z - x_k||^2\right]. \end{align} \] 该优化问题的解析解为： \[ \begin{align} \label{eq:GD_f} x_{k+1} = x_k - t \nabla f(x_k). \end{align} \]
因此可以得到梯度下降算法的逐次逼近视角：
是一种 逐次逼近 的方法
- 逐次怎么逼近：
- 先找目标函数 \(f\) 的上界 \(\hat{f}\)
- 目标函数 \(f\) 虽然凸但是直接优化困难，取而代之去优化上界 \(\hat{f}\)
- 上界 \(\hat{f}\) 具有良好的解析性质，可以直接得到最小值的显示表达式
- 总结一句话：针对上界，找上界的最小值
- 每次迭代都在求解近似目标函数 \(\hat{f}(z;x,t)\) 而不是原目标函数 \(f(z)\)
- 在 \(x_k\) 处的近似目标函数 \(\hat{f}(z;x,t)\) 最小值点就是 \(x_{k+1}\)，并且 \(x_{k+1}\) 具有解析表达式 \(\eqref{eq:GD_f}\)
交互式可视化：函数近似演示
下面的交互式图表展示了函数 \(f(x) = \ln(\cosh(x))\) 的二阶泰勒近似。通过调节参数 \(c\) 和 \(t\)，可以观察近似函数的变化。
1.
定义（\(\beta\)-smooth / 梯度 \(\beta\)-Lipschitz ）
设函数 \(f:\mathbb{R}^n\to\mathbb{R}\) 可微，若存在常数 \(\beta>0\) 使得对任意 \(z, x\in\mathbb{R}^n\) 都有： \[ \left\| {\nabla f\left( z \right) - \nabla f\left( x \right)} \right\| \le \beta \left\| {z - x} \right\|, \] 则称 \(f\) 为 \(\beta\)-smooth，或称 \(f\) 的梯度在 \(\mathbb{R}^n\) 上是 \(\beta\)-Lipschitz 连续的。
引理 设函数 \(f:\mathbb{R}^n\to\mathbb{R}\) 二阶可导且为 \(\beta\)-smooth，则对任意 \(z \in\mathbb{R}^n\)，其 Hessian 矩阵满足 \[ \nabla^2 f(z)\preceq \beta I, \] 亦即 \(\nabla^2 f(z)\) 的所有特征值都不超过 \(\beta\)，\(\beta\) 是 \(f\) 曲率的上界。
引理（Descent Lemma） \(f\) 在任意点 \(x\) 处都可被一个二次函数从上方界定： \[ f(z)\le f(x)+\langle \nabla f(x), z-x\rangle+\frac{\beta}{2}\left\|z-x\right\|^2, \forall x, z\in\mathbb{R}^n. \]
\(\beta\)-smooth 意味着函数不会比曲率为 \(\beta\) 的二次函数增长得更快。
点击展开：Descent Lemma 的证明
记 \[ d:=z-x. \]
定义一元函数（沿线段 \(x\to z\)）： \[ \phi(\tau):=f(x+\tau d),\quad \tau\in[0,1]. \] 则 \(\phi\) 可导，且由链式法则 \[ \phi'(\tau)=\left\langle \nabla f(x+\tau d), d\right\rangle. \] 由微积分基本定理 \[ f(z)-f(x)=\phi(1)-\phi(0)=\int_0^1 \phi'(\tau) d\tau =\int_0^1 \left\langle \nabla f(x+\tau d), d\right\rangle d\tau. \]
在被积项中加减 \(\nabla f(x)\)： \[ \left\langle \nabla f(x+\tau d),d\right\rangle =\left\langle \nabla f(x),d\right\rangle +\left\langle \nabla f(x+\tau d)-\nabla f(x),d\right\rangle. \] 代回积分： \[ f(z)-f(x)=\left\langle \nabla f(x),d\right\rangle +\int_0^1 \left\langle \nabla f(x+\tau d)-\nabla f(x),d\right\rangle d\tau. \]
对误差积分中的内积，用 Cauchy–Schwarz： \[ \left\langle \nabla f(x+\tau d)-\nabla f(x),d\right\rangle \le \left\|\nabla f(x+\tau d)-\nabla f(x)\right\|\cdot \left\|d\right\|. \] 由 \(\beta\)-smooth 可得： \[ \left\|\nabla f(x+\tau d)-\nabla f(x)\right\| \le \beta\left\|x+\tau d-x\right\|=\beta \tau \left\| d \right\|. \] 合并得 \[ \left\langle \nabla f(x+\tau d)-\nabla f(x),d\right\rangle \le \beta\tau\left\| d \right\|^2. \] 因此误差项积分满足 \[ \int_0^1 \left\langle \nabla f(x+\tau d)-\nabla f(x),d\right\rangle d\tau \le \int_0^1 \beta\tau\left\| d \right\|^2 d\tau =\frac{\beta}{2}\left\| d \right\|^2. \] 所以有： \[ f(z)-f(x)\le \langle \nabla f(x),d\rangle+\frac{\beta}{2}\left\| d \right\|^2. \] 即 \[ \boxed{f(z)\le f(x)+\langle \nabla f(x),z-x\rangle+\frac{\beta}{2}\left\| z-x \right\|^2,\quad \forall x,z.} \]
如果选步长 \(t\) 使得 \[ \frac{1}{t}\ge \beta\quad (\text{等价于 } t\le \frac{1}{\beta}), \] 则对任意 \(x,z\)： \[ \frac{\beta}{2}\left\|z-x\right\|^2\le \frac{1}{2t}\left\|z-x\right\|^2. \] 将其代入上面的 Descent Lemma 立刻得到 \[ f(z)\le f(x)+\langle \nabla f(x),z-x\rangle+\frac{1}{2t}\left\|z-x\right\|^2 =\hat f(z;x,t). \] 因此 \[ \boxed{\text{若 }f\text{ 是 }\beta\text{-smooth 且 }t\le 1/\beta,\ \text{则 }\hat f(\cdot;x,t)\text{ 是 }f\text{ 的上界}。} \]
直观理解：\(\hat f(\cdot;x,t)\) 二次项的曲率 \(\frac{1}{t}\) 够大，能盖住 \(f\) 的曲率上界 \(\beta\)。
2) 用二阶泰勒余项看同一件事
若 \(f\) 二次可导，泰勒定理给出： \[ f(z)=f(x)+\nabla f(x)^{\top}(z-x)+\frac{1}{2}(z-x)^{\top}\nabla^{2}f(\xi)(z-x), \] 其中 \(\xi\) 在 \(x\) 与 \(z\) 的连线上。若对这条线段上任意点都有 \[ \nabla^{2}f(\xi)\preceq \frac{1}{t}I, \] 则余项满足 \[ \frac{1}{2}(z-x)^{\top}\nabla^{2}f(\xi)(z-x)\le \frac{1}{2t}\|z-x\|^{2}, \] 同样推出 \(f(z)\le \hat f(z;x,t)\)。