Backend
Structural conditions on trust-region radius updates. Part II: second-order convergence and asymptotic radius behaviour
arXiv cs.NA0 views
arXiv:2610.26137v1 Announce Type: cross Abstract: Continuing Part I (arXiv:2606.30202), we ask not which structural conditions on $\{\Delta_k\}$ suffice for global convergence but what the radius does; the answers separate the mechanisms by whether the radius is tied to a criticality measure. We identify three asymptotic regimes: the criticality-anchored rules give $\sum_k \Delta_k^2/M_k < +\infty$, hence $\liminf_k \Delta_k = 0$, and $\Delta_k \to 0$ once the model Hessians are bounded; the step-driven rules inherit the summability of the step series, hence $\sum_k \Delta_k < +\infty$; the fixed-factor rules keep $\Delta_k$ bounded away from zero. Near a critical point with positive definite Hessian, convergence of a subsequence forces convergence of the full sequence. We then extend the framework to second-order criticality through $\tau_k = \max\{\|g_k\|, -\lambda_k^-\}$, obtaining convergence to second-order critical points with the worst-case complexity $\mathcal{O}(\max\{\varepsilon_g^{-2}\varepsilon_H^{-1}, \varepsilon_H^{-3}\})$, which reduces to $\mathcal{O}(\varepsilon^{-3})$ for a common tolerance and is sharp for quadratic models. Finally we establish eventual inactivity of the constraint and superlinear convergence, isolating the two properties of the radius rule through which the mechanism enters; the rate itself is mechanism-independent. The criticality-anchored and capped gradient-scaled rules reach inactivity only under a side condition, $\zeta > \overline{\kappa}$ or $\overline{\mu} > \overline{\kappa}$, with $\overline{\kappa}$ a constant of the solution that cannot be checked in advance. These conditions are necessary, not artefacts: on $f(x) = \sin(x)/x$, $\overline{\kappa}$ is unbounded over the minimisers, so no parameter value meets the condition at all of them. Among the rules tied to a criticality measure, only those with an unbounded multiplier escape such a constant.
Source:https://arxiv.org/abs/2610.26137PreviousA numerical study of radius update rules in trust-region algorithmsNextTight lower bounds for Lipschitz geodesically convex optimization on hyperbolic space
Related posts

Copilot Fusion Takes Local Models, and the Offline Boundary Is Somewhere Else
0dev.to AI

A CTO Checklist for Evaluating AI Features Before Production Release
0dev.to AI
Humanoid Robot Demo Makes the Case for Keeping the Human Form
0dev.to AI
Supabase anon key vs service role key: what each one opens
0dev.to Security
After the eMudhra CA compromise: audit your own TLS stack in 30 minutes
0dev.to Security
Exposed Building Automation Services: Bavaria and DACH
0dev.to Security