High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
This provides a theoretical complexity result for high-order optimization methods, which is incremental as it extends prior work on oracle complexity.
The paper tackles the problem of optimizing highly smooth and strongly convex functions using a k-th order oracle, proving a worst-case oracle complexity bound of order (μ_k D^{k-1}/λ)^{2/(3k+1)} + log log(1/ε) for achieving accuracy ε, with concrete parameters like Lipschitz constant μ_k and strong convexity λ.
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 D^{k-1}}λ\right)^{\frac{2}{3k+1}}+\log\log\left(\frac{1}ε\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.