{"ID":2847330,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.00680","arxiv_id":"2511.00680","title":"Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency","abstract":"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.","short_abstract":"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{...","url_abs":"https://arxiv.org/abs/2511.00680","url_pdf":"https://arxiv.org/pdf/2511.00680v2","authors":"[\"Yuntian Jiang\",\"Chuwen Zhang\",\"Bo Jiang\",\"Yinyu Ye\"]","published":"2025-11-01T19:48:08Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}