Year: 2018

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.

text: 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.

heading: 1 INTRODUCTION
text: 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 (Massé 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., (LeCun 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.

heading: 2 ALL LEARNING RATES AT ONCE: DESCRIPTION
text: 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:
θl,i ← θl,i − ηl,i · ∇θl,i`(Φθ(x), y) (1) 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 = {(x1, y1), ..., (xN , yN )}, with yi ∈ {1, ...,K}, be a classification dataset. The goal is to predict the yi given the xi, 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: 1N ∑ i `(Φθ(xi), yi).
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 classifier layer Cθcl with K categories is defined by Cθcl = softmax ◦ ( WTx+ b ) with θcl = (W, b),
and softmax(x1, ..., xK)k = exk/( ∑ 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:
CAlraoθcl (z) := Ncl∑ j=1 aj Cθclj (z), Φ Alrao θ (x) := C Alrao θcl (φθpc(x)) (2)
where the Cθclj are copies of the original classifier layer, with non-tied parameters, and θ cl := (θcl1 , ..., θ cl Ncl
). The aj are the parameters of the model averaging, and are such that for all j, 0 ≤ aj ≤ 1, and ∑ j aj = 1. These are not updated by gradient descent, but via a model averaging method from the literature (see below).
For each classifier Cθclj , we set a learning rate ηj defined by log ηj = log ηmin + j−1 Ncl−1 log ( ηmax ηmin ) , so that the classifiers’ learning rates are log-uniformly spread on the interval [ηmin, ηmax]. 1With 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.
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:
θl,i ← θl,i − ηl,i · ∇θl,i`(ΦAlraoθ (x), y) (3)
• The parameters θclj of each classifier clone j on the classifier layer are updated as if this classifier alone was the only output of the model:
θclj ← θclj − ηj · ∇θclj `(Cθclj (φθpc(x)), y) (4)
(still sharing the same pre-classifier φθpc ). This ensures classifiers with low weights aj still learn, and is consistent with model averaging philosophy. Algorithmically this requires differentiating the loss Ncl times with respect to the last layer (but no additional backpropagations through the preclassifier).
• To set the weights aj , 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 (aj) 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 withNcl classifiers and learning rates in [ηmin, ηmax] 1: aj ← 1/Ncl for each 1 ≤ j ≤ Ncl . Initialize the Ncl model averaging weights aj 2: ΦAlraoθ (x) := ∑Ncl j=1 aj Cθclj (φθ
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 ≤ Ncl do 6: Define log ηj = log ηmin + j−1Ncl−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: zt ← φθpc(xt) . 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θ (xt), yt) . Update the pre-classifier weights 11: for all Classifier j do 12: θclj ← θclj − ηj · ∇θclj `(Cθclj (zt), yt) . Update the classifiers’ weights 13: a← ModelAveraging(a, (Cθcli (zt))i, yt) . Update the model averaging weights. 14: t← t+ 1 mod N

heading: 3 EXPERIMENTS
text: We tested Alrao on various convolutional networks for image classification (Imagenet and CIFAR10), 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 ImageNet (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.
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.
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.

heading: 4 LIMITATIONS, FURTHER REMARKS, AND FUTURE DIRECTIONS
text: 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.

heading: 5 CONCLUSION
text: 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.

heading: A MODEL AVERAGING WITH THE SWITCH
text: 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 aj are chosen in Alrao.
Assume that we have a set of prediction strategies M = {pj , j ∈ I}. We define the set of switch sequences, S = {((t1, j1), ..., (tL, jL)), 1 = t1 < t2 < ... < tL , j ∈ I}. Let s = ((t1, j1), ..., (tL, jL)) be a switch sequence. The associated prediction strategy ps(y1:n|x1:n) uses model pji on the time interval [ti; ti+1), namely
ps(y1:i+1|x1:i+1, y1:i) = pKi(yi+1|x1:i+1, y1:i) (5)
where Ki is such that Ki = jl for tl ≤ i < tl+1. We fix a prior distribution π over switching sequences. In this work, I = {1, ..., NC} the prior is, for a switch sequence s = ((t1, j1), ..., (tL, jL)):
π(s) = πL(L)πK(j1) L∏ i=2 πT (ti|ti > ti−1)πK(ji) (6)
with πL(L) = θ L 1−θ a geometric distribution over the switch sequences lengths, πK(j) = 1 NC
the uniform distribution over the models (here the classifiers) and πT (t) = 1t(t+1) .
This defines a Bayesian mixture distribution: psw(y1:T |x1:T ) = ∑ s∈S π(s)ps(y1:T |x1:T ) (7)
Then, the model averaging weight aj for the classifier j after seeing T samples is the posterior of the switch distribution: π(KT+1 = j|y1:T , x1:T ).
aj = psw(KT+1 = j|y1:T , x1:T ) = psw(y1:T ,KT+1 = j|x1:T )
psw(y1:T |x1:T ) (8)
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.

heading: B CONVERGENCE RESULT IN A SIMPLE CASE
text: 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 θclj (there is no more ambiguity since the pre-classifier is fixed).
The loss of some classifier C on a dataset with features (xi) and labels (yi) is L(C) := 1 N ∑ i `(C(xi), yi), where for each input xi, (C(xi)y)y∈Y is a probability distribution over the possible labels y ∈ Y , and we use the log-loss `(C(xi), yi) := − logC(xi)yi . For a classifier Cθ with parameter θ, let us abbreviate L(θ) := L(Cθ). We assume that L(θ) is a non-negative convex function, with ∇2L(θ) λ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 θ∗: ∇2L(θ∗) 0. The Alrao architecture for such a classifier Cθ uses Ncl copies of the same classifier, with different parameter values:
ΦAlraoθAlrao(x) = Ncl∑ j=1 ajCθj (9)
where θAlrao := (θ1, ..., θNcl), and where the (aj)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
θ (t+1) j = θ (t) j − ηj∇L(θ (t) j ) (10)
a(t+1) = ModelAveraging(a(t), (Cθi(x1:N ))i, y1:N ) (11)
We assume that the model averaging method is Bayesian Model Averaging.
We have assumed that the Hessian of the loss of the model satisfies ∇2L(θ) λ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,
A := j ∈ J such that ∑ t≥0 ( L(θ (t) j )− L ∗ ) <∞  , (13) B :=
j ∈ J such that ∑ t≥0 ( L(θ (t) j )− L ∗ ) =∞  (14) and in particular, for any j ∈ A, limt L(θ(t)j ) = L∗. The proof is organized as follows: We first show that A is not empty. Then, we show that limt→∞ 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 thatA 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 MarchettiBowick, 2013)), namely, the loss (L(θ(t)j ))t converges to L ∗. Moreover, since L is localy stricly convex around θ∗, this implies that limt θ (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 ∇2L(θ∗) µI . Since L is C2, there is ε′ such that for any θ such that ‖θ − θ∗‖≤ ε′, then ∇2L(θ) µ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− γ (16)
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, limt→∞ a (t) j = 0. Let j ∈ B and take some i ∈ A. In Bayesian model averaging, the weights are
a (t) j =
∏t s=1 pθ(s)j
(y1:N |x1:N )∑ k ∏t s=1 pθ(s)k (y1:N |x1:N ) (17)
≤ t∏
s=1
p θ (s) j
(y1:N |x1:N )
p θ (s) i
(y1:N |x1:N ) (18)
= t∏ s=1 exp(−NL(θ(s)j )) exp(−NL(θ(s)i )) (19)
= exp ( −N
t∑ s=1 ( L(θ (s) j )− L ∗ ) +N t∑ s=1 ( L(θ (s) i )− L ∗ ))
(20)
Since i ∈ A and j ∈ B, by definition of A and B this tends to 0. Therefore, limt a(t)j = 0 for all j ∈ B.
We now prove the statement of the theorem. We have:
L(θ (t) Alrao) =
1
N ∑ i − log ∑ j∈A aje −`(C θ (t) j (xi),yi) + ∑ j∈B aje −`(C θ (t) j (xi),yi)  (21) ≤ 1 N ∑ i − log ∑ j∈A aje −`(C θ (t) j (xi),yi)
 (22) For all i ∈ A, set ã(t)i := a (t) i∑
j∈A a (t) j
= a (t) i 1− ∑ j∈B a (t) j . Then
L(θ (t) Alrao) ≤ − log 1−∑ j∈B a (t) j + 1 N ∑ i − log ∑ j∈A ãje −`(C θ (t) j (xi),yi)  (23) ≤ 1 N ∑ i ∑ j∈A ãj`(Cθ(t)j (xi), yi) + o(1) (24)
= ∑ j∈A ãjL(θ (t) j ) + o(1) (25) = L∗ + o(1) (26)
thanks to Jensen’s inequality for − log, then because limt a(t)j = 0 for j ∈ B, and finally because limt 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.

heading: C EVOLUTION OF THE POSTERIOR
text: 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 = 101.
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 aj 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.

heading: D ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
text: In the case of CIFAR-10, we normalize each input channel xi (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 (x1, x2, x3) 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.

heading: E ALRAO WITH ADAM
text: 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.

heading: F NUMBER OF PARAMETERS
text: 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 (Ncl − 1) × K × d where Ncl 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.

heading: G SAMPLING A LEARNING RATE PER WEIGHT
text: 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.
0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0 epochs
0.0
0.5
1.0
1.5 2.0 lo ss
Loss train alrao-adam adam lr=1e-05 adam lr=1e-04 adam lr=1e-03 adam lr=1e-02
0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0 epochs
0.0
0.5
1.0
1.5
2.0
lo ss
Loss test
(a) 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.
0 10 20 30 40 epochs
0.0
0.5
1.0
1.5
2.0
lo ss
Loss train alrao alrao
0 10 20 30 40 epochs
0.0
0.5
1.0
1.5 2.0 lo ss
Loss test
(b) Alrao-Adam with MobileNet on CIFAR10: Alrao-Adam with two different learning rate intervals, (10−6, 10−2) for the first one, (10−6, 10−1) for the second one, with 10 classifiers each. The first one is with ηmin = 10−6Each 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.
0 10 20 30 40 50 epochs
0.0
0.5
1.0
1.5
2.0
lo ss
Loss train
0 10 20 30 40 50 epochs
0.0
0.5
1.0
1.5
2.0
lo ss
Loss test
(c) 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.

heading: H FROZEN FEATURES DO NOT HURT TRAINING
text: 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.

heading: J TUTORIAL
text: 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.
The first step is to build the preclassifier. Here, we use the VGG19 architecture. The model is built without a classifier. Nothing else is required for Alrao at this step.
class VGG(nn.Module): def __init__(self, cfg):
super(VGG, self).__init__() self.features = self._make_layers(cfg) # The dimension of the preclassier’s output need to be specified. self.linearinputdim = 512
def forward(self, x): out = self.features(x) out = out.view(out.size(0), -1) # The model do not contain a classifier layer. return out
def _make_layers(self, cfg): layers = [] in_channels = 3 for x in cfg:
if x == ’M’: layers += [nn.MaxPool2d(kernel_size=2, stride=2)] else: layers += [nn.Conv2d(in_channels, x, kernel_size=3, padding
=1), nn.BatchNorm2d(x), nn.ReLU(inplace=True)]
in_channels = x layers += [nn.AvgPool2d(kernel_size=1, stride=1)] return nn.Sequential(*layers)
preclassifier = VGG([64, 64, ’M’, 128, 128, ’M’, 256, 256, 256, 256, ’M’, \ 512, 512, 512, 512, ’M’, 512, 512, 512, 512, ’M’])
Then, we can build the Alrao-model with this preclassifier, sample the learning rates for the model, and define the Alrao optimizer
# We define the interval in which the learning rates are sampled minlr = 10 ** (-5) maxlr = 10 ** 1
# nb_classifiers is the number of classifiers averaged by Alrao. nb_classifiers = 10 nb_categories = 10
net = AlraoModel(preclassifier, nb_categories, preclassifier. linearinputdim, nb_classifiers)
# We spread the classifiers learning rates log-uniformly on the interval. classifiers_lr = [np.exp(np.log(minlr) + \
k /(nb_classifiers-1) * (np.log(maxlr) - np.log(minlr)) \ ) for k in range(nb_classifiers)]
# We define the sampler for the preclassifier’s features. lr_sampler = lr_sampler_generic(minlr, maxlr) lr_preclassifier = generator_randomlr_neurons(net.preclassifier,
lr_sampler)
# We define the optimizer optimizer = SGDAlrao(net.parameters_preclassifier(),
lr_preclassifier, net.classifiers_parameters_list(), classifiers_lr)
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.
def train(epoch): for batch_idx, (inputs, targets) in enumerate(trainloader):
# We update the model averaging weights in the optimizer optimizer.update_posterior(net.posterior()) optimizer.zero_grad()
# Forward pass of the Alrao model outputs = net(inputs) loss = nn.NLLLoss(outputs, targets)
# 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)

Review summaries:
In this paper the authors propose a method called “All learning rates at once” (Alrao) which aims to save the time needed to tune learning rate for DNN models testing. The method sets individual learning rate to each feature in each layer of a network using the values sampled from truncated log-uniform distribution. The only cost of the method is the creation of several branches of the classifier layer. Each of the branches is trained with a predefined learning rate value, and the final predictions are obtained by model averaging. In the presented experiments Alrao demonstrates performance comparable to SGD with optimal learning rate and more stable results compared to Adam. The authors indicate limitations of Alrao caused by the overhead in the final layer which complicates the application of the method for models with large classifier layer.