Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness

Ankit Garg, Robin Kothari, Praneeth Netrapalli +1

We study the complexity of optimizing highly smooth convex functions. For a positive integer $p$, we want to find an $\epsilon$-approximate minimum of a convex function $f$, given oracle…