## 2 Background
### Second-Order Quasi-Newton Methods
#### 2.2.2 [PERSON]'s Accelerated Quasi-Newton Method  
The [PERSON]'s Accelerated Quasi-Newton (NAQ) [24] method introduces [PERSON]'s acceleration to the BFGS quasi-Newton method by approximating the quadratic model of the objective function at \(\mathbf{w}_{k}+\mu_{k}\mathbf{v}_{k}\) and by incorporating [PERSON]'s accelerated gradient \(\
abla E(\mathbf{w}_{k}+\mu_{k}\mathbf{v}_{k})\) in its Hessian update. The update vector of NAQ can be written as:  
\[\mathbf{v}_{k+1}=\mu_{k}\mathbf{v}_{k}+\alpha_{k}\mathbf{g}_{k}, \tag{8}\]  
where \(\mathbf{g}_{k}=-\mathbf{H}_{k}^{\text{NAQ}}\
abla E(\mathbf{w}_{k}+\mu_{k} \mathbf{v}_{k})\) is the search direction and the Hessian update equation is given as  
\[\mathbf{H}_{k+1}^{\text{NAQ}}=\left(\mathbf{I}-\frac{\mathbf{p}_{k}\mathbf{ q}_{k}^{\text{T}}}{\mathbf{q}_{k}^{\text{T}}\mathbf{p}_{k}}\right)\mathbf{H}_{k}^{ \text{NAQ}}\left(\mathbf{I}-\frac{\mathbf{q}_{k}\mathbf{p}_{k}^{\text{T}}}{ \mathbf{q}_{k}^{\text{T}}\mathbf{p}_{k}}\right)+\frac{\mathbf{p}_{k}\mathbf{ p}_{k}^{\text{T}}}{\mathbf{q}_{k}^{\text{T}}\mathbf{p}_{k}}, \tag{9}\]  
where  
\[\mathbf{p}_{k}=\mathbf{w}_{k+1}-(\mathbf{w}_{k}+\mu_{k}\mathbf{v}_{k})\;\;\text {and}\;\;\mathbf{q}_{k}=\
abla E(\mathbf{w}_{k+1})-\
abla E(\mathbf{w}_{k}+ \mu_{k}\mathbf{v}_{k}). \tag{10}\]  
(9) is derived from the secant condition \(\mathbf{q}_{k}=(\mathbf{H}_{k+1}^{\text{NAQ}})^{-1}\mathbf{p}_{k}\) and the rank-2 updating formula [24]. It is proven that the Hessian matrix \(\mathbf{H}_{k+1}^{\text{NAQ}}\) updated by (9) is a positive definite symmetric matrix, given \(\mathbf{H}_{k}^{\text{NAQ}}\) is initialized to identity matrix [24]. It is shown in [24] that NAQ has similar convergence properties to that of BFGS.  
The algorithms of BFGS and NAQ are as shown in Algorithm 3 and Algorithm 4, respectively. Note that the gradient is computed twice in one iteration. This increases the computational cost compared to the BFGS quasi-Newton method. However, due to acceleration by the momentum and Nesterov's gradient term, NAQ is faster in convergence compared to BFGS. Often, as the scale of the neural network model increases, the \(O(d^{2})\) cost of storing and updating the Hessian matrices \(\mathbf{H}_{k}^{\text{BFGS}}\) and \(\mathbf{H}_{k}^{\text{NAQ}}\) become expensive. Hence, limited memory variants LBFGS and LNAQ were proposed, and the respective Hessian matrices were updated using only the last \(m_{L}\) curvature information pairs \(\{\mathbf{p}_{i},\mathbf{q}_{i}\}_{i=k-1}^{k-m_{L}-1}\), where \(m_{L}\) is the limited memory size and is chosen such that \(m_{L}\ll b\).  
```
0:\(\varepsilon\) and \(k_{max}\)
0:\(\mathbf{w}_{k}\in\mathbb{R}^{d}\) and \(\mathbf{H}_{k}=\mathbf{I}\).
1:\(k\gets 1\)
2:Calculate \(\
abla E(\mathbf{w}_{k})\)
3:while\(||E(\mathbf{w}_{k})||>\varepsilon\) and \(k<k_{max}\)do
4:\(\mathbf{g}_{k}\leftarrow-\mathbf{H}_{k}^{\text{BRGS}}\
abla E(\mathbf{w}_{k})\)
5: Determine \(\alpha_{k}\) by line search
6:\(\mathbf{v}_{k+1}\leftarrow\alpha_{k}\mathbf{g}_{k}\)
7:\(\mathbf{w}_{k+1}\leftarrow\mathbf{w}_{k}+\mathbf{v}_{k+1}\)
8: Calculate \(\
abla E(\mathbf{w}_{k+1})\)
9: Update \(\mathbf{H}_{k+1}^{\text{BRGS}}\) using (6)
10:\(k\gets k+1\)
11:endwhile
```  
**Algorithm 3** BFGS Method  
```
0:\(0<\mu_{k}<1\), \(\varepsilon\) and \(k_{max}\)
0:\(\mathbf{w}_{k}\in\mathbb{R}^{d}\), \(\mathbf{H}_{k}=\mathbf{I}\) and \(\mathbf{v}_{k}=0\).
1:\(k\gets 1\)
2:while\(||E(\mathbf{w}_{k})||>\varepsilon\) and \(k<k_{max}\)do
3: Calculate \(\
abla E(\mathbf{w}_{k}+\mu_{k}\mathbf{v}_{k})\)
4:\(\mathbf{g}_{k}\leftarrow-\mathbf{H}_{k}^{\text{NAQ}}\
abla E(\mathbf{w}_{k}+ \mu_{k}\mathbf{v}_{k})\)
5: Determine \(\alpha_{k}\) by line search
6:\(\mathbf{v}_{k+1}\leftarrow\mu_{k}\mathbf{v}_{k}+\alpha_{k}\mathbf{g}_{k}\)
7:\(\mathbf{w}_{k+1}\leftarrow\mathbf{w}_{k}+\mathbf{v}_{k+1}\)
8: Calculate \(\
abla E(\mathbf{w}_{k+1})\)
9: Update \(\mathbf{H}_{k}^{\text{NAQ}}\) using (9)
10:\(k\gets k+1\)
11:endwhile
```  
**Algorithm 4** NAQ Method