Entropy-Smooth Convex Optimization Cannot Be Accelerated

Jacob M. Aguirre, Dmitrii M. Ostrovskii

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$-…