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

机器学习笔记之优化算法——梯度下降法在凸函数上的收敛性

• 引言
• • 回顾：
  • 梯度下降法在凸函数上的收敛性

引言

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

回顾：

收敛速度：次线性收敛

关于次线性收敛，分为两种判别类型： R \mathcal R R-次线性收敛与 Q \mathcal Q Q-次线性收敛。而次线性收敛的特点是：随着迭代次数的增加，相邻迭代步骤产生的目标函数结果 f ( x k ) , f ( x k + 1 ) f(x_k),f(x_{k+1}) f(xk​),f(xk+1​)，其差异性几乎完全相同：
lim ⁡ k ⇒ ∞ ∣ ∣ x k + 1 − x ∗ ∣ ∣ ∣ ∣ x k − x ∗ ∣ ∣ = 1 \mathop{\lim}\limits_{k \Rightarrow \infty}\frac{||x_{k+1} - x^*||}{||x_k - x^*||} = 1 k⇒∞lim​∣∣xk​−x∗∣∣∣∣xk+1​−x∗∣∣​=1
例如：如果数值解 x k x_k xk​的目标函数结果 f ( x k ) f(x_k) f(xk​)与目标函数最优解 f ∗ f^* f∗之间的差异性 ∣ ∣ f ( x k ) − f ∗ ∣ ∣ ||f(x_k) - f^*|| ∣∣f(xk​)−f∗∣∣与迭代次数 k k k存在如下函数关系 G ( k ) \mathcal G(k) G(k)：
∣ ∣ f ( x k ) − f ∗ ∣ ∣ ≤ G ( k ) = 1 k ||f(x_k) - f^*|| \leq \mathcal G(k) = \frac{1}{k} ∣∣f(xk​)−f∗∣∣≤G(k)=k1​
当 k k k充分大时， f ( x k ) , f ( x k + 1 ) f(x_k),f(x_{k+1}) f(xk​),f(xk+1​)与 f ∗ f^* f∗之间差异性的比值表示如下：
lim ⁡ k ⇒ ∞ ∣ ∣ f ( x k + 1 ) − f ∗ ∣ ∣ ∣ ∣ f ( x k ) − f ∗ ∣ ∣ = lim ⁡ k ⇒ ∞ k k + 1 = 1 \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{||f(x_{k+1}) - f^*||}{||f(x_k) - f^*||} = \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{k}{k+1} = 1 k⇒∞lim​∣∣f(xk​)−f∗∣∣∣∣f(xk+1​)−f∗∣∣​=k⇒∞lim​k+1k​=1
也就是说：虽然随着 k k k的增加， f ( x k ) f(x_k) f(xk​)在减小;但相邻迭代结果 f ( x k ) , f ( x k + 1 ) f(x_k),f(x_{k+1}) f(xk​),f(xk+1​)之间的差异性几乎可以忽略不计。那么称这种收敛速度为次线性收敛。
准确的说，是 ⇒ 0 \Rightarrow 0 ⇒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 ( ⋅ ) f(\cdot) f(⋅)可微，并对应梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) ∇f(⋅)满足利普希兹连续，则函数 f ( ⋅ ) f(\cdot) f(⋅)存在二次上界。即：
∀ x , y ∈ R n ⇒ f ( y ) ≤ f ( x ) + [ ∇ f ( x ) ] T ( y − x ) + L 2 ∣ ∣ y − x ∣ ∣ 2 \forall x,y \in \mathbb R^n \Rightarrow f(y) \leq f(x) + [\nabla f(x)]^T (y - x) + \frac{\mathcal L}{2}||y - x||^2 ∀x,y∈Rn⇒f(y)≤f(x)+[∇f(x)]T(y−x)+2L​∣∣y−x∣∣2
而二次上界引理的作用是：可以通过该引理，得到最优步长上界的最小值：

• 假设 x x x固定，令 ϕ ( y ) = f ( x ) + [ ∇ f ( x ) ] T ( y − x ) + L 2 ∣ ∣ y − x ∣ ∣ 2 \begin{aligned}\phi(y) = f(x) + [\nabla f(x)]^T (y - x) + \frac{\mathcal L}{2}||y - x||^2 \end{aligned} ϕ(y)=f(x)+[∇f(x)]T(y−x)+2L​∣∣y−x∣∣2​，通过选择合适的 y m i n y_{min} ymin​，使 ϕ ( y ) \phi(y) ϕ(y)达到最小值：
  y m i n = arg ⁡ min ⁡ y ∈ R n ϕ ( y ) y_{min} = \mathop{\arg\min}\limits_{y \in \mathbb R^n} \phi(y) ymin​=y∈Rnargmin​ϕ(y)
• 令 ∇ ϕ ( y ) ≜ 0 \nabla \phi(y) \triangleq 0 ∇ϕ(y)≜0，有：
  y m i n = x + 1 L ⋅ [ − ∇ f ( x ) ] y_{min} = x + \frac{1}{\mathcal L} \cdot [- \nabla f(x)] ymin​=x+L1​⋅[−∇f(x)]
• 其中 − ∇ f ( x ) - \nabla f(x) −∇f(x)即 P k \mathcal P_k Pk​，也就是最速下降方向；而 1 L \begin{aligned}\frac{1}{\mathcal L}\end{aligned} L1​​则是最优步长的上确界：
  f ( y ) ≤ ϕ ( y m i n ) = min ⁡ y ∈ R n ϕ ( y ) f(y) \leq \phi(y_{min}) = \mathop{\min}\limits_{y \in \mathbb R^n} \phi(y) f(y)≤ϕ(ymin​)=y∈Rnmin​ϕ(y)
  也就是说：
  • 在没有二次上界引理的约束下，步长 α k \alpha_k αk​的选择在其定义域内没有约束： ( 0 , + ∞ ) (0, +\infty) (0,+∞)；
  • 经过二次上界引理的约束后，步长 α k \alpha_k αk​的选择从原始的 ( 0 , + ∞ ) (0,+\infty) (0,+∞)约束至 ( 0 , 1 L ] \begin{aligned}\left(0,\frac{1}{\mathcal L}\right]\end{aligned} (0,L1​]​。

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

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

收敛性定理介绍

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

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

证明过程

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

• 将内积写作 ∣ ∣ ⋅ ∣ ∣ 2 ||\cdot||^2 ∣∣⋅∣∣2的形式。
• ∣ ∣ − ∇ f ( x i − 1 ) ⋅ α ∣ ∣ 2 = ∣ ∣ ∇ f ( x i − 1 ) ⋅ α ∣ ∣ 2 ||- \nabla f(x_{i-1}) \cdot \alpha||^2 = ||\nabla f(x_{i-1}) \cdot \alpha||^2 ∣∣−∇f(xi−1​)⋅α∣∣2=∣∣∇f(xi−1​)⋅α∣∣2,这里消掉一个负号;
• 由于 α ∈ ( 0 , 1 L ] \begin{aligned}\alpha \in \left(0,\frac{1}{\mathcal L}\right]\end{aligned} α∈(0,L1​]​,是一个标量，直接将其提到范数外侧。
  I r i g h t = f ( x i − 1 ) − α ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 + L 2 ⋅ α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 \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 Iright​=f(xi−1​)−α⋅∣∣∇f(xi−1​)∣∣2+2L​⋅α2⋅∣∣∇f(xi−1​)∣∣2

由 α ≤ 1 L \begin{aligned}\alpha \leq \frac{1}{\mathcal L}\end{aligned} α≤L1​​可知： L ≤ 1 α \begin{aligned}\mathcal L \leq \frac{1}{\alpha} \end{aligned} L≤α1​​。将该式代入到上式中：
消掉分母中的 α \alpha α，并于前面的项结合。
I r i g h t ≤ f ( x i − 1 ) − α ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 + 1 2 α ⋅ α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 = f ( x i − 1 ) − α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 \begin{aligned} \mathcal I_{right} & \leq 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{aligned} Iright​​≤f(xi−1​)−α⋅∣∣∇f(xi−1​)∣∣2+2α1​⋅α2⋅∣∣∇f(xi−1​)∣∣2=f(xi−1​)−2α​⋅∣∣∇f(xi−1​)∣∣2​
基于梯度下降法，使用二次上界引理，可以得到 f ( x i − 1 ) f(x_{i-1}) f(xi−1​)与 f ( x i ) f(x_i) f(xi​)之间存在如下关联关系：
f ( x i ) ≤ f ( x i − 1 ) − α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 i = 1 , 2 , 3 , ⋯ f(x_i) \leq f(x_{i-1}) - \frac{\alpha}{2} \cdot ||\nabla f(x_{i-1})||^2\quad i=1,2,3,\cdots f(xi​)≤f(xi−1​)−2α​⋅∣∣∇f(xi−1​)∣∣2i=1,2,3,⋯
根据凸函数的性质，必然有：函数 f ( ⋅ ) f(\cdot) f(⋅)任一位置的切线， f ( ⋅ ) f(\cdot) f(⋅)均在该切线上方。见下图：
由于条件: f ( ⋅ ) f(\cdot) f(⋅)向下有界,因此，该函数必然’开口向上‘。

其中红色点 ( x ∗ , f ∗ ) (x^*,f^*) (x∗,f∗)表示最优点，以上一次迭代产生的 x i − 1 x_{i-1} xi−1​为切点做一条切线，必然有 x ∗ x^* x∗在该切线函数上的函数值 f ′ ≤ f ∗ f' \leq f^* f′≤f∗。 f ′ f' f′表示如下：
f ′ = f ( x i − 1 ) − [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) ≤ f ∗ f' = f(x_{i-1}) - [\nabla f(x_{i-1})]^T (x_{i-1} - x^*) \leq f^* f′=f(xi−1​)−[∇f(xi−1​)]T(xi−1​−x∗)≤f∗
移项，从而有：
f ( x i − 1 ) ≤ f ∗ + [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) f(x_{i-1}) \leq f^* + [\nabla f(x_{i-1})]^T (x_{i-1} - x^*) f(xi−1​)≤f∗+[∇f(xi−1​)]T(xi−1​−x∗)
将上式代入，有：
I r i g h t ≤ f ∗ + [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) ⏟ 替换 f ( x i − 1 ) − α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 \mathcal I_{right} \leq \underbrace{f^* + [\nabla f(x_{i-1})]^T (x_{i-1} - x^*)}_{替换f(x_{i-1})}- \frac{\alpha}{2} \cdot ||\nabla f(x_{i-1})||^2 Iright​≤替换f(xi−1​) f∗+[∇f(xi−1​)]T(xi−1​−x∗)​​−2α​⋅∣∣∇f(xi−1​)∣∣2
为了凑平方项，将上式调整至如下形式：
将 − α 2 \begin{aligned}-\frac{\alpha}{2}\end{aligned} −2α​​凑出 α 2 \alpha^2 α2,其他项跟随变化。
I r i g h t ≤ − 1 2 α { α 2 ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 − 2 α ⋅ [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) } \mathcal I_{right} \leq -\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^*)\right\} Iright​≤−2α1​{α2∣∣∇f(xi−1​)∣∣2−2α⋅[∇f(xi−1​)]T(xi−1​−x∗)}
对大括号内的项进行配方：
I r i g h t ≤ f ∗ − 1 2 α { α 2 ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 − 2 α ⋅ [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) + ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 ⏟ 平方项 − ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 } = f ∗ − 1 2 α [ ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 − ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 ] \begin{aligned} \mathcal I_{right} & \leq f^* - \frac{1}{2 \alpha} \left\{\underbrace{\alpha^2 ||\nabla f(x_{i-1})||^2 - 2\alpha \cdot [\nabla f(x_{i-1})]^T(x_{i-1} - x^*) + ||x_{i-1} - x^*||^2 }_{平方项}- ||x_{i-1} - x^*||^2\right\} \\ & = f^* - \frac{1}{2\alpha} \left [||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 - ||x_{i-1} - x^*||^2\right] \end{aligned} Iright​​≤f∗−2α1​⎩ ⎨ ⎧​平方项 α2∣∣∇f(xi−1​)∣∣2−2α⋅[∇f(xi−1​)]T(xi−1​−x∗)+∣∣xi−1​−x∗∣∣2​​−∣∣xi−1​−x∗∣∣2⎭ ⎬ ⎫​=f∗−2α1​[∣∣α⋅∇f(xi−1​)−(xi−1​−x∗)∣∣2−∣∣xi−1​−x∗∣∣2]​
观察中括号内第一项： ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 ||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 ∣∣α⋅∇f(xi−1​)−(xi−1​−x∗)∣∣2，由于是范数的平方项，因而在范数内部添加一个负号不会影响其值的变化：
∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 = ∣ ∣ x i − 1 − α ⋅ ∇ f ( x i − 1 ) − x ∗ ∣ ∣ 2 ||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 = ||x_{i-1} - \alpha \cdot \nabla f(x_{i-1}) - x^*||^2 ∣∣α⋅∇f(xi−1​)−(xi−1​−x∗)∣∣2=∣∣xi−1​−α⋅∇f(xi−1​)−x∗∣∣2
从迭代角度观察： x i − 1 − α ⋅ ∇ f ( x i − 1 ) = x i x_{i-1} - \alpha \cdot \nabla f(x_{i-1}) = x_{i} xi−1​−α⋅∇f(xi−1​)=xi​，从而上式可继续化简为：
提一个负号，调换一下位置。
{ ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 = ∣ ∣ x i − x ∗ ∣ ∣ 2 I r i g h t ≤ f ∗ − 1 2 α [ ∣ ∣ x i − x ∗ ∣ ∣ 2 − ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 ] = f ∗ + 1 2 α [ ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x i − x ∗ ∣ ∣ 2 ] \begin{cases} ||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 = ||x_i - x^*||^2 \\ \quad \\ \begin{aligned} \mathcal I_{right} & \leq f^* - \frac{1}{2\alpha} \left[||x_i - x^*||^2 - ||x_{i-1} - x^*||^2\right] \\ & = f^* + \frac{1}{2\alpha} \left[||x_{i-1} - x^*||^2 - ||x_i - x^*||^2\right] \end{aligned} \end{cases} ⎩ ⎨ ⎧​∣∣α⋅∇f(xi−1​)−(xi−1​−x∗)∣∣2=∣∣xi​−x∗∣∣2Iright​​≤f∗−2α1​[∣∣xi​−x∗∣∣2−∣∣xi−1​−x∗∣∣2]=f∗+2α1​[∣∣xi−1​−x∗∣∣2−∣∣xi​−x∗∣∣2]​​

至此，可以得到如下不等式结果：
f ( x i ) − f ∗ ≤ 1 2 α ( ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x i − x ∗ ∣ ∣ 2 ) f(x_i) - f^* \leq \frac{1}{2\alpha}(||x_{i-1} - x^*||^2 - ||x_i - x^*||^2) f(xi​)−f∗≤2α1​(∣∣xi−1​−x∗∣∣2−∣∣xi​−x∗∣∣2)
观察：不等式左侧描述的意义是：当前迭代步骤的目标函数结果 f ( x i ) f(x_i) f(xi​)与最优解 f ∗ f^* f∗之间的偏差。从初始化数值解 x 0 x_0 x0​开始，我们会得到一系列的不等式结果：
{ f ( x 1 ) − f ∗ ≤ 1 2 α ( ∣ ∣ x 0 − x ∗ ∣ ∣ 2 − ∣ ∣ x 1 − x ∗ ∣ ∣ 2 ) f ( x 2 ) − f ∗ ≤ 1 2 α ( ∣ ∣ x 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x 2 − x ∗ ∣ ∣ 2 ) ⋮ f ( x k ) − f ∗ ≤ 1 2 α ( ∣ ∣ x k − 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x k − x ∗ ∣ ∣ 2 ) \begin{cases} \begin{aligned} f(x_1) - f^* & \leq \frac{1}{2\alpha} (||x_0 - x^*||^2 - ||x_1 - x^*||^2) \\ f(x_2) - f^* & \leq \frac{1}{2\alpha} (||x_1 - x^*||^2 - ||x_2 - x^*||^2) \\ & \vdots \\ f(x_k) - f^* & \leq \frac{1}{2\alpha} (||x_{k-1} - x^*||^2 - ||x_k - x^*||^2) \end{aligned} \end{cases} ⎩ ⎨ ⎧​f(x1​)−f∗f(x2​)−f∗f(xk​)−f∗​≤2α1​(∣∣x0​−x∗∣∣2−∣∣x1​−x∗∣∣2)≤2α1​(∣∣x1​−x∗∣∣2−∣∣x2​−x∗∣∣2)⋮≤2α1​(∣∣xk−1​−x∗∣∣2−∣∣xk​−x∗∣∣2)​​
将这些不等式对应位置相加，有：

• 等式右侧的中间项都被消掉了~
• 因为 ∣ ∣ x k − x ∗ ∣ ∣ 2 ≥ 0 ||x_k - x^*||^2 \geq 0 ∣∣xk​−x∗∣∣2≥0恒成立，从而消掉含变量的项。
  ∑ i = 1 k [ f ( x i ) − f ∗ ] ≤ 1 2 α ( ∣ ∣ ∣ x 0 − x ∗ ∣ ∣ 2 − ∣ ∣ x k − x ∗ ∣ ∣ 2 ) ≤ 1 2 α ∣ ∣ x 0 − x ∗ ∣ ∣ 2 \sum_{i=1}^k [f(x_i) - f^*] \leq \frac{1}{2\alpha}(|||x_0 - x^*||^2 - ||x_k - x^*||^2) \leq \frac{1}{2 \alpha} ||x_0 - x^*||^2 i=1∑k​[f(xi​)−f∗]≤2α1​(∣∣∣x0​−x∗∣∣2−∣∣xk​−x∗∣∣2)≤2α1​∣∣x0​−x∗∣∣2

关于我们要证的 ∣ ∣ f ( x k ) − f ∗ ∣ ∣ ||f(x_k) - f^*|| ∣∣f(xk​)−f∗∣∣，可以表示为如下形式：

• 由于优化问题的收敛性，必然有： f ( x k ) ≤ f ( x k − 1 ) ≤ ⋯ ≤ f ( x 1 ) f(x_{k}) \leq f(x_{k-1})\leq \cdots\leq f(x_1) f(xk​)≤f(xk−1​)≤⋯≤f(x1​),从而每一项: ∣ ∣ f ( x k ) − f ∗ ∣ ∣ ≤ ∣ ∣ f ( x k − 1 ) − f ∗ ∣ ∣ ≤ ⋯ ≤ ∣ ∣ f ( x 1 ) − f ∗ ∣ ∣ ||f(x_k) - f^*|| \leq ||f(x_{k-1}) - f^*|| \leq \cdots \leq ||f(x_1) - f^*|| ∣∣f(xk​)−f∗∣∣≤∣∣f(xk−1​)−f∗∣∣≤⋯≤∣∣f(x1​)−f∗∣∣,从而有: ∑ i = 1 k [ f ( x k ) − f ∗ ] ≤ ∑ i = 1 k [ f ( x i ) − f ∗ ] \begin{aligned}\sum_{i=1}^k[f(x_k) - f^*] \leq \sum_{i=1}^{k} [f(x_i) - f^*]\end{aligned} i=1∑k​[f(xk​)−f∗]≤i=1∑k​[f(xi​)−f∗]​。
• 将上式结果带入~

f ( x k ) − f ∗ = 1 k ∑ i = 1 k [ f ( x k ) − f ∗ ] ≤ 1 k ∑ i = 1 k [ f ( x i ) − f ∗ ] ≤ 1 k [ 1 2 α ∣ ∣ x 0 − x ∗ ∣ ∣ 2 ] f(x_k) - f^* = \frac{1}{k} \sum_{i=1}^{k}[f(x_k) - f^*] \leq \frac{1}{k} \sum_{i=1}^{k}[f(x_i) - f^*] \leq \frac{1}{k} \left[\frac{1}{2\alpha}||x_0 - x^*||^2\right] f(xk​)−f∗=k1​i=1∑k​[f(xk​)−f∗]≤k1​i=1∑k​[f(xi​)−f∗]≤k1​[2α1​∣∣x0​−x∗∣∣2]

观察： [ 1 2 α ∣ ∣ x 0 − x ∗ ∣ ∣ 2 ] \begin{aligned}\left[\frac{1}{2\alpha}||x_0 - x^*||^2\right]\end{aligned} [2α1​∣∣x0​−x∗∣∣2]​中 α ∈ ( 0 , 1 L ] \begin{aligned}\alpha \in \left(0,\frac{1}{\mathcal L} \right] \end{aligned} α∈(0,L1​]​， x 0 , x ∗ x_0,x^* x0​,x∗都是确定的常数，因而该项可视作常数 C \mathcal C C。最终有：
f ( x k ) − f ∗ ≤ 1 k ⋅ C f(x_k) - f^* \leq \frac{1}{k} \cdot \mathcal C f(xk​)−f∗≤k1​⋅C
我们可以令 G ( k ) = 1 k ⋅ C \begin{aligned}\mathcal G(k) = \frac{1}{k} \cdot \mathcal C\end{aligned} G(k)=k1​⋅C​，可以看出：它就是一个级别为 1 k \begin{aligned}\frac{1}{k}\end{aligned} k1​​的次线性收敛。

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