机器学习笔记之优化算法(十三)关于二次上界引理

这篇具有很好参考价值的文章主要介绍了机器学习笔记之优化算法(十三)关于二次上界引理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言

本节将介绍二次上界的具体作用以及它的证明过程

回顾:

利普希兹连续

Wolfe \text{Wolfe} Wolfe准则收敛性证明一节中简单介绍了利普希兹连续 ( Lipschitz Continuity ) (\text{Lipschitz Continuity}) (Lipschitz Continuity)。其定义对应数学符号表达如下:
∀ x , x ^ ∈ R n , ∃ L : s . t . ∣ ∣ f ( x ) − f ( x ^ ) ∣ ∣ ≤ L ⋅ ∣ ∣ x − x ^ ∣ ∣ \forall x,\hat x \in \mathbb R^n , \exist \mathcal L: \quad s.t. ||f(x) - f(\hat x)|| \leq \mathcal L \cdot ||x - \hat x|| x,x^Rn,L:s.t.∣∣f(x)f(x^)∣∣L∣∣xx^∣∣
如果函数 f ( ⋅ ) f(\cdot) f()满足利普希兹连续,对上式进行简单变换可得到:
不等式左侧可使用拉格朗日中值定理进行进一步替换。
∃ ξ ∈ ( x , x ^ ) ⇒ ∣ ∣ f ( x ) − f ( x ^ ) ∣ ∣ ∣ ∣ x − x ^ ∣ ∣ = f ′ ( ξ ) ≤ L \exist \xi \in (x,\hat x) \Rightarrow \frac{||f(x) - f(\hat x)||}{||x - \hat x||} = f'(\xi)\leq \mathcal L ξ(x,x^)∣∣xx^∣∣∣∣f(x)f(x^)∣∣=f(ξ)L
这意味着:在函数 f ( ⋅ ) f(\cdot) f()在定义域内的绝大部分点处的变化率存在上界,受到 L \mathcal L L的限制。

梯度下降法介绍

在梯度下降法铺垫:总体介绍一节中对梯度下降法进行了简单认识。首先,梯度下降法是一个典型的线搜索方法 ( Line Search Method ) (\text{Line Search Method}) (Line Search Method)。其迭代过程对应数学符号表示如下:
x k + 1 = x k + α k ⋅ P k x_{k+1} = x_k + \alpha_k \cdot \mathcal P_k xk+1=xk+αkPk

  • 其中 P k ∈ R n \mathcal P_k \in \mathbb R^n PkRn,描述数值解的更新方向,在梯度下降法中,它选择目标函数 f ( ⋅ ) f(\cdot) f() x k x_k xk处梯度的反方向 − ∇ f ( x k ) - \nabla f(x_k) f(xk)作为更新方向,也称最速下降方向
    P k = − ∇ f ( x k ) \mathcal P_k = -\nabla f(x_k) Pk=f(xk)
  • α k \alpha_k αk表示步长。基于步长的选择方式分为精确搜索非精确搜索两类。关于非精确搜索——通过迭代获取数值解序列并以此近似最优步长的方法详见:
    • Armijo \text{Armijo} Armijo准则
    • Glodstein \text{Glodstein} Glodstein准则
    • Wolfe \text{Wolfe} Wolfe准则

本节将介绍梯度下降法使用精确搜索求解最优步长,以及精确搜索的限制条件——二次上界引理

二次上界引理:介绍与作用

在求解梯度下降法的精确步长过程中,关于目标函数 f ( ⋅ ) f(\cdot) f(),在其定义域内可微的基础上增加一个条件:目标函数的梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()满足利普希兹连续
如果是梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) f()满足利普希兹连续,根据上面的格式,可以得到:
∇ 2 f ( ⋅ ) ≤ L \nabla^2 f(\cdot) \leq \mathcal L 2f()L
而二阶梯度描述的是梯度 ∇ f ( ⋅ ) \nabla f(\cdot) f()的变化量。这意味着:关于 ∇ f ( ⋅ ) \nabla f(\cdot) f()的变化情况不会过于剧烈。相反,如果 ∇ f ( ⋅ ) \nabla f(\cdot) f()的变化情况过于剧烈:即便迭代过程中极小的一次更新,对应函数结果的变化也极大,例如: f ( x ) = 1 x \begin{aligned}f(x) = \frac{1}{x}\end{aligned} f(x)=x1 x ∈ ( 0 , 1 ] x \in (0,1] x(0,1]区间内 ∇ 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 \cdot (y-x) + \frac{\mathcal L}{2}||y - x||^2 x,yRnf(y)f(x)+[f(x)]T(yx)+2L∣∣yx2
我们之前仅知道函数梯度 ∇ f ( ⋅ ) \nabla f(\cdot) f()的变化率存在上界对其进行约束,但可通过该结论求出该上界的精确结果
首先通过图像观察该结论各部分的具体意义:
机器学习笔记之优化算法(十三)关于二次上界引理,数学,机器学习,深度学习,二次上界,利普希兹连续,凸优化方法,梯度下降法
很明显,这仅是一个一维变量对应的函数结果 ( R ↦ R ) (\mathbb R \mapsto\mathbb R) (RR),其中蓝色虚线箭头表示 f ( y ) f(y) f(y)黑色虚线箭头表示 f ( x ) + [ ∇ f ( x ) ] T ⋅ ( y − x ) f(x) + [\nabla f(x)]^T \cdot (y - x) f(x)+[f(x)]T(yx)。在上述结论中,两者之间的差距(绿色实线)不会无限大下去,而是存在一个上界约束这个差距
f ( y ) − [ f ( x ) + [ ∇ f ( x ) ] T ⋅ ( y − x ) ] ≤ L 2 ∣ ∣ y − x ∣ ∣ 2 f(y) - [f(x) + [\nabla f(x)]^T \cdot (y-x)] \leq \frac{\mathcal L}{2}||y -x||^2 f(y)[f(x)+[f(x)]T(yx)]2L∣∣yx2
假如这个差距结果远远大于 L 2 ∣ ∣ y − x ∣ ∣ 2 \begin{aligned}\frac{\mathcal L}{2}||y -x||^2\end{aligned} 2L∣∣yx2。例如:
机器学习笔记之优化算法(十三)关于二次上界引理,数学,机器学习,深度学习,二次上界,利普希兹连续,凸优化方法,梯度下降法

从图像中可以明显看到,如果 f ( y ) f(y) f(y) f ( x ) + [ ∇ f ( x ) ] T ( y − x ) f(x) + [\nabla f(x)]^T (y - x) f(x)+[f(x)]T(yx)之间的差距过大的话,那么必然是 f ( y ) f(y) f(y)处的斜率与 f ( x ) f(x) f(x)处的斜率差距过大产生的结果。因此这个差距上界 L 2 ∣ ∣ y − x ∣ ∣ 2 \begin{aligned}\frac{\mathcal L}{2}||y - x||^2\end{aligned} 2L∣∣yx2本质上依然是约束 ∇ f ( ⋅ ) \nabla 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 \cdot (y-x) + \frac{\mathcal L}{2}||y - x||^2 x,yRnf(y)f(x)+[f(x)]T(yx)+2L∣∣yx2
既然二次上界引理对于 ∀ x , y ∈ R n \forall x,y \in \mathbb R^n x,yRn均成立,我们可以将 x , y x,y x,y视作:某次迭代步骤 k k k x k , x k + 1 x_k,x_{k+1} xk,xk+1
后续依然使用 x , y x,y x,y进行表示。
{ x ⇒ x k y ⇒ x k + 1 y = x + α k ⋅ P k \begin{cases} x \Rightarrow x_k \\ y \Rightarrow x_{k+1} \\ y = x + \alpha_k \cdot \mathcal P_k \end{cases} xxkyxk+1y=x+αkPk
由于 x ⇒ x k x \Rightarrow x_k xxk是上一次迭代步骤产生的位置,是已知项。这意味着:上述不等式右侧相当于关于变量 y ⇒ x k + 1 y \Rightarrow x_{k+1} yxk+1的一个二次函数。记作 ϕ ( y ) \phi(y) ϕ(y)
{ ϕ ( y ) ≜ f ( x ) + [ ∇ f ( x ) ] T ⋅ ( y − x ) + L 2 ∣ ∣ y − x ∣ ∣ 2 f ( y ) ≤ ϕ ( y ) \begin{cases} \phi(y) \triangleq f(x) + [\nabla f(x)]^T \cdot (y - x) + \frac{\mathcal L}{2}||y - x||^2 \\ \quad \\ f(y) \leq \phi(y) \end{cases} ϕ(y)f(x)+[f(x)]T(yx)+2L∣∣yx2f(y)ϕ(y)
由于关于 y y y的二次项 L 2 > 0 \begin{aligned}\frac{\mathcal L}{2} > 0\end{aligned} 2L>0,说明函数 ϕ ( 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 ) \phi(y) ϕ(y)关于 y y y求解梯度
    x x x相关的项均视作常数。
    ∇ ϕ ( y ) = 0 + ∇ f ( x ) ⋅ 1 + L 2 ⋅ 2 ⋅ ( y − x ) = ∇ f ( x ) + L ⋅ ( y − x ) \begin{aligned} \nabla \phi(y) & = 0 + \nabla f(x) \cdot 1 + \frac{\mathcal L}{2} \cdot 2 \cdot (y-x) \\ & = \nabla f(x) + \mathcal L \cdot (y-x) \end{aligned} ϕ(y)=0+f(x)1+2L2(yx)=f(x)+L(yx)
  • ∇ ϕ ( y ) ≜ 0 \nabla \phi(y) \triangleq 0 ϕ(y)0,有:
    y m i n = − ∇ f ( x ) L + x y_{min} = -\frac{\nabla f(x)}{\mathcal L} + x ymin=Lf(x)+x
    对应 ϕ ( y ) \phi(y) ϕ(y)最小值 min ⁡ ϕ ( y ) \min \phi(y) minϕ(y)有:
    min ⁡ ϕ ( y ) = ϕ ( y m i n ) = f ( x ) + [ ∇ f ( x ) ] T ⋅ ( − ∇ f ( x ) L ) + L 2 ⋅ [ − ∇ f ( x ) ] T [ − ∇ f ( x ) ] L 2 = f ( x ) − ∣ ∣ ∇ f ( x ) ∣ ∣ 2 2 L \begin{aligned} \min \phi(y) & = \phi(y_{min}) \\ & = f(x) + [\nabla f(x)]^T \cdot \left(-\frac{\nabla f(x)}{\mathcal L}\right) + \frac{\mathcal L}{2} \cdot \frac{[- \nabla f(x)]^T [- \nabla f(x)]}{\mathcal L^2}\\ & = f(x) - \frac{||\nabla f(x)||^2}{2\mathcal L} \end{aligned} minϕ(y)=ϕ(ymin)=f(x)+[f(x)]T(Lf(x))+2LL2[f(x)]T[f(x)]=f(x)2L∣∣∇f(x)2

y = x + α k ⋅ P k y = x + \alpha_k \cdot \mathcal P_k y=x+αkPk代入,观察:

  • P k \mathcal P_k Pk描述更新方向的向量对应的是负梯度方向 − ∇ f ( x ) -\nabla f(x) f(x)
  • 同理, α k \alpha_k αk对应 1 L \begin{aligned}\frac{1}{\mathcal L}\end{aligned} L1
    { y = x + α k ⋅ P k y m i n = x + 1 L ⋅ [ − ∇ f ( x ) ] ⇒ { α k = 1 L P k = − ∇ f ( x ) \begin{cases} \begin{aligned} y & = x + \alpha_k \cdot \mathcal P_k \\ y_{min} & = x + \frac{1}{\mathcal L} \cdot [-\nabla f(x)] \end{aligned} \end{cases} \Rightarrow \begin{cases} \begin{aligned}\alpha_k & = \frac{1}{\mathcal L} \\ \mathcal P_k & = - \nabla f(x) \end{aligned} \end{cases} yymin=x+αkPk=x+L1[f(x)] αkPk=L1=f(x)

但需要注意的是: f ( y ) ≤ ϕ ( y ) f(y) \leq \phi(y) f(y)ϕ(y),而 y m i n y_{min} ymin仅仅是 ϕ ( y ) \phi(y) ϕ(y)中的最小值。也就是说: y m i n y_{min} ymin f ( y ) f(y) f(y)取值上界中的最小值。在这种条件下,我们认为 α k = 1 L \begin{aligned}\alpha_k = \frac{1}{\mathcal L}\end{aligned} αk=L1就是可控制的最优步长。

二次上界引理证明过程

条件:函数 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 \cdot (y - x) + \frac{\mathcal L}{2}||y - x||^2 x,yRnf(y)f(x)+[f(x)]T(yx)+2L∣∣yx2

证明:
由于上述的 x , y ∈ R n x,y \in \mathbb R^n x,yRn定义域内任意取值,因而无法直接从条件中获取到 f ( x ) , f ( y ) f(x),f(y) f(x),f(y)之间的大小关系。这里不妨设: y > x y > x y>x,并引入辅助函数 G ( θ ) \mathcal G(\theta) G(θ)
x , y ∈ R n   ( y > x ) x,y \in \mathbb R^n \text{ } (y > x) x,yRn (y>x)确定的情况下,构建一个关于 θ \theta θ的函数,从而通过调节 θ \theta θ来获取 [ f ( x ) , f ( y ) ] [f(x),f(y)] [f(x),f(y)]之间的函数结果。
G ( θ ) = f [ θ ⋅ y + ( 1 − θ ) ⋅ x ] = f [ x + θ ( y − x ) ] θ ∈ [ 0 , 1 ] \begin{aligned} \mathcal G(\theta) & = f [\theta \cdot y + (1 - \theta) \cdot x] \\ & = f [x + \theta(y - x)] \quad \theta \in [0,1] \end{aligned} G(θ)=f[θy+(1θ)x]=f[x+θ(yx)]θ[0,1]
从而有: G ( 0 ) = f ( x ) ; G ( 1 ) = f ( y ) \mathcal G(0) = f(x);\mathcal G(1) = f(y) G(0)=f(x);G(1)=f(y)。将其与结论中的对应项进行替换
仅需证明‘替换’后的式子成立即可。
G ( 1 ) ≤ G ( 0 ) + [ ∇ f ( x ) ] T ⋅ ( y − x ) + L 2 ∣ ∣ y − x ∣ ∣ 2 ⇒ G ( 1 ) − G ( 0 ) − [ ∇ f ( x ) ] T ⋅ ( y − x ) ≤ L 2 ∣ ∣ y − x ∣ ∣ 2 \begin{aligned} & \quad \quad \mathcal G(1) \leq \mathcal G(0) + [\nabla f(x)]^T \cdot (y - x) + \frac{\mathcal L}{2} ||y - x||^2 \\ & \Rightarrow \mathcal G(1) - \mathcal G(0) - [\nabla f(x)]^T \cdot (y - x) \leq \frac{\mathcal L}{2} ||y - x||^2 \end{aligned} G(1)G(0)+[f(x)]T(yx)+2L∣∣yx2G(1)G(0)[f(x)]T(yx)2L∣∣yx2
观察不等式左侧
使用牛顿-莱布尼兹公式,可以将 G ( 1 ) − G ( 0 ) \mathcal G(1) - \mathcal G(0) G(1)G(0)表示成如下形式:
G ( 1 ) − G ( 0 ) = G ( θ ) ∣ 0 1 = ∫ 0 1 G ′ ( θ ) d θ \mathcal G(1) - \mathcal G(0) = \mathcal G(\theta) |_{0}^1 = \int_{0}^1 \mathcal G'(\theta) d\theta G(1)G(0)=G(θ)01=01G(θ)dθ
关于项 [ ∇ f ( x ) ] T ⋅ ( y − x ) [\nabla f(x)]^T \cdot (y - x) [f(x)]T(yx),同样可以使用定积分的形式进行表示。其中 [ ∇ f ( x ) ] T ⋅ ( y − x ) [\nabla f(x)]^T \cdot (y - x) [f(x)]T(yx)中不含 θ \theta θ,被视作常数。
[ ∇ f ( x ) ] T ⋅ ( y − x ) = [ ∇ f ( x ) ] T ⋅ ( y − x ) ⋅ 1 = [ ∇ f ( x ) ] T ⋅ ( y − x ) ⋅ θ ∣ 0 1 = [ ∇ f ( x ) ] T ⋅ ( y − x ) ⋅ ∫ 0 1 1 d θ = ∫ 0 1 [ ∇ f ( x ) ] T ⋅ ( y − x ) d θ \begin{aligned} [\nabla f(x)]^T \cdot(y - x) & = [\nabla f(x)]^T \cdot (y - x) \cdot 1 \\ & = [\nabla f(x)]^T \cdot (y - x) \cdot \theta |_0^1 \\ & = [\nabla f(x)]^T \cdot (y - x) \cdot \int_0^1 1 d\theta \\ & = \int_{0}^1 [\nabla f(x)]^T \cdot (y - x) d\theta \end{aligned} [f(x)]T(yx)=[f(x)]T(yx)1=[f(x)]T(yx)θ01=[f(x)]T(yx)011dθ=01[f(x)]T(yx)dθ
至此,不等式左侧可表示为:
I l e f t = ∫ 0 1 G ′ ( θ ) d θ − ∫ 0 1 [ ∇ f ( x ) ] T ⋅ ( y − x ) d θ = ∫ 0 1 { [ ∇ f ( x + θ ⋅ ( y − x ) ) ] T ⋅ ( y − x ) − [ ∇ f ( x ) ] T ⋅ ( y − x ) } d θ \begin{aligned} \mathcal I_{left} & = \int_{0}^1 \mathcal G'(\theta) d\theta - \int_{0}^1 [\nabla f(x)]^T \cdot (y - x) d\theta \\ & = \int_0^1 \left \{[\nabla f(x + \theta \cdot (y - x))]^T\cdot (y - x) - [\nabla f(x)]^T \cdot (y - x) \right\} d\theta \end{aligned} Ileft=01G(θ)dθ01[f(x)]T(yx)dθ=01{[f(x+θ(yx))]T(yx)[f(x)]T(yx)}dθ
提出公共部分: y − x y - x yx,将剩余部分进行合并
I l e f t = ∫ 0 1 { ∇ f [ x + θ ⋅ ( y − x ) ] − ∇ f ( x ) } T ⋅ ( y − x ) d θ \mathcal I_{left} = \int_{0}^1 \left\{\nabla f[x + \theta \cdot (y - x)] - \nabla f(x)\right\}^T \cdot (y - x) d\theta Ileft=01{f[x+θ(yx)]f(x)}T(yx)dθ
观察积分号内的项,其本质上是向量 ∇ f [ x + θ ⋅ ( y − x ) ] − ∇ f ( x ) \nabla f[x + \theta \cdot (y - x)] - \nabla f(x) f[x+θ(yx)]f(x)与向量 y − x y - x yx的内积结果。因而有:
不等式满足的原因: cos ⁡ θ ∈ [ − 1 , 1 ] \cos \theta \in [-1,1] cosθ[1,1]
{ ∇ f [ x + θ ⋅ ( y − x ) ] − ∇ f ( x ) } T ⋅ ( y − x ) = ∣ ∣ ∇ f [ x + θ ⋅ ( y − x ) ] − ∇ f ( x ) ∣ ∣ ⋅ ∣ ∣ y − x ∣ ∣ ⋅ cos ⁡ θ ≤ ∣ ∣ ∇ f [ x + θ ⋅ ( y − x ) ] − ∇ f ( x ) ∣ ∣ ⋅ ∣ ∣ y − x ∣ ∣ \begin{aligned} \left\{\nabla f[x + \theta \cdot (y - x)] - \nabla f(x)\right\}^T \cdot (y - x) & = ||\nabla f[x + \theta \cdot (y - x)] - \nabla f(x)|| \cdot ||y - x|| \cdot \cos \theta \\ & \leq ||\nabla f[x + \theta \cdot (y - x)] - \nabla f(x)|| \cdot ||y - x|| \end{aligned} {f[x+θ(yx)]f(x)}T(yx)=∣∣∇f[x+θ(yx)]f(x)∣∣∣∣yx∣∣cosθ∣∣∇f[x+θ(yx)]f(x)∣∣∣∣yx∣∣
将该不等式带回 I l e f t \mathcal I_{left} Ileft,有:
I l e f t ≤ ∫ 0 1 ∣ ∣ ∇ f [ x + θ ⋅ ( y − x ) ] − ∇ f ( x ) ∣ ∣ ⋅ ∣ ∣ y − x ∣ ∣ d θ \mathcal I_{left} \leq \int_0^1 ||\nabla f[x + \theta \cdot (y - x)] - \nabla f(x)|| \cdot ||y - x|| d\theta Ileft01∣∣∇f[x+θ(yx)]f(x)∣∣∣∣yx∣∣dθ
由于 f ( ⋅ ) f(\cdot) f()满足利普希兹连续,因而有:
其中 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ[0,1],因而可以将其从范数符号中提出来。
∣ ∣ ∇ f [ x + θ ⋅ ( y − x ) ] − ∇ f ( x ) ∣ ∣ ≤ L ⋅ ∣ ∣ x + θ ⋅ ( y − x ) − x ∣ ∣ = L ⋅ θ ⋅ ∣ ∣ y − x ∣ ∣ ||\nabla f[x + \theta \cdot (y - x)] - \nabla f(x)|| \leq \mathcal L \cdot ||x + \theta \cdot (y -x) - x|| = \mathcal L \cdot \theta \cdot ||y - x|| ∣∣∇f[x+θ(yx)]f(x)∣∣L∣∣x+θ(yx)x∣∣=Lθ∣∣yx∣∣
整理有:
I l e f t ≤ ∫ 0 1 L ⋅ θ ⋅ ∣ ∣ y − x ∣ ∣ 2 d θ \mathcal I_{left} \leq \int_0^1 \mathcal L \cdot \theta \cdot ||y - x||^2 d\theta Ileft01Lθ∣∣yx2dθ
又因为 L , ∣ ∣ y − x ∣ ∣ 2 \mathcal L,||y - x||^2 L,∣∣yx2 θ \theta θ无关,因而从积分号中提出:
I l e f t ≤ L ⋅ ∣ ∣ y − x ∣ ∣ 2 ⋅ ∫ 0 1 θ d θ = L ⋅ ∣ ∣ y − x ∣ ∣ 2 ⋅ 1 2 θ 2 ∣ 0 1 = L 2 ⋅ ∣ ∣ y − x ∣ ∣ 2 = I r i g h t \begin{aligned} \mathcal I_{left} & \leq \mathcal L \cdot ||y - x||^2 \cdot \int_0^1 \theta d\theta \\ & = \mathcal L \cdot ||y - x||^2 \cdot \frac{1}{2} \theta^2|_0^1 \\ & = \frac{\mathcal L}{2} \cdot ||y - x||^2 \\ & = \mathcal I_{right} \end{aligned} IleftL∣∣yx201θdθ=L∣∣yx221θ201=2L∣∣yx2=Iright
证毕。

相关参考:
【优化算法】梯度下降法-二次上界文章来源地址https://www.toymoban.com/news/detail-649862.html

到了这里,关于机器学习笔记之优化算法(十三)关于二次上界引理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 机器学习笔记之优化算法(二十)牛顿法与正则化

    本节我们介绍 经典牛顿法 在训练 神经网络 过程中的迭代步骤,并介绍 正则化 在牛顿法中的使用逻辑。 经典牛顿法 自身是一个典型的 线搜索方法 ( Line-Search Method ) (text{Line-Search Method}) ( Line-Search Method ) 。它的迭代过程使用 数学符号 表示如下: x k + 1 = x k + α k ⋅ P k x_

    2024年02月11日
    浏览(43)
  • 机器学习笔记之优化算法(十)梯度下降法铺垫:总体介绍

    从本节开始,将介绍 梯度下降法 ( Gradient Descent,GD ) (text{Gradient Descent,GD}) ( Gradient Descent,GD ) 。 线搜索方法作为一种常见优化问题的 策略 ,该方法的特点是: 其迭代过程中,将 数值解 的方向和步长分开执行 。对应 数学符号 表达如下: 其中 P k mathcal P_k P k ​ 是一个向量

    2024年02月13日
    浏览(41)
  • 机器学习笔记之优化算法(十五)Baillon Haddad Theorem简单认识

    本节将简单认识 Baillon Haddad Theorem text{Baillon Haddad Theorem} Baillon Haddad Theorem ( 白老爹定理 ),并提供相关证明。 如果 函数 f ( ⋅ ) f(cdot) f ( ⋅ ) 在其定义域内 可微 ,并且是 凸函数 ,则存在如下 等价 条件 : 以下几个条件之间相互等价。 关于 f ( ⋅ ) f(cdot) f ( ⋅ ) 的 梯度

    2024年02月12日
    浏览(56)
  • 机器学习笔记之优化算法(十九)经典牛顿法的收敛性分析

    上一节整体介绍了 经典牛顿法 ,并讨论了其更新方向 P k mathcal P_k P k ​ 是否为 下降方向 。本节将对 经典牛顿法 在迭代过程中的收敛性 进行分析。 在这些迭代算法中,我们关注的重点在于 算法在迭代过程中 是否收敛 ,以及它的 收敛速度 。 Wolfe text{Wolfe} Wolfe 准则的收

    2024年02月11日
    浏览(42)
  • 机器学习笔记值优化算法(十四)梯度下降法在凸函数上的收敛性

    本节将介绍 梯度下降法 在 凸函数 上的收敛性。 收敛速度:次线性收敛 关于 次线性收敛 ,分为两种 判别 类型: R mathcal R R -次线性收敛与 Q mathcal Q Q -次线性收敛。而次线性收敛的 特点 是: 随着迭代次数的增加,相邻迭代步骤产生的目标函数结果 f ( x k ) , f ( x k + 1 ) f

    2024年02月13日
    浏览(49)
  • 机器学习笔记之优化算法(十七)梯度下降法在强凸函数的收敛性分析

    上一节介绍并证明了: 梯度下降法 在 强凸函数 上的收敛速度满足 Q mathcal Q Q -线性收敛 。 本节将介绍:在 更强 的条件下:函数 f ( ⋅ ) f(cdot) f ( ⋅ ) 在其定义域内 二阶可微 , 梯度下降法 在 f ( ⋅ ) f(cdot) f ( ⋅ ) 上的收敛速度存在什么样的结论。 关于 梯度下降法 在

    2024年02月12日
    浏览(47)
  • 机器学习笔记之优化算法(七)线搜索方法(步长角度;非精确搜索;Wolfe Condition)

    上一节介绍了 Glodstein text{Glodstein} Glodstein 准则 ( Glodstein Condition ) (text{Glodstein Condition}) ( Glodstein Condition ) 及其弊端。本节将针对该弊端,介绍 Wolfe text{Wolfe} Wolfe 准则 ( Wolfe Condition ) (text{Wolfe Condition}) ( Wolfe Condition ) 。 Armijo text{Armijo} Armijo 准则及其弊端 在当前迭代步骤

    2024年02月14日
    浏览(44)
  • 机器学习笔记之优化算法(十六)梯度下降法在强凸函数上的收敛性证明

    本节将介绍: 梯度下降法 在 强凸函数 上的收敛性,以及 证明过程 。 凸函数与强凸函数 关于 凸函数 的定义使用 数学符号 表示如下: ∀ x 1 , x 2 ∈ R n , ∀ λ ∈ ( 0 , 1 ) ⇒ f [ λ ⋅ x 2 + ( 1 − λ ) ⋅ x 1 ] ≤ λ ⋅ f ( x 2 ) + ( 1 − λ ) ⋅ f ( x 1 ) forall x_1,x_2 in mathbb R^n, forall

    2024年02月11日
    浏览(41)
  • 【现代机器人学】学习笔记十三:配套代码解析

    最近一直忙于工作,每天都在写一些业务代码。而目前工程中的技术栈并没有使用旋量这一套机器人理论系统,因此时间长了自己都忘记了。 于是决定把这本书配套的代码内容也过一遍,查漏补缺,把这本书的笔记内容完结一下。 代码来源于github:https://github.com/NxRLab/Moder

    2024年02月12日
    浏览(41)
  • 机器学习笔记 - 关于GPT-4的一些问题清单

            据报道,GPT-4 的系统由八个模型组成,每个模型都有 2200 亿个参数。GPT-4 的参数总数估计约为 1.76 万亿个。         近年来,得益于 GPT-4 等高级语言模型的发展, 自然 语言处理(NLP) 取得了长足的进步。 凭借其前所未有的规模和能力, GPT-4 为语言 AI​​设立

    2024年02月13日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包