Title: LEARNING WITH RANDOM LEARNING RATES

Abstract: Hyperparameter tuning is a bothersome step in the training of deep learning models. One of the most sensitive hyperparameters is the learning rate of the gradient descent. We present the All Learning Rates At Once (Alrao) optimization method for neural networks: each unit or feature in the network gets its own learning rate sampled from a random distribution spanning several orders of magnitude. This comes at practically no computational cost. Perhaps surprisingly, stochastic gradient descent (SGD) with Alrao performs close to SGD with an optimally tuned learning rate, for various architectures and problems. Notably, Alrao is robust: all runs were able to learn without any tuning. This makes Alrao a candidate for situations in which a neural network has to work from the first try. This text comes with a PyTorch implementation of the method, which can be plugged on an existing PyTorch model.

1. INTRODUCTION:

Hyperparameter tuning is a notable source of computational cost with deep learning models (Zoph and Le, 2016) . One of the most critical hyperparameters is the learning rate of the gradient descent (Theodoridis, 2015, p. 892) . With too large learning rates, the model does not learn; with too small learning rates, optimization is slow and can lead to local minima and poor generalization (Jastrzebski et al., 2017; Kurita, 2018; Mack, 2016; Surmenok, 2017) . Although popular optimizers like Adam (Kingma and Ba, 2015) come with default hyperparameters, fine-tuning and scheduling of the Adam learning rate is still frequent (Denkowski and Neubig, 2017) , and we suspect the default setting might be somewhat specific to current problems and architecture sizes. Such hyperparameter tuning takes up a lot of engineering time. These and other issues largely prevent deep learning models from working out-of-the-box on new problems, or on a wide range of problems, without human intervention (AutoML setup, (Guyon et al., 2016) ).

We propose All Learning Rates At Once (Alrao), an alteration of standard stochastic gradient descent for deep learning models. Alrao uses multiple learning rates at the same time in the same network. By sampling one learning rate per feature, Alrao reaches performance close to the performance of the optimal learning rate, without having to try multiple learning rates.

In our experiments, Alrao was found to be quite resilient: not a single run failed to learn, provided a large enough range of admissible learning rates are included. On the other hand, the admissible range of learning rates for SGD is quite narrow. Alrao could be useful in situations where a neural network has to be trained and work out of the box, or for quickly testing network architectures.

Alrao increases the size of a model on the output layer, but not on the internal layers: this usually adds little computational cost unless most parameters occur on the output layer. This text comes along with a Pytorch implementation usable on a wide set of architectures.

Related Work. Automatically using the "right" learning rate for each parameter was one motivation behind "adaptive" methods such as RMSProp (Tieleman and Hinton, 2012) , AdaGrad (Duchi et al., 2011) or Adam (Kingma and Ba, 2015) . Adam with its default setting is currently considered the default method in many works (Wilson et al., 2017) , and we use it as a baseline. However, further global adjustement of the Adam learning rate is common (Liu et al., 2017) . Many other heuristics for setting the learning rate have been proposed, e.g., (Schaul et al., 2013) ; most start with the idea of approximating a second-order Newton step to define an optimal learning rate (LeCun et al., 1998) .

Methods that directly set per-parameter learning rates are equivalent to preconditioning the gradient descent with a diagonal matrix. Asymptotically, an arguably optimal preconditioner is either the Hessian of the loss (Newton method) or the Fisher information matrix (Amari, 1998) . These can be viewed as setting a per-direction learning rate after redefining directions in parameter space. From this viewpoint, Alrao just replaces these preconditioners with a random diagonal matrix whose entries span several orders of magnitude.

Another approach to optimize the learning rate is to perform a gradient descent on the learning rate itself through the whole training procedure (for instance (Maclaurin et al., 2015) ). This can be applied online to avoid backpropagating through multiple training rounds (Massé and Ollivier, 2015) . This idea has a long history, see, e.g., (Schraudolph, 1999; Mahmood et al., 2012) . Some training algorithms depart from gradient descent altogether, and become learning rate-free, such as (Orabona and Tommasi, 2017) using betting strategies to simulate gradient descent.

The learning rate can also be optimized within the framework of architecture search, exploring both the architecture and learning rate at the same time (e.g., (Real et al., 2017) ). The methods range from reinforcement learning (Zoph and Le, 2016; Baker et al., 2016; Li et al., 2017) , evolutionary algorithms (e.g., (Stanley and Miikkulainen, 2002; Jozefowicz et al., 2015; Real et al., 2017) ), Bayesian optimization (Bergstra et al., 2013) or differentiable architecture search (Liu et al., 2018) . These methods are resource-intensive and do not allow for finding a good learning rate in a single run.

Motivation. Alrao was inspired by the intuition that not all units in a neural network end up being useful. Hopefully, in a large enough network, a sub-network made of units with a good learning rate could learn well, and hopefully the units with a wrong learning rate will just be ignored. (Units with a too large learning rate may produce large activation values, so this assumes the model has some form of protection against those, such as BatchNorm or sigmoid/tanh activations.) Several lines of work support the idea that not all units of a network are useful or need to be trained. First, it is possible to prune a trained network without reducing the performance too much (e.g., (Le-Cun et al., 1990; Han et al., 2015a; b; See et al., 2016) ). Li et al. (2018) even show that performance is reasonable if learning only within a very small-dimensional affine subspace of the parameters, chosen in advance at random rather than post-selected.

Second, training only some of the weights in a neural network while leaving the others at their initial values performs reasonably well (see experiments in Appendix H). So in Alrao, units with a very small learning rate should not hinder training.

Alrao is consistent with the lottery ticket hypothesis, which posits that "large networks that train successfully contain subnetworks that-when trained in isolation-converge in a comparable number of iterations to comparable accuracy" (Frankle and Carbin, 2018) . This subnetwork is the lottery ticket winner: the one which had the best initial values. Arguably, given the combinatorial number of subnetworks in a large network, with high probability one of them is able to learn alone, and will make the whole network converge. Viewing the per-feature learning rates of Alrao as part of the initialization, this hypothesis suggests there might be enough sub-networks whose initialization leads to good convergence.

2. ALL LEARNING RATES AT ONCE: DESCRIPTION:

Principle. Alrao starts with a standard optimization method such as SGD, and a range of possible learning rates (η min , η max ). Instead of using a single learning rate, we sample once and for all one learning rate for each feature, randomly sampled log-uniformly in (η min , η max ). Then these learning rates are used in the usual optimization update:

EQUATION

where θ l,i is the set of parameters used to compute the feature i of layer l from the activations of layer l -1 (the incoming weights of feature i). Thus we build "slow-learning" and "fast-learning" features, in the hope to get enough features in the "Goldilocks zone".

What constitutes a feature depends on the type of layers in the model. For example, in a fully connected layer, each component of a layer is considered as a feature: all incoming weights of the same unit share the same learning rate. On the other hand, in a convolutional layer we consider each convolution filter as constituting a feature: there is one learning rate per filter (or channel), thus keeping translation-invariance over the input image. In LSTMs, we apply the same learning rate to all components in each LSTM unit (thus in the implementation, the vector of learning rates is the same for input gates, for forget gates, etc.).

However, the update (1) cannot be used directly in the last layer. For instance, for regression there may be only one output feature. For classification, each feature in the final classification layer represents a single category, and so using different learning rates for these features would favor some categories during learning. Instead, on the output layer we chose to duplicate the layer using several learning rate values, and use a (Bayesian) model averaging method to obtain the overall network output (Fig. 1 ). Appendix B contains a proof (under convexity assumptions) that this mechanism works, given the initial layers.

We set a learning rate per feature, rather than per parameter. Otherwise, every feature would have some parameters with large learning rates, and we would expect even a few large incoming weights to be able to derail a feature. So having diverging parameters within a feature is hurtful, while having diverging features in a layer is not necessarily hurtful since the next layer can choose to disregard them. Still, we tested this option; the results are compatible with this intuition (Appendix G).

Definitions and notation. We now describe Alrao more precisely for deep learning models with softmax output, on classification tasks (the case of regression is similar).

Let D = {(x 1 , y 1 ), ..., (x N , y N )}, with y i ∈ {1, ..., K}, be a classification dataset. The goal is to predict the y i given the x i , using a deep learning model Φ θ . For each input x, Φ θ (x) is a probability distribution over {1, ..., K}, and we want to minimize the categorical cross-entropy loss over the dataset:

1 N i (Φ θ (x i ), y i ).

A deep learning model for classification Φ θ is made of two parts: a pre-classifier φ θ pc which computes some quantities fed to a final classifier layer

C θ cl , namely, Φ θ (x) = C θ cl (φ θ pc (x)). The clas- sifier layer C θ cl with K categories is defined by C θ cl = softmax • W T x + b with θ cl = (W, b),

and softmax(x 1 , ..., x K ) k = e x k /( i e xi ) .The pre-classifier is a computational graph composed of any number of layers, and each layer is made of multiple features.

We denote log-U(•; η min , η max ) the log-uniform probability distribution on an interval (η min , η max ): namely, if η ∼ log-U(•; η min , η max ), then log η is uniformly distributed between log η min and log η max . Its density function is log-U(η; η min , η max ) =

1 η min ≤η≤ηmax log(ηmax)-log(ηmin) × 1 η .

Alrao for the pre-classifier: A random learning rate for each feature. In the pre-classifier, for each feature i in each layer l, a learning rate η l,i is sampled from the probability distribution log-U(.; η min , η max ), once and for all at the beginning of training.1 Then the incoming parameters of each feature in the preclassifier are updated in the usual way with this learning rate (Eq. 3).

Alrao for the classifier layer: Model averaging from classifiers with different learning rates.

In the classifier layer, we build multiple clones of the original classifier layer, set a different learning rate for each, and then use a model averaging method from among them. The averaged classifier and the overall Alrao model are:

EQUATION

where the C θ cl j are copies of the original classifier layer, with non-tied parameters, and θ cl := (θ cl 1 , ..., θ cl N cl ). The a j are the parameters of the model averaging, and are such that for all j, 0 ≤ a j ≤ 1, and j a j = 1. These are not updated by gradient descent, but via a model averaging method from the literature (see below).

For each classifier C θ cl j , we set a learning rate η j defined by log η j = log η min + j-1 N cl -1 log ηmax ηmin , so that the classifiers' learning rates are log-uniformly spread on the interval [η min , η max ]. Thus, the original model Φ θ (x) leads to the Alrao model Φ Alrao θ (x). Only the classifier layer is modified, the pre-classifier architecture being unchanged.

Update rule. Alg. 1 presents the full Alrao algorithm. The updates for the pre-classifier, classifier, and model averaging weights are as follows.

• The update rule for the pre-classifier is the usual SGD one, with per-feature learning rates.

For each feature i in each layer l, its incoming parameters are updated as:

EQUATION

• The parameters θ cl j of each classifier clone j on the classifier layer are updated as if this classifier alone was the only output of the model:

EQUATION

(still sharing the same pre-classifier φ θ pc ). This ensures classifiers with low weights a j still learn, and is consistent with model averaging philosophy. Algorithmically this requires differentiating the loss N cl times with respect to the last layer (but no additional backpropagations through the preclassifier).

• To set the weights a j , several model averaging techniques are available, such as Bayesian Model Averaging (Wasserman, 2000) . We decided to use the Switch model averaging (Van Erven et al., 2012) , a Bayesian method which is both simple, principled and very responsive to changes in performance of the various models. After each sample or mini-batch, the switch computes a modified posterior distribution (a j ) over the classifiers. This computation is directly taken from (Van Erven et al., 2012) and explained in Appendix A. The observed evolution of this posterior during training is commented in Appendix C.

Implementation. We release along with this paper a Pytorch (Paszke et al., 2017) implementation of this method. It can be used on an existing model with little modification. A short tutorial is given in Appendix J. The features (sets of weights which will share the same learning rate) need to be defined for each layer type: for now we have done this for linear, convolutional, and LSTMs layers.

Algorithm 1 Alrao for model

Φ θ = C θ cl •φ θ pc with N cl classifiers and learning rates in [η min , η max ] 1: a j ← 1/N cl for each 1 ≤ j ≤ N cl Initialize the N cl model averaging weights a j 2: Φ Alrao θ (x) := N cl j=1 a j C θ cl j (φ θ pc (x))

Define the Alrao architecture 3: for all layers l, for all feature i in layer l do

4: Sample η l,i ∼ log-U(.; η min , η max ).

Sample a learning rate for each feature 5: for all classifiers j, 1 ≤ j ≤ N cl do 6:

Define log η j = log η min + j-1 N cl -1 log ηmax ηmin .

Set a learning rate for each classifier j 7: while stopping criterion is false do The criterion we use is given in section 3 8:

z t ← φ θ pc (x t )

Store the pre-classifier output 9:

for all layers l, for all feature i in layer l do 10:

θ l,i ← θ l,i -η l,i • ∇ θ l,i (Φ Alrao θ (x t ), y t )

Update the pre-classifier weights 11:

for all Classifier j do 12:

θ cl j ← θ cl j -η j • ∇ θ cl j (C θ cl j (z t ), y t ) Update the classifiers' weights 13: a ← ModelAveraging(a, (C θ cl i (z t )) i , y t )

Update the model averaging weights.

14:

t ← t + 1 mod N

3. EXPERIMENTS:

We tested Alrao on various convolutional networks for image classification (Imagenet and CI-FAR10), and on LSTMs for text prediction. The baselines are SGD with an optimal learning rate, and Adam with its default setting, arguably the current default method (Wilson et al., 2017) .

Image classification on ImageNet and CIFAR10. For image classification, we used the Ima-geNet (Deng et al., 2009) and CIFAR10 (Krizhevsky, 2009) datasets. The ImageNet dataset is made of 1,283,166 training and 60,000 testing data; we split the training set into a smaller training set and a validation set with 60,000 samples. We do the same on CIFAR10: the 50,000 training samples are split into 40,000 training samples and 10,000 validation samples.

For each architecture, training on the smaller training set was stopped when the validation loss had not improved for 20 epochs. The epoch with best validation loss was selected and the corresponding model tested on the test set. The inputs are normalized, and training used data augmentation: random cropping and random horizontal flipping (see Appendix D for details). Each setting was run 5 or 10 times: the confidence intervals presented are the standard deviation over these runs.

We tested Alrao on several standard architectures for these tasks. On ImageNet, we tested Resnet50 (He et al., 2016) , Densenet121 (Huang et al., 2017) and Alexnet (Krizhevsky, 2014) , all using the standard Pytorch implementation (Paszke et al., 2017) . On CIFAR10, we tested GoogLeNet (Szegedy et al., 2015) , VGG19 (Simonyan and Zisserman, 2014) and MobileNet (Howard et al., 2017) with implentation from (Kianglu, 2018) .

The Alrao learning rates were sampled log-uniformly from η min = 10 -5 to η max = 10. For the output layer we used 10 classifiers with switch model averaging (Appendix A); the learning rates of the output classifiers are deterministic and log-uniformly spread in [η min , η max ].

In addition, each model was trained with SGD for every learning rate in the set {10 -5 , 10 -4 , 10 -3 , 10 -2 , 10 -1 , 1., 10.}. The best SGD learning rate is selected on the validation set, then reported in Table 1 . We also compare to Adam with its default hyperparameters (η = 10 -3 , β 1 = 0.9, β 2 = 0.999).

Finally, since Alrao may waste units with unadapted learning rates, we also tested architectures with increased width (3 times as many units) with Alrao and Adam on ImageNet.

The results are presented in Table 1 . Learning curves with various SGD learning rates, with Adam, and with Alrao are presented in Fig. 2 . Fig. 3 tests the influence of η min and η max .

Recurrent learning on Penn Treebank. To test Alrao on a different kind of architecture, we used a recurrent neural network for text prediction on the Penn Treebank (Marcus et al., 1993) dataset. While Alrao uses learning rates from the entire range, its performance is comparable to the optimal learning rate.

The experimental procedure is the same, with (η min , η max ) = (0.001, 100) and 6 output classifiers for Alrao. The results appear in Table 1 , where the loss is given in bits per character and the accuracy is the proportion of correct character predictions.

The model was trained for character prediction rather than word prediction. This is technically easier for Alrao implementation: since Alrao uses copies of the output layer, memory issues arise for models with most parameters on the output layer. Word prediction (10,000 classes on PTB) requires more output parameters than character prediction; see Section 4 and Appendix F.

The model is a two-layer LSTM (Hochreiter and Schmidhuber, 1997) with an embedding size of 100 and with 100 hidden features. A dropout layer with rate 0.2 is included before the decoder. The training set is divided into 20 minibatchs. Gradients are computed via truncated backprop through time (Werbos, 1990) with truncation every 70 characters.

Comments. As expected, Alrao often performs slightly worse than the best learning rate (though it performs better in one setup). Even with wide intervals (η min , η max ), Alrao comes reasonably close to the best learning rate, across all setups. Although Adam with its default parameters almost matches optimal SGD, this is not always the case. On ImageNet, Adam either learns quickly then strongly overfits (Figs. 2a, 2b) , or fails to learn altogether (Table 1 , Fig. 5c ). This confirms a known risk of overfit with Adam (Wilson et al., 2017) . Overall, in our setup, Alrao seems to be a more reliable default method.

Table 1::

Performance of Alrao, of SGD with optimal learning rate from {10 -5 , 10 -4 , 10 -3 , 10 -2 , 10 -1 , 1., 10.}, and of Adam with its default setting. Three convolutional models are reported for image classification on CIFAR10, three others for ImageNet, and one recurrent model for character prediction (Penn Treebank). The Alrao learning rates have been taken in wide a priori reasonable intervals, [η min ; η max ] = [10 -5 ; 10] for CNNs (CIFAR10 and ImageNet) and [10 -3 ; 10 2 ] for RNNs (PTB). Each experiment is run 10 times (CIFAR10), 5 times (PTB) or 1 time (ImageNet); the confidence intervals report the standard deviation over these runs. (TODO: ongoing for ImageNet) 

4. LIMITATIONS, FURTHER REMARKS, AND FUTURE DIRECTIONS:

Increased number of parameters for the classification layer. Alrao modifies the output layer of the optimized model. The number of parameters for the classification layer is multiplied by the number of classifier copies used (the number of parameters in the pre-classifier is unchanged). On CIFAR10 (10 classes), the number of parameters increased by less than 5% for the models used. On Penn Treebank, the number of parameters increased by 15% in our setup (working at the character level); working at word level it would have increased threefold (Appendix F).

This is clearly a limitation for models with most parameters in the classifier layer. For output-layerheavy models, this can be mitigated by handling the copies of the classifiers on distinct computing units: in Alrao these copies work in parallel given the pre-classifier.

Still, models dealing with a very large number of output classes usually rely on other parameterizations than a direct softmax, such as a hierarchical softmax (see references in (Jozefowicz et al., 2016) ); Alrao could be used in conjunction with such methods.

Adding two hyperparameters. We claim to remove a hyperparameter, the learning rate, but replace it with two hyperparameters η min and η max . Formally, this is true. But a systematic study of the impact of these two hyperparameters (Fig. 3 ) shows that the sensitivity to η min and η max is much lower than the original sensitivity to the learning rate. In our experiments, convergence happens as soon as (η min ; η max ) contains a reasonable learning rate (Fig. 3 ).

A wide range of values of (η min ; η max ) will contain one good learning rate and achieve close-tooptimal performance (Fig. 3 ). Typically, we recommend to just use an interval containing all the learning rates that would have been tested in a grid search, e.g., 10 -5 to 10.

So, even if the choice of η min and η max is important, the results are much more stable to varying these two hyperparameters than to the learning rate. For instance, standard SGD fails due to numerical issues for η = 100 while Alrao with η max = 100 works with any η min ≤ 1 (Fig. 3 ), and is thus stable to relatively large learning rates. We would still expect numerical issues with very large η max , but this has not been observed in our experiments.

Alrao with Adam. The Alrao idea can be used with other optimizers, such as Adam. But Alrao with Adam is much less reliable than standard Alrao. Surprisingly, this occurs mostly for test per- formance, which can even diverge, while training curves mostly look good (Appendix E). We have no definitive explanation for this at present. It might be that changing Adam's learning rate requires changing its momentum parameters in a correlated way. It might be that Alrao does not work on Adam because Adam is more sensitive to its hyperparameters. The stark train/test discrepancy also suggests that Alrao with Adam may perform well as a pure optimization method but exacerbates the underlying risk of overfit of Adam (Wilson et al., 2017; Keskar and Socher, 2017) .

Increasing network size. With Alrao, neurons with unsuitable learning rates will not learn: those with a too large learning rate might learn nothing, while those with too small learning rates will learn too slowly to be used. Thus, Alrao may reduce the effective size of the network to only a fraction of the actual architecture size, depending on (η min , η max ).

Our first intuition was that increasing the width of the network was going to be necessary with Alrao, to avoid wasting too many units. Tests of Alrao with increased width are reported in Table 1 and Appendix I. Incidentally, these tests show that width was a limiting factor of the models used for both Alrao and SGD (Appendix I). Still, to our surprise, Alrao worked well even without width augmentation.

Other optimization algorithms, other hyperparameters, learning rate schedulers... Using a learning rate schedule instead of a fixed learning rate is often effective (Bengio, 2012) . We did not use learning rate schedulers here; this may partially explain why the results in Table 1 are worse than the state-of-the-art. Nothing prevents using such a scheduler within Alrao, e.g., by dividing all Alrao learning rates by a time-dependent constant; we did not experiment with this yet.

The idea behind Alrao could be used on other hyperparameters as well, such as momentum. However, if more hyperparameters are initialized randomly for each feature, the fraction of features having all their hyperparameters in the "Goldilocks zone" will quickly decrease.

5. CONCLUSION:

Applying stochastic gradient descent with random learning rates for different features is surprisingly resilient in our experiments, and provides performance close enough to SGD with an optimal learning rate, as soon as the range of random learning rates contains a suitable one. This could save time when testing deep learning models, opening the door to more out-of-the-box uses of deep learning.

A MODEL AVERAGING WITH THE SWITCH:

As explained is Section 2, we use a model averaging method on the classifiers of the output layer. We could have used the Bayesian Model Averaging method (Wasserman, 2000) . But one of its main weaknesses is the catch-up phenomenon (Van Erven et al., 2012) : plain Bayesian posteriors are slow to react when the relative performance of models changes over time. Typically, for instance, some larger-dimensional models need more training data to reach good performance: at the time they become better than lower-dimensional models for predicting current data, their Bayesian posterior is so bad that they are not used right away (their posterior needs to "catch up" on their bad initial performance). This leads to very conservative model averaging methods.

The solution from (Van Erven et al., 2012) against the catch-up phenomenon is to switch between models. It is based on previous methods for prediction with expert advice (see for instance (Herbster and Warmuth, 1998; Volf and Willems, 1998) and the references in (Koolen and De Rooij, 2008; Van Erven et al., 2012 )), and is well rooted in information theory. The switch method maintains a Bayesian posterior distribution, not over the set of models, but over the set of switching strategies between models. Intuitively, the model selected can be adapted online to the number of samples seen.

We now give a quick overview of the switch method from Van Erven et al. ( 2012): this is how the model averaging weights a j are chosen in Alrao.

Assume that we have a set of prediction strategies M = {p j , j ∈ I}. We define the set of switch sequences, S = {((t 1 , j 1 ), ..., (t L , j L )), 1 = t 1 < t 2 < ... < t L , j ∈ I}. Let s = ((t 1 , j 1 ), ..., (t L , j L )) be a switch sequence. The associated prediction strategy p s (y 1:n |x 1:n ) uses model p ji on the time interval [t i ; t i+1 ), namely

p s (y 1:i+1 |x 1:i+1 , y 1:i ) = p Ki (y i+1 |x 1:i+1 , y 1:i ) (5)

where K i is such that K i = j l for t l ≤ i < t l+1 . We fix a prior distribution π over switching sequences. In this work, I = {1, ..., N C } the prior is, for a switch sequence s = ((t 1 , j 1 ), ..., (t L , j L )):

π(s) = π L (L)π K (j 1 ) L i=2 π T (t i |t i > t i-1 )π K (j i ) (6)

with π L (L) = θ L 1-θ a geometric distribution over the switch sequences lengths, π K (j) = 1 N C the uniform distribution over the models (here the classifiers) and π T (t) = 1 t(t+1) . This defines a Bayesian mixture distribution:

p sw (y 1:T |x 1:T ) = s∈S π(s)p s (y 1:T |x 1:T ) (7)

Then, the model averaging weight a j for the classifier j after seeing T samples is the posterior of the switch distribution: π(K T +1 = j|y 1:T , x 1:T ).

EQUATION

These weights can be computed online exactly in a quick and simple way (Van Erven et al., 2012) , thanks to dynamic programming methods from hidden Markov models.

The implementation of the switch used in Alrao exactly follows the pseudo-code from (Van Erven et al., 2008) , with hyperparameter θ = 0.999 (allowing for many switches a priori). It can be found in the accompanying online code.

B CONVERGENCE RESULT IN A SIMPLE CASE:

We prove a convergence result on Alrao in a simplified case: we assume that the loss is convex, that the pre-classifier is fixed, that we work with full batch gradients rather than stochastic gradient descent, and that the Alrao model averaging method is standard Bayesian model averaging. The convexity and fixed classifier assumptions cover, for instance, standard logistic regression: in that case the Alrao output layer contains copies of a logistic classifier with various learning rates, and the Alrao pre-classifier is the identity (or any fixed linear pre-classifier).

For each Alrao classifier j, for simplicity we denote its parameters by θ j instead of θ cl j (there is no more ambiguity since the pre-classifier is fixed).

The loss of some classifier C on a dataset with features (x i ) and labels

(y i ) is L(C) := 1 N i (C(x i ), y i )

, where for each input x i , (C(x i ) y ) y∈Y is a probability distribution over the possible labels y ∈ Y, and we use the log-loss (C(x i ), y i ) := -log C(x i ) yi .

For a classifier C θ with parameter θ, let us abbreviate L(θ) := L(C θ ). We assume that L(θ) is a non-negative convex function, with ∇ 2 L(θ) λI for all θ. Let L * be its global infimum; we assume L * is a minimum, reached at some point θ * , namely L(θ * ) = L * . Moreover we assume that L is locally strongly convex at its minimum θ * : ∇ 2 L(θ * ) 0.

The Alrao architecture for such a classifier C θ uses N cl copies of the same classifier, with different parameter values:

Φ Alrao θ Alrao (x) = N cl j=1 a j C θj (9)

where θ Alrao := (θ 1 , ..., θ N cl ), and where the (a j ) j are the weights given by the model averaging method. We abbreviate L(θ Alrao ) := L(Φ Alrao θ Alrao ).

The Alrao classification layer uses a set of learning rates (η j ) j∈J , and starting points (θ (0) j ) j∈J . Using full-batch (non stochastic) Alrao updates we have

EQUATION

EQUATION

We assume that the model averaging method is Bayesian Model Averaging.

We have assumed that the Hessian of the loss of the model satisfies ∇ 2 L(θ) λI. Under this condition, the standard theory of gradient descent for convex functions requires that the learning rate be less than 1/λ, otherwise the gradient descent might diverge. Therefore, for Alrao we assume that at least one of the learning rates considered by Alrao is below this threshold. Theorem 1. Assume that at least one of the Alrao learning rates η j satisfies η j < 1/λ, with λ as above. Then, under the assumptions above, the Alrao loss is at most the optimal loss when t → ∞:

lim sup t L(θ (t) Alrao ) ≤ L * (12)

Proof. Let us analyze the dynamics of the different models in the model averaging method. Let us split the set of Alrao classifiers in two categories according to whether their sum of errors is finite or infinite, namely,

EQUATION

EQUATION

and in particular, for any j ∈ A, lim t L(θ (t) j ) = L * . The proof is organized as follows: We first show that A is not empty. Then, we show that lim t→∞ a (t) j = 0 for all j ∈ B: these models are eliminated by the model averaging method. Then we will be able to conclude.

First, we show that A is not empty: namely, that there is least one j such that t≥0 (L(θ

(t) j )-L * ) < ∞.

We know that there is j such that η j < 2 λ . Hence, the standard theory of gradient descent for convex functions shows that this particular classifier converges (e.g., (Tibshirani and Marchetti-Bowick, 2013 )), namely, the loss (L(θ (t) j )) t converges to L * . Moreover, since L is localy stricly convex around θ * , this implies that lim t θ (t) j = θ * . We now show that the sum of errors for this specific j converges. We assumed that L(θ) is locally strongly convex in θ * . Let µ > 0 such that ∇ 2 L(θ * ) µI. Since L is C 2 , there is ε such that for any θ such that θ -θ * ≤ ε , then ∇ 2 L(θ)

µ 2 I. Let τ ∈ N such that θ (τ ) j -θ * < ε .

Then, from the theory of gradient descent for strongly convex functions (Tibshirani and Marchetti-Bowick, 2013) , we know there is some γ < 1 such that for t > τ , L(θ

(t) j ) -L * ≤ C θ (τ ) j -θ * γ t . We have: t s=1 L(θ (s) j ) -L * = τ s=1 L(θ (s) j ) -L * + t s=τ L(θ (s) j ) -L * (15) ≤ τ s=1 L(θ (s) j ) -L * + C θ (τ ) j -θ * γ τ 1 1 -γ Thus t≥0 L(θ (t) j ) -L * < ∞. Therefore, A is not empty.

We now show that the weights a (t) j tend to 0 for any j ∈ B, namely, lim t→∞ a (t) j = 0. Let j ∈ B and take some i ∈ A. In Bayesian model averaging, the weights are

EQUATION

EQUATION

EQUATION

Since i ∈ A and j ∈ B, by definition of A and B this tends to 0. Therefore, lim t a (t) j = 0 for all j ∈ B.

We now prove the statement of the theorem. We have:

EQUATION

= j∈A ãj L(θ

EQUATION

EQUATION

thanks to Jensen's inequality for -log, then because lim t a (t) j = 0 for j ∈ B, and finally because lim t L(θ (t) j ) = L * for j ∈ A. Taking the lim sup, we have:

lim sup t L(θ (t) Alrao ) ≤ L * (27)

which ends the proof.

C EVOLUTION OF THE POSTERIOR:

The evolution of the model averaging weights can be observed during training. In Figure 4 , we can see their evolution during the training of the GoogLeNet model with Alrao on CIFAR10, 10 classifiers, with η min = 10 -5 and η max = 10 1 .

We can make several observations. First, after only a few gradient descent steps, the model averaging weights corresponding to the three classifiers with the largest learning rates go to zero. This means that their parameters are moving too fast, and their loss is getting very large.

Next, for a short time, a classifier with a moderately large learning rate gets the largest posterior weight, presumably because it is the first to learn a useful model.

Finally, after the model has seen approximately 4,000 samples, a classifier with a slightly smaller learning rate is assigned a posterior weight a j close to 1, while all the others go to 0. This means that after a number of gradient steps, the model averaging method acts like a model selection method. 

D ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS:

In the case of CIFAR-10, we normalize each input channel x i (1 ≤ i ≤ 3), using its mean and its standard deviation over the training set. Let µ i and σ i be respectively the mean and the standard deviation of the i-th channel. Then each input (x 1 , x 2 , x 3 ) is transformed into ( x1-µ1 σ1 , x2-µ2 σ2 , x3-µ3 σ3 ). This operation is done over all the data (training, validation and test).

Moreover, we use data augmentation: every time an image of the training set is sent as input of the NN, this image is randomly cropped and and randomly flipped horizontally. Cropping consists in filling with black a band at the top, bottom, left and right of the image. The size of this band is randomly chosen between 0 and 4 in our experiments.

On CIFAR10 and PTB, the batch size was 32 for every architecture. On ImageNet, the batch-size is 256 for Alexnet and ResNet50, and 128 for Densent121. 

E ALRAO WITH ADAM:

In Figure 6 , we report our experiments with Alrao-Adam on CIFAR10. As explained in Section 4, Alrao is much less reliable with Adam than with SGD. This is especially true for the test performance, which can even diverge while training performance remains either good or acceptable (Fig. 6 ). Thus Alrao-Adam seems to send the model into atypical regions of the search space.

F NUMBER OF PARAMETERS:

As explained in Section 4, Alrao increases the number of parameters of a model, due to output layer copies. The additional number of parameters is approximately equal to (N cl -1) × K × d where N cl is the number of classifier copies used in Alrao, d is the dimension of the output of the pre-classifier, and K is the number of classes in the classification task (assuming a standard softmax output; classification with many classes often uses other kinds of output parameterization instead). The number of parameters for the models used, with and without Alrao, are in Table 2 . We used 10 classifiers in Alrao for convolutional neural networks, and 6 classifiers for LSTMs. Using Alrao for classification tasks with many classes, such as word prediction (10,000 classes on PTB), increases the number of parameters noticeably.

For those model with significant parameter increase, the various classifier copies may be done on parallel GPUs.

G SAMPLING A LEARNING RATE PER WEIGHT:

In Alrao we sample a learning rate for each feature. Intuitively, each feature (or neuron) is a computation unit of its own, using a number of inputs from the previous layer. If we assume that there is a "right" learning rate for learning new features based on information from the previous layer, then we should try a learning rate per feature; some features will be useless, while others will be used further down in the network.

An obvious variant is to set a random learning rate per weight, instead of for all incoming weights of a given feature. However, this runs the risk that every feature in a layer will have a few incoming weights with a large rate, so intuitively every feature is at risk of diverging. This is why we favored per-feature rates.

Still, we tested sampling a learning rate for each weight in the pre-classifier (while keeping the same Alrao method for the classifier layer).

In our experiments on LSTMs, per-weight learning rates sometimes perform well but are less stable and more sensitive to the interval (η min , η max ): for some intervals (η min , η max ) with very large η max , results with per-weight learning rates are a lot worse than with per-feature learning rates. This is consistent with the intuition above. ) for the first one, (10 -6 , 10 -1 ) for the second one, with 10 classifiers each. The first one is with ηmin = 10 -6 Each plot is averaged on 10 experiments. Exactly as with GoogLeNet model, optimization itself is efficient (for both intervals). For the interval with the smallest ηmax, the test loss does not converge and is very unstable. For the interval with the largest ηmax, the test loss diverges. As explained in the introduction, several works support the idea that not all units are useful when learning a deep learning model. Additional results supporting this hypothesis are presented in Figure 8 . We trained a GoogLeNet architecture on CIFAR10 with standard SGD with learning rate η 0 , but learned only a random fraction p of the features (chosen at startup), and kept the others at their initial value. This is equivalent to sampling each learning rate η from the probability distribution P (η = η 0 ) = p and P (η = 0) = 1 -p.

We observe that even with a fraction of the weights not being learned, the model's performance is close to its performance when fully trained.

When training a model with Alrao, many features might not learn at all, due to too small learning rates. But Alrao is still able to reach good results. This could be explained by the resilience of neural networks to partial training.

I INCREASING NETWORK SIZE:

As explained in Section 4, learning with Alrao reduces the effective size of the network to only a fraction of the actual architecture size, depending on (η min , η max ). We first tought that increasing the width of each layer was going to be necessary in order to use Alrao. However, our experiments show that this is not necessary.

Alrao and SGD experiments with increased width are reported in Figure 9 . As expected, Alrao with increased width has better performance, since the effective size increases. However, increasing the width also improves performance of standard SGD, by roughly the same amount.

Thus, width is still a limiting factor both for GoogLeNet and MobileNet. This shows that Alrao can perform well even when network size is a limiting factor; this runs contrary to our initial intuition that Alrao would require very large networks in order to have enough features with suitable learning rates. 9 : Increasing network width. We compare the performance of the GoogLeNet and MobileNet models trained on CIFAR10, to the same models with 3 times as many units in each layer, both for standard SGD and for Alrao.

J TUTORIAL:

In this section, we briefly show how Alrao can be used in practice on an already implemented method in Pytorch. The full code will be available once the anonymity constraint is lifted.

Finally, we can train the model. The only differences here with the usual training procedure is that each classifier needs to be updated as if it was alone, and that we need to update the model averaging weights, here the switch weights. 

:

With learning rates resampled at each time, each step would be, in expectation, an ordinary SGD step with learning rate Eη l,i , thus just yielding an ordinary SGD trajectory with more noise.

Figures and Tables:

Figure 1: Left: a standard fully connected neural network for a classification task with three classes, made of a pre-classifier and a classifier layer. Right: Alrao version of the same network. The single classifier layer is replaced with a set of parallel copies of the original classifier, averaged with a model averaging method. Each unit uses its own learning rate for its incoming weights (represented by different styles of arrows).

Figure2: Learning curves for SGD with various learning rates, Alrao, and Adam with its default setting, with the Resnet50 architecture on ImageNet and the MobileNetV2 architecture on CIFAR10. Left: training loss; right: test loss. While Alrao uses learning rates from the entire range, its performance is comparable to the optimal learning rate.

Figure 3: Performance of Alrao with a GoogLeNet model on CIFAR10, depending on the interval (η min , η max ). Left: loss on the train set; right: on the test set. Each point with coordinates (η min , η max ) above the diagonal represents the loss after 30 epochs for Alrao with this interval.Points (η, η) on the diagonal represent standard SGD with learning rate η after 50 epochs. Standard SGD with η = 10 2 is left blank to due numerical divergence (NaN). Alrao works as soon as (η min , η max ) contains at least one suitable learning rate.

Figure 4: Model averaging weights during training. During the training of the GoogLeNet model with Alrao on CIFAR10, 10 classifiers, with η min = 10 -5 and η max = 10 1 , we represent the evolution of the model averaging weights a j , depending on the corresponding classifier's learning rate.

Figure 5: Additional learning curves for SGD with various learning rates, Alrao, and Adam with its default setting, with the Densenet121 and Alexnet architectures on ImageNet and the GoogLeNet architecture on CIFAR10. Left: training loss; right: test loss.

Alrao-Adam with GoogLeNet on CIFAR10: Alrao-Adam compared with standard Adam with various learning rates. Alrao uses 10 classifiers and learning rates in the interval [10 -6 , 1]. Each plot is averaged on 10 experiments. We observe that optimization with Alrao-Adam is efficient, since train loss is comparable to the usual Adam methods. But the model starkly overfits, as the test loss diverges. Alrao-Adam with MobileNet on CIFAR10: Alrao-Adam with two different learning rate intervals, (10 -6 , 10 -2

Alrao-Adam with VGG19 on CIFAR10: Alrao-Adam on the interval [10 -6 , 1], with 10 classifiers. The 10 plots are 10 runs of the same experiments. While 9 of them do converge and generalize, the last one exhibits wide oscillations, both in train and test.

Figure 6: Alrao-Adam: Experiments with the VGG19, GoogLeNet and MobileNet networks on CIFAR10.

Figure 8: Loss of a model where only a random fraction p of the features are trained, and the others left at their initial value, as a function of p. The architecture is GoogLeNet, trained on CIFAR10.

Figure9: Increasing network width. We compare the performance of the GoogLeNet and MobileNet models trained on CIFAR10, to the same models with 3 times as many units in each layer, both for standard SGD and for Alrao.

Overall, our results with either SGD, Adam, or SGD-Alrao, are somewhat below the art: in part this is because we train on only 40,000 CIFAR samples, and do not use stepsize schedules.

Table content: <table><tr><td>MODEL</td><td/><td colspan="2">SGD WITH OPTIMAL LR</td><td colspan="2">ADAM -DEFAULT</td><td colspan="2">ALRAO</td></tr><tr><td/><td>LR</td><td>LOSS</td><td>TOP1 (%)</td><td>LOSS</td><td>TOP1 (%)</td><td>LOSS</td><td>TOP1 (%)</td></tr><tr><td>CIFAR10</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>MOBILENET</td><td>1e-1</td><td>0.37 ± 0.01</td><td>90.2 ± 0.3</td><td>1.01 ± 0.95</td><td>78 ± 11</td><td>0.42 ± 0.02</td><td>88.1 ± 0.6</td></tr><tr><td>GOOGLENET</td><td>1e-2</td><td>0.45 ± 0.05</td><td>89.6 ± 1.0</td><td>0.47 ± 0.04</td><td>89.8 ± 0.4</td><td>0.47 ± 0.03</td><td>88.9 ± 0.8</td></tr><tr><td>VGG19</td><td>1e-1</td><td>0.42 ± 0.02</td><td>89.5 ± 0.2</td><td>0.43 ± 0.02</td><td>88.9 ± 0.4</td><td>0.45 ± 0.03</td><td>87.5 ± 0.4</td></tr><tr><td>ImageNet</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>ALEXNET</td><td>1e-2</td><td>2.15</td><td>53.2</td><td>6.91</td><td>0.10</td><td>? (&lt; 2.87)</td><td>? (&gt; 38.0)</td></tr><tr><td>DENSENET121</td><td>1</td><td>1.35</td><td>69.7</td><td>1.39</td><td>67.9</td><td>1.41</td><td>67.3</td></tr><tr><td>RESNET50</td><td>1</td><td>1.49</td><td>67.4</td><td>1.39</td><td>67.1</td><td>1.42</td><td>67.5</td></tr><tr><td>RESNET50, WIDTH*3</td><td/><td/><td/><td>1.99</td><td>60.8</td><td>1.33</td><td>70.9</td></tr><tr><td>Penn Treebank</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>LSTM</td><td>1</td><td>1.566 ± 0.003</td><td>66.1 ± 0.1</td><td>1.587 ± 0.005</td><td>65.6 ± 0.1</td><td>1.67 ± 0.01</td><td>64.1 ± 0.2</td></tr></table>

Comparison between the number of parameters in models used without and with Alrao. LSTM (C) is a simple LSTM cell used for character prediction while LSTM (W) is the same cell used for word prediction.

Table content: <table><tr><td>MODEL</td><td colspan="2">NUMBER OF PARAMETERS</td></tr><tr><td/><td colspan="2">WITHOUT ALRAO WITH ALRAO</td></tr><tr><td>GOOGLENET</td><td>6.166M</td><td>6.258M</td></tr><tr><td>VGG</td><td>20.041M</td><td>20.087M</td></tr><tr><td>MOBILENET</td><td>2.297M</td><td>2.412M</td></tr><tr><td>LSTM (C)</td><td>0.172M</td><td>0.197M</td></tr><tr><td>LSTM (W)</td><td>2.171M</td><td>7.221M</td></tr></table>

Table 1 because the full training for Table 1 takes approximately 300 epochs.) H FROZEN FEATURES DO NOT HURT TRAINING

Table content: <table><tr><td/><td/><td colspan="2">test_nll as a function of p</td><td/><td/></tr><tr><td>1.6</td><td/><td/><td/><td/><td/></tr><tr><td>1.4</td><td/><td/><td/><td/><td/></tr><tr><td>1.2</td><td/><td/><td/><td/><td/></tr><tr><td>1.0</td><td/><td/><td/><td/><td/></tr><tr><td>0.8</td><td/><td/><td/><td/><td/></tr><tr><td>0.6</td><td/><td/><td/><td/><td/></tr><tr><td>0.0</td><td>0.2</td><td>0.4</td><td>0.6</td><td>0.8</td><td>1.0</td></tr></table>

We compute the gradient of all the model's weights loss.backward() # We reset all the classifiers gradients, and re-compute them with # as if their were the only output of the network. optimizer.classifiers_zero_grad() newx = net.last_x.detach() for classifier in net.classifiers(): loss_classifier = criterion(classifier(newx), targets) loss_classifier.backward() # Then, we can run an update step of the gradient descent. optimizer.step() # Finally, we update the model averaging weights net.update_switch(targets, catch_up=False)

Table content: <table><tr><td>def train(epoch):</td></tr><tr><td>for batch_idx, (inputs, targets) in enumerate(trainloader):</td></tr><tr><td># We update the model averaging weights in the optimizer</td></tr><tr><td>optimizer.update_posterior(net.posterior())</td></tr><tr><td>optimizer.zero_grad()</td></tr><tr><td># Forward pass of the Alrao model</td></tr><tr><td>outputs = net(inputs)</td></tr><tr><td>loss = nn.NLLLoss(outputs, targets)</td></tr><tr><td>#</td></tr></table>

Peer review (iclr2019):
 POST REBUTTAL: I think the paper is decent, there are some significant downsides to the method but it could constitute a first step towards a more mature learning-rate-free method. However, in its current state the paper is left with some gaping holes in its experiment section. The authors tried to add experiments on Imagenet, but these experiments apparently didn*t finish before the end of the rebuttal period. For that reason, the paper probably should not be accepted for publication (even if the authors manage to finish running these experiments, we would not have a chance to review these results). ------ Original review ------ In this paper, the authors present a method for training deep networks with randomly sampled feature-wise learning rates, removing the need for fixed learning rates and their tuning. The method is shown to perform comparatively to SGD with a learning rate roughly optimized with regards to validation performance. The method applies to the most popular types of deep learning architectures, which includes fully connected layers, convolutional layers and recurrent cells. Quality: The paper is of a decent quality in general, I noticed no glaring omissions while reading the paper. However, I do worry that the method provides little gain for a lot of work. It is becoming more and more easy to tune the learning rate of deep learning models with strategies such as early stopping, and this method comes at a high cost for models with a big final layer. Clarity: The paper is well written, but the reader is often (too often?) sent to the Appendix, which is itself ordered in a strange way (e.g., the first reference to the Appendix in the paper refers to Appendix F?). If some sections of the Appendix are not needed, I would remove them. Originality: The work is original in the approach, i.e. randomization as a way to get rid of learning rates is a novel method. However, there was one work presented last year at NIPS which concerns itself with the same problem, which is getting rid of learning rates: “Training Deep Networks without Learning Rates Through Coin Betting” by Francesco Orabona and Tatiana Tommasi, NIPS, 2017. They don’t compare on the same methods and the same datasets, but I think the authors should be aware of this work and perhaps compare themselves with it. The work takes a very different approach to solve the problem so I don’t think it’s an issue for this paper. Significance: I think the work is important, in that it adds another tool to solve the learning rate problem. I would not say it is likely to have a very high impact, because it involves a lot of work, for little benefit. Furthermore, the cost of reproducing multiple times the last layer of the network will be prohibitive in many cases for NLP. The method feels ad-hoc in many respects, and there are no guarantees that it would work any better than Adam does on pathological cases. Perhaps some mathematical analysis on simpler problems would help make the contributions stronger. The authors state that the learning rate range has little impact on performance, yet it still has enough impact to justify tuning it for different models and datasets (on CIFAR it is 10^-5 to 10^1, on Pennbank it is 10^-3 to 10^2). I would tend to agree that the alrao method is more robust to the choice of learning rate than plain SGD, however the fact of the matter is that there are still parameters to tune. Figure 5. also seems to suggest that the range is important, although the models were not trained until the end, so it is not clear. Some additional comments: Nitpicking: In Section 2, most sub-sections (or paragraphs titles?) have the name of the method in them. That’s redundant. Instead of “Alrao principle”, “Alrao update”, etc., just write “Principle.”, “Update.”. Is there a justification for using the same learning rate for all weights in an LSTM unit? I believe there is a mistake in Equation 2. The denominator should be log(.eta_{max}) - log(.eta_{min}) [second paragraph on page 4.] Once again nitpicking for the sake of clarity: “For each classifier Cθ cl j, we set a learning rate log eta_j = …” this reads as if the learning rate would be set to log eta_j, but you probably mean you will set the learning rate to eta_j = exp(...). Figure 5b in the appendix does not specify which curve has which learning rate interval.