High-Order Oracle Complexity of Smooth and Strongly Convex Optimization

2020/10/13 by Guy Kornowski, Ohad Shamir, Kornowski, Guy +1
Computer Science · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2010.06642

openalex publication_date 2020/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note, we consider the complexity of optimizing a highly smooth (Lipschitz k-th order derivative) and strongly convex function, via calls to a k-th order oracle which returns the value and first k derivatives of the function at a given point, and where the dimension is unrestricted. Extending the techniques introduced in Arjevani et al. [2019], we prove that the worst-case oracle complexity for any fixed k to optimize the function up to accuracy ε is on the order of (\fracμ_k D^k-1λ)^(2)/(3k+1)+loglog(\frac1ε) (in sufficiently high dimension, and up to log factors independent of ε), where μ_k is the Lipschitz constant of the k-th derivative, D is the initial distance to the optimum, and λ is the strong convexity parameter.

Citations

• Lower Bound for Randomized First Order Convex Optimization

Related

• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Smooth Convex Optimization using Sub-Zeroth-Order Oracles
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
• Near-optimal method for highly smooth convex optimization
• On the oracle complexity of smooth strongly convex minimization