Entropy-Smooth Convex Optimization Cannot Be Accelerated

Abstract: We prove an Q(L/T) lower bound for first-order optimization of convex functions smooth relative to negative entropy on the simplex, showing mirror descent is nearly optimal and acceleration is generally impossible.
Unlike prior results, our prox-function is standard rather than pathological.
We extend the same non-acceleration result to quantum optimization over spectrahedra.