# 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
Defining \(O_{k}=J_{k}\cap J_{k+1}\
eq\emptyset\) of size \(os\triangleq|O_{k}|\), the curvature pairs are computed as  
\[(s_{k},y_{k})=(p_{k},g_{t}^{O_{k}}-g_{k}^{O_{k}}), \tag{24}\]  
where \(g_{t}^{O_{k}}\triangleq\
abla F^{O_{k}}(w_{t})\). As \(O_{k}\), and thus \(J_{k}\), should be sizeable, this strategy is called multi-batch sampling. Both these approaches were originally considered for a stochastic algorithm using L-BFGS updates without and with line search methods, respectively. Progressive sampling approaches to use L-SR1 updates in a TR framework were instead considered, to train fully connected networks in [29; 39]. More precisely, in [29], the curvature pairs and the model goodness ratio are computed as  
\[(s_{k},y_{k})=(p_{k},g_{t}^{I_{k}}-g_{k}^{I_{k}}),\qquad\rho_{k}=\frac{f_{t}^{ I_{k}}-f_{k}^{I_{k}}}{Q_{k}(p_{k})}, \tag{25}\]  
such that \(J_{k}=J_{k}\cap J_{k+1}\). Progressive sampling strategies may avoid acquiring noisy gradients by increasing the batch size at each iteration [31], which may lead to increased costs per iteration. A recent study of a non-monotone trust-region method with adaptive batch sizes can be found in [40]. In this work, we use fixed-size sampling for both methods. We have examined the following two strategies to implement the considered sQN methods in a TR approach, in which the subsampled function and gradient evaluations are computed using a fixed-size batch per iteration. Let \(O_{k}=J_{k}\cap J_{k+1}\
eq\emptyset\); then, we can consider one of the following options:  
* \((s_{k},y_{k})=(p_{k},g_{t}^{I_{k}}-g_{k}^{J_{k}}),\qquad\rho_{k}=\frac{f_{t}^{ I_{k}}-f_{k}^{I_{k}}}{Q_{k}(p_{k})}\). * \((s_{k},y_{k})=(p_{k},g_{t}^{O_{k}}-g_{k}^{O_{k}}),\qquad\rho_{k}=\frac{f_{t}^{ O_{k}}-f_{k}^{O_{k}}}{Q_{k}(p_{k})}\). Clearly, in both options, every two successive batches have an overlapping set (\(O_{k}\)), which helps to avoid extra computations in the subsequent iteration. We have performed experiments with both sampling strategies and have found that the L-SR1 algorithm fails to converge when using the second option. As this fact deserves further investigation, we have only used the first sampling option in this paper. Let \(J_{k}=O_{k-1}\cup O_{k}\), where \(O_{k-1}\) and \(O_{k}\) are the overlapping samples of \(J_{k}\) with batches \(J_{k-1}\) and \(J_{k+1}\), respectively. Moreover, the fixed-size batches are drawn without replacement, to ensure the whole dataset is visited in one epoch. We assume that \(|O_{k-1}|=|O_{k}|=os\) and, thus, overlap ratio \(or\triangleq\frac{os}{bs}=\frac{1}{2}\) (half overlapping). It is easy to see that \(\bar{N}=\left\lfloor\frac{N}{os}\right\rfloor-1\) indicates the number of batches in one epoch, where \(\lfloor a\rfloor\) rounds \(a\) to the nearest integer less than or equal to \(a\). To create \(\bar{N}\) batches, we can consider the two following cases: \(rs\triangleq\text{mod}(N,os)=0\) and \(rs\triangleq\text{mod}(N,os)\
eq 0\), where the mod (modulo operation) of \(N\) and \(os\) returns the remainder after division of \(N\) and \(os\). In the first case, all \(\bar{N}\) batches are duplex, composed by two subsets, \(O_{k-1}\) and \(O_{k}\), as \(J_{k}=O_{k-1}\cup O_{k}\), while in the second case, the \(\bar{N}\)-th batch is a triple batch, defined as \(J_{k}=O_{k-1}\cup R_{k}\cup O_{k}\), where \(R_{k}\) is a subset of size \(rs\
eq 0\) and other \(\bar{N}-1\) batches are duplex. In the former case, the required quantities for computing \(y_{k}\) and \(\rho_{k}\) at iteration \(k\) are determined as  
\[f_{k}^{I_{k}}=or(f_{k}^{O_{k-1}}+f_{k}^{O_{k}})\]and  
\[g_{k}^{Ik}=or(g_{k}^{O_{k-1}}+g_{k}^{O_{k}}),\]  
where \(or=\frac{1}{2}\). In the latter case, the required quantities with respect to the last triple batch \(J_{k}=O_{k-1}\cup R_{k}\cup O_{k}\) are computed as  
\[f_{k}^{Ik}=or(f_{k}^{O_{k-1}}+f_{k}^{O_{k}})+(1-2 or)f_{k}^{R_{k}}\]  
and  
\[g_{k}^{Ik}=or(g_{k}^{O_{k-1}}+g_{k}^{O_{k}})+(1-2 or)g_{k}^{R_{k}},\]  
where \(or=\dfrac{os}{2 os+rs}\). In this work, we have considered batches corresponding to the first case.