2021
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
NeurIPS 2021spotlight
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 access to the function and its first $p$ derivatives, assuming that the $p$th derivative of $f$ is Lipschitz. R…