Multi-rate high-order regularization with an order-$(p-2)$ oracle

Abstract

We consider unconstrained minimization of a possibly nonconvex function $f:{\mathbb{R}}^n\to \mathbb{R}$ whose $p$th derivative is Lipschitz continuous, with $p\ge 3$, when derivative information is available only through order $p-2$. The unavailable tensors ${\nabla }^{p-1}f$ and ${\nabla }^{p}f$ are reconstructed from central finite differences of ${\nabla }^{p-2}f$. Since the two reconstructions have different point-query costs, we use a block length $m$ for the order-$p$ approximation and a subblock length $\ell \le m$ for the order-$(p-1)$ approximation. The latter is transported between consecutive reconstruction points using the stored order-$p$ approximation. This leads to an adaptive regularization method that does not require prior knowledge of the Lipschitz constant. We prove finite termination at an $\epsilon$-approximate first-order stationary point and derive an explicit bound on the number of bundled order-$(p-2)$ oracle queries. For $m=(p-2)n^2$ and $\ell =(p-2)n$, the accuracy-dependent term has dimension--accuracy scaling $n^{3/p}{\epsilon }^{-(p+1)/p}$. Thus the method retains the ${\epsilon }^{-(p+1)/p}$ dependence of full order-$p$ regularization while using derivatives only through order $p-2$. Within the dense reconstruction framework considered here, using separate block and subblock lengths gives dimension dependence of order $n^{3/p}$, compared with $n^{4/p}$ when a common length is imposed.