Processing math: 19%

梯度下降收敛速度

1. 梯度下降收敛速度

梯度下降迭代更新公式

xk+1=xktf(xk)

根据Lipschitz连续

f(xk+1)f(xk)+f(xk)|xk+1xk|+L2||xk+1xk||2 f(xk)t||f(xk)||2+Lt22||f(xk)||2

L=1t

f(xk+1)f(xk)t2||f(xk)||2

根据一阶导数性质,替换f(xk)f(x)

f(x)f(xk)+f(xk)(xxk) f(xk)f(x)f(xk)(xxk)

不等式右边由以下推导

||xk+1x||2=||xktf(xk)x||2=||xkx||22tf(xk)(xkx)+t2||f(xk)||2=||xkx||22t(f(xk)(xkx)t2||f(xk)||2)f(xk)(xkx)t2||f(xk)||2=12t(||xkx||2||xk+1x||2) f(xk+1)f(x)12t(||xkx||2||xk+1x||2)

【注:mirror descent“三点”性质可由该式推导出】

对每步迭代求和

i=1K(f(xi)f(x))12t(||x0x||2||xKx||2)12t||x0x||2

迭代完的位置与最优值之间的差值可以忽略不计,第一项占主导位置。

f(xk)f(x)f(xk1)f(x)...f(x0)f(x)f(xk)f(x)1Ki=1K(f(xi)f(x))12tK||x0x||2=CK

如果想获得精度为ϵ的解,那么:

f(xk)f(x)=CKϵ KCϵ

即需要迭代O(1ϵ)次,收敛速度为O(K)
注:步长t=1L.上文中直接用

2. 次梯度下降收敛速度

由凸函数一阶性质

f(x)f(xk)+f(xk)(xk+1xk) f(xk)f(x)f(xk)(xkxk+1)

【同上】

||xk+1x||2=||xktf(xk)x||2=||xkx||22tf(xk)(xkx)+t2||f(xk)||2 2tf(xk)(xkx)=||xkx||2||xk+1x||2+t2||f(xk)||2

【同上】求和,其中根据lipschitz有f(x)G

i=1K(f(xi)f(x))||x0x||2+t2G2k2t f(xk)f(x)1ki=1k(f(xi)f(x))=||x0x||2+t2G2k2tk

ϵ最优解:

R22tk+tG22ϵ

令两部分都等于ϵ2,那么:

t=ϵG2k=R2ϵt=G2R22ϵ2

收敛速度为O(1ϵ2)

3. 总结

  适用问题 Lipschitz约束 f(xk)f(x) 步长t 收敛速度
GD 凸函数且可导 |f(x)f(y)|L|xy| ||x0x||22tk 1L O(1ϵ)
subGD 凸函数不可导 |f(x)f(y)|G|xy| ||x0x||2+t2G2k2tk ϵG2 O(1ϵ2)



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 近端梯度下降
  • Variance Reduction
  • 梯度下降与镜像下降线性耦合
  • Primal Dual Problem
  • 差分隐私-三种机制