# Deep Neural Networks Training by Stochastic Quasi-Newton Trust-Region Methods
## 2 Materials and Methods
### The L-SR1-TR Method  
Another popular QN update in the Broyden class is the SR1 formula, which generates good approximations to the true Hessian matrix, often better than the BFGS approximations [10]. The SR1 updating formula verifying the secant condition (4) is given by  
\[B_{k+1}=B_{k}+\frac{(y_{k}-B_{k}s_{k})(y_{k}-B_{k}s_{k})^{T}}{(y_{k}-B_{k}s_{ k})^{T}s_{k}},\quad k=0,1,\ldots. \tag{18}\]  
In this case, the difference between the symmetric approximations \(B_{k}\) and \(B_{k+1}\) is a rank-one matrix. To prevent the vanishing of the denominator in (18), a simple safeguard that performs well in practice is to simply skip the update if the denominator is small [10], i.e., \(B_{k+1}=B_{k}\). Therefore, the update (18) is applied only if  
\[|s^{T}(y_{k}-B_{k}s_{k})|\geq\tau\|s_{k}\|\|y_{k}-B_{k}s_{k}\|, \tag{19}\]  
where \(\tau\in(0,1)\) is small, say \(\tau=10^{-8}\). In (18), if \(B_{k}\) is positive-definite, \(B_{k+1}\) may not have the same property. Regardless of the sign of \(y_{k}^{T}s_{k}\) for each \(k\), the SR1 method generates a sequence of matrices that may be indefinite. We note that the value of the quadratic model in (2) evaluated at the descent direction \(p^{*}\) is always less if this direction is also a direction of negative curvature. Therefore, the ability to generate indefinite approximations can actually be regarded as one of the chief advantages of SR1 updates in non-convex settings, like in DL applications. In the limited-memory version of the SR1 (L-SR1) update, as in L-BFGS, only the \(l\) most recent curvature pairs are stored in matrices \(S_{k}\) and \(Y_{k}\) defined in (10). Using \(S_{k}\) and \(Y_{k}\), the L-SR1 matrix \(B_{k}\) can be represented in the following compact form:  
\[B_{k}=B_{0}+\Psi_{k}M_{k}\Psi_{k}^{T},\quad k=1,2,,\ldots, \tag{20}\]  
where \(B_{0}=\gamma_{k}I\) for some \(\gamma_{k}\
eq 0\) and  
\[\Psi_{k}=Y_{k}-B_{0}S_{k},\qquad M_{k}=(D_{k}+L_{k}+L_{k}^{T}-S_{k}^{T}B_{0}S_{ k})^{-1}. \tag{21}\]In (21), \(L_{k}\) and \(D_{k}\) are, respectively, the strictly lower triangular part and the diagonal part of \(S_{k}^{T}Y_{k}\). We note that \(\Psi_{k}\) and \(M_{k}\) in the L-SR1 update have, at most, \(l\) columns. In [29], it was proven that the trust region subproblem solution becomes closely parallel to the eigenvector corresponding to the most negative eigenvalue of the L-SR1 approximation \(B_{k}\). This shows the importance of \(B_{k}\) to be able to capture curvature information correctly. On the other hand, it was highlighted how the choice of \(B_{0}=\gamma_{k}I\) affects \(B_{k}\); in fact, not choosing \(\gamma_{k}\) judiciously in relation to \(\lambda\), the smallest eigenvalue of (17), can have adverse effects. Selecting \(\gamma_{k}>\lambda\) can result in false curvature information. Moreover, if \(\gamma_{k}\) is too close to \(\lambda\) from below, then \(B_{k}\) becomes ill-conditioned. If \(\gamma_{k}\) is too close to \(\lambda\) from above, then the smallest eigenvalue of \(B_{k}\) becomes negatively large arbitrarily. According to [29], the following lemma suggests selecting \(\gamma_{k}\) near but strictly less than \(\lambda\), to avoid asymptotically poor conditioning while improving the negative curvature approximation properties of \(B_{k}\). **Lemma 1**. : _For a given quadratic objective function (15), let \(\lambda\) denote the smallest eigenvalue of the generalized eigenvalue problem (17). Then, for all \(\gamma_{k}<\lambda\), the smallest eigenvalue of \(B_{k}\) is bounded above by the smallest eigenvalue of \(H\) in the span of \(S_{k}\), i.e.,_  
\[\lambda_{min}(B_{k})\leq\min_{S_{k}\
eq 0}\frac{v^{T}S_{k}^{T}HS_{k}\
u}{v^{T }S_{k}^{T}S_{k}\
u}.\]  
In this work, we set \(\gamma_{k}=\max\{10^{-6},0.5\lambda\}\) in the case where \(\lambda>0\); otherwise, the \(\gamma_{k}\) is set to \(\gamma_{k}=\min\{-10^{-6},1.5\lambda\}\).