The exact information-based complexity of smooth convex minimization
Journal of Complexity(2016)
We obtain a new lower bound on the information-based complexity of first-order
minimization of smooth and convex functions. We show that the bound matches the
worst-case performance of the recently introduced Optimized Gradient Method (Drori
and Teboulle, 2013; Kim and Fessler, 2015), thereby establishing that the bound is
tight and can be realized by an efficient algorithm. The proof is based on a novel
construction technique of smooth and convex functions.