Entropy-Smooth Convex Optimization Cannot Be Accelerated

We prove an Omega(L/T) lower bound for the convergence rate of minimization in the class of functions that are convex and L-smooth relative to negative entropy on the standard d-simplex, valid for every first-order method when d = Omega(T2). In particular, this shows that mirror descent is optimal up to a logarithmic factor in this class. This may be surprising due to the fact that accelerated methods are readily available under the assumption of smoothness in ℓ1-norm. While Dragomir et al. (Mathematical Programming, 2022) have already showed that acceleration might be impossible under relative smoothness, their prox-function is pathological and constructed together with the hard instance. In contrast, we show non-acceleration for a specific prox-function with particularly favorable structure. We also extend the result to the quantum setting, proving the same lower bound in the class of functions L-smooth relative to negative von Neumann entropy on the spectrahedron of d × d Hermitian positive-semidefinite matrices with unit trace.