Accelerating Trust-Region Methods: An Attempt to Balance Global and Local Efficiency

Balancing global efficiency and local convergence remains a central challenge in second-order methods for unconstrained convex optimization problems.

Newton's method enjoys fast local convergence but may diverge when initialized far from the solution.

In contrast, accelerated second-order methods provide global guarantees but typically suffer from slower local convergence.

This raises the fundamental question of to what extent global acceleration can be achieved without sacrificing strong local convergence.

In this paper, we tackle this challenge by proposing the first accelerated trust-region-type methods and leveraging their inherent primal-dual information.

Our primary contribution is the Accelerated Trust-Region method with Local Detection, which utilizes the Lagrange multiplier to detect local regions and achieves a global oracle complexity of \tilde{O}(\epsilon^{-1/3}), while maintaining quadratic local convergence.

We further examine the trade-off that arises when global convergence is pushed to the limit.

Specifically, we introduce the Accelerated Trust-Region Extragradient Method, which achieves a global oracle complexity of \tilde{O}(\epsilon^{-2/7}) but no longer enjoys quadratic local convergence.

This reveals a phase-transition-like phenomenon in accelerated trust-region-type methods: quadratic local convergence is preserved under moderate global acceleration, but it breaks down when pursuing extreme global efficiency.

Numerical experiments are consistent with the theoretical predictions and illustrate the global-local trade-off.