2026/07/22 by Clemens Sirotenko
#math.OC
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 ν-Hölder-continuous Hessian, it attains the global complexity bound O(ε-1/(1+ν)) for computing an ε-approximate minimizer, without knowledge of ν∈[0,1] or the corresponding Hölder constant. In the nonconvex regime, the method retains the classical O(ε-2) first-order complexity bound under the usual additional bounded-Hessian assumption. With suitably vanishing inexactness, it also recovers Q-superlinear local convergence for ν=0 and convergence of order 1+ν for ν∈(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 O(ε-(2+ν)/(1+ν)), while preserving the universal convex complexity and the local Newton rates. These guarantees require no knowledge of ν 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.