机器学习笔记之优化算法(九)收敛速度的简单认识

引言

本节对收敛速度简单介绍。

收敛速度的判别标准

我们之前几节介绍了线搜索方法$(\text{Line Search Method})$，并从方向角度、步长角度描述了先搜索方法的迭代优化过程。关于针对目标函数$f(\mathcal{X})$优化的终极目标：$\underset{\mathcal{X}\in {\mathbb{R}}^n}{\min }f(\mathcal{X})$，我们希望通过一系列数值解 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​，使其对应的目标函数结果 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​收敛到最优值$f^{\ast }$：
也可以等价写作： { x k } k = 0 ∞ ⇒ x ∗ ; f ( x ∗ ) = f ∗ \{x_k\}_{k=0}^{\infty} \Rightarrow x^*;f(x^*) = f^* {xk​}k=0∞​⇒x∗;f(x∗)=f∗。其中$x^{\ast }$则表示迭代产生的最优数值解：$x^{\ast }=\underset{\mathcal{X}\in {\mathbb{R}}^n}{\mathrm{argmin}}f(\mathcal{X})$
{ f ( x k ) } k = 0 ∞ ⇒ f ∗ \{f(x_k)\}_{k=0}^{\infty} \Rightarrow f^* {f(xk​)}k=0∞​⇒f∗

本节将介绍两种关于收敛速度的判别标准：$\mathcal{Q}$-收敛速度与$\mathcal{R}$-收敛速度。

$\mathcal{Q}$-收敛速度

其中$\mathcal{Q}$-收敛速度中的$\mathcal{Q}$是指：$\text{Quotient}$，也就是除法中的商。该方式主要围绕迭代过程中数值解$x_k,x_{k+1}$与最优解$x^{\ast }$之间差异性的商值对收敛速度进行描述：

• 由于$x_k,x_{k+1},x^{\ast }$可能是$\in {\mathbb{R}}^n$的向量，因此关于差异性的描述使用范数进行表示。
• 而这个范数也可以理解为：数值解与最优解之间的距离，是一个正值。
  $$\underset{k\Rightarrow \infty }{\lim }\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}$$

在判断是否为$\mathcal{Q}$-收敛时，我们事先假定：

• $k$充分大——这意味着$x_k,x_{k+1}$都经过充分迭代产生的数值解，因而它们均无限趋近于$x^{\ast }$。也就是说：无论$||x_{k+1}-x^{\ast }||$还是$||x_k-x^{\ast }||$，它们都可视作无穷小量：
  $$\{\begin{array}{l}\underset{k\Rightarrow \infty }{\lim }||x_{k+1}-x^{\ast }||=0\\ \underset{k\Rightarrow \infty }{\lim }||x_k-x^{\ast }||=0\end{array}$$
• $x_k$与$f(x_k)$同理——这个意思并不是说$x_k$与$f(x_k)$可以进行相互替换，而是说在$\mathcal{Q}$-收敛中，$f(x_k)$与·$x_k$一样存在相同形式的定义：
  这两个定义在$\mathcal{Q}$-收敛中没有区别，针对具体情况都可以进行使用。
  $$\underset{k\Rightarrow \infty }{\lim }\frac{||f(x_{k+1})-f^{\ast }||}{||f(x_k)-f^{\ast }||}$$

我们根据收敛速度的强度由低到高介绍$4$种$\mathcal{Q}$-收敛：

• $\mathcal{Q}$-次线性收敛$(\text{Q-SubLinear Convergence})$，其定义用数学符号表示为：
  $$\underset{k\Rightarrow \infty }{\lim }\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}=1$$

• $\mathcal{Q}$-线性收敛$(\text{Q-Linear Convergence})$。对应数学符号表示为：
  $$\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}\le a\in (0,1)$$
  我们发现，与$\mathcal{Q}$-次线性收敛不同的是，它并没有加极限符号。并且：差异性的比值被$(0,1)$范围内的常数$a$限制着。例如：目标函数值集合 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​服从函数$\mathcal{G}(k)=2^{-k}$。其定义域内对应的函数图像表示如下：
  
  可以发现：随着$k\Rightarrow \infty$，可以得到最优解$f^{\ast }=0$，而对应的$\begin{array}{r}\frac{||f(x_{k+1})-f^{\ast }||}{||f(x_k)-f^{\ast }||}\end{array}$在图像中可表示为相邻红色直线之间的比值。这个比值的计算结果为：
  $$\frac{||f(x_{k+1})-f^{\ast }||}{||f(x_k)-f^{\ast }||}=\frac{2^{-(k+1)}-0}{2^{-k}-0}=\frac{1}{2}$$
  因此，由$\mathcal{G}(k)$表示的 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​是$\begin{array}{r}a=\frac{1}{2}\end{array}$的$\mathcal{Q}$-线性收敛。
  此处所谓线性是指：将 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​视作为误差序列。也就是说：随着迭代次数$k$的增加，误差信息$\mathcal{G}(k)$越来越小，最终减少到$0$。对误差取对数操作后，其结果$\log \mathcal{G}(k)$与$k$之间呈线性关系：
  这里关于$\log$取底数为$2$。
  $$\log \mathcal{G}(k)={\log }_2{2}^{-k}=-k$$
  当$a$取到极限$1$时，$\mathcal{Q}$-线性收敛会退化至$\mathcal{Q}$-次线性收敛；相反，当$a$取到极限$0$时，$\mathcal{Q}$-线性收敛会进化至$\mathcal{Q}$-超线性收敛。反过来说：

  • 为什么被称作$\mathcal{Q}$-次线性收敛是因为：相比$\mathcal{Q}$-线性收敛中相邻迭代产生的差异性比值能够明显地用$a\in (0,1)$描述出来；而$\mathcal{Q}$-次线性收敛中相邻迭代产生的差异性几乎完全相同，它们之间的差距可以忽略不计。从而才有：
    很明显，相比$\mathcal{Q}$-次线性收敛，$\mathcal{Q}$-线性收敛的差异性更明显，收敛的速度更快。
    $$\underset{k\Rightarrow \infty }{\lim }\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}=1$$
    例如：$\begin{array}{r}\mathcal{G}(k)=\frac{1}{k}\end{array}$就是一个明显的$\mathcal{Q}$-次线性收敛。其对应函数图像表示如下：
    很明显，相比上述的$\mathcal{G}(k)=2^{-k}$，随着迭代次数$k$的增加，相邻红色线比值的变化并不非常明显。
    
    其次通过计算比值也能观察到类似的效果：
    很明显，当充分迭代之后，此时$k$已经充分大，而$\begin{array}{r}\frac{k}{k+1}\end{array}$这样的收敛效果完全可以忽略不计。
    $$\underset{k\Rightarrow \infty }{\lim }\frac{||f(x_{k+1})-f^{\ast }||}{||f(x_k)-f^{\ast }||}=\underset{k\Rightarrow \infty }{\lim }\frac{\frac{1}{k+1}-0}{\frac{1}{k}-0}=\underset{k\Rightarrow \infty }{\lim }\frac{k}{k+1}=1$$

• 与$\mathcal{Q}$-次线性收敛相反，$\mathcal{Q}$-超线性收敛$(\text{Q-Superlinear Convergence})$的定义用数学符号表示为：
  这意味着相邻迭代次数之间差异性极大，使得$x_{k+1}$对应的差异性结果与$x_k$的差异性结果相比小到可以忽略不计，这里不再过多赘述。
  $$\underset{k\Rightarrow \infty }{\lim }\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}=0$$

• $\mathcal{Q}$-二次收敛$(\text{Q-Quadratic Convergence})$的定义用数学符号表示为：

  • 同理，如$\mathcal{Q}$-三次收敛$(\text{Cubic Convergence})$等等，仅与分母中的指数项相关。
  • 相比于线性收敛中$a\in (0,1)$，我们在$\mathcal{Q}$-二次收敛中不会更多计较$a$的范围，因为无穷小量的级别就可以说明其收敛速度。
    $$\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }|{|}^2}\le a\in (0,+\infty )$$

  与$\mathcal{Q}$-线性收敛的定义类似，也同样没有极限符号。由于$||x_k-x^{\ast }||$自身就是一个无穷小量，那么它的平方结果可理解为一个更高级别的无穷小量，反过来说明：如果$x_{k+1}$差异性所描述的无穷小量与$x_k$差异性的平方所描述的无穷小量是一个级别的话，那么它的收敛速度已经超越了线性范畴。

  例如：$\mathcal{G}(k)=2^{-2^k}$就是明显的$\mathcal{Q}$-二次收敛。其对应的函数图像表示如下：
  很明显，相比上面的收敛，它的收敛速度更快了，这里不再过多赘述。
  
  对应比值的计算结果是：
  $$\begin{array}{r}\frac{\mathcal{G}(k+1)-0}{[\mathcal{G}(k){]}^2}=\frac{2^{-2^{k+1}}}{[2^{-2^k}{]}^2}=1\in (0,+\infty )\end{array}$$

$\mathcal{R}$-收敛速度

其中$\mathcal{R}$-收敛速度中的$\mathcal{R}$是指：$\text{Root}$。关于假设条件与$\mathcal{Q}$-收敛速度相同，这里不再赘述：

• $k$充分大；
• $x_k$与$f(x_k)$共用相同概念。

关于$\mathcal{R}$-收敛速度定义的数学符号表示如下：
$$||x_k-x^{\ast }||\le t_k$$
其中$||x_k-x^{\ast }||$依然是数值解与最优解之间的差异性信息(距离范数)；该结果被另外一个序列 { t k } k = 0 ∞ \{t_k\}_{k=0}^{\infty} {tk​}k=0∞​限制住：

• 如果$t_k$是$\mathcal{Q}$-次线性/线性/超线性/二次收敛；
• 并且$\underset{k\Rightarrow \infty }{\lim }{t}_k=0$；
  这说明 { t k } k = 0 ∞ \{t_k\}_{k=0}^{\infty} {tk​}k=0∞​是一个 误差序列而不是数值解序列。上面的函数例子中，我们使用这些函数描述的是数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​或者 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​,但这里示例函数$\mathcal{G}(k)$最终都会收敛到$0$，因而也可以将其视作误差序列。

则称$x_k$是$\mathcal{R}$-次线性/线性/超线性/二次收敛。
可以看出：$\mathcal{Q}$与$\mathcal{R}$的区别在于：

• 关于差异性的描述：$\begin{array}{r}\mathcal{Q}\Rightarrow \frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }|{|}^p}(p=1,2,3,\cdots )\end{array}$与$\mathcal{R}\Rightarrow ||x_k-x^{\ast }||$
• 相比于$\mathcal{Q}$中使用具体值(0、1)或者范围$(0,1);(0,+\infty )$，$\mathcal{R}$则使用误差序列 { t k } k = 0 ∞ \{t_k\}_{k=0}^{\infty} {tk​}k=0∞​,并且每一个迭代步骤$k=0,1,2,\cdots$均被对应 { t k } k = 0 ∞ \{t_k\}_{k=0}^{\infty} {tk​}k=0∞​中的$t_0,t_1,t_2,\cdots$限制住。

之所以会定义$\mathcal{R}$-收敛速度，原因在于：一些情况下，$\mathcal{Q}$-收敛速度不容易求解，如果找到一组合适的 { t k } k = 0 ∞ \{t_k\}_{k=0}^{\infty} {tk​}k=0∞​，可以根据$t_k$的收敛速度，从而对$x_k$的收敛速度进行表达。例如：
$$||f(x_k)-f^{\ast }||\le \mathcal{G}(k)=\frac{1}{k}$$
我们已经知道：满足$\mathcal{G}(k)$的误差序列是$\mathcal{Q}$-次线性收敛，因而可以判断 { f ( x k ) } k = 0 ∞ \{f(x_k)\}_{k=0}^{\infty} {f(xk​)}k=0∞​是$\mathcal{R}-$次线性收敛。

关于算法复杂度与收敛速度

在真实情况下，我们不能任由算法无限迭代下去，即$k$不能无限大。因而我们会设置一些判断条件。例如：
这里$ϵ$表示描述限制条件的超参数。达到该条件，即可停止算法。
$$||f(x_k)-f^{\ast }||\le ϵ$$

• 如果依然以$\mathcal{Q}$-次线性收敛$\begin{array}{r}\frac{1}{k}\end{array}$为例，需要满足：
  $$||f(x_k)-f^{\ast }||\le \mathcal{G}(k)=\frac{1}{k}\le ϵ\Rightarrow k\ge \frac{1}{ϵ}$$
  可以看出：当$ϵ$越小时，迭代的次数$k$越大。
• 如果以$\mathcal{Q}$-线性收敛$2^{-k}$为例，需要满足：
  $$2^{-k}\le ϵ\Rightarrow k\ge {\log }_2\frac{1}{ϵ}$$

可以观察到：在$ϵ$很小的情况下，关于$\begin{array}{r}\frac{1}{ϵ}\end{array}$其量级远高于$\begin{array}{r}{\log }_2\frac{1}{ϵ}\end{array}$：
随着$\begin{array}{r}\frac{1}{ϵ}\end{array}$的增加,$\mathcal{Q}$-次线性收敛(蓝色直线)与$\mathcal{Q}$-线性收敛(橙色曲线)对应的函数结果相比，其对应函数值的增速明显更高，而更高意味着更多的迭代步骤。

因此，一般情况下，使用更高强度的收敛速度，那么他的迭代步骤就会减小，从而降低算法复杂度。

相关参考：
【优化算法】收敛速度简介
优化里的Q-linear Convergence和R-linear convergence是什么意思？