Adaptive cubic regularization reaches first-order accuracy in O(ε⁻³ᐟ²) evaluations

On any trial segment, put $s=s_k$ and, for each coordinate $i$, let $e_i$ be its standard basis vector and $r_i(t):=e_i^T(\mathrm{\nabla }f(x_k+ts)-g_k-t{B}_{k}s),0\le t\le 1.$ Since $B_k={\mathrm{\nabla }}^{2}f(x_k)$ by the algorithm and [F4] confirms its symmetry, $r_i(0)=0$ and $r_i^{\mathrm{\prime }}(t)=e_i^T({\mathrm{\nabla }}^{2}f(x_k+ts)-B_k)s\mathrm{.}$ By [A1], [F6], [F7], and [F8], $\mathrm{\mid }{r}_i^{\mathrm{\prime }}(t)\mathrm{\mid }\le Lt\mathrm{\parallel }s{\mathrm{\parallel }}_2^2$. Applying [F5] to $r_i$ on $[0,1]$ gives $\mathrm{\mid }{r}_i(1)\mathrm{\mid }\le L\mathrm{\parallel }s{\mathrm{\parallel }}_2^2$. Consequently, $\mathrm{\parallel }\mathrm{\nabla }f(x_k+s)-g_k-B_{k}s{\mathrm{\parallel }}_2\le \sqrt{n}L\mathrm{\parallel }s{\mathrm{\parallel }}_2^2\mathrm{.}$

In case 1, at a nonstationary accepted trial, the exact model-minimizer condition in [F2] and step 1.1 yield $\mathrm{\parallel }\mathrm{\nabla }f(x_{k+1}){\mathrm{\parallel }}_2\le ({\sigma }_k+\sqrt{n}L)\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2^2\le C_g\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2^2\mathrm{.}$ If the accepted trial is nonterminal, then $\mathrm{\parallel }\mathrm{\nabla }f(x_{k+1}){\mathrm{\parallel }}_2>\epsilon$, so $\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2>(\epsilon \mathrm{/}{C}_g{)}^{1\mathrm{/}2}$. By [F2], its predicted reduction is greater than ${\sigma }_{min}(\epsilon \mathrm{/}{C}_g{)}^{3\mathrm{/}2}\mathrm{/}6$. Acceptance therefore decreases $f$ by more than $c_g{\epsilon }^{3\mathrm{/}2}$. Summing over nonterminal accepted trials and using [A2] bounds their number by $[f(x_0)-f_{inf}]\mathrm{/}(c_g{\epsilon }^{3\mathrm{/}2})$. At most one further accepted trial reaches the first iterate with gradient norm at most $\epsilon$.

In case 2, let $s=s_k$, $r=\mathrm{\parallel }s{\mathrm{\parallel }}_2$, $g=g_k$, and $g^{+}=\mathrm{\nabla }f(x_k+s)$. The candidate residual check in [F1] gives $\mathrm{\parallel }g+B_{k}s+{\sigma }_{k}rs{\mathrm{\parallel }}_2\le {\kappa }_{\theta }\min \{1,r\}\mathrm{\parallel }g{\mathrm{\parallel }}_2\mathrm{.}$ Step 1.1 and the triangle inequality therefore imply $\mathrm{\parallel }{g}^{+}{\mathrm{\parallel }}_2\le ({\sigma }_{max}+\sqrt{n}L)r^2+{\kappa }_{\theta }\min \{1,r\}\mathrm{\parallel }g{\mathrm{\parallel }}_2\mathrm{.}$ By the $K$-Lipschitz gradient assumption, $\mathrm{\parallel }g{\mathrm{\parallel }}_2\le \mathrm{\parallel }{g}^{+}{\mathrm{\parallel }}_2+Kr$. Substitution and $r\min \{1,r\}\le r^2$ give $(1-{\kappa }_{\theta }\min \{1,r\})\mathrm{\parallel }{g}^{+}{\mathrm{\parallel }}_2\le ({\sigma }_{max}+\sqrt{n}L+{\kappa }_{\theta }K)r^2\mathrm{.}$ Since $1-{\kappa }_{\theta }\min \{1,r\}\ge 1-{\kappa }_{\theta }>0$, $\mathrm{\parallel }{g}^{+}{\mathrm{\parallel }}_2\le D_g{r}^2$.

In case 1 an infinite nonterminal run would have infinitely many accepted trials: solver calls succeed and [F3] bounds every rejection block by $R$. Each such accepted trial decreases $f$ by more than the fixed positive $c_g{\epsilon }^{3\mathrm{/}2}$ by step 2.1, contradicting [A2]. Thus a target iterate exists. By [F3], every block of rejected trials has length at most $R$. There is no rejected block after the first stationary or target-achieved iterate, so $N_u\le R{N}_s$. In case 1 this gives $N_s+N_u\le (R+1)(\frac{f(x_0)-f_{inf}}{c_g{\epsilon }^{3\mathrm{/}2}}+1)\mathrm{.}$

If an accepted trial in case 2 is nonterminal, then $\mathrm{\parallel }{g}^{+}{\mathrm{\parallel }}_2>\epsilon$, so $r>(\epsilon \mathrm{/}{D}_g{)}^{1\mathrm{/}2}$. The second decrease conclusion of [F2] gives predicted reduction greater than ${\sigma }_{min}(\epsilon \mathrm{/}{D}_g{)}^{3\mathrm{/}2}\mathrm{/}6$. Acceptance thus decreases $f$ by more than $c_a{\epsilon }^{3\mathrm{/}2}$. Summing over nonterminal accepted trials and using [A2] bounds their number by $[f(x_0)-f_{inf}]\mathrm{/}(c_a{\epsilon }^{3\mathrm{/}2})$; at most one further accepted trial reaches the first iterate with gradient norm at most $\epsilon$.

In case 2, solver success and [F3] likewise force infinitely many accepted trials in an infinite nonterminal run, contradicting the positive decrease in step 3.2 and [A2]. Thus a target iterate exists. The rejection count [F3] applies in case 2 as well, so $N_u\le R{N}_s$ and $N_s+N_u\le (R+1)(\frac{f(x_0)-f_{inf}}{c_a{\epsilon }^{3\mathrm{/}2}}+1)\mathrm{.}$ Both trial bounds are $O({\epsilon }^{-3\mathrm{/}2})$ for fixed constants. Each outer trial evaluates at most one objective, gradient, and Hessian; an additional terminal gradient check changes the count by at most one. Taking the cap $N$ at least the corresponding bound prevents budget exhaustion before a stationary or target-achieved iterate.