Tốc độ hội tụ của gradient descent

Do tính $L$-trơn, với mọi $x, y$: $L(y) \le L(x) + \nabla L(x)^\top (y-x) + \dfrac{L}{2}\|y-x\|^2$. Đặt $y = \theta_{k+1} = \theta_k - \dfrac{1}{L}\nabla L(\theta_k)$ và $x = \theta_k$ ta được bổ đề giảm dần: $L(\theta_{k+1}) \le L(\theta_k) - \dfrac{1}{2L}\|\nabla L(\theta_k)\|^2$.

Do tính lồi của $L$: $L(\theta_k) \le L(\theta^\star) + \nabla L(\theta_k)^\top(\theta_k - \theta^\star)$. Cộng vào bổ đề giảm dần: $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$.

Hoàn thiện bình phương ở vế phải: $\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)$, vì $\theta_{k+1} - \theta^\star = \theta_k - \theta^\star - \dfrac{1}{L}\nabla L(\theta_k)$.

Vậy $L(\theta_{k+1}) - L(\theta^\star) \le \dfrac{L}{2}\left(\|\theta_k - \theta^\star\|^2 - \|\theta_{k+1} - \theta^\star\|^2\right)$. Cộng dồn bất đẳng thức này với $k = 0, \dots, K-1$, vế phải rút gọn kính viễn vọng thành $\dfrac{L}{2}\left(\|\theta_0 - \theta^\star\|^2 - \|\theta_K - \theta^\star\|^2\right) \le \dfrac{L}{2}\|\theta_0 - \theta^\star\|^2$.

Bổ đề giảm dần cũng cho thấy $L(\theta_k)$ không tăng, nên $L(\theta_K)$ nhỏ hơn hoặc bằng trung bình của $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}$, đúng bằng chặn cần chứng minh.