A survey of trust-region radius update mechanisms. Part I: First-order analysis

Jérémy Rieussec, Fabian Bastin · 2026

Read A survey of trust-region radius update mechanisms. Part I: First-order analysis by Jérémy Rieussec, Fabian Bastin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30202.txt.

Introduction

Jérémy Rieussec and Fabian Bastin survey how trust-region methods should update the radius that limits each step. These methods minimize a local model inside a ball of set radius. Good steps expand the radius; bad steps shrink it. Many update rules exist, with scattered convergence guarantees. In their 2026 survey, the authors isolate three structural conditions that unify them.

The conditions bound the radius below by the gradient size. They require contraction after unsuccessful iterations. They allow only controlled expansion after successful ones. Weak admissibility combines the first two conditions. It already forces the gradient norm to vanish eventually. Strong admissibility swaps in controlled expansion and yields optimal complexity. That bound governs worst-case steps to first-order stationarity. Five mechanism classes are verified against the conditions. Retrospective updates are newly proved convergent under growing model Hessians.

Catalog record

CREATORJérémy Rieussec, Fabian Bastin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115 KB
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30202

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A survey of trust-region radius update mechanisms. Part I: First-order analysis Jérémy Rieussec, Fabian Bastin Abstract We isolate three structural conditions on trust-region radius update rules for smooth unconstrained nonlinear optimisation, and study the class of mechanisms they define. The conditions act on the radius directly: 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 conditions, and strongly admissible if it satisfies the lower bound together with the controlled-expansion condition. Under uniformly bounded model Hessians, weak admissibility yields lim k → ∞ ‖ ∇ f ​ ( x k ) ‖ = 0 \lim_{k\to\infty}\|\nabla f(x_{k})\|=0 , and strong admissibility yields the optimal worst-case complexity 𝒪 ⁡ ( ε − 2 ) {\mathcal{O}}(\varepsilon^{-2}) for first-order stationarity. Strong admissibility extends the convergence guarantee to linearly growing model Hessians. We verify admissibility for five mechanism classes: fixed-factor, step-driven, retrospective, criticality-anchored, and gradient-scaled. Along the way, we prove convergence of the retrospective update under linearly growing model Hessians and revisit the framework of Curtis and Scheinberg 2020 ; Wang and Yuan 2022 : we extend it to three distinct scaling factors with decoupled step acceptance (covering η = 0 \eta=0 ), and specialise its stochastic version to the deterministic gradient-scaled update. 1 Introduction In this work, we study unconstrained, possibly nonconvex, optimisation problems of the form \min_{x\in\mathbb{R}^{p}}\;f(x), (1.1) where f:\mathbb{R}^{p}\to{\mathbb{R}} is at least continuously differentiable. Since global minima are in general hard to locate, we seek first-order critical points , i.e., points where \nabla f(x^{*})=0 . Trust-region methods. Originating in the work of Levenberg and Marquardt [ 39 ; 40 ] , trust-region methods compute steps by approximately minimising a local quadratic model of f within a ball of radius \Delta_{k} . The radius adapts to model quality: it expands when the model is accurate and contracts when it is not. For comprehensive overviews, see [ 17 ; 46 ; 41 ; 63 ; 64 ] . The framework has been extended in many directions: discretised problems arising in PDE-constrained optimisation [ 34 ] , constrained optimisation in Hilbert spaces [ 55 ] , composite optimisation [ 13 ] , and nonsmooth optimisation [ 61 ; 30 ] . Recent work has focused on worst-case complexity bounds [ 11 ; 14 ; 15 ; 21 ; 22 ; 23 ; 32 ; 33 ] , extensions to derivative-free and stochastic settings [ 48 ; 18 ; 1 ; 4 ; 16 ; 20 ; 57 ] , and unified frameworks across trust-region and line-search methods [ 20 ] . The radius update problem. The radius update rule drives this adaptation of \Delta_{k} . Many rules have been proposed: ratio-based, step-tracking, retrospective, criticality-based, gradient-proportional. Each has been analysed in isolation, under its own assumptions and with its own convergence proof. No unified perspective exists on which structural properties make a rule work. This makes it hard to compare mechanisms, to identify what is intrinsic to the trust-region framework, and to transfer guarantees across settings. Beyond the deterministic setting. Modern applications, such as machine learning, often lack exact function and derivative evaluations. Several methods extend classical algorithms to noisy settings, through stochastic gradient [ 52 ; 7 ] , variable sampling [ 29 ; 8 ; 5 ; 6 ] . For example, Carter 1991 ; Xu et al. 2020 ; Yao et al. 2021 accommodate inexact gradient and Hessian information in a trust-region framework. Recent advances extend convergence frameworks Curtis and Scheinberg 2020 to stochastic settings through martingale analysis and renewal processes [ 57 ; 1 ; 4 ; 16 ] . A central concept in these analyses is model accuracy, formalised through the notions of \kappa -fully linear and \kappa -fully quadratic models [ 18 ; 19 ] . For \kappa=(\kappa_{\scriptscriptstyle\text{ef}},\kappa_{\scriptscriptstyle\text{eg}})>0 , a model m_{k} is \kappa -fully linear on the ball of radius \Delta_{k} if, for all s with \|s\|\leq\Delta_{k} , \|\nabla f(x_{k})-\nabla m_{k}(0)\|\leq\kappa_{\scriptscriptstyle\text{eg}}\Delta_{k},\quad\text{and}\quad|f(x_{k}+s)-m_{k}(s)|\leq\kappa_{\scriptscriptstyle\text{ef}}\Delta_{k}^{2}, (1.2) with an analogous \kappa -fully quadratic notion for second-order models, which requires \kappa=(\kappa_{\scriptscriptstyle\text{ef}},\kappa_{\scriptscriptstyle\text{eg}},\kappa_{\scriptscriptstyle\text{eh}})>0 such that, for all s with \|s\|\leq\Delta_{k} , \|\nabla^{2}f(x_{k})-\nabla^{2}m_{k}(0)\|\leq\kappa_{\scriptscriptstyle\text{eh}}\Delta_{k},\quad\|\nabla f(x_{k})-\nabla m_{k}(0)\|\leq\kappa_{\scriptscriptstyle\text{eg}}\Delta_{k}^{2},\quad|f(x_{k}+s)-m_{k}(s)|\leq\kappa_{\scriptscriptstyle\text{ef}}\Delta_{k}^{3}. (1.3) These model conditions ( 1.2 ) and ( 1.3 ) tie the trust-region radius to model accuracy: the radius must converge to zero to guarantee accurate models near optimality. By contrast, classical trust-region methods [ 17 ; 46 ] maintain \Delta_{k} bounded below near a minimiser, allowing eventual Newton or quasi-Newton steps and faster local convergence under standard assumptions. Fan 2006 ; Fan and Lu 2015 ; Fan and Pan 2011 bridge these two regimes. \Delta_{k} may converge to zero at the rate {\mathcal{O}}(\|x_{k}-x^{*}\|) while preserving global and superlinear convergence. Yuan and Fan 2001 ; Fan et al. 2016 propose update rules that achieve this regime. Contributions and outline. The choice of the radius update mechanism is crucial. Various mechanisms have been proposed across contexts, with distinct convergence analyses and asymptotic behaviours. We address the following questions: 1. Which trust-region radius update mechanisms have been proposed in the literature? 2. Which properties are intrinsic to the trust-region framework, i.e. independent of the specific radius update rule? 3. Do all mechanisms ensure global convergence? Do they compare in their guarantees? 4. Does the update mechanism affect the worst-case complexity of the algorithm? 5. Which updates can offer superlinear convergence under suitable conditions? We isolate three structural conditions on the radius update rule and study the class of mechanisms they define. Let M_{k} denote a running bound on the model Hessian norm, and let g_{k} denote the model gradient at iteration k . The three conditions are, with \underline{\gamma_{2}}\in(0,1) , \overline{\gamma_{3}}>1 , and some constant \tilde{\eta}\in(0,1) : \displaystyle\textbf{Lower bound:}\quad\Delta_{k}\;\geq\;\frac{\kappa_{\scriptscriptstyle\text{lbd}}}{M_{k}}\min_{0\leq j\leq k}\|g_{j}\|\quad\text{for some }\kappa_{\scriptscriptstyle\text{lbd}}>0, (1.4) \displaystyle\textbf{Contraction:}\quad\Delta_{k+1}\;\leq\;\underline{\gamma_{2}}\,\Delta_{k}\quad\text{when }\rho_{k}<\tilde{\eta}, (1.5) \displaystyle\textbf{Expansion:}\quad\Delta_{k+1}\;\leq\;\overline{\gamma_{3}}\,\Delta_{k}\quad\text{when }\rho_{k}\geq\tilde{\eta}, (1.6) A mechanism is weakly admissible if it satisfies the first two conditions, and strongly admissible if it satisfies all three. Under uniformly bounded model Hessians, \liminf_{k\to\infty}\left\lVert g_{k}\right\rVert=0 implies \lim_{k\to\infty}\left\lVert g_{k}\right\rVert=0 independently of the update rule (Theorem 2.11 ). Adding weak admissibility yields \lim_{k\to\infty}\left\lVert g_{k}\right\rVert=0 (Theorem 3.2 ), and strong admissibility yields the optimal complexity {\mathcal{O}}(\varepsilon^{-2}) (Theorem 4.3 ). Strong admissibility extends the liminf guarantee to linearly growing model Hessians (Theorem 3.5 ). We verify admissibility for five mechanism classes: fixed-factor [ 17 ] , step-driven [ 50 ; 36 ] , retrospective [ 2 ] , criticality-anchored [ 20 ] , and gradient-scaled [ 28 ; 65 ] . We extend the retrospective analysis of [ 2 ] to linearly growing model Hessians, complementing Yuan 2015 . We also adapt the Lyapunov framework of Curtis and Scheinberg 2020 with three multiplicative factors and decoupled step acceptance, this allows \eta=0 which is not treated in [ 20 ] , and specialise the stochastic analysis of Wang and Yuan 2022 to the deterministic case. Relation to existing work. The closest predecessor of the present work is the survey of Yuan 2015 , which reviews trust-region algorithms for unconstrained optimisation, nonsmooth problems, equality- and inequality-constrained problems, and conic and subspace variants. Yuan’s survey is broad in scope and catalogues mechanisms, applications, and open questions across the trust-region landscape. Our focus is narrower and complementary. Whereas Yuan 2015 surveys mechanisms one at a time, we organise them

Read the complete text