返回

梯度下降的收敛性分析

编辑此页

前置知识

Lipschitz 连续

f:Rn→Rmf: \mathbb{R}^n \rightarrow \mathbb{R}^m 是 Lipschitz 连续（LL-continuous）的，当且仅当 ∃L>0\exists L > 0，使得 ∀x,y∈Rn\forall x, y \in \mathbb{R}^n，有

∥f(x)−f(y)∥≤L∥x−y∥\|f(x) - f(y)\| \le L \|x - y\|

Lipschitz 光滑

与 Lipschitz 连续类似，f:Rn→Rmf: \mathbb{R}^n \rightarrow \mathbb{R}^m 是 Lipschitz 光滑（LL-smooth）的，当且仅当 ∃L>0\exists L > 0，使得 ∀x,y∈Rn\forall x, y \in \mathbb{R}^n，有

∥∇f(x)−∇f(y)∥≤L∥x−y∥\|\nabla f(x) - \nabla f(y)\| \le L \|x - y\|

凸函数

f:Rn→Rf: \mathbb{R}^n \rightarrow \mathbb{R} 是凸函数（convex function），当且仅当 ∀x,y∈Rn,∀λ∈[0,1]\forall x, y \in \mathbb{R}^n, \forall \lambda \in [0, 1]，有

f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)⇔f(y)≥f(x)+∇f(x)T(y−x)⇔∇2f(x)≽0f(\lambda x + (1 - \lambda) y) \le \lambda f(x) + (1 - \lambda) f(y) \\ \Leftrightarrow f(y) \ge f(x) + \nabla f(x)^T (y - x) \\ \Leftrightarrow \nabla^2 f(x) \succcurlyeq 0
注

对于矩阵 A∈Rn×nA \in \mathbb{R}^{n\times n}，∀x∈Rn\forall x \in \mathbb{R}^n：

  • 如果 xTAx≥0x^T A x \ge 0，则称 AA 是半正定矩阵（positive semi-definite matrix, p.s.d. matrix），记作 A≽0A \succcurlyeq 0。
  • 如果 xTAx>0x^T A x > 0，则称 AA 是正定矩阵（positive definite matrix, p.d. matrix），记作 A≻0A \succ 0。

从特征值的角度来看，对于 AA 的所有特征值 λi,∀i=1,⋯ ,n\lambda_i, \forall i=1,\cdots,n

  • A≽0A \succcurlyeq 0 等价于 λi≥0\lambda_i \ge 0
  • A≻0A \succ 0 等价于 λi>0\lambda_i > 0。

强凸函数

f:Rn→Rf: \mathbb{R}^n \rightarrow \mathbb{R} 是强凸函数（strongly convex function），当且仅当 ∃μ>0\exists \mu > 0，使得 ∀x,y∈Rn,∀λ∈[0,1]\forall x, y \in \mathbb{R}^n, \forall \lambda \in [0, 1]，有

f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)−μ2λ(1−λ)∥x−y∥2⇔f(y)≥f(x)+∇f(x)T(y−x)+μ2∥x−y∥2⇔∇2f(x)≽μIf(\lambda x + (1 - \lambda) y) \le \lambda f(x) + (1 - \lambda) f(y) - \frac{\mu}{2} \lambda (1 - \lambda) \|x - y\|^2 \\ \Leftrightarrow f(y) \ge f(x) + \nabla f(x)^T (y - x) + \frac{\mu}{2} \|x - y\|^2 \\ \Leftrightarrow \nabla^2 f(x) \succcurlyeq \mu I

梯度下降

梯度下降（gradient descent）是一种迭代算法，在这里我们只考虑最简单的形式，即要求函数 ff 至少是 Lipschitz 光滑的，则有

f(xk+1)≤f(xk)+∇f(xk)T(xk+1−xk)+L2∥xk+1−xk∥2f(x_{k+1}) \le f(x_k) + \nabla f(x_k)^T (x_{k+1} - x_k) + \frac{L}{2} \|x_{k+1} - x_k\|^2

因此尽管 ff 可能不是二次函数，但是梯度下降的迭代过程可以看作是在二次函数 f(xk)+∇f(xk)T(x−xk)+L2∥x−xk∥2f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{L}{2} \|x - x_k\|^2 上进行的，因此其优化的目标函数为

qxk(x)=f(xk)+∇f(xk)T(x−xk)+L2∥x−xk∥2≈f(x)q_{x_k}(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{L}{2} \|x - x_k\|^2 \approx f(x)

要最小化二次函数 qxk(x)q_{x_k}(x)，只需要令其梯度为 0 即可，即令

∇qxk(x)=∇f(xk)+L(x−xk)=!0⇒xk+1=x=xk−1L∇f(xk)\nabla q_{x_k}(x) = \nabla f(x_k) + L (x - x_k) \xlongequal{!} 0 \\ \Rightarrow x_{k+1} = x = x_k - \frac{1}{L} \nabla f(x_k)

这里的 −∇f(xk)-\nabla f(x_k) 即为梯度下降的方向，而 1L\frac{1}{L} 则是步长，记作 α\alpha；我们由此也能得到

f(xk+1)≤f(xk)+∇f(xk)T(xk+1−xk)+L2∥xk+1−xk∥2=f(xk)−1L∥∇f(xk)∥2+12L∥∇f(xk)∥2=f(xk)−12L∥∇f(xk)∥2\begin{align*} f(x_{k+1}) \le & f(x_k) + \nabla f(x_k)^T (x_{k+1} - x_k) + \frac{L}{2} \|x_{k+1} - x_k\|^2 \\ = & f(x_k) - \frac{1}{L} \|\nabla f(x_k)\|^2 + \frac{1}{2L} \|\nabla f(x_k)\|^2 \\ = & f(x_k) - \frac{1}{2L} \|\nabla f(x_k)\|^2 \end{align*}
牛顿法

除了梯度下降，我们还可以使用牛顿法（Newton’s method）来进行优化。为了解 h(x)=0h(x)=0，我们可以令 g(x)=x−αh(x)g(x)=x-\alpha h(x)，其中 α>0\alpha>0 是缩放系数，那么我们可以如此迭代：

xk+1=g(xk)x_{k+1} = g(x_k)

迭代至收敛时，则有

x∗=g(x∗)=x∗−αh(x∗)⇒h(x∗)=0x_* = g(x_*) = x_* - \alpha h(x_*) \\ \Rightarrow h(x_*) = 0

收敛标准

假定定义域中 x∗∈Ωx_*\in\Omega 是 ff 的最小值点，对应的函数值为 f(x∗)=f∗f(x_*) = f_*，那么对于 ∀ε>0\forall\varepsilon > 0：

  1. 如果 f(x)−f∗≤εf(x)-f_* \le\varepsilon，那么称 xx 是 ε\varepsilon-最优点（ε\varepsilon-optimal point）
  2. 如果 ∥∇f(x)∥≤ε\|\nabla f(x)\| \le\varepsilon，那么称 xx 是 ε\varepsilon-临界点（ε\varepsilon-critical point）

收敛性分析

在前面的推导中，我们得到了对于 Lipschitz 光滑函数 ff，梯度下降的迭代步长为 α=1L\alpha = \frac{1}{L}，因此以下分析都是基于这个步长的。需要说明的是，不管是在实际应用中还是理论分析中，对于不仅光滑并且凸的函数，有更优的迭代步长，能够以更快的速度收敛，但是其推导较为复杂，这里我们只考虑最简单的情况。

Lipschitz 光滑函数

对于 Lipschitz 光滑函数 ff，我们有

f(x+αd)≤f(x)+α∇f(x)Td+L2α2∥d∥2⇒f(xk+1)≤f(xk)−12L∥∇f(xk)∥2⇒f(xT)≤f(x0)−12L∑k=0T−1∥∇f(xk)∥2⇒∑k=0T−1∥∇f(xk)∥2≤2L(f(x0)−f(xT))≤2L(f(x0)−f∗)⇒min⁡0≤k≤T−1∥∇f(xk)∥2≤2LT(f(x0)−f∗)⇒min⁡0≤k≤T−1∥∇f(xk)∥≤2LT(f(x0)−f∗)\begin{align*} f(x+\alpha d) \le & f(x) + \alpha\nabla f(x)^Td + \frac{L}{2}\alpha^2\|d\|^2 \\ \Rightarrow f(x_{k+1}) \le & f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2 \\ \Rightarrow f(x_T) \le & f(x_0) - \frac{1}{2L}\sum_{k=0}^{T-1}\|\nabla f(x_k)\|^2 \\ \Rightarrow \sum_{k=0}^{T-1}\|\nabla f(x_k)\|^2 \le & 2L\left(f(x_0) - f(x_T)\right) \\ \le & 2L\left(f(x_0) - f_*\right) \\ \Rightarrow \min_{0\le k\le T-1}\|\nabla f(x_k)\|^2 \le & \frac{2L}{T}\left(f(x_0) - f_*\right) \\ \Rightarrow \min_{0\le k\le T-1}\|\nabla f(x_k)\| \le & \sqrt{\frac{2L}{T}\left(f(x_0) - f_*\right)} \end{align*}

因此可以看到要达到 ε\varepsilon-临界点，需要迭代次数要满足

2LT(f(x0)−f∗)≤ε⇒T≥2Lε2(f(x0)−f∗)\begin{align*} \sqrt{\frac{2L}{T}\left(f(x_0) - f_*\right)} \le & \varepsilon \\ \Rightarrow T \ge & \frac{2L}{\varepsilon^2}\left(f(x_0) - f_*\right) \end{align*}

因此收敛所需时间复杂度为 O(1ε2)O\left(\frac{1}{\varepsilon^2}\right)，为次线性收敛。

收敛速度

对于序列 {an}\{a_n\}，如果 lim⁡n→∞an→0\lim_{n\to\infty}a_n\to0，并且有

lim⁡n→∞an+1an=ρ\lim_{n\to\infty}\frac{a_{n+1}}{a_n} = \rho
  1. 如果 ρ=0\rho=0，则称 {an}\{a_n\} 是超线性收敛的
  2. 如果 ρ∈(0,1)\rho\in(0,1)，则称 {an}\{a_n\} 是线性收敛的
  3. 如果 ρ=1\rho=1，则称 {an}\{a_n\} 是次线性收敛的

Lipschitz 光滑 + 凸函数

对于凸函数 ff，我们有

f(y)≥f(x)+∇f(x)T(y−x)Let{y=x∗x=xk⇒f∗≥f(xk)+∇f(xk)T(x∗−xk)⇒f(xk)≤f∗+∇f(xk)T(xk−x∗)\begin{align*} f(y) \ge & f(x) + \nabla f(x)^T(y - x) \\ \text{Let} \begin{cases} y=x_*\\ x=x_k \end{cases} \Rightarrow f_* \ge & f(x_k) + \nabla f(x_k)^T(x_* - x_k) \\ \Rightarrow f(x_k) \le & f_* + \nabla f(x_k)^T(x_k - x_*) \end{align*}

结合前面推到的 Lipschitz 光滑函数有 f(xk+1)≤f(xk)−12L∥∇f(xk)∥2f(x_{k+1}) \le f(x_k)-\frac{1}{2L}\left\|\nabla f(x_k)\right\|^2，代入可得

f(xk+1)≤f∗+∇f(xk)T(xk−x∗)−12L∥∇f(xk)∥2f(x_{k+1}) \le f_* + \nabla f(x_k)^T(x_k - x_*) - \frac{1}{2L}\left\|\nabla f(x_k)\right\|^2

又有

∥∇f(xk)∥2=L2∥xk+1−xk∥2=L2(∥xk+1−x∗∥2+∥xk−x∗∥2−2<xk+1−x∗,xk−x∗>)=L2(∥xk+1−x∗∥2+∥xk−x∗∥2−2<xk−1L∇f(xk)−x∗,xk−x∗>)=L2(∥xk+1−x∗∥2−∥xk−x∗∥2+2L<∇f(xk),xk−x∗>)=L2(∥xk+1−x∗∥2−∥xk−x∗∥2+2L∇f(xk)T(xk−x∗))\begin{align*} \left\|\nabla f(x_k)\right\|^2 = & L^2\left\|x_{k+1} - x_k\right\|^2 \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 + \left\|x_k - x_*\right\|^2 - 2 \left<x_{k+1}-x_*,x_k-x_*\right>\right) \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 + \left\|x_k - x_*\right\|^2 - 2 \left<x_k-\frac{1}{L}\nabla f(x_k)-x_*,x_k-x_*\right>\right) \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2 + \frac{2}{L} \left<\nabla f(x_k),x_k-x_*\right>\right) \\ = & L^2 \left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2 + \frac{2}{L} \nabla f(x_k)^T(x_k-x_*)\right) \\ \end{align*}

代入上式可得

f(xk+1)≤f∗+∇f(xk)T(xk−x∗)−L2(∥xk+1−x∗∥2−∥xk−x∗∥2+2L∇f(xk)T(xk−x∗))=f∗−L2(∥xk+1−x∗∥2−∥xk−x∗∥2)⇒∑k=0T−1f(xk+1)≤Tf∗−L2(∥xT−x∗∥2−∥x0−x∗∥2)≤Tf∗+L2∥x0−x∗∥2\begin{align*} f(x_{k+1}) \le & f_* + \nabla f(x_k)^T(x_k - x_*) \\ & - \frac{L}{2}\left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2 + \frac{2}{L} \nabla f(x_k)^T(x_k-x_*)\right) \\ = & f_* - \frac{L}{2}\left(\left\|x_{k+1} - x_*\right\|^2 - \left\|x_k - x_*\right\|^2\right) \\ \Rightarrow \sum_{k=0}^{T-1}f(x_{k+1}) \le & Tf_* - \frac{L}{2}\left(\left\|x_T - x_*\right\|^2 - \left\|x_0 - x_*\right\|^2\right) \\ \le & Tf_* + \frac{L}{2}\left\|x_0 - x_*\right\|^2 \end{align*}

又因为每一步都有 f(xk+1)≤f(xk)−12L∥∇f(xk)∥2f(x_{k+1}) \le f(x_k)-\frac{1}{2L}\left\|\nabla f(x_k)\right\|^2，因此 ∀k=0,⋯ ,T−1,f(xT)<f(xk)\forall k=0,\cdots,T-1,\quad f(x_T)<f(x_k)，因此有

Tf(xT)≤Tf∗+L2∥x0−x∗∥2⇒f(xT)−f∗≤L2T∥x0−x∗∥2\begin{align*} T f(x_T) \le & T f_* + \frac{L}{2}\left\|x_0 - x_*\right\|^2 \\ \Rightarrow f(x_T) - f_* \le & \frac{L}{2T}\left\|x_0 - x_*\right\|^2 \\ \end{align*}

要达到 ε\varepsilon-最优点，需要迭代次数要满足

L2T∥x0−x∗∥2≤ε⇒T≥L2ε∥x0−x∗∥2\begin{align*} \frac{L}{2T}\left\|x_0 - x_*\right\|^2 \le & \varepsilon \\ \Rightarrow T \ge & \frac{L}{2\varepsilon}\left\|x_0 - x_*\right\|^2 \end{align*}

因此收敛所需时间复杂度为 O(1ε)O\left(\frac{1}{\varepsilon}\right)，依然为次线性收敛。

Lipschitz 光滑 + 强凸函数

对于强凸函数 ff，我们有

f(y)≥f(x)+∇f(x)T(y−x)+μ2∥y−x∥2Let{y=x∗y−x=−∇f(x)μ⇒f∗≥f(x)−1μ∥∇f(x)∥2+μ2⋅1μ2∥∇f(x)∥2=f(x)−12μ∥∇f(x)∥2⇒f(x)−f∗≤12μ∥∇f(x)∥2\begin{align*} f(y) \ge & f(x) + \nabla f(x)^T(y - x) + \frac{\mu}{2}\|y - x\|^2 \\ \text{Let} \begin{cases} y=x_*\\ y-x=-\frac{\nabla f(x)}{\mu} \end{cases} \Rightarrow f_* \ge & f(x) - \frac{1}{\mu}\left\|\nabla f(x)\right\|^2 + \frac{\mu}{2}\cdot\frac{1}{\mu^2}\left\|\nabla f(x)\right\|^2 \\ = & f(x) - \frac{1}{2\mu}\left\|\nabla f(x)\right\|^2 \\ \Rightarrow f(x)-f_* \le & \frac{1}{2\mu}\left\|\nabla f(x)\right\|^2 \end{align*}

结合前面推到的 Lipschitz 光滑函数有 f(xk+1)≤f(xk)−12L∥∇f(xk)∥2f(x_{k+1}) \le f(x_k)-\frac{1}{2L}\left\|\nabla f(x_k)\right\|^2，代入可得

f(xk+1)≤f(xk)−2μ2L(f(xk)−f∗)⇒f(xk+1)−f∗≤f(xk)−f∗−μL(f(xk)−f∗)=(1−μL)(f(xk)−f∗)⇒f(xT)−f∗≤(1−μL)T(f(x0)−f∗)\begin{align*} f(x_{k+1}) \le & f(x_k) - \frac{2\mu}{2L}\left(f(x_k)-f_*\right) \\ \Rightarrow f(x_{k+1})-f_* \le & f(x_k)-f_* - \frac{\mu}{L}\left(f(x_k)-f_*\right) \\ = & \left(1-\frac{\mu}{L}\right)\left(f(x_k)-f_*\right) \\ \Rightarrow f(x_T)-f_* \le & \left(1-\frac{\mu}{L}\right)^T\left(f(x_0)-f_*\right) \end{align*}

要达到 ε\varepsilon-最优点，需要迭代次数要满足

(1−μL)T(f(x0)−f∗)≤ε⇒f(x0)−f∗ε≤(1−μL)−T⇒log⁡f(x0)−f∗ε≤Tlog⁡11−μL⏟≈μL⇒T≥Lμlog⁡f(x0)−f∗ε\begin{align*} \left(1-\frac{\mu}{L}\right)^T\left(f(x_0)-f_*\right) \le & \varepsilon \\ \Rightarrow \frac{f(x_0)-f_*}{\varepsilon} \le & \left(1-\frac{\mu}{L}\right)^{-T} \\ \Rightarrow \log\frac{f(x_0)-f_*}{\varepsilon} \le & T\underbrace{\log\frac{1}{1-\frac{\mu}{L}}}_{\approx \frac{\mu}{L}} \\ \Rightarrow T \ge & \frac{L}{\mu}\log\frac{f(x_0)-f_*}{\varepsilon} \end{align*}

因此收敛所需时间复杂度为 O(log⁡1ε)O\left(\log\frac{1}{\varepsilon}\right)，为线性收敛。

杂记

期中季实在太忙了，有好多想写的东西，但是连手头在做的项目代码都没时间写，就都别提这些了，只能先记一点可能是最有用的，其他的以后再补充吧。

凸优化相关的还有很多内容，包括加速梯度下降算法，随机梯度下降算法，约束优化等等等等，这些都是很有意思的，当然如果要做收敛性分析就很有挑战了，以后有机会再写吧。大概率太难不写。

参考资料

编辑此页
分享此文章:
通过 WhatsApp 分享此文章分享此文章到 Facebook分享此文章到 X通过 Telegram 分享此文章分享此文章到 Pinterest通过 Mail 分享此文章
上一篇
他们是肉做的。
下一篇
初见 GitHub Actions