Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness - Garg, Ankit; Kothari, Robin; , Praneeth Netrapalli,; Sherif, Suhail (NeurIPS 2021, 2021)
We study the complexity of optimizing highly smooth convex functions. For a positive integer , we want to find an ϵ-approximate minimum of a convex function , given oracle access to the function and its first derivatives, assuming that the th derivative of 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 solves this problem with oracle calls for constant . This is known to be optimal (up to log factors) for deterministic algorithms, but known lower bounds for randomized algorithms do not match this bound. We prove a new lower bound that matches this bound (up to log factors), and holds not only for randomized algorithms, but also for quantum algorithms.