Multi-rate high-order regularization with an order-(p−2) oracle
Abstract
We consider unconstrained minimization of a possibly nonconvex function f:ℝn→ℝ whose pth derivative is Lipschitz continuous, with p≥3, when derivative information is available only through order p−2. The unavailable tensors ∇p−1f and ∇pf are reconstructed from central finite differences of ∇p−2f. Since the two reconstructions have different point-query costs, we use a block length m for the order-p approximation and a subblock length ℓ≤ 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 ε-approximate first-order stationary point and derive an explicit bound on the number of bundled order-(p−2) oracle queries. For m=(p−2)n2 and ℓ=(p−2)n, the accuracy-dependent term has dimension--accuracy scaling n3/pε−(p+1)/p. Thus the method retains the ε−(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 n3/p, compared with n4/p when a common length is imposed.
Related
- Beyond Conventional Federated Learning via High-Order Regularization
- Marker-Delimited Codes for Short-Blocklength, High-Rate Coding over Multi-Read Edit Channels
- Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization
- Higher Order Risk Comparisons of Oracle Calibrated Global Local Priors
- Greedy sign-based box splitting: exact solvable classes, sharp thresholds and order-oracle complexity
BibTeX
@misc{kabgani2026multirate,
title = {{Multi-rate high-order regularization with an order-$(p-2)$ oracle}},
author = {Alireza Kabgani},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01819},
eprint = {2611.01819},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01819},
}
RIS
TY - UNPB
TI - Multi-rate high-order regularization with an order-(p−2) oracle
AU - Alireza Kabgani
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01819
UR - https://arxiv.org/abs/2611.01819
AB - We consider unconstrained minimization of a possibly nonconvex function f:ℝ^n→ℝ whose pth derivative is Lipschitz continuous, with p≥3, when derivative information is available only through order p−2. The unavailable tensors ∇^p−1f and ∇^pf are reconstructed from central finite differences of ∇^p−2f. Since the two reconstructions have different point-query costs, we use a block length m for the order-p approximation and a subblock length ℓ≤ 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 ε-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 ℓ=(p−2)n, the accuracy-dependent term has dimension--accuracy scaling n^3/pε^−(p+1)/p. Thus the method retains the ε^−(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.
ER -