Structural conditions on trust-region radius updates. Part I: first-order convergence and complexity
Abstract
Trust-region methods differ chiefly in how they update the radius, and each rule has traditionally been analysed on its own terms. We show that three structural conditions on the radius sequence suffice: a lower bound relative to the gradient norm, a contraction on unsuccessful iterations, and a controlled expansion on successful ones. A mechanism is weakly admissible if it satisfies the first two, and strongly admissible if it satisfies the first and third. Strong admissibility yields the optimal worst-case complexity 𝒪(ε−2) for first-order stationarity, and extends global convergence to model Hessians growing linearly with the iteration; weak admissibility gives limk→∞|∇ f(xk)| = 0 under uniformly bounded model Hessians. Both hold for every rule in the class, so a new mechanism is covered by verifying two inequalities rather than by a fresh convergence proof. We verify admissibility for five mechanism classes (fixed-factor, step-driven, retrospective, criticality-anchored and gradient-scaled), prove convergence of the retrospective update under linearly growing model Hessians, and extend the Lyapunov framework of Curtis and Scheinberg (2020), Wang and Yuan (2022) to three distinct scaling factors with decoupled step acceptance, covering η= 0; its stochastic version specialises to the deterministic gradient-scaled rule. Part II treats the asymptotic behaviour of the radius and convergence to second-order critical points.
Related
- Structural conditions on trust-region radius updates. Part II: second-order convergence and asymptotic radius behaviour
- High-Probability Convergence of SGD via Batched Updates
- Online adaptive non-intrusive model reduction via manifold interpolation and subspace updates: application to FSI convergence acceleration
- Pay Only for Disagreement: Certified No-Regression Verdicts for Model Updates with Matching Label-Complexity Bounds
- Sharp convergence rates for mean field control in the region of strong regularity
BibTeX
@misc{rieussec2026structural,
title = {{Structural conditions on trust-region radius updates. Part I: first-order convergence and complexity}},
author = {Jérémy Rieussec and Fabian Bastin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.30202},
eprint = {2606.30202},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.30202},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Structural conditions on trust-region radius updates. Part I: first-order convergence and complexity
AU - Jérémy Rieussec
AU - Fabian Bastin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2606.30202
UR - https://arxiv.org/abs/2606.30202
AB - Trust-region methods differ chiefly in how they update the radius, and each rule has traditionally been analysed on its own terms. We show that three structural conditions on the radius sequence suffice: a lower bound relative to the gradient norm, a contraction on unsuccessful iterations, and a controlled expansion on successful ones. A mechanism is weakly admissible if it satisfies the first two, and strongly admissible if it satisfies the first and third. Strong admissibility yields the optimal worst-case complexity 𝒪(ε^−2) for first-order stationarity, and extends global convergence to model Hessians growing linearly with the iteration; weak admissibility gives lim_k→∞|∇ f(x_k)| = 0 under uniformly bounded model Hessians. Both hold for every rule in the class, so a new mechanism is covered by verifying two inequalities rather than by a fresh convergence proof. We verify admissibility for five mechanism classes (fixed-factor, step-driven, retrospective, criticality-anchored and gradient-scaled), prove convergence of the retrospective update under linearly growing model Hessians, and extend the Lyapunov framework of Curtis and Scheinberg (2020), Wang and Yuan (2022) to three distinct scaling factors with decoupled step acceptance, covering η= 0; its stochastic version specialises to the deterministic gradient-scaled rule. Part II treats the asymptotic behaviour of the radius and convergence to second-order critical points.
ER -