No quantum speedup over gradient descent for non-smooth convex optimization

Ankit Garg, Robin Kothari, Praneeth Netrapalli +1

We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function $f:{\mathbb{R}}^n\to \mathbb{R}$ and its (sub)gradient. O…