# Deep Neural Networks Training by Stochastic Quasi-Newton Trust-Region Methods
## 2 Materials and Methods  
We provide in this section an overview of quasi-Newton trust-region methods in the deterministic setting and introduce suitable stochastic variants.  
Trust-region (TR) methods [34] are powerful techniques for solving nonlinear unconstrained optimization problems that can incorporate second-order information, without re quiring it to be positive-definite. TR methods generate a sequence of iterates, \(w_{k}+p_{k}\), such that the search direction \(p_{k}\) is obtained by solving the following TR subproblem,  
\[p_{k}=\arg\min_{p\in\mathbb{R}^{n}}Q_{k}(p)\triangleq\frac{1}{2}p^{T}B_{k}p+g_{ k}^{T}p\quad\text{s.t.}\quad\left\|p\right\|_{2}\leq\delta_{k}, \tag{2}\]  
for some TR radius \(\delta_{k}>0\), where  
\[g_{k}\triangleq\
abla F(w_{k})=\frac{1}{N}\sum_{i=1}^{N}\
abla L_{i}(w_{k}) \tag{3}\]  
and \(B_{k}\) is a Hessian approximation. For quasi-Newton trust-region methods, the symmetric quasi-Newton (QN) matrices \(B_{k}\) in (2) are approximations to the Hessian matrix constructed using gradient information, and they satisfy the following secant equation:  
\[B_{k+1}s_{k}=y_{k}, \tag{4}\]  
where  
\[s_{k}=p_{k},\qquad y_{k}=g_{t}-g_{k}, \tag{5}\]  
in which \(g_{t}\) is the gradient evaluated at \(w_{t}=w_{k}+p_{k}\). The trial point is subject to the value of the ratio of actual to predicted reduction in the objective function of (1), that is:  
\[\rho_{k}=\frac{f_{k}-f_{t}}{Q_{k}(0)-Q_{k}(p_{k})}, \tag{6}\]  
where \(f_{t}\) and \(f_{k}\) are the objective function values at \(w_{t}\) and \(w_{k}\), respectively. Therefore, since the denominator in (6) is non-negative, if \(\rho_{k}\) is positive then \(w_{k+1}\triangleq w_{t}\); otherwise, \(w_{k+1}\triangleq w_{k}\). Based on the value of (6), the step may be accepted or rejected. Moreover, it is safe to expand \(\delta_{k}\in(\delta_{0},\delta_{max})\) with \(\delta_{0}\), \(\delta_{max}>0\) when there is very good agreement between the model and function. However, the current \(\delta_{k}\) is not altered if there is good agreement, or it is shrunk when there is weak agreement. Algorithm 1 describes the TR radius adjustment.  
```
1:Inputs: Current iteration \(k\), \(\delta_{k},\rho_{k},0<\tau_{2}<0.5<\tau_{3}<1\), \(0<\eta_{2}\leq 0.5\), \(0.5<\eta_{3}<1<\eta_{4}\)
2:if\(\rho_{k}>\tau_{3}\)then
3:if\(\left\|p_{k}\right\|\leq\eta_{3}\delta_{k}\)then
4:\(\delta_{k+1}=\delta_{k}\)
5:else
6:\(\delta_{k+1}=\eta_{4}\delta_{k}\)
7:endif
8:else if\(\tau_{2}\leq\rho_{k}\leq\tau_{3}\)then
9:\(\delta_{k+1}=\delta_{k}\)
10:else
11:\(\delta_{k+1}=\eta_{2}\delta_{k}\)
12:endif
```  
**Algorithm 1** Trust region radius adjustment  
A primary advantage of using TR methods is their ability to work with both positive-definite and indefinite Hessian approximations. Moreover, the progress of the learning process will not stop or slow down even in the presence of occasional step rejection, i.e., when \(w_{k+1}\triangleq w_{k}\).  
Using the Euclidean norm (2-norm) to define the subproblem (2) leads to characterizing the global solution of (2) by the optimality conditions given in the following theorem from [PERSON] (35) and [PERSON] and [PERSON] (36):  
**Theorem 1**.: _Let \(\delta_{k}\) be a given positive constant. A vector \(p_{k}\triangleq p^{*}\) is a global solution of the trust region problem (2) if and only if \(\left\|p^{*}\right\|_{2}\leq\delta_{k}\) and there exists a unique \(\sigma^{*}\geq 0\), such that \(B_{k}+\sigma^{*}I\) is positive semi-definite with_  
\[(B_{k}+\sigma^{*}I)p^{*}=-g_{k},\quad\sigma^{*}(\delta_{k}-\left\|p^{*} \right\|_{2})=0. \tag{7}\]  
_Moreover, if \(B_{k}+\sigma^{*}I\) is positive-definite, then the global minimizer is unique._  
According to [37; 38], the subproblem (2) or, equivalently, the optimality conditions (7) can be efficiently solved if the Hessian approximation \(B_{k}\) is chosen to be a QN matrix. In the following sections, we provide a comprehensive description of two methods in a TR framework with limited memory variants of two well-known QN Hessian approximations, i.e., L-BFGS and L-SR1.