On the complexity of lower-order implementations of higher-order methods

Abstract In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous p th-order derivatives, starting from $$p \ge 1$$ p ≥ 1 . The method, however, only requires derivative information up to order $$(p-1)$$ ( p - 1 ) , since the p th-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of recomputing a finite-difference approximation of the p th-order derivative at every iteration, we attempt to reuse each approximation for m consecutive iterations before recomputing it, with $$m \ge 1$$ m ≥ 1 as a key parameter. As a result, we obtain an adaptive method of order $$(p-1)$$ ( p - 1 ) that requires no more than $$\mathcal {O}(\epsilon ^{-\frac{p+1}{p}})$$ O ( ϵ - p + 1 p ) iterations to find an $$\epsilon $$ ϵ -approximate stationary point of the objective function and that, for the choice $$m=(p-1)n + 1$$ m = ( p - 1 ) n + 1 , where n is the problem dimension, takes no more than $$\mathcal {O}(n^{1/p}\epsilon ^{-\frac{p+1}{p}})$$ O ( n 1 / p ϵ - p + 1 p ) oracle calls of order $$(p-1)$$ ( p - 1 ) . This improves previously known bounds for tensor methods with finite-difference approximations in terms of the problem dimension.