Non-greedy Gradient-based Hyperparameter Optimization Over Long Horizons
Authors: Paul Micaelli
Amos Storkey
Venue:  (2021)
Keywords: Hyperparameter optimization
Meta-learning

Abstract: Gradient-based meta-learning has earned a widespread popularity in few-shot learning, but remains broadly impractical for tasks with long horizons (many gradient steps), due to memory scaling and gradient degradation issues. A common workaround is to learn meta-parameters online, but this introduces greediness which comes with a significant performance drop. In this work, we enable non-greedy meta-learning of hyperparameters over long horizons by sharing hyperparameters that are contiguous in time, and using the sign of hypergradients rather than their magnitude to indicate convergence. We implement this with forward-mode differentiation, which we extend to the popular momentum-based SGD optimizer. We demonstrate that the hyperparameters of this optimizer can be learned non-greedily without gradient degradation over $\sim 10^4$ inner gradient steps, by only requiring $\sim 10$ outer gradient steps. On CIFAR-10, we outperform greedy and random search methods for the same computational budget by nearly $10\%$. Code will be available upon publication.

Under review as a conference paper at ICLR 2021
NON-GREEDY GRADIENT-BASED HYPERPARAMETER OPTIMIZATION OVER LONG HORIZONS
Anonymous authors
Paper under double-blind review
ABSTRACT
Gradient-based meta-learning has earned widespread popularity in few-shot deep learning, but remains broadly impractical for tasks with long horizons (many gradient steps), due to memory scaling and gradient degradation issues. A com- mon workaround is to learn meta-parameters online, but this introduces greediness which comes with significant performance drop. In this work, we enable non- greedy meta-learning of hyperparameters over long horizons by sharing hyperpa- rameters that are contiguous in time, and using the sign of hypergradients rather than their magnitude to indicate convergence. We implement this with forward- mode differentiation, which we extend to the popular momentum-based SGD op- timizer. We demonstrate that the hyperparameters of this optimizer can be learned non-greedily without gradient degradation over ~ 10 inner gradient steps, by only requiring 10 outer gradient steps. On CIFAR-10. 10, we outperform greedy and random search methods for the same computational budget by nearly 10%. Code will be available upon publication.
INTRODUCTION
Deep neural networks have shown tremendous success a wide range of applications, including classification (He et al., 2016). generative models (Brock et al. 2019), natural language processing (Devlin al., (2118) and speech recognition (Oord al. (016)). This success
part due to
effective optimizers such as SGD with momentum or Adam (Kingma & Ba 2015), which require carefully tuned hyperparameters for each application. In recent years, a long list of heuristics to tune such hyperparameters has been compiled by the deep learning community, including things like: how best decay the learning rate (Loshchilov Hutter (207)). how to scale hyperparameters with the budget available (Li et al. 2020). and how to scale learning rate with batch size (Goyal et al.) 2017). Unfortunately these heuristies are often dataset specific and architecture dependent (Dong et al.
2020j, and must constantly evolve to accommodate new optimizers (Loshchilov & Hutter, or new tools, like batch normalization which allows for larger learning rates and smaller weight decay (Ioffe & Szegedy 2015).
2019
With so many ways to choose hyperparameters, the deep learning community is at risk of adopting models based how much effort went into tuning them, rather than their methodological insight. The field of hyperparameter optimization (HPO) aims to find hyperparameters that provide a good generalization performance automatically. Unfortunately, existing tools rather unpopular for deep networks, largely owing to their inefficiency. Here we focus on gradient-based HPO, which calculates hypergradients, i.c. the gradient of some generalization loss with respect each hyperpa- rameter. Gradient- HPO should be more efficient than black box methods as the dimensionality of the hyperparameter space increases, since it relies on gradients rather than trial and error. prac- tice however, learning hyperparameters with gradients has only been popular in few-shot learning tasks where the horizon short. This is because long horizons cause hypergradient degradation, and incur memory cost that makes reverse-mode differentiation prohibitive. Greedy alternatives allevi- ate both of these issues, but come at the cost of solving hyperparameters locally instead of globally. forward-mode differentiation has been shown to offer memory cost constant with horizon size, but it doesn't 't address gradient degradation and only scales to few hyperparameters, which has limited its to the greedy setting well.

---

Under review as a conference paper at ICLR 2021
0.5
0.30
0.25
0:4
beet anc 18
stegs
0.3
0..1
0.10
Ours
ITD (groedy)
0.0
0.00
40
20
40
20
40
epochs
epochs
epochss
epochs
Our method applied the SGD optimizer learn (from left right) the learning rate schedule a. the momentum B, and weight decay for a WRN-16-1 on CIFAR-10. For each outer step (color) we solve CIFAR- 10 from scratch for 50 epochs, and update all hyperparameters such that the final weights minimize some validation loss. We use hyperparameter sharing over 10, 50 and 50 epochs for a, ,3 and l respectively. All hyperparameters are initialized to zero and converge within just 10 outer steps to values that significantly outperform the online greedy alternative (Baydin et al.) 2018), and match aggressively hand-tuned baselines for this setting (see Section 5.2)
Figure 1:
To the best of our knowledge, this work demonstrates for the first time that gradient-based HPO can be applied for long horizon problems like CIFAR-10 without being greedy. Specifically, make the following contributions: (1) we propose to share hyperparameters through time and show that this significantly reduces the variance of hypergradients, (2) we show that the sign of hypergradients is a better indicator of convergence than their magnitude and enables small number of outer steps, (3) we combine the above in a forward- mode algorithm adapted to modern SGD optimizers with momentum and weight decay, and (4) we show that our method significantly outperforms random search and greedy alternatives when used with the same computational budget.
RELATED WORK
There many ways to perform hyperparameter optimization (HPO), including Bayesian optimiza- tion (Snoek et al. 2015), reinforcement learning (Zoph & Le 2017). a mix of the two (Falkner et al,, 2018). evolutionary algorithms (Jaderberg al. 2017) and gradient-based methods (Bengio (0000) Here we focus on the latter, but a comparison of HPO methods can be found in (Feurer & Hut- ter| 2019). Modern work in meta-learning deals with various forms of gradient-based HPO, many
examples of which are discussed in this survey (Hospedales et al., (020). However, meta-learning
typically focuses on the sew- regime where horizons are conveniently short, while in this work we focus on long horizons.
Gradient-based HPO. Using the gradient of some validation loss with respect the hyperparam- eters is typically the preferred choice when the underlying optimization is differentiable. This is type of bilevel optimization (Franceschi al. 2018) which stems from earlier work on backprop- agation through time (Werbos) 1990) and real-time recurrent learning (Williams & Zipser 1989), Unfortunately, differentiating optimization is an expensive procedure both time and memory, and most proposed methods are limited to small models and toy datasets (Domke 2012 Maclaurin et al., 2015 Pedregosa, 2016). Efforts to make the problem more tractable include optimization shortcuts (uu et al. 2016)) truncation (Shaban et al. (2099) and implicit gradients (Rajeswaran et al.) 2019) Lorraine et al. 2019). Truncation can be combined with our approach but produces biased gradients (Metz et al.) 2019). while implicit differentiation is only applicable to hyperparameters that define the training loss (e.g. augmentation) but not to hyperparameters that define how the training loss minimized (e.g. optimizer hyperparameters). Forward-mon mode differentiation (Williams & Zipser 1989) boasts memory cost constant with horizon size, but it doesn't it address gradient degradation which has restricted its use to the greedy setting (Franceschi et al. 2017).
2

---

Under review as a conference paper at ICLR 2021
Greedy Methods. One trick that prevents gradient degradation and significantly reduces compute and memory cost is to solve the bilevel optimization greedily. This has become the default trick in various long-horizon problems, including HPO over optimizers (Luketina et al., 2016, Franceschil eet al. 2017 Baydin et al., 2018 Donini et al. 2019). architecture search (Liu et al. 2019), dataset curriculum learning (Ren et. 2018). Greediness refers finding
distillation WWag et al. 2018) the best hyperparameters locally rather than globally. In practice, it involves splitting the inner opti- mization problem into smaller chunks (often just one batch), and solving for hyperparameters over these smaller horizons instead; often in an online fashion. In this paper we expand upon previous observations (Wu et al. 2018) and take the view that greediness fundamentally solves for the wrong objective. Instead, the focus of our paper is to extend forward-mode differentiation methods to the non-greedy setting.
Gradient Degradation. Gradient degradation of some scalar w.r.t parameter is a broad issue that arises when that parameter influences the scalar in a chaotic fashion, such as through long chains of nonlinear mappings. This manifests itself in HPO as vanishing or exploding hypergradients. due to low or high curvature components of the validation loss surface respectively. This leads to hypergradients with large variance, which we denote as hypervariance (more in Section [ and which prevents long-hone horizon optimization. This is usually observed in the context of recurrent neural networks (Bengio et al. 1993; 1994). but also in reinforcement learning (Parmas et al. 2018) and HPO (Maclaurin et al.) 2015). Solutions like LSTMs (Hochreiter & Schmidhuber, 1997) and gradient clipping (Pascanu et al., 2013) have been proposed, but are respectively inapplicable and insufficient to our problem. Variational optimization (Metz et al., 2019) and preconditioning warp- layers (Flennerhag et al. 2020) can mitigate gradient degradation, but these methods are expensive in memory and therefore are limited to small architectures and/or few hundred inner steps. In comparison, we differentiate over ~ 10 inner steps for Wide ResNets (Zagoruyko & Komodakis, 2016).
BACKGROUND
3.1
PROBLEM STATEMENT
Consider a neural network with weights 0, trained to minimize a loss Lerein over dataset 'D Drrains with a gradient-based optimizer & 0c+1 (0, (Aoo:=11) Ate)). Here E RKXT hyperpa- rameter matrix, with K the number of hyperparameters used per step (c.g. 2 if learning momentum and learning rate), and T the total number of update steps. Throughout this paper we write column indices in brackets to differentiate them from a variable evaluated at time t.
We would like find X such that the minimizer of Lerain. namely 0 (A). also minimizes some generalization loss Leat on a validation dataset Dentt Bilevel optimization (Stackelberg 1952) the usual framework to express this problem:
X = arg min Leat Loar (A)( Deal)
(1)
subject to OT = arg min Ctrain(O. Derain)
(2)
solved with i 0 (0: Aqy)
(3)
The inner loop (lower level) in Eq expresses constraint on the outer loop (upper level) in Eq [ In gradient-based HPO, our task is to compute the hypergradient dlCatt/d and update À accordingly. The horizon H refers to the number of update steps taken in the inner loop (to optimize 0) before one step is taken in the outer loop (to optimize
A). When solving Eq non-greedily we have H = T. However, most modern approaches are greedy: they rephrase the above problem into sequence of several independent problems of smaller horizons, where (1 is learned in the outer loop subject to an inner loop optimization from O, to 0,4H with H < T. Despite its popularity, we argue against greediness in Section 4
3

---

Under review as a conference paper at ICLR 2021
3.2 FORWARD-MODS DIFFERENTIATION OF MODERN OPTIMIZERS
In modern gradient-based HPO, reverse-mode differentiation is used in the inner optimization prob- lem (Eq 2 optimize 0. However, the memory cost of using it for the outer optimization (Eq is ((FH) where F is the memory cost of one forward pass through the network (weights plus acti- vations). This is extremely limiting: for large networks, only H 10 could be solved with modern GPUs, while problems like CIFAR- require И ~ 10 Instead, we must use forward-mot differ- entiation, which scales memory as O DDDN), where D is the number weights and N is the number of learnable hyperparameters. The additional scaling with N is limitation in many applications, conveniently allows for smaller values N.
but sharing hyperparameters (Section 4
In this section we give background on forward-mode differentiation of hyperparameters, and ex- tend it to the most popular optimizer, namely SGD with momentum and weight decay. To the best of our knowledge, previous work focuses simpler versions of this optimizer, usually by removing momentum and weight decay, and only learns the learning rate, greedily.
First, we use the chain rule to write:
d&Caal dX
DLual d0T
00, dA
Note that the direct gradient has been dropped since eLeat /0x = 0 for optimizer hyperparameters. The first term on the RHS is trivial and can be obtained with reverse-mode differentiation as usual.
The second term is more problematic because 0r = 0r (0--2-)))) (rr))))))2))) App-1)) We use the chain rule again to calculate this term recursively:
d0, yx
a0,
d
a0,
which we write
Z: = A. + B,
(5)
00,
1-1
0X
where Ze E RDxN, A. E RDxD and B, E RDxN, We use Pytorch's 's update rule for SGD Paszke ct al. 2019), with learning rate at, momentum Be. weight decay be and velocity v;:
0, = - - av where 8, = 3 + (0Crrain/00:-) + 1:01-1
(6)
Now let us consider the case where we learn the learning rate schedule, namely X a. we use the update rule without momentum (Donini et al.) 2019). B, is conveniently sparse: it is a D x N matrix that only has one non-zero column corresponding to the hyperparameters used step i.e. However we introduce momentum and therefore the velocity depends on the hyperparameters of previous steps. A further recursive term C, = (0v,/A>) must now be considered get exact hypergradients. Putting it together (see Appendix A) we obtain:
182 Ltrain
A = DxD -at
+ 111 DXD
00%-1
ILtrain
B = B.ar - -8p 8PxN B
+ 140=-1
a0,-1
02 Lerain
C = 3.C
[111DD +
Z
002_1
where 8.xN(g) turns vector q of size into zero matrix of size D N where the column corresponding to the hyperparameter used at step t is set to q. A similar technique can be applied to momentum and weight decay to get - and Z (Appendix A). The first-order approximation of the above system corresponds to setting the Hessian to zero, but in practice we find it too crude of an approximation for large horizons. All hypergradient derivations in this paper were thoroughly checked with finite differences. Finally, note that the approach above can extended to any dif- ferentiable hyperparameter. In particular, other optimizers like Adam (Kingma & Ba 2015) simply have different Z,, At and B, matrices.
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Non-gree -reedyyedy learning of the learning rate schedule a, using forward-mode differ- entiation with hyperparameter sharing and sign-based outer optimizer.
for o in 1, do
initialize: Dtrain. vval. 0 E IR, a= 0%a 2 = 0DxNs, aa=00==000 = =0DNN, ya RNo
for in ..., H do
Etrain, ytroin Drrain
Stroin itrain (Itrain Mtroin) /
if truncate==False then
HZ = =0(grran 2 //0 za = A a + Ba
(Eq)
update and v (Eq
Ival = 0Lvat (DeallDeall) /00
8, sgn )
// hypergradient signs
for n in 2, ......... Na do
if 8 in # [,]] then
|n| f- mm)
α + a 8n O y
ENABLING NON-GREEDINESS
Greedy approaches (Luketina et al. 2016 Franceschi et al. 2017 Baydin et al. 2018 Donini al., 2019) have many advantages: they mitigate gradient degradation issues, lower training time, and require less memory in eovere-mode differentiation. However, these methods look for X that does well locally rather than globally, i.c. they constrain A to a subspace solutions such that 0H 0 -...
1..0..... Of all yield good validation performances. In the way that running marathon by optimizing for sequence of 100m sprints is sub optimal, greediness is poor proxy to minimize (va((O)) In our experiments, we found that getting competitive hyperparameters with greediness often revolves around tricks such as online learning with very low outer learning rate combined with hand-tuned initial hyperparameter values, to manually prevent convergence small values. But solving the greedy objective correctly leads to poor solutions, a special case of which was previously described as the ishort-horizon bias" (Wu al., 2018) when learning the learning rate. Finally, we found that most of the greedy literature uses the test set as the validation set, which creates risk of meta-overfitting to the test set. Throughout this work, we carve out validation set from our training set instead.
The main challenge of doing non-greedy bilevel optimization over long horizons is gradient degra- dation. In HPO this arises because small change in the state of the network inner step ć can cascade forward into a completely different weight trajectory given enough subsequent steps, yield- ing very different hypergradients. We refer to this phenomenon as hypervariance, and quantify it in Section 5.1
Hyperparameter Sharing. One way to iron out this hypervariance would take many outer steps on the hyperparameters, with previous work suggesting that few thousands would be re- quired (Wu al. 2018). But since each outer step requires computing the entire inner problem, this is intractable. Instead, we propose to the long horizon our advantage and average out hypergradients through inner steps rather than outer steps. This is equivalent to hyperparameter sharing: learning hyperparameter for several contiguous steps in the inner loop. Assuming that contiguous steps have hypergradients drawn from the same distribution, the average hypergradient more stable, since it is less likely to reflect single batch in the inner loop. The key to this solution
5

---

Under review as a conference paper at ICLR 2021
being effective is that it gets better degradation gets worse: the larger the horizon, the more noisy individual hypergradients become, but the more samples are included in the average hypergradient, and the less noisy the average hypergradient becomes. Assuming contiguous hypergradients are drawn from the same distribution, the standard error their mean will scale as 1/yn.
Convergence From Hypergradient Signs. While hyperparameter sharing produces stable hyper- gradients with reasonable range (see Appendix C), reaching zero hypergradients and thus conver- gence remains difficult, and often requires a large number outer steps. We propose to use the sign of hypergradients an indicator of convergence instead of their magnitude. More specifically, update hyperparameters with positive (negative) hypergradients by an amount +- ( (-7). and yy is de- cayed by factor of 2 every time the corresponding hypergradient changes sign across consecutive outer steps. This allows for convergence after hypergradients have changed signs few times, and find this much more robust than using modern optimizers to update À like Adam. This has the added benefit of letting the user define the range of hyperparameter search more explicitly, rather than having it implicitly defined by the magnitude of hypergradients.
Putting it all together, Algorithm I shows how to learn a schedule of No learning rates efficiently. Hyperparameter sharing is implemented by reusing the same Za columns for several consecutive inner steps. The most expensive part per outer step is to compute the Hessian matrix product H each inner step We can adapt the work of (Shaban et al.] 2019) to forward mode differentiation by truncating alternating steps. We could also use functional forms for more complex schedules to learned in terms of fewer hyperparameters, which would cheapen the calculation of HZa. However, this typically results in including stronger inductive bias about the general shape of each hyperparameter schedule, which can easily cloud the true performance of HPO algorithms. In practice,
similar form to Algorithm to learn the learning rate, momentum and weight decay jointly.
5 EXPERIMENTS
In Section 5.1 we quantify gradient degradation and show that non-greediness increases it while hyperparameter sharing significantly reduces In Section [5.2] we show that our method allows for stable non-greedy HPO on 3 datasets, and outperforms several other methods when used with the same computational budget. Implementation details for each of our experiments can be found in Appendix B.
5.1 REDUCING GRADIENT DEGRADATION
Gradient degradation in the context of HPO over long horizons isn't well understood. In this section we propose simple metric to quantify this degradation (hypervariance), and we propose method to reduce it (hyperparameter sharing). We also consider the fluctuation of the sign of the hypergradients to motivate the use of the outer optimizer described in Section 4
Hypervariance Definition. Consider the hypergradients of the learning rates a. These are af- fected by four main factors: the training data, the validation data, the weights' initialization Og and the current learning rate schedule Ogg. We can slightly perturb each factor individually P times while keeping all others constant. This gives for each hyperparameter, which should have low variance order for the outer optimization to be stable. We define the hypervariance to be (unitless) inverse signal to noise ratio, namely the ratio of the standard deviation to the mean of hypergradients, computed for each hyperparameter. This makes the norm of the hypergradients irrelevant, which is desired since it always be scaled as needed with some outer learning rate in practice.
distribution of hypergradients around fixed point
Hypergradient Sign Fluctuation. Section f we made the case for using the sign of hyper- gradients alone. Since hypervariance doesn't capture the fluctuation in the sign of hypergradients, we also measure this quantity by looking at the smallest quantity between P. and P_, the number of positive and negative signs, expressed ratio: sign fluctuation min P+/P) P). This quantity is capped at 50% which corresponds to hypergradients maximally uninformative regarding whether or not some hyperparameter should increase or decrease.

---

the first to Under review as a conference paper at ICLR 2021
D train
D
0
hypervariance
3-
sign fucetaaiinn (96)
Greedy
Non- Kon-greody
Ours
150
300
150
300
150
300
150
300
steps
steps
steeps
steeps
Figure 2: The hypervariance (top row) and sign fluctuation (bottom row), when learning several learning rates on the SVHN dataset. These are calculated as we perturb, from left to right, the choice of training data, the choice of validation data, the initial weights and the initial learning rates. We observe that non-greediness over long horizons is responsible for a large hypervariance and sign fluctuation (purple vs blue). However, we can preserve non-gr -onggreediness and greatly reduce gradient degradation by sharing hyperparameters for each 40 contiguous inner steps (red).
The variance and sign fluctuation of hypergradients are shown in Figure 2 when hypergradients calculated for several learning rates, for LeNet the SVHN dataset. We observe that non- greediness makes hypergradients much more sensitive to small changes in the optimization land- scape. For instance, changing the seed for the sampling of the training dataset produces hypergradi- ents with a standard deviation that is over 6 times larger than the mean, making outer optimization very inefficient. However, sharing contiguous hyperparameters lowers the hypervariance and sign fluctuation drastically. In particular, the sign of hypergradients only fluctuates by an average of 1.5% across all factors of variation, making a robust quantity for outer optimization.
5.2 NON-GREEDY HPO OVER LONG HORIZONS
The section above considered hypergradient noise around a fixed hyperparameter setting. In this section, consider how that noise and its mitigation translate to the outer optimization process, where hyperparameters are updated at each outer step.
We start with HPO over medium length horizons with small networks, where reverse-mode differentiation can be used to learn many hyperparameters non- non-greedily as baseline. In Figure 3 we learn the learning rate schedule starting from a = O, in the maximally greedy and non-greedy setting, with and without hyperparameter sharing. We do not use tricks like online learning as in (Baydin et al. (2018) to make greediness more transparent. As previously observed by Wu et al. (2018), greedy optimization leads to poor solutions with learning rates that are too small. While the vanilla non-greed con-greddy setting works well for simple datasets like MNIST, it fails to learn a good schedule for real-world datasets like SVHN, converging much higher values than reasonable. By sharing hyperparameters, we stabilize the outer optimization by lowering hypervariance, and this allows us learn schedule that even beats off-the-shelf baseline for this dataset.
MNIST & SVHN.
We test Algorithm I on 50 epochs of CIFAR-10, for a Wide ResNet of 16 layers. Results are shown Figure [ We choose not to use larger architectures or more epochs to save compute time, and because find that hyperparameters matter most for fewer epochs. Note also that we are not interested in the absolute performance of the model, but rather in the performance of the hyperparameters for any given model. To the best of our knowledge,
CIFAR-10.

---

Under review as a conference paper at ICLR 2021
100
test 8e0 (%))
MNIST
Greedy Non-greedy
0.04
40-
Ours Baseline
20
0.00
80
SVHN
tost a00 (9)
60
40-
0.1
20-
0.0
100
200
300
400
100
200 300
400
steps
steps
Figure 3: The learning rate schedule a learned for the MNIST and SVHN datasets using a LeNet architecture over 500 inner gradient steps. We observe that real-world datasets like SVHN, both greedy and non-greedy hyperparameter optimizations fail to learn decent learning rate schedules. However, sharing learning rates within neighbouring batches stabilizes non-greedy hypergradients and allows us to find schedules that can even outperform off-the-shelf schedules.
demonstrate a stable gradient- bastee optimization of the learning rate, momentum and weight decay for such large number of steps (~ 10*). Interestingly, algorithm mostly relies high weight decays for regularization, which allows for smaller momentum with no performance drop. Finally, note that the search range of algorithm is much larger than typical methods learning similar hyperparameters. By initializing a to zero and y to 0.1, taking 10 outer steps effectively defines search range of [-1, which is about 20 times larger than usual competing methods the same dataset (Falkner et al. 2018). In short, we assume much less prior knowledge about the nature of the hyperparameters to learn. This makes much harder for non- non-gradient based methods like random search or Bayesian optimization to find good hyperparameter configurations.
Baseline Comparison. We compare our algorithm to baselines in Table I A common theme in meta-learning research been the lack of appropriate baselines, with researchers often finding that random search (RS) can outperform complex search algorithms, for instance in NAS (Li & Tal- walkar 2019) or automatic augmentation (Cubuk et al. 2020). One reason why RS may beat greedy alternatives is precisely that RS isn't greedy. Another reason is that many of these applications de- fine a search range that is contrived to have mostly good candidates. In the case of DARTS (Liu et al. 2019), expanding the search space include many poor architectures has helped diagnose issues with its search algorithm (Zela et al. (2020). We run RS over the same search space as our method, and for comparable GPU time ( 13 hours). As stated above, our search space is large and this makes difficult for RS to find good hyperparameters quickly. Bayesian optimization un- derperforms RS in our experimental setting, and we refer the reader to Appendix for more details. We also evaluate hypergradient descent (Baydin et al. 2018) with various initial hyperparameters sampled from our search range, so as to match computational budget with ours.
Hand-tuned Comparison. Finally, we manually search for the best hyperparameters by using the ones that are most common in the literature, and evaluating multiple values around them (see Appendix D). Note that this manual baseline relies on strong inductive biases which wouldn't be available, say, when learning hyperparameters for new unknown optimizer. Our method signifi- cantly outperforms both random search and hypergradient descent, while matching the performance of the best hand-tuned hyperparameters. The latter suggests that method would be efficient way to perform HPO for new applications or new optimizers, where good hyperparameter priors don't already exist.
8

---

Under review as a conference paper at ICLR 2021
Test accuracy of our method compared baselines ran for the same computational budget. MNIST and SVHN are optimized over 2 epochs (~ 10 steps) while CIFAR- 10 is optimized over 50 epochs (~ 10 steps). Note how greediness gets worse as the dataset becomes more complex.
Table 1:
Method
MNIST
SVHN
CIFAR-10
Hand-tuned (best choice)
98.4 +0.1
85.1
89.2
Random Search
98.0 =0.2
82.2 #1.1
82.3 =0.7
Greedy (Baydin et al. 2018)
97.5
84.0 +0.2
80.8 #0.2
Ours
98.7 +0.1
85.7 +0.8
89.3 #0.1
DISCUSSION
This work makes an important step towards gradient-based HPO for long horizons, by enabling non- greediness through the mitigation of gradient degradation. More specifically, we show that sharing contiguous hyperparameters is simple and efficient way to reduce the variance of hypergradients. The nature of non non-greedy bilevel optimization requires the inner optimization to be run several times, datasets remains costly. However, we show that only ~ 10 outer
and so HPO over ImageNet-Iie steps sufficient to converge to good hyperparameterss in previous work (Wu et al. 2018). This is in part made possible by high quality hypergradients, and by using the fluctuation of their sign criterion for convergence. Extensions to this work could consider extending our method to discrete-valued hyperparameters with relaxation techniques, which would enable larger range of non-greedy meta-learning applications. We hope that our work encourages the community to reconsider gradient-bard based hyperparameter optimization in terms of greediees,ssss, and pave the way towards ubiquitous hyperparameter solver.
opposed the thousands conjectured

---

Under review as a conference paper at ICLR 2021
REFERENCES
Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson, and Eytan Bakshy. Botorch: Programmable bayesian optimization in py- torch. CoRR, abs/1910.06403, 2019.
/app//191000 910. 1tt.a/////....0...000 06403
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. On- line learning rate adaptation with hypergradient descent. In International Conference on Learning Representations, 2018.
Y. Bengio, P. Frasconi, and P. Simard. The problem of learning long-term dependencies in recurrent networks. In IEEE International Conference Neural Networks, 1993.
Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions Neural Networks, 1994.
Yoshua Bengio. Gradient-based optimization of hyperaarameters. Neural Comput., August 2000.
ISSN 0899-7667. doi: 10. 1011668/88896660000111111111
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019.
E. D. Cubuk, Barret Zoph, Jonathon Shlens, and Quoe V. Le. Randaugment: Practical automated data augmentation with a reduced search space. 2020 IEEF/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pp. 3008-3017, 2020.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Justin Domke. Generic methods for optimization baaae modeling. In Neil D. Lawrence and Mark Girolami (eds.). International Conference Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, La Palma, Canary Islands, 21-23 Apr 2012. PMLR.
Xuanyi Dong, Mingxing Tan, Adams Wei Yu. Daiyi Peng, Bogdan Gabrys, and Quoc V. Le. Auto- has: Differentiable paper-par and architecture search, 2020.
Michele Donini, Luca Franceschi, Massimiliano Pontil, Orchid Majumder, and Paolo Frasconi. Scheduling the Learning Rate via Hypergradients: New Insights and New Algorithm. arXiv e-prints, art. 1rXiv:190000855 October 2019.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter opti- mization at scale. Proceedings of the 35th International Conference on Machine Learning, pp- 1436-1445, 2018.
Matthias Feurer and Frank Hutter. Hyperparameter Optimization. Springer International Publishing. Cham, 2019. ISBN 978-3-030-0533 18-5. doi: 10. 100100779988330000053111
Sebastian Flennerhag, Andrei A. Rusu, Razvan Pascanu, Francesco Visin, Hujun Yin, and Raia Hadsell. Meta-learning with warped gradient descent. In International Conference on Learning Representations, 2020.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In Doina Precup and Yee Whye Teh (eds.), Inter- national conference on Machine Learning, Proceedings of Machine Learning Research, Interna- tional Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on Machine Learning. 2018.
Jie Fu, Hongyin Luo, Jiashi Feng, Kian Hsiang Low, and Tat-Seng Chua. Drmad: Distilling reverse- mode automatic differentiation for optimizing hyperparameters of deep neural networks. In IJCAI, 2016.
10

---

Under review as a conference paper at ICLR 2021
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint 1e3tv:1706.0266611 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1997.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. arXiv preprint arXiv:2004.05443,, 2020.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei (eds.), International conference Machine Learning, Proceedings of Machine Learning Research, Lille, France, 07-09 Jul 2015.
PMLR.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based train- ing of neural networks. arXiv preprint arXiv:
2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), International Conference on Learning Representations, 2015.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In UAI, 2019.
Mengtian Li, Ersin Yumer, and Deva Ramanan. Budgeted training: Rethinking deep neural network training under resource constraints. In International Conference Learning Representations, 2020.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference Learning Representations, 2019.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing Millions of Hyperparameters by
Implicit Differentiation. arXiv e-prints, art. arXiv:19111 191.0299,,,, November 2019.
Ilya Loshchilov and Frank Hutter. Sgdr: tional Conference on Learning Representations, 2017.
Stochastic gradient descent with warm restarts. In Interna-
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2019.
Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient-based tuning of continuous regularization hyperparameters. In International conference Machine Learning, 2016.
Dougal Maclaurin, David Duvenaud, and Ryan P. Adams. Gradient-based Hyperparameter Opti- mization through Reversible Learning. arXiv e-prints, art. arXiv:1502.034499 February 2015.
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. volume 97 of Proceedings of Machine Learning Research, pp. 4556-4565, Long Beach, California, USA, 09- 15 Jun 2019. PMLR.
Aaron van den Oord, Sander Dieleman, Hciga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint arXiv: 2016.
Paavo Parmas, Carl Edward Rasmussen, Jan Peters, and Kenji Doya. PIPPS: Flexible model-based policy search robust to the curse of chaos. volume 80 of Proceedings of Machine Learning Re- search, pp.
Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on Machine Learning, 2013.

---

Under review as a conference paper at ICLR 2021
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vitito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International con- ference on Machine Learning, 2016.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International conference Machine Learning, 2018.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagaan for bilevel optimization. In AISTATS, 2019.
Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference Machine Learning. 2015.
H Stackelberg. The Theory Of Market Economy. Oxford University Press, 1952.
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei Efros. Dataset distillation. arXiv preprint arXiv:1811.10995 2018.
P. J. Werbos. Backpropagation through time: what it does and how to do it. Proceedings of the IEEE, 1990.
R. J. Williams and D. Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 1989.
Yuhuai Wu. Mengye Ren, Renjie Liao, and Roger Grosse. Understanding short-horizon bias in stochastic meta-optimization. In International Conference on Learning Representations, 2018.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hut-
ter. Understanding and robustifying differentiable architecture search. In International Confer- Learning Representations, 2020. URL https:/ ptttps:///penreviews net hwtp::wwwweeeeeeeeeeeeee forum?id= H1 H1cDNyrKDS
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. In Interna- tional Conference on Learning Representations, 2017.
12

---

Under review as a conference paper at ICLR 2021
Appendices
A: Forward-mode Hypergradient Derivations
Recall that interested in caleulating
Z = A. Bi
recursively during the inner loop, where
d0,
00;
00, 0x 0
Zi
A,
B,
yx
00;-1
so that we can calculate the hypergradients on the final step using
dL
0L Zr
dA
00r
Each type of hyperparameter needs its own matrix Z,, and therefore its own matrices A,, and B,.
Consider first the derivation of these matrices for the learning rate, namely a. Recall that the update rule after substituting the velocity in is
0 as (B10111 OLtrain 11:0011
00,-1
and therefore it follows directly that
02 Cirain 00%_ (
AC = 1 DXD aat
4,1 DxD
The calculation of BT is a bit more involved our work because when using momentum U:-1 now itself function of a. First we write
dve-1
da:
(Etrain (100-1))
B -3c
11-1 +
dx
da
da
00.-1
Dv,-1
ALtrain 1100-1
-Be0k
8PXN
(3,0011+
0a
00,-1
Now since
iLtrain
= 1,00-1 +
140:-1
we can write the partial derivative of the velocity an another recursive rule:
dv:
C da
8 Ltrain
00,-1
B,C + 0x00,11
+ 14:
da
= =,,00 + (m11DD + Ltrainn
00,-1
002 00
da
13

---

Under review as a conference paper at ICLR 2021
And putting all together recovers the system:
18 Ltrain
A 1 DxD at
+ Mell" DxD
00,-1
ÔLtrain
B. Bran
88 8DxN
B100-1+
+ 1,,00-1
a0,-1
0 Lerain
Cf 3,0 +
(uiDDD=
Z
00%
For learning the momentum and weight decay, a very similar approach yiclds
( 002
A 1DxD -a,
14 DxD
B -ia, C, -6pxN(av0-)
8 Ltrain
C = =0 DxN (u;) + +,,0,1+ + 111DDD +
2
003
and
182 Ltrain
A DXD
M, M,1DDD
00?
B -3,a, 8PpN (a,0=-1)
03 Irrrrain 000_1
Ct of ODXN (0--1) 1 [1110D
D
B: Implementation Details
Figure We learn 5 values for the learning rates, 1 for the momentum and 1 for the weight decay, make it comparable to the hyperparameters used in the literature for CIFAR-10 (see Appendix D). A batch size 256 is used, with 5% of the training set of each epoch set aside for validation. We found larger validation sizes not to be helpful. Hypergradient descent uses hyperparameters initialized at zero as well, and trains all hyperparameters online with an SGD outer optimizer with learning rate 0.2 and +1 clipping of the hypergradients. We used initial values % 0.1, 733 0.15 and 7/ = 4x 14 but the performance barely changed when these values were multiplied or divided by 2. Since we take 10 outer steps and initialize all hyperparameters at zero, this defines search ranges: a E [-1, 1]. 3 [-1,5, 1.5), and [-4 10-3 10-5,4 4 x 10-3). The Hessian matrix product is clipped to +10 to prevent one batch from having dominating contribution to hypergradients. Strictly speaking, sharing hyperparameters corresponds summing their hypergradients rather than averaging them, and therefore we divide this sum by the number of batches each hyperparameter is used for.
Figure Here we wanted isolate all factors responsible for hypervariance, We thus used float64 precision with batch size 64, as this reduced hypervariance across all methods. Clipping did not change the hypervariance drastically but was applied to =1
inner loop. We learned learning rates for our method, namely one learning rate per 40 steps. The unperturbed learning rate was set to Okj = 0.05. The perturbation for initial weights and hyperparameters (here a) corresponds to adding +1% of their value, while perturbation of Dirain and Deal correspond to a different sampling seed. For the plots, we used a moving average for the greedy and non-greedy lines for clarity.
Figure 3. Here we used a batch size 128 for both datasets to allow epochs worth of inner optimization in about 500 inner steps. Clipping restricted to #3 to show the effect of noisy hypergradients more clearly. Since MNIST and SVHN are cheap datasets to run on a LeNet archi- tecture, afford 50 outer steps and early stopping based validation accuracy.
14

---

Under review as a conference paper at ICLR 2021
Table 1. Each method for given dataset is run for similar GPU budget. For CIFAR-10 that's about 13 hours on a 2080 GTX GPU. Random search and our method both consider 7 learning rates, 1 momentum and 1 weight decay. Note that random search struggles in finding good hyperparame- ters even though ~ 100 random hyperparameter settings are evaluated, because some hyperparam- eters compromise the whole training process. This is the case of large positive learning rates, negative learning rates, or momentums greater than one. Since random search is memory-less trial- and-error method, any hyperparameter region that compromises learning altogether is very harmful. Truncation was kept < 15% to obtain maximal performance. The error bars are calculated over seeds for each entry in the table.
C: Hypergradients
Here provide the hypergradients corresponding to the outer optimization shown in Figure 1. Note that the range of these hypergradients is made reasonable by the averaging of gradients coming from contiguous hyperparameters.
0.03
10
0.002
6.01
0.001
0Cuut 0ex
0.00
0.000
Oc.s/O Op
0.005
-0.001
-0.2
0.000
0.002
0.4
-0.003
-0.05
0
20
40
0
20
40
20
epochs
epocls
epocls
Figure 4: Hypergradients have reasonable range but fail to always converge to zero when the validation performance stops improving.
D: Baselines
The objective here is to select the best hyperparameter setting that deep learning practitioner would reasonably expected to use, based on the hyperparameters used by the community for the datasets at hand. For CIFAR-10, the most common hyperparameter setting is the following: is initialized at (kn = 0.2 (for batch size 256, as used in our experiments) and decayed by a factor /j 0.2 at 30%, 60% and 80% of the run (Mult irtistee istee in Pytorch); the momentum 3 is constant at 0.9, and the weight decay ş is constant at 5 x 10 4 We search for combinations of hyperparameters around this setting. More specifically,
search over all combinations of ag (0.05, 0.1, 0.2, 0.4. 0.6), (0.1, 0.2, 0.4), = (0.45, 0.9, 0.99), and μ (2.5 x 10-4,5 5 x 10-1 x 10-33. This makes up total of 135 hyperparameter settings, which each run 3 times get
and standard deviation. The distribution of those means are provided in Figure 5 and the best hyperparameter setting is picked based on validation performance. This is the value report in Table I under Hand-tumed (best).
MNIST and SVHN hyperparameters matter less, and in particular we observed no gain from using momentum and weight decay. The most popular learning rate schedules used for these datasets seem to be the cosine annealing one. We evaluate this schedule for og = {0.05, 0.1, 0.2, 0.4, 0.6) and select the best hyperparameters based on validation performance.
15

---

Under review as a conference paper at ICLR 2021
0.6
10
0.4
0.6
3 0.3
0.4
0.1
0.2
0.0
0
20
20
46
20 spochs
opocls
ogpochs
10
82.0
82.5
$3.0
85.5
$4.0
81.5
$5.0
$5.5
$6.0
86.5
87.0
87.5
88.0
$8.5
80.0
noxes (36)
Figure 5: The combination of hyperparameters searched over for CIFAR-10 (top row) and the cor- responding distribution test accuracies (bottom row).
E: Bayessian Optimization
We ran numerous BO experiments for our experimental configuration. We used the modern BoTorch-AA library (Balandat et al.) 2019), with the common BO settings found the HPO litera- ture: Gaussian process with Matern 5/2 kernel, with expected improvement (El) as the acquisition function, and using Sobol search for the first few arms.
In our experiments, sought to showcase the efficiency of using gradients in HPO by considering large hyperparameter search range. This means that we assume very little about the hyperparameters trying to learn. For instance learn the learning rate in range search range in BO would be about 20 times smaller like a E [10-6 10-1] (Falkner et al. 2018). and would use log scaling search this space related methods struggle to even match random search. This is because the search space mostly contains configurations that have high validation loss, and BO spends much of its time exploring irrelevant fluctuations in that high loss region. In order to slightly outperform random search with BO, had to divide the search range by 20 and use times the computational budget. Indeed, BO is usually orders of magnitude more expensive to run than our method, with some methods reporting up to GPU days on CIFAR-10 (Falkner et al. 2018) while our algorithm takes 13 hours (albeit for smaller architectures).
1- while common
efficiently. In our setting, we find that B0 and
16


Reviews:
[{"review_id": "YUfkoOYJ8C", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review Non-greedy Gradient-based Hyperparameter Optimization Over Long Horizons\nThe paper presents an approach to hyper parameter optimisation over long horizons avoiding greedyness. This is achieved by calculating gradients wrt to the hyper parameters and using the sign of the gradients to indicate convergence. The paper is well written and structured and the suggested approach shows promising results. I only have two minor comments/ suggestions. \n\nIntroduction:\nAfter first sentence: there is an empty space missing: \").This\"\n\nExperiments:\nCould you compare your results based on some Bayesian Optimization based algorithm and compare to the computational cost? If not, why?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KJxsMXXyKx", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors tackle the problem of HPO, focusing on the optimization of real-valued hyperparameters for DNNs using a gradient-based method. This novel method enables non-greediness through the mitigation of gradient degradation and allows for long horizons.\n\nHow does this work compare against tools like BOHB (not cited in this paper) [1]? The method introduced here is based on hypergradients while BOHB is based on a combination of Hyperband and Bayesian optimization, so these are two different algorithms. Nonetheless, since BOHB can perhaps be considered state-of-the-art for DNN HPO including continuous and discrete hyperparameters, it is still worth to provide a  comparison in the experimental section. This is reinforced by the fact that the authors use random sampling as a baseline which has been shown to be inferior to BOHB on similar or identical benchmarks.  \n\nIn the methodology section, 3.1 and 3.2 are background material. It'd perhaps be clearer if the authors move these parts in a background section so as to differentiate the contributions from the background. The contribution section of this paper is section 3.3 where the key idea is the reduction of the hypervariance induced by the gradient degradation phenomenon. In the experiment section, the authors define the hypervariance, which should be defined in a previous section instead of the empirical part. Or else, since the hypervariance is somewhat defined twice, these two parts could be merged in section 3.3.  \n\nTo reduce the hypervariance the authors propose hyperparameter sharing and show empirically how it helps gradient degradation. In addition, the authors propose to use gradient signs as an indicator of convergence and show the impact empirically. No formal justification is provided for these two contributions which is a weakness of the paper. \n\nMinor remarks: \n- The abstract should explicitly mention that this is a Deep learning paper. The authors shouldn't expect that since the paper is submitted at ICLR then a reader will know that the paper is on DL. \n- It is usually a good idea to have the figures either at the beginning or at the end of a page rather than in the middle of the page. See for example Figure 2. \n- It is odd to have figure 1 on the second page if the figure is then used on page 8. On page 2, the readers are not able to understand the figure because the outer step in the figure is introduced later in the text. \n\n[1] Falkner, Stefan, Aaron Klein, and Frank Hutter. \"BOHB: Robust and Efficient Hyperparameter Optimization at Scale.\" ICML. 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6mBOyff5_h-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall I vote for (weak) rejecting. IMO the main weakness of the paper is the clarity, for instance I had to read the article multiple times before understanding the main contribution. Some crucial terms should may have to be mathematically defined in the paper, like 'greedyness' for hyperparameter optimization, a term a was not aware of.\n\n\nAdvantages of the paper:\n- the proposed algorithm seems to lead to significance gain in performance in practice\n- authors proposed a new stopping criterion which seems to be more efficient in practice\n\n\nConcerns:\n\n1- The notion of greedyness is paramount for the paper, however it is not defined. Moreover the references provided are not very helpful to understand the concept. The word 'greedy' appears once in [1], twice in [4] and is not defined properly. The word 'greedy' does not appear in [2, 3]. Would it be possible for the authors to define the concept properly in the paper, or the provide a selfcontained reference?\n\n2- I founded the main contribution of the paper hard to find. If I understood well, authors propose a new to estimate the hypergradient by averaging out, and then updating the hyperparameter. This is very subjective, I would recommend to highlight this contribution, and maybe to remove 'we combined the above [...] with momentum decay' in the introduction.\n\n3- The experiments do not seem clear to me, I do not know if it comes from my lack of experience in the field of from the lack of clarity of the paper, but experiments were hard to follow. In particular the number of steps in the inner problem is provided, but what is the size of the hyperparameter searching space? In particular all the experiments are provided with convergence as a function of the number of steps. Since authors rely on forward differentiation, one step of the proposed algorithm can be more costly than one step of the algorithms in the baseline. Am I missing something? Is forward differentiation paramount for the proposed algorithm?\n\n4- Authors claim that hyperparameter sharing is equivalent to averaging (page 5). Is it mathematically grounded? Is it trivial? Or could authors provide a reference?\n\nThere are a lot of things I did not understand, thus I voted for weak reject. However if authors answer my questions I am of course willing to change my score.\n\n\nMinor:\n- in section 1 there should have a space after the point in l3\n\n\n[1] Luketina, J., Berglund, M., Greff, K., & Raiko, T. (2016). Scalable gradient-based tuning of continuous regularization hyperparameters. ICML 2016\n\n[2] Franceschi, L., Donini, M., Frasconi, P., & Pontil, M. (2017). Forward and reverse gradient-based hyperparameter optimization. ICML 2017\n\n[3] Baydin, A. G., Pearlmutter, B. A., Radul, A. A., & Siskind, J. M. (2017). Automatic differentiation in machine learning: a survey. JMLR\n\n[4] Donini, M., Franceschi, L., Pontil, M., Majumder, O., & Frasconi, P. (2019). Scheduling the Learning Rate via Hypergradients: New Insights and a New Algorithm. arXiv preprint\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6HQMY4zt-_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an algorithm for tuning hyperparameters over long optimization problems to mitigate sub-optimal greedy solutions from short-horizon bias.  This is done by:\n \n(1) sharing hyperparameters across optimization steps which reduces the variance of hypergradients and computational cost\n \n(2) A method for assessing when our hyperparameters have converged\n \n(3) A forward-mode gradient calculation for SGD with momentum\n \nThese components are combined into an algorithm and empirical results are presented.\n \n \n \nStrengths:\n \nThe paper is well-written\n\nThe contributions are well-placed with the related work\n\nSharing hyperparameters across multiple steps is well-motivated.\n\nThe experiments on hypergradient variance are a useful diagnostic for these kinds of algorithms.\n\nTuning hyperparameters like this could be impactful if we scale it to state-of-the-art models and optimization procedures/horizons.\n \n \nWeaknesses:\n \nThe forward-mode algorithm is limited to SGD with momentum and weight-decay.  More complicated optimization algorithms are used in many domains.\n\nIt’s not clear to me the sign of the hypergradient is a good test for convergence.\n\nIf we can’t use modern optimizers like Adam with the hypergradient, I am worried that the algorithm is very brittle.\n\nThe improvements aren’t very large relative to the hand-tuned baseline.  See CIFAR-10 where the baseline is 89.2 +- .2 and theirs is 89.3 +- .1.  Perhaps your algorithm may find this setting faster since there are about 100 runs for the hand-tuning.  I would want to see if there is some way to offer an improvement over the grid-search.  What happens if you start your training with the hyperparameters initialized at the best-value from the grid-search?\n\nOnly a handful of hyperparameters are tuned -- perhaps this is due to how the gradient calculation scales with the number of hyperparameters.  In this hyperparameter regime, a good baseline to test against might be bayesian optimization as opposed to grid-search.\n \n\nMy recommendation for the paper is a 6 -- i.e., marginally above the acceptance threshold. This is because the paper makes useful contributions toward optimizing hyperparameters over long-horizons, by motivating sharing hyperparameters via gradient variance and providing a forward-gradient calculation skeleton.  However, the current improvements relative to the baseline are mediocre, and it’s not clear how to scale the method to optimizers besides SGD with momentum.\n \n \nThe following points may help improve the paper, but did not affect my score:\n \nFigure 1 says “10, 50 and 50”.  Is there a typo here?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates methods for gradient-based tuning of optimization hyperparameters.  This is an interesting area, and the paper isn't bad.  The examination of hypervariance seems relatively novel and useful.  I also appreciate the point about Bayesopt sometimes working well simply due to small ranges.

However, I agree with the criticisms of the reviewers.  Overall this paper isn't quite clear, thorough and impactful enough to make it in this round, but I think with more attention to baselines and scope this paper could be acceptable.

Some minor comments:

1) The signed-based optimizer, while simple and sensible (which is good), seem kind of ad hoc.
2) The authors don't seem to have properly scoped the problem and method, since greediness is only a major concern for inner optimization hyperparameters specifically.  It's not clear that for regularization parameters that this problem exists or that your method would apply.

A small nit:  Is hypervariance the right thing to look at, since the problem can exist even in deterministic settings?  Perhaps some sort of sensitivity analysis would be more appropriate.  Also you should reference Barack Pearlmutter's thesis which first explores these issues.   I would also mention that the hypervariance is generally tiny for smaller-than-optimal learning rates, and massive for larger-than-optimal learning rates, (the chaotic regime).
Decision: Reject