凸优化笔记17：次梯度下降

对于光滑函数，我们可以用梯度下降法，并且证明了取不同的步长，可以得到次线性收敛，如果加上强凸性质，还可以得到线性收敛速度。那如果现在对于不可导的函数，我们就只能沿着次梯度下降，同样会面临步长的选择、方向的选择、收敛性分析等问题。

1. 收敛性分析

次梯度下降的一般形式为 $$x^{(k)}=x^{(k-1)}-t_k{g}^{(k-1)},k=1,2,\dots g\in \partial f(x^{(k-1)})$$ 一般有 3 种步长的选择方式：

1. fix step： $t_k$ 为常数
2. fix length：$t_k{\Vert g^{(k-1)}\Vert }_2={\Vert x^{(k)}-x^{(k-1)}\Vert }_2$ 为常数
3. diminishing：$t_k\to 0,\sum _{k=1}^{\mathrm{\infty }}{t}_k=\mathrm{\infty }$

要证明这几种方法的收敛性，需要先引入 Lipschitz continuous 假设，即 $$ 这等价于 $$ 对任意 $$ 都成立。

在分析收敛性之前，我们需要引入一个非常重要的式子:arrow_down:！！！在后面的分析中会一直用到： $$ 那么如果定义 $$，就有 $$ 根据上面的式子，就可以得到对于

Fixed step size：$$ $$ Fixed step length：$$ $$ 这两个式子中的第一项都随着 $$ 增大而趋于 0，但第二项却没有办法消掉，也就是与最优解的误差不会趋于 0。并且他们有一个微妙的不同点在于，fixed step size 情况下 $$，$$ 一般是较大的。

Diminishing step size：$$ $$ 可以证明，$$，因此 $$ 会收敛于 $$。

下面看几幅图片，对于优化问题 $$

Fixed step length	Diminishing step size

前面考虑了固定步长的情况，假设现在我们固定总的迭代次数为 $$，可不可以优化步长 $$ 的大小来尽可能使 $$ 接近 $$ 呢？这实际上可以表示为优化问题 $$ 其中 $$，那么最优步长为 $$，此时 $$ 因此收敛速度为 $$，对比之前光滑函数的梯度下降，收敛速度为 $$。

我们对前面的收敛速度并不满意，如果有更多的信息，比如已知最优解 $$ 的大小，能不能改进收敛速度呢？根据前面的式子，有 $$ 这实际上是关于 $$ 的一个二次函数，因此可以取 $$，就可以得到 $$ 可见还是没有改进收敛速度。

如果引入强凸性质呢？如果假设满足 $$ 强凸，则 $$，可以取 $$，那么就可以得到 $$