勾配降下法の収束速度

$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}$ となり、まさに主張された評価式が得られる。