Praneeth Netrapalli

Abstract We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function f:R^n->R and its (sub)gradient. Our goal is to find an eps-approximate minimum of f starting from a point that is distance at most R from the true minimum. If f is G-Lipschitz, then the classic gradient descent algorithm solves this problem with O((GR/eps)^2) queries. Importantly, the number of queries is independent of the dimension n and gradient descent is optimal in this regard: No deterministic or randomized algorithm can achieve better complexity that is still independent of the dimension n. In this paper we reprove the matching randomized lower bound using a simpler argument than previous lower bounds. We then show that although the function family used in the lower bound is hard for randomized algorithms, it can be solved quadratically faster using quantum queries. We then show an improved lower bound against quantum algorithms using a different set of instances and establish our main result that in general even quantum algorithms need Omega((GR/eps)^2) queries to solve the problem. Hence there is no quantum speedup over gradient descent for black-box first-order convex optimization without further assumptions on the function family. In our second result, we consider the case of smooth functions. Here the optimal classical algorithm is not gradient descent, but accelerated gradient descent, which is also known to be optimal among all classical (randomized) algorithms. We show a matching quantum lower bound, showing that there is no quantum speedup over accelerated gradient descent either.