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

• 成果类型: Article; Early Access
• 署名作者: Doikov, Nikita; Grapiglia, Geovani Nunes
• 署名单位: Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02386-6
• 发表日期: 2026-07-08
• 关键词: Nonconvex optimization; Higher-Order Methods; Tensor Methods; finite difference; worst-case complexity; regularization

摘要

In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous pth-order derivatives, starting from p >= 1 . The method, however, only requires derivative information up to order (p-1) , since the pth-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of recomputing a finite-difference approximation of the pth-order derivative at every iteration, we attempt to reuse each approximation for m consecutive iterations before recomputing it, with m >= 1 as a key parameter. As a result, we obtain an adaptive method of order (p-1) that requires no more than O(& varepsilon;-p+1p) iterations to find an & varepsilon; -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(n1/p & varepsilon;-p+1p) oracle calls of order (p-1) . This improves previously known bounds for tensor methods with finite-difference approximations in terms of the problem dimension.