首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

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

  • 24-03-09 02:01
  • 3603
  • 11248
blog.csdn.net

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

  • 引言
    • 回顾:
      • 收敛速度:次线性收敛
      • 二次上界引理
    • 梯度下降法在凸函数上的收敛性
      • 收敛性定理介绍
      • 证明过程

引言

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

回顾:

收敛速度:次线性收敛

关于次线性收敛,分为两种判别类型: 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 ϕ(y)=f(x)+[∇f(x)]T(y−x)+L2||y−x||2
    ϕ(y)=f(x)+[∇f(x)]T(y−x)+L2||y−x||2
    ϕ(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 1L
    1L
    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 ] (0,1L]
      (0,L1​]​
      。

延伸:关于区间 ( 0 , 1 L ] (0,1L]

(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 (0,1L]
α∈(0,L1​]​
时,等价于:存在一条直线 L ( α ) \mathcal L(\alpha) L(α),以该直线作为划分边界对应 α \alpha α的范围正好是 ( 0 , 1 L ] (0,1L]
(0,L1​]​
:
吐槽:实际上用这张图是不太合理的,因为下面的图对应的 f ( ⋅ ) f(\cdot) f(⋅)更加复杂,二次上界约束的范围仅仅在下面 α \alpha α轴的绿色实线部分,但很明显,在该函数中,存在更优质的 α \alpha α结果。
Armijo准则与二次上界

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

收敛性定理介绍

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

  • 条件:
    • 函数 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 ] αk∈(0,1L]
      α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 ) O(1k)
    O(k1​)​
    收敛于目标函数最优解 f ∗ f^* f∗。
    其中 O ( 1 k ) O(1k)
    O(k1​)​
    表示以 G ( k ) = C ⋅ 1 k G(k)=C⋅1k
    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 ] α∈(0,1L]
    α∈(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 α≤1L

α≤L1​​可知: L ≤ 1 α L≤1α
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 Iright≤f(xi−1)−α⋅||∇f(xi−1)||2+12α⋅α2⋅||∇f(xi−1)||2=f(xi−1)−α2⋅||∇f(xi−1)||2
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 −α2
−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 ] Iright≤f∗−12α{α2||∇f(xi−1)||2−2α⋅[∇f(xi−1)]T(xi−1−x∗)+||xi−1−x∗||2⏟平方项−||xi−1−x∗||2}=f∗−12α[||α⋅∇f(xi−1)−(xi−1−x∗)||2−||xi−1−x∗||2]
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 ] {||α⋅∇f(xi−1)−(xi−1−x∗)||2=||xi−x∗||2Iright≤f∗−12α[||xi−x∗||2−||xi−1−x∗||2]=f∗+12α[||xi−1−x∗||2−||xi−x∗||2]
⎩ ⎨ ⎧​∣∣α⋅∇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 ) {f(x1)−f∗≤12α(||x0−x∗||2−||x1−x∗||2)f(x2)−f∗≤12α(||x1−x∗||2−||x2−x∗||2)⋮f(xk)−f∗≤12α(||xk−1−x∗||2−||xk−x∗||2)

⎩ ⎨ ⎧​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 ∗ ] k∑i=1[f(xk)−f∗]≤k∑i=1[f(xi)−f∗]
    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 ] [12α||x0−x∗||2]

[2α1​∣∣x0​−x∗∣∣2]​中 α ∈ ( 0 , 1 L ] α∈(0,1L]
α∈(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 G(k)=1k⋅C
G(k)=k1​⋅C​
,可以看出:它就是一个级别为 1 k 1k
k1​​
的次线性收敛
。

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

注:本文转载自blog.csdn.net的静静的喝酒的文章"https://blog.csdn.net/qq_34758157/article/details/132229111"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top