# 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 solving (2), where \(B_{k}\) is a compact L-SR1 matrix (20), the efficient Algorithm 1, called the Orthonormal Basis L-SR1 (OBS), was proposed in [38]. Let (10) be the eigenvalue decomposition of (20), where \(\Lambda=\text{diag}(\lambda_{1},\ldots,\lambda_{n})=\text{diag}(\hat{\lambda}_ {1}+\gamma_{k},\ldots,\hat{\lambda}_{k}+\gamma_{k},\gamma_{k},\ldots,\gamma_{k })\in\mathbb{R}^{n\times n}\) with \(\Lambda_{1}\in\mathbb{R}^{l\times l}\) and \(\Lambda_{2}\in\mathbb{R}^{(n-l)\times(n-l)}\) when \(k>l\). We note that \(\Lambda_{1}\in\mathbb{R}^{\times k}\) and \(\Lambda_{2}\in\mathbb{R}^{(n-k)\times(n-k)}\) when \(k\leq l\). We also assume the eigenvalues in \(\Lambda_{1}\) are ordered in increasing values. Note that \(\Lambda_{1}\) includes, at most, \(l\) elements with limited memory parameter \(l\). The OBS method exploits the Sherman-Morrison-Woodbury formula in different cases for L-SR1 \(B_{k}\); by dropping subscript \(k\) in (20), these cases are:  
\(B\) _is positive-definite_  
In this case, the global solution of (2) is (11) or (13). \(B\) _is positive semi-definite (singular)_  
As \(\gamma\
eq 0\) and \(B\) is positive semi-definite with all non-negative eigenvalues, then \(\lambda_{min}=\text{min}\{\lambda_{1},\gamma\}=\lambda_{1}=0\). Let \(r\) be the multiplicity of \(\lambda_{min}\); therefore,  
\[0=\lambda_{1}=\lambda_{2}=\cdots=\lambda_{r}<\lambda_{r+1}\leq\lambda_{r+2} \leq\cdots\leq\lambda_{k}.\]  
For \(\sigma>-\lambda_{min}=0\), the matrix \((\Lambda+\sigma I)\) in (10) is invertible and, thus, \(\|p(\sigma)\|\) in (10) is well defined. For \(\sigma=-\lambda_{min}=0\), we consider the two following sub-cases to have a well-defined expression in (10); we will discuss in the limit setting at \(-\lambda_{min}^{+}\). If \(\lim_{\sigma\to 0^{+}}\phi(\sigma)<0\), then \(\lim_{\sigma\to 0^{+}}\|p(\sigma)\|>\delta\). Here, the OBS algorithm uses [PERSON]'s method to find \(\sigma^{*}\in(0,\infty)\), so that the global solution \(p^{*}\) lies on the boundary of the trust region, i.e., \(\phi(\sigma^{*})=0\). This solution \(p^{*}=p(\sigma^{*})\) is computed using (11), by which, the global pair solution \((\sigma^{*},p^{*})\) satisfies the first and second optimal conditions in (7). If \(\lim_{\sigma\to 0^{+}}\phi(\sigma)\geq 0\), then \(\lim_{\sigma\to 0^{+}}\|p(\sigma)\|\leq\delta\). It can be proved that \(\phi(\sigma)\) is strictly increasing for \(\sigma>0\) (see Lemma 7.3.1 in [34]). This makes \(\phi(\sigma)\geq 0\) for \(\sigma>0\), as it is non-negative at \(0^{+}\) and, thus, \(\phi(\sigma)\) can only have a root \(\sigma^{*}=0\) in \(\sigma\geq 0\). Here, we should note that even if \(\phi(\sigma)>0\), the solution \(\sigma^{*}=0\) makes the second optimality condition in (7) hold. As matrix \(B+\sigma I\)at \(\sigma^{*}=0\) is not invertible, the global solution \(p^{*}\) for the first optimality condition in (7) is computed by  
\[ \begin{split} p^{*}&=p(\sigma^{*})=-(B+\sigma^{*}I)^{ \ddagger}g=-P(\Lambda+\sigma^{*}I)^{\ddagger}P^{\ddagger}g\\ &=-P_{\parallel}(\Lambda_{1}+\sigma^{*}I)^{\ddagger}P_{\parallel }^{\ddagger}g-\frac{1}{\gamma+\sigma^{*}}P_{\perp}P_{\perp}^{\ddagger}g\\ &=-\Psi R^{-1}U(\Lambda_{1}+\sigma^{*}I)^{\ddagger}g_{\parallel }-\frac{1}{\gamma+\sigma^{*}}P_{\perp}P_{\perp}^{\ddagger}g,\end{split}  \tag{10}\]  
where \((g_{\parallel})_{i}=(P_{\parallel}^{\ddagger}g)_{i}=0\) for \(i=1,\ldots,r\) if \(\sigma^{*}=-\lambda_{min}=-\lambda_{1}=0\), and  
\[P_{\perp}P_{\perp}^{\ddagger}g=(I-P_{\parallel}P_{\parallel}^{\ddagger})g=( I-\Psi R^{-1}R^{-T}\Psi^{T})g.\]  
Therefore, both optimality conditions in (7) hold for the pair solution \((\sigma^{*},p^{*})\). _B is indefinite_  
Let \(r\) be the algebraic multiplicity of the leftmost eigenvalue \(\lambda_{min}\). As \(B\) is indefinite and \(\gamma\
eq 0\), we obtain \(\lambda_{min}=\min\{\lambda_{1},\gamma\}<0\). Evidently, for \(\sigma>-\lambda_{min}\), the matrix \((\Lambda+\sigma I)\) in (11) is invertible and, thus, \(\|p(\sigma)\|\) in (10) is well defined.