High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
share
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 (μ_k D^k-1/λ)^2/3k+1+loglog(1/ϵ) (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.
READ FULL TEXT