## 2 Related Work
### Per-Dimension First-Order Adaptive Methods  
In mini-batch SGD, a single global learning rate is set for all dimensions of the parameters, which may not be optimal when training data are sparse and different coordinates vary significantly. A per-dimension learning rate that can compensate for these differences is often advantageous. Momentum [24; 25] is one method of speeding up training per dimension. The main idea is to accelerate progress along dimensions in which gradients are in the same direction and to slow progress elsewhere. This is done by keeping track of past parameters with an exponential decay, \(v_{t}=\rho v_{t-1}+\gamma\tilde{g}_{t},w_{t+1}=w_{t}-v_{t}\), where \(\rho\) is an undetermined parameter to control the decay of previous updated parameters. This gives an intuitive improvement over SGD when the cost surface is a long narrow valley. Adagrad [13; 26] adjusts the learning rate according to the accumulated gradients and has shown significant improvement on large-scale tasks in a distributed environment [27]. This method only uses information of gradients with the following update rule: \(w_{t+1}=w_{t}-\frac{\gamma}{\sqrt{\sum_{t=1}^{T}\delta_{t}^{2}}}\cdot\delta_{t}\). Here the denominator computes the \(L_{2}\) norm of all previous gradients per-dimension. Since the learning rate for each dimension inversely grows with the gradient magnitudes, the large gradients have a small learning rate and vice versa. This has the nice property, as in second-order methods, that the progress along each dimension evens out over time. However, Adagrad is sensitive to initial model parameters. When some dimensions of gradient are too large, or as gradients accumulate, the learning rate will quickly tend to zero before achieving a good result. Subsequently, several adaptive methods are proposed to overcome the drawback. RMSprop [14; 28] is a modification of Adagrad, using the root-mean-square (RMS) to replace the denominator in Adagrad, with the following update rule:  
\[\mathbb{E}[g^{2}]_{t}=\rho\mathbb{E}[g^{2}]_{t-1}+(1-\rho)\tilde{g}_{t}^{2},w_ {t+1}=w_{t}-\frac{\gamma}{\sqrt{\mathbb{E}[g^{2}]_{t}+\varepsilon}}\tilde{g} _{t}.\]  
This can mitigate the fast decay of learning rate in Adagrad and damp oscillation. The parameter \(\rho\) is used to control the decaying speed and \(\varepsilon\) is a positive small constant to keep the denominator meaningful. Adadelta [29; 30] is another improvement of Adagrad from two aspects. On one hand, Adadelta replaces the denominator in Adagrad by the average of exponential decay of history gradients over a window with some fixed size. On the other hand, Adadelta uses the Hessian approximation to correct units of updates. Adadelta uses the following update rule:  
\[\mathbb{E}[\tilde{g}^{2}]_{t}=\rho\mathbb{E}[\tilde{g}^{2}]_{t-1}+(1-\rho) \tilde{g}_{t}^{2},\ \mathbb{E}[\Delta w^{2}]_{t}=\rho\mathbb{E}[\Delta w^{2}]_{t-1}+(1-\rho) \Delta w_{t}^{2},\]  
\[w_{t+1}=w_{t}-\frac{\sqrt{\mathbb{E}[\Delta w^{2}]_{t}}}{\sqrt{\mathbb{E}[ \tilde{g}^{2}]_{t}+\varepsilon}}\cdot\tilde{g}_{t}.\]  
The advantage is no requirement of manually setting the global learning rate. At the beginning and middle phases, Adadelta achieves a good accelerating effect. However, at the late phase, it may oscillate at local minima. Adam [15; 31] can be viewed as a combination of Momentum and RMSprop, with additional bias correction. Adam uses the following update rule:  
\[m_{t}=\rho_{1}m_{t-1}+(1-\rho_{1})\tilde{g}_{t},v_{t}=\rho_{2}v_ {t-1}+(1-\rho_{2})\tilde{g}_{t}^{2},\] \[m_{t}\leftarrow\frac{m_{t}}{1-\rho_{1}^{t}},v_{t}\leftarrow\frac {v_{t}}{1-\rho_{2}^{t}},w_{t+1}=w_{t}-\gamma\frac{m_{t}}{\sqrt{v_{t}}+\varepsilon}.\]  
Here \(m_{t},v_{t}\) are factors of momentum and root-mean-square, and \(\frac{m_{t}}{1-\rho_{1}^{t}},\frac{v_{t}}{1-\rho_{2}^{t}}\) are corresponding bias corrections.