# Deep Neural Networks Training by Stochastic Quasi-Newton Trust-Region Methods
## 2 Materials and Methods
### Stochastic Variants of L-BFGS-TR and L-SR1-TR
```
1:Inputs:\(w_{0}\in\mathbb{R}^{n}\), \(os\), \(\mathsf{epoch}_{max}\), \(l\), \(\gamma_{0}>0\), \(c\), \(S_{0}=\gamma_{0}=[\cdot]\), \(0<\tau\), \(\tau_{1}<1\)
2:for\(k=0,1,\ldots\)do
3: Take a random and uniform multi-batch \(I_{k}\) of size \(bs\) and compute \(f_{k}^{h}\), \(g_{k}^{h}\) by (22)
4:if\(\mathsf{epoch}>\mathsf{epoch}_{max}\)then
5: Stop training
6:endif
7: Compute \(p_{k}\) using Algorithm 1
8: Compute \(w_{t}=w_{k}+p_{k}\) and \(f_{t}^{h}\), \(g_{t}^{h}\) by (22)
9: Compute \((s_{k},y_{k})=(w_{t}-w_{k},g_{t}^{h}-g_{k}^{h})\) and \(\rho_{k}=\frac{f_{t}^{h}-f_{k}^{h}}{Q(p_{k})}\)
10:if\(\rho_{k}\geq\tau_{1}\)then
11:\(w_{k+1}=w_{t}\)
12:else
13:\(w_{k+1}=w_{k}\)
14:endif
15: Update \(\delta_{k}\) by Algorithm 1
16:if\(s_{k}^{*}y_{k}>\tau|s_{k}|^{2}\)then
17: Update storage matrices \(S_{k+1}\) and \(Y_{k+1}\) by \(l\) recent \(\{s_{j},y_{j}\}_{j=k-l+1}^{k}\)
18: Compute the smallest eigenvalue \(\tilde{\lambda}\) of (17) for updating \(B_{0}=\tau_{k}I\)
19:if\(\tilde{\lambda}>0\)then
20:\(\tau_{k+1}=\max\{1,c\tilde{\lambda}\}\in(0,\tilde{\lambda})\)
21:else
22: Compute \(\gamma_{k}^{h}\) by (14) and set \(\tau_{k+1}=\max\{1,\gamma_{k}^{h}\}\)
23:endif
24: Update \(\mathbf{\bar{v}}_{k+1}\), \(M_{k+1}^{-1}\) by (11)
25:else
26: Set \(\tau_{k+1}=\tau_{k}\), \(\mathbf{\bar{v}}_{k+1}=\mathbf{\bar{v}}_{k}\) and \(M_{k+1}^{-1}=M_{k}^{-1}\)
27:endif
28:endfor
```  
**Algorithm 3** sL-SR1-TR  
```
1:Inputs:\(w_{0}\in\mathbb{R}^{n}\), \(os\), \(\mathsf{epoch}_{max}\), \(l\), \(\gamma_{0}>0\), \(c\), \(S_{0}=\gamma_{0}=[\cdot]\), \(0<\tau\), \(\tau_{1}<1\)
2:for\(k=0,1,\ldots\)do
3: Take a random and uniform multi-batch \(I_{k}\) of size \(bs\) and compute \(f_{k}^{h}\), \(g_{k}^{h}\) by (22)
4:if\(\mathsf{epoch}>\mathsf{epoch}_{max}\)then
5: Stop training
6:endif
7: Compute \(p_{k}\) using Algorithm 2
8: Compute \(w_{t}=w_{k}+p_{k}\) and \(f_{t}^{h}\), \(g_{t}^{h}\) by (22)
9: Compute \((s_{k},y_{k})=(w_{t}-w_{k},g_{t}^{h}-g_{k}^{h})\) and \(\rho_{k}=\frac{f_{t}^{h}-f_{k}^{h}}{Q(p_{k})}\)
10:if\(\rho_{k}\geq\tau_{1}\)then
11:\(w_{k+1}=w_{t}\)
12:else
13:\(w_{k+1}=w_{k}\)
14:endif
15: Update \(\delta_{k}\) by Algorithm 1
16:if\(|s_{k}^{\top}(y_{k}-g_{k}y_{k})|\geq\tau|s_{k}|\|y_{k}-B_{k}|\)then
17: Update storage matrices \(S_{k+1}\) and \(Y_{k+1}\) by \(l\) recent \(\{s_{j},y_{j}\}_{j=k-l+1}^{k}\)
18: Compute the smallest eigenvalue \(\lambda\) of (17) for updating \(B_{0}=\tau_{k}I\)
19:if\(\tilde{\lambda}>0\)then
20:\(\tau_{k+1}=\max\{c,c_{1}\tilde{\lambda}\}\)
21:else
22:\(\tau_{k+1}=\min\{-c,c_{2}\tilde{\lambda}\}\)
23:endif
24: Update \(\mathbf{\bar{v}}_{k+1}\), \(M_{k+1}^{-1}\) by (21)
25:else
26: Set \(\tau_{k+1}=\gamma_{k},\mathbf{\bar{v}}_{k+1}=\mathbf{\bar{v}}_{k}\) and \(M_{k+1}^{-1}=M_{k}^{-1}\)
27:endif
28:endfor
```  
**Algorithm 4** sL-SR1-TR  
Subsampling Strategy and Batch Formation  
In a stochastic setting, as batches change from one iteration to the next, differences in stochastic gradients can cause the updating process to yield poor curvature estimates\((s_{k},y_{k})\). Therefore, updating \(B_{k}\), whether as (11) or (20), may lead to unstable Hessian approximations. To address this issue, the following two approaches have been proposed in the literature. As a primary remedy [19], one can use the same batch, \(J_{k}\), for computing curvature pairs, as follows:  
\[(s_{k},y_{k})=(p_{k},g_{t}^{J_{k}}-g_{k}^{J_{k}}), \tag{23}\]  
where \(g_{t}^{J_{k}}\triangleq\
abla F^{J_{k}}(w_{t})\). We refer to this strategy as full-batch sampling. In this strategy, the stochastic gradient at \(w_{t}\) is computed twice: once in (23) and again to compute the subsequent step, i.e., \(g_{t}^{J_{k+1}}\) if \(w_{t}\) is accepted; otherwise, \(g_{k}^{J_{k+1}}\) is computed. As a cheaper alternative, an overlap sampling strategy was proposed in [27], in which only a common (overlapping) part between every two consecutive batches \(J_{k}\) and \(J_{k+1}\) is employed for computing \(y_{k}\).