Gradient-based Hyperparameter Optimization Over Long Horizons
Authors: Paul Micaelli
Amos Storkey
Venue: NeurIPS 2021 Poster (2021)
Keywords: Meta-learning
Hyperparameter Optimization
Gradient-based
Gradient Degradation
Forward-mode differentiation
AutoML

Abstract: Gradient-based hyperparameter optimization has earned a widespread popularity in the context of few-shot meta-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 hyperparameters online, but this introduces greediness which comes with a significant performance drop. We propose forward-mode differentiation with sharing (FDS), a simple and efficient algorithm which tackles memory scaling issues with forward-mode differentiation, and gradient degradation issues by sharing hyperparameters that are contiguous in time. We provide theoretical guarantees about the noise reduction properties of our algorithm, and demonstrate its efficiency empirically by differentiating through $\sim 10^4$ gradient steps of unrolled optimization. We consider large hyperparameter search ranges on CIFAR-10 where we significantly outperform greedy gradient-based alternatives, while achieving $\times 20$ speedups compared to the state-of-the-art black-box methods.

Gradient-based Hyperparameter Optimization Over Long Horizons
Paul Micaelli University of Edinburgh [oul.micaelli]eee ac.
Amos Storkey University of Edinburgh {a. storkey)@dd. ac.
Abstract
Gradient-based hyperparameter optimization has earned widespread popularity in the context of few-shot meta-learning, but remains broadly impractical for tasks with long horizons (many gradient steps), due memory scaling and gradient degradation issues. A common workaround is to learn hyperparameters online, but this introduces greediness which comes with significant performance drop. We propose forward-mode differentiation with sharing (FDS), simple and efficient algorithm which tackles memory scaling issues with forward-mode differentiation, and gradient degradation issues by sharing hyperparameters that are contiguous in time. We provide theoretical guarantees about the noise reduction properties of our algorithm, and demonstrate its efficiency empirically by differentiating through 10 gradient steps of unrolled optimization. We consider large hyperparameter search ranges on CIFAR-10 where we significantly outperform greedy gradient- based alternatives, while achieving x20 speedups compared to the oate-of-theeare black-box methods. Code is available at: https:/ //gi githhu...... commpolo5/
Introduction
Deep neural networks have shown tremendous success a wide range of applications, including classification [1], generative models [2], natural language processing [3] and speech recognition [4]. This success is in part due to effective optimizers such SGD with momentum Adam [5], which require carefully tuned hyperparameters for each application.
recent years, long list of heuristics to tune such hyperparameters has been compiled by the deep learning community, including things like: how to best decay the learning rate [6], how to scale hyperparameters with the budget available [7], and how scale learning rate with batch size [8]. Unfortunately these heuristics are often dataset specific and architecture dependent [9]. They also don't t apply well to new optimizers [10], or tools, like batch normalization which allows for larger learning rates [11].
With so many ways to choose hyperparameters, the deep learning community is at risk of adopting models based on how much effort went into tuning them, rather than their methodological insight. The field of hyperparameter optimization (HPO) aims to find hyperparameters that provide good generalization performance automatically. Unfortunately, existing tools rather unpopular for deep learning, largely owing to their computational cost. The method developed here is gradient- based HPO approach; that is, it calculates hypergradients, i.e. the gradient of some validation loss with respect to each hyperparameter. Gradient baseed HPO should be more efficient than black-bo -ox methods as the dimensionality of the hyperparameter space increases, since it is able utilize gradient information rather than rely on trial and error. In practice however, learning hyperparameters with gradients has only been popular in few-shot learning tasks where the horizon is short, i.e. where the underlying task is solved with few gradient steps. This is because long horizons cause hypergradient degradation, and incur memory cost that makes reverse-mode differentiation prohibitive.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Greedy gradient-basee methods alleviate both of these issues by calculating local hypergradients based on intermediate validation losses. Un- fortunately, this introduces some bias [15] and results in significant performance drop, which we are able to quantify in this work. We make use of forward-mode differentiation, which has been shown to offer a memory cost constant with horizon size. However, previous forward- mode methods don't address gradient degrada- tion explicitly and are thus limited to the greedy setting 6, 17].
RS
HBS
BO
BOHB
00-
FDS (OUN))
regret (%%
10 20
40
Lane (GP hours)
We introduce FDS (Foward-mode Differentia- tion with hyperparameter Sharing), which to the best of our knowledge demonstrates for the first time that hyperparameters can be differentiated non-greedily over long horizons. Specifically, we make the following contributions: (1) we propose to share hyperparameters through time, both motivating theoretically and with vari- experiments, (2) we combine the above in poward-mode differentiation algorithm, and (3) show that method can significantly out- perform various HPO algorithms, for instance when learning the hyperparameters of the SGD- momentum optimizer.
Figure Performance of the most popular hy- perparameter optimization methods when learning the learning rate, momentum and weight decay on 50 epochs of CIFAR-IO, for WideResNet of 16 layers. Non-greedy methods (RS, BO, HB [12], BOHB [13]) solve for global hyperparameters but rely on trial-andeerrol which makes them slow. Greedy gradient-based methods (e.g. HD [14]) faster but solve for local hyperparameters which makes them suboptimal. Our method combines the strengths of these two paradigms and outperforms the next best method while converging 20 times faster. Each curve is the average of 8 seeds.
2 Related Work
There are many ways to perform hyperparameter optimization (HPO) [18], including Bayesian optimization (BO) [19], reinforcement learning [20], evolutionary algorithms [21] and gradient-based methods [22]. The state-of-the-art in HPO depends on the problem setting, but black-box methods like Hyperband (HB) [12), and its combination with BO into a method called BOHB [13] have been the most popular. Modern work in meta-learning deals with various forms of gradient- based HPO [23], but usually focuses the few-shot regime [24] where horizons are conveniently short (~ 10 steps) while we focus on long horizons (~ 10 steps).
Gradient-based HPO. Using the gradient of some validation loss with respect to the hyperparam- eters is typically the preferred choice when the underlying optimization is differentiable. This is a type of constrained optimization [25] which stems from earlier work on backpropagation through time [26] and real-time recurrent learning [27]. Unfortunately, differentiating optimization is an expensive procedure in both time and memory, and most proposed methods limited to small models and toy datasets [28-30]. Efforts to make the problem more tractable include optimization shorteuts [31], truncation [32] and implicit gradients [33-35]. Truncation be combined with our approach but produces biased gradients [36], 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 is minimized (e.g. optimizer hyperparameters) Forward-mode differentiation [27] boasts a memory cost constant with horizon size, but gradient degradation has restricted its use to the greedy setting [16, 17].
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 [14, 16, 17, 37], architecture search [38], dataset distillation [39] or curriculum learning [40]. Greediness refers to finding the best hyperparameters locally rather than globally. practice, involves splitting the inner optimization problem into smaller chunks (often just one batch), and solving for hyperparameters over these smaller horizons instead; often in an online fashion. We formalize greediness in Section 3.2. this paper expand upon previous observations [15] 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 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 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. This leads to hypergradients that have large variance, making differentiation through long horizons impractical. This is usually observed in the context of recurrent neural networks [41,42], but also in reinforcement learning [43] and HPO [29]. Solutions like LSTMs [44] and gradient clipping [45] have been proposed, but are respectively inapplicable and insufficient to long-horizes HPO. Variational optimization [36] and preconditioning warp-layers [46] can mitigate gradient degradation, but these methods are expensive in memory and therefore are limited to small architectures and/or a few hundred inner steps. In comparison, we differentiate over ~ 10 inner steps for WideResNets [47].
3 Background
3.1 Problem statement
Consider neural network with weights 0, trained to minimize a loss Luain over dataset Dunin. This is done by taking T' steps with a gradient-baat -based optimizer 4, which uses a collection of hyperparameetess À E RR, For clarity of notation, consider that & uses one hyperparameter per step, written X where indices are shown in brackets to differentiate them from a variable evaluated at time t. We can explicitly write out this optimizer as + 0u+1 {( (0 (11=))). Duraia) ((+11) Vt
(1. T}. Note that 0g is function of [1::]]= and it follows that Or Or (A).T)) = Ar(A).
We would like to find the hyperparameters A such that the result, at time T, of the gradient process minimizing objective Cuain also minimizes some generalization loss Lval on validation dataset V This can be cast as the following constrained optimization:
X arg min Leal (0r vval)
A
subject to 0.11 = (( (f (A(1=e)): Duaa)), ) 1)++1))
(2)
The inner loop in Eq 2 expresses a constraint on the outer loop in Eq 1. In gradient- HPO, our task to compute the hypergradient ddvvi//d and update X accordingly. Note that some methods require Or = arg ming Cinin (0, Durain A) with Lizin being function of À explicitly [33-35], in which case the above becomes a bilevel optimization [48]. Our algorithm waives these requirements.
3.2 Greediness
Let H be the horizon, which corresponds to the number of gradient steps taken in the inner loop (to optimize 0) before one gradient step is taken in the outer loop (to optimize A). When solving Eiq 1 non-greedily we have H = T. However, most modern approaches are greedy [14, 16, (7-39. in that they rephrase the above problem into a sequence of several independent problems of smaller horizons, where A B is learned in the outer loop subject to an inner loop optimization from O, to
Oct-1 with H < T. Online methods such Hypergradient Descent (HD) [14] are an example of greedy differentiation, where H and A is updated at time Instead, non-greedy algorithms like FDS only update \lq at time T.
Greediness mitigates gradient degradation and lowers the memory cost of backpropagation through time (BPTT). However, greedy methods do not solve for the actual objective in Eq 1, but for some proxy objective which minimizes intermediate validation losses evaluated at 0H 02H ... The degree to which these two objectives overlap is unknown and problem dependent. In our experiments, we found that finding competitive hyperparameters with greedy methods often revolves around tricks like online learning with very low outer learning rate combined with hand-tuned initial hyperparameter values, to manually prevent convergence to small values. But solving the greedy objective correctly leads to poor solutions, a special case of which was previously described as the "short-horizon bias" [15]. In FDS, we learn global hyperparameters in a non-greedy fashion, which means that the hypergradient d(C.al/ dA is only ever calculated at 0r.
3

---

3.3 Forward-mode differentiation of modern optimizers
The vast majority of meta- meta-learnng applications use reverse- reverse-mode differentiation in the inner optimiza- tion problem (Eq 2) to optimize 0. However, the memory cost of BPTT, namely using reverse- mode differentiation for the outer optimization (Eq 1) is O(FH), where F is the memory used by one forward pass through the network (weights plus activations). In the non-greedy setting where H T. BPTT is extremely limiting: for large networks, only T ~ 10 gradient steps could be solved with modern GPUs, while problems like CIFAR- 10 require T 10 Instead, we make use of forward- mode differentiation, which scales in memory as (DN), where D is the number of weights and N is the number of learnable hyperparameters. The additional scaling with is a limitation if we learn one hyperparameter per inner step (N T). Sharing hyperparameters (section 4.1) mitigates gradient degradation, but also conveniently allows for smaller values of N.
For clarity of notation, we consider forward mode hypergradients for the general case of using one hyperparameter per step, i.c. À E R². First, we use the chain rule write d where the direct gradient has been dropped since a = 0 for optimizer byperparameters. The first term on the RHS is trivial and can obtained with reverse-mode differentiation as usual. The second term is more problematic because O, (0r-1 >pT- Apr)). We use the chain rule again calculate this term recursively:
d0,
00,
d0,
00;
which write Z. A, + B,
dx
00;-1
06
dx
0X 0
where 0, E ERR,AE XERT, Z, E RDX A₁ E RDXD and B, E RDxT, Note that the columns Z step t are zeros for indices t +,,++2, T, since the hyperparameters at those steps haven't 't been used yet.
The expressions for A, and B: depend on the specific hyperparameters we are differentiating. In this work, we consider 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. We use Pytorch's ' update rule for SGD [49], namely 0, ((0,-2) 0,-1 a,U, with learning rate au, momentum 8, weight decay & and velocity v2 = 3,0;-1 + (aCuin/ (0 E:0,-1- Consider the when we learn the learning rate schedule, namely À
If we use the update rule without momentum [17]. Bt is conveniently sparse: it is x T matrix that only has one non-zero column index /. corresponding to 00, /0a,- However, velocity depends on the hyperparameters of previous steps. In that case, a further recursive term C, (ōv./0l must be considered get exact hypergradients. Putting together (see Appendix A) we obtain:
include terms like momentum and therefore the
88 Lmain
A 04.
+ E.1
dLuain + -510--1
B
-8
B
(4)
00,-1
0 Cirain
C 3,00
(,1+
2
007_1
where 1 is a D x D identity matrix, and 8. (q) turns vector q of size D into matrix of size D x T, whose t-th column is set to q and other columns to Os. While the matrices in Eq 4 are updated online, the hyperparameters aren't 't. This is because in the non non-greedy setting hypergradients until we have computed ZF A similar technique can be applied to momentum and
don't 't have access to the
weight decay to get Z and z (see Appendix A). All hypergradient derivations in this paper were checked with finite differences. Note that we focus on learning the hyperparameters of SGD with momentum because it is the most common optimizer in the deep learning literature. However, just like reverse-mode differentiation, forward-mode differentiation can be applied to any differentiable hyperparameter, albeit with appropriate A, and B, matrices.

---

4 Non-greedy Differentiation Over Long Horizons
4.1 Hyperparameter sharing: trading off noise reduction with bias increase
The main challenge of doing non-greedy meta-learning over long horizons is gradient degradation. In HPO this arises because small change in (0)) can cascade forward into a completely different 0r, resulting in large fluctuations of the hypergradients. This noise makes the generalization loss hard minimize (Eq 1). We find that the two main causes for this noise are the ordering of the training minibatches, and the weight initialization og. Ideally, the hyperparameters we learn should be agnostic to both of these factors, and so we would like to average out their effect hypergradients.
Ensemble averaging The most obvious way to address the above is to compute all hypergradients across several random seeds, where each seed corresponds to a different dataset ordering and weight initialization. We could then obtain an average hypergradient J4t for each inner step f. Here, l E RT is often called an ensemble average in statistical mechanics. The issue with ensemble averaging in our setting is its computational and memory cost, since each random seed requires differentiating through T' unrolled inner steps for I" hyperparameters. This makes both reverse-mode and forward-mode differentiation intractable. We consider the ensemble average as optimal in our analysis, which allows us to derive expression for the mean square error between our hypergradients estimate and μ.
Time averaging In FDS, we use the long horizon to our advantage and propose to do time averaging instead of ensemble averaging. i.c. we average out hypergradients across the inner loop (Eq 2) rather than the outer loop (Eq 1). More specifically, we sum hypergradients from W neighbouring time steps in the inner loop, which is exactly equivalent to sharing one hyperparameter over all these steps. The average is then obtained trivially by dividing by W. For instance, when learning the learning rate schedule a for H = 10 inner steps, we can learn a E R where each learning rate is used for a window of W 10 contiguous gradient steps. stochastic system where the time average is equivalent to the ensemble average is called ergodic [50] and has been the subject of much research in thermodynamics [51] and finance [52]. In our case, hypergradients aren't 't generally ergodic, and so using a single average hypergradient for W contiguous steps can introduce a bias. Informally, time averaging contiguous hypergradients leads to both noise reduction and bias increase, and we flesh out the nature of this trade-off in Theorem 4.1.
21, T) have corresponding hyperparameter d and non-greedy hypergradient 9t = - (0r) Each Ii is viewed as a random variable due to the sampling process of the weight initialization Gg and the inner loop minibatch selection. Let ... gr] be sufficiently well approximated by Gaussian distribution g N(, E), = [91. 92 92. with mean μ [P1, .... Mr] and covariance matrix Σ, where fl corresponds to the optimal hypergradients. Assume that the changes in the values of μu over time are bounded, i.e. μa can be written as the c-Lipschitz function M4+1 = le + et, where 6 E [-c,c]. Finally, let E [0, 1] denote the maximum absolute correlation between the values of g. i.e. c 2 |Ewe Vivle/EEn Vt + t'. Then, we show that the mean squared error of the hypergradients with respect to μ when sharing W contiguous hyperparameters has an upper bound:
Theorem 4.1. Let each time step
(1 + c(W 1))
MSE, +e2 2W2 1)
MSEW S
(5)
W
12
where MSE = T
1
Σ Σn
(6)
and for sufficiently small e and have with certainty, MSEW < MSE, for some W > 1, where M MSE, is the hypergradient error without any sharing (See Appendix B for a proof).
Discussion Theorem 4.1 demonstrates how sharing W contiguous hyperparameters has two effects: 1) it reduces the hypergradient noise by a factor O(W((1 + cW)) due the averaging of noisy hypergradients, and 2) it increases the error up to an amount W due to an induced bias. Intuitively, averaging contiguous hypergradients maximally reduces noise when they aren't 't correlated (c = 0), and minimally increases bias when they are drawn from distributions of similar means (c = 0). In the simpler case where hypergradients are iid and have the same variance at each step, namely g ~ N(,, (21,,²1) 1), the expressions above become MSE, = o² and MSEw < MSE. + - 11)/12. Note that all cases, the upper bound on MSE has a single minimum W corresponding to the optimal trade-off between noise reduction and bias increase.
5

---

1.0
10
111
4.00
aon-gryryy {g)
greedy
3,75
grewly
optimal (pc)
Iepestralinns
hypesgralinnts
non-groddy MSE,
0.7
0.9
MSE
0.8
nou-greddy S4.
-0.6
-0.6
0.4
100 200
100 2000
100 200
W
Figure 2: Hypergradients of a on SVHN for 100 seeds in the non-greedy (left) and greedy (middle) setting. The mean squared error is also shown (right), and is calculated with respect the optimal hypergradient (μ)) i.c. the ensemble average of non non- non-greedy greedy hypergradients (dotted line in left figure). We can that sharing hyperparameters over W steps lowers the MSF even for the small value of T= 250 used here. The best trade-off between noise reduction and bias increase W 50.
4.2 The FDS algorithm
As it is presented in Section 3.3, forward-mode differentiation would still have memory cost that scales as (DT) since we are learning one hyperparameter per step. However, addressing gradient degradation by sharing hyperparameters also conveniently reduces that memory cost by a factor W down to (DN), where = T T/W is the number of unique hyperparameter values we learn. This because we can safely average hypergradients without calculating them individually, by reusing the same column of Z for W contiguous steps. This shown in Algorithm 1, when learning a schedule of No learning rates with FDS. Here, 4 refers the i-th column of matrix za We don't need to store H. or a in memory since we calculate the Hessian matrix product Z2 directly. Most importantly, note that hyperparameters aren't 't updated greedily or online, but are updated once per outer step, which corresponds to differentiating through the entire unrolled inner loop optimization and getting the exact hypergradients 0L.ai (OT) /8ax
The main of Algorithm comes from cal- culating 7 There exists several methods to approximate this product, but we found them too crude for long horizons. This includes first-order approximations or truncation [32], which can be adapted to FDS trivially. One could also use functional forms for more complex schedules to be learned in terms of fewer hyperparame- ters, but this typically makes stronger assump- tions about the shape of each hyperparameter schedule, which can easily cloud the true per- formance of HPO algorithms. In practice, we calculate H a exactly, and use a similar form to Algorithm I to learn a, f9 and
Algorithm 1 Simplified FDS algorithm when learning Na learning rates for the SGD optimizer with momentum. Each learning rate is shared over W contiguous time steps
Initialize: No, W =T/Na, a 0
#outer loop for in 1, 1,2,... ... do
Initialize: D Igin. D 0g R.D. 2 00 a Dx
#inner loop for in 1,2, ..., T do
Turain Uuain Derain
Iwain Ō (Ferain: Mraain ) 00
5 Experiments
#hyperparameter sharing
[t/W]
HZ [1:]] = O Z [1:6
)/00
Our experiments show how FDS mitigates gra- dient degradation and outperforms competing HPO methods for tasks with long horizon. In Sections 5.1 and 5.2 we consider small datasets (MNIST and SVHN) and a small net- work (LeNet) to make reverse-mode differentia- tion tractable, so that the effect of hyperparame- ter sharing can be directly measured. In Sections 5.3 and 5.4, we then showease FDS on CIFAR- 10 where only forward-ma mode differentiation is
Za = A Zii:a
B
[1:a]
update a (Eq 4) 0.41 (0,, Juain)
end for
Ival HCral D2a a f a - 0.1 x gval Za /W
end for

---

0.12
100
80
MNIST
noa geeggreedy
greedy
Test
baseline
FDS (ours)
90
test (96)
SINS
300
100 200
stops
Figure 3: The learning rate schedule a learned for the MNIST and SVHN datasets using a LeNet architecture over epoch. We observe that real-world datasets like SVHN, both greedy and non-greedy hyperparameter optimizations fail to learn decent learning rate schedules when using hypergradient per inner step. However, sharing learning rates contiguous steps stabilizes non-greedy hypergradients and allows us to find learning rates that can even outperform reasonable off-the-shell schedules in this setting.
tractable. All experiments are carried out on a single GTX 2080 GPU. More implementation details can be found in Appendix C.
5.1 The effect of hyperparameter sharing on hypergradient noise
We consider a LeNet network trained on an inner loop of T 250 gradient steps, and calculate the hypergradients of the learning rate across 100 seeds. Each seed is evaluated at the same value of a, but corresponds to a different training dataset ordering and weight initialization. We can calculate the hypergradients greedily (H 1) and non-greedily (H T). The optimal hypergradients considered to be the ensemble average of the non-greedy seeds as per Section 4.1, which allows MSE be calculated for each method. These results are shown in Figure 2 for learning rate schedule initialized to small values. We observe that greediness optimal hypergradients, and that time averaging contiguous hypergradients in the non-greedy can significantly reduce the MSE even when averaging over only W 50 steps.
poor approximation to the
The simplicity of this problem allows to calculate E, and as defined in Theorem 4.1, to verify that our upper bound holds and that its shape as a function of is realistic. the setting shown in Figure 2 we find max |4+1 Mel 0.08 and (1/T) Σ, En 0.25. The value of the maximum correlation between any two steps, c, can be quite high which makes the upper bound loose. In practice however, the shape of the upper bound in Theorem 4.1 function of W (as plotted in Appendix B) closely matches that the measured MSE shown in Figure 2. Note that the values of e, E, and e vary depending on the value of a. As illustrated in Theorem 4.1, find that settings that have smaller values of é benefit from a larger W and reduce the MSE more (see Appendix D) for more examples).
5.2
The effect of hyperparameter sharing on HPO
In the section above, we considered hypergradient noise around a fixed hyperparameter setting. In this section, consider how that noise and its mitigation translate to meta-learning hyperparameters over several outer steps.
In Figure 3, we initialize a 0 and train LeNet network over epoch (7 500 gradient steps) on MNIST and SVHN. We compare the maximally greedy setting (H = 1), the non-greedy setting (H 7), and FDS (also H T but with sharing of W 50 contiguous hyperparameters) In

---

X30-1
0.25
30
0.3
0.2
FDS (ours)
0.1
0.10
(gready)
0.00
spochs
epocchs
egoochs
oppchs
Figure 4: FDS applied to the SGD optimizer to learn (from left to right) the learning rate schedule a, the momentum B, and weight decay & for a WRN-16-1 on CIFAR-IO. For each outer step (color) solve 110AR-10 from scratch for 50 epochs, and update all hyperparameters such that the final weights minimize some validation loss. We use hyperparameter sharing over W = 10, 50 and 50 epochs for 3 and & respectively. All hyperparameters are initialized to and converge within just 10 outer steps to values that significantly outperform Hypergradient Descent (HD) [14], the greedy alternative. We match the performance of the best known hyperparameters in that setting and do so much faster than state-of-the-art black-box methods (see Section 5.4).
all cases take 50 outer steps per hyperparameter. We make greediness transparent by not using tricks as in Hypergradient Descent [14], where ar is set to 0x-1 before its hypergradients calculated, As previously observed by [15], greedy optimization leads poor solutions with learning rates that are always too small. While the non-greedy setting without sharing works well for simple datasets like MNIST, fails for real-world datasets like SVHN, converging to much higher learning rates than reasonable. This is due to gradient degradation, whose negative effect can compound during outer optimization, as single large learning rate can increase the hypergradient noise for neighbouring steps. As we share hyperparameters in FDS, we reduce and stabilize the outer optimization. This allows us learn much more sensible learning rate schedule, which can even outperform reasonable cosine annealing off-the- thellf schedule on SVHN.
5.3 FDS on CIFAR-10
We demonstrate that our algorithm can be used to learn the learning rate, momentum and weight decay over 50 epochs of CIFAR-10 (H 104) for a WideResNet of 16 layers (WRN-16-1). We choose not to use larger architectures or more epochs to enable compute time for more extensive comparisons and because hyperparameters matter most for fewer epochs. Note also that we are not interested in finding the architecture with the best performance, but rather in finding the best hyperparameters given an architecture. For the learning rate, we choose such that the ratio of T T/W similar the optimal one found in 5.1, and set W T for the momentum and weight decay since only single value commonly used for these hyperparameters. The schedules learned are shown in Figure 4, which demonstrates that FDS converges in just 10 outer steps to hyperparameters that are very different to online greedy differentiation [14], and correspond to significantly better test accuracy performances. Note that having the maximum learning rate be large and occur half way during training reminiscent of the one-cycle schedule [53].
5.4 FDS compared to other HPO methods
A common theme in meta-learning research has been the lack of appropriate baselines, with re- searchers often finding that random search (RS) can outperform complex search algorithms, for instance in NAS [54] or automatic augmentation [55]. In this section we compare FDS to several competing HPO methods on CIFAR-10, in both the performance of the hyperparameters found and the time it takes to find them. We consider Random Search (RS), Bayesian Optimization (BO), Hypergradient Descent (HD) [14], HyperBand (HB) [12] and the combination of BO and HB, namely BOHB [13]. The latter is typically regarded as sfate-of-the-art in HPO. We use the official HpBandster [56] implementation of these algorithms, except for HD which we re-implemented ourselves.

---

The performance of HPO methods is often clouded by very small search ranges, For instance, in [13] the learning rate searched over the range [10 110-6,10-10 10_ In the case of DARTS [38], expanding the search space to include many poor architectures has helped diagnose issues with its search algorithm [57]. For these reasons, we assume only weak priors and consider large search ranges: a [-1,1], 3 E [-1.5, 1.5), and 5 E [-4 10-3, .4 x 10-3), which includes many poor hyperparameter values. In FDS we can specify search ranges by using a fixed update size Y to the hyperparameters, which decays by 2 every time the hypergradient flips sign, which is common in sign based optimizers [58-61]. We found that black-box HPO methods did not scale well to more than ~ 10 hyperparameters for such large search ranges, and considered learning 7 learning rates, 1 momentum and weight decay over 50 epochs. Note that increasing these numbers doesn't 't affect the accuracy of FDS but significantly reduces that of RS, BO, HB and BOHB. The performance over time of the hyperparameters found by each method is shown in Figure 1. As is common in HPO, plot regret (in test accuracy) with respect to the best hyperparameters known in this setting, which we obtained from an expensive grid search around the most common hyperparameters used in the literature (more details in Appendix F). To squeeze the optimal performance this experiment, we match the process used in HB and BOHB, namely using smaller budgets for some runs, in particular early ones. We can see that our method reaches zero regret in just 3 hours, while the next best method (BOHB) reaches zero regret in 60 hours. Other methods did not reach zero regret in the maximum of 100 hours they were run for. Note also that we retain the convergence speed of online greedy differentiation [14] while outperforming its regret by ~ 10% test accuracy.
of FDS in
6 Discussion
FDS is significantly better than modern HPO alternatives the case of learning differentiable hyperparameters over long horizons. Its main advantage over black-box methods is its convergence speed, and its main advantage over other gradient- methods is that it's non- non-greedy. Furthermore, forward-me mode differentiation can provide exact hypergradients for any differentiable hyperparameter, contrary to some other approaches like implicit differentiation which approximates hypergradients, and can do so for certain types of differentiable hyperparameters only.
Nonetheless, is worth pointing out the main limitations of FDS. First, black-box methods are slower but can readily tackle donfdiffere hyperparameters, while FDS would need to use relaxation techniques to differentiate through, say, discrete variables. Then, the computational and memory cost of FDS scales linearly with the number of hyperparameters. For instance, for WideResNet of 16 layers we are limited in memory to ~ 10 hyperparameters on a single GB GPU, which falls short of reverse-mode- mode-based greedy methods which scale to millions of hyperparameters. Finally, while automatic forward-modk diffcrentiation is becoming available for some toolboxes like JAX [62], it remains unavailable for the most popular deep learning libraries, which means that some pen-and-pape work is still required to derive hypergradients for given hyperparameters (Eq 4).
The focus of our future work will be on adapting FDS to the many meta- meta-learning applications that rely on greedy optimization, such as differentiable architecture search, to improve their performance by making them non-greedy.
7 Conclusion
This work makes an important step towards gradient-based HPO for long horizons by introducing FDS, which enables non non-greediness through the mitigation of gradient degradation. More specifically, we theorize and demonstrate that sharing hyperparameters over contiguous time steps is a simple yet efficient way reduce the error in their hypergradients; setting which naturally lands itself to forward-mode differentiation. Finally, we show that FDS outperform greedy gradient-based alternatives in the quality of hyperparameters found, while being significantly faster than all state- of-the-art black-box methods. We hope that our work encourages the community to reconsider gradient-based HPO in terms of non-greediness, and pave the way towards a universal hyperparameter solver.

---

The authors would like to thank Joseph Mellor, Antreas Antoniou, Miguel Jaques, Luke Darlow and Benjamin Rhodes for their useful feedback throughout this project. Our work was supported in part by the EPSRC Centre for Doctoral Training in Data Science, funded by the UK Engineering and Physical Sciences Research Council (grant EP/L001427/1) and the University of Edinburgh, as well as Huawei DDMPLab Innovation Research Grant.
Acknowledgements
References
[1] K. He, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition," in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016.
[2] A. Brock, J. Donahue, and Simonyan, "Large scale GAN training for high fidelity natural image synthesis," in International Conference on Learning Representations, 2019.
[3] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, "Bert: Pre-training of deep bidirectional transformers for language understanding," arXiv preprint arXiv: 04805, 2018.
[4] A. v. d. Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalchbrenner, A. Senior, and K. Kavukcuoglu, "Wavenet: A generative model for raw audio," arXiv preprint arXiv: 03499, 2016.
[5] D. P. Kingma and J. Ba. "Adam: A method for stochastic optimization." in International Conference on Learning Representations (Y. Bengio and Y. LeCun, eds.), 2015.
[6] I. Loshchilov and F. Hutter, "Sgdr: Stochastic gradient descent with warm restarts," in Interna- tional Conference on Learning Representations, 2017.
[7] M. Li, E. Yumer, and D. Ramanan, "Budgeted training: Rethinking deep neural network training under resource constraints," in International Conference on Learning Representations, 2020.
[8] P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He, "Accurate, large minibatch sgd: Training imagenet in 1 hour," arXiv preprint 1706.00770 2017.
[9] X. Dong, M. Tan, A. W. Yu, D. Peng. B. Gabrys, and Q. V. Le, "Autohas: Differentiable prper-paraette and architecture search," 2020.
[10] Loshchilov and F. Hutter, "Decoupled weight decay regularization," in International Confer- ence on Learning Representations, 2019.
[11] S. loffe and C. Szegedy, "Batch normalization:
Accelerating deep network training by reducing internal covariate shift," in International conference on Machine Learning (F. Bach and D. Blei, eds.), Proceedings of Machine I learning Research, (Lille, France), PMIR, 07-09 Jul 2015.
[12] L. Li, K. G. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar, "Hyperband: A novel bandit-based approach to hyperparameter optimization," J. Mach. Learn. Res., vol. 18, pp. 185:1-185:52, 2017.
[13] S. Falkner, A. Klein, and F. Hutter, "BOHB: Robust and efficient hyperparameter optimization scale," in Proceedings of the 35th International Conference on Machine Learning, pp. 1436-
1445, 2018.
[14] A. G. Baydin, R. Cornish, D. M. Rubio, M. Schmidt, and F. Wood, "Online learning rate adap- tation with hypergradient descent," " in International Conference on Learning Representations, 2018.
[15] Y. Wu, M. Ren, R. Liao, and R. Grosse., "Understanding short-horizon bias in stochastic meta-optimization," in International Conference on Learning Representations, 2018
[16] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil, "Forward and reverse gradient- based hyperparameter optimization," in International conference Machine Leurning (D. Precup and Y. W. Teh, eds.), Proceedings of Machine Learning Research, (International Convention Centre, Sydney, Australia), PMLR, 06-11 Aug 2017.
[17] M. Donini, L.. Franceschi, M. Pontil, O. Majumder, and P. Frasconi, "Scheduling the Learning Rate via Hypergradients: New Insights and New Algorithm,"" arXiv e-prints, Oct. 2019.
[18] M. Feurer and F. Hutter, Chapter I: Hyperparameter Optimization. Cham: Springer Interna- tional Publishing, 2019.
10

---

[19] J. Snoek, O. Rippel, K. Swersky, R. Kiros, N. Satish, N. Sundaram, M. Patwary, M. Prabhat, and R. Adams, "Scalable bayesian optimization using deep neural networks," in International conference on Machine Learning, 2015.
[20] B. Zoph and Q. V. Le, "Neural architecture search with reinforcement learning," in International Conference on Learning Representations, 2017.
[21] M. Jaderberg, V. Dalibard, S. Osindero, W. M. Czarnecki, J. Donahue, A. Razavi, O. Vinyals, T. Green, I. Dumning, K. Simonyan, et al., "Population based training of neural networks," arXiv preprint arXiv:/711.09e0 2017.
[22] Y. Bengio, "Gradient-based optimization of hy heerpaarameters""" Neural Comput., Aug. 2000.
[23] Hospedales, Antoniou, Micaclli, and A. Storkey, "Meta-learning in neural networks: survey," arXiv preprint arXiv:2004.054533 2020.
[24] C. Finn, P. Abbeel, and S. Levine, "Model-agnostic meta-learning for fast adaptation of deep networks," in Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017 (D. Precup and Y. W. Teh, eds.), vol. 70 of Proceedings of Machine Learning Research, pp. 1 1126-1135 1135, PMLR, 2017.
[25] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil, "Bilevel programming for hyperparameter optimization and meta-learning," in International conference on Machine Learning. 2018
[26] J. Werbos, "Backpropagation through time: what it does and how to do it," Proceedings of the IEEE, 1990.
[27] R. J. Williams and D. Zipser, "A learning algorithm for continually running fully recurrent neural networks," Neural Computation, 1989.
[28] Domke, "Generic methods for optimization-based modeling." in International Conference on Artificial Intelligence and Statistics (N. D. Lawrence and M. Girolami, eds.), Proceedings of Machine Learning Research, (La Palma, Canary Islands). PMLR, 21-23 Apr 2012.
[29] D. Maclaurin, D). Duvenaud, and R. P. Adams, "Gradient-based Hyperparameter Optimization through Reversible Learning," arXiv e-prints, Feb. 2015.
[30] F. Pedregosa, "Hyperparameter optimization with approximate gradient," in International conference Machine Learning, 2016.
[31] J. Fu, H. Luo, J. Feng, K. H. Low, and T.-S. Chua, "Drmad: Distilling reverse-mode automatic differentiation for optimizing hyperparameters deep neural networks," in IJCAI, 2016.
[32] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots, "Truncated back-propagation for bilevel optimization," in AISTATS, 2019.
[33] J. Larsen, L. K. Hansen, C. Svarer, and M. Ohisson, "Design and regularization of neural networks: the optimal use of a validation set," in Neural Networks for Signal Processing VI. Proceedings of the 1996 IEEE Signal Processing Society Workshop, pp. 62 71, 1996.
[34] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine, "Meta-learning with implicit gradients," in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2019.
[35] J. Lorraine, P. Vicol, and D. Duvenaud, "Optimizing Millions of Hyperparameters by Implicit Differentiation," arXiv e-prints, Nov. 2019.
[36] L. Metz, N. Maheswaranathan, J. Nixon, D. Freeman, and J. Sohl-Dickstein, "Understanding and correcting pathologies in the training of learned optimizers," vol. 97, pp. 1556-4565 09-15 Jun 2019.
[37] J. Luketina, M. Berglund, K. Greff, and T. Raiko, "Scalable gradient-based tuning of continuous regularization hyperparameters." in International conference on Machine Learning, 2016.
[38] H. Liu, K. Simonyan, and Yang, "DARTS: Differentiable architecture search," in International Conference Learning Representations, 2019.
[39] T. Wang, J. Zhu, A. Torralba, and A. A. Efros, "Dataset distillation," CoRR, vol. abs/18 1t./1811.100999 2018.
[40] M. Ren, W. Zeng, B. Yang, and R. Urtasun, "Learning to reweight examples for robust deep learning," in International conference on Machine Learning, 2018.
11

---

[41] Y. Bengio, P. Frasconi, and P. Simard, "The problem of learning long-term dependencies in recurrent networks," IEEE International Conference on Neural Networks, 1993.
[42] Y. Bengio. P. Simard, and P. Frasconi, "Learning long-term dependencies with gradient descent is difficult," JEEE Transactions on Neural Networks, 1994.
[43] P. Parmas, C. E. Rasmussen, J. Peters, and K. Doya, "PIPPS: Flexible model-based policy search robust to the curse of chaos," vol. 80 of Proceedings of Machine Learning Research, (Stockholmsmässann Stockholm Sweden), pp. 4065-4074, PMLR, 10-15 Jul 2018.
[44] S. Hochreiter and J. Schmidhuber, "Long short-term memory," Neural computation, 1997.
[45] R. Pascanu, T. Mikolov, and Y. Bengio, "On the difficulty of training recurrent neural networks," in International conference on Machine Learning, 2013.
[46] S. Flennerhag. A. A. Rusu, R. Pascanu, F. Visin, H. Yin, and R. Hadsell, "Metanlearning with warped gradient descent," in International Conference Learning Representations, 2020.
[47] S. Zagoruyko and N. Komodakis, "Wide residual networks," in BMVC, 2016.
[48] H. Stackelberg, The Theory Of Market Economy. Oxford University Press, 1952.
[49] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. VeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, "Pytorch: An imperative style, nigh-performance deep learning library," in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2019.
[50] Walters, An Introduction to Ergodic Theory. Graduate texts in mathematics, Springer- Verlag, 1982.
[51] L. Boltzmann, Vorlesungen uber Gastheorie. J.A. Barth, 1896.
[52] O. Peters, "The ergodicity problem in economics," Nature Physics, vol. 15, pp. 1216-1221, Dec 2019.
[53] L. N. Smith and N. Topin, "Super-convergene Very fast training of residual networks using large learning rates," CoRR, vol. abs/1708.07 000880712000 2017.
[54] L. Li and A. Talwalkar, "Random search and reproducibility for neural architecture search," in UAI, 2019.
[55] E. D. Cubuk, B. Zoph, J. Shlens, and Q. V. Le, "Randaugment: Practical automated data augmentation with reduced search space." " 2020 IEEE/CVF Conference Computer Vision 2020.
and Pattern Recognition Workshops (CVPRW), pp.
[56] A. Klein. 2019.
html, -gi io httpaa/tttteeeualaaaaaaaaa//a/aa
[57] A. Zela, T. Elsken, T. Saikia, Y. Marrakchi, T. Brox, and F. Hutter, "Understanding and robustify- ing differentiable architecture search," in International Conference on Learning Representations, 2020.
[58] "Increased rates of convergence through learning rate adaptation," " Neural Networks, vol. 1, 4, pp. 295-307, 1988.
[59] M. Riedmiller and H. Braun, "A direct adaptive method for faster backpropagation learning: the rprop algorithm," in IEEE International Conference on Neural Networks, pp. 586-591 vol.1, 1993.
[60] J. Bernstein, Y. Wang, K. Azizzadenesheli, and A. Anandkumar, "SIGNSGD: compressed optimisation for non-convex problems." in Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmüsson, Stockholm, Sweden, July 10-15, 2018 (J. G. Dy and A. Krause, eds.), vol. of Proceedings of Machine Learning Research, pp. 359-568. PMLR, 2018.
[61] M. Safaryan and P. Richtárik, "On Stochastic Sign Descent Methods," " arXiv e-prints,
p. 1.Xiv:1905.1299. May 2019.
[62] J. Bradbury, R. Frostig, P. Hawkins, M. Johnson, C. Leary, D. G. Necula, A. Paszke,
J. VanderPlas, S. iiniderrmn--iinnee and Q Zhang, "JAX: composable transformations of Nuthon+NumPPy programs," 2018.
12


Reviews:
[{"review_id": "oe9JYQ8uJov", "reviewer": "Reviewer_3Csr", "summary": "This paper studies the problem of gradient based hyperparameter optimization.\n\nThe paper makes a distinction between \"greedy\" (truncated horizons) and \"non-greedy\" (full horizon) hypergradients. The problem with greedy methods is that they are biased, while non-greedy methods suffer from poor conditioning due to the long multiplication chains inherent in computing the hypergradient over many time steps (eq. 3). This poor conditioning means that with respect to variation in the inner problem (e.g. due to initialization and mini batch ordering), exact (full horizon) hypergradients will have high variance.\n\nThe paper proposes using forward mode autodiff to compute hypergradients, and choosing hyperparameters that are tied across multiple timesteps in order to reduce hypergradient variance.\n\nThe paper demonstrates the method by tuning learning rate schedules and momentum and weight decay hyperparameters on SVHN, MNIST, and CIFAR-10.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "I thought the paper was fairly well written, but I have a number of questions about the method.\n\nI think the problem of \"gradient degradation\" and how it induces variance in the hypergradient could be made clearer. As far as I can tell, the paper treats gradient degradation as the problem of exploding and vanishing gradients (poor conditioning), due to the long chain of multiplications that arises in the hypergradient computation. This poor conditioning subsequently causes two additional issues. First, trying to do gradient based hyperparameter optimization will be difficult due to poor conditioning of the hypergradients. This is an issue even if the inner problem is completely deterministic (e.g. fixed random seed). Second, when the inner problem has some stochasticity (in this paper, the stochasticity arises from random initialization and mini batch ordering of the inner problem), then the hypergradients will have high variance. Do the authors think of \"gradient degradation\" as purely the second point? That's kind of how that section is written (it equates degradation to high variance). But it seems to me like the poor conditioning itself is also a big problem (even when there is no variance in the hypergradient), and one that the proposed method does not address (since the proposed method is focused on how to compute the hypergradient, not what to do with it). Do the authors agree with this statement? If not, what am I missing?\n\nThe \"time-averaging\" approach proposed in this paper is motivated as a way of reducing the variance of the hypergradient. I was confused as to which hypergradient this is referring to. Over a window of size W, there will be W different hypergradients. Averaging these gives a new hypergradient, which is said to have lower variance - but lower than what? What is the other gradient estimate that is used for comparison for this statement? Is it each of the individual hypergradients in the window?\n\nIn Figure 3, the learned schedule quenches the learning rate right at the end of training. Is this some artifact of having a fixed number of steps in the inner loop while learning the hyperparameters? If you train for longer, does that schedule become suboptimal?\n\nAlso in Figure 3, how come the non-greedy curve does so poorly for SVHN? Is it because the non-greedy gradients are high variance? What happens if you decrease the outer-loop learning rate?\n\nIt would be nice if the paper provided some intuition or guidance for when and how to choose the window size W. Are there cases where it is better to use the full (non-greedy) hypergradient? Does this method only work when the optimal underlying hyperparameter (e.g. optimal learning rate schedule) varies smoothly over iteration, so that chunking the hyperparameters into windows is not too harmful?\n\nFinally, it would be much more convincing if the paper would greatly expand the set of problems used to test the method. Does this work for training other hyperparameters, outside of optimizer hyperparameters for training convolutional neural nets?\n\nOther minor questions:\n- Did you try using a rolling window (instead of fixed windows) to average hypergradients?\n- In Figure 2a, do you have intuition for why the particular curve looks the way it does (with non-monotonic behavior)? Why are there two humps in the curve, one early in training and one close to the end?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "d-Mzz8eKg0", "reviewer": "Reviewer_E74o", "summary": "This paper tackles the problem of gradient-based optimization of hyperparameters over long training horizons, considering specifically optimizer hyperparams like learning rates (schedules), weight decay, and momentum, which are not easily optimized by scalable implicit differentation approaches. \n\nThe paper proposes to use  forward-mode (FM) differentiation to learn these hyperparameters, and contributes an algorithm to do so. FM differentiation  has the advantage that it scales better with memory over long horizons, unlike reverse-mode exact differentiation through the learning process. \n\nIn experiments, the paper  demonstrates that it does not suffer from the problems that greedy/online hyperparameter optimization approaches might face, and that it can be much more time efficient than gradient-free approaches like bayesian optimisation.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The approach taken by the work is original: they combine work on forward mode differentiation with a nice strategy for reducing gradient degradation through the use of time-sharing hyperparameters. This naturally leads to the learning of e.g. learning rate schedules for optimizers.  They also provide a clear empirical study of the potential problems with greedy/online approaches for hyperparameter optimization.  The theoretical analysis in the paper of gaussian hypergradients and the associated reduction in MSE is clear, and is well-supported by Figure 2, right.\n\nThe paper has a clear algorithmic contribution and also good empirical results on MNIST, SVHN, and CIFAR-10. It is also written clearly and the results are well-presented. However, there are certain things that would be good to improve:\n\n- The paper's abstract refers to general hyperparameters, whereas the paper itself mainly concerns itself with a small set of optimizer hyperparameters, and that too focuses on only SGD with momentum/weight decay. It would be good to clarify the scope in the abstract, and also include some further experiments on other optimizers at least (eg Adam), to demonstrate that improvements can still be obtained in other settings. If there are other low-dimensional hyperparameters that could be analysed, that would make the paper a lot stronger too.\n- The results are mostly on three smaller-scale datasets; it would be good to at least include one or two other settings. For example, some similar results on CIFAR-100 or CUB-200 would make this paper stronger.\n- Minor: error bars on Fig 1 might be good to get a sense of variation across seeds.\n- Very minor: on line 193, is T hyperparameters a typo?\n\nOverall, I think this is a good paper, but it would benefit from some further experimental study, so for now it is just below the acceptance threshold. If the authors can clarify the scope, and run  experiments on another optimizer/one other dataset, I am happy to raise my score.\n\n# Update post author response\nThank you very much for your answers to my questions! The comments regarding testing on Adam and CIFAR-100 make sense -- if these could be included in the appendix of the final paper, that would be great. Similarly with the error bars -- I understand that it will make the figure harder to read, so perhaps an appendix version of this figure with the detail would be nice to include.  I am raising my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes -- a good discussion of these. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LBF74e_gOZK", "reviewer": "Reviewer_MsYr", "summary": "Real-time recurrent learning (RTRL) is a useful approach for computing the gradient of hyperparameters through an inner optimization problem, because its memory usage does not scale with the length of the task. This paper introduces a method for hyperparameter optimization called Forward-Mode Differentiation with Sharing (FDS). The main contribution in FDS is the notion of sharing the same hyperparameter over a contiguous chunk of steps of the inner optimization, to achieve a kind of averaging over weights and minibatches. The paper discusses the trade-off between reducing noise and increasing bias when sharing hyperparameters over more contiguous steps: it provides an upper bound on the error of the approximate hypergradient when averaging across chunks of time, compared to the optimal hypergradient. The authors evaluate FDS on MNIST, SVHN, and CIFAR-10, using LeNet and WideResNet-16-1; they use FDS to tune the learning rate, momentum, and weight decay for SGD+momentum. They show some illustrative small-scale experiments looking at the approximate hypergradients obtained with different methods, and visualizing the adaptation of learning rates over outer optimization steps by their method. They also compare hyperparameter optimization performance of FDS against several popular black-box methods, including random search, BayesOpt, Hyperband, BOHB, and hypergradient descent.", "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": "Pros\n----\n* The paper is well-written; the method is described clearly.\n* The discussion of related work is pretty comprehensive, covering relevant black-box and gradient-based hyperparameter optimization.\n* It is nice that the proposed approach (FDS) is able to obtain useful hypergradients over many inner optimization steps for a fairly large real-world model and task, training a ResNet on CIFAR-10.\n* The authors provide a theorem quantifying the error of the FDS-estimated hypergradient (using shared hyperparameters over continugous chunks of inner training) compared to the true hypergradient, based on the horizon length over which hyperparameters are shared.\n* Figure 2 is a nice visualization of the optimal vs \"greedy\" and \"non-greedy\" hypergradients.\n* The rightmost plot in Figure 2 is also very interesting as it demonstrates that the best choice of chunk size is an intermediate value, which makes sense in terms of balancing between reducing noise and increasing bias.\n* Provides comparisons to real-world methods for hyperparameter optimization, including random search, BayesOpt, Hyperband, Bayesopt-Hyperband (BOHB), and hypergradient descent (HD). However, I have concerns regarding the search spaces for these comparisons.\n\n\nIssues and Questions\n--------------------\n* L178-179: \"can be applied to any differentiable hyperparameter, albeit with appropriate A_t and B_t matrices\"\n    - Do you have to define these matrices manually? Why is this the approach used in the paper? It should be possible to define a differentiable version of any optimizer (such as SGDm, RMSprop, or Adam), and use autodiff to compute gradients rather than manually specifying matrices for use in forward-mode for each potential optimizer.\n\n* L360-362: \"forward-mode doesn't come in an automatic-differentiation package yet, like reverse differentiation\"\n    - You can do forward-mode via reverse-on-reverse in any package that supports reverse-mode (as described here: https://j-towns.github.io/2017/06/12/A-new-trick.html). Also, libraries like JAX include explicit support for forward-mode differentiation. This goes together with my question above about why it is necessary to hand-derive the update rules for different hyperparameters?\n\n* The method is strange in that depending on the horizon over which hyperparameters are shared, the learned schedule is more or less fine-grained (since each chunk effectively has its own hyperparameters). I think it makes the most sense to consider learning a fixed outer parameter for the entire inner training procedure: this fixed outer parameter can still be high-dimensional, and can parameterize a learning rate schedule (e.g., a linear schedule).\n\n* L342: \"we match the process used in HB and BOHB, namely using smaller budgets for some runs, in particular early ones\"\n    - It would be good to have more detail about how this was done: why were some runs of FDS stopped early? Did the runs diverge? Or was there a manual or automatic curriculum that progressively increased the inner problem length?\n\n* In Figures 1, 3, and 4, it would also be useful to show the validation losses achieved by each method, since this is what is being optimized by FDS.\n\t- For clarity, what objective is being optimized by the black-box approaches in Figure 1, is it validation loss or validation accuracy?\n\n* The search spaces for the learning rate and momentum coefficient in Section 5.4 are strange: it looks like the range for the LR is [-1, 1], which includes negative LRs? Coupled with the fact that there are 7 learning rates to learn, I would imagine that choosing any of the 7 LRs to be negative would substantially harm performance, making it hard for many of the methods (RS, BO, HB, and BOHB) to find good hyperparameters, since they would try he extremes of each range and frequently sample at least one negative LR, which would likely cause training to diverge.\n    - Also, what were the initializations of the hyperparameters for FDS? From the algorithm, it looks like the initial hyperparameters are 0, which sounds good. But would FDS recover from starting with a random initialization in the range [-1, 1] for the LR or momentum?\n    - I think it would be good to see the same experiment but with learning rates in a range like [0,1] or [0,10] for all methods.\n    - Another question is how the hyperparameter ranges were parameterized (e.g., are the LRs searched over in log-space)?\n\n* Does FDS use any mapping to constrain the values of different hyperparameters, such as exponential, sigmoid, or softplus transforms?\n\n* Why do the experiments consider 7 learning rates but only 1 momentum and 1 weight decay value? Why not also try schedules for the momentum and weight decay?\n\n* FDS is based on forward-mode differentiation, and is thus related to forward-mode hyperparameter optimization approaches such as RTHO [1] and MARTHE [2]. I think it would help to clarify the discussion of \"greediness\" of these approaches: I don't think greedy is necessarily the right terminology, since one of the main purposes of RTRL is to allow for online updates to the parameters of a system while remaining unbiased; of course, it is well-known that in order to obtain the true gradient of the parameters when using online updates, one would need to use vanishingly small step sizes. I think the effect of online updates in RTRL would be better referred to as \"hysteresis\" rather than \"greediness.\" (When training RNNs, one of the main advantages of RTRL compared to TBPTT is the ability to make unbiased online updates; the RNN is never unrolled over a full sequence before making a parameter update.)\n\t- I also think it would be good to explicitly compare to RTHO and MARTHE as gradient-based approaches in the experiments.\n\t- How well would FDS work if you updated the hyperparameters after each horizon H rather than only once at the end of the full length T run?\n\n* Since FDS is gradient-based, it would be good to show how it scales with the number of hyperparameters, for example per-layer learning rates. Did the authors try this? Or maybe this is too costly in terms of memory, since the RTRL Jacobian has dimension (# model params x # hyperparams), which is fine.\n\n[1] Franceschi et al., \"Forward and Reverse Gradient-Based Hyperparameter Optimization\" ICML 2017.\n\n[2] Donini et al., \"MARTHE: Scheduling the Learning Rate Via Online Hypergradients\" IJCAI 2020.\n\n\nMinor\n-----\n* On Line 108, the notation is a bit confusing because $\\lambda \\in \\mathbb{R}^T$ implies that there is only a 1D hyperparameter used at each step, when there can be a vector of hyperparameters at each step; it would be clearer to write $\\lambda \\in \\mathbb{R}^{M \\times T}$, there $M$ is the number of hyperparameters.\n* L118: \"waves\" --> \"waives\"\n* L130: I'm not sure \"subspace\" is the right terminology here, because this has a specific mathematical definition. Is this sentence really referring to a subspace?\n* Use $\\mathcal{L}\\_{\\text{train}}$ rather than $\\mathcal{L}\\_{train}$\n\n\nPost-Rebuttal\n------------------\nI have read the all the reviews and the author responses. I thank the authors for their rebuttal. Overall, I still have some concerns about the search space for comparisons. Also, I think the discussion of greediness and RTRL should be improved, and the positioning of FDS should be made clearer.\n\nThe search space is still quite strange, because it is a bit extreme to consider a space of [-1, 1] for learning rates; if the goal is to make the space uninformative, then why not [-100, 100]? I have not seen any prior work that uses a search space that goes into negative learning rates. Also, not using a log-scaled parameterization for this search space makes it very improbable that any of the baselines will find a good LR (even more so if one tried to tune the LR for Adam, where the optimal LR would be somewhere around 1e-3 or 1e-4). Learning rates (and also weight decay coefficients) are typically represented in log-space because reasonable values often range over several orders of magnitude. One would expect that using log-space would even benefit FDS, since it would more easily fine-tune the learning rate.\n\nI think the main contribution of this paper is an investigation into the effect of using different numbers of chunks over which to share hyperparameters in an inner optimization problem, when using forward-mode differentiation for hyperparameter optimization. That is, the paper looks at a slight modification of RTRL.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have mostly addressed the limitations of their work. (E.g., they point out that FDS is not applicable to discrete hyperparameters (unless we use relaxations.)", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "-QhlGH1Y4WB", "reviewer": "Reviewer_7zoB", "summary": "The paper proposes a gradient based technique for efficient long horizon hyper-parameter optimization. The problem is quite important and the paper discusses the existing techniques and their shortcomings quite well. \n\nThe authors propose a technique which utilises forward-mode Automatic differentiation (AD). This helps overcome the gradient degradation which occurs in greedy gradient based hyper-parameter optimization methods like Hyper-gradient descent. \n\n", "questions": "", "limitations": "", "rating": 6, "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": "- Hyper-parameter optimization over long gradients is an important problem. The authors exploit forward mode differentiation to design a memory and compute efficient algorithm for the problem. The idea is good and authors show its effectiveness with good experimentation.\n\n- The theoretical results and the discussions presented also back the hypothesis. \n\n- The authors conduct thorough experiments and compare with a wide range of state-of-the-art baselines.\n\n- The writing is also good. A figure showing a pictorial representation for the parameter sharing across time and forward-mode AD could be helpful.\n\n- So PyTorch does not have forward mode differentiation. A lack of forward mode differentiation in common autodiff packages might make the adoption of this method a bit difficult. But I think this is a step in the right direction and it would be helpful for the community.\n\n- But can you check if JAX or AutoGrad has forward mode differentiation implemented?\n\n===========================================================\n#### POST REBUTTAL\n\nThanks to the authors for their response. After going through the discussion, I have decided to retain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed this quite well.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this paper proposed a useful method. Some questions regarding clarity, implementation and experiments were raised but addressed by the authors in the rebuttal phrase. Some reviewers have made suggestions to improve clarity and presentation of the results which I urge the authors to take into account for the camera ready version. 
Decision: Accept (Poster)