## 3 Adacomp Method
### Idea 2: Approximate Unknown Terms
Note that \(\Pi_{21}+\Pi_{22}\approx\frac{1}{2}-\frac{\arctan(-\delta+1/\gamma)}{5.5\pi}\) when \(\gamma\) is small, which satisfies the requirement. * When \(\gamma\) is large, the decrement of \(\Pi_{21}+\Pi_{22}\) should be larger than the increment in \(\Pi_{1}\) given the same \(|\Delta_{t}|\). That is, we can fast decrease the large learning rate when the function loss is negative. Therefore, we set \(\beta\in(1/2,5]\) in \(\Pi_{21}\) to satisfy that \(\frac{\arctan(\gamma)}{\beta\pi}+\frac{\arctan(-\Delta_{t}+1/\gamma)}{5.5\pi}\) (in the case \(\Delta_{t}<0\)) is greater than \(\frac{\arctan(\Delta_{t}+1/\gamma)}{5\pi}\) (in the case \(\Delta_{t}>0\)). Furthermore, the inferior bound \(1/2\) of \(\beta\) is used to ensure \(\frac{\gamma}{2}+\gamma\mathbb{I}_{\Delta_{t}<-\epsilon}(\Pi_{21}+\Pi_{22})>0\) when \(\Delta_{t}<-\epsilon\), i.e., the meaningfulness of \(\gamma\). Remark. In \(\Pi_{1},\Pi_{22}\), the denominator \(5\pi,5.5\pi\) can be generalized as \(\alpha_{1},\alpha_{2}\), with \(\alpha_{1}<\alpha_{2}\), while keeping the difference between \(\Pi_{1}\) and \(\Pi_{22}\) is not significant. Meanwhile, \(1/2<\beta\leq 5\) is replaced by \(1/2<\beta\leq\alpha_{1}\). Note that any settings satisfying the above requirements can be used to substitute Equation (9). Here, \(5\pi\) and \(5.5\pi\) are just one satisfied setting and one can adjust the parameter \(\beta\) to control the tradeoff between \(\Pi_{1}\) and \(\Pi_{21}+\Pi_{22}\). In summary, Equation (9) penalizes the large learning rate and compensates the too small learning rate, and presents an overall decreasing trend. These satisfy all the requirements. Note that this adjusting strategy is complementary to \(\Delta_{t}\) and \(\gamma\); we named it Adacomp. Although Adacomp is robust to hyperparameters, it may fluctuate at a local minimum. The reason for this is that Adacomp will increase the learning rate when the loss function decreases near the local minima, and the increment potentially makes model parameters skip the local minima. Then, Adacomp in turn will penalize learning rate to decrease loss function. Thus, the alternately adaptive adjustment possibly makes model parameters fluctuate at a local minimum. To achieve both robustness and high-utility, one can view Adacomp as a pre-processing step to reduce the cost of tuning hyperparameters, and combine Adacomp with other methods to improve the final model utility. Algorithm 1 shows the pseudocode, which consists of two phases. Phase one uses Adacomp to fast-train the model by avoiding and carefully tuning the initial learning rate. Phase two uses other methods (e.g., SGD) to improve the model utility. More details are as follows. At the beginning (Input), one should define four parameters, including number of total iterations \(T\) with phase threshold \(T_{1}\), initial learning rate \(\gamma_{0}\), and one specific value \(\beta\) of Adacomp used to control the tradeoff between increment and decrement. In phase 1 (Lines 2-8), two variables, \(loss_{l},loss_{c}\), are used to track the loss difference \(\Delta_{t}\) in Equation (9), where \(loss_{l}=\frac{1}{b}\sum_{\xi\in\mathcal{B}_{t-1}}F(w_{t-1},\xi)\) is loss of last time and \(loss_{c}=\frac{1}{b}\sum_{\xi\in\mathcal{B}_{t}}F(w_{t},\xi)\) is loss of current time (Lines 3-5). Then \(\Delta_{t}\) is used to update learning rate based on Equation (9) (Line 6). The updated learning rate \(\gamma_{t}\) is used to update the model parameters \(w_{t}\) to \(w_{t+1}\) based on \(w_{t+1}=w_{t}-\gamma_{t}\xi_{t}\) (Line 7) until \(t\) reaches to \(T_{1}\). In phase 2, we set the average of the learning rate used in phase one, \(\gamma_{avg}\), as the new current initial learning rate (Line 9). Then, one can adopt a decaying scheduler, such as StepLR in mini-batch gradient descent update to stabilize the training process (Lines 11-13). The final model parameter is output when the stopping criterion is satisfied (Line 15).