Proof. Denote \(\mathbf{x}_+\mathrel{\vcenter{:}}= \mathbf{x}+r_0\mathbf{y}\) and \(\mathbf{x}_-\mathrel{\vcenter{:}}= \mathbf{x}-r_0\mathbf{y}\). Since \(f\) has \(L_2\)-Lipschitz Hessian, \[\begin{align} \tag{3} \left\|\nabla f(\mathbf{x}_+)-\nabla f(\mathbf{x})-r_{0} \nabla^2f(\mathbf{x})\cdot\mathbf{y}\right\|\leq L_2 r_{0}^{2}/2, \\ \left\|\nabla f(\mathbf{x}_-)-\nabla f(\mathbf{x})+r_{0} \nabla^2f(\mathbf{x})\cdot\mathbf{y}\right\|\leq L_2 r_{0}^{2}/2. \tag{4} \end{align}\] Therefore, we have \(\left\|\nabla f(\mathbf{x}_+)+\nabla f(\mathbf{x}_-)-2\nabla f(\mathbf{x})\right\|\leq L_2 r_{0}^{2}\) and \(\big\|\nabla^2f(\mathbf{x})\cdot\mathbf{y}-\frac{\nabla f(\mathbf{x}_+)-\nabla f(\mathbf{x}_-)}{2r_0}\big\|\leq L_2 r_{0}/2\). Furthermore, as \(r_0\leq \gamma_\mathbf{x}/(100L_1)\) and \(f\) has \(L_1\)-Lipschitz gradient, both \(\|\nabla f(\mathbf{x}_+)\|\) and \(\|\nabla f(\mathbf{x}_-)\|\) is at least \(\gamma_{\mathbf{x}}-L_1\gamma_\mathbf{x}/(100L_1)=0.99\gamma_{\mathbf{x}}\). We first understand how to approximate \(\nabla^2f(\mathbf{x})\cdot\mathbf{y}\) by normalized vectors \(\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}, \frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|}, \frac{\nabla f(\mathbf{x}_-)}{\|\nabla f(\mathbf{x}_-)\|}\), and then analyze the approximation error due to using \(\hat{\mathbf{g}}_{0}, \hat{\mathbf{g}}_{1}, \hat{\mathbf{g}}_{-1}\), respectively. By Lemma [15](#lem:vector-norm-1){reference-type=“ref” reference=“lem:vector-norm-1”}, we have \[\begin{align} &\frac{1}{2\|\nabla f(\mathbf{x})\|}\frac{\|\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|}{\sqrt{1-\left\langle\frac{\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}}\nonumber\\ &\qquad=\frac{1}{2\|\nabla f(\mathbf{x})\|}\frac{\|\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|}{\sqrt{1-\left\langle\frac{\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}}. \end{align}\] We denote the value above as \(\alpha\). Because \(f\) is \(L_2\)-Hessian Lipschitz, \(\|r_{0} \nabla^2f(\mathbf{x})\cdot\mathbf{y}\|\leq r_{0}L_2\). Since \(r_{0}\leq\frac{\gamma_{\mathbf{x}}}{100L_2}\), \(\|r_{0} \nabla^2f(\mathbf{x})\cdot\mathbf{y}\|\leq\frac{\gamma_{\mathbf{x}}}{100}\). Also by Lemma [14](#lem:dist-inner-vector){reference-type=“ref” reference=“lem:dist-inner-vector”} we have \[\begin{align} &\left\langle\frac{\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle\geq 0.94, \\ &\left\langle\frac{\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle\geq 0.94, \end{align}\] which promises that \(\alpha\geq\frac{0.99}{2\sqrt{1-0.94^{2}}}\geq 1\). In arguments next, we say a vector \(\mathbf{u}\) is \(\xi\)-close to a vector \(\mathbf{v}\) if \(\|\mathbf{u}-\mathbf{v}\|\leq \xi\) for any \(\xi\geq0\). We prove that the vector \[\begin{align} \tilde{\mathbf{g}}_{1}&\mathrel{\vcenter{:}}=\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}+\alpha\cdot\Bigg(\sqrt{1-\left\langle\frac{\nabla f(\mathbf{x}_-)}{\|\nabla f(\mathbf{x}_-)\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}\frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|}\nonumber\\ &\qquad\qquad-\sqrt{1-\left\langle\frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}\frac{\nabla f(\mathbf{x}_-)}{\|\nabla f(\mathbf{x}_-)\|}\Bigg)\label{eq:direction-vector43} \end{align}\tag{5}\] is \(\frac{7L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}\)-close to a vector proportional to \(\nabla f(\mathbf{x}_+)\). This is because (3 ), (4 ), and Lemma [13](#lem:dist-norm-vector){reference-type=“ref” reference=“lem:dist-norm-vector”} imply that \(\frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|}\text{\quad and\quad}\frac{\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|}\) are \(\frac{L_2 r_{0}^{2}}{0.99\gamma_{\mathbf{x}}}\)-close to each other, \[\begin{align} \label{eq:direction-vector43coeff} \sqrt{1-\left\langle\frac{\nabla f(\mathbf{x}_-)}{\|\nabla f(\mathbf{x}_-)\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}\frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|} \end{align}\tag{6}\] is proportional to \(\nabla f(\mathbf{x}_+)\), and the definition of \(\alpha\) implies \[\begin{align} &\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}-\alpha\cdot\frac{\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|}\cdot\sqrt{1-\left\langle\frac{\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}\nonumber\\ &\qquad=\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}/(2\|\nabla f(\mathbf{x})\|).\label{eq:HV-alpha-diff} \end{align}\tag{7}\] The above vector is \(\frac{L_2 r_{0}^{2}}{4\gamma_{\mathbf{x}}}\)-close to \(\frac{\nabla f(\mathbf{x}_+)}{2\|\nabla f(\mathbf{x})\|}\) by (3 ), and the error in above steps cumulates by at most \(\frac{6L_2 r_{0}^{2}}{0.99\gamma_{\mathbf{x}}}\) using Lemma [14](#lem:dist-inner-vector){reference-type=“ref” reference=“lem:dist-inner-vector”}. In total, the error is at most \(\frac{6L_2 r_{0}^{2}}{0.99\gamma_{\mathbf{x}}}+\frac{L_2 r_{0}^{2}}{4\gamma_{\mathbf{x}}}\leq \frac{7L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}\). Furthermore, this vector proportional to \(\nabla f(\mathbf{x}_+)\) that is \(\frac{L_2 r_{0}^{2}}{4\gamma_{\mathbf{x}}}\)-close to ([eq:direction-vector+]) has norm at least \((1-0.01)/2=0.495\) because the coefficient in ([eq:direction-vector+coeff]) is positive, while in the equality above we have \(\|r_{0} \nabla^2f(\mathbf{x})\cdot\mathbf{y}\|\leq\frac{\gamma_{\mathbf{x}}}{100}\). Therefore, applying Lemma [13](#lem:dist-norm-vector){reference-type=“ref” reference=“lem:dist-norm-vector”}, the vector \(\tilde{\mathbf{g}}_{1}\) in ([eq:direction-vector+]) satisfies \[\begin{align} \label{eq:HV-error-1} \big\|\tilde{\mathbf{g}}_{1}/\|\tilde{\mathbf{g}}_{1}\|-\nabla f(\mathbf{x}_+)/\|\nabla f(\mathbf{x}_+)\|\big\|\leq 29L_2 r_{0}^{2}/\gamma_{\mathbf{x}}. \end{align}\tag{8}\] Following the same logic, we can prove that the vector \[\begin{align} \tilde{\mathbf{g}}_{-1}&\mathrel{\vcenter{:}}=\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}-\alpha\sqrt{1-\left\langle\frac{\nabla f(\mathbf{x}_-)}{\|\nabla f(\mathbf{x}_-)\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}\frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|}\nonumber\\ &\qquad +\alpha\sqrt{1-\left\langle\frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|},\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\right\rangle^{2}}\frac{\nabla f(\mathbf{x}_-)}{\|\nabla f(\mathbf{x}_-)\|}\label{eq:direction-vector-} \end{align}\tag{9}\] satisfies \[\begin{align} \label{eq:HV-error-2} \big\|\tilde{\mathbf{g}}_{-1}/\|\tilde{\mathbf{g}}_{-1}\|-\nabla f(\mathbf{x}_-)/\|\nabla f(\mathbf{x}_-)\|\big\|\leq 29L_2 r_{0}^{2}/\gamma_{\mathbf{x}}. \end{align}\tag{10}\] Furthermore, (7 ) implies that the vector \(\tilde{\mathbf{g}}_{1}-\tilde{\mathbf{g}}_{-1}\) is \(\frac{14L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}\)-close to \[\begin{align} \frac{\nabla f(\mathbf{x})+r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{2\|\nabla f(\mathbf{x})\|}-\frac{\nabla f(\mathbf{x})-r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}}{2\|\nabla f(\mathbf{x})\|} =r_{0}\nabla^{2}f(\mathbf{x})\cdot\mathbf{y}/\|\nabla f(\mathbf{x})\| \label{eq:HV-ideal}. \end{align}\tag{11}\] Given that \(\|\nabla^2f(\mathbf{x})\|\ge\sqrt{L_2\epsilon}\) and \(|y_1|\geq\gamma_\mathbf{y}\), \(\|\nabla^2f(\mathbf{x})\cdot\mathbf{y}\|\geq \sqrt{L_2\epsilon}\gamma_\mathbf{y}\). Therefore, the RHS of (11 ) has norm at least \(\frac{r_{0}\sqrt{L_2\epsilon}\gamma_\mathbf{y}}{\gamma_{\mathbf{x}}}\), and by Lemma [13](#lem:dist-norm-vector){reference-type=“ref” reference=“lem:dist-norm-vector”} we have \[\begin{align} \left\|\frac{\tilde{\mathbf{g}}_{1}-\tilde{\mathbf{g}}_{-1}}{\|\tilde{\mathbf{g}}_{1}-\tilde{\mathbf{g}}_{-1}\|}-\frac{\nabla^2f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla^2f(\mathbf{x})\cdot\mathbf{y}\|}\right\|\leq\frac{14L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}\Big/\Big(\frac{r_{0}\sqrt{L_2\epsilon}\gamma_\mathbf{y}}{\gamma_{\mathbf{x}}}\Big)=\frac{14r_{0}\sqrt{L_2}}{\sqrt{\epsilon}\gamma_{\mathbf{y}}}\label{eq:HV-error-3}. \end{align}\tag{12}\] Finally, by Theorem [3](#thm:Comparison-GDE){reference-type=“ref” reference=“thm:Comparison-GDE”}, the error terms coming from \(\texttt{ComparisonGE}\), \(\big\|\hat{\mathbf{g}}_{0}-\frac{\nabla f(\mathbf{x})}{\|\nabla f(\mathbf{x})\|}\big\|\), \(\;\big\|\hat{\mathbf{g}}_{1}-\frac{\nabla f(\mathbf{x}_+)}{\|\nabla f(\mathbf{x}_+)\|}\big\|\), and \(\;\big\|\hat{\mathbf{g}}_{-1}-\frac{\nabla f(\mathbf{x}_-)}{\|\nabla f(\mathbf{x}_-)\|}\big\|\), are all upper bounded by \(\frac{L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}\). Combined with (8 ) and (10 ), we know that the vector \(\mathbf{g}\) we obtained in Algorithm [[algo:Comparison-Triangle]](#algo:Comparison-Triangle){reference-type=“ref” reference=“algo:Comparison-Triangle”} is \(\frac{61L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}\) close to \(\frac{\tilde{\mathbf{g}}_{1}-\tilde{\mathbf{g}}_{-1}}{2\alpha}\). Since \(\alpha\geq 1\), by Lemma [13](#lem:dist-norm-vector){reference-type=“ref” reference=“lem:dist-norm-vector”} we have \[\begin{align} \label{eq:HV-error-4} \left\|\frac{\mathbf{g}}{\|\mathbf{g}\|}-\frac{\tilde{\mathbf{g}}_{1}-\tilde{\mathbf{g}}_{-1}}{\|\tilde{\mathbf{g}}_{1}-\tilde{\mathbf{g}}_{-1}\|}\right\|\leq\frac{61L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}. \end{align}\tag{13}\] Combining (12 ) and (13 ), \[\begin{align} \label{eq:HV-error-5} \left\|\frac{\mathbf{g}}{\|\mathbf{g}\|}-\frac{\nabla^2f(\mathbf{x})\cdot\mathbf{y}}{\|\nabla^2f(\mathbf{x})\cdot\mathbf{y}\|}\right\|\leq\frac{61L_2 r_{0}^{2}}{\gamma_{\mathbf{x}}}+\frac{14r_{0}\sqrt{L_2}}{\sqrt{\epsilon}\gamma_{\mathbf{y}}}. \end{align}\tag{14}\] Our choice of \(r_{0}=\min\big\{\frac{\gamma_{\mathbf{x}}}{100L_1},\frac{\gamma_{\mathbf{x}}}{100L_2},\frac{\sqrt{\gamma_{\mathbf{x}}\hat{\delta}}}{20\sqrt{L_2}},\frac{\gamma_{\mathbf{y}}\hat{\delta}\sqrt{\epsilon}}{20\sqrt{L_2}}\big\}\) guarantees that the RHS of (14 ) is at most \(\hat{\delta}\). In terms of query complexity, we make 3 calls to \(\texttt{ComparisonGE}\). By Theorem [3](#thm:Comparison-GDE){reference-type=“ref” reference=“thm:Comparison-GDE”}, the total query complexity is \(O\big(n\log\big(nL_2 L_1^{2}/\gamma_{\mathbf{x}}\gamma_{\mathbf{y}}^{2}\epsilon\hat{\delta}^{2}\big)\big)\). ◻

Proof. By the mean value theorem, \[|F(\hat{r},\hat{\alpha})-F(r_i,\hat{\alpha})| = |\frac{\partial F}{\partial r}(\xi,\hat{\alpha})|\,|\hat{r}-r_i|\] for some \(\xi\) between \(\hat{r}\) and \(r_i\). Therefore, \[|\hat{r}-r_i| = \frac{|\hat{\beta}-F(r_i,\hat{\alpha})|}{|\frac{\partial F}{\partial r}(\xi,\hat{\alpha})|}.\] We bound numerator and denominator respectively. By triangle inequality, \[\label{eq:tri95bound} |\hat{\beta}-F(r_i,\hat{\alpha})| \le |\hat{\beta}-\beta_i| + |F(r_i,\alpha_i)-F(r_i,\hat{\alpha})| \le \epsilon + L_\alpha \epsilon,\tag{17}\] where \(L_\alpha\) is a Lipschitz constant of \(F\) in \(\alpha\) on the compact set \(r\in[0,1]\), \(\alpha\in[-1,1]\). We can bound \(L_\alpha\) explicitly by computing \(\partial F/\partial \alpha\) and taking a supremum; a crude universal bound \(L_\alpha\le 2\) suffices (indeed, one can check \(|\partial F/\partial\alpha|\le 2\) on this domain). Thus the numerator is less than \(3\epsilon\).

On the other hand, We have \[\left|\frac{\partial F}{\partial r}(\xi,\hat{\alpha})\right| = \frac{\xi(1-\hat{\alpha}^2)}{(1+\xi^2+2\xi\hat{\alpha})^{3/2}}.\] Since \(\xi\) lies between \(\hat{r}\in[0,1]\) and \(r_i\ge r_{\min}\), we have \(\xi\ge r_{\min}/2\) provided \(\epsilon\) is small enough; we can ensure this by restricting to \(\epsilon\le \gamma/10\) and using continuity of the inverse map. Also, \(\hat{\alpha} \le \alpha_i+\epsilon \le 1-\gamma+\frac{\gamma{10}}{=} 1-\tfrac{9}{10}\gamma\), so \[1-\hat{\alpha}^2 = (1-\hat{\alpha})(1+\hat{\alpha}) \ge \left(\tfrac{9}{10}\gamma\right)\cdot 1 = \tfrac{9}{10}\gamma.\] Therefore \[\left|\frac{\partial F}{\partial r}(\xi,\hat{\alpha})\right| \ge \frac{(r_{\min}/2)\cdot (\tfrac{9}{10}\gamma)}{8} \ge c\,r_{\min}\gamma\] for a universal constant \(c>0\). Combining numerator and denominator gives \[|\hat{r}-r_i| \le \frac{3\varepsilon}{c\,r_{\min}\gamma} = \frac{C_0}{r_{\min}\gamma}\,\varepsilon\] with \(C_0:=3/c\). ◻

Proof. If \(\hat{r}_i\) is set to \(0\), by Line [[lin:beta]](#lin:beta){reference-type=“ref” reference=“lin:beta”} and Line [[lin:alpha]](#lin:alpha){reference-type=“ref” reference=“lin:alpha”} in Algorithm [[algo:normhess]](#algo:normhess){reference-type=“ref” reference=“algo:normhess”}, we have \[\widehat{\alpha}_i\le 1-\tau_\alpha.\]

Geometry tells us \[\label{eq:r95min} \tau_\alpha=\cos(\arctan r_{\min})\tag{18}\]

Plugging in \(\widehat{\alpha}_i=\left\langle \mathbf{g}_i,\, \mathbf{g}_1 \right\rangle\) and ([eq:r_min]) we get \[r_i\le r_{\min}.\] ◻

Proof. By Theorem [5](#thm:triangle){reference-type=“ref” reference=“thm:triangle”}, \(\|\hat{\mathbf{v}}-\mathbf{v}\|\le \eta\), \(\|\hat{\mathbf{w}}-\mathbf{w}\|\le \eta\), and also \(\|\mathbf{g}_1-\mathbf{u}_1\|\le \eta\). Apply Lemma [14](#lem:dist-inner-vector){reference-type=“ref” reference=“lem:dist-inner-vector”} we have \[\label{eq:ab95err95app} |\hat{\alpha}-\alpha|\le 3\eta,\qquad |\hat{\beta}-\beta|\le 3\eta.\tag{19}\] and \[\left|\frac{\partial F}{\partial r}(r_i,\alpha)\right| = \frac{r_i(1-\alpha^2)}{(1+r_i^2+2r_i\alpha)^{3/2}} \ge \frac{r_{\min}(1-\alpha^2)}{8}.\] Using the separation \(1-\alpha^2\ge c_0\rho^2\), we obtain \[\label{eq:dF95lb95app} \left|\frac{\partial F}{\partial r}(r_i,\alpha)\right|\ge \frac{r_{\min}c_0}{8}\rho^2\tag{20}\] By the mean value theorem, \[|\hat{r}-r_i| = \frac{|\hat{\beta}-F(r_i,\hat{\alpha})|}{|\frac{\partial F}{\partial r}(\xi)|}\] for some \(\xi\) between \(r_i\) and \(\hat{r}\). For \(\eta\) sufficiently small, \(\hat{\alpha}\) is close to \(\alpha\) and thus \(1-\hat{\alpha}^2 \ge \frac{1}{2}(1-\alpha^2)\ge \frac{1}{2} c_0\rho^2\), and \(\xi\) remains in a compact interval containing \([r_{\min}/2,1+\rho]\). Therefore, the lower bound ([eq:dF_lb_app]) holds for \(|\frac{\partial F}{\partial r}(\xi)|\) as well \[\left|\frac{\partial F}{\partial r}(\xi,\hat{\alpha})\right| \ge \frac{r_{\min}c_0}{16} \rho^2.\] Hence \[|\hat{r}-r_i| \le \frac{16}{r_{\min}c_0\rho^2}\,|\hat{\beta}-F(r_i,\hat{\alpha})|.\] Similar to ([eq:tri_bound]), we have \[|\hat{\beta}-F(r_i,\hat{\alpha})| \le |\hat{\beta}-\beta|+|F(r_i,\alpha)-F(r_i,\hat{\alpha})| \le 3\eta+3L_\alpha\eta.\] where \(L_\alpha\) is a Lipschitz constant of \(F\) in \(\alpha\) on the compact set \(r\in[0,1]\), \(\alpha\in[-1,1]\). Conclude that the numerator is \(\le C'\eta\), and therefore \[|\hat{r}-r_i|\le C\frac{\eta}{r_{\min}\rho^2}.\] ◻

Proof. The first term \(C\eta/\rho^2\) follows from Lemma [[lem:amp_app]](#lem:amp_app){reference-type=“ref” reference=“lem:amp_app”}. The second term accounts for the fact that the perturbation uses \(\mathbf{v}\) (direction of \(\mathbf{h}_i+\rho \mathbf{h}_j\)) rather than \(\mathbf{u}_i\) (direction of \(\mathbf{h}_i\)). By Lemma [[lem:bias_app]](#lem:bias_app){reference-type=“ref” reference=“lem:bias_app”}, \(\|\mathbf{v}-\mathbf{u}_i\|\le O(\rho)\) (with explicit constant \(4/r_{\min}\)). On the non-degenerate set enforced by \(1-\alpha^2\ge c_0\rho^2\), the mapping from input directions to the recovered ratio is Lipschitz; therefore this \(O(\rho)\) direction change induces an \(O(\rho)\) bias in \(r\). Combining the two terms of error yields the stated bound. ◻

Proof. By Lemma [18](#lem:coordinate-bounds){reference-type=“ref” reference=“lem:coordinate-bounds”}, we have \(\Pr_{\mathbf{u}\sim \mathrm{Unif}(S_1(0))}[|\langle \mathbf{u}, \mathbf{v}\rangle| \ge 1/\sqrt{n}]\ge 2/5\) where \(\mathbf{v}\) is the eigenvalue of \(H\) with the largest absolute eigenvalue. Because of the isotropy of n coordinates, \(\mathbf{v}\sim \mathrm{Unif}(S_1(0))\). So we have \[\begin{align} \Pr_{\mathbf{u}\sim \mathrm{Unif}(S_1(0))}[|\langle \mathbf{u}, \mathbf{v}\rangle| \ge 1/\sqrt{n}]&=\Pr_{\mathbf{u}\sim \mathrm{Unif}(S_1(0)), \mathbf{v}\sim \mathrm{Unif}(S_1(0))}[|\langle \mathbf{u}, \mathbf{v}\rangle| \ge 1/\sqrt{n}]\\ &=\Pr_{\mathbf{u}\sim \mathrm{Unif}(\{\mathbf{e}_1,\ldots,\mathbf{e}_n\}), \mathbf{v}\sim \mathrm{Unif}(S_1(0))}[|\langle \mathbf{u}, \mathbf{v}\rangle| \ge 1/\sqrt{n}]\\ &=\Pr_{t \sim \mathrm{Unif}(\{1,\ldots,n\}), \mathbf{v}\sim \mathrm{Unif}(S_1(0))}[|\langle \mathbf{e}_t, \mathbf{v}\rangle| \ge 1/\sqrt{n}]\\ &\ge 2/5. \end{align}\] Repeat for \(O(1)\) times and the success probability can be more than \(2/3\). Let \(H^\star\) be the scale-free target matrix ([eq:Hstar_app]), so that \(H/\|H\|=H^\star/\|H^\star\|\). Let \(\widetilde{H}=[\hat{r}_1 \mathbf{g}_1,\dots,\hat{r}_n \mathbf{g}_n]\) and define \(E:=\widetilde{H}-H^\star\). Fix \(i\). If \(\hat{r}_i\) is produced by the non-degenerate solver, Corollary [[cor:nondeg_eta_app]](#cor:nondeg_eta_app){reference-type=“ref” reference=“cor:nondeg_eta_app”} gives \[|\hat{r}_i-r_i|\le \frac{C}{r_{\min}\tau_\alpha}\eta\] for some constant \(C\).

In the case that \(\mathbf{h}_i\) has a sufficiently small norm, by Lemma [[lem:norm_small]](#lem:norm_small){reference-type=“ref” reference=“lem:norm_small”} we have \[|\hat{r}_i-r_i|<r_{\min}.\]

In the case that the directions of \(\mathbf{h}_1\) and \(\mathbf{h}_i\) are too close, ([eq:r_min]) tells us \[r_{\min}=\tan{(\arccos(1-\tau_\beta))}.\] When \(\eta\) is sufficiently small, through Taylor expansion, \(f(x)=\tan(\arccos(1-x))\sim \sqrt{2x}+O(x^{3/2})\), i.e. \(r_{\min}\sim \sqrt{\tau_\beta}\). If \(\hat{r}_i\) is produced by perturbation, then Lemma [[lem:tradeoff_app]](#lem:tradeoff_app){reference-type=“ref” reference=“lem:tradeoff_app”} yields \[|\hat{r}_i-r_i|\le \frac{1}{r_{\min}}\left(C\,\frac{\eta}{\rho^2} + B\rho\right).\]

Combine these three cases and set \(\rho=\Theta(\eta^{1/3})\), \(\tau_\alpha=\tau_\beta=\Theta(\sqrt{\eta})\), we get \[|\hat{r}_i-r_i|\le O(\eta^{1/4}),\] and \[\|E\mathbf{e}_i\| = \|\hat{r}_i \mathbf{g}_i-r_i \mathbf{u}_i\| \le \|(\hat{r}_i-r_i)\mathbf{g}_i\| + \|r_i(\mathbf{g}_i-\mathbf{u}_i)\| \le |\hat{r}_i-r_i|\cdot\|\mathbf{g}_i\| + r_i\eta \le 2|\hat{r}_i-r_i|+\eta,\] since \(\|\mathbf{g}_i\|\le 1+\eta\le 2\) and \(r_i\le 1\). Thus \(\|E\mathbf{e}_i\|\le K_1\eta^{1/4}\) for a constant \(K_1\). By Lemma [[lem:col2spec_app]](#lem:col2spec_app){reference-type=“ref” reference=“lem:col2spec_app”}, \[\|E\|\le K_1\sqrt{n}\,\eta^{1/4}.\] By Lemma [[lem:Hstar_lb_app]](#lem:Hstar_lb_app){reference-type=“ref” reference=“lem:Hstar_lb_app”}, \(\|H^\star\|\ge 1\). If \(\eta\) is small enough that \(\|E\|\le 1/2\), then Lemma [[lem:normstab_app]](#lem:normstab_app){reference-type=“ref” reference=“lem:normstab_app”} gives \[\left\|\frac{\widetilde{H}}{\|\widetilde{H}\|}-\frac{H^\star}{\|H^\star\|}\right\| \le 4\|E\| \le 4K_1\sqrt{n}\,\eta^{1/4}.\] Using \(H/\|H\|=H^\star/\|H^\star\|\) then gives the stated bound with \(K:=4K_1\). ◻

Proof. Consider the \(m=\lceil18\ln(1/p)\rceil\) independent base runs in the algorithm. Define \(\widehat H^{(r)}\) to be the output of the \(r\)-th iteration and set \(\mathcal{N}_r=\{s\in\{1,\ldots,m\}:\|\widehat H^{(r)}-\widehat H^{(s)}\|\le 2\delta/3\}\). We finally return any \(\widehat H^{(r)}\) with \(|\mathcal{N}_r|\ge m/2\) and prove that it satisfies our requirements with success probability at least \(1-p\). Let \(X_r\) be the indicator that the \(r\)-th candidate satisfies \(\|\widehat H^{(r)}-H\|\le \delta_0\). Since \(\Pr[X_r=1]\ge2/3\), Hoeffding’s inequality gives \[\Pr\left[\sum_{r=1}^m X_r\le m/2\right]\le \exp(-m/18)\le p.\] Conditioned on the complementary event, more than half of the candidates are good. Any two good candidates are within \(2\delta_0=2\delta/3\) of each other, so every good candidate satisfies the selection condition \(|\mathcal{N}_r|\ge m/2\). Thus the algorithm can select at least one candidate. Moreover, for any selected candidate \(\widehat H^{(r)}\), the set \(\mathcal{N}_r\) intersects the set of good candidates because both sets have size greater than \(m/2\) or at least \(m/2\) with a strict majority of good candidates. Therefore, for some good \(\widehat H^{(s)}\), \[\|\widehat H^{(r)}-H\|\le \|\widehat H^{(r)}-\widehat H^{(s)}\|+\|\widehat H^{(s)}-H\|\le 2\delta/3+\delta/3=\delta.\] The total query complexity is \(m\cdot O(n^2\log\frac{1}{\delta})=O(n^2\log\frac{1}{\delta}\log\frac{1}{p})\). ◻

Proof. Since \(\|\widehat H-H\|\le\xi_3\), by Davis-Kahan Theorem (Lemma [22](#lem:Davis-Kahan){reference-type=“ref” reference=“lem:Davis-Kahan”}), we have \(k=k'\) and \[\sin\big(\Theta(U,V)\big)\le\frac{\xi_3}{\lambda_k-\lambda_{k+1}}=O\left(\frac{n\xi_3}{\epsilon\delta_\kappa}\right),\] and hence \[\label{eq:uv95bound} \|\mathbf{u}-\mathbf{v}\|\le O\left(\frac{n\xi_3}{\epsilon\delta_\kappa}\right).\tag{22}\]

For our choice of \(\mathbf{u}\), We prove \(\|H\|-\|H\mathbf{u}\|\le\frac{\epsilon\delta_\kappa}{2}+2\xi_3\). Our intuition is shown in Figure 4. We find the first pair of eigenvalue \((\lambda_k',\lambda_{k+1}')\) that are far apart (distance longer than \(\frac{\epsilon\delta_\kappa}{2n}\)), thus we can say \(\lambda_1',\ldots,\lambda_k'\) are close enough, and so \(\lambda_1,\ldots,\lambda_k\) are close too. Then we can apply Davis-Kahan Theorem to bound the distance between \(U\) and \(V\). Since \(\mathbf{u}\in U\), we can write \(\mathbf{u}=\sum_{i=1}^{k}s_i\mathbf{u}_i\) where \(\sum_{i=1}^{k}s_i^2=1\). Therefore, \[H\mathbf{u}=\sum_{i=1}^ks_iH\mathbf{u}_i=\sum_{i=1}^ks_i\lambda_i\mathbf{u}_i,\] and \[\|H\mathbf{u}\|=\sqrt{\sum_{i=1}^ks_i^2\lambda_i^2}\ge\lambda_k\sqrt{\sum_{i=1}^ks_i^2}=\lambda_k.\] Since for any \(i<k\) we have \(\lambda_i'-\lambda_{i+1}'\le\frac{\epsilon\delta_\kappa}{2n}\), we can further derive that \[\lambda_1'-\lambda_k'\le\sum_{i=1}^{k-1}\lambda_i'-\lambda_{i+1}'\le\frac{(k-1)\epsilon\delta_\kappa}{2n}\le\frac{\epsilon\delta_\kappa}{2}.\] From \(|\lambda_i-\lambda_i'|\le\xi_3\), \[\label{eq:Hu} \|H\|-\|H\mathbf{u}\|=\lambda_1-\|H\mathbf{u}\|\le\lambda_1'+\xi_3-(\lambda_k'-\xi_3)\le\frac{\epsilon\delta_\kappa}{2}+2\xi_3.\tag{23}\]  ◻

Proof. Note that \[\begin{align} \nabla f(\mathbf{x}+\mu \mathbf{v})&=\nabla f(\mathbf{x})+\frac{1}{2}\nabla^2f(\mathbf{x})\cdot\mu \mathbf{v}+O(\mu^2). \end{align}\] From the observation in Figure 3, if there exist \(\eta'\) such that two vectors \(\nabla f(\mathbf{x}+\mu \mathbf{v})+k_2\mathbf{v}_2\) and \(\nabla f(\mathbf{x})+k_1\mathbf{v}_1+\eta' H\cdot\mu \mathbf{u}\) are colinear, then

\[\begin{align} \label{eq:two95ratios} \eta' &= \frac{|BD|}{|BE|}=\frac{|CD|}{|CE|}\cdot\frac{\sin \angle BCD}{\sin \angle BCE}=\frac{\sin \angle CED}{\sin\angle CDE}\cdot\frac{\sin \angle BCD}{\sin \angle BCE}. \end{align}\tag{24}\] We compute two ratios in ([eq:two_ratios]) separately \[\begin{align} \label{eq:CED47BCE} \frac{\sin \angle CED}{\sin \angle BCE}&=\frac{\sin(\angle BCE+O(\sqrt{\mu}))}{\sin\angle BCE} \notag\\ &=\frac{\sin\angle BCE\cos O(\sqrt{\mu})+\cos \angle BCE\sin O(\sqrt{\mu})}{\sin \angle BCE} \notag\\ &=\cos O(\sqrt{\mu})+\frac{O(\sqrt{\mu})}{\tan \angle BCE}. \end{align}\tag{25}\] We can then compute the angle \[\begin{align} \langle \nabla^2f(\mathbf{x})\cdot\mu \mathbf{u}, \nabla^2f(\mathbf{x})\cdot\mu \mathbf{u}+O(\mu^2)\rangle&=\arccos\frac{(\lambda_\mathbf{u}\cdot\mu)^2+(\lambda_\mathbf{u}\cdot\mu+O(\mu^2))^2-O(\mu^4)}{2\lambda_\mathbf{u}\cdot\mu(\lambda_\mathbf{u}\cdot\mu+O(\mu^2))} \notag \\ &=\arccos\frac{2(\lambda_\mathbf{u}\cdot\mu)^2+O(\mu^3)}{2(\lambda_\mathbf{u}\cdot\mu)^2}\left(1-O \left(\frac{\mu^2}{\lambda_\mathbf{u}\mu}\right)\right) \notag \\ &=\arccos(1-O(\mu)) \notag \\ &=O(\sqrt{\mu}). \label{eq:figure-1} \end{align}\tag{26}\] So there exists an angle \(\zeta\) such that \(\angle BEC=\frac{\pi-O(\sqrt{\mu})}{2}+\zeta\), \(\angle BCE=\frac{\pi-O(\sqrt{\mu})}{2}-\zeta\). From \[\begin{align} \sin(\frac{\pi-O(\sqrt{\mu})}{2}+\zeta)=\cos(\frac{O(\sqrt{\mu})}{2}-\zeta) \quad \text{and} \quad \cos x=1-\frac{x^2}{2}+O(x^4), \end{align}\] we get \[\begin{align} &\sin \angle BEC=1-\frac{1}{2}(\frac{O(\sqrt{\mu})}{2}-\zeta)^2+O((\sqrt{\mu}+\zeta)^4), \\ &\sin\angle BCE=1-\frac{1}{2}(\frac{O(\sqrt{\mu})}{2}+\zeta)^2+O((\sqrt{\mu}+\zeta)^4). \end{align}\] Therefore, \[\begin{align} \frac{\sin \angle BEC}{\sin \angle BCE}&=\frac{1-\frac{1}{2}(\frac{O(\sqrt{\mu})}{2}-\zeta)^2+O((\sqrt{\mu}+\zeta)^4)}{1-\frac{1}{2}(\frac{O(\sqrt{\mu})}{2}+\zeta)^2+O((\sqrt{\mu}+\zeta)^4)} \\ &=1+\frac{1}{2}\left(\left(\frac{O(\sqrt{\mu})}{2}+\zeta\right)^2-\left(\frac{O(\sqrt{\mu})}{2}-\zeta\right)^2\right)+O(\mu^{1.5}, \zeta^3) \\ &=1+O(\sqrt{\mu}\zeta)+O(\mu^{1.5}, \zeta^3). \end{align}\] On the other hand, by the Law of Sines, \[\begin{align} \frac{\sin \angle BEC}{\sin \angle BCE}&=\frac{\|\nabla^2f(\mathbf{x})\cdot\mu u+O(\mu^2)\|}{\|\nabla^2f(\mathbf{x})\cdot\mu u\|}=1+O(\mu). \end{align}\] Comparing two equations with the same left-hand side, we know that: \(\zeta=O(\sqrt{\mu})\), i.e. \(\angle BCE=\frac{\pi}{2}+O(\sqrt{\mu})\). Naturally, we have \[\begin{align} \tan \angle BCE=O(1/\sqrt{\mu}). \end{align}\] Plugging in ([eq:CED/BCE]), we obtain \[\begin{align} \frac{\sin \angle CED}{\sin\angle BCE}=1+O(\sqrt{\mu}). \end{align}\] Denote \(\langle \nabla f(\mathbf{x}), \nabla f(\mathbf{x}+\mu \mathbf{v})\rangle=\alpha\). Applying the Law of Cosines, we can compute \(\alpha\) as \[\cos\alpha=\frac{\|\nabla f(\mathbf{x})\|^2+\|\nabla f(\mathbf{x}+\mu \mathbf{v})\|^2-\|\nabla^2f(\mathbf{x})\cdot\mu \mathbf{v}+O(\mu^2)\|^2}{2\cdot\|\nabla f(\mathbf{x})\|\cdot\|\nabla f(\mathbf{x}+\mu \mathbf{v})\|}.\] So we have \[\label{eq:sin-ratio-1} \alpha=O(\sqrt{\mu}).\tag{27}\] Denote \(\langle \nabla f(\mathbf{x}), \mathbf{u}\rangle=\theta\). The other ratio \(\frac{\sin\angle BCD}{\sin \angle CDE}\) in ([eq:two_ratios]) can be computed as \[\begin{align} \frac{\sin \angle BCD}{\sin \angle CDE}&=\frac{\sin\theta\cos O(\sqrt{\mu})+\cos\theta\sin O(\sqrt{\mu})}{\sin\theta\cos\alpha-\cos\theta\sin\alpha} \notag\\ &=\frac{1+O(\mu)+\cot\theta\cdot O(\sqrt{\mu})}{1+O(\mu)-\cot\theta\cdot O(\sqrt{\mu})} \notag\\ &=1+\cot\theta\cdot O(\sqrt{\mu}). \label{eq:sin-ratio-2} \end{align}\tag{28}\] Combining (27 ) and (28 ), we have \[\begin{align} \eta'&=\frac{\sin \angle BEC}{\sin\angle BCE}\cdot \frac{\sin \angle BCD}{\sin\angle CDE} =(1+O(\mu))(1+\cot\theta\cdot O(\sqrt{\mu})) =1+O\left(\frac{\sqrt{\mu}}{\tan\theta}\right). \end{align}\] Since \(\|u-v\|\le O(\frac{n\xi_3}{\epsilon\delta_\kappa})\), we can further derive that \[\begin{align} \frac{\eta}{\|H\|} &=(1+O(\mu))(1+\cot(\theta-O\Big(\frac{n\xi_3}{\epsilon\delta_\kappa}\Big))\cdot O(\sqrt{\mu})) \\ &=1+O\left(\frac{\sqrt{\mu}}{\tan(\theta-O(\frac{n\xi_3}{\epsilon\delta_\kappa}))}\right)\\ &=1+O\left(\frac{\sqrt{\mu}}{\tan\beta}\right)+O\left(\frac{n\xi_3}{\epsilon\delta_\kappa}\right). \end{align}\] ◻

Proof of . Theorem 7] By Lemma [[lem:choose_eigenvector]](#lem:choose_eigenvector){reference-type=“ref” reference=“lem:choose_eigenvector”} we have ([eq:estimate_norm]). Given Line [[lin:HE_in_ratio]](#lin:HE_in_ratio){reference-type=“ref” reference=“lin:HE_in_ratio”} and Line [[lin:GE_in_ratio]](#lin:GE_in_ratio){reference-type=“ref” reference=“lin:GE_in_ratio”} in Algorithm [[algo:Comparison-ratio]](#algo:Comparison-ratio){reference-type=“ref” reference=“algo:Comparison-ratio”}, by Theorem [[thm:main_app]](#thm:main_app){reference-type=“ref” reference=“thm:main_app”} and Theorem [3](#thm:Comparison-GDE){reference-type=“ref” reference=“thm:Comparison-GDE”} we have \[\left\|\hat{H}-\frac{H}{\|H\|}\right\|\le \xi_3,\qquad\hat{\mathbf{g}}_1=\frac{\mathbf{g}+k_1\mathbf{v}_1}{\|\mathbf{g}+k_1\mathbf{v}_1\|},\qquad \|k_1\mathbf{v}_1\|\le O(\xi_1)\|\mathbf{g}\|.\] (Analogous notation holds for \(\hat{\mathbf{g}}_2\) with error \(k_2\mathbf{v}_2\).) Observe that \[\begin{align} \left\|\frac{H}{\|H\|}\cdot\mu \mathbf{u}-\hat{H}\cdot\mu \mathbf{v}\right\| &\leq \mu\left( \left\|\frac{H}{\|H\|}\cdot \mathbf{u}-\frac{H}{\|H\|}\cdot \mathbf{v}\right\| + \left\|\frac{H}{\|H\|}\cdot \mathbf{v}-\hat{H}\cdot \mathbf{v}\right\| \right) \\ &\leq \mu\left( \|\mathbf{u}-\mathbf{v}\|+\left\|\frac{H}{\|H\|}-\hat{H}\right\| \right). \end{align}\] By ([eq:uv_bound]), we have \(\|\mathbf{u}-\mathbf{v}\|\le O(\xi_3/\epsilon\delta_\kappa)\). Therefore, we have \[\label{eq:inc95mismatch} \left\|\frac{H}{\|H\|}\cdot\mu \mathbf{u}-\hat{H}\cdot\mu \mathbf{v}\right\| \le O\left(\frac{\mu n\xi_3}{\epsilon\delta_\kappa}\right).\tag{29}\] and \[\label{eq:figure-2} \left\|H\cdot\mu \mathbf{u}-\|H\|\cdot\hat{H}\cdot\mu \mathbf{v}\right\| \le \|H\|\cdot O\left(\frac{\mu n\xi_3}{\epsilon\delta_\kappa}\right).\tag{30}\] The geometric calculation in Lemma [6](#lem:difference-colinear){reference-type=“ref” reference=“lem:difference-colinear”} gives \(\eta/\|H\|=1+O(\sqrt{\mu}/\tan\theta)\), where \(\theta=\angle(\mathbf{g},\mathbf{u})\). Due to (30 ), replacing the exact increment direction \(H\mu \mathbf{u}\) by the estimated increment direction \(\|H\|\hat{H}\mu \mathbf{v}\) perturbs the relevant triangle angles by at most \(O(\frac{n\xi_3}{\epsilon\delta_\kappa})\), hence we can write \[\label{eq:eta95ratio} \frac{\eta}{\|H\|} = 1+O\!\left(\frac{\sqrt{\mu}}{\tan(\theta-O(\frac{n\xi_3}{\epsilon\delta_\kappa}))}\right) = 1+O\!\left(\frac{\sqrt{\mu}}{\tan\beta}\right)+O\left(\frac{ n\xi_3}{\epsilon\delta_\kappa}\right),\tag{31}\] using \(\theta\ge \beta\) and \(\frac{\mu n\xi_3}{\epsilon\delta_\kappa}\) sufficiently small. Furthermore, by Lemma [15](#lem:vector-norm-1){reference-type=“ref” reference=“lem:vector-norm-1”} and Lemma [[lem:eta_prime_enters]](#lem:eta_prime_enters){reference-type=“ref” reference=“lem:eta_prime_enters”}, \[\label{eq:Delta95gamma95norm95ratio} \hat{\kappa}=\dfrac{\sqrt{1-\left\langle \hat{\mathbf{g}}_1,\, \hat{\mathbf{g}}_2 \right\rangle^2}} {\mu\,\sqrt{1-\left\langle \hat{\mathbf{g}}_2,\, \mathbf{v} \right\rangle^2}}=\frac{\eta\cdot\|\hat{H}\cdot\mu \mathbf{v}\|}{\mu\|\mathbf{g}+k_1\mathbf{v}_1\|}.\tag{32}\] By Taylor expansion, \[\label{eq:grad95diff95u} \nabla f(\mathbf{x}+\mu \mathbf{u})-\nabla f(\mathbf{x})=H\cdot\mu \mathbf{u}+O(\mu^2),\tag{33}\] so by (23 ) we have \[\begin{align} \label{eq:hatgamma95expand} \frac{1}{\mu}\frac{\|\nabla f(\mathbf{x}+\mu \mathbf{u})-\nabla f(\mathbf{x})\|}{\|\mathbf{g}\|} &= \frac{\|H\cdot\mu \mathbf{u}+O(\mu^2)\|}{\mu\|\mathbf{g}\|}\notag\\ &= \frac{\|H \mathbf{u}\|}{\|\mathbf{g}\|}+O\!\left(\frac{\mu}{\|\mathbf{g}\|}\right)\notag\\ &= \frac{\|H\mathbf{u}\|}{\|\mathbf{g}\|}+O\left(\frac{\mu}{\|\mathbf{g}\|}\right)\notag\\ &= \frac{\|H\|}{\|\mathbf{g}\|}+O\left(\frac{\epsilon\delta_\kappa+\xi_3+\mu}{\|\mathbf{g}\|}\right). \end{align}\tag{34}\] Combine ([eq:Delta_gamma_norm_ratio]) and ([eq:hatgamma_expand]), \[\begin{align} \left|\hat{\kappa}-\frac{1}{\mu}\frac{\|\nabla f(\mathbf{x}+\mu \mathbf{u})-\nabla f(\mathbf{x})\|}{\|\mathbf{g}\|}\right| &= \left| \frac{\eta\|\hat{H}\mu \mathbf{v}\|}{\mu\|\mathbf{g}+k_1\mathbf{v}_1\|} - \frac{\|H\mu \mathbf{u}+O(\mu^2)\|}{\mu\|\mathbf{g}\|} \right| \notag\\ &\le \underbrace{ \left| \frac{\eta\|\hat{H}\mu \mathbf{v}\|}{\mu\|\mathbf{g}+k_1\mathbf{v}_1\|} - \frac{\|H\|\|\hat{H}\mu \mathbf{v}\|}{\mu\|\mathbf{g}+k_1\mathbf{v}_1\|} \right|}_{T_1} + \underbrace{ \left| \frac{\|H\|\|\hat{H}\mu \mathbf{v}\|}{\mu\|\mathbf{g}+k_1\mathbf{v}_1\|} - \frac{\|H\|\|\hat{H}\mu \mathbf{v}\|}{\mu\|\mathbf{g}\|} \right|}_{T_2} \notag\\ &\qquad+ \underbrace{ \left| \frac{\|H\|\|\hat{H}\mu \mathbf{v}\|}{\mu\|\mathbf{g}\|} - \frac{\|H\mu \mathbf{u}\|}{\mu\|\mathbf{g}\|} \right|}_{T_3} + \underbrace{ \left|\frac{\|H\mu \mathbf{u}\|}{\mu\|\mathbf{g}\|}-\frac{\|H\mu \mathbf{u}+O(\mu^2)\|}{\mu\|\mathbf{g}\|}\right|}_{T_4}. \label{eq:mediator95split} \end{align}\tag{35}\] Using \(\|\hat{H}\mu \mathbf{v}\|\le \mu\|\hat{H}\|\le \mu(1+\xi_3)\le 2\mu\) and \(\|\mathbf{g}+k_1\mathbf{v}_1\|\ge \|\mathbf{g}\|-\|k_1\mathbf{v}_1\|\ge (1-O(\xi_1))\|\mathbf{g}\|\ge \tfrac12\|\mathbf{g}\|\), \[\label{eq:T195bound} T_1 = \frac{|\eta-\|H\||\cdot\|\hat{H}\mu \mathbf{v}\|}{\mu\|\mathbf{g}+k_1\mathbf{v}_1\|} \le \frac{C}{\|\mathbf{g}\|}\,|\eta-\|H\||.\tag{36}\] By ([eq:eta_ratio]), \(|\eta-\|H\||\le \|H\|\left(O(\frac{\sqrt{\mu}}{\tan\beta})+O(\frac{n\xi_3}{\epsilon\delta_\kappa})\right)\). Hence \[\label{eq:T195bound95final} T_1 \le \frac{\|H\|}{\|\mathbf{g}\|}\left(O\!\left(\frac{\sqrt{\mu}}{\tan\beta}\right)+O\left(\frac{n\xi_3}{\epsilon\delta_\kappa}\right)\right).\tag{37}\] Using the inequality \(\left|\frac{1}{\|\mathbf{g}+k_1\mathbf{v}_1\|}-\frac{1}{\|\mathbf{g}\|}\right| =\frac{|\|\mathbf{g}\|-\|\mathbf{g}+k_1\mathbf{v}_1\||}{\|\mathbf{g}\|\|\mathbf{g}+k_1\mathbf{v}_1\|} \le \frac{\|k_1\mathbf{v}_1\|}{\|\mathbf{g}\|\|\mathbf{g}+k_1\mathbf{v}_1\|}\), we obtain \[\label{eq:T295bound} T_2 \le \frac{\|H\|\|\hat{H}\mu \mathbf{v}\|}{\mu}\cdot \frac{\|k_1\mathbf{v}_1\|}{\|\mathbf{g}\|\|\mathbf{g}+k_1\mathbf{v}_1\|} \le \frac{\|H\|}{\|\mathbf{g}\|}\cdot O(\xi_1).\tag{38}\] Moreover, \[\big|\|H\|\|\hat{H}\mu \mathbf{v}\|-\|H\mu \mathbf{u}\|\big| = \big|\|H\|\mu\lambda_\mathbf{v}-\mu\|H\mathbf{u}\|\big| \le \|H\|\cdot O(\mu (\epsilon\delta_\kappa+\xi_3)).\] which gives \[\label{eq:T395bound} T_3 \le \frac{\|H\|\cdot O(\mu (\epsilon\delta_\kappa+\xi_3))}{\mu\|\mathbf{g}\|} = \frac{\|H\|}{\|\mathbf{g}\|}\cdot O(\epsilon\delta_\kappa+\xi_3).\tag{39}\] As for \(T_4\), from ([eq:grad_diff_u]) we have \(\|O(\mu^2)\|\le C\mu^2\) and thus \[\label{eq:T495bound} T_4 \le \frac{\|O(\mu^2)\|}{\mu\|\mathbf{g}\|} \le O\!\left(\frac{\mu}{\|\mathbf{g}\|}\right).\tag{40}\] Plugging ([eq:T1_bound_final])–([eq:T4_bound]) into ([eq:mediator_split]) yields \[\label{eq:gamma95hatgamma} \left|\hat{\kappa}-\frac{1}{\mu}\frac{\|\nabla f(\mathbf{x}+\mu \mathbf{u})-\nabla f(\mathbf{x})\|}{\|\mathbf{g}\|}\right| \le \frac{\|H\|}{\|\mathbf{g}\|} \left( O\!\left(\frac{\sqrt{\mu}}{\tan\beta}\right) +O(\frac{n\xi_3}{\epsilon\delta_\kappa}) +O(\xi_1) +O(\epsilon\delta_\kappa+\xi_3) \right) + O\!\left(\frac{\mu}{\|\mathbf{g}\|}\right),\tag{41}\] Combine ([eq:hatgamma_expand]) and ([eq:gamma_hatgamma]), we have \[\begin{align} \label{eq:ratio95bound} \left|\hat{\kappa}-\frac{\|H\|}{\|\mathbf{g}\|}\right| &\le \frac{\|H\|}{\|\mathbf{g}\|} \left( O\!\left(\frac{\sqrt{\mu}}{\tan\beta}\right) +O(\frac{n\xi_3}{\epsilon\delta_\kappa}) +O(\xi_1) +O(\epsilon\delta_\kappa+\xi_3) \right) + O\!\left(\frac{\mu}{\|\mathbf{g}\|}\right)\notag\\ &\le O\left(\frac{\sqrt{\mu}}{\epsilon} +\frac{n\xi_3}{\epsilon^2\delta_\kappa} +\frac{\xi_1+\xi_3}{\epsilon} +\delta_\kappa\right). \end{align}\tag{42}\] By our choice of parameters in Algorithm [[algo:Comparison-ratio]](#algo:Comparison-ratio){reference-type=“ref” reference=“algo:Comparison-ratio”} and using the Lipschitzness, the right-hand side of ([eq:ratio_bound]) is at most \(O(\delta_\kappa)\), which completes our proof. ◻

Proof. We use the cubic Taylor remainder bound for any \(\mathbf{p}\in\mathbb{R}^n\), \[\label{eq:cand195taylor} f(\mathbf{x}_t+\mathbf{p})\le f(\mathbf{x}_t)+\mathbf{g}^\top \mathbf{p}+\frac{1}{2} \mathbf{p}^\top H \mathbf{p}+\frac{L_2}{6}\|\mathbf{p}\|^3.\tag{43}\] Denote \(\mathbf{p}_1=-r\hat{\mathbf{g}}\). We will bound the linear and quadratic terms for \(\mathbf{p}_1\) and then absorb the remainder term.

Let \(\bar \mathbf{g}:=\mathbf{g}/\|\mathbf{g}\|\). Since \(\|\hat{\mathbf{g}}-\bar \mathbf{g}\|\le\xi_1\) and both are unit vectors, \[\left\langle \bar \mathbf{g},\, \hat{\mathbf{g}} \right\rangle = 1-\frac{1}{2}\|\bar \mathbf{g}-\hat{\mathbf{g}}\|^2 \ge 1-\frac{1}{2}\xi_1^2 \ge 1-\xi_1.\] Therefore \[\label{eq:cand195lin} \mathbf{g}^\top \mathbf{p}_1 = -r\,\left\langle \mathbf{g},\, \hat{\mathbf{g}} \right\rangle = -r\,\|\mathbf{g}\|\,\left\langle \bar \mathbf{g},\, \hat{\mathbf{g}} \right\rangle \le -(1-\xi_1)\,r\,\|\mathbf{g}\|.\tag{44}\] Since \(\|\mathbf{p}_1\|=r\) and \(\|H\|\) denotes the spectral norm, \[\label{eq:cand195quad95worst} \frac{1}{2} \mathbf{p}_1^\top H \mathbf{p}_1 \le \frac{1}{2} \|H\|\,\|\mathbf{p}_1\|^2 = \frac{1}{2}\|H\|\,r^2.\tag{45}\] Plugging ([eq:cand1_lin]) and ([eq:cand1_quad_worst]) into ([eq:cand1_taylor]) with \(\mathbf{p}=\mathbf{p}_1\) yields \[\label{eq:cand195master} f(\mathbf{x}^{(1)})-f(\mathbf{x}_t) \le -(1-\xi_1)r\|\mathbf{g}\|+\frac{1}{2}\|H\|r^2+\frac{L_2}{6}r^3.\tag{46}\] Using \(\|\mathbf{g}\|\ge\epsilon\) and \(r=\sqrt{\epsilon/L_2}\) gives \[r\|\mathbf{g}\| \ge \,\frac{\epsilon^{3/2}}{\sqrt{L_2}}, \qquad r^2 = \frac{\epsilon}{L_2}, \qquad \frac{L_2}{6}r^3 = \frac{1}{6}\frac{\epsilon^{3/2}}{\sqrt{L_2}}.\] Hence ([eq:cand1_master]) becomes \[\label{eq:cand195master95scaled} f(\mathbf{x}^{(1)})-f(\mathbf{x}_t) \le -\Big((1-\xi_1)-\frac{1}{6}\Big)\frac{\epsilon^{3/2}}{\sqrt{L_2}} +\frac{1}{2}\|H\|\cdot\frac{\epsilon}{L_2}.\tag{47}\] We now argue that in each of the three cases (i)–(iii), the positive quadratic term is controlled so that the right hand side of ([eq:cand1_master_scaled]) is less than \(-C\,\epsilon^{3/2}\) after choosing \(c\) as a sufficiently small constant.

In Case (i), \(\|H\|\le \sqrt{L_2\epsilon}\). Then the quadratic term in ([eq:cand1_master_scaled]) is bounded by \[\frac{1}{2}\|H\|\cdot\frac{\epsilon}{L_2} \le \frac{1}{2} \sqrt{L_2\epsilon}\cdot\frac{\epsilon}{L_2} = \frac{1}{2}\frac{\epsilon^{3/2}}{\sqrt{L_2}}.\] Therefore \[f(\mathbf{x}^{(1)})-f(\mathbf{x}_t) \le -\left((1-\xi_1)-\frac{1}{6}-\frac{1}{2} \right)\frac{\epsilon^{3/2}}{\sqrt{L_2}}.\] So we have \[f(\mathbf{x}^{(1)})\le f(\mathbf{x}_t)-C\,\epsilon^{3/2}\] for an absolute constant \(C>0\).

In Case (ii), \(H\preceq \mathbf{0}\) or \(H\succeq \mathbf{0}\). By \(L_2\)-Lipschitzness, for any \(p\), \[f(\mathbf{x}_t+\mathbf{p})\le f(\mathbf{x}_t)+\mathbf{g}^\top \mathbf{p}+\frac{1}{2} \mathbf{p}^\top H \mathbf{p}+\frac{L_2}{6}\|\mathbf{p}\|^3.\] Apply this with \(\mathbf{p}=\mathbf{p}_1=-r\hat{\mathbf{g}}\) to obtain \[\label{eq:l195smooth95step} f(\mathbf{x}^{(1)})-f(\mathbf{x}_t)\le r\mathbf{g}^\top \hat{\mathbf{g}}+\frac{r^2}{2}\hat{\mathbf{g}}^\top H\hat{\mathbf{g}}+\frac{L_2}{6}|r|^3.\tag{48}\]

Let \(\bar \mathbf{g}:=\mathbf{g}/\|\mathbf{g}\|\). Since \(\|\hat{\mathbf{g}}-\bar \mathbf{g}\|\le \xi_1\) and both are unit vectors, \[\left\langle \bar \mathbf{g},\, \hat{\mathbf{g}} \right\rangle =1-\frac{1}{2}\|\bar \mathbf{g}-\hat{\mathbf{g}}\|^2 \ge 1-\frac{1}{2}\xi_1^2 \ge 1-\xi_1.\] Therefore \[\mathbf{g}^\top \mathbf{p}_1=-r\,\left\langle \mathbf{g},\, \hat{\mathbf{g}} \right\rangle =-r\|\mathbf{g}\|\,\left\langle \bar \mathbf{g},\, \hat{\mathbf{g}} \right\rangle \le -(1-\xi_1)\,r\|\mathbf{g}\|.\]

If \(H\preceq \mathbf{0}\), we have \[\frac{1}{2}\mathbf{p}_1^\top H\mathbf{p}_1\le 0.\] so \[f(\mathbf{x}^{(1)})- f(\mathbf{x}_t)\le\mathbf{g}^\top \mathbf{p}_1+\frac{L_2}{6}|r|^3\le-\epsilon\left((1-\xi_1)-\frac{1}{6}\right)r=-\Omega(\epsilon^{3/2}).\]

Else if \(H\succeq \mathbf{0}\), consider the 1-dimension function \(f_\star\) on the direction \(\hat{\mathbf{g}}\). By the Lipschitzness of \(H\), for any \(l\in[0,r]\), we have \[f_\star''(\mathbf{x}_t-l\hat{\mathbf{g}})\ge 0.\] It tells us that \[f_\star'(\mathbf{x}_t-l\hat{\mathbf{g}})\ge \epsilon.\] So the function value descent \[f(\mathbf{x}^{(1)})- f(\mathbf{x}_t)\le -r\epsilon=-\Omega(\epsilon^{3/2}).\] ◻

Proof. Consider \(\phi(t)=f(\mathbf{x}_t+l \mathbf{v})\) and expand around \(l=0\), we have \[\phi(l)=\phi(0)+l\left\langle \mathbf{g},\, \mathbf{v} \right\rangle+\frac{1}{2} l^2\,\mathbf{v}^\top H \mathbf{v}+ O(L_2|l|^3).\] For \(|\left\langle \mathbf{g},\, \mathbf{v} \right\rangle|\ge \frac{1}{2}\|\mathbf{g}\|\), choosing \(l=-r\,\mathrm{sign}(\left\langle \mathbf{g},\, \mathbf{v} \right\rangle)\) yields \[\phi(l)-\phi(0)\le -r\cdot \tfrac12\|\mathbf{g}\| + O(L_2 r^3) \le -\Omega(\epsilon^{3/2})\] since \(\|\mathbf{g}\|\ge \epsilon\) and \(L_2 r^3=\epsilon^{3/2}/\sqrt{L_2}\). If instead \(|\left\langle \mathbf{g},\, \mathbf{v} \right\rangle|<\frac{1}{2}\|\mathbf{g}\|\), then \(\mathbf{g}\) has a component orthogonal to \(\mathbf{v}\) of magnitude at least \(\frac{\sqrt{3}}{2}\|\mathbf{g}\|\), and Candidate 1 already provides a decrease of order \(r\|\mathbf{g}\|\) up to quadratic/cubic corrections; therefore the best-of-all selection ensures the stated decrease. ◻

Proof. This is a direct corollary of Lemma [[lem:tr_quadratic]](#lem:tr_quadratic){reference-type=“ref” reference=“lem:tr_quadratic”}, taking \(q=m_{\mathbf{x}_t}\), \(b=\mathbf{g}\) and \(A=\hat{\kappa}\hat{H}\). ◻

Proof. We use the cubic Taylor remainder bound for any \(\mathbf{p}\in\mathbb{R}^n\), \[f(\mathbf{x}_t+\mathbf{p})\le f(\mathbf{x}_t)+\mathbf{g}^\top \mathbf{p}+\frac{1}{2} \mathbf{p}^\top H \mathbf{p}+\frac{L_2}{6}\|\mathbf{p}\|^3.\] Plugging in \(\mathbf{p}_4=r\mathbf{v}_{\min}\) we have \[\begin{align} f(\mathbf{x}^{(4)})&\le f(\mathbf{x}_t)+r\mathbf{g}^\top \mathbf{v}_{\min}+\frac{1}{2} r^2 \mathbf{v}_{\min}^\top H \mathbf{v}_{\min}+\frac{L_2}{6}r^3 \\ &= f(\mathbf{x}_t)+\sqrt{\frac{\epsilon}{L_2}}\mathbf{g}^\top \mathbf{v}_{\min}+\frac{1}{2} \frac{\epsilon}{L_2} \mathbf{v}_{\min}^\top H \mathbf{v}_{\min}+\frac{L_2}{6}\cdot \frac{\epsilon^{3/2}}{L_2^{3/2}} \\ &\le f(\mathbf{x}_t)+\sqrt{\frac{\epsilon^3}{L_2}}\left(-\frac{1}{2}+\frac{1}{6}\right)=f(\mathbf{x}_t)-c_4\epsilon^{3/2}. \end{align}\] ◻

Proof. Denote \(x^{(3)}=\mathbf{x}_t+\mathbf{p}_3\), \(x^{(4)}=\mathbf{x}_t+\mathbf{p}_4\). For our choice of \(x^{(3)}\), we have \[m_{\mathbf{x}_t}(\mathbf{p}_3)\le m_{\mathbf{x}_t}(\mathbf{p}_4),\] which is equivalent to \[\label{eq:sosp951} T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_3)\le T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_4).\tag{49}\] By Lemma [[lem:taylor_cubic_best]](#lem:taylor_cubic_best){reference-type=“ref” reference=“lem:taylor_cubic_best”} we have \[\label{eq:sosp952} |f(\mathbf{x}_t+\mathbf{p}_3)-T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_3)|\le \frac{L_2}{6}\|\mathbf{p}_3\|^3=\frac{L_2}{6}r^3,\tag{50}\] \[\label{eq:sosp953} |f(\mathbf{x}_t+\mathbf{p}_4)-T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_4)|\le \frac{L_2}{6}\|\mathbf{p}_4\|^3=\frac{L_2}{6}r^3.\tag{51}\] Combining ([eq:sosp_1]), ([eq:sosp_2]) and ([eq:sosp_3]), we can conclude ([eq:trust_region_better]). ◻

Proof of . Lemma 7] Assume \(\|\mathbf{g}(\mathbf{x}_t)\|\ge \epsilon\). Let \(\mathbf{x}_{t+1}=\arg\min\{f(\mathbf{x}^{(1)}),f(\mathbf{x}^{(2)}),f(\mathbf{x}^{(3)})\}\) in Algorithm [[algo:best-of-all]](#algo:best-of-all){reference-type=“ref” reference=“algo:best-of-all”}. By Lemma [[lem:taylor_cubic_best]](#lem:taylor_cubic_best){reference-type=“ref” reference=“lem:taylor_cubic_best”}, for each candidate \(\mathbf{p}_i=\mathbf{x}^{(i)}-\mathbf{x}_t\) with \(\|\mathbf{p}_i\|\le r\), \[\label{eq:model95to95true95transfer} f(\mathbf{x}^{(i)})-f(\mathbf{x}_t) \le \big(T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_i)-T_{\mathbf{x}_t}(\mathbf{x}_t)\big) + \frac{L_2}{3}r^3.\tag{52}\]

We show that at least one candidate has \(T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_i)-T_{\mathbf{x}_t}(\mathbf{x}_t)\le -c' r\epsilon\) for a constant \(c'>0\); then since \(\frac{L_2}{3}r^3=\frac{1}{3}\epsilon^{3/2}/\sqrt{L_2}\), for \(c\) sufficiently small, we obtain \(f(\mathbf{x}^{(i)})-f(\mathbf{x}_t)\le -\Omega(\epsilon^{3/2})\) and thus the same for \(\mathbf{x}_{t+1}\).

If the Hessian is rank-one or \(\left\langle \mathbf{g},\, \mathbf{v} \right\rangle\ge\frac{1}{2}\|\mathbf{g}\|\), \(\mathbf{x}^{(2)}\) ensures the \(\Omega(\epsilon^{3/2})\) decrease by Lemma [[lem:cand2_descent]](#lem:cand2_descent){reference-type=“ref” reference=“lem:cand2_descent”}. Else, for cases in Lemma [[lem:cand1_descent]](#lem:cand1_descent){reference-type=“ref” reference=“lem:cand1_descent”}, \[T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_1)-T_{\mathbf{x}_t}(\mathbf{x}_t)\le -\frac{99}{100}r\|\mathbf{g}\|+\frac{1}{2} r^2\|H\|.\] Using the ratio \(\|H\|/\|\mathbf{g}\|\approx \hat{\kappa}\), we have \[\frac{1}{2} r^2\|H\|\le c r\|\mathbf{g}\|\] at the scale \(r=\sqrt{\epsilon/L_2}\), so the linear term dominates for small \(\epsilon\). Hence \[T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_1)-T_{\mathbf{x}_t}(\mathbf{x}_t)\le -\Omega(r\|\mathbf{g}\|)\le -\Omega(r\epsilon)=-\Omega(\epsilon^{3/2}).\] Then ([eq:model_to_true_transfer]) yields \[f(\mathbf{x}^{(1)})-f(\mathbf{x}_t)\le -\Omega(\epsilon^{3/2}).\]

In the case that \(H\) is not rank-one, \(\|H\|\ge\sqrt{L_2\epsilon}\), and \(H\) is not positive or negative definite. Denote the eigenvector of \(H\) that corresponding to the largest magnitude eigenvalue as \(\mathbf{v}\) and assume that \(\left\langle \mathbf{v},\, \mathbf{g} \right\rangle\le\frac{1}{2}\|\mathbf{g}\|\).

If ([eq:cand3_stationary]) fails, then by Lemma [[lem:cand3_descent]](#lem:cand3_descent){reference-type=“ref” reference=“lem:cand3_descent”}, we have \[m_{\mathbf{x}_t}(\mathbf{p}_3)-m_{\mathbf{x}_t}(\mathbf{0})\le -\frac{1}{2} r\|\nabla m_{\mathbf{x}_t}(\mathbf{p}_3)\|.\] Since the failure of ([eq:cand3_stationary]) means \(\|\nabla m_{\mathbf{x}_t}(\mathbf{p}_3)\|>\epsilon\), we get \[m_{\mathbf{x}_t}(\mathbf{p}_3)-m_{\mathbf{x}_t}(\mathbf{0})\le -\frac{1}{2} r\epsilon=-\Omega(\epsilon^{3/2}).\] By the constant-factor accuracy of \(\hat{\kappa}\) and \(\hat{H}\), the model \(m_{\mathbf{x}_t}\) is a constant-factor approximation of the quadratic model \(T_{\mathbf{x}_t}\) when \(\|\mathbf{p}\|\le r\). Thus \[T_{\mathbf{x}_t}(\mathbf{x}_t+\mathbf{p}_3)-T_{\mathbf{x}_t}(\mathbf{x}_t)\le -\Omega(\epsilon^{3/2}),\] and ([eq:model_to_true_transfer]) gives \[f(\mathbf{x}^{(3)}-f(\mathbf{x}_t)\le -\Omega(\epsilon^{3/2}).\]

Assume \(\|\mathbf{g}\|\le\epsilon\) and \(\lambda_{\min}(H)\le-\sqrt{L_2\epsilon}\). By Lemma [[lem:trust_region_better]](#lem:trust_region_better){reference-type=“ref” reference=“lem:trust_region_better”} we have \[f(\mathbf{x}_3)-f(\mathbf{x}_t)\le -\Omega(\epsilon^{3/2}).\]

In all cases, at least one candidate \(x^{(i)}\) satisfies \(f(\mathbf{x}^{(i)})\le f(\mathbf{x}_t)-C\epsilon^{3/2}\). Since \(\mathbf{x}_{t+1}=\arg\min\{f(\mathbf{x}^{(1)}),f(\mathbf{x}^{(2)}),f(\mathbf{x}^{(3)})\}\), we have \(f(\mathbf{x}_{t+1})\le f(\mathbf{x}^{(i)})\) for that index \(i\), proving ([eq:best_of_all_descent]). ◻

Proof of . Theorem 8] We use contradiction to prove the theorem. If the statement is not true and any iterate \(\mathbf{x}_t\) is not an \(\epsilon\)-stationary point, by Lemma [7](#lem:best-of-all){reference-type=“ref” reference=“lem:best-of-all”} we have \[\begin{align} \mathbb{E}[f(\mathbf{x}_{t+1})-f(\mathbf{x}_t)]\leq -\frac{2C}{3}\epsilon^{1.5}, \end{align}\] where \(C\) is the constant in Lemma [7](#lem:best-of-all){reference-type=“ref” reference=“lem:best-of-all”}, since we have \(f(\mathbf{x}_{t+1})-f(\mathbf{x}_t)\leq -C\epsilon^{1.5}\) if Algorithm [[algo:normhess]](#algo:normhess){reference-type=“ref” reference=“algo:normhess”} succeeds, which happens with probability at least \(2/3\) by Theorem [[thm:main_app]](#thm:main_app){reference-type=“ref” reference=“thm:main_app”}, and we have \(f(\mathbf{x}_{t+1})-f(\mathbf{x}_t)\leq 0\) otherwise. Sum from \(t=0\) to \(T-1\) we get \[\begin{align} \mathbb{E}[f(\mathbf{x}_T)-f(\mathbf{x}_0)]&=\sum_{t=0}^{T-1}\mathbb{E}[f(\mathbf{x}_{t+1})-f(\mathbf{x}_t)] =-\sum_{t=0}^{T-1}C'\epsilon^{1.5} =-TC'\epsilon^{1.5}. \end{align}\] By Markov’s Inequality, \[\begin{align} \Pr(f(\mathbf{x}_0)-f(\mathbf{x}_T)\ge \frac{1}{2}TC'\epsilon^{1.5}) \ge \frac{a-\mathbb{E}[f(\mathbf{x}_0)-f(\mathbf{x}_T)]}{a-\frac{1}{2}TC'\epsilon^{1.5}} =\frac{2}{3}. \end{align}\]

Therefore, with probability at least \(2/3\), the total decrease of function value is larger than \(f(\mathbf{x}_0)-f(\mathbf{x}^\star)\), which leads to a contradiction. Consequently, in \(T\) steps, we have visited at least an \(\epsilon\)-stationary point. ◻

Proof. By the triangle inequality, we have \[\begin{align} \left\|\frac{\mathbf{v}}{\|\mathbf{v}\|}-\frac{\mathbf{v}'}{\|\mathbf{v}'\|}\right\|&\leq \left\|\frac{\mathbf{v}}{\|\mathbf{v}\|}-\frac{\mathbf{v}'}{\|\mathbf{v}\|}\right\|+\left\|\frac{\mathbf{v}'}{\|\mathbf{v}\|}-\frac{\mathbf{v}'}{\|\mathbf{v}'\|}\right\|\\ &=\frac{\|\mathbf{v}-\mathbf{v}'\|}{\|\mathbf{v}\|}+\frac{|\|\mathbf{v}\|-\|\mathbf{v}'\||\|\mathbf{v}'\|}{\|\mathbf{v}\|\|\mathbf{v}'\|}\\ &\leq\frac{\tau}{\gamma}+\frac{\tau}{\gamma}=\frac{2\tau}{\gamma}. \end{align}\] ◻

Proof. By the triangle inequality, we have \[\begin{align} \left|\left\langle\frac{\mathbf{v}_1}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2}{\|\mathbf{v}_2\|}\right\rangle-\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1'\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2'\|}\right\rangle\right|&\leq \left|\left\langle\frac{\mathbf{v}_1}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2}{\|\mathbf{v}_2\|}\right\rangle-\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2\|}\right\rangle\right| \\ &\quad+\left|\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2\|}\right\rangle-\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1'\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2'\|}\right\rangle\right|. \end{align}\] On the one hand, by the triangle inequality and the Cauchy-Schwarz inequality, \[\begin{align} \left|\left\langle\frac{\mathbf{v}_1}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2}{\|\mathbf{v}_2\|}\right\rangle-\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2\|}\right\rangle\right| &\leq \frac{1}{\|\mathbf{v}_1\|\|\mathbf{v}_2\|}(\left|\langle\mathbf{v}_1,\mathbf{v}_2\rangle-\langle\mathbf{v}_1,\mathbf{v}_2'\rangle\right|+\left|\langle\mathbf{v}_1,\mathbf{v}_2'\rangle-\langle\mathbf{v}_1',\mathbf{v}_2'\rangle\rangle\right|)\\ &\leq \frac{\|\mathbf{v}_2-\mathbf{v}_2'\|}{\|\mathbf{v}_2\|}+\frac{\|\mathbf{v}_1-\mathbf{v}_1'\|\|\mathbf{v}_2'\|}{\|\mathbf{v}_1\|\|\mathbf{v}_2\|}\\ &\leq \frac{\tau}{\gamma}+\frac{\tau(\gamma+\tau)}{\gamma^{2}}. \end{align}\] On the other hand, by the Cauchy-Schwarz inequality, \(|\langle \mathbf{v}_1',\mathbf{v}_2'\rangle|\leq\|\mathbf{v}_1'\|\|\mathbf{v}_2'\|\), and hence \[\begin{align} \left|\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2\|}\right\rangle-\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1'\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2'\|}\right\rangle\right|&=|\langle \mathbf{v}_1',\mathbf{v}_2'\rangle|\left|\frac{1}{\|\mathbf{v}_1\|\|\mathbf{v}_2\|}-\frac{1}{\|\mathbf{v}_1'\|\|\mathbf{v}_2'\|}\right|\\ &\leq \left|\frac{\|\mathbf{v}_1'\|\|\mathbf{v}_2'\|}{\|\mathbf{v}_1\|\|\mathbf{v}_2\|}-1\right|\\ &\leq \left(\frac{\gamma+\tau}{\gamma}\right)^{2}-1. \end{align}\] In all, due to \(\tau<\gamma\), \[\begin{align} \left|\left\langle\frac{\mathbf{v}_1}{\|\mathbf{v}_1\|},\frac{\mathbf{v}_2}{\|\mathbf{v}_2\|}\right\rangle-\left\langle\frac{\mathbf{v}_1'}{\|\mathbf{v}_1'\|},\frac{\mathbf{v}_2'}{\|\mathbf{v}_2'\|}\right\rangle\right|\leq \frac{\tau}{\gamma}+\frac{\tau(\gamma+\tau)}{\gamma^{2}}+\left(\frac{\gamma+\tau}{\gamma}\right)^{2}-1=\frac{2\tau(2\gamma+\tau)}{\gamma^{2}}\leq\frac{6\tau}{\gamma}. \end{align}\] ◻

Proof. We have \[\begin{align} \frac{1-\langle\frac{\mathbf{v}+\mathbf{g}}{\|\mathbf{v}+\mathbf{g}\|},\frac{\mathbf{v}}{\|\mathbf{v}\|}\rangle^{2}}{1-\langle\frac{\mathbf{v}-\mathbf{g}}{\|\mathbf{v}-\mathbf{g}\|},\frac{\mathbf{v}}{\|\mathbf{v}\|}\rangle^{2}}\cdot\frac{\|\mathbf{v}+\mathbf{g}\|^{2}}{\|\mathbf{v}-\mathbf{g}\|^{2}}&=\frac{\|\mathbf{v}+\mathbf{g}\|^{2}-\langle \mathbf{v}+\mathbf{g},\frac{\mathbf{v}}{\|\mathbf{v}\|}\rangle^{2}}{\|\mathbf{v}-\mathbf{g}\|^{2}-\langle \mathbf{v}-\mathbf{g},\frac{\mathbf{v}}{\|\mathbf{v}\|}\rangle^{2}}\\ &=\frac{\langle\mathbf{v}+\mathbf{g},\mathbf{v}+\mathbf{g}\rangle-(\|\mathbf{v}\|+\frac{\langle\mathbf{v},\mathbf{g}\rangle}{\|\mathbf{v}\|})^{2}}{\langle\mathbf{v}-\mathbf{g},\mathbf{v}-\mathbf{g}\rangle-(\|\mathbf{v}\|-\frac{\langle\mathbf{v},\mathbf{g}\rangle}{\|\mathbf{v}\|})^{2}}\\ &=\frac{\|\mathbf{v}\|^{2}+\|\mathbf{g}\|^{2}+2\langle \mathbf{v},\mathbf{g}\rangle-(\|\mathbf{v}\|^{2}+2\langle \mathbf{v},\mathbf{g}\rangle+\frac{\langle \mathbf{v},\mathbf{g}\rangle^{2}}{\|\mathbf{v}\|^{2}})}{\|\mathbf{v}\|^{2}+\|\mathbf{g}\|^{2}-2\langle \mathbf{v},\mathbf{g}\rangle-(\|\mathbf{v}\|^{2}-2\langle \mathbf{v},\mathbf{g}\rangle+\frac{\langle \mathbf{v},\mathbf{g}\rangle^{2}}{\|\mathbf{v}\|^{2}})}=1. \end{align}\] ◻

Proof. Write \[\frac{A}{\|A\|}-\frac{B}{\|B\|} = \frac{A-B}{\|A\|} + B\left(\frac{1}{\|A\|}-\frac{1}{\|B\|}\right).\] Since \(\|A\|\ge \|B\|-\|A-B\|\ge \|B\|-\rho\ge \frac{1}{2}\|B\|\), we have \(\|A\|^{-1}\le 2\|B\|^{-1}\). Also, \[\left|\frac{1}{\|A\|}-\frac{1}{\|B\|}\right| = \frac{|\|A\|-\|B\||}{\|A\|\|B\|} \le \frac{\rho}{(\frac{1}{2}\|B\|)\|B\|} = \frac{2\rho}{\|B\|^2}.\] Therefore, \[\left\|\frac{A}{\|A\|}-\frac{B}{\|B\|}\right\| \le \frac{\|A-B\|}{\|A\|} + \|B\|\left|\frac{1}{\|A\|}-\frac{1}{\|B\|}\right| \le \frac{\rho}{\frac{1}{2}\|B\|} + \|B\|\frac{2\rho}{\|B\|^2} = \frac{4\rho}{\|B\|}.\] ◻

Proof. For any \(\mathbf{v}\in\mathbb{R}^n\) with \(\|\mathbf{v}\|=1\), \[E\mathbf{v}=\sum_{i=1}^n v_i(E\mathbf{e}_i),\] so \[\|E\mathbf{v}\| \le \sum_{i=1}^n |v_i|\|E\mathbf{e}_i\| \le \varepsilon_c\sum_{i=1}^n |v_i| \le \varepsilon_c\sqrt{n}\Big(\sum_{i=1}^n v_i^2\Big)^{1/2} =\varepsilon_c\sqrt{n}.\] Taking the supremum over \(\|\mathbf{v}\|=1\) yields \(\|E\|\le \varepsilon_c\sqrt{n}\). ◻

Proof. Because \(r_1=1\) and \(\mathbf{u}_1\) is a unit vector, the first column of \(H^\star\) equals \(H^\star \mathbf{e}_1 = \mathbf{u}_1\) and thus \[\|H^\star\| \ge \|H^\star \mathbf{e}_1\| = \|\mathbf{u}_1\| = 1.\] ◻

Proof. We analyze \(\mathbf{g}_i\) here, \(\mathbf{g}_{1i}\) case is similar. Assume that \(\mathbf{v}\) is an eigenvector of \(H\) corresponding to minimum eigenvalue, and \(|\langle \mathbf{e}_t, \mathbf{v}\rangle|\ge\frac{1}{\sqrt{n}}\). Fix an index \(i\). Denote \[\mathbf{y}_i^0=\mathbf{e}_i,\; \mathbf{y}_i^1=\mathbf{e}_i+\sigma \mathbf{e}_t,\; \mathbf{y}_i^2=\mathbf{e}_i-\sigma \mathbf{e}_t.\] Observe that for any \(j\neq k\in\{0,1,2\}\), \[|\langle \mathbf{y}_i^j-\mathbf{y}_i^k, \mathbf{v}\rangle|\ge\frac{\sigma}{\sqrt{n}}.\] This implies at least two of three queries satisfies \[\label{eq:lower95bound95hv} |\langle \mathbf{y}_i^j, \mathbf{v}\rangle|\ge\frac{\sigma}{2\sqrt{n}}.\tag{54}\] For each index \(j\) satisfies ([eq:lower_bound_hv]), by taking \(\gamma_\mathbf{y}= \frac{\sigma}{2\sqrt{n}}\), \(\gamma_\mathbf{x}=\epsilon\), accuracy \(\hat{\delta}=\frac{\eta}{4}\) in Algorithm [[algo:Comparison-Triangle]](#algo:Comparison-Triangle){reference-type=“ref” reference=“algo:Comparison-Triangle”}, we know at least two queries in the setting \(\{\mathbf{y}_i^0, \mathbf{y}_i^1,\mathbf{y}_i^2\}\) satisfies the condition \(|\langle\mathbf{y}_i^j, \mathbf{v}\rangle|\ge\gamma_\mathbf{y}\). Therefore, according to Theorem [5](#thm:triangle){reference-type=“ref” reference=“thm:triangle”}, at least two of three inequalities hold: \[\left\| \mathbf{g}_i^0-\frac{\mathbf{h}_i}{\|\mathbf{h}_i\|}\right\|\le\frac{\eta}{4},\quad \left\| \mathbf{g}_i^+-\frac{\mathbf{h}_i+\sigma \mathbf{h}_t}{\|\mathbf{h}_i+\sigma \mathbf{h}_t\|}\right\|\le\frac{\eta}{4}, \quad \left\| \mathbf{g}_i^--\frac{\mathbf{h}_i-\sigma \mathbf{h}_t}{\|\mathbf{h}_i-\sigma \mathbf{h}_t\|}\right\|\le\frac{\eta}{4}.\] In non-degenerate case, our choice \((\mathbf{v}_1, \mathbf{v}_2)\gets \arg\max_{\mathbf{v}_1\neq \mathbf{v}_2\in\{\mathbf{g}_i^{0},\mathbf{g}_i^{+},\mathbf{g}_i^{-}\}}\langle \mathbf{v}_1, \mathbf{v}_2\rangle\) tells \(\mathbf{v}_1\) and \(\mathbf{v}_2\) are two success queries to Algorithm [[algo:Comparison-Triangle]](#algo:Comparison-Triangle){reference-type=“ref” reference=“algo:Comparison-Triangle”}, take \(\mathbf{v}_1=\mathbf{g}_i^+\), \(\mathbf{v}_2=\mathbf{g}_i^-\) for example, other case is the same, from Lemma [13](#lem:dist-norm-vector){reference-type=“ref” reference=“lem:dist-norm-vector”} we have \[\begin{align} \left\|\frac{\mathbf{v}_1+\mathbf{v}_2}{\|\mathbf{v}_1+\mathbf{v}_2\|}-\frac{\mathbf{h}_i}{\|\mathbf{h}_i\|}\right\| &\le\left\| \mathbf{g}_i^+-\frac{\mathbf{h}_i+\sigma \mathbf{h}_t}{\|\mathbf{h}_i+\sigma \mathbf{h}_t\|}\right\|+\left\| \mathbf{g}_i^--\frac{\mathbf{h}_i-\sigma \mathbf{h}_t}{\|\mathbf{h}_i-\sigma \mathbf{h}_t\|}\right\|+\left\| \frac{\mathbf{h}_i+\sigma \mathbf{h}_t}{\|\mathbf{h}_i+\sigma \mathbf{h}_t\|}-\frac{\mathbf{h}_i-\sigma \mathbf{h}_t}{\|\mathbf{h}_i-\sigma \mathbf{h}_t\|}\right\| \\ &\le \frac{\eta}{4}+\frac{\eta}{4}+\frac{2\eta}{4}=\eta, \end{align}\] where the last inequality holds because \(\langle \mathbf{g}_i^{+},\mathbf{g}_i^{-}\rangle \ge 1-\tau_\alpha\) tell us \(\|\mathbf{h}_i\|/\|\sigma \mathbf{h}_t\|\ge\frac{4}{\eta}\).

In the degenerate case \(\langle \mathbf{g}_i^{+},\mathbf{g}_i^{-}\rangle \le 1-\tau_\alpha\), we have \(\|\mathbf{h}_i\|/\|\sigma \mathbf{h}_t\|\le\frac{4}{\eta}\), i.e., \[\|\mathbf{h}_i\|\le\frac{\eta}{32\sqrt{n}}.\] In this case, taking \(\mathbf{g}_i=0\) guarantees error on this column is \(O\left(\frac{\eta}{\sqrt{n}}\right)\). ◻

Proof. By triangle inequality, \(\|\mathbf{a}+\rho \mathbf{c}\|\ge \|\mathbf{a}\|-\rho\|\mathbf{c}\|\ge \|\mathbf{a}\|-\rho\|\mathbf{h}_1\|\). Using \(\|\mathbf{a}\|\ge r_{\min}\|\mathbf{h}_1\|\) and \(\rho\le r_{\min}/2\), we get \(\|\mathbf{a}+\rho \mathbf{c}\|\ge \frac{1}{2}\|\mathbf{a}\|\). Therefore, \[\mathbf{v}-\mathbf{u} = \frac{\mathbf{a}+\rho \mathbf{c}}{\|\mathbf{a}+\rho \mathbf{c}\|}-\frac{\mathbf{a}}{\|\mathbf{a}\|} = \mathbf{a}\left(\frac{1}{\|\mathbf{a}+\rho \mathbf{c}\|}-\frac{1}{\|\mathbf{a}\|}\right)+\frac{\rho}{\|\mathbf{a}+\rho \mathbf{c}\|}\mathbf{c}.\] Hence \[\|\mathbf{v}-\mathbf{u}\| \le \|\mathbf{a}\|\left|\frac{1}{\|\mathbf{a}+\rho \mathbf{c}\|}-\frac{1}{\|\mathbf{a}\|}\right| + \frac{\rho}{\|\mathbf{a}+\rho \mathbf{c}\|}\|\mathbf{c}\|.\] Also \[\left|\frac{1}{\|\mathbf{a}+\rho \mathbf{c}\|}-\frac{1}{\|\mathbf{a}\|}\right| = \frac{|\|\mathbf{a}+\rho \mathbf{c}\|-\|\mathbf{a}\||}{\|\mathbf{a}+\rho \mathbf{c}\|\|\mathbf{a}\|} \le \frac{\rho\|\mathbf{c}\|}{\|\mathbf{a}+\rho \mathbf{c}\|\|\mathbf{a}\|},\] by which we can conclude that \[\|\mathbf{v}-\mathbf{u}\| \le \|\mathbf{a}\|\frac{\rho\|\mathbf{c}\|}{\|\mathbf{a}+\rho \mathbf{c}\|\|\mathbf{a}\|} + \frac{\rho}{\|\mathbf{a}+\rho \mathbf{c}\|}\|\mathbf{c}\| = \frac{2\rho\|\mathbf{c}\|}{\|\mathbf{a}+\rho \mathbf{c}\|} \le \frac{2\rho\|\mathbf{h}_1\|}{\frac{1}{2}\|\mathbf{a}\|} = \frac{4\rho}{r_{\min}}.\] ◻

Proof. Let \(\bar \mathbf{z}=\mathbf{z}/\|\mathbf{z}\|\). Define \(\mathbf{e}:=\|\mathbf{z}\|(\hat{\mathbf{z}}-\bar \mathbf{z})\). Then \(\|\mathbf{e}\|\le \xi\|\mathbf{z}\|\) and \(\mathbf{z}+\mathbf{e}=\|\mathbf{z}\|\hat{\mathbf{z}}\), hence \(\hat{\mathbf{z}}=(\mathbf{z}+\mathbf{e})/\|\mathbf{z}+\mathbf{e}\|\). ◻

Proof. Standard integral remainder; included for completeness. \[\nabla f(\mathbf{x}+\mu \mathbf{v})-\nabla f(\mathbf{x})=\int_0^\mu \nabla^2 f(\mathbf{x}+t \mathbf{v})\,\mathbf{v}\,\mathrm{d}t =\mu \nabla^2 f(\mathbf{x})\mathbf{v}+\int_0^\mu (\nabla^2 f(\mathbf{x}+t \mathbf{v})-\nabla^2 f(\mathbf{x}))\mathbf{v}\,\mathrm{d}t,\] so \(\|\mathbf{r}_\mu\|\le \int_0^\mu L_2 t\,\mathrm{d}t=\tfrac{1}{2}L_2\mu^2\). ◻

Proof. Apply Lemma [15](#lem:vector-norm-1){reference-type=“ref” reference=“lem:vector-norm-1”} to the pair \((\mathbf{v},\mathbf{g})=(\mathbf{d}_1,\mathbf{d})\): it expresses the norm ratio \(\|\mathbf{d}\|/\|\mathbf{d}_1\|\) via the sines of the angles between \(\mathbf{d}_1\), \(\mathbf{d}_1+\mathbf{d}\) and \(\mathbf{d}\). Noting that \(\hat{\mathbf{g}}_1=\mathbf{d}_1/\|\mathbf{d}_1\|\) and \(\hat{\mathbf{g}}_2=\mathbf{d}_2/\|\mathbf{d}_2\|\) by ([eq:g_noise_forms]), we obtain ([eq:eta_prime_ratio_exact]). ◻

Proof. If \(\|\mathbf{p}^\star\|<r\), first-order optimality gives \(b+A \mathbf{p}^\star=\mathbf{0}\). Otherwise \(\|\mathbf{p}^\star\|=r\) and there exists \(\lambda\ge 0\) with \(b+A \mathbf{p}^\star+\lambda \mathbf{p}^\star=\mathbf{0}\) and \(A+\lambda I\succeq \mathbf{0}\). Then \(\nabla q(\mathbf{p}^\star)=b+A \mathbf{p}^\star=-\lambda \mathbf{p}^\star\) so \(\|\nabla q(\mathbf{p}^\star)\|=\lambda r\). Moreover, \[q(\mathbf{0})-q(\mathbf{p}^\star)=-b^\top \mathbf{p}^\star-\tfrac12 (\mathbf{p}^\star)^\top A \mathbf{p}^\star.\] From \(b+A \mathbf{p}^\star+\lambda \mathbf{p}^\star=\mathbf{0}\) we get \(-b^\top \mathbf{p}^\star=\lambda r^2+(\mathbf{p}^\star)^\top A \mathbf{p}^\star\). Using \(A+\lambda I\succeq \mathbf{0}\) we have \((\mathbf{p}^\star)^\top A \mathbf{p}^\star\ge -\lambda r^2\), hence \(q(\mathbf{0})-q(\mathbf{p}^\star)\ge \frac{1}{2}\lambda r^2=\frac{1}{2} r\|\nabla q(\mathbf{p}^\star)\|\). ◻

Proof of . Theorem [thm:lazy_TR_value]] Take stepsize \(r=c\sqrt{\epsilon/n}\) where \(c\) is an absolute constant that is small enough, and let \(\mathbf{x}_{km+t+1}=\mathbf{x}_{km+t}+\mathbf{p}\). By Lemma [[lem:taylor_cubic_best]](#lem:taylor_cubic_best){reference-type=“ref” reference=“lem:taylor_cubic_best”}, we have \[|f(\mathbf{x}_{km+t+1})-T_{\mathbf{x}_{km+t}}(\mathbf{p})|\le \frac{L_2}{6}\left(\frac{\epsilon}{n}\right)^{\frac{3}{2}}.\] Due to the \(L_2\)-Lipschitzness of Hessian, after \(t\le m\) steps, we have \[\begin{align} \|\hat{H}_{km+t}-\widetilde{H}_{km}\|&\le L_2\|\mathbf{x}_{km+t}-\mathbf{x}_{km}\|\le L_2\sum_{i=km}^{km+t-1}\|\mathbf{x}_{i+1}-\mathbf{x}_{i}\|\le L_2\cdot rm. \end{align}\] When \(\|\mathbf{x}_{t+1}-\mathbf{x}_t\|\le r\), the error, denoted \(\Delta_{\text{err}}\), can be estimated as \[\begin{align} \Delta_{\text{err}}:=|T_{\mathbf{x}_{km+t}}(\mathbf{p})-m_{km+t}(\mathbf{p})|&=\frac{1}{2}(\mathbf{x}-\mathbf{x}_{km+t})^\top(\hat{H}_{km+t}-\widetilde{H}_{km})(\mathbf{x}-\mathbf{x}_{km+t})\notag\\ &\le\frac{1}{2}r^2 L_2\cdot rm =\frac{L_2}{2}r^3m =O(r^3\cdot m). \end{align}\] From Lemma [[lem:tr_quadratic]](#lem:tr_quadratic){reference-type=“ref” reference=“lem:tr_quadratic”}, we have \[\begin{align} |T_{\mathbf{x}_{km+t}}(\mathbf{p})-f(\mathbf{x}_{km+t})|&\ge \frac{r}{2}\|\nabla f(\mathbf{x}_{km+t})+\hat{H}_{km+t}\cdot \mathbf{p}\|=O(r\epsilon). \end{align}\] Choosing \(c\) small enough for \(r=c\sqrt{\epsilon/n}\), we obtain \(|\Delta_{km+t+1}-\Delta_{km+t}|\ge2\Delta_{\text{err}}\), thus we can get a descent at least \(\Theta(\epsilon^{1.5}/\sqrt{n})\). When \(\|\mathbf{x}_{t+1}-\mathbf{x}_t\|<r\), we have \[\begin{align} \nabla f(\mathbf{x}_{km+t+1})&=\nabla f(\mathbf{x}_{km+t})+\widetilde{H}_{km}(\mathbf{x}_{km+t+1}-\mathbf{x}_{km+t})+(\nabla^2f(\mathbf{x}_{km+t})-\widetilde{H}_{km})(\mathbf{x}_{km+t+1}-\mathbf{x}_{km+t})\notag\\ &=(\nabla^2f(\mathbf{x}_{km+t})-\widetilde{H}_{km})(\mathbf{x}_{km+t+1}-\mathbf{x}_{km+t}). \end{align}\] As a result, we can obtain \[\begin{align} \|\nabla f(\mathbf{x}_{km+t+1})\|&\le\|\nabla^2f(\mathbf{x}_{km+t})-\widetilde{H}_{km}\|\cdot\|\mathbf{x}_{km+t+1}-\mathbf{x}_{km+t}\|\le rd\cdot r\le\epsilon. \end{align}\] In Algorithm [[algo:LazyTrustRegion]](#algo:LazyTrustRegion){reference-type=“ref” reference=“algo:LazyTrustRegion”}, the total times that we update the gradient is \(T_{\text{iter}}=O(\sqrt{n}/\epsilon^{1.5})\). Therefore, the total query complexity is \[\begin{align} n\cdot \left(T_{\text{iter}}+\left(T_{\text{iter}}\cdot\frac{1}{m}+1\right)n\right)=O\left(\frac{n^{1.5}}{\epsilon^{1.5}}+n^2\right). \end{align}\] ◻