# Deep Neural Networks Training by Stochastic Quasi-Newton Trust-Region Methods
## 2 Materials and Methods
### The L-BFGS-TR Method  
BFGS is the most popular QN update in the Broyden class; that is, it provides a Hessian approximation \(B_{k}\), for which (4) holds. It has the following general form:  
\[B_{k+1}=B_{k}-\frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}}+\frac{y_{k} y_{k}^{T}}{y_{k}^{T}s_{k}},\quad k=0,1,\ldots, \tag{8}\]  
which is a positive-definite matrix, i.e., \(B_{k+1}\succ 0\) if \(B_{0}\succ 0\) and the _curvature condition_ holds, i.e., \(s_{k}^{T}y_{k}>0\). The difference between the symmetric approximations \(B_{k}\) and \(B_{k+1}\) is a rank-two matrix. In this work, we bypass updating \(B_{k}\) if the following curvature condition is not satisfied for \(\tau=10^{-2}\):  
\[s_{k}^{T}y_{k}>\tau\|s_{k}\|^{2}. \tag{9}\]  
For large-scale optimization problems, using the limited-memory BFGS (L-BFGS) would be more efficient. In practice, only a collection of the most recent pairs \(\{s_{j},y_{j}\}\) is stored in memory: for example, \(l\) pairs, where \(l\ll n\) (usually \(l<100\)). In fact, for \(k\geq l\), the \(l\) recent computed pairs are stored in the following matrices \(S_{k}\) and \(\gamma_{k}\):  
\[S_{k}\triangleq\big{[}s_{k-l}\quad s_{k-(l-1)}\quad\ldots\quad s_{k-1}\big{]},\quad\gamma_{k}\triangleq\big{[}y_{k-l}\quad y_{k-(l-1)}\quad\ldots\quad y_{ k-1}\big{]}. \tag{10}\]  
Using (10), the L-BFGS 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{11}\]  
where \(B_{0}\succ 0\) and  
\[\Psi_{k}=\big{[}B_{0}S_{k}\quad Y_{k}\big{]},\qquad M_{k}= \begin{bmatrix}-S_{ k}^{T}B_{0}S_{k}&-L_{k}\\ -L_{k}^{T}&D_{k}\end{bmatrix} ^{-1}. \tag{12}\]  
We note that \(\Psi_{k}\) and \(M_{k}\) have at most \(2l\) columns. In (12), matrices \(L_{k}\), \(U_{k}\), and \(D_{k}\) are, respectively, the strictly lower triangular part, the strictly upper triangular part, and the diagonal part of the following matrix splitting:  
\[S_{k}^{T}Y_{k}=L_{k}+D_{k}+U_{k}. \tag{13}\]  
Let \(B_{0}=\gamma_{k}I\). A heuristic and conventional method of choosing \(\gamma_{k}\) is  
\[\gamma_{k}=\frac{y_{k-1}^{T}y_{k-1}}{y_{k-1}^{T}s_{k-1}}\triangleq\gamma_{k}^ {h}. \tag{14}\]  
The quotient of (14) is an approximation to an eigenvalue of \(\
abla^{2}F(w_{k})\) and appears to be the most successful choice in practice [10]. Evidently, the selection of \(\gamma_{k}\) is important in generating Hessian approximations \(B_{k}\). In DL optimization, the positive-definite LBFGS matrix \(B_{k}\) has the difficult task of approximating the possibly indefinite true Hessian. According to [29; 30], an extra condition can be imposed on \(\gamma_{k}\), to avoid false negative curvature information, i.e., to avoid \(p_{k}^{T}B_{k}p_{k}<0\) whenever \(p_{k}^{T}\
abla^{2}(w_{k})p_{k}>0\). Let, for simplicity, the objective function of (1) be a quadratic function:  
\[F(w)=\frac{1}{2}w^{T}Hw+g^{T}w, \tag{15}\]  
where \(H=\
abla^{2}F(w)\), which results in \(\
abla F(w_{k+1})-\
abla F(w_{k})=H(w_{k+1}-w_{k})\) and, thus, \(y_{k}=Hs_{k}\) for all \(k\). Thus, we obtain \(S_{k}^{T}\gamma_{k}=S_{k}^{T}HS_{k}\). For the quadratic model, and using (11), we obtain  
\[S_{k}^{T}HS_{k}-\gamma_{k}S_{k}^{T}S_{k}=S_{k}^{T}\Psi_{k}M_{k}\Psi_{k}^{T}S_{k}. \tag{16}\]  
According to (16), if \(H\) is not positive-definite, then its negative curvature information can be captured by \(S_{k}^{T}\Psi_{k}M_{k}\Psi_{k}^{T}S_{k}\) as \(\gamma_{k}>0\). However, false curvature information can be produced when the \(\gamma_{k}\) value chosen is too large while \(H\) is positive-definite. To avoid this, \(\gamma_{k}\) is selected in \((0,\hat{A})\), where \(\hat{A}\) is the smallest eigenvalue of the following generalized eigenvalue problem:  
\[(L_{k}+D_{k}+L_{k}^{T})u=\lambda S_{k}^{T}S_{k}u, \tag{17}\]  
with \(L_{k}\) and \(D_{k}\) defined in (13). Therefore, if \(\hat{\lambda}\leq 0\), then \(\gamma_{k}\) is the maximum value of \(1\) and \(\gamma_{k}^{h}\) defined in (14).