# Deep Neural Networks Training by Stochastic Quasi-Newton Trust-Region Methods
## Appendix A Solvers for the TR Subproblem
### Computing with an L-SR1 Matrix
For \(\sigma=-\lambda_{min}\), we discuss the two following cases. If \(\lim_{\sigma\rightarrow-\lambda_{min}^{+}}\phi(\sigma)<0\), then \(\lim_{\sigma\rightarrow-\lambda_{min}^{+}}\|p(\sigma)\|>\delta\). The OBS algorithm uses [PERSON]'s method, to find \(\sigma^{*}\in(-\lambda_{min},\infty)\) as the root of \(\phi(\sigma)=0\), so that the global solution \(p^{*}\) lies on the boundary of the trust region. By using (10) to compute \(p^{*}=p(\sigma^{*})\), the pair \((\sigma^{*},p^{*})\) satisfies both the conditions in (7). If \(\lim_{\sigma\rightarrow-\lambda_{min}^{+}}\phi(\sigma)\geq 0\), then \(\lim_{\sigma\rightarrow-\lambda_{min}^{+}}\|p(\sigma)\|\geq\delta\). For \(\sigma>-\lambda_{min}\), we obtain \(\phi(\sigma)\geq 0\), but the solution \(\sigma^{*}=-\lambda_{min}\) as the only root of \(\phi(\sigma)=0\) is a positive number, which cannot satisfy the second optimal condition when \(\phi(\sigma)\) is strictly positive. Hence, we should consider the cases of equality and inequality separately:  
_Equality._ Let \(\lim_{\sigma\rightarrow-\lambda_{min}^{+}}\phi(\sigma)=0\). As matrix \(B+\sigma I\) at \(\sigma^{*}=-\lambda_{min}\) is not invertible, the global solution \(p^{*}\) for the first optimality condition in (7) is computed using (10) by  
\[p^{*}= \begin{cases}-\Psi R^{-1}U(\Lambda_{1}+\sigma^{*}I)^{\ddagger}g_{ \parallel}-\frac{1}{\gamma+\sigma^{*}}P_{\perp}P_{\perp}^{\ddagger}g,&\sigma^ {*}\
eq-\gamma,\\ -\Psi R^{-1}U(\Lambda_{1}+\sigma^{*}I)^{\ddagger}g_{\parallel},&\sigma^{*}=- \gamma,\end{cases}  \tag{11}\]  
where \(g_{\perp}=P_{\perp}^{\ddagger}g=0\) and, thus, \(\|g_{\perp}\|=0\) if \(\sigma^{*}=-\lambda_{min}=-\gamma\). For \(i=1,\ldots,r\), we obtain \((g_{\parallel})_{i}=(P_{\parallel}^{\ddagger}g)_{i}=0\) if \(\sigma^{*}=-\lambda_{min}=-\lambda_{1}\). We note that both optimality conditions in (7) hold for the computed \((\sigma^{*},p^{*})\). _Inequality._ Let \(\lim_{\sigma\rightarrow-\lambda_{min}^{+}}\phi(\sigma)>0\); then, \(\lim_{\sigma\rightarrow-\lambda_{min}^{+}}\|p(\sigma)\|<\delta\). As mentioned above, \(\sigma=-\lambda_{min}>0\) cannot satisfy the second optimality condition. In this case, a so-called _hard case_, we attempt to find a solution that lies on the boundary. For \(\sigma^{*}=-\lambda_{min}\), this optimal solution is provided by  
\[p^{*}=\hat{p}^{*}+z^{*}, \tag{12}\]  
where \(\hat{p}^{*}=-(B+\sigma^{*}I)^{\ddagger}g\) is computed by (11) and \(z^{*}=\alpha u_{min}\). Vector \(u_{min}\) is a unit eigenvector in the subspace associated with \(\lambda_{min}\), and \(\alpha\) is obtained so that \(\|p^{*}\|=\delta\), i.e.,  
\[\alpha=\sqrt{\delta^{2}-\|\hat{p}^{*}\|^{2}}. \tag{13}\]The computation of \(u_{min}\) depends on \(\lambda_{min}=\min\{\lambda_{1},\gamma\}\). If \(\lambda_{min}=\lambda_{1}\), then the first column of \(P\) is a leftmost eigenvector of \(B\) and, thus, \(u_{min}\) is set to the first column of \(P_{\parallel}\). On the other hand, if \(\lambda_{min}=\gamma\), then any vector in the column space of \(P_{\perp}\) will be an eigenvector of \(B\) corresponding to \(\lambda_{min}\). However, we avoid forming matrix \(P_{\perp}\) to compute \(P_{\perp}P_{\perp}^{T}g\) in (A11) if \(\lambda_{min}=\lambda_{1}\). By definition (A1), we have that  
\[\text{Range}(P_{\perp})=\text{Range}(P_{\parallel})^{\perp},\qquad\text{Range} (P_{\parallel})=\text{Ker}(I-P_{\parallel}P_{\parallel}^{T}).\]  
To find a vector in the column space of \(P_{\perp}\), we use \(I-P_{\parallel}P_{\parallel}^{T}\) as a projection matrix mapping onto the column space of \(P_{\perp}\). For simplicity, we can map one canonical basis vector at a time onto the column space of \(P_{\perp}\) until a nonzero vector is obtained.