# High-Order Oracle Complexity of Smooth and Strongly Convex Optimization

arXiv: https://arxiv.org/abs/2010.06642 · HTML: https://mlsanity.com/paper/2010.06642/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2020.

## Built on by (most cited first, 4 of 4)

- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [Tight Lower Bounds under Asymmetric High-Order H"older Smoothness and Uniform Convexity](https://mlsanity.com/paper/2409.10773/) (2024)
- [Stochastic Newton Proximal Extragradient Method](https://mlsanity.com/paper/2406.01478/) (2024)

## Abstract (arXiv)

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 left(fracμk Dk-1λright)^frac23k+1+loglogleft(frac1εright) (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.