机器学习笔记之优化算法(十六)梯度下降法在强凸函数上的收敛性证明

引言

本节将介绍：梯度下降法在强凸函数上的收敛性，以及证明过程。

回顾：

凸函数与强凸函数

关于凸函数的定义使用数学符号表示如下：
$$\forall x_1,x_2\in {\mathbb{R}}^n,\forall \lambda \in (0,1)\Rightarrow f[\lambda \cdot x_2+(1-\lambda )\cdot x_1]\le \lambda \cdot f(x_2)+(1-\lambda )\cdot f(x_1)$$
很明显，这描述的是$f[\lambda \cdot x_2+(1-\lambda )\cdot x_1]$与$\lambda \cdot f(x_2)+(1-\lambda )\cdot f(x_1)$两个量之间的大小关系。以$x_1,x_2\in \mathbb{R}$为例，它们的大小关系在图像中表示如下：

观察公式，可以看出：作为凸函数的定义，两个量之间有机会取等。依然以$x_1,x_2\in \mathbb{R}$为例，两个量取等情况下的图像示例如下：
很明显，这是一个线性函数,对应的函数图像是一条直线。任选$x_1,x_2\in \mathbb{R}$,对应函数结果的连线内的任意一点都在该直线上。

类似地，关于强凸函数的定义使用数学符号表示如下：对于$\forall x_1,x_2\in {\mathbb{R}}^n,\forall \lambda \in (0,1),\exists m>0$，总有：
$$\lambda \cdot f(x_1)+(1-\lambda )\cdot f(x_2)\ge f[\lambda \cdot x_1+(1-\lambda )\cdot x_2]+\frac{m}{2}\cdot \lambda (1-\lambda )\cdot ||x_1-x_2|{|}^2$$
相比于凸函数的定义，强凸函数定义明显的特点是：两个量之间不仅不能取等，并且还要相差一个大小为$\begin{array}{r}\frac{m}{2}\cdot \lambda (1-\lambda )\cdot ||x_1-x_2|{|}^2\end{array}$的正值。

• 其中$m$表示描述强凸函数的参数，也被称作$m$-强凸函数。
• 这种定义的描述彻底杜绝了线性函数这种‘看起来不凸’的凸函数的情况。也就是说，强凸函数对于两个量之间的大小关系的约束更强了。

梯度下降法：凸函数上的收敛性分析

关于梯度下降法在凸函数上的收敛性描述表示如下：

• 条件：
  • 函数$f(\cdot )$向下有界，在其定义域内可微，并且$f(\cdot )$是凸函数；
  • 关于梯度函数$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续；
  • 在梯度下降法的迭代过程中，步长${\alpha }_k(k=1,2,3,\cdots )$存在明确的约束范围：$\begin{array}{r}{\alpha }_k\in \left(0,\frac{1}{\mathcal{L}}\right]\end{array}$；
    关于步长${\alpha }_k$约束范围的上界$\begin{array}{r}\frac{1}{\mathcal{L}}\end{array}$,详见二次上界引理，这里不再赘述。
• 结论：目标函数序列 { 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 }$。
  关于证明过程详见优化算法——梯度下降法在凸函数上的收敛性

关于白老爹定理的一些新的认识

在$\text{Baillon Haddad Theorem}$一节中介绍过：如果$f(\cdot )$在定义域内可微，并且是凸函数，而且$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续，那么必然有：函数$\begin{array}{r}\mathcal{G}(x)=\frac{\mathcal{L}}{2}{x}^{T}x-f(x)\end{array}$同样是凸函数。

虽然证明过程比较简单，但新的问题出现：为什么要设计$\mathcal{G}(x)$这样的函数$?$或者关于项$\begin{array}{r}\frac{\mathcal{L}}{2}{x}^{T}x\end{array}$产生的原因是什么$?$是否存在什么意义$?$

重新观察：$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续这个条件：
$$\forall x,y\in {\mathbb{R}}^n,\exists \mathcal{L}\Rightarrow ||\nabla f(x)-\nabla f(y)||\le \mathcal{L}\cdot ||x-y||$$
如果函数$f(\cdot )$在其定义域内二阶可微，根据拉格朗日中值定理，有：
其中$\mathcal{I}$表示单位矩阵。
$$\exists \xi \in (x,y)\Rightarrow \frac{||\nabla f(x)-\nabla f(y)||}{||x-y||}={\nabla }^{2}f(\xi )\preccurlyeq \mathcal{L}\cdot \mathcal{I}$$
最终整理，有：
$$\mathcal{L}\cdot \mathcal{I}-{\nabla }^{2}f(\xi )\succcurlyeq 0$$
而不等式左侧正是$\begin{array}{r}\frac{\mathcal{L}}{2}{\xi }^T\xi -f(\xi )\end{array}$的二阶梯度结果。这意味着：$\begin{array}{r}\mathcal{G}(x)=\frac{\mathcal{L}}{2}{x}^{T}x-f(x)\end{array}$与二阶梯度${\nabla }^{2}f(x)(\text{Hessian Matrix})$存在关联关系。

当然，关于二次项$x^{T}x$，我们在强凸函数的定义中也发现过这种格式：
这里也使用$\mathcal{G}(x)$描述了~
$$\mathcal{G}(x)\triangleq f(x)-\frac{m}{2}{x}^{T}x$$
假设这里的$\mathcal{G}(x)$同样也是二阶可微的情况下，那么关于${\nabla }^2\mathcal{G}(x)$可表示为：
$${\nabla }^2\mathcal{G}(x)={\nabla }^{2}f(x)-m\cdot \mathcal{I}$$
根据强凸函数的二阶条件，必然有：
$${\nabla }^{2}f(x)-m\cdot \mathcal{I}\succcurlyeq 0$$

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

收敛性定理介绍

类似地，关于梯度下降法在$m$-强凸函数上的收敛性描述表示如下：

• 条件：
  • 函数$f(\cdot )$向下有界，在其定义域内可微，并且$f(\cdot )$是$m$-强凸函数；
  • 关于梯度函数$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续；
  • 在梯度下降法的迭代过程中，步长${\alpha }_k(k=1,2,3,\cdots )$存在明确的约束范围$\begin{array}{r}{\alpha }_k\in \left(0,\frac{2}{\mathcal{L}+m}\right)\end{array}$；
• 结论：
  数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​以$\mathcal{Q}$-线性收敛的收敛速度收敛于最优数值解$x^{\ast }$。
  • 关于$\mathcal{Q}$-线性收敛的数学符号描述为:$\begin{array}{r}\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}\le a\in (0,1)\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∞​来描述收敛性，本质上是一样的。

结论分析

观察分子：$||x_{k+1}-x^{\ast }||$，使用线搜索方法的通式对其进行表达：

• 分母可看作是常量，因为$x_k$是上一次迭代产生的已知信息;而最优解$x^{\ast }$随着函数$f(\cdot )$客观存在的一个值，它不会发生变化。
• 由于是梯度下降法，因而方向${\mathcal{P}}_k=-\nabla f(x_k)$;而当前迭代步骤下,${\alpha }_k$是我们要求解的量，因而将其记作变量$\alpha$。
  $$||x_{k+1}-x^{\ast }||=||x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }||$$

为了证明过程中对该量进行放缩，在上述等式两侧分别执行平方操作，从而得到一个新的等式：
$$||x_{k+1}-x^{\ast }|{|}^2=||x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }|{|}^2$$
对等式右侧进行展开：

• 将项$x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }$视作项$x_k-x^{\ast }$与项$\alpha \cdot \nabla f(x_k)$之间的减法。

• 这里啰嗦一下：关于$||(x-x^{\ast })-\alpha \cdot \nabla f(x_k)|{|}^2$,可以描述成内积形式：
  $$||(x-x^{\ast })-\alpha \cdot \nabla f(x_k)|{|}^2={\left[(x-x^{\ast })-\alpha \cdot \nabla f(x_k)\right]}^T[(x-x^{\ast })-\alpha \cdot \nabla f(x_k)]$$
  其中${\left[(x-x^{\ast })-\alpha \cdot \nabla f(x_k)\right]}^T=[(x-x^{\ast }{)}^T-(\alpha \cdot \nabla f(x_k){)}^T]$,将其替换后可得到如下三项结果:

  • $(x_k-x^{\ast }{)}^T(x_k-x^{\ast })=||x_k-x^{\ast }|{|}^2$；
  • $[\alpha \cdot \nabla f(x_k){]}^T[\alpha \cdot \nabla f(x_k)]={\alpha }^2\cdot ||\nabla f(x_k)|{|}^2$
  • 其中$-(x_k-x^{\ast }{)}^T[\alpha \cdot \nabla f(x_k)]$与$-(x_k-x^{\ast })[\alpha \nabla f(x_k){]}^T$结果都是$1\times 1$的标量，因而这两项相等，并将其合并在一起：
    $$-2\alpha \cdot [\nabla f(x_k){]}^T(x_k-x^{\ast })$$

  对于$-2\alpha \cdot [\nabla f(x_k){]}^T(x_k-x^{\ast })$,可以继续进行描述:由于$x^{\ast }$是最优数值解，那么必然有：$\nabla f(x^{\ast })=0$,将该式代入到上式中有：
  $$-2\alpha \cdot [\nabla f(x_k){]}^T(x_k-x^{\ast })=-2\alpha \cdot [\nabla f(x_k)-\nabla f(x^{\ast }){]}^T(x_k-x^{\ast })$$

最终有：
$$\begin{array}{rl}||x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }|{|}^2& =||(x-x^{\ast })-\alpha \cdot \nabla f(x_k)|{|}^2\\ & =||x_k-x^{\ast }|{|}^2-2\alpha \cdot [\nabla f(x_k)-\nabla f(x^{\ast }){]}^T(x_k-x^{\ast })+{\alpha }^2||\nabla f(x_k)|{|}^2\end{array}$$
从而将关注点放在寻找$[\nabla f(x_k)-\nabla f(x^{\ast }){]}^T(x_k-x^{\ast })$的下界信息，从而关注$\begin{array}{r}\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}\end{array}$的相关信息。

证明过程

思考：
由于函数$f(\cdot )$是$m$-强凸函数，本质上就是约束性更苛刻的凸函数，并且$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续，那么根据优化算法——白老爹定理中介绍的，该函数$f(\cdot )$一定满足余强制性：
$$\forall x_1,x_2\in {\mathbb{R}}^n\Rightarrow [\nabla f(x_1)-\nabla f(x_2){]}^T(x_1-x_2)\ge \frac{1}{\mathcal{L}}||\nabla f(x_1)-\nabla f(x_2)|{|}^2$$
相反地，由于$f(\cdot )$是$m$-强凸函数，因而对$[\nabla f(x_1)-\nabla f(x_2){]}^T(x_1-x_2)$的下界描述：$\begin{array}{r}\frac{1}{\mathcal{L}}||\nabla f(x_1)-\nabla f(x_2)|{|}^2\end{array}$过于宽松，至少没有看到参数$m$在余强制性中的作用。因而我们需要找到一个更严格的下界。

回归证明过程：
由于$f(\cdot )$是$m$-强凸函数，根据强凸函数的定义，令$\begin{array}{r}\mathcal{G}(x)\triangleq f(x)-\frac{m}{2}{x}^{T}x\end{array}$，必然有：$\mathcal{G}(x)$是凸函数。
充分必要条件~

由于$f(\cdot )$可微，并且$\begin{array}{r}\frac{m}{2}{x}^{T}x\end{array}$是关于$x$的二次函数——必然在定义域内可微。因此：函数$\mathcal{G}(\cdot )$在定义域内可微。对应梯度$\nabla \mathcal{G}(x)$表示为：
$$\nabla \mathcal{G}(x)=\nabla \left[f(x)-\frac{m}{2}{x}^{T}x\right]=\nabla f(x)-m\cdot x$$

思考：
又因为$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续，那么$\mathcal{G}(\cdot )$是否也满足利普希兹连续$?$ 必然是满足的。可以从定义角度观察 $\Rightarrow$$||\nabla \mathcal{G}(x)-\nabla \mathcal{G}(y)||$与$||x-y||$之间的关联关系：

• 将$\nabla \mathcal{G}(x)=\nabla f(x)-m\cdot x$代入~
• 使用三角不等式：$||[\nabla f(x)-\nabla f(y)]-m(x-y)||\le ||\nabla f(x)-\nabla f(y)||+||m\cdot (x-y)||$
• 利用利普希兹连续将$||\nabla f(x)-\nabla f(y)||$替换成$\mathcal{L}\cdot ||x-y||$，不等号不发生变化。
  $$\begin{array}{rl}||\nabla \mathcal{G}(x)-\nabla \mathcal{G}(y)||& =||\nabla f(x)-\nabla f(y)-m(x-y)||\\ & \le ||\nabla f(x)-\nabla f(y)||+||m\cdot (x-y)||\\ & \le \mathcal{L}\cdot ||x-y||+m\cdot ||x-y||\\ & =(\mathcal{L}+m)\cdot ||x-y||\end{array}$$

虽然通过一个简单的证明确定了$\nabla \mathcal{G}(\cdot )$满足利普希兹连续，并得到了一个关于$\nabla \mathcal{G}(\cdot )$的利普希兹常数：$\mathcal{L}+m$，但这个常数并不合理。因为相比于$\nabla f(\cdot )$，$\nabla \mathcal{G}(\cdot )$的约束强度变低了：
关于函数$\mathcal{G}(\cdot )$的斜率变化范围反而大于$f(\cdot )$。
$$\exists \xi \in (x,y)\Rightarrow \frac{||\nabla \mathcal{G}(x)-\nabla \mathcal{G}(y)||}{||x-y||}={\mathcal{G}}^{\prime }(\xi )\le \mathcal{L}+m$$
我们希望能够找到一个约束性更强的利普希兹常数，而不是$\mathcal{L}+m$。

回归证明过程：
如果令$\begin{array}{r}\mathcal{H}(x)\triangleq \frac{\mathcal{L}}{2}{x}^{T}x-f(x)\end{array}$，根据白老爹定理，$\mathcal{H}(x)$必然也是凸函数。将$f(x)$使用$\mathcal{G}(x)$进行替换：
$$\{\begin{array}{l}\begin{array}{rl}f(x)& =\mathcal{G}(x)+\frac{m}{2}{x}^{T}x\\ \mathcal{H}(x)& \triangleq \frac{\mathcal{L}}{2}{x}^{T}x-\frac{m}{2}{x}^{T}x-\mathcal{G}(x)\\ & =\frac{\mathcal{L}-m}{2}{x}^{T}x-\mathcal{G}(x)\end{array}\end{array}$$

观察这个新式子：$\begin{array}{r}\mathcal{H}(x)=\frac{\mathcal{L}-m}{2}{x}^{T}x-\mathcal{G}(x)\end{array}$，由于$\mathcal{H}(x),\mathcal{G}(x)$都是凸函数，那么可以再次使用白老爹定理，可推出：$\mathcal{G}(\cdot )$的梯度$\nabla \mathcal{G}(\cdot )$满足余强制性。即：

• 其中$\mathcal{G}(x)$为凸函数是前提条件;$\mathcal{H}(x)$为凸函数是其中一个等价条件。
• 对应描述余强制性不等式的系数由$\begin{array}{r}\frac{1}{\mathcal{L}}\end{array}$变为$\begin{array}{r}\frac{1}{\mathcal{L}-m}\end{array}$。
• 实际上，关于白老爹定理的最后一个等价条件也是满足的。即：$\nabla \mathcal{G}(\cdot )$满足$(\mathcal{L}-m)$-利普希兹连续。与之前的$(\mathcal{L}+m)$-利普希兹连续相反,它的约束性比$\mathcal{L}$-利普希兹连续更强了。

$$[\nabla \mathcal{G}(x)-\nabla \mathcal{G}(y){]}^T(x-y)\ge \frac{1}{\mathcal{L}-m}||\nabla \mathcal{G}(x)-\nabla \mathcal{G}(y)|{|}^2$$

$(2023/8/20)$：关于为什么凸函数$\mathcal{G}(\cdot )$相比$m-$强凸函数$f(\cdot )$在利普希兹连续的角度有更强的约束性，个人错误的认为是凸函数与强凸函数之间的差异性导致的。（错误想法）
因为强凸函数、凸函数之间的差异性主要体现在下界;而利普希兹连续$(\mathcal{L};\mathcal{L}-m)$约束描述的是上界。
\quad
正确的逻辑思路是：关于凸函数$\begin{array}{r}\mathcal{G}(x)\triangleq f(x)-\frac{m}{2}{x}^{T}x\end{array}$，我们可以将其理解为：在凸函数$f(x)$的基础上，减掉了一部分恒正二次项系数$(m>0)$，从而相比于$f(x)$，$\mathcal{G}(x)$函数凸的效果有所减小。这才是导致其利普希兹常数$(\mathcal{L}-m)<f(x)$利普希兹常数$(\mathcal{L})$的真正原因。

基于该结论，将$\nabla \mathcal{G}(x)=\nabla f(x)-m\cdot x$代入，有：
我们的目标是凑出$[\nabla f(x)-\nabla f(y){]}^T(x-y)$。
$$[\nabla f(x)-\nabla f(y)-m\cdot (x-y){]}^T(x-y)\ge \frac{1}{\mathcal{L}-m}||\nabla f(x)-\nabla f(y)-m\cdot (x-y)|{|}^2$$
由于$[(\nabla f(x)-\nabla f(y))-m\cdot (x-y){]}^T=[\nabla f(x)-\nabla f(y){]}^T-m\cdot (x-y{)}^T$，因此将不等式左侧继续展开：

• 展开过程中将$m\cdot (x-y{)}^T(x-y)$写成范数平方的形式：$m\cdot ||x-y|{|}^2$
• 关于不等式右侧的范数平方可看作上述两项$\nabla f(x)-\nabla f(y)$与$m\cdot (x-y)$差的平方形式，使用完全平方公式进行展开。
  $$[\nabla f(x)-\nabla f(y){]}^T(x-y)-m\cdot ||x-y|{|}^2\ge \frac{1}{\mathcal{L}-m}\left\{||\nabla f(x)-\nabla f(y)|{|}^2+m^2\cdot ||x-y|{|}^2-2m\cdot [\nabla f(x)-\nabla f(y){]}^T(x-y)\right\}$$

将不等式右侧的含$[\nabla f(x)-\nabla f(y){]}^T(x-y)$的项移到不等式左侧，同时将不等式左侧的含$||x-y|{|}^2$的项移到不等式右侧，从而有：

• 此时不等式左侧仅包含关于$[\nabla f(x)-\nabla f(y){]}^T(x-y)$项的信息。

$$\left(1+\frac{2m}{\mathcal{L}-m}\right)[\nabla f(x)-\nabla f(y){]}^T(x-y)\ge \frac{1}{\mathcal{L}-m}||\nabla f(x)-\nabla f(y)|{|}^2+\left(m+\frac{m^2}{\mathcal{L}-m}\right)||x-y|{|}^2$$
继续化简，有
由于$\mathcal{L},m$分别是约束${\nabla }^{2}f(\cdot )$上界与下界的常数参数，由于$f(\cdot )$是强凸函数，那么$\mathcal{L}>m$恒成立。

• 如果$\mathcal{L}<m$,即上界小于下界，那就不是凸函数了~
• 如果$\mathcal{L}=m$,例如线性函数,那么它只是凸函数,而不是强凸函数。

因而将不等式左侧的系数$\begin{array}{r}\frac{\mathcal{L}+m}{\mathcal{L}-m}\end{array}$移到右侧，不等号方向不变。此时，不等式左侧只剩下了$[\nabla f(x)-\nabla f(y){]}^T(x-y)$。
$$\begin{array}{rl}& \frac{\mathcal{L}+m}{\mathcal{L}-m}[\nabla f(x)-\nabla f(y){]}^T(x-y)\ge \frac{1}{\mathcal{L}-m}||\nabla f(x)-\nabla f(y)|{|}^2+\frac{\mathcal{L}\cdot m}{\mathcal{L}-m}||x-y|{|}^2\\ & \\ & \Rightarrow [\nabla f(x)-\nabla f(y){]}^T(x-y)\ge \left(\frac{1}{\mathcal{L}-m}\cdot \frac{\mathcal{L}-m}{\mathcal{L}+m}\right)||\nabla f(x)-\nabla f(y)|{|}^2+\left(\frac{\mathcal{L}\cdot m}{\mathcal{L}-m}\cdot \frac{\mathcal{L}-m}{\mathcal{L}+m}\right)||x-y|{|}^2\\ & =[\nabla f(x)-\nabla f(y){]}^T(x-y)\ge \frac{1}{\mathcal{L}+m}||\nabla f(x)-\nabla f(y)|{|}^2+\frac{\mathcal{L}\cdot m}{\mathcal{L}+m}||x-y|{|}^2\end{array}$$

至此，回顾结论分析，由于$x,y\in {\mathbb{R}}^n$内任意取值，因此令：$x=x_k;y=x^{\ast }$，上式有：
关于不等式右侧的$\nabla f(x^{\ast })=0$这里就省略了~
$$[\nabla f(x_k)-\nabla f(x^{\ast }){]}^T(x_k-x^{\ast })\ge \frac{1}{\mathcal{L}+m}||\nabla f(x_k)|{|}^2+\frac{\mathcal{L}\cdot m}{\mathcal{L}+m}||x_k-x^{\ast }|{|}^2$$
从而将这个描述$[\nabla f(x_k)-\nabla f(x^{\ast }){]}^T(x_k-x^{\ast })$下界的不等式代回到结论分析的式子中有：

• 由于$-2\alpha$使不等号方向发生变化~
• 合并同类项~
  $$\begin{array}{rl}||x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }|{|}^2& =||x_k-x^{\ast }|{|}^2-2\alpha \cdot [\nabla f(x_k)-\nabla f(x^{\ast }){]}^T(x_k-x^{\ast })+{\alpha }^2||\nabla f(x_k)|{|}^2\\ & \le ||x_k-x^{\ast }|{|}^2-2\alpha \left(\frac{1}{\mathcal{L}+m}||\nabla f(x_k)|{|}^2+\frac{\mathcal{L}\cdot m}{\mathcal{L}+m}||x_k-x^{\ast }|{|}^2\right)+{\alpha }^2||\nabla f(x_k)|{|}^2\\ & \le ||x_k-x^{\ast }|{|}^2-\frac{2\alpha }{\mathcal{L}+m}||\nabla f(x_k)|{|}^2-\frac{2\alpha \mathcal{L}m}{\mathcal{L}+m}||x_k-x^{\ast }|{|}^2+{\alpha }^2||\nabla f(x_k)|{|}^2\\ & =\left(1-\frac{2\alpha \mathcal{L}m}{\mathcal{L}+m}\right)||x_k-x^{\ast }|{|}^2+\alpha \left(\alpha -\frac{2}{\mathcal{L}+m}\right)||\nabla f(x_k)|{|}^2\end{array}$$

根据收敛性定理中关于步长$\alpha$的条件：$\begin{array}{r}\alpha \in \left(0,\frac{2}{\mathcal{L}+m}\right)\end{array}$，有：
很明显，项$\begin{array}{r}\alpha \left(\alpha -\frac{2}{\mathcal{L}+m}\right)||\nabla f(x_k)|{|}^2\end{array}$是一个负值，从而可以对$||x_k=\alpha \cdot \nabla f(x_k)-x^{\ast }|{|}^2$进行进一步的约束。
$$\begin{array}{r}||x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }|{|}^2\le \left(1-\alpha \cdot \frac{2\mathcal{L}m}{\mathcal{L}+m}\right)||x_k-x^{\ast }|{|}^2\end{array}$$
最终移项并开根号，得到关于收敛速度定义的一个表达：
关于收敛速度，详见收敛速度的简单认识。
$$\begin{array}{r}\frac{||x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }||}{||x_k-x^{\ast }||}\le \sqrt{1-\alpha \cdot \frac{2\mathcal{L}m}{\mathcal{L}+m}}\end{array}$$
记$\begin{array}{r}\mathcal{C}=1-\alpha \cdot \frac{2\mathcal{L}m}{\mathcal{L}+m}\end{array}$，观察：

• 由于：$\alpha ,\mathcal{L},m$均$>0$，因而$\mathcal{C}<1$；
• 根据$\alpha$条件：$\begin{array}{r}\alpha <\frac{2}{\mathcal{L}+m}\end{array}$，因而将该式代入，有：
  $$\begin{array}{r}\mathcal{C}=1-\alpha \cdot \frac{2\mathcal{L}m}{\mathcal{L}+m}>1-\frac{4\mathcal{L}m}{(\mathcal{L}+m{)}^2}=\frac{(\mathcal{L}+m{)}^2-4\mathcal{L}m}{(\mathcal{L}+m{)}^2}=\frac{(\mathcal{L}-m{)}^2}{(\mathcal{L}+m{)}^2}\end{array}$$
  由于$\mathcal{L},m$恒正，必然有：$\begin{array}{r}\frac{(\mathcal{L}-m{)}^2}{(\mathcal{L}+m{)}^2}>0\end{array}$

从而最终有：$\mathcal{C}\in (0,1)$，从而$\sqrt{\mathcal{C}}\in (0,1)$。即：
$$\begin{array}{r}\frac{||x_{k+1}-x^{\ast }||}{||x_k-x^{\ast }||}=\frac{||x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }||}{||x_k-x^{\ast }||}\le \sqrt{\mathcal{C}}\in (0,1)\end{array}$$
因而 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​的收敛速度是$\mathcal{Q}$-线性收敛，证毕。

相关参考：
【优化算法】梯度下降法-强凸函数的收敛性分析（上）文章来源地址https://www.toymoban.com/news/detail-670501.html

到了这里，关于机器学习笔记之优化算法(十六)梯度下降法在强凸函数上的收敛性证明的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！