梯度下降收敛速度

1. 梯度下降收敛速度

梯度下降迭代更新公式

$$x_{k+1}=x_k-t▽f(x_k)$$

$\bullet$根据Lipschitz连续

$$\begin{array}{r}f(x_{k+1})\le f(x_k)+▽f(x_k)|x_{k+1}-x_k|+\frac{L}{2}||x_{k+1}-x_k|{|}^2\end{array}$$ $$\le f(x_k)-t||▽f(x_k)|{|}^2+\frac{L{t}^2}{2}||▽f(x_k)|{|}^2$$

令$L=\frac{1}{t}$

$$f(x_{k+1})\le f(x_k)-\frac{t}{2}||▽f(x_k)|{|}^2$$

根据一阶导数性质,替换$f(x_k)$为$f(x^{\ast })$：

$$f(x^{\ast })\ge f(x_k)+▽f(x_k)(x^{\ast }-x_k)$$ $$f(x_k)\le f(x^{\ast })-▽f(x_k)(x^{\ast }-x_k)$$ $$\therefore f(x_{k+1})-f(x^{\ast })\le ▽f(x_k)(x_k-x^{\ast })-\frac{t}{2}||▽f(x_k)|{|}^2$$

$\bullet$不等式右边由以下推导

$$\begin{array}{rl}||x_{k+1}-x^{\ast }|{|}^2& =||x_k-t▽f(x_k)-x^{\ast }|{|}^2\\ & =||x_k-x^{\ast }|{|}^2-2t▽f(x_k)(x_k-x^{\ast })+t^2||▽f(x_k)|{|}^2\\ & =||x_k-x^{\ast }|{|}^2-2t(▽f(x_k)(x_k-x^{\ast })-\frac{t}{2}||▽f(x_k)|{|}^2)\\ ▽f(x_k)(x_k-x^{\ast })-\frac{t}{2}||▽f(x_k)|{|}^2& =\frac{1}{2t}(||x_k-x^{\ast }|{|}^2-||x_{k+1}-x^{\ast }|{|}^2)\end{array}$$ $$\therefore f(x_{k+1})-f(x^{\ast })\le \frac{1}{2t}(||x_k-x^{\ast }|{|}^2-||x_{k+1}-x^{\ast }|{|}^2)$$

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

$\bullet$对每步迭代求和

$$\begin{array}{rl}\sum _{i=1}^K(f(x_i)-f(x^{\ast }))& \le \frac{1}{2t}(||x_0-x^{\ast }|{|}^2-||x_K-x^{\ast }|{|}^2)\\ & \le \frac{1}{2t}||x_0-x^{\ast }|{|}^2\end{array}$$

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

$$\begin{array}{rl}f(x_k)-f(x^{\ast })& \le f(x_{k-1})-f(x^{\ast })\le ...f(x_0)-f(x^{\ast })\\ \\ f(x_k)-f(x^{\ast })& \le \frac{1}{K}\sum _{i=1}^K(f(x_i)-f(x^{\ast }))\\ & \le \frac{1}{2tK}||x_0-x^{\ast }|{|}^2=\frac{C}{K}\end{array}$$

$\bullet$如果想获得精度为$ϵ$的解，那么：

$$f(x_k)-f(x^{\ast })=\frac{C}{K}\le ϵ$$ $$K\ge \frac{C}{ϵ}$$

即需要迭代$O(\frac{1}{ϵ})$次，收敛速度为$O(K)$
注：步长$t=\frac{1}{L}$.上文中直接用

2. 次梯度下降收敛速度

$\bullet$由凸函数一阶性质：

$$f(x^{\ast })\ge f(x_k)+▽f(x_k)(x_{k+1}-x_k)$$ $$f(x_k)-f(x^{\ast })\le ▽f(x_k)(x_k-x_{k+1})$$

$\bullet$【同上】

$$\begin{array}{rl}||x_{k+1}-x^{\ast }|{|}^2& =||x_k-t▽f(x_k)-x^{\ast }|{|}^2\\ \\ & =||x_k-x^{\ast }|{|}^2-2t▽f(x_k)(x_k-x^{\ast })+t^2||▽f(x_k)|{|}^2\end{array}$$ $$2t▽f(x_k)(x_k-x^{\ast })=||x_k-x^{\ast }|{|}^2-||x_{k+1}-x^{\ast }|{|}^2+t^2||▽f(x_k)|{|}^2$$

$\bullet$【同上】求和,其中根据lipschitz有$▽f(x)\le G$：

$$\begin{array}{r}\sum _{i=1}^K(f(x_i)-f(x^{\ast }))\le \frac{||x_0-x^{\ast }|{|}^2+t^2{G}^{2}k}{2t}\end{array}$$ $$f(x_k)-f(x^{\ast })\le \frac{1}{k}\sum _{i=1}^k(f(x_i)-f(x^{\ast }))=\frac{||x_0-x^{\ast }|{|}^2+t^2{G}^{2}k}{2tk}$$

$\bullet$$ϵ-$最优解：

$$\frac{R^2}{2tk}+\frac{t{G}^2}{2}\le ϵ$$

令两部分都等于$\frac{ϵ}{2}$,那么：

$$\begin{array}{rl}t& =\frac{ϵ}{G^2}\\ k& =\frac{R^2}{ϵt}=\frac{G^2{R}^2}{2{ϵ}^2}\end{array}$$

收敛速度为$O(\frac{1}{{ϵ}^2})$

3. 总结

	适用问题	Lipschitz约束	$f(x_k)-f(x^{\ast })\le$	步长$t$	收敛速度
$GD$	凸函数且可导	$|f^{\prime }(x)-f^{\prime }(y)|\le L|x-y|$	$\frac{||x_0-x^{\ast }|{|}^2}{2tk}$	$\frac{1}{L}$	$O(\frac{1}{ϵ})$
$subGD$	凸函数不可导	$|f(x)-f(y)|\le G|x-y|$	$\frac{||x_0-x^{\ast }|{|}^2+t^2{G}^{2}k}{2tk}$	$\frac{ϵ}{G^2}$	$O(\frac{1}{{ϵ}^2})$