A consistently adaptive trust-region method
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910554709295104 |
|---|---|
| author | Hamad, Fadi Hinder, Oliver |
| author_facet | Hamad, Fadi Hinder, Oliver |
| contents | Adaptive trust-region methods attempt to maintain strong convergence guarantees without depending on conservative estimates of problem properties such as Lipschitz constants. However, on close inspection, one can show existing adaptive trust-region methods have theoretical guarantees with severely suboptimal dependence on problem properties such as the Lipschitz constant of the Hessian. For example, TRACE developed by Curtis et al. obtains a $O(Δ_f L^{3/2} ε^{-3/2}) + \tilde{O}(1)$ iteration bound where $L$ is the Lipschitz constant of the Hessian. Compared with the optimal $O(Δ_f L^{1/2} ε^{-3/2})$ bound this is suboptimal with respect to $L$. We present the first adaptive trust-region method which circumvents this issue and requires at most $O( Δ_f L^{1/2} ε^{-3/2}) + \tilde{O}(1)$ iterations to find an $ε$-approximate stationary point, matching the optimal iteration bound up to an additive logarithmic term. Our method is a simple variant of a classic trust-region method and in our experiments performs competitively with both ARC and a classical trust-region method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01874 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A consistently adaptive trust-region method Hamad, Fadi Hinder, Oliver Optimization and Control Adaptive trust-region methods attempt to maintain strong convergence guarantees without depending on conservative estimates of problem properties such as Lipschitz constants. However, on close inspection, one can show existing adaptive trust-region methods have theoretical guarantees with severely suboptimal dependence on problem properties such as the Lipschitz constant of the Hessian. For example, TRACE developed by Curtis et al. obtains a $O(Δ_f L^{3/2} ε^{-3/2}) + \tilde{O}(1)$ iteration bound where $L$ is the Lipschitz constant of the Hessian. Compared with the optimal $O(Δ_f L^{1/2} ε^{-3/2})$ bound this is suboptimal with respect to $L$. We present the first adaptive trust-region method which circumvents this issue and requires at most $O( Δ_f L^{1/2} ε^{-3/2}) + \tilde{O}(1)$ iterations to find an $ε$-approximate stationary point, matching the optimal iteration bound up to an additive logarithmic term. Our method is a simple variant of a classic trust-region method and in our experiments performs competitively with both ARC and a classical trust-region method. |
| title | A consistently adaptive trust-region method |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2408.01874 |