Performance Estimation of second-order optimization methods on classes of univariate functions
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_ | 1866909664886652928 |
|---|---|
| author | Rubbens, Anne Bousselmi, Nizar Hendrickx, Julien M. Glineur, François |
| author_facet | Rubbens, Anne Bousselmi, Nizar Hendrickx, Julien M. Glineur, François |
| contents | We develop a principled approach to obtain exact computer-aided worst-case guarantees on the performance of second-order optimization methods on classes of univariate functions. We first present a generic technique to derive interpolation conditions for a wide range of univariate functions, and use it to obtain such conditions for generalized self-concordant functions (including self-concordant and quasi-self-concordant functions) and functions with Lipschitz Hessian (both convex and non-convex). We then exploit these conditions within the Performance Estimation framework to tightly analyze the convergence of second-order methods on univariate functions, including (Cubic Regularized) Newton's method and several of its variants. Thereby, we improve on existing convergence rates, exhibit univariate lower bounds (that thus hold in the multivariate case), and analyze the performance of these methods with respect to the same criteria. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22764 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Performance Estimation of second-order optimization methods on classes of univariate functions Rubbens, Anne Bousselmi, Nizar Hendrickx, Julien M. Glineur, François Optimization and Control 68Q25, 90C53, 90C25, 26A06 We develop a principled approach to obtain exact computer-aided worst-case guarantees on the performance of second-order optimization methods on classes of univariate functions. We first present a generic technique to derive interpolation conditions for a wide range of univariate functions, and use it to obtain such conditions for generalized self-concordant functions (including self-concordant and quasi-self-concordant functions) and functions with Lipschitz Hessian (both convex and non-convex). We then exploit these conditions within the Performance Estimation framework to tightly analyze the convergence of second-order methods on univariate functions, including (Cubic Regularized) Newton's method and several of its variants. Thereby, we improve on existing convergence rates, exhibit univariate lower bounds (that thus hold in the multivariate case), and analyze the performance of these methods with respect to the same criteria. |
| title | Performance Estimation of second-order optimization methods on classes of univariate functions |
| topic | Optimization and Control 68Q25, 90C53, 90C25, 26A06 |
| url | https://arxiv.org/abs/2506.22764 |