优化器二：Vanilla Gradient Descent

前言

  本文我们分析Vanilla Gradient Descent在各种条件下的收敛性能。在理论分析之前，我们先简要对应用优化算法的学习问题进行建模。

学习问题的建模

  设空间$\mathcal X$为服从某种概率分布的随机变量的集合，某种规律$F$使得将随机变量$\boldsymbol{x}\in\mathcal{X}$映射至$\boldsymbol{y}\in\mathcal{Y}$。设$(\boldsymbol{x},\boldsymbol{y})\in\mathcal X \times \mathcal Y$服从联合概率分布：$\boldsymbol{P}(\boldsymbol{x},\boldsymbol{y})$，其中$\boldsymbol{x}\in\mathcal X,\boldsymbol{y}\in\mathcal Y$，且称$\mathcal X,\mathcal Y$分别为输入空间、输出空间。
  为了找出这种规律$F$，我们参数化地构造一个映射：$f(\boldsymbol{x};\boldsymbol{\theta})$，其中所有参数所有可能取值的集合记为参数空间$\boldsymbol{\Theta}$，称$f$为模型。对于任意一个$\boldsymbol{x}\in\mathcal{X}$，模型的预测值$\boldsymbol{\hat y}=f(\boldsymbol{x};\boldsymbol{\theta})$与真实值$\boldsymbol{y}=F(\boldsymbol{x})$之间往往存在差异，此时我们依托某种度量函数$L$来刻画这种差异：$L=L(\boldsymbol{\hat y},\boldsymbol{y})$，这种度量函数通常称为损失函数，相应的度量值称为损失。我们定义：

$$ \mathcal L(\boldsymbol{\theta})=\int_{\mathcal X\times \mathcal Y} L(f(\boldsymbol{x};\boldsymbol{\theta}),\boldsymbol{y})\text{d}\boldsymbol{P}(\boldsymbol{x},\boldsymbol{y})=\mathbb{E}[L(f(\boldsymbol{x};\boldsymbol{\theta}),\boldsymbol{y})]\tag{1} $$

称之为期望风险（expected risk）或期望损失（expected loss）。显然地，我们需要求解：

$$ \begin{aligned} \min \ & \mathcal{L}(\boldsymbol{\theta}) \\ where:\ & \boldsymbol{\theta}\in\boldsymbol{\Theta} \end{aligned}\tag{2} $$

问题（2）的最优解即为：$\boldsymbol{\theta}^*_E=\text{argmin}_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}\mathcal L(\boldsymbol{\theta})$（$E$表示它是期望风险最小化的解），最优值为：$\mathcal L(\boldsymbol{\theta}^*_E)$，对应的模型为：$f(\boldsymbol{x};\boldsymbol{\theta}^*_E)$。
  但在绝大多数情况下，概率分布$\boldsymbol{P}$是不可知的，因此在实践中我们往往寻求期望风险的一个估计。在监督学习中，我们从空间$\mathcal{X}$中采样获得一组独立同分布样本：集合$\boldsymbol{X}=\{\boldsymbol{x}_i\}_{i=1}^N$，$\boldsymbol{X}$在映射$F$下的像为$\boldsymbol{Y}$，则称集合$\boldsymbol{T}=\{(\boldsymbol{x}_1,\boldsymbol{y}_1),\cdots,(\boldsymbol{x}_N,\boldsymbol{y}_N)\}$为训练集。我们称训练集上所有损失的均值：

$$ \mathcal{L}(\boldsymbol{\theta};\boldsymbol{T})=\frac 1N \sum_{i=1}^N L(\boldsymbol{\hat y}_i, \boldsymbol{y}_i)\tag{3} $$

为经验风险（empirical risk）。如下问题：

$$ \begin{aligned} \min \ & \mathcal{L}(\boldsymbol{\theta};\boldsymbol{T}) \\ where:\ & \boldsymbol{\theta}\in\boldsymbol{\Theta} \end{aligned}\tag{4} $$

称为经验风险最小化（Empirical Risk Minimization，ERM）问题。其最优解为：$\boldsymbol{\theta}^*=\text{argmin}_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}\mathcal L(\boldsymbol{\theta};\boldsymbol{T})$，最优值为：$\mathcal{L}(\boldsymbol{\theta}^*;\boldsymbol{T})$，对应的模型为：$f(\boldsymbol{x};\boldsymbol{\theta}^*)$，以下简记为$f^*$。
  一般地，参数空间$\boldsymbol{\Theta}$即为$\mathbb{R}^{P(f)}$，其中$P(f)$即为$f$的总体参数量也即$\boldsymbol{\theta}$的维度。所以（2）与（4）都可以看做是一个无约束优化问题，往往精确地、解析地求解是不可能的，我们采用迭代的方式即：

$$ \boldsymbol{\theta}^{(\tau+1)}=\boldsymbol{\theta}^{(\tau)}+\eta^{(\tau)}\cdot \boldsymbol{d}^{(\tau)}\tag{5} $$

其中$\tau=0,1,\cdots$称为迭代数，$\boldsymbol{\theta}^{(\tau)}$为$\tau$时刻的模型参数，特别地$\boldsymbol{\theta}^{(0)}$称为初始参数。正数$\eta^{(\tau)}\in\mathbb{R}$称为步长，$\boldsymbol{d}^{(\tau)}\in\mathbb R^{P(f)}$称为方向。

Vanilla Gradient Descent

  根据凸优化的知识我们很自然地想到，若$\mathcal{L}$是可微的，则可以取方向为负梯度方向：

$$ \boldsymbol{d}^{(\tau)}=-\nabla_{\boldsymbol{\theta}} \mathcal{L}\left(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}\right)=-\frac 1N\sum_{i=1}^N \nabla_{\boldsymbol{\theta}} L\left(\boldsymbol{\hat y}_i^{(\tau)} ,\boldsymbol{y}_i^{(\tau)}\right) \tag{6} $$

结合（5）（6），我们即得出了求解问题（4）的一个算法：梯度下降法：

定义2：Vanilla Gradient Descent

$$ {\boldsymbol{\theta}^{(\tau+1)}=\boldsymbol{\theta}^{(\tau)}-\eta^{(\tau)} \cdot \nabla_{\boldsymbol{\theta}} \mathcal{L}\left(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}\right)}\tag{7} $$

GD的理论分析

  显然地，Vanilla Gradient Descent只能来求解经验风险最小化的问题。那么现在我们已经有了求解（4）的一个算法，（7）在迭代过程中产生了一个序列：$\{\mathcal{L}(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \}$，于是自然地我们想探求它是否收敛？收敛速度如何？
  对于一个优化算法，如果不对数据与问题做任何假设，那么理论分析是很困难的。我们往往在各种假设下分析其理论性质。最好研究的即是Lipschitz光滑性与凸性（凸、强凸）。这两者的定义与性质我们已经在：

一文中介绍过了。
  同时，规定$\|\cdot\|$为标准内积诱导的2范数，序列$\{\|\mathcal{L}(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\mathcal{L}(\boldsymbol{\theta}^* ; \boldsymbol{T})\| \}$、$\{\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\| \}$、$\{\|\nabla\mathcal{L}(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})\| \}$是递减的。此外我们有如下定义：

定义3：$\epsilon$-次优解集与$\tau(\epsilon)$

  设有一给定的正数：$\epsilon>0$，所有满足：

$$ \|\mathcal L(\boldsymbol{\theta} ; \boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T}) \|\leq\epsilon $$

的解的集合记为$\epsilon$-次优解集：$\boldsymbol{\Theta}_\epsilon$。记$\boldsymbol{\Theta}_\epsilon$中所有解的迭代次数的最小值为：$\tau(\epsilon)$。它有一个下界，可用$\Omega$符号刻画。

定义4：$\tau$-精度

  给定一迭代次数：$\tau\geq 0$，定义：

$$ \epsilon(\tau)=\|\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T}) \| $$

称为$\tau$-精度。它有一个上界，可用$O$符号刻画。

定义5：$\epsilon$-稳定解集

  设有一给定的正数：$\epsilon>0$，所有满足：

$$ \|\nabla\mathcal L(\boldsymbol{\theta} ; \boldsymbol{T})\|\leq\epsilon $$

的解的集合记为$\epsilon$-稳定解集：$\boldsymbol{\Theta}_\epsilon^S$（$S$表示Stable）。记$\boldsymbol{\Theta}_\epsilon^S$中所有解的迭代次数的最小值为：$\tau_S(\epsilon)$。它有一个下界，可用$\Omega$符号刻画。

  同时在（7）两边同时减去$\boldsymbol{\theta}$再平方我们有以下结论：

定理1：

  对于任意的$\boldsymbol{\theta}\in\boldsymbol{\Theta}$，有：

$$ \|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}\|^2=\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}\|^2-2\eta^{(\tau)}\left\langle \nabla\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}),\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta} \right\rangle+\left(\eta^{(\tau)}\right)^2\|\nabla\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\tag{8} $$

  接下来，开始我们的排列组合吧！

L-光滑情况

  我们先假设$\mathcal L$是Lipschitz光滑的，也即：

$$ \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau_1)} ; \boldsymbol{T})-\nabla \mathcal L(\boldsymbol{\theta}^{(\tau_2)} ; \boldsymbol{T}) \|\leq L\|\boldsymbol{\theta}^{(\tau_1)}-\boldsymbol{\theta}^{(\tau_2)} \|\tag{9} $$

此时我们可以得到一个结论：

定理2：

  若（7）式中$\mathcal L$是$L$-光滑的，且$\eta^{(\tau)}\leq 1/L$则：

$$ \mathcal L(\boldsymbol{\theta}^{(\tau+1)} ; \boldsymbol{T})\leq \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\frac{1}{2L} \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\tag{10} $$

证明：

$$ \begin{align} \mathcal L(\boldsymbol{\theta}^{(\tau+1)} ; \boldsymbol{T})&\leq \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})+\left\langle \nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}), \boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^{(\tau)}\right\rangle+\frac L2 \|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^{(\tau)} \|^2\tag{10.1}\\ &=\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\eta^{(\tau)}\cdot\|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2+\frac{L\left(\eta^{(\tau)} \right)^2}{2}\| \nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\tag{10.2}\\ &\leq\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\frac{\eta^{(\tau)}}{2} \| \nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2 \tag{10.3}\\ &\leq\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\frac{1}{2L} \| \nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\tag{10} \end{align} $$

其中，（10.1）式由凸性、强凸性与L-光滑定理5（b）可得，将（7）式代入（10.1）得（10.2）式，再代入$\eta^{(\tau)}\leq 1/L$即得证。注意后两个不等号都在$\eta^{(\tau)}=1/L$时取等。

1.非凸情况

  若$\mathcal L$是光滑的但非凸的，此时关于最优解与最优值的$\tau(\epsilon),\epsilon(\tau)$都不好研究，我们只能来研究$\epsilon$-稳定解，我们能用的只有$L$-光滑这一个条件，我们能得到什么结论呢？

  若$\mathcal L$是$L$-光滑但非凸的，令步长固定且小于等于$1/L$，则达到$\epsilon$-稳定：$\|\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T}) |\leq \epsilon$所需的最小步数$\tau_S(\epsilon)$有：$\tau_S(\epsilon)=\Omega(\frac 1 {\epsilon^2})$，精确地：

$$ \tau_S(\epsilon)\geq \frac{2L[\mathcal L(\boldsymbol{\theta}^{(0)};\boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T})]}{\epsilon^2}-1\tag{11} $$

证明：
  由（10）式：

$$ \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})- \mathcal L(\boldsymbol{\theta}^{(\tau+1)} ; \boldsymbol{T})\geq \frac{1}{2L} \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2 $$

设有迭代数：$\tau=0,\cdots,\tau_S(\epsilon)$，则对上式两边求和得：

$$ \mathcal L(\boldsymbol{\theta}^{(0)};\boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T})\geq \mathcal L(\boldsymbol{\theta}^{(0)};\boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^{(\tau_S(\epsilon))};\boldsymbol{T})\geq\frac {1}{2L}\sum_{\tau=0}^{\tau_S(\epsilon)} \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2 $$

由于我们假定了$\{\|\nabla\mathcal{L}(\boldsymbol{\theta}^{(\tau)};\boldsymbol{T})\| \}$是递减的，所以：

$$ \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau_S(\epsilon))};\boldsymbol{T}) \|\leq \sqrt{\frac{2L[\mathcal L(\boldsymbol{\theta}^{(0)};\boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T})]}{\tau_S(\epsilon)+1}}\leq \epsilon $$

整理则式（11）得证。

2.凸

  若$\mathcal L$是$L$-光滑且是凸的，令步长固定且小于等于$1/L$，则迭代数为$\tau$时的$\tau$-精度有：

$$ \epsilon(\tau)=\|\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T}) \|\leq \frac{L\|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^*\|^2}{2\tau}=O(\frac{1}{\tau})\tag{12} $$

证明：
  由（10）式：

$$ \underbrace{[\mathcal L(\boldsymbol{\theta}^{(\tau+1)} ; \boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T})]}_{\epsilon(\tau+1)}- \underbrace{[\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T})]}_{\epsilon(\tau)}\leq -\frac{1}{2L} \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\tag{13} $$

  此外，由定理1（8）式知：

$$ \|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}\|^2=\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}\|^2-2\eta^{(\tau)}\left\langle \nabla\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}),\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta} \right\rangle+\left(\eta^{(\tau)}\right)^2\|\nabla\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\tag{14} $$

取：$\boldsymbol{\theta}=\boldsymbol{\theta}^*\in\boldsymbol{\Theta}$，同时由于$\mathcal L$是凸函数，应用凸优化二：凸函数定义2.1.1.3知：

$$ \mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T})\geq \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})+\left\langle \nabla\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}),\boldsymbol{\theta}^*-\boldsymbol{\theta}^{(\tau)} \right\rangle\tag{15} $$

所以：

$$ \begin{align} \epsilon(\tau)=\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})-\mathcal L(\boldsymbol{\theta}^* ; \boldsymbol{T}) &\leq \left\langle \nabla\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}),\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \right\rangle\\ &= \frac{1}{2\eta^{(\tau)}}(\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2 -\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^*\|^2)+ \frac{\eta^{(\tau)}}{2} \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2 \tag{16.1}\\ &\leq \frac{1}{2\eta^{(\tau)}}(\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2 -\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^*\|^2)+ \frac{1}{2L} \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2 \tag{16.2}\\ \tag{16} \end{align} $$

我们将（13）与（16.2）相加，则：

$$ \epsilon(\tau+1)\leq\frac{L}{2}(\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2 -\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^*\|^2)\tag{17} $$

又是两个迭代式相减，所以立刻有：

$$ \sum_{k=0}^{\tau-1} \epsilon(k+1)=\frac{L}{2}(\|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^*\|^2 -\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2)\leq \frac{L}{2} \|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^*\|^2 $$

同时，我们有：

$$ \tau\cdot \epsilon(\tau)\leq\sum_{k=0}^{\tau-1} \epsilon(k+1)\leq\frac{L}{2} \|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^*\|^2\tag{18} $$

所以（12）式得证。
  注意到$\mathcal L$是$L$-光滑的，则由凸性、强凸性与L-光滑定理7知：

$$ \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\leq 2L\cdot\epsilon(\tau) $$

所以：

$$ \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|\leq \sqrt{\frac{L^2 \|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^*\|^2}{\tau}} $$

也即：$\tau_S(\epsilon)=\Omega(\frac{1}{\epsilon^2})$。同时，由（12）式立刻有：$\tau(\epsilon)=\Omega(\frac 1\epsilon)$。

3.强凸

  若$\mathcal L$是$L$-光滑且是$\mu$-强凸的，设其条件数为：$\kappa=L/\mu>1$，令步长固定且小于等于$1/L$，则：

$$ \begin{align} &\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^*\|^2<\left(1-\frac 1\kappa \right)\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2<\left(1-\frac 1\kappa\right)^{\tau+1}\|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^*\|^2 \tag{19}\\ &\epsilon(\tau+1)\leq \left(1-\frac 1\kappa \right)\epsilon(\tau)\leq \left(1-\frac 1\kappa \right)^{\tau + 1}\epsilon(0)\tag{20}\\ \end{align} $$

证明：
  由$\mathcal L$是$\mu$-强凸的，由凸性、强凸性与L-光滑定理4（b）可得：

$$ \epsilon(\tau)\leq -\left\langle \nabla\mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}),\boldsymbol{\theta}^*-\boldsymbol{\theta}^{(\tau)} \right\rangle-\frac{\mu}{2}\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^* \|^2\tag{21} $$

类似于我们在凸函数情况中的讨论，则：

$$ \epsilon(\tau) \leq \frac{L-\mu}{2}\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2 - \frac{L}{2}\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^*\|^2+ \frac{1}{2L} \|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}) \|^2\tag{22} $$

再与（13）相加，则：

$$ \epsilon(\tau+1) \leq \frac{L-\mu}{2}\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2 - \frac{L}{2}\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^*\|^2\tag{23} $$

由于$\epsilon(\tau+1)\geq0$所以：

$$ \|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^*\|^2\leq\left(1-\frac 1\kappa \right)\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^*\|^2\leq\left(1-\frac 1\kappa\right)^{\tau+1}\|\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^*\|^2 \tag{24} $$

这便是（19）式。此外，由凸性、强凸性与L-光滑定理7，结合（13）式：

$$ \epsilon(\tau+1)\leq \left(1-\frac 1\kappa \right)\epsilon(\tau)\leq \left(1-\frac 1\kappa \right)^{\tau + 1}\epsilon(0)\tag{25} $$

这便是（20）式。
  显然由（19）式我们知道此时是线性收敛的，而由（20）式，$\epsilon(\tau)=O\left((1-\kappa^{-1})^\tau \right)$，相应的，$\tau(\epsilon)=\Omega((\log \frac{1}{\epsilon})/\log \frac{\kappa}{\kappa-1})$。由于当$\kappa$较大时$\log \frac{\kappa}{\kappa -1}\approx \kappa^{-1}$，故而有的资料上也会将上述结论写做：$\epsilon(\tau)=O\left(e^{\tau/\kappa} \right),\tau(\epsilon)=\Omega(\kappa\log \frac{1}{\epsilon})$。

4.小结

  我们已经研究了$L$-光滑情况下在非凸、凸、强凸时的收敛性能，总结如下：

其他条件

  我们在上一部分中使用了$L$-光滑性假设与凸性来研究收敛性能，事实上这是一个比较强的条件。我们可以选取其他条件进行分析。例如：

$$ \left\langle\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T}), \boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}\right\rangle \geq \frac{\mu}{2}\left\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}\right\|_{2}^{2}+\frac{1}{2 L}\|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)} ; \boldsymbol{T})\|_{2}^{2}\tag{26} $$

这被称为Regularity Condition（RL条件）。乍一看好像是Lipschitz光滑+强凸的组合，事实上RL条件也确实是一个比Lipschitz光滑+强凸更弱的条件：

$$ \begin{aligned} 0 & \leq \mathcal L\left(\boldsymbol{\theta}^{+};\boldsymbol{T}\right)-\mathcal L\left(\boldsymbol{\theta}^{*};\boldsymbol{T}\right)=\mathcal L\left(\boldsymbol{\theta}^{+};\boldsymbol{T}\right)-\mathcal L(\boldsymbol{\theta};\boldsymbol{T})+\mathcal L(\boldsymbol{\theta};\boldsymbol{T})-\mathcal L\left(\boldsymbol{\theta}^{*};\boldsymbol{T}\right) \\ & \leq \underbrace{\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})^{\top}\left(\boldsymbol{\theta}^{+}-\boldsymbol{\theta}\right)+\frac{L}{2}\left\|\boldsymbol{\theta}^{+}-\boldsymbol{\theta}\right\|_{2}^{2}}_{\text {L-smoothness }}+\underbrace{\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})^{\top}\left(\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right)-\frac{\mu}{2}\left\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right\|_{2}^{2}}_{\text {strong convex }} \\ &=\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})^{\top}\left(\boldsymbol{\theta}^{+}-\boldsymbol{\theta}^{*}\right)+\frac{1}{2 L}\left\|\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})\right\|_{2}^{2}-\frac{\mu}{2}\left\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right\|_{2}^{2}\\ &=\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})^{\top}\left(\boldsymbol{\theta}^{+}-\boldsymbol{\theta}+\boldsymbol{\theta} -\boldsymbol{\theta}^{*}\right)+\frac{1}{2 L}\left\|\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})\right\|_{2}^{2}-\frac{\mu}{2}\left\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right\|_{2}^{2}\\ &=\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})^{\top}\left(\boldsymbol{\theta} -\boldsymbol{\theta}^{*}\right)-\frac{1}{2 L}\left\|\nabla \mathcal L(\boldsymbol{\theta};\boldsymbol{T})\right\|_{2}^{2}-\frac{\mu}{2}\left\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right\|_{2}^{2} \end{aligned} $$

  那么我们根据RL条件能否得出与Lipschitz光滑+强凸相同的结论呢？我们有：

$$ \begin{aligned} \left\|\boldsymbol{\theta}^{(\tau+1)}-\boldsymbol{\theta}^{*}\right\|_{2}^{2} &=\left\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}-\frac{1}{L} \nabla \mathcal L\left(\boldsymbol{\theta}^{(\tau)};\boldsymbol{T}\right)\right\|_{2}^{2} \\ &=\left\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}\right\|_{2}^{2}+\frac{1}{L^{2}}\left\|\nabla \mathcal L\left(\boldsymbol{\theta}^{(\tau)};\boldsymbol{T}\right)\right\|_{2}^{2}-\frac{2}{L}\left\langle\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}, \nabla \mathcal L\left(\boldsymbol{\theta}^{(\tau)};\boldsymbol{T}\right)\right\rangle \\ & \leq \left\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}\right\|_{2}^{2}-\frac{\mu}{L}\left\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}\right\|_{2}^{2} \\ &=\left(1-\frac{\mu}{L}\right)\left\|\boldsymbol{\theta}^{(\tau)}-\boldsymbol{\theta}^{*}\right\|_{2}^{2} \end{aligned} $$

其中第一步为取$\eta^{(\tau)}=1/L$，第三步则为代入RL条件。显然此时算法也是线性收敛的。

  此外还有很多很多玩法，比如动态调整步长、$\mathcal L$满足不同的性质、给定不同的条件等等，在这里就不赘述了。

References

1. Lectures on Convex Optimization，Yurii Nesterov
2. 不同条件下梯度方法的收敛性分析1
3. 梯度下降在强凸/凸/非凸下的收敛速率证明
4. 无约束梯度下降(Unconstrained)
5. Convergence Theorems for Gradient Descen