次梯度算法的收敛速度证明

次梯度算法的执行步骤如下：
首先，任取$x_0$属于$f$的定义域，再任取一个正实数列$h_k$满足。接着，对于$k$迭代，每一次求出$f$在$x_k$处的一个次梯度$g(x_k)$，如果$\|g(x_k)\|=0$显然$x_k$已经是最值点，直接结束，而如果$\|g(x_k)\|>0$，那么取

$$x_{k+1}=x_k-h_k\frac{g(x_k)}{\|g(x_k)\|}.$$ 整个过程中一直要记录$f(x_i)$的前缀最小值。
现在说明此算法的收敛性。

下文用$x^*$表示真实最小值点。

首先要注意到，由于$f(x^*)-f(x)\geq g(x)(x^*-x)$，故$g(x)(x-x^*)\geq0$。

定理设凸函数$f$满足$\forall x,y,|f(x)-f(y)|\leq M\|x-y\|$，且$x_0\in B_2(x^*,R)$那么

$$\bigwedge_{i=0}^kf(x_i)-f(x^*)\leq M\frac{R^2+\sum_{i=0}^kh_i^2}{2\sum_{i=0}^kh_i}.$$ 证明：
记$r_i:=\|x_i-x^*\|$。那么 $$r_{i+1}^2=\bigg\|x_i-h_i\frac{g(x_i)}{\|g(x_i)\|}-x^*\bigg\|^2=r_i^2+h_i^2-2h_iv_i.$$ 将上式对$i=0,...,k$求和可知 $$r_0^2+\sum_{i=0}^kh_i^2=2\sum_{i=0}^kh_iv_i+r_{k+1}^2\geq2v_k^*\sum_{i=0}^kh_i,$$ 其中$v_k^*$表示$\bigwedge_{i=0}^kv_i$。于是 $$v_k^*\leq\frac{R^2+\sum_{i=0}^kh_i^2}{2\sum_{i=0}^kh_i},$$ 注意其中$v_i=(x_i-x^*)\frac{g(x_i)}{\|g(x_i)\|}$且非负。现在设$y_i:=\frac{g(x_i)}{\|g(x_i)\|}v_i+x^*$，那么$g(x_i)(y_i-x_i)=0$且$\|y_i-x^*\|=v_i$。于是 $$f(y_i)\geq f(x_i)+g(x_i)(y_i-x_i)=f(x_i),$$ 从而 $$f(x_i)-f(x^*)\leq f(y_i)-f(x^*)\leq Mv_i,$$ 再用上$v_k^*\leq\frac{R^2+\sum_{i=0}^kh_i^2}{2\sum_{i=0}^kh_i}$即可知道 $$\exists i\in[0,k],f(x_i)-f(x^*)\leq M\frac{R^2+\sum_{i=0}^kh_i^2}{2\sum_{i=0}^kh_i}.$$ 证毕。

现在考虑怎么加速，考虑目标误差限为$T$，那么如果直接按照上文所给结论，$h$应该取$\frac{T}{M}$，而步数将达到$\frac{M^2R^2}{T^2}$，这非常慢。下文中的叙述将非常不严格，有空再完成证明：
实际上，每一次取$h$为$\frac{T}{\|g(x_k)\|}$即可，因为实际上$M$是作为$\|g(x_k)\|$的上界存在的，而没必要每一步都用上界作为依据。