First-Order and Stochastic Optimization Methods for Machine Learning II: Subgradient Descent, Mirror Descent and Accelerated Gradient DescentTextbook
Gradient descent's convergence rate for a general smooth convex problem is in the function-value gap; Nemirovski and Yudin (1983) proved that no first-order method can do better than is achievable, and Nesterov (1983, 1988, 2004) constructed the first method attaining it — the accelerated (or "fast") gradient method. For thirty years this…