{"ID":2858042,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.07992","arxiv_id":"2510.07992","title":"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 \\geq 1$. The method, however, only requires derivative information up to order $(p-1)$, since the $p$th-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of computing finite-difference approximations at every iteration, we reuse each approximation for $m$ consecutive iterations before recomputing it, with $m \\geq 1$ as a key parameter. As a result, we obtain an adaptive method of order $(p-1)$ that requires no more than $O(ε^{-\\frac{p+1}{p}})$ iterations to find an $ε$-approximate stationary point of the objective function and that, for the choice $m=(p-1)n + 1$, where $n$ is the problem dimension, takes no more than $O(n^{1/p}ε^{-\\frac{p+1}{p}})$ oracle calls of order $(p-1)$. This improves previously known bounds for tensor methods with finite-difference approximations in terms of the problem dimension.","short_abstract":"In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous $p$th-order derivatives, starting from $p \\geq 1$. The method, however, only requires derivative information up to order $(p-1)$, since the $p$th-order derivatives are approximated via finite differences. To ensure oracle ef...","url_abs":"https://arxiv.org/abs/2510.07992","url_pdf":"https://arxiv.org/pdf/2510.07992v1","authors":"[\"Nikita Doikov\",\"Geovani Nunes Grapiglia\"]","published":"2025-10-09T09:29:51Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}