## 3 Adacomp Method
### Idea 2: Approximate Unknown Terms  
To set learning rate according to Equation (5), two terms, expected gradient \(\
abla f(w_{t})\) and smooth constant \(L\), are unknown in practice. Note that in the training process, we only get access to information of stochastic gradient \(\bar{g}_{t}\), model parameters \(w_{t}\), and loss value \(f(w_{t})\). Most first-order adaptive learning methods exploit stochastic gradient and model parameters, which are usually high-dimensional vectors. Instead, we will use the stochastic gradient \(\bar{g}_{t}\) and loss value to reformulate Equation (5). In particular, based on Equation (4), we have  
\[\gamma_{t}=\frac{\langle\
abla f(w_{t}),\gamma_{t}\bar{g}_{t}\rangle}{L\gamma _{t}\|\bar{g}_{t}\|^{2}}\leq\frac{\frac{L\gamma_{t}^{2}}{2}\|\bar{g}_{t}\|^{2} +f(w_{t})-f(w_{t+1})}{L\gamma_{t}\|\bar{g}_{t}\|^{2}}. \tag{7}\]  
In the above inequality, parameters square norm of gradients \(\|\bar{g}_{t}\|^{2}\) and learning rate \(\gamma_{t}\) are known, and loss value of expected \(f(w_{t})\) at the current iteration can be approximated by empirical value \(F(w_{t},\bar{\varsigma})\); however, smooth constant \(L\) and the loss value \(f(w_{t+1})\) of the next iteration are unknown. Derived from the basic analysis [6], it is known that when \(L\gamma_{t}\leq 1\), SGD can converge to the stationary point. Therefore, we introduce a new parameter \(\theta:=L\gamma_{t}\in(0,1]\) and use \(f(w_{t-1})-f(w_{t})\) to approximate \(f(w_{t})-f(w_{t+1})\) based on the assumption that \(f(w)\) is smooth. Then, for any given learning rate \(\gamma\) subject to \(\theta\stackrel{{\triangle}}{{=}}L\gamma\in(0,1]\), we adjust the learning rate based on the following formula:  
\[\gamma\leftarrow\frac{\frac{\theta\gamma}{2}\|\bar{g}_{t}\|^{2}+\max\{f(w_{t-1 })-f(w_{t}),0\}}{\theta\|\bar{g}_{t}\|^{2}},\theta\in(0,1]. \tag{8}\]  
Equation (8) has straightforward interpretations. _First_, when \(\|\bar{g}_{t}\|^{2}\) dominates \(f(w_{t-1})-f(w_{t})\) in the numerator, we will use an exponential decaying learning rate strategy to prevent divergence. This includes the case that \(f(w_{t-1})-f(w_{t})\) tends to zero, i.e., the model converges to a stationary point. In such case, \(\gamma_{t}\) will decay to zero to stabilize the process. As shown in [46], in such case, any fixed large learning larger than a threshold will diverge the training. _Second_, when \(f(w_{t-1})-f(w_{t})\) is relatively large, which means that the current model point is located at the rapid descent surface of \(f(w)\), we can use a relatively large learning rate to accelerate the descent speed. This usually happens at the initial phase of the training procedure. _Third_, the parameter \(\theta\in(0,1]\) can control the tradeoff between \(\|\vec{g}_{t}\|^{2}\) and \(f(w_{t-1})-f(w_{t})\). Note that these two terms have different magnitudes, and \(\|\vec{g}_{t}\|^{2}\) is generally much larger than \(f(w_{t-1})-f(w_{t})\). In such case, Equation (8) with \(\theta=1\) reduces to a totally exponential decaying strategy, which may slow down the convergence. To address it, one can set an adaptive \(\theta\) according to \(f(w_{t-1})-f(w_{t})\). Although Equation (8) is meaningful, the remaining challenge is how to set the proper \(\theta\) according to the observed gradients \(\|\vec{g}_{t}\|^{2}\) and difference in loss function \(f(w_{t-1})-f(w_{t})\). To address this, we deal with \(\theta\|\vec{g}_{t}\|^{2}\) as a whole and reformulate the term \(\frac{\max\{f(w_{t-1})-f(w_{t}),\theta\}}{\|\vec{g}_{t}\|^{2}}\) as a pure function of \(f(w_{t-1})-f(w_{t})\). Here, we propose an effective adaptive schedule Ada-comp that only uses the information of loss values and satisfies the following requirements.