机器学习笔记值优化算法(十四)梯度下降法在凸函数上的收敛性

引言

本节将介绍梯度下降法在凸函数上的收敛性。

回顾：

收敛速度：次线性收敛

关于次线性收敛，分为两种判别类型：$\mathcal{R}$-次线性收敛与$\mathcal{Q}$-次线性收敛。而次线性收敛的特点是：随着迭代次数的增加，相邻迭代步骤产生的目标函数结果$f(x_k),f(x_{k+1})$，其差异性几乎完全相同：
$$\underset{k\Rightarrow \infty }{\lim }\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}=1$$
例如：如果数值解$x_k$的目标函数结果$f(x_k)$与目标函数最优解$f^{\ast }$之间的差异性$||f(x_k)-f^{\ast }||$与迭代次数$k$存在如下函数关系$\mathcal{G}(k)$：
$$||f(x_k)-f^{\ast }||\le \mathcal{G}(k)=\frac{1}{k}$$
当$k$充分大时，$f(x_k),f(x_{k+1})$与$f^{\ast }$之间差异性的比值表示如下：
$$\underset{k\Rightarrow \infty }{\lim }\frac{||f(x_{k+1})-f^{\ast }||}{||f(x_k)-f^{\ast }||}=\underset{k\Rightarrow \infty }{\lim }\frac{k}{k+1}=1$$
也就是说：虽然随着$k$的增加，$f(x_k)$在减小;但相邻迭代结果$f(x_k),f(x_{k+1})$之间的差异性几乎可以忽略不计。那么称这种收敛速度为次线性收敛。
准确的说，是$\Rightarrow 0$的次线性收敛：
lim ⁡ k ⇒ ∞ { f ( x k ) } ⇒ lim ⁡ k ⇒ ∞ G ( k ) = 0 \mathop{\lim}\limits_{k \Rightarrow \infty} \{f(x_k)\} \Rightarrow \mathop{\lim}\limits_{k \Rightarrow \infty} \mathcal G(k) = 0 k⇒∞lim​{f(xk​)}⇒k⇒∞lim​G(k)=0

二次上界引理

关于二次上界引理的描述表示如下：如果函数$f(\cdot )$可微，并对应梯度函数$\nabla f(\cdot )$满足利普希兹连续，则函数$f(\cdot )$存在二次上界。即：
$$\forall x,y\in {\mathbb{R}}^n\Rightarrow f(y)\le f(x)+[\nabla f(x){]}^T(y-x)+\frac{\mathcal{L}}{2}||y-x|{|}^2$$
而二次上界引理的作用是：可以通过该引理，得到最优步长上界的最小值：

• 假设$x$固定，令$\begin{array}{r}\varphi (y)=f(x)+[\nabla f(x){]}^T(y-x)+\frac{\mathcal{L}}{2}||y-x|{|}^2\end{array}$，通过选择合适的$y_{min}$，使$\varphi (y)$达到最小值：
  $$y_{min}=\underset{y\in {\mathbb{R}}^n}{\mathrm{argmin}}\varphi (y)$$
• 令$\nabla \varphi (y)\triangleq 0$，有：
  $$y_{min}=x+\frac{1}{\mathcal{L}}\cdot [-\nabla f(x)]$$
• 其中$-\nabla f(x)$即${\mathcal{P}}_k$，也就是最速下降方向；而$\begin{array}{r}\frac{1}{\mathcal{L}}\end{array}$则是最优步长的上确界：
  $$f(y)\le \varphi (y_{min})=\underset{y\in {\mathbb{R}}^n}{\min }\varphi (y)$$
  也就是说：
  • 在没有二次上界引理的约束下，步长${\alpha }_k$的选择在其定义域内没有约束：$(0,+\infty )$；
  • 经过二次上界引理的约束后，步长${\alpha }_k$的选择从原始的$(0,+\infty )$约束至$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$。

延伸：关于区间$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$可以模糊地认为满足$\text{Armijo}$准则。关于步长变量$\alpha$的函数$\varphi (\alpha )=f(x_{k+1})$中，当$\alpha \in \begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$时，等价于：存在一条直线$\mathcal{L}(\alpha )$，以该直线作为划分边界对应$\alpha$的范围正好是$\begin{array}{r}\left(0,\frac{1}{\mathcal{L}}\right]\end{array}$：
吐槽：实际上用这张图是不太合理的，因为下面的图对应的$f(\cdot )$更加复杂，二次上界约束的范围仅仅在下面$\alpha$轴的绿色实线部分，但很明显，在该函数中，存在更优质的$\alpha$结果。

梯度下降法在凸函数上的收敛性

收敛性定理介绍

梯度下降法在凸函数上的收敛性定理表示如下：

• 条件：
  • 函数$f(\cdot )$向下有界，在定义域内可微，并且$f(\cdot )$是凸函数；
  • 关于$f(\cdot )$的梯度函数$\nabla f(\cdot )$满足利普希兹连续；
  • 梯度下降法迭代过程中步长${\alpha }_k(k=1,2,3,\cdots )$有明确的约束范围：$\begin{array}{r}{\alpha }_k\in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$；
• 结论：数值解序列 { 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∞​以$\begin{array}{r}\mathcal{O}\left(\frac{1}{k}\right)\end{array}$收敛于目标函数最优解$f^{\ast }$。
  其中$\begin{array}{r}\mathcal{O}\left(\frac{1}{k}\right)\end{array}$表示以$\begin{array}{r}\mathcal{G}(k)=\mathcal{C}\cdot \frac{1}{k}\end{array}$的次线性收敛级别的收敛速度($\mathcal{C}$为常数)。

证明过程

根据二次上界引理，依然将$x$设为上一次迭代的数值解$x_{i-1}$，对应的$y$为当前迭代步骤的数值解$x_i$。由于是梯度下降法，因而在线搜索方法的基础上，将方向${\mathcal{P}}_i$表示为最速下降方向$\nabla f(x_{i-1})$步长依然使用步长变量$\alpha$进行表示：
$$y-x=x_i-x_{i-1}=-\nabla f(x_{i-1})\cdot \alpha$$
将二次上界不等式进行相应替换：
将上式代入~
$$f(x_i)\le f(x_{i-1})+[\nabla f(x_{i-1}){]}^T[-\nabla f(x_{i-1})\cdot \alpha ]+\frac{\mathcal{L}}{2}||-\nabla f(x_{i-1})\cdot \alpha |{|}^2$$
观察不等式右侧，可以继续化简：

• 将内积写作$||\cdot |{|}^2$的形式。
• $||-\nabla f(x_{i-1})\cdot \alpha |{|}^2=||\nabla f(x_{i-1})\cdot \alpha |{|}^2$,这里消掉一个负号;
• 由于$\begin{array}{r}\alpha \in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$,是一个标量，直接将其提到范数外侧。
  $${\mathcal{I}}_{right}=f(x_{i-1})-\alpha \cdot ||\nabla f(x_{i-1})|{|}^2+\frac{\mathcal{L}}{2}\cdot {\alpha }^2\cdot ||\nabla f(x_{i-1})|{|}^2$$

由$\begin{array}{r}\alpha \le \frac{1}{\mathcal{L}}\end{array}$可知：$\begin{array}{r}\mathcal{L}\le \frac{1}{\alpha }\end{array}$。将该式代入到上式中：
消掉分母中的$\alpha$，并于前面的项结合。
$$\begin{array}{rl}{\mathcal{I}}_{right}& \le f(x_{i-1})-\alpha \cdot ||\nabla f(x_{i-1})|{|}^2+\frac{1}{2\alpha }\cdot {\alpha }^2\cdot ||\nabla f(x_{i-1})|{|}^2\\ & =f(x_{i-1})-\frac{\alpha }{2}\cdot ||\nabla f(x_{i-1})|{|}^2\end{array}$$
基于梯度下降法，使用二次上界引理，可以得到$f(x_{i-1})$与$f(x_i)$之间存在如下关联关系：
$$f(x_i)\le f(x_{i-1})-\frac{\alpha }{2}\cdot ||\nabla f(x_{i-1})|{|}^{2}i=1,2,3,\cdots$$
根据凸函数的性质，必然有：函数$f(\cdot )$任一位置的切线，$f(\cdot )$均在该切线上方。见下图：
由于条件:$f(\cdot )$向下有界,因此，该函数必然’开口向上‘。

其中红色点$(x^{\ast },f^{\ast })$表示最优点，以上一次迭代产生的$x_{i-1}$为切点做一条切线，必然有$x^{\ast }$在该切线函数上的函数值$f^{\prime }\le f^{\ast }$。$f^{\prime }$表示如下：
$$f^{\prime }=f(x_{i-1})-[\nabla f(x_{i-1}){]}^T(x_{i-1}-x^{\ast })\le f^{\ast }$$
移项，从而有：
$$f(x_{i-1})\le f^{\ast }+[\nabla f(x_{i-1}){]}^T(x_{i-1}-x^{\ast })$$
将上式代入，有：
$${\mathcal{I}}_{right}\le \underset{替换f(x_{i-1})}{\underbrace{f^{\ast }+[\nabla f(x_{i-1}){]}^T(x_{i-1}-x^{\ast })}}-\frac{\alpha }{2}\cdot ||\nabla f(x_{i-1})|{|}^2$$
为了凑平方项，将上式调整至如下形式：
将$\begin{array}{r}-\frac{\alpha }{2}\end{array}$凑出${\alpha }^2$,其他项跟随变化。
$${\mathcal{I}}_{right}\le -\frac{1}{2\alpha }\left\{{\alpha }^2||\nabla f(x_{i-1})|{|}^2-2\alpha \cdot [\nabla f(x_{i-1}){]}^T(x_{i-1}-x^{\ast })\right\}$$
对大括号内的项进行配方：
$$\begin{array}{rl}{\mathcal{I}}_{right}& \le f^{\ast }-\frac{1}{2\alpha }\left\{\underset{平方项}{\underbrace{{\alpha }^2||\nabla f(x_{i-1})|{|}^2-2\alpha \cdot [\nabla f(x_{i-1}){]}^T(x_{i-1}-x^{\ast })+||x_{i-1}-x^{\ast }|{|}^2}}-||x_{i-1}-x^{\ast }|{|}^2\right\}\\ & =f^{\ast }-\frac{1}{2\alpha }\left[||\alpha \cdot \nabla f(x_{i-1})-(x_{i-1}-x^{\ast })|{|}^2-||x_{i-1}-x^{\ast }|{|}^2\right]\end{array}$$
观察中括号内第一项：$||\alpha \cdot \nabla f(x_{i-1})-(x_{i-1}-x^{\ast })|{|}^2$，由于是范数的平方项，因而在范数内部添加一个负号不会影响其值的变化：
$$||\alpha \cdot \nabla f(x_{i-1})-(x_{i-1}-x^{\ast })|{|}^2=||x_{i-1}-\alpha \cdot \nabla f(x_{i-1})-x^{\ast }|{|}^2$$
从迭代角度观察：$x_{i-1}-\alpha \cdot \nabla f(x_{i-1})=x_i$，从而上式可继续化简为：
提一个负号，调换一下位置。
$$\{\begin{array}{l}||\alpha \cdot \nabla f(x_{i-1})-(x_{i-1}-x^{\ast })|{|}^2=||x_i-x^{\ast }|{|}^2\\ \\ \begin{array}{rl}{\mathcal{I}}_{right}& \le f^{\ast }-\frac{1}{2\alpha }\left[||x_i-x^{\ast }|{|}^2-||x_{i-1}-x^{\ast }|{|}^2\right]\\ & =f^{\ast }+\frac{1}{2\alpha }\left[||x_{i-1}-x^{\ast }|{|}^2-||x_i-x^{\ast }|{|}^2\right]\end{array}\end{array}$$

至此，可以得到如下不等式结果：
$$f(x_i)-f^{\ast }\le \frac{1}{2\alpha }(||x_{i-1}-x^{\ast }|{|}^2-||x_i-x^{\ast }|{|}^2)$$
观察：不等式左侧描述的意义是：当前迭代步骤的目标函数结果$f(x_i)$与最优解$f^{\ast }$之间的偏差。从初始化数值解$x_0$开始，我们会得到一系列的不等式结果：
$$\{\begin{array}{l}\begin{array}{rl}f(x_1)-f^{\ast }& \le \frac{1}{2\alpha }(||x_0-x^{\ast }|{|}^2-||x_1-x^{\ast }|{|}^2)\\ f(x_2)-f^{\ast }& \le \frac{1}{2\alpha }(||x_1-x^{\ast }|{|}^2-||x_2-x^{\ast }|{|}^2)\\ & ⋮\\ f(x_k)-f^{\ast }& \le \frac{1}{2\alpha }(||x_{k-1}-x^{\ast }|{|}^2-||x_k-x^{\ast }|{|}^2)\end{array}\end{array}$$
将这些不等式对应位置相加，有：

• 等式右侧的中间项都被消掉了~
• 因为$||x_k-x^{\ast }|{|}^2\ge 0$恒成立，从而消掉含变量的项。
  $$\sum _{i=1}^k[f(x_i)-f^{\ast }]\le \frac{1}{2\alpha }(|||x_0-x^{\ast }|{|}^2-||x_k-x^{\ast }|{|}^2)\le \frac{1}{2\alpha }||x_0-x^{\ast }|{|}^2$$

关于我们要证的$||f(x_k)-f^{\ast }||$，可以表示为如下形式：

• 由于优化问题的收敛性，必然有：$f(x_k)\le f(x_{k-1})\le \cdots \le f(x_1)$,从而每一项:$||f(x_k)-f^{\ast }||\le ||f(x_{k-1})-f^{\ast }||\le \cdots \le ||f(x_1)-f^{\ast }||$,从而有:$\begin{array}{r}\sum _{i=1}^k[f(x_k)-f^{\ast }]\le \sum _{i=1}^k[f(x_i)-f^{\ast }]\end{array}$。
• 将上式结果带入~

$$f(x_k)-f^{\ast }=\frac{1}{k}\sum _{i=1}^k[f(x_k)-f^{\ast }]\le \frac{1}{k}\sum _{i=1}^k[f(x_i)-f^{\ast }]\le \frac{1}{k}\left[\frac{1}{2\alpha }||x_0-x^{\ast }|{|}^2\right]$$

观察：$\begin{array}{r}\left[\frac{1}{2\alpha }||x_0-x^{\ast }|{|}^2\right]\end{array}$中$\begin{array}{r}\alpha \in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$，$x_0,x^{\ast }$都是确定的常数，因而该项可视作常数$\mathcal{C}$。最终有：
$$f(x_k)-f^{\ast }\le \frac{1}{k}\cdot \mathcal{C}$$
我们可以令$\begin{array}{r}\mathcal{G}(k)=\frac{1}{k}\cdot \mathcal{C}\end{array}$，可以看出：它就是一个级别为$\begin{array}{r}\frac{1}{k}\end{array}$的次线性收敛。

相关参考：
【优化算法】梯度下降法-凸函数的收敛性