On Global Rates for Regularization Methods based on Secant Derivative Approximations
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912578405400576 |
|---|---|
| author | Cartis, Coralia Jerad, Sadok |
| author_facet | Cartis, Coralia Jerad, Sadok |
| contents | An inexact framework for high-order adaptive regularization methods is presented, in which approximations may be used for the $p$th-order tensor, based on lower-order derivatives. Between each recalculation of the $p$th-order derivative approximation, a high-order secant equation can be used to update the $p$th-order tensor as proposed in (Welzel 2024) or the approximation can be kept constant in a lazy manner. When refreshing the $p$th-order tensor approximation after $m$ steps, an exact evaluation of the tensor or a finite difference approximation can be used with an explicit discretization stepsize. For all the newly adaptive regularization variants, we prove an $\mathcal{O}\left( \max[ ε_1^{-(p+1)/p}, \, ε_2^{(-p+1)/(p-1)} ] \right)$ bound on the number of iterations needed to reach an $(ε_1, \, ε_2)$ second-order stationary points. Discussions on the number of oracle calls for each introduced variant are also provided.
When $p=2$, we obtain a second-order method that uses quasi-Newton approximations with an $\mathcal{O}\left(\max[ε_1^{-3/2}, \, \, ε_2^{-3}]\right)$ iteration bound to achieve approximate second-order stationarity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07580 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Global Rates for Regularization Methods based on Secant Derivative Approximations Cartis, Coralia Jerad, Sadok Optimization and Control Numerical Analysis An inexact framework for high-order adaptive regularization methods is presented, in which approximations may be used for the $p$th-order tensor, based on lower-order derivatives. Between each recalculation of the $p$th-order derivative approximation, a high-order secant equation can be used to update the $p$th-order tensor as proposed in (Welzel 2024) or the approximation can be kept constant in a lazy manner. When refreshing the $p$th-order tensor approximation after $m$ steps, an exact evaluation of the tensor or a finite difference approximation can be used with an explicit discretization stepsize. For all the newly adaptive regularization variants, we prove an $\mathcal{O}\left( \max[ ε_1^{-(p+1)/p}, \, ε_2^{(-p+1)/(p-1)} ] \right)$ bound on the number of iterations needed to reach an $(ε_1, \, ε_2)$ second-order stationary points. Discussions on the number of oracle calls for each introduced variant are also provided. When $p=2$, we obtain a second-order method that uses quasi-Newton approximations with an $\mathcal{O}\left(\max[ε_1^{-3/2}, \, \, ε_2^{-3}]\right)$ iteration bound to achieve approximate second-order stationarity. |
| title | On Global Rates for Regularization Methods based on Secant Derivative Approximations |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2509.07580 |