A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent

Sahar Karimi, Stephen Vavasis

Nesterov's accelerated gradient (AG) method for minimizing a smooth strongly convex function $f$ is known to reduce $f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })$ by a factor of $\epsilon \in (0,1)$ after $k=…