# Entropy-Smooth Convex Optimization Cannot Be Accelerated

arXiv: https://arxiv.org/abs/2607.27476 · HTML: https://mlsanity.com/paper/2607.27476/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 29 Jul 2026.

## Builds on (most cited first, 7 of 7)

- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods](https://mlsanity.com/paper/1502.05666/) (2015)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization](https://mlsanity.com/paper/1808.03045/) (2018)
- [Optimal Complexity and Certification of Bregman First-Order Methods](https://mlsanity.com/paper/1911.08510/) (2019)
- [Regularizing with Bregman-Moreau envelopes](https://mlsanity.com/paper/1705.06019/) (2017)
- [An optimal lower bound for smooth convex functions](https://mlsanity.com/paper/2404.18889/) (2024)

## Abstract (arXiv)

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.