## 1 Introduction
Nevertheless, one challenge of applying these theoretical results in practice comprises the unknown parameters \(f(w_{1})\), \(L\) and \(\sigma\), which are related to network architecture, network initialization, loss function, and data distribution. To avoid computing exact values that are network- and dataset-dependent, there are two common ways to set the learning rate in practice. One way is setting an initial level at the beginning and then adjusting it with a certain schedule [4], such as step, multi-step, exponential decaying, or cosine annealing [10]. However, setting the learning rate typically involves a tuning procedure in which the highest possible learning rate is chosen by hand [11; 12]. Besides, there are additional parameters in the schedule that also need to be tuned. To avoid the delicate and skillful parameter tuning, the other way is using adaptive learning rate methods, such as Adagrad [13], RMSprop [14], and Adam [15], in which only the initial learning rate needs to be predefined. However, as shown in our experiments and other studies [16; 17; 18], they are sensitive to the initial learning rate and each of them has its own effective intervals (refer to Figure 1). Usually, the setting of an initial learning rate is model- and dataset-dependent. This increases the cost of tuning the learning rate and the difficulty of selecting the proper adaptive method in practice. This motivates us to design an adaptive method, which can reduce the cost of tuning the initial learning rate. Furthermore, the method should achieve a satisfied accuracy no matter what the network architecture and data are. To achieve this, we propose a zerothorder method, _Adacomp_, to adaptively tune the learning rate. Unlike existing first-order adaptive methods, which adjust learning rate by exploiting gradients or additional model parameters, Adacomp only uses the values of loss function and is derived from minimizing Equation (1) with respect to \(\gamma_{t}\), which has the original expression  
\[\gamma\leftarrow\gamma/2+\frac{\max\{0,f(w_{t})-f(w_{t+1})\}}{\theta\|g(w_{t} )\|^{2}}, \tag{3}\]  
where \(\theta\) is an undetermined parameter and \(\theta\|g(w_{t})\|^{2}\) will be further substituted by other explicit factors. Refer to Equation (8) for details. Note that Equation (3) only uses the observable variables \(\|g(w_{t})\|\) and \(f(w_{t})-f(w_{t+1})\) to adjust \(\gamma\). It can be interpreted that when \(f(w_{k})-f(w_{k+1})\) dominates \((\gamma/2)\|g(w_{t})\|^{2}\), we use an aggressive learning rate to enhance the progress. In contrast, we use an exponential decaying learning rate to ensure convergence. Therefore, in a highly abstract level, \(\gamma\) is complementary to loss difference \(f(t_{k})-f(w_{t+1})\) and we name it _Adacomp_, which has the following two advantages. Firstly, Adacomp is insensitive to learning rate, batch size, network architecture, and network initialization. Secondly, due to only exploiting values of loss function rather than high-dimensional gradients, Adacomp has high computation efficiency. In summary, our contributions are as follows. * We propose a highly computation-efficient adaptive learning rate method, Adacomp, which only uses loss values rather than exploiting gradients as other adaptive methods. Additionally, Adacomp is robust to initial learning rate and other hyper-parameters, such as batch size and network architecture. * Based on the analysis of Adacomp, we give a new insight into why a diminishing learning rate is necessary when solving Equation (1) and why a gradient clipping strategy can outperform a fixed learning rate. * We conduct extensive experiments to compare the proposed Adacomp with several first-order adaptive methods on MNIST, KMNIST, Fashion-MNIST, CIFAR-10, and CIFAR-100 classification tasks. Additionally, we compare Adacomp with two evolutionary algorithms on MNIST and CIFAR-10 datasets.