Convex Optimization Is Free When Accuracy Is Expensive

Arthur Paing, Arthur Jacot

This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like ${\delta }^{-\gamma }$ in the ac…