Entropy-Smooth Convex Optimization Cannot Be Accelerated
This resolves a question about the possibility of acceleration under relative smoothness for a natural prox-function, providing a strong negative result for optimization theory.
The authors prove an Ω(L/T) lower bound for the convergence rate of first-order methods on convex functions that are L-smooth relative to negative entropy on the simplex, showing that mirror descent is optimal up to a logarithmic factor and that acceleration is impossible for this specific prox-function. They extend the result to the quantum setting with von Neumann entropy.
We prove an $Ω(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 = Ω(T^2)$. 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 $\ell_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 \times d$ Hermitian positive-semidefinite matrices with unit trace.