Accelerated Gradient Descent

Efficiency Estimation

可见，对于上面两种问题类（强凸+利普希茨连续、凸+利普希茨连续），使用梯度下降法进行优化，上界和下界是有差距的。

上界就是用 vanilla gradient descent 实现的。下界就会用到更好的方法。