# A Bounded Scheduling Method for Adaptive Gradient Methods
## 2 Background
### Adaptive Gradient Methods  
The recently proposed adaptive gradient methods can provide an element-wise scaling term on learning rates without the need to tune the learning rate manually. These methods use historical information to estimate the curvature of the loss function and adopt different learning rates for each parameter, so the learning rate is a vector and each element for a parameter, which is different from the traditional learning rate methods. The representative adaptive gradient methods are Adagrad [9], RMSprop [15], Adam [16], AMSgrad [18], etc.  
Adagrad [9] is the first proposed adaptive gradient method. Its main idea is to adopt a smaller learning rate for the parameters corresponding to frequent features and a larger learning rate for the parameters corresponding to infrequent features. Therefore, Adagrad is very suitable for training sparse data, which can improve the robustness of SGD. The update of Adagrad can be shown as follows:\[w_{k}=w_{k-1}-\eta\frac{\
abla f(w_{k-1})}{\sqrt{v_{k}}+\epsilon}, \tag{3}\]  
where  
\[v_{k}=\Sigma_{j=0}^{k-1}\
abla f(w_{j})^{2}, \tag{4}\]  
\(\epsilon\) is a smoothing term that avoids division by zero, \(\eta\) is general learning rate.  
Adagrad uses the accumulation of the squared gradients and the squared gradients are positive, which will lead to a rapid decline in learning rate to infinite small and the standstill of loss function. RMSprop [15] was proposed to solve the problem of the rapid disappearance of the gradient for Adagrad. The update rule of RMSprop is the same as (3), but the updating of \(v_{k}\) adopts exponential decaying average of square gradients, which can be shown as follows:  
\[v_{k}=\beta v_{k-1}+(1-\beta)\
abla f(w_{k-1})^{2}, \tag{5}\]  
where \(\beta\in[0,1)\) is the hyper-parameter that controls the exponential decay rate of average. The use of the exponential moving averages of squared past gradients can prevent the rapid rise of \(v_{k}\) and the learning rate will not decline rapidly.  
[PERSON] [16] can also calculate adaptive learning rate for each parameter. As a complement to RMSprop, Adam preserves the exponential moving averages of squared past gradients, as well as the exponential moving averages of past gradients, which gives the gradient momentum. The update formula of Adam is shown as follows:  
\[w_{k}=w_{k-1}-\eta\cdot\frac{\sqrt{1-\beta_{2}^{k}}}{1-\beta_{1}^{k}}\cdot \frac{m_{k}}{\sqrt{v_{k}}+\epsilon}, \tag{6}\]  
where  
\[\begin{split} m_{k}=\beta_{1}m_{k-1}+(1-\beta_{1})\
abla f(w_{k-1 }),\\ v_{k}=\beta_{2}v_{k-1}+(1-\beta_{2})\
abla f(w_{k-1})^{2},\end{split} \tag{7}\]  
where \(\beta_{1}\), \(\beta_{2}\in[0,1)\) are hyper-parameters that control the exponential decay rate of moving average.  
[PERSON] et al. pinpoint that the use of exponential moving averages of squared past gradients may make Adam fail to converge to the optimal solution. As a result, AMSGrad was proposed [18]. Unlike Adam, AMSGrad uses the maximum of exponential moving averages of squared past gradients, the update rule of \(v_{k}\) is show as follows:  
\[\begin{split}\widehat{v}_{k}=\beta_{2}\widehat{v}_{k-1}+(1-\beta _{2})\
abla f(w_{k-1})^{2},\\ v_{k}=\max(\widehat{v}_{k},v_{k-1}).\end{split} \tag{8}\]  
The adaptive gradient methods has low generalization ability in training complex models and its performance is worse than the optimal learning rate tuned manually.