梯度下降的收敛速度

由 $L$-光滑性，对任意 $x, y$：$L(y) \le L(x) + \nabla L(x)^\top (y-x) + \dfrac{L}{2}\|y-x\|^2$。取 $y = \theta_{k+1} = \theta_k - \dfrac{1}{L}\nabla L(\theta_k)$、$x = \theta_k$，得到下降引理：$L(\theta_{k+1}) \le L(\theta_k) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2$。

由 $L$ 的凸性：$L(\theta_k) \le L(\theta^\star) + \nabla L(\theta_k)^\top(\theta_k - \theta^\star)$。将其加到下降引理上：$L(\theta_{k+1}) - L(\theta^\star) \le \nabla L(\theta_k)^\top(\theta_k - \theta^\star) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2$。

对右边配方：$\nabla L(\theta_k)^\top(\theta_k - \theta^\star) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2 = \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \left\|\theta_k - \theta^\star - \dfrac{1}{L}\nabla L(\theta_k)\right\|^2\right) = \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \|\theta_{k+1} - \theta^\star\|^2\right)$，因为 $\theta_{k+1} - \theta^\star = \theta_k - \theta^\star - \dfrac{1}{L}\nabla L(\theta_k)$。

于是 $L(\theta_{k+1}) - L(\theta^\star) \le \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \|\theta_{k+1} - \theta^\star\|^2\right)$。对 $k = 0, \dots, K-1$ 求和，右边望远镜式相消为 $\dfrac{L}{2}\left(\|\theta_0 - \theta^\star\|^2 - \|\theta_K - \theta^\star\|^2\right) \le \dfrac{L}{2}\|\theta_0 - \theta^\star\|^2$。

下降引理还表明 $L(\theta_k)$ 是非增的，因此 $L(\theta_K)$ 不超过 $L(\theta_1), \dots, L(\theta_K)$ 的平均值：$L(\theta_K) - L(\theta^\star) \le \dfrac{1}{K}\sum_{k=1}^K \left(L(\theta_k) - L(\theta^\star)\right) \le \dfrac{L\|\theta_0 - \theta^\star\|^2}{2K}$，这正是所要证明的界。