Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness Robin Kothari Microsoft Research India Microsoft Quantum and Microsoft Research Bengaluru, KA, India

We study the complexity of optimizing highly smooth convex functions. For a positive integer p, we want to find an ɛ-approximate minimum of a convex function f, given oracle access to the function and its first p derivatives, assuming that the pth derivative of f is Lipschitz. Recently, three independent research groups (Jiang et al., PLMR 2019; Gasnikov et al., PLMR 2019; Bubeck et al., PLMR 2019) developed a new algorithm that