Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911255274455040 |
|---|---|
| author | Jiang, Yuntian Zhang, Chuwen Jiang, Bo Ye, Yinyu |
| author_facet | Jiang, Yuntian Zhang, Chuwen Jiang, Bo Ye, Yinyu |
| contents | Historically speaking, it is hard to balance the global and local efficiency of second-order optimization algorithms. For instance, the classical Newton's method possesses excellent local convergence but lacks global guarantees, often exhibiting divergence when the starting point is far from the optimal solution~\cite{more1982newton,dennis1996numerical}. In contrast, accelerated second-order methods offer strong global convergence guarantees, yet they tend to converge with slower local rate~\cite{carmon2022optimal,chen2022accelerating,jiang2020unified}. Existing second-order methods struggle to balance global and local performance, leaving open the question of how much we can globally accelerate the second-order methods while maintaining excellent local convergence guarantee. In this paper, we tackle this challenge by proposing for the first time the accelerated trust-region-type methods, and leveraging their unique primal-dual information. Our primary technical contribution is \emph{Accelerating with Local Detection}, which utilizes the Lagrange multiplier to detect local regions and achieves a global complexity of $\tilde{O}(ε^{-1/3})$, while maintaining quadratic local convergence. We further explore the trade-off when pushing the global convergence to the limit. In particular, we propose the \emph{Accelerated Trust-Region Extragradient Method} that has a global near-optimal rate of $\tilde{O}(ε^{-2/7})$ but loses the quadratic local convergence. This reveals a phase transition in accelerated trust-region type methods: the excellent local convergence can be maintained when achieving a moderate global acceleration but becomes invalid when pursuing the extreme global efficiency. Numerical experiments further confirm the results indicated by our convergence analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00680 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency Jiang, Yuntian Zhang, Chuwen Jiang, Bo Ye, Yinyu Optimization and Control Historically speaking, it is hard to balance the global and local efficiency of second-order optimization algorithms. For instance, the classical Newton's method possesses excellent local convergence but lacks global guarantees, often exhibiting divergence when the starting point is far from the optimal solution~\cite{more1982newton,dennis1996numerical}. In contrast, accelerated second-order methods offer strong global convergence guarantees, yet they tend to converge with slower local rate~\cite{carmon2022optimal,chen2022accelerating,jiang2020unified}. Existing second-order methods struggle to balance global and local performance, leaving open the question of how much we can globally accelerate the second-order methods while maintaining excellent local convergence guarantee. In this paper, we tackle this challenge by proposing for the first time the accelerated trust-region-type methods, and leveraging their unique primal-dual information. Our primary technical contribution is \emph{Accelerating with Local Detection}, which utilizes the Lagrange multiplier to detect local regions and achieves a global complexity of $\tilde{O}(ε^{-1/3})$, while maintaining quadratic local convergence. We further explore the trade-off when pushing the global convergence to the limit. In particular, we propose the \emph{Accelerated Trust-Region Extragradient Method} that has a global near-optimal rate of $\tilde{O}(ε^{-2/7})$ but loses the quadratic local convergence. This reveals a phase transition in accelerated trust-region type methods: the excellent local convergence can be maintained when achieving a moderate global acceleration but becomes invalid when pursuing the extreme global efficiency. Numerical experiments further confirm the results indicated by our convergence analysis. |
| title | Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.00680 |