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 $ν$-Hölder-continuous Hessian, it attains the global complexity bound $\mathcal{O}(\varepsilon^{-1/(1+ν)})$ for computing an $\varepsilon$-approximate minimizer, without knowledge of $ν\in[0,1]$ or the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.19647
curl -X POST /api/v1/records/arxiv/2607.19647/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.19647/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'