Machine learning has intimate ties to optimization, considering that many learning problems are formulated as the minimization of a loss function that depends on a training set. An optimization problem that frequently appears in machine learning is the minimization of the average of loss functions over a finite training set, i.e.,

where -th observation in the training set , the function is the loss corresponding to , and is the weight vector. Starting with an initial guess for the weight vector w, stochastic gradient descent (SGD) methods [1] attempt to minimize the loss function by iteratively updating the values of w. Each iteration utilizes a sample , commonly called a “mini-batch”, which is taken randomly from the training set . The update from to at the t-th iteration relies on a gradient estimator, which in turn depends on the current mini-batch. The typical unbiased gradient estimator of the unknown true gradient is defined by

where is the gradient produced by the i-th observation within the current mini-batch of size N. The gradient estimator entails variance, since it depends on a random set of observations. If the variance of is large, the SGD method may have difficulty converging and perform poorly. Indeed, the variance may be reduced by increasing the mini-batch size N. However, this increases the computational cost of each iteration. Some recent methods in the literature that attempt

Figure 1: The proposed method, dubbed as AutoOpt, provides a general approach to an automatic and simultaneous adjustment of the learning rate and momentum hyperparameters. We deploy and examine the generic technique for the SGD, Adam, and AdaGrad optimizers, for the sake of training CNN based classifiers.

to reduce the variance of the gradient estimator include [2, 3, 4, 5, 6], to mention a few. While these methods provide unbiased gradient estimators, they are not necessarily optimal in the sense of meansquared error (MSE) which allows reducing the variance with the cost of bias. Momentum-based methods (see [7] and other references within) trade-off between variance and bias by constructing the gradient estimator as a combination of the current unbiased gradient estimator and previous gradient estimators. Other state-of-the-art methods use biased estimators by scaling the gradient with square roots of exponential moving averages of past squared gradients [8]. These methods include, for example, AdaGrad [9], Adam [10], AdaDelta [11], NAdam [12], etc. The main drawback for these methods is their reliance on one or more hyperparameters, i.e., parameters which must be tuned in advance to obtain adequate performance. Unfortunately, manual hyperparameter tuning is very costly, as every hyperparameter configuration is typically tested over many iterations. Previous attempts to automatically tune the learning rate alone were proposed in [13, 14] and examined for simple architectures, such as logistic regression and fully-connected neural networks (FCNN’s). The technique presented in [13], for example, proposes an automatic adjustment of the learning rate, limited by the assumption of a diagonal Hessian matrix, and disregarding the off-diagonal elements of the observations’ covariance matrix. The approach proposed in [14] set the learning rate by utilizing the Barzilai-Borwein method [15] which in turn relies on an approximation of the Hessian, ignoring gradient estimators as suggested in [13]. To the best of our knowledge, there is no method to adjust the momentum hyperparameter automatically; neither in solitary nor simultaneously with the learning rate.

In this paper, we present a novel and generic method to automatically and simultaneously adjust the learning rate and the momentum hyperparameters, to minimize (or maximally decrease) the expected loss after the next update. The general method, dubbed as AutoOpt, is deployed for three popular optimizers: SGD, Adam and AdaGrad, schematically described in Figure 1. The technique is practical for modern deep learning architectures and is successfully examined for convolutional neural networks (CNN’s) [16]. The rest of the paper is organized as follows. In Section 2, we provide background and motivation for the proposed method. In Section 3, we derive the general formulation and the theoretical properties of the optimal learning rate and momentum. The optimal values depend on the unknown true gradient, thus unattainable and annunciate as the “oracle” solution. Nevertheless, we show in Section 4 that the oracle solution can be estimated, hence makes it feasible for a practical use. We deploy the proposed technique in SGD, Adam [10], and AdaGrad [9] for the sake of training CNN based classifiers. Our experimental results which appear in Section 5, show that the method automatically achieves the lowest or comparable classification errors, obtained through a tedious systematic search of the learning rate and momentum. We conclude the paper with a discussion on some future work. Notations: We depict vectors in lowercase boldface letters and matrices in uppercase boldface. The transpose operator and the diagonal operator are denoted by and , respectively. The column vector of p ones is denoted by and the expectation operator is denoted by

We outset our discussion from the theoretical (and ideal) scenario of an unlimited training set. Suppose that the observations within the training set are independent identically distributed (i.i.d), drawn from a probability density function P (x). In the ideal case of an unlimited amount of training examples, the loss function (1) approaches the real unknown loss function, defined as

The loss function J (w) (3) is deterministic, and assumed to be continuously differentiable with respect to the weight vector w. Starting with an initial guess , we would like to generate a sequence of weights such that the loss function J (w) (3) is reduced at each iteration of the algorithm, i.e.,

The loss function J (w) (3) can be approximated by a second-order (i.e., quadratic) Taylor series expansion around

where

and

are the gradient vector and the Hessian matrix of the loss function J (w) (3), evaluated at . By deriving with respect to w and setting the result to zero, we find that the next weight vector which minimizes (5) is given by

The iterative equation (8) is also known as the Newton-Raphson method [17]. In practice, at time t, only a finite sample (the current mini-batch) of size N is available. As a result, neither the gradient vector , nor the Hessian matrix (and its inverse) required in (8), are known. To practically apply the update rule (8) for , both quantities and , must be replaced by their estimators, denoted as , respectively. The use of the estimators (instead of to the general update rule of SGD methods given by

We confine our discussion regarding the gradient estimator in (9), to the frequently used model

where is the unbiased estimator of the unknown true gradient momentum parameter which is a scalar between 0 and 1, and is the learning rate, a positive scalar which ensures that the update rule (9) do not produce a weight vector with an implausible large norm [18]. The inverse of the estimated Hessian matrix is not easy to compute. There are various methods to estimate the inverse of the Hessian matrix, such as Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton based methods [19, 20]. However, if computational simplicity is of paramount importance, then it is common to assume that is equal to the identity matrix I. In this paper we refer to that case as the classic SGD. The Adam optimizer [10], a popular SGD algorithm which is vastly used these days, assumes a diagonal Hessian matrix estimator of the form

Table 1: SGD methods that follow the general update rule (9) along with their gradient and Hessian estimators. These optimizers share the same gradient estimator model , with or without momentum, while utilizing different Hessian estimators.

The AdaGrad method [9], which corresponds to a version of Adam, utilizes the gradient estimator (10) with momentum , and a diagonal Hessian matrix estimator of the form

These methods propose different gradient and Hessian estimators, to be plugged into the update rule (9), and are summarized in Table 1.

Our objective in this paper is to find the optimal values of and at time t, which minimize the expected value of the loss function (5) when using the update rule (9), i.e.,

We provide the solution for (13) in the following section. Recall that (13) is solved for the general update rule (9). Thus, the proposed solution can be deployed in any SGD method that utilizes the gradient estimator . As previously mentioned, the optimizers which appear in Table 1 are examined in the experiments section.

In this section, we derive the optimal learning rate and momentum as defined in (13). By changing variables such that , we can rewrite the gradient estimator

where matrix defined as

and vector. Then, by substituting the update rule using the gradient estimator (14), we can rewrite the expected value of the loss function (5) as

where

The matrix and the vector , are of size and , respectively. The optimal vector , which we denote by , is the solution that minimizes the loss function (16), i.e.,

Since depends on the true gradient , which is unknown in practice, we refer to it as the oracle solution. In the following section we propose an estimator for the oracle solution

The oracle vector minimizes the loss function , but unfortunately depends on the unknown quantities and . Consider first the perplexing vector (18) which depends on the unknown gradient and the Hessian matrix . With the aim of proceeding toward a practical method, we unfold the tangled equation by assuming that the Hessian is known, i.e., , and provided by the optimizer currently in use (see Table 1). As a result, the vector (18) can be simplified (after a few mathematical manipulations) to

where

The scalar still depends on the unknown true gradient , however, can be

estimated. The derivation of an unbiased estimator of appears in Appendix A, and is equal to

where is the gradient produced by the i-th observation within the current mini-batch of size N. The estimator of (18) is therefore

The estimator of is calculated by replacing all expectations in by their sample counterparts, i.e.,

Finally, by incorporating the estimators , the oracle solution is estimated by

Consider that the values of varies based on the current mini-batch at time t, we mitigates this effect by using an exponentially weighted moving average model , defined as

We summarize the proposed method for an automatic and simultaneous adjustment of the learning rate and momentum in Algorithm 1. The vector is computed in each step with a time-complexity that is equal or better than the time-complexity of the back-propagation algorithm [21] (see Appendix B), therefore make the method feasible for a practical use in deep learning architectures. In the next section, we examine the proposed method for classification purposes using CNN’s, and show that the technique attains the lowest or comparable classification errors as expected from theory.

We utilize the proposed method to train CNN classifiers for the MNIST [22] and CIFAR10 [23] data sets. The neural network architecture for MNIST has two convolution layers (10 and 20 channels with a kernel size 5), max pooling (kernel size 2), ReLU non-linearity and drop-out, which produces 320 features, followed by two fully connected layers (50 and 10 output features). The output layer is a log softmax layer, and the loss function is the negative log likelihood (NLL) loss. The architecture for CIFAR10 (3 input channels) has two convolution layers (6 and 16 channels with a kernel size 5), max pooling (kernel size 2) and ReLU non-linearity, which produces 400 features followed by three fully connected layers (120, 84, and 10 output features). The output layer is again a log softmax layer and the loss function is the NLL loss. We run thousands of configurations with different learning rate, momentum and random initial weights that were generated from 10 different seeds. For the SGD optimizer we run exhaustive hyperparameter search with

Figure 2: Automatic learning rate and momentum for SGD as a function of step for the first convolutional layer of the MNIST classifier. As expected, the learning rate increases as the mini-batch size increases. Whereas the learning rate starts to decay automatically, the previous gradient shifts to be less biased. As a result, the method utilizes the benefits of the previous gradient by gradually increasing the momentum value.

learning rate , momentum M = {0, 0.3, 0.8, 0.9, 0.95, 0.99} and batch size values. This yields different settings for each data set. Every setting is run with 10 different seeds. Thus, a total of 3,240 different configurations have been tested for the SGD optimizer. For the Adam and AdaGrad optimizers, best parameter search is carried out among the same learning rate and batch size values as in SGD. In Adam, we use and as suggested in the original Adam paper. The parameter tuning for Adam and AdaGrad optimizers each yield a total of 54 different settings and 540 results due to the use of 10 different seeds. The proposed method produces for each layer its own learning rate and momentum. To get further insights and intuition regarding the approach’s behavior; we present in Figure 2 the learning rate and momentum, generated by SGD, for the first convolutional layer of the MNIST classifier as a function of the mini-batch size N. As expected, the learning rate, provided in Figure 2(a), increases as the mini-batch size increases. Since a larger mini-batch result with less variance of the gradient estimator, the proposed method increases the learning rate. Once the learning rate reaches its peak, we can observe a learning rate decay. The learning rate decay is another hyperparameter that should be set in advance. In our case, however, the learning rate decay emerges automatically based on the data. The momentum values are provided in Figure 2(b). Initially, since the learning rate is relatively large, the previous gradient is too biased to be combined with the current gradient , which results with low values of momentum. As the learning rate decay (and step size become smaller), the previous gradient less biased and therefore gain a greater presence when combined with the current unbiased gradient estimator . The latter is reflected by increasing values of momentum as can be seen in Figure 2(b). In Figure 3, we present the scatter plots of test errors vs. train errors, achieved by the CNN

Figure 3: Train and test errors for the MNIST CNN classifier, after 10 epochs with SGD, as a function of the mini-batch size. The proposed method (denoted in black dots) achieves comparable, or the lowest error, which otherwise would be attained by an exhaustive manual tuning.

Table 2: Lowest train and test errors (mean and std across 10 seeds), for SGD, Adam, and AdaGrad, obtained by a tedious manual tuning. The optimal learning rate and momentum are provided by the first and second configuration values, respectively. The automatic tuning counterparts of these optimizers achieve comparable, or better results.

architecture for MNIST after 10 epochs. It can be seen how the optimal learning rate changes as a function of the mini-batch size while the method adapts and achieves the lowest error rates. For N = 32, we observe that the optimal learning rate is , denoted by blue diamonds. It can be seen that the proposed method (denoted in the figure as AutoOpt), achieves the same error rates by automatically adapt to the optimal learning rate. For N = 64, the learning rate becomes sub-optimal and the new optimal learning rate increases to . Still, the proposed method adapts and achieves comparable test and train errors. Finally, when the mini-batch size increases to N = 256, the optimal learning rate increases to , and the previous learning rate of become sub-optimal. The optimal learning rate for ) is almost off the plot for the case of N = 256. Likewise, the proposed method performs similarly, or better, in the case of Adam and AdaGrad, as observed in Figure 4. For completeness, the lowest train and test errors (mean and std from 10 different seeds) obtained by the best performing configuration are summarized in Table 2. The first row in Table 2 lists the total number of parameter settings per data set for each optimizer. It can be observed that by conducting a tedious manual tuning, SGD, Adam and AdaGrad achieve comparable results. The deployment of the proposed method for these optimizers (AutoSGD, AutoAdam and AutoAdaGrad), avoids the tedious manual tuning while still achieving comparable train and test errors as shown in the table. The case of AutoAdam with CIFAR10 have a relatively large gap of more than 10%. The reason for that gap is a discrepancy between the unknown Hessian and the Hessian estimator provided by Adam (See the method’s assumption regarding the Hessian in Section 4, and Table 1 for different Hessian estimators). Nevertheless, as observed in Figure 4(e), the automatically tuned version attains a near-optimal solution in comparison to other configurations that were examined, and therefore, saves a substantial amount of time and efforts. Moreover, since SGD, Adam, and AdaGrad perform relatively the same after carefully tuned, it is straightforward to switch between their automatically tuned counterparts and reveal the best performing optimizer. An examination of three different automatic optimizers is still easily managed, in comparison to an intensive manual adjustment of each optimizer alone. The difference between the number of settings

Figure 4: Train and test errors for N = 128 after 10 epochs, for MNIST and CIFAR10, achieved by different optimizers. The MNIST classification errors, obtained by SGD, Adam, and AdaGrad, are presented in Figure (a), Figure (b), and Figure (c), respectively. The CIFAR10 errors, obtained by SGD, Adam, and AdaGrad, are presented in Figure (d), Figure (e), and Figure (f), respectively. The proposed method (denoted in black dots) automatically achieves comparable, or the lowest errors, and therefore avoids the exhaustive manual tuning.

for the original (manually tuned) optimizers and their automatic counterparts show the huge gain of the approach. To conclude, in all cases the proposed method automatically attains the lowest, or comparable test and train errors that otherwise would be achieved by an exhaustive manual tuning.

We tackle the manual tuning problem of two imperative hyperparameters: the learning rate and momentum. In Section 3, we derive a general method to compute the optimal learning rate and momentum that minimize the expected loss (13) after the next update. The technique relies on the unbiased gradient estimator which depends on the current mini-batch of size N at time t, and is summarized in Algorithm 1. The method is generic and can easily be deployed for different optimizers. Specifically, we examined the method for three well-known optimizers: SGD, Adam, and AdaGrad. The experimental results in Section 5 confirm the theoretical expectations where the learning rate and momentum automatically tuned to maximally decrease the expected loss by utilizing the mini-batch statistics, thus eliminating the need for an exhaustive manual tuning. We show that the method either outperform or comparable to the manual tuning by comparing classification errors of CNN based classifiers. Given the successful validation and the method’s generality, we intend to expand the proposed method into other deep learning architectures, and deploy it into more state-of-the-art optimizers previously mentioned. Also, as the optimal values of learning rate and momentum can freely increase or decrease based on the available data, we intend to examine the proposed approach for on-line training scenarios with non-stationary data. In these cases, the learning rate and momentum automatically adapt to the evolving data, and may stabilize to more appropriate settings based on the new distribution.

[1] James C Spall. Introduction to stochastic search and optimization: estimation, simulation, and control, volume 65. John Wiley & Sons, 2005.

[2] Chong Wang, Xi Chen, Alexander J Smola, and Eric P Xing. Variance reduction for stochastic gradient optimization. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 181–189. Curran Associates, Inc., 2013.

[3] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pages 315–323, 2013.

[4] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alexander J Smola. On variance reduction in stochastic gradient descent and its asynchronous variants. In Advances in Neural Information Processing Systems, pages 2647–2655, 2015.

[5] Hiroyuki Kasai. Stochastic variance reduced multiplicative update for nonnegative matrix factorization. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6338–6342. IEEE, 2018.

[6] Bicheng Ying, Kun Yuan, and Ali H Sayed. Convergence of variance-reduced learning under random reshuffling. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2286–2290. IEEE, 2018.

[7] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1139–1147, 2013.

[8] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.

[9] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):2121–2159, 2011.

[10] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.

[11] Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012.

[12] Timothy Dozat. Incorporating nesterov momentum into adam. In International Conference on Learning Representations, Workshop Track, 2016.

[13] Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. In International Conference on Machine Learning, pages 343–351, 2013.

[14] Conghui Tan, Shiqian Ma, Yu-Hong Dai, and Yuqiu Qian. Barzilai-borwein step size for stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 685–693, 2016.

[15] Jonathan Barzilai and Jonathan M Borwein. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1):141–148, 1988.

[16] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097–1105. Curran Associates, Inc., 2012.

[17] C. M. Bishop. Pattern recognition and machine learning, volume 4. Springer, New York, 2006.

[18] Antoine Bordes, Léon Bottou, and Patrick Gallinari. Sgd-qn: Careful quasi-newton stochastic gradient descent. Journal of Machine Learning Research, 10(Jul):1737–1754, 2009.

[19] Aryan Mokhtari and Alejandro Ribeiro. Res: Regularized stochastic bfgs algorithm. IEEE Transactions on Signal Processing, 62(23):6089–6104, 2014.

[20] Xunying Liu, Shansong Liu, Jinze Sha, Jianwei Yu, Zhiyuan Xu, Xie Chen, and Helen Meng. Limited-memory bfgs optimization of recurrent neural network language models for speech recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6114–6118. IEEE, 2018.

[21] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6088):533, 1986.

[22] Yann Lecun and Corinna Cortes. The MNIST database of handwritten digits. 2009.

[23] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.

[24] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.

[25] Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), pages 807–814, 2010.

The expression (21) can be written as

and finally

The expression in the expectation is therefore the unbiased estimator of , provided in

. When the Hessian estimator is diagonal, as in SGD, Adam, and AdaGrad (see

Table 1), the estimator (22) have a time-complexity of O (pN).

The proposed method for an automatic adjustment of learning rate and momentum (see Algorithm 1) can be utilized in fully-connected neural networks (FCNN’s) and convolution neural networks (CNN’s). Practically, when the Hessian estimator is a diagonal matrix, as in SGD, Adam, and AdaGrad (see Table 1) , the time complexity of the proposed algorithm remains the same as for the back-propagation phase [21], thus doesn’t increase the time complexity of the training. Consider the case of a FCNN with L layers [24]. The L layers, l = 1, . . . , L, are connected to each other by the following relation:

where f(.) is the activation function (for example, sigmoid() or rectified linear unit ReLU(.)[25]). The weight matrices and the bias vectors , are of size , respectively. The activation matrix (as well as ) is of size is the mini-batch size. Note that is the forwarded mini-batch of size

The gradients of a loss function J with respect to the parametersare calculated using the back-propagation algorithm [21], i.e., we can compute the gradientsl = 1, . . . , L by the following procedure:

For l = L, . . . , 1 calculate:

The time complexities for (28), (29), (30), (31) are , and , respectively. Recall the computation of the gradient , the individual gradients are calculated by

where have a time complexity of . Therefore, the time complexity for all individual gradients is . The time complexity for when the Hessian estimator is diagonal is also the same as computing (see Appendix A). Therefore, the time complexity of Algorithm 1, when deployed for a fully-connected layer, have the same time complexity as its back-propagation, which is

Similarly, assume that the l-th layer is a convolutional layer having the filter . The latter is a 4-dimensional tensor of size is the convolve window size, and denotes the number of channels of the l-th layer. The gradient of the c-th channel (is a 3-dimensional tensor of size , denoted as , and computed by

where is the gradient with respect to the i-th observation, defined as

The scalar indicates the gradient of the activation denote the height and width of the l-th layer. The tensor of size corresponds to the activation of the previous layer which was used to generate the activation -th observation.

Therefore, the time-complexity for calculating the mini-batch gradient (or the set of indi- vidual gradients. Once we have the gradients per-observation, we can proceed to Algorithm 1 that have a time-complexity of which is lower than the time-complexity of