On the Universality of Simple Trust-Region Algorithms

We establish universal complexity guarantees for quadratic trust-region methods and identify a common mechanism underlying their universal behavior under convexity, based on a function-gap model-decrease estimate that appears to be new in the trust-region literature.

First, we prove that the basic trust-region method with inexact subproblem solves is universal under convexity.

Under a $\nu$-Hölder-continuous Hessian, it attains the global complexity bound $\mathcal{O}(\varepsilon^{-1/(1+\nu)})$ for computing an $\varepsilon$-approximate minimizer, without knowledge of $\nu\in[0,1]$ or the corresponding Hölder constant.

In the nonconvex regime, the method retains the classical $\mathcal{O}(\varepsilon^{-2})$ first-order complexity bound under the usual additional bounded-Hessian assumption.

With suitably vanishing inexactness, it also recovers Q-superlinear local convergence for $\nu=0$ and convergence of order $1+\nu$ for $\nu\in(0,1]$.

Second, we show that the same convex-universal mechanism applies to a trust-region variant with exact subproblem solves and a simple modification of the acceptance ratio.

This variant is universal simultaneously in the nonconvex, convex, and local regimes: it attains the optimal nonconvex first-order complexity $\mathcal{O}(\varepsilon^{-(2+\nu)/(1+\nu)})$, while preserving the universal convex complexity and the local Newton rates.

These guarantees require no knowledge of $\nu$ or its Hölder constant.

Both methods use the usual quadratic trust-region model and the classical radius-update mechanism, without gradient-dependent radii or model modifications such as cubic, gradient, or tensor regularization.

The results show that the trust-region mechanism is inherently adaptive across nonconvex, convex, and locally strongly convex regimes, providing further theoretical support for the practical success of trust-region methods.