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

这篇具有很好参考价值的文章主要介绍了机器学习笔记值优化算法(十四)梯度下降法在凸函数上的收敛性。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言

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

回顾:

收敛速度:次线性收敛

关于次线性收敛,分为两种判别类型: 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 klim∣∣xkx∣∣∣∣xk+1x∣∣=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 klim∣∣f(xk)f∣∣∣∣f(xk+1)f∣∣=klimk+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 klim{f(xk)}klimG(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,yRnf(y)f(x)+[f(x)]T(yx)+2L∣∣yx2
二次上界引理的作用是:可以通过该引理,得到最优步长上界的最小值

  • 假设 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(yx)+2L∣∣yx2,通过选择合适的 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=yRnargminϕ(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)=yRnminϕ(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)=Ck1次线性收敛级别的收敛速度( C \mathcal C C为常数)。

证明过程

根据二次上界引理,依然将 x x x设为上一次迭代数值解 x i − 1 x_{i-1} xi1,对应的 y y y当前迭代步骤数值解 x i x_i xi。由于是梯度下降法,因而在线搜索方法的基础上,将方向 P i \mathcal P_i Pi表示为最速下降方向 ∇ f ( x i − 1 ) \nabla f(x_{i-1}) f(xi1)步长依然使用步长变量 α \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 yx=xixi1=f(xi1)α
二次上界不等式进行相应替换:
将上式代入~
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(xi1)+[f(xi1)]T[f(xi1)α]+2L∣∣f(xi1)α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(xi1)α2=∣∣∇f(xi1)α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(xi1)α∣∣∇f(xi1)2+2Lα2∣∣∇f(xi1)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} Irightf(xi1)α∣∣∇f(xi1)2+2α1α2∣∣∇f(xi1)2=f(xi1)2α∣∣∇f(xi1)2
基于梯度下降法,使用二次上界引理,可以得到 f ( x i − 1 ) f(x_{i-1}) f(xi1) 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(xi1)2α∣∣∇f(xi1)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} xi1为切点做一条切线,必然有 x ∗ x^* x在该切线函数上的函数值 f ′ ≤ f ∗ f' \leq f^* ff 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(xi1)[f(xi1)]T(xi1x)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(xi1)f+[f(xi1)]T(xi1x)
将上式代入,有:
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(xi1) f+[f(xi1)]T(xi1x)2α∣∣∇f(xi1)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\} Iright2α1{α2∣∣∇f(xi1)22α[f(xi1)]T(xi1x)}
大括号内的项进行配方
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} Irightf2α1 平方项 α2∣∣∇f(xi1)22α[f(xi1)]T(xi1x)+∣∣xi1x2∣∣xi1x2 =f2α1[∣∣αf(xi1)(xi1x)2∣∣xi1x2]
观察中括号内第一项 ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 ||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 ∣∣αf(xi1)(xi1x)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(xi1)(xi1x)2=∣∣xi1αf(xi1)x2
迭代角度观察: x i − 1 − α ⋅ ∇ f ( x i − 1 ) = x i x_{i-1} - \alpha \cdot \nabla f(x_{i-1}) = x_{i} xi1αf(xi1)=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(xi1)(xi1x)2=∣∣xix2Irightf2α1[∣∣xix2∣∣xi1x2]=f+2α1[∣∣xi1x2∣∣xix2]

至此,可以得到如下不等式结果:
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)f2α1(∣∣xi1x2∣∣xix2)
观察:不等式左侧描述的意义是:当前迭代步骤的目标函数结果 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)ff(x2)ff(xk)f2α1(∣∣x0x2∣∣x1x2)2α1(∣∣x1x2∣∣x2x2)2α1(∣∣xk1x2∣∣xkx2)
将这些不等式对应位置相加,有:

  • 等式右侧的中间项都被消掉了~
  • 因为 ∣ ∣ x k − x ∗ ∣ ∣ 2 ≥ 0 ||x_k - x^*||^2 \geq 0 ∣∣xkx20恒成立,从而消掉含变量的项。
    ∑ 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=1k[f(xi)f]2α1(∣∣∣x0x2∣∣xkx2)2α1∣∣x0x2

关于我们要证的 ∣ ∣ 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(xk1)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(xk1)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=1k[f(xk)f]i=1k[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=k1i=1k[f(xk)f]k1i=1k[f(xi)f]k1[2α1∣∣x0x2]

观察: [ 1 2 α ∣ ∣ x 0 − x ∗ ∣ ∣ 2 ] \begin{aligned}\left[\frac{1}{2\alpha}||x_0 - x^*||^2\right]\end{aligned} [2α1∣∣x0x2] α ∈ ( 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)fk1C
我们可以令 G ( k ) = 1 k ⋅ C \begin{aligned}\mathcal G(k) = \frac{1}{k} \cdot \mathcal C\end{aligned} G(k)=k1C,可以看出:它就是一个级别为 1 k \begin{aligned}\frac{1}{k}\end{aligned} k1次线性收敛

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【机器学习】P17 梯度下降 与 梯度下降优化算法(BGD 等 与 Adam Optimizer、AdaGrad、RMSProp)

    梯度下降(Gradient Descent)是一种常用的优化算法,用于求解目标函数的最小值。(在机器学习应用梯度下降中,主要目标是为了最小化损失函数); 其基本思想是通过不断迭代调整参数,使得目标函数的值不断逼近最小值。(机器学习中是为了最小化损失函数,即使得预测

    2023年04月16日
    浏览(46)
  • 深入探讨梯度下降:优化机器学习的关键步骤(一)

    在机器学习领域,梯度下降是一种核心的优化算法,它被广泛应用于训练神经网络、线性回归和其他机器学习模型中。本文将深入探讨梯度下降的工作原理,并且进行简单的代码实现 梯度下降是一种迭代优化算法,旨在寻找函数的局部最小值(或最大值)以最小化(或最大化

    2024年02月10日
    浏览(48)
  • 深入探讨梯度下降:优化机器学习的关键步骤(二)

    承接上篇,这篇主要有两个重点,一个是 eta 参数的调解;一个是在sklearn中实现梯度下降 在梯度下降算法中,学习率(通常用符号η表示,也称为步长或学习速率)的选择非常重要,因为它直接影响了算法的性能和收敛速度。学习率控制了每次迭代中模型参数更新的幅度。以

    2024年02月09日
    浏览(46)
  • 机器学习梯度下降法笔记

    梯度下降法(Gradient Descent)是一种常用的优化算法,用于在机器学习和深度学习中最小化或最大化一个函数的值。在机器学习中,梯度下降法常用于调整模型的参数,使得模型能够更好地拟合训练数据。 这个优化算法的基本思想是通过迭代的方式,不断调整参数的值,使得

    2024年02月15日
    浏览(40)
  • 机器学习:基于梯度下降算法的线性拟合实现和原理解析

    当我们需要寻找数据中的趋势、模式或关系时,线性拟合和梯度下降是两个强大的工具。这两个概念在统计学、机器学习和数据科学领域都起着关键作用。本篇博客将介绍线性拟合和梯度下降的基本原理,以及它们在实际问题中的应用。 线性拟合是一种用于找到数据集中线性

    2024年02月10日
    浏览(34)
  • 每天五分钟机器学习:梯度下降算法和正规方程的比较

    梯度下降算法和正规方程是两种常用的机器学习算法,用于求解线性回归问题。它们各自有一些优点和缺点,下面将分别对它们进行详细的讨论。 1. 梯度下降算法是一种迭代的优化算法,通过不断迭代调整参数来逼近最优解。它的基本思想是根据目标函数的梯度方向,沿着负

    2024年02月13日
    浏览(40)
  • 机器学习:基于梯度下降算法的逻辑回归实现和原理解析

    当涉及到二元分类问题时,逻辑回归是一种常用的机器学习算法。它不仅简单而且有效,通常是入门机器学习领域的第一步。本文将介绍逻辑回归的基本概念、原理、应用场景和代码示例。 逻辑回归是一种用于解决二元分类问题的统计学习方法。尽管其名称中包含\\\"回归\\\"一词

    2024年02月09日
    浏览(51)
  • 飞控学习笔记-梯度下降算法(gradient descent algorithm)

    笔记来源于文章:An_efficient_orientation_filter_for_inertial_and_inertial_magnetic_sensor_arrays 共轭: 四元数叉乘: 式(6)为方向余弦矩阵 欧拉角等式: w:角速度

    2024年02月16日
    浏览(39)
  • 人工智能基础_机器学习015_BGD批量梯度下降代码演示_在批量梯度下降中使用逆时衰减---人工智能工作笔记0055

    然后我们用代码来演示一下BGD批量梯度下降,首先启动jupyter notebook 然后我们新建一个文件 新建文件夹,然后新建一个python文件 然后我们这里用一元一次方程进行批量梯度下降. import numpy as np 导入数学计算包 X = np.random.rand(100,1)  `np.random.rand(100, 1)` 是NumPy库中的一个函数,用于

    2024年02月05日
    浏览(61)
  • 优化算法之梯度下降|Matlab实现梯度下降算法

    题目要求: 使用Matab实现梯度下降法 对于函数: min ⁡ f ( x ) = 2 x 1 2 + 4 x 2 2 − 6 x 1 − 2 x 1 x 2 min f(x)=2 x_{1}^{2}+4 x_{2}^{2}-6 x_{1}-2 x_{1} x_{2} min f ( x ) = 2 x 1 2 ​ + 4 x 2 2 ​ − 6 x 1 ​ − 2 x 1 ​ x 2 ​ 试采用 MATLAB实现最速下降法求解该问题, 给出具体的迭代过程、 最终优化结果、

    2024年02月16日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包