Scalable One-Pass Optimisation of High-Dimensional Weight-Update Hyperparameters by Implicit Differentiation
Authors: Ross M Clarke
Elre Talea Oldewage
José Miguel Hernández-Lobato
Venue: ICLR 2022 Spotlight (2022)
Keywords: Hyperparameter Optimisation

Abstract: Machine learning training methods depend plentifully and intricately on hyperparameters, motivating automated strategies for their optimisation. Many existing algorithms restart training for each new hyperparameter choice, at considerable computational cost. Some hypergradient-based one-pass methods exist, but these either cannot be applied to arbitrary optimiser hyperparameters (such as learning rates and momenta) or take several times longer to train than their base models. We extend these existing methods to develop an approximate hypergradient-based hyperparameter optimiser which is applicable to any continuous hyperparameter appearing in a differentiable model weight update, yet requires only one training episode, with no restarts. We also provide a motivating argument for convergence to the true hypergradient, and perform tractable gradient-based optimisation of independent learning rates for each model parameter. Our method performs competitively from varied random hyperparameter initialisations on several UCI datasets and Fashion-MNIST (using a one-layer MLP), Penn Treebank (using an LSTM) and CIFAR-10 (using a ResNet-18), in time only 2-3x greater than vanilla training.

Published as a conference paper at ICLR 2022
SCALABLE ONE-PASS OPTIMISATION OF HIGH-DIMENSIONAL WEIGHT- UPDATE
HYPERPARAMETERS BY IMPLICIT DIFFERENTIATION
Ross M. Clarke University of Cambridge rmc 88 cam. ac. uk
Eire T. Oldewage
José Miguel Hernández-Lobane University of Cambridge Alan Turing Institute
University of Cambridge vt cam. ac. uk
jmh2338cam ac uk
ABSTRACT
Machine learning training methods depend plentifully and intricately hyperpa- rameters, motivating automated strategies for their optimisation. Many existing algorithms restart training for each new hyperparameter choice, at considerable computational cost. Some hypergradient-baset one-pass methods exist, but these either cannot be applied to arbitrary optimiser hyperparameters (such as learning rates and momenta) or take several times longer to train than their base models. We extend these existing methods to develop an approximate hypergradient-br based hyperparameter optimiser which is applicable to any continuous hyperparameter appearing in a differentiable model weight update, yet requires only one training episode, with restarts. We also provide motivating argument for convergence to the true hypergradient, and perform tractable gradient-based optimisation independent learning rates for each model parameter. Our method performs compet- itively from varied random hyperparameter initialisations on several UCI datasets and Fashion-MNIST (using lny-layer MI.P), Penn Treebank (using LSTM) and CIFAR-10 (using a ResNet-18), 18), in time only 2-3x greater than vanilla training.
INTRODUCTION
Many machine learning methods are governed by hyperparameters: quantities other than model parameters or weights which nonetheless influence training (e.g. optimiser settings, dropout probabili- ties and dataset configurations). As suitable hyperparameter selection is crucial to system performance (e.g. Kohavi & John (1995)), it a pillar efforts to automate machine learning (Hutter et al., 2018, Chapter 1). spawning several hyperparameter optimisation (HPO) algorithms (e.g. Bergstra & Bengio (2012); Snock et al. (2012; 2015); Falkner et al. (2018)). However, HPO is computationally intensive and random search is unexpectedly strong (but beatable; Turner et al. (2021)) baseline; beyond random or grid searches, HPO is relatively underused in research (Bouthillier & Varoquaux, 2020).
Recently, Lorraine al. (2020) used gradient- based updates adjust hyperparameters during training, displaying impressive optimisation performance and scalability to high-dimensional hyperparameters. Despite their computational efficiency (since updates occur before final training performance is known), Lorraine et al. 's algorithm only applies to hyperparameters on which the loss function depends explicitly (such as lg regularisation), notably excluding optimiser hyperparameters.
Our work extends Lorraine et al.'s algorithm to support arbitrary continuous inputs to a differentiable weight update formula, including learning rates and momentum factors. We demonstrate our algo- rithm handles a range of hyperparameter initialisations and datasets, improving test loss after a single training episode ('one pass'). Relaxing differentiation ceartttiin-troouu--ooo bbrough-optimisation (Donke, 2012) and hypergradient descent's 's (Baydin et al., 2018) exactness allows us to improve computational and mem- ory efficiency. Our scalable one-pass method improves performance from arbitrary hyperparameter initialisations, and could be augmented with a further search over those initialisations if desired.
2 WEIGHT-UPDATE HYPERPARAMETES TUNING
In this section, we develop our method. Expanded derivations and a summary of differences from Lorraine al. (2020) are given in Appendix C.

---

Published as a conference paper at ICLR 2022
Training Loss Cr(A. w)
Validation Loss Lv w)
Aw BCr
AA X
dey
dA
AN X
dey
dx
Hyperparameter A
W (2)
Hyperparaneter
CT A0; w)
min Cr A w
Weight w
Weight w
min w Ly (A, w)
projected onto
corresponding loss surface
(a) Training Space
(b) Validation Space
Figure I: Summary of our derivation (Section 2): an example of online hypergradient descent using exact hypergradients from the implicit function theorem (IFT) (+). with our method', 's approximate hypergradients (-+ superimposed. We target optimal validation loss (o), adjusting weights w based on the training loss. Classical weight updates (for fixed hyperparameters À) converge ( --))
to the best-response line w w*(A) minimum of validation loss along w" (A). Our approximate hyperparameter updates ( () differ in
); the IFT gives hyperparameter updates (~)) leading to
magnitude from these exact updates, but still give useful guidance.
2.1 IMPLICIT FUNCTION THEOREM BILEVEL OPTIMISATION
Consider some model with learnable parameters w, training loss Lr. optimisation hyperparameters and validation loss Ly. We use w w', A* to represent the optimal values of these quantities, found by solving the following bilevel optimisation problem:
arg min Lv (A, wn (A)),
such that
(b) w''w (A) = arg min (A, w).
(1)
The optimal model parameters w* may vary with X, making Lv an implicit function of À alone.
approach the outer optimisation (la) similarly to Lorraine al. (2020) and Majumder al. (2019), using the hypergradient: the total derivative of Lv with respect to the hyperparameters X. One strategy for solving (1) is therefore to alternate between updating w for several steps using åCr and updating À using the hypergradient, as shown in Figure (by and -+).
dw
Carefully distinguishing the total differential dA and the partial differential ax, we have dLy
aLv
OLv Ow" ax
Ow"
yd aA
While derivatives of Lv are easily computed for typical loss functions, the final derivative of the optimal model parameters (2w") presents some difficulty. Letting square brackets indicate the evaluation of the interior the subscripted values, we may rewrite dw" follows:
Theorem (Cauchy's 's Implicit Function Theorem (IFT)) Suppose for some X and w' that Ow N O. If dCr is continuously differentiable function with invertible Jacobian, then there Oow
(0Cr
exists a function w (A) over an open subset of hyperparameter space, such that X lies in the open
subset, 10w
(BCr)
A.w (X) = O and
Ow
8 LT
82 LT
0x
twÖwT
TWeXT
(*) is called the best response of (Figure 1). While (3) suggests a route to computing Uw" inverting potentially high-dimensional Hessian in w is not computationally tractable.
8x
2.2 APPROXIMATE BEST- RES-OEE DERIVATIVE
To develop and justify computationally tractable approximation (3), we mirror the strategy of Lorraine et al. (2020). Consider the broad class of weight optimisers with updates of the form
w:(A)
w; (A) u(A, (A))
2

---

Published as a conference paper at ICLR 2022
for some arbitrary differentiable function u, with indexing each update iteration. We deviate here from the approach of Lorraine et al. (2020) by admitting general functions u(>, w), rather than assuming the particular choice USGD = aw (see Appendix A.4 for more details). In particular, this allows À to include optimiser hyperparameters. Differentiating (4) and unrolling the recursion gives
Ow: ax
du
du aA
=
Σ OSj<i
II USAー
I
(5)
Ow
x
where j indexes our steps back through time from Wi-1 to Wo. and all w depend on the current hyperparameters X see Appendix C.2 for the full derivation. Now, we follow Lorraine al. and assume Wo...., W,-1 to be equal to w,. With this, we simplify the product in (5) to a jth power by evaluating all derivatives at w, This result is then used to approximate Ow by further assuming that ax
W; 2 w". These two approximations lead
Ow 0A
Iu
f du
Ow* OA
Σ OS.I<i
(6)
dw
ax
Xww,(A')
We reinterpret as predefined look-back distance, trading off accuracy and computational efficiency.
The combination of these approximations implies w; = ww for all i, which initially inaccurate, but which we would expect to become more correct as training proceeds. In mitigation, perform several weight updates prior to each hyperparameter update. This means derivatives in earlier terms of the series of (6) (which are likely the largest, dominant terms) are evaluated weights closer to w", therefore making the summation more accurate. In Section 4, we show that the approximations described here result in algorithm that is both practical and effective.
Our approximate result (6) combines the general weight update of Majumder et al. (2019) with the overall approach and constant-weight assumption of Lorraine al. (2020). The latter empirically show that an approximation similar to (6) leads to a directionalll-aacuraal approximate hypergradient; we illustrate the approximate updates from our derivations Figure (by -*).
2.3 CONVERGENCE TO
DERIVATIVE
To justify the approximations in (6), note that the central part of that equation is a truncated Neumann series. Taking the limit > xo when such a limit exists, results the closed form
Ow ad
iu Ow
du
ax
This is precisely the result of the IFT (Theorem 1) applied to u instead of 2cz that is, substituting the simple SGD update uSGD (A, w) 17 dCr into (7) recovers (3) exactly. Thus, under certain conditions, our approximation (6) converges to the true best-response Jacobian in the limit of infinitely long look-back windows.
2.4 HYPERPARAMETER UPDATES
Substituting (6) into (2) yields a tractable approximation for the hypergradient dey with which we can update hyperparameters by gradient descent. Our implementation in Algorithm (Figure 4) closely parallels Lorraine et al.'s algorithm, invoking Jacobian-vector products (Pearlmutter, 1994) during gradient computation for memory efficiency via the grad _odddutsutttss s argument, which also provides the repeated multiplication for the jth power in (6). Thus, retain the O(ww) + (A]) denotes cardinality. The core loop to
time and memory cost of Lorraine et al. (2020), where compute the summation in (6) comes from algorithm of Liao et al. (2018). Note that Algorithm 1 approximates dey retrospectively by considering only the last weight update rather than any future weight updates.
(Domke, 2012), Algorithm 1 crucially estimates hy- pergradients without reference to old model parameters, thanks to the ppproximatt-hyyerrraadd construction of Lorraine al. (2020) and (6). We thus do not store network weights multiple time
Unlike
3

---

Published as a conference paper at ICLR 2022
steps, so gradient-based HPO becomes possible on meeviossl--inrractaie large-scale problems. In essence, we develop an approximation to online hypergradient descent (Baydin et al., 2018).
Optimiser hyperparameters generally do not affect the optimal weights, suggesting their hypergradi- ents should be zero, However, in practice, w is better reinterpreted as the approximately optimal weights obtained after a finite training episode. These certainly depend on the optimiser hyperparam- eters, which govern the convergence of w, thus justifying our use of the bilevel framework.
We emphasise training is not reset after each hyperparameter update from where we left off, using the new hyperparameters. Consequently, Algorithm I avoids the time cost of multiple training restarts. While our locally greedy hyperparameter updates threaten short-horizon bias (Wu et al., 2018), we still realise practical improvements in our experiments.
simply continue training
2.5 REINTER OF ITERATIVE OPTIMISATION
Originally, we stated the IFT (3) in terms of minima of Lr (zeros of aLz), ). and substituting USGD aCr into (7) recovers this form of (3). However, in general. (7) recovers the Theorem for zeros of which are not necessarily minima of the training loss. Despite this, our development can be compared to Lorraine et al. (2020) by expressing u as the derivative of an augmented 'pseudo-loss' function. Consider again the simple SGD update USGD. which provides the weight update rule BCr By trivially defining pseudo-loss L nLT, we may absorb y) into loss-like W; W dww
1) Sw
derivative, yielding w. = Wi-1
ac More generally, we may write C f u(x, w) dw.
Ow
Expressing the update in this form suggests a reinterpretation of the role of optimiser hyperparameters. Conventionally, our visualisation of gradient descent has the learning rate control the size of steps over some undulating landscape. Instead, we propose fixing a unit step size, with the 'learning rate' scaling the landscape underneath. Similarly, we suppose a 'momentum' could, at every point, locally squash the loss surface in the negative- gradient direction and stretch it in the resitive-gradien direction. In aggregate, these transformations straighten out optimisation trajectories and bring local optima closer to the current point. While more complex hyperparameters lack a clear visualisation in this framework, it nevertheless allows broader class of hyperparameters to 'directly alter the loss function' instead of remaining completely independent, circumventing the problem with optimiser hyperparameters noted by Lorraine et al. (2020). Figure 2 and Appendix A.3 support this argument.
-rrgaiive-rrdient
RELATED WORK
Kohavi & John (1995) first noted different problems respond optimally to different hyperparameters; Hutter et al. (2018, Chapter I) summarise the resulting hyperparameter optimisation (HPO) field.
Black-box HPO treats the training process atomic, selecting trial configurations by grid search (coarse or intractable at scale), random search (Bergstra & Bengio (2012); often more efficient) or population- based searches (mutating promising trials). Pure Bayesian Optimisation (Močkus et al., 1978; Snock et al., 2012) guides the search with a predictive model; many works seek to exploit its sample efficiency (e.g. Swersky al. (2014a); Snoek al. (2015); Wang et al. (2016); Kandasamy et al. (2017); Lévesque et al. (2017); Perrone et al. (2019)) However, these methods require each proposed configuration to be fully trained, incurring considraale computational expense. Other techniques infer information during a training run from learning curves (Provost et al., 1999; Swersky et al., 2014b; Domhan al., 2015; Chandrashekaran & Lane, 2017: Klein et al., 2017), smaller surrogate problems (Petrak, 2000; van den Bosch, A. et al., 2004; Krueger et al., 2015; Sparks al., 2015; Thornto et al., 2013; Sabharwal al., 2016) or intelligent resource allocation (Jamieson & Talwalkar, 2016 6; Li et al., 2017; Falkner et al., 2018; Bertrand et al., 2017; Wang et al., 201 8). Such techniques could be applied on top of our algorithm to improve performance.
In HPO with nested bilevel optimisation, hyperparameters are optimised conditioned on optimal weights, enabling updates during training, with a separate validation set mitigating overfitting risk; this relates to meta-learning (Franceschi et al., 2018). Innovations include differentiable unrolled stochastic gradient descent (SGD) updates (Domke, 2012; Maclaurin et al., 2015; Baydin et al., 2018; Shaban et al., 2019; Majumder et al.. 2019), conjugate gradients or hypernetworks (Lorraine & Duvenaud, 2018: Lorraine et al., 2020; MacKay et al., 2019; Fu et al., 2017), solving one level while penalising suboptimality of the other (Mehra & Hamm, 2020), and deploying Cauchy's implicit
4

---

Published as a conference paper at ICLR 2022
10
10a
Final Test MSE (No HPO)
0C 7/2 Uw
BC
Weight Decay
10-2
110
113 dw
7)1 Bw
C
OC
10:4.
TJ
CCa
8w
10-9
Es
BC2
Ow
C2
10
10:1
aci
C1
Leaming Rate
Initialisation / trajectory / end of multiple runs
(b) c
Z, n/C
3w
Weight updates
(projected onto C)
Figure 3: Sample hyperparameter trajectories from training UCI Energy under Our WD+LR con- figuration. Background shading gives a non- HPO baseline with hyperparameters fixed at the corresponding initial point; these results are in- terpolated by Gaussian process. Note the tra- jectories are generally attracted to the valley of high performance at learning rates around 10-1 and weight decays below 10
Figure 2: Reinterpreting the role of learning rate ?) over a loss function L. (a) In the classical setting, ? scales the gradient of some fixed L. (b) In our setting, 7) scales L to form 'pseudo- loss' Z. whose gradient is used as-is: our loss function has become dependent r). The same weight updates are obtained both (a) and (b).
function theorem (Larsen et al., 1996; Bengio, 2000; Luketina al., 2016; Lorraine al., 2020). Donini et al. (2020) extrapolate training to optimise arbitrary learning rate schedules, extending earlier work on gradient computation (Franceschi et al., 2017), but do not immediately accommodate other hyperparameters. While non-smooth procedures exist (Lopez-Ramos & Beferull-Lozano, 2021), most methods focus on smooth hyperparameters which augment the loss function (c.g. weight regularisation) and work with the augmented loss directly. Consequently, they cannot handle optimiser hyperparameters not represented in the loss function (e.g. learning rates and momentum factors; Lorraine et al. (2020)). Many of these methods compute hyperparameter updates locally (not over the entire training process), which may induce short-horizon bias (Wu et al., 2018), causing myopic convergence local optima.
Modern developments include theoretical reformulations bilevel optimisation to improve per- formance (Liu al., 2020: et al., 2020a), optimising distinct hyperparameters for each model parameter (Lorraine et al., 2020; Jie et al., 2020), and computing forward-mode hypergradient aver- ages using more exact techniques than we do (Micaelli & Storkey, 2020). Although these approaches increase computational efficiency and the range of tunable parameters, achieving both benefits at once remains challenging. Our algorithm accommodates a diverse range of differentiable hyperparameters. but retains the efficiency of existing approaches (specifically Lorraine et al. (2020)). Inevitably, we also inherit gradient- based methods' difficulties with robustness and discrete hyperparameters.
EXPERIMENTS
Our empirical evaluation uses the hardware and software detailed Appendix A. with code available at https: //gthhub. com/ /t////mlaaa httm///ccarke/pgee imis heteeeegggnupattteeeeppppppee
Throughout, we train models using SGD with weight decay and momentum. We uniformly sample initial learning rates, weight decays and momenta, using logarithmic and sigmoidal transforms (see Appendix B.3), applying each initialisation in the following eight settings:
5

---

Published as a conference paper at ICLR 2022
Algorithm
Scalable One-Pass Optimisation of High-DDmensional Weight-Update Hyperparameters by Implicit Differentiation
8317
while training continues do for t 1 to T do wo f w- u(>, w)
(a) Baseline: Random (x 000)
T steps of weight updates
10
115
530
452
437
300
384
522
322
end for
706
415
426
440
161
3
122
464
124
457
p = v = dw A.w
@Lv
b Initialise accumulators
515
334
453
323
47A
436
G24
523
for < 1 to i do D Accumulate first summand in (6)
V 4 v grad(u(), w), w, grad_oupputs v)
Updetee Intervel
p p +
318
922
605
end for
D Now p ~
BCv
81
5
1012
417
566
600
1412
SE3
677
700
Ow
dw
A.
1297
115r
2259 1462
192
307
34.5
992
1:00
gindirect
gradduuaaaaaa A2 w). X, grad outputs P)
1761
1537
1369
69C
1682
1955
1954
1.00
D Now gindines
DCv Dw
Hu Bw
2x
A - X - (I A.w + gindirect
4010
4075
4:54
3049
5642
4152
Any gradient-based optimiser (SGD shown, LR k) end while
Lock-Back ancce
(b) Our approach: Ours WD-LR-M (x1 000)
Figure 4: Left: Pseudocode for our method. Right: Median final test loss UCI Energy after 400 hyperparameter updates from random initialisations, for various update intervals T and look-back distances i, with (a) hyper-parameter tuning, Random, and (b) our proposed method, Ours WD+LR+M
Random No HPO; hyperparameters held constant at their initial values, as in random search. Random (x LR) Random with an extra hyperparameter increasing or decreasing the learning rate by multiplication after every T = 10 update steps (emulating a hyperparameter update).
Random (3-batched) Random reprocessed to retain only the best result of every three runs. Allows Random to exceed our methods' computational budgets; imitates population training. Lorraine Lorraine et al. (2020)'s 's method optimising weight decay; other hyperparameters constant, Baydin Baydin et al. (2018)'s 9)'s method optimising learning rate only; other hyperparameters constant. WD-L. Algorithm updating weight decay and learning rate; other hyperparameters constant. WD-LLL-LR-M Optimising all hyperparameters (adding momentum to Ours WD-LR)
Ours WD-HDLRMM WD-LR-M with independent learning rates for each model parameter
Diff-through-Opt Optimising all hyperparameters using exact hypergradients (Domke, 2012)
Any unoptimised hyperparameters are fixed at their random initial values. Ideally, we seek resilience to poor initialisations, which realistically arise in unguided hyperparameter selection. Hyperparameters tuned the validation set; this is combined with the training set for our Random settings, each algorithm observes the same data. We use the UCI/Kinšnm dataset split sizes of Gal & Ghahramani (2016) and standard 60%/20% /20% splits for iraining/vllidationnesst datasets elsewhere, updating hyperparameters every T = 10 batches with look-back distance i = 5 steps (except Baydin, which has no such inpeeraraarr,s,sss so updates hyperparameters at every batch (Baydin et al., 2018)).
Numerical data is normalised to zero-mean, unit-variance. For efficiency. the computational graph detached after each hyperparameter update, so we never differentiate through hyperparameter updates essentially, prok-propngttion and momentum histories are truncated. Our approximate hypergradient is passed to Adam (Kingma & Ba, 2015) with meta-learning rate 0.05 and default 31 = 0.9, 82 0.999. While these metaa-yyperpraametrr are not tuned, previous work indicates performance progressively less sensitive to higher-order hyperparameters (Franceschi et al., 2017; 2018; Majumder et al.. 2019). As some settings habitually chose unstable high learning rates, we clip these to [10- 10 1] throughout.
Proof of Concept First, we broadly illustrate Algorithm 1 on UCI Energy, using a one-layer multi-layer perceptron (MLP) with 50 hidden units and ReLU (Glorot et al., 2011) activation functions, trained under WD+LR for 4 000 full-batch epochs (see Appendix B. for details). Figure 3 shows the evolution of learning rate and weight decay from a variety of initialisations, overlaid on the performance obtained when all hyperparameters the trajectories are attracted towards the region of lowest test loss, indicating our algorithm is capable of useful learning rate and weight decay adjustment.
UCI Energy:
kept fixed during training. Notice

---

Published as a conference paper at ICLR 2022
Table 1: Final test MSEs after training UCI and Kin8nm datasets for 4 000 full-batch epochs from each of 200 random hyperparameter initialisations, showing best and bootstrapped average performance. Uncertainties are standard errors; bold values lie in the error bars of the best algorithm.
UCI Energy
KinSam (00)
UCI Power
Method
Mean
Median
Best
Mean
Median
Best
Mean
Median
Best
Random
24
#2
8.3
207
0.124
#2
30
#:
5.70
70
20
15.4
Random (x I.)
35
13
1.1
01.11
44
1:3
6.18
106
1
29
4.5
16.0
Random (3-batched)
5
+1
2
0.104
15
=1
10
6.24
17.9 =:44
17.0
+:11
15.5
Lorraine
24
8.7 #00
0.145
=2
30
#3
6.32
19.7
Baydin
5.5
#02
6.8 =0.1
0.144
23.4
26
#1
6.00
17.80 0:07
17.94
4:00
15.4
Ours Ours
2.1
1.8
0.130
7,60
6.21
17.26
17.21
15.6
Ours WiD RRM
0.96 a.0
0,30 9:008
0,112
8.1 0.4
7.10 + D.08
5,90
17.19 =0001
17.192 + 0.004
15.6
Ours WD-HILL-MM
0.6 1002
0.28 0:001
2.3
7.47 a:
6.04
16.69
4:007
15.4
Diff-through-pt
0.93 0.00
0.34 = 0.04
0,132
7,9
7.13 + 000
5.88
17.15
= 0.02
17.184 + 0.006
15.5
4.1 UCI AND KIN8NM DATASETS: ESTABLISHING ROBUSTNESS
Next, we consider the same 50-hidden-unit MLP applied to seven standard UCI datasets (Boston Housing, Concrete, Energy, Naval, Power, Wine, Yacht) and Kin8nm, in a fashion analogous to Gal & Ghahramani (2016) (we do not consider dropout or Bayesian formulations). We train 200 hyperparameter initialisations for 000 full-batch epochs. Table shows results for three datasets, with complete loss evolution and distribution plots in Appendix B.4. Some extreme hyperparameters caused numerical instability and NaN final losses, which our averages ignore. NaN results are not problematic: they indicate extremely poor initialisations, which should be easier for the user to rectify than merely mediocre hyperparameters. Error bars are based on 1 000 sets of bootstrap samples.
Given the sparse distribution of strong hyperparameter initialitions, random sampling unsurprisingly achieves generally poor averages. Random (x LR) applies a learning rate multiplier, uniformly chosen in [0.95, 1.01]: these limits allow extreme initial learning rates revert to more typical values after 400 multiplications. This setting's 's poor performance shows naive learning rate schedules cannot match our algorithms' average improvements. A stronger baseline is Random (3-batched), which harshly simulates the greater computational cost of our methods by retaining only the best of every three Random trials (according to validation loss). This setting comes close to, but cannot robustly beat, our methods - a claim reinforced by final test loss distributions (Figure 9, Appendix B.4).
Lorraine et al. (2020)'s s algorithm is surprisingly indistinguishable from Random our trials, though it must account for three random hyperparameters while varying only one (the weight decay). We surmise that learning rates and momenta are more important hyperparameters to select, and poor choices cannot be overcome by intelligent use of weight decay. Baydin et al. (2018)'s algorithm, however, comes closer to the performance of Random (3-batched), indicating more successful intervention in its sole optimisable hyperparameter (learning rate). Variance is also much lower than the preceding algorithms, suggesting greater stability. That said, despite concentrating on a more important hyperparameter, Baydin still suffers from being unable to control every hyperparameter.
Our scalar algorithms WOurS and Ours Ours WD+LR+M appear generally more robust to these initiali- sations, with average losses beating Random, Lorraine and Baydin. Figures 8 and 9 (Appendix B.4) clearly distinguish these algorithms from the preceding: we achieve performant results over a wider space of initial hyperparameters. Given it considers more hyperparameters. Ours WD+LK+M predictably outperforms Ours WD although the difference is less prominent in certain datasets. Unlike pure HPO. the non-Random algorithms in Table vary hyperparameters during training, combining aspects of HPO and schedule learning. They are thus more flexible than conventional, static- static-hyperparameter techniques, even in high dimensions (Lorraine et al., 2020).
Diff-throggh-Opp exactly differentiates the current loss with respect to the hyperparameters, over the same look-back window and = 10 update interval. As an exact version WD+LL-M (though subject to the same short-horizon bias), it unsurprisingly matches the other algorithms (Figures 8 and 9, Appendix B.4). However, our scalar methods proximity to this exact baseline is reassuring given our much-reduced memory requirements and generally comparable error bars. In these experiments, lengthening Diff- www.tttthohhhpeee Opr's book-back horizon to all 4 000 training steps, and repeating those steps for 30 hyperparameter updates, did not improve its performance (Appendix B.7).
7

---

Published as a conference paper at ICLR 2022
WWr theoretically mitigates short-horizon bias (Wu et al., 2018) by adapting appropriately to high- and low-curvature directions. While this substantially improves performance on some datasets, it is outperformed by scalar methods others (Figures 8 and 9, Appendix B.4). We also see slightly reduced stability, with more trials diverging to NaN final losses. Intuitively, the risk of overfitring the validation set is expected increase as we introduce more hyperparameters, which could explain this behaviour committing to large learning rates in few selected directions, as this method often does, may prove harmful if the loss surface dynamics change suddenly. However, we leave detailed investigation of the high-dimensionas dynamics to future work.
4.2 LARGE-SCALE DATASETS: PRACTICAL SCALABILITY
Fashion-MNIST: HPO in Multi-Layer Perceptrons We train the same single 50-unit hidden layer MLP on 10 epochs of Fashion-MNIST (Xiao et al., 2017), using 50-sample batches. Table and Figure 12a (Appendix B.6) show average test set cross-entropies over 100 initialisations. Clearly- outlying final losses (above 102) are set to NaN to stop them dominating our error bars.
Echoing Section 4.1, for arbitrary hyperparameter initialisations, methods generally converge more robustly to lower losses, even when (as in Figure 12a, Appendix B.6) NaN solutions are included in our statisties. Importantly, we see mini-batches provide sufficient gradient information for our HPO task. Diff-through-Or' failure to beat our methods is surprising; we suppose noisy approximate gradients may regularise our algorithms, preventing them from seeking the short-horizon optimum so directly, thus mitigating short-horizon bias (see our sensitivity study in Section 4.3). Diff- thr-thh-oohhh-p with long look-back horizons does not improve performance for equal computation (Appendix B.7). Finally, median and best loss evolution plots are shown in Figures 5b and 5c, the latter including results for a Bayesian Optimisation baseline. For more details, see Appendices B.5 and B.6.
Penn Treebank: HPO in Recurrent Networks Now, we draw inspiration from Lorraine et al. (2020)'s large-scale trials: a 2-layer, 650-unit LSTM (Hochreiter & Schmidhuber, 1997) with learnable embedding, trained on the standard Penn Treebank-3-subhe
benchmark dataset (Marcus al., 1999) for 72 epochs. To focus our study, we omit the dropout, activation regularisation and predefined learning rate schedules used by Lorraine et al., though we retain training gradient clipping to Euclidean norm of 0.25. Training considers length-70 subsequences of parallel sequences, using 50 random hyperparameter initialisations.
Table and Figure 12b (Appendix B.6) show final test perplexities. They reflect our intuition that adjusting progressively more hyperparameters reduces average test losses, continuing the trend we have seen thus far. Highly bimodal final loss distributions for some algorithms cause wide hootstrap-sampled error bars. Learning rate adjustments show particular gains: Our algorithms and Diff-through-OO Opt perform particularly well in less- less-optimal configurations.
CIFAR-10: HPO in Convolutional Networks Finally, to demonstrate scalability, we train a R8 (He et al., 2016) on CIFAR-10 (Krizhevsky, 2009) for 72 epochs. We use the unaugmented dataset (since unbiased data augmentation over both training and validation datasets exhausts our GPU memory) and optimise hyperparameters as before, using 100-image batches.
Table 2 and Figure 12c (Appendix B.6) show our results. Our gains are now more marginal, with this setting apparently robust its initialisation, though the general ranking of algorithms remains similar, and we retain useful improvements over our baselines. However, our best final accuracies fall short of State-of-the-ard suggesting more intricate and clever setting may yield further performance gains.
Table 2: Final test entrssy ('perplexity) on larger datasets. Bold values are the lowest in class.
Fashion-MNIST
Penn Treebank
CIFAR-IO'
Method
Mean
Median
Best
Mean
Median
Best
Mean
Median
Best
Random
0:007
0.60
20.0
0.340
4700
3000 3000
=0..1
0.819
Random (x LR)
1.29
+:00k
1.2
20.3
0.339
5700
7000 =: 2000
200
1.77
=0005
00000
0.847
Random (3-batched)
0.8
#0.1
0.49
2.09
0.349
1300 :: co)
470 2:10
171
1.60
2:007
1.55
2:0
0.817
Lormine
0.95
4.007
0.61
2000
0.343
4700 1 wm)
3000 a: 3000
170
1.41
2.007
1.26
2.0.0
0.688
Baydin
0.409
0.:03
0.337
4200
2000
=000
1.6
=0.11
0.756
Our Whee.k
0,373 0.0002
0.375 0.00
0.336
360 ::20
360 30
139
1.17
=:002
1.170
0.005
0.715
Ours WiHH R+M
0.369 1:
0.369 1.0000
0.339
50
10002
1:0.01
0.712
Ours HDLR
0.398 no000
0.386 0.03
0.350
310 1 30
270 10
1.5
1.33
20005
1.32
4.00
0,822
Diff through Opt
0,386
0.385
0.02
0.355
300
290
114
1.195
1.197
0.967
8

---

Published as a conference paper at ICLR 2022
2x
2 10
Test Cross-Ennen Entropy
Test Cross-Enne Ennrrpy
Experiment Duration
550
500
109
400
6 10
6x100-2
350
4xx10-1
4
300
5000
10000
10:
10a
250
Network Weight Update Step
Runtime (s)
(a) Single-Pass Runtimes
(b) Median Loss Evolution
(c) Best Loss Evolution
Random
Random (x LR)
Random (3-batched)
Lorraine
Baydin
Ours WD+LR
Ours WD+LR+M
Ours WD+HDLR+M
Diff-through-Opt
Bayesian Optimisation
Mean Runtime
*
Median Runtime
+ Standard Error
Figure 5: Illustrations of training a one-layer 50-umit MLP on Fashion-MNIST over 100 random hyperparameter initialisations. We include a Bayesian Optimisation baseline from Appendix B.5 and loss evolution plots from Appendix B.6.
4.3 MISCELLANEOUS STUDIES
Experiment Runtimes For our larger-scale experiments, we illustrate comparative runtimes in Figure 14 (Appendix B.6.1, where they are discussed in detail). Note from our Fashion-MNIST sample (Figure 5a) that all HPO algorithms have lower computational cost than naïvely training two typical fixed hyperparameter initialisations, despite achieving substantial HPO effect. This compares extremely favourably HPO methods relying repeated retraining. Additional experi- ments in Appendix B.8.2 combine Ours WD-LRRM with Asynchronous Hyperband (Li et al., 2020b) Population-Bart Based Training (Jaderberg al., 2017), showing improved and unchanged perfor- mance/time trade-offs, respectively.
UCI Energy: Sensitivity Study Finally, we consider a range of update intervals T' and look-back distances on UCI Energy, performing 400 hyperparameter updates from 100 random initialisations on each, using OursWD-TReot We plot the median final test losses for each choice of and the right of Figure 4, and also the median performance with no HPO (Random), which we outperform every case. Performance generally improves with larger - likely because the total number of weight updates increases with T, since the number of hyperparameter updates is fixed at 400. While increasing gives more terms in our approximating series (6), these extra terms become more and more biased: they evaluated the current weight values instead of at the progressively more different past weight values. We theorise this trade-off explains the more complex relationship between and final performance. More details given in Appendix B.2.
CONCLUSION AND FUTURE WORK
We have presented algorithm for optimising continuous hyperparameters, specifically those appearing in a differentiable weight update, including optimiser hyperparameters. Our method requires only single training pass, has motivating true-hypergradient convergence argument, and demonstrates practical benefits at a range of experimental scales without greatly sacrificing training time. We also tackle traditionally- -intraatlly per-parameter learning rate optimisation on non-trin -tivial datasets. However, this setting surprisingly underperformed its scalar counterpart; further work is necessary to understand this result.
As future work, our myopic approach could be extended to longer horizons by incorporating the principles of recent work by Micaelli & Storkey (2020), which presents a promising research direction. We also depend inconveniently on meta-hyperparameters. which are not substantially tuned. Ultimately, we desire systems which are completely independent human configuration, thus motivating investigations into the removal of these settings.

---

Published as a conference paper at ICLR 2022
SOCIETAL IMPACT / ETHICS STATEMENT
Our work fits into the broad subfield of automatic machine learning (AutoML), which aims to use automation strip away the tedious work that is necessary to implement practical ML systems. Our method focuses on automating the oft-labelled 'black art' of optimising hyperparameters. This contributes towards the democratisation of ML techniques, which we hope will improve accessibility to non-experts.
However, our method also has some associated risks. For one, developers of unethical machine learning applications (e.g. for mass surveillance, identity theft or automated weaponry) may use our techniques improve their systems' performance. The heavily metric-dominated nature of our field creates additional concerns for instance, end-users of our method may not appreciate that optimising naïvely for training and validation loss alone may result in dangerously poorly-trained or unethical models if the chosen metric, developer's intentions and moral good do not align.
More broadly, users may rely excessively on HPO techniques to optimise their models' performance, which can lead to poor results and inaccurate comparisons if the HPO strategy is imperfect. Further, reducing the need to consider hyperparmeter tuning abstracts away an important component of how machine learning methods work in practice. Knowledge of this component may then become less accessible, inhibiting understanding and future research insights from the wider community.
Our datasets drawn from standard benchmarks, and thus should not introduce risks. Similarly, our work aims to decrease the computational burden of HPO, which should miti- gate the environmental impact of ML training wwrironmenttlly-cooniiii society.
societal
important goal in increasingly
REPRODUCIBILITY STATEMENT
All datasets we use are publicly available; for the Penn Treebank dataset, we provide a link in Table (Appendix A.2). What little data processing we perform is fully explained in the corresponding subsection of Section 4.
Our mathematical arguments are presented fully and with disclosure of all assumptions Section C.
Source code for all our experiments is provided to reviewers, and is made available on GitHub (https: //github. com/ rme rmelarre Larke / Opt imi ingWei Updat
This source code contains complete description of our experimental environment, configuration files and instructions on the reproduction of our experiments.
ACKNOWLEDGEMENTS
We acknowledge computation provided by the Cambridge Service for Data Driven Discovery (CSD3) operated by the University of Cambridge Research Computing Service (www. www.. cam. ac. uk), provided by Dell EMC and Intel using Tier-2 funding from the Engineering and Physical Sciences Research Council (capital grant EP/P020259/1), and DiRAC funding from the Science and Technology Facilities Council (www. dirac adirac.ac.u. uk).
We thank Austin Tripp for his feedback drafts of this paper.
Ross Clarke acknowledges funding from the Engineering and Physical Sciences Research Council (project reference 2107369, grant EP/S515334/1).
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Baydin, A. G., Cornish, R., Martúnez-Rubio, D., Schmidt, M., and Wood, F. Online Learning Rate Adaptation with Hypergradient Descent. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Bengio, Y. Gradient-Based Optimization of Hyperparameters. Neural Computation, 12(8):1889-199)
August 2000.
Bergstra, J. and Bengio, Y. Random Search for Hyper-Parameter Optimization. Journal of Machine Learning Research, 13(Feb):281-305, 2012.
Bertrand, H., Ardon, R., Perrot, M., and Bloch, I. Hyperparameter Optimization of Deep Neural Net- works: Combining Hyperband with Bayesian Model Selection. In Conférence Sur l'Apprentissage Automatique, pp. 5, 2017.
Bouthillier, X. and Varoquaux, G. Survey of machine-learning experimental methods at NeurIPS2019 and ICLR2020. Research Report, Inria Saclay Ile de France, January 2020.
Chandrashekaran, A. and Lane, I. R. Speeding up Hyper-parameter Optimization by Extrapolation of Learning Curves Using Previous Builds. Ceci, M., Hollmén, J., Todorovski, L., Vens. C., and Džeroski, S. (eds.), Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Computer Science, pp. 477-492 Cham, 2017. Springer International Publishing.
Domhan, T., Springenberg. J. T., and Hutter, F. Speeding Up Automatic Hyperparameter Optimization of Deep Neural Networks by Extrapolation of Learning Curves. In Twenty-Fourth International Joint Conference on Artificial Intelligence, June 2015.
Domke, J. Generic Methods for Optimization- Modeling. In Artificial Intelligence and Statistics, pp. 318-326, March 2012.
Donini, M., Franceschi, L., Frasconi, P., Pontil, M., and Majumder, O. MARTHE: Scheduling the Learning Rate Via Online Hypergradients. In Twenty-Ninth International Joint Conference on Artificial Intelligence, volume 3, pp. 21 2119-2125, July 2020.
Falkner, S., Klein, A., and Hutter, F. BOHB: Robust and Efficient Hyperparameter Optimization at Scale. In International Conference on Machine Learning, pp. 1437-1446. PMLR, July 2018.
Franceschi, L., Donini, M., Frasconi, and Pontil, M. Forward and Reverse Gradient-Baan Based Hyperparameter Optimization. In International Conference on Machine Learning, pp. 1165-1173, July 2017.
Franceschi, I.., Frasconi, P., Salzo, S., Grazzi, R., and Pontil, M. Bilevel Programming for Hyperpa- rameter Optimization and Meta-Learning. In International Conference on Machine Learning, pp. 1568-1577. PMLR, July 2018
Fu, J.. Ng, R.. Chen, D... Ilievski, I., Pal, C.,, and Chua, T.-S. Neural Optimizers with Hypergradients for Tuning Parameter- Wise Learning Rates. In Automatic Machine Learning Workshop at ICML. 2017, pp. Sydney, August 2017.
Gal, Y. and Ghahramani, Z. Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning. In International Conference Machine Learning, pp. 1050-1059, June 2016.
Glorot, X., Bordes, A., and Bengio, Deep Sparse Rectifier Neural Networks. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 315-323, June 2011.
Grefenstette, E., Amos, B., Yarats, D., Htut, P. M., Molchanov, A., Meier, F., Kiela, D., Cho. K., and Chintala, S. Generalized Inner Loop Meta-Learning, arXiv:1910.01727 [cs, stat], October 2019.
Hc, K., Zhang, X., Ren, S., and Sun, J. Deep Residual Learning for Image Recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CrloinnnCC (CVPR), pp. 770-778, June 2016.

---

Published as a conference paper at ICLR 2022
Hochreiter, S. and Schmidhuber, J. Long Short-Term Memory. Neural Computation, 9(8):1735-1780 November 1997.
Hutter, F., Kotthoff, L., and Vanschoren, J. (eds.). Automated Machine Learning: Methods, Systems, Challenges. Springer, 2018.
Jaderberg, M., Dalibard, V., Osindero, S., Czarnecki, W. M., Donahue, J., Razavi, A., Vinyals, O., Green, T., Dunning, I., Simonyan, K., Fernando, C., and Kavukcuoglu, K. Population Based Training of Neural Networks. arXiv:/711.098/ [cs], November 2017.
Jamieson, K. and Talwalkar, A. Non-stochastic Best Arm Identification and Hyperparameter Op- timization. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp. 240-248, May 2016.
Jie, R., Gao, J., Vasnev, A., and Tran, M.-N. Adaptive Multi-level Hyper-gradient Descent. (xXiv:0088.07277 [cs], August 2020.
Kandasamy, K., Dasarathy, G., Schneider, J., and Póezos, Multi-fidelity Bayesian Optimisation with Continuous Approximations. In Proceedings of the 34th International Conference on Machine Learning, pp. 1799-11911 1799-1808 1808. PMLR, July 2017.
Kingma, D. P. and Ba, J. Adam: Method for Stochastic Optimization. In Bengio, Y. and LeCun, Y. (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Klein, A., Falkner, S., Springenberg. J. T., and Hutter, F. Learning Curve Prediction with Bayesian Neural Networks. In 5th International Conference on Learning Representations, 2017.
Kohavi, R. and John, G. H. Automatic Parameter Selection by Minimizing Estimated Error. In Prieditis, A. and Russell, (eds.), Machine Learning Proceedings 1995, pp. 304-312. Morgan Kaufmann, San Francisco (CA), January 1995.
Krizhevsky, A. Learning Multiple Layers of Features from Tiny Images. MSc Thesis, University of Toronto, April 2009.
Krueger, T., Panknin, D.,, and Braun, M. Fast Cross- Validation via Sequential Testing. Journal of Machine Learning Research, 16(33): 103-1155, 2015.
I Larsen, J., Hansen, I.., Svarer, C.,, and Ohlsson, M. Design and regularization of neural networks: The optimal use of validation set. In Neural Networks for Signal Processing Proceedings of the 1996 IEEE Signal Processing Society Workshop, pp. 62-71, September 1996.
Lévesque, Durand, A., Gagné, C., and Sabourin, R. Bayesian optimization for conditional hyperparameter spaces. In 2017 International Joint Conference on Neural Networks (IJCNN) pp. 286-293, May 2017.
Li, Gu, B., and Huang, H. Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee. arXi::2009006990 [cs, stat), September 2020a.
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and Talwalkar, A. Hyperband: A novel bandit- based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18 (1):6765-68) 16, January 2017.
Li, L., Jamieson, K., Rostamizadeh, A., Gonina, E., Ben-tzur, J., Hardt, M., Recht, B., and Talwalkar, A. A System for Massively Parallel Hyperparameter Tuning. Proceedings of Machine Learning and Systems, 2:230-246, March 2020b.
Liao, R., Xiong, Y., Fetaya E.,, Zhang, L., Yoon, K., Pitkow, X., Urtasun, R., and Zemel, R. Reviving and Improving Recurrent Back- sooc-Propagation. In International Conference on Machine Learning. pp. 3082-3091. PMLR, July 2018.
Liaw, R., Liang, E., Nishihara. R., Moritz, P., Gonzalez, J. E., and Stoica, I. Tune: A Research Platform for Distributed Model Selection and Training. arXiv: arXiv:1807.00 807.051 18 [cs, stat), July 2018.
12

---

Published as a conference paper at ICLR 2022
Liu, R., Mu, P., Yuan, X., Zeng, S., and Zhang, J. A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lever-Level Singleton. In Proceedings of the International Conference Machine Learning. PMLR, 2020.
Lopez-Rame Hamez, L. M. and Beferull-Lozand B. Online Hyperparameter Search Interleaved with Proximal Parameter Updates. In 2020 28th European Signal Processing Conference (EUSIPCO), pp. 2085-2089, January 2021.
Lorraine, J. and Duvenaud, D. Stochastic Hyperparameter Optimization through Hypernetworks. arXivv1802.09419 [cs], March 2018.
Lorraine, J., Vicol, P., and Duvenaud, D. Optimizing Millions of Hyperparameters by Implicit Differ- entiation. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pp. 1540-1552. PMLR, June 2020.
Luketina, J., Berglund, M., Greff, K., and Raiko, T. Scalable Gradient- Based Tuning Continuous Regularization Hyperparameters. In International Conference Machine Learning, pp. 2952- 2960. PMLR, June 2016.
MacKay, M., Vicol, P., Lorraine, J., Duvenaud, D., and Grosse, R. B. Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Maclaurin, D., Duvenaud, D., and Adams, R. Gradient-based Hyperparameter Optimization through Reversible Learning. In International Conference on Machine Learning, pp. 2113-2122. PMLR, June 2015.
Majumder, O., Donini, M., and Chaudhari, P. Learning the Learning Rate for Gradient Descent by Gradient Descent. In 6th AutoML Workshop (CML.2019 pp. 8, 2019.
Marcus, M. P., Santorini, B., Marcinkiewicz, M. A., and Taylor, A. Treebank-3, 1999.
Mehra, A. and Hamm, J. Penalty Method for Inversion-Free Deep Bilevel Optimization. UrXiv:1911.033 [es, math, stat], June 2020.
Micaelli, P. and Storkey, A. Non-greedy Gradient-based Hyperparameter Optimization Over Long Horizons. arXiv:2007. 07766 [cs, stat], July 2020.
Močkus, J., Tiešis, V., and Zilinskas, A. The Application of Bayesian Methods for Seeking the Extremum. Towards Global Optimisation, 2: 2:117-129, 1978.
Nogueira, F. Bayesian Optimization: Open source constrained global optimization tool for Python, 2014.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein,
N., Antiga, I.,, Desmaison, A., Kopf, A., Yang, E.,, Vito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32 (NeurIPS 2019), pp. 12, Vancouver, Canada, 2019.
Pearlmutter, B. A. Fast exact multiplication by the Hessian. Neural Computation, 6(1):147-160, January 1994.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, É. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12885))2855-2830 2011.
Perrone, V., Shen, H., Seeger, M. W., Archambeau, C.,, and Jenatton, R. Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning. In Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
13

---

Published as a conference paper at ICLR 2022
Petrak, J. Fast Subsampling Performance Estimates for Classification Algorithm Selection. Technical Report TR-2000-07, Austrian Research Institute for Artificial Intelligence, 2000.
Provost, F., Jensen, D., and Oates, T. Efficient progressive sampling. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '99, pp. 23-32, San Diego, California, USA, August 1999. Association for Computing Machinery.
Sabharwal, A., Samulowitz, H., and Tesauro, G. Selecting near-optimal learners via incremental data allocation. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. AAAI' 16, pp. 2007-2015, Phoenix, Arizona, February 2016. AAAI Press.
Shaban, A., Cheng, C.-A,, Hatch, N., and Boots, B. Truncated Back-propagation for Bilevel Optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1723 1732, April 2019.
Snoek, J., Larochelle, H., and Adams, R. P. Practical Bayesian Optimization of Machine Learning Algorithms. In Pereira, F., Burges, C. C., Bottou, I.., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 25, pp. 2951-29555 Curran Associates, Inc., 2012.
Snoek, J., Rippel, O., Swersky, K., Kiros, R., Satish, N., Sundaram, N., Patwary, M., Prabhat, M., and Adams, Scalable Bayesian Optimization Using Deep Neural Networks. In International Conference on Machine Learning, pp. 2171-2180 PMLR, June 2015.
Sparks, R., Talwalkar, A., Haas, D., Franklin, M. J., Jordan, M. I., and Kraska, T. Automating model search for large scale machine learning. In Proceedings of the Sixth ACM Symposium Cloud Computing, SoCC '15, pp. 368-380, Kohala Coast, Hawaii, August 2015. Association for Computing Machinery.
Swersky, K., Duvenaud, D., Snoek, J., Hutter, F., and Osborne, M. A. Raiders of the Lost Architecture: Kernels for Bayesian Optimization in Conditional Parameter Spaces. arXiv:1409.4011 [stat], September 2014a.
Swersky, K., Snoek, J., and Adams, R. P. Freeze-Thaw Bayesian Optimization. /rXiv:/406.3800 [cs, star], June 2014b.
Thornton, C., Hutter, F., Hoos, H. H., and Leyton-Brown, K. Auto-WEKA Combined selection and hyperparameter optimization of classification algorithms. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '13, pp. 847-855, Chicago, Illinois, USA, August 2013, Association for Computing Machinery.
Turner, R., Eriksson, D., McCourt, M., Kiili, J., Laaksonen, E.,, Xu, Z., and Guyon, I. Bayesian Opti- mization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020. In Proceedings of the NeurIPS 2020 Competition and Demonstration Track, pp. 3-26. PMLR, August 2021.
van den Bosch, A., Verbrugge, R., Taatgen, N., and Schomaker, L. Wrapped progressive sampling search for optimizing learning algorithm parameters. In Proceedings of the Nethiuns-etherlladdd Conference on Artificial Intelligence, BNA1C"04, pp. 219-226, October 2004.
Wang, J., Xu, J., and Wang, X. Combination of Hyperband and Bayesian Optimization for Hyperpa- rameter Optimization in Deep Learning. 1rX1vv1801.01S0 [cs], January 2018.
Wang, Z., Hutter, F., Zoghi, M., Matheson, D., and de Feitas, N. Bayesian Optimization in a Billion Dimensions via Random Embeddings. Journal of Artificial Intelligence Research, 55:361-387, February 2016.
Williams, I. and Rasmussen, C. E. Gaussian Processes for Regression. In Touretzky, D. S., Mozer, M. C., and Hasselmo, M. E. (eds.), Advances in Neural Information Processing Systems 8, pp. 514-520. MIT Press, 1996.
Wu, Y., Ren, M., Liao, R., and Grosse, R. B. Understanding Short-Horizon Bias in Stochastic Mleaa-Optimization In 6th International Conference on Learning Representations, Vancouver, BC, Canada, 2018 OpenReview.net.
Xiao, H., Rasul, K., and Vollgraf, R. Pashion-MNISTI A Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv: /10.:0770007774 [cs, stat], September 2017.
14

---

Published as a conference paper at ICLR 2022
A NOTES
A.1 EXPERIMENTAL CONFIGURATION
Table 3: System configurations used to run our experiments.
Type
CPU
GPU (NVIDIA)
Python
PyTorch
CUDA
Consumer Desktop Local Cluster
Intel Core 17-3930K Intel Core 19- 1090000XX
RTX 2080GTX
3.9.7
1.8.1
10.1
RTX 2080GTX
3.7.12
1.8.1
10.1
Cambridge Service for Data Driven Discovery (CSD3)*
EPYC 7763
Ampere A100
3.7.7
1.10.1
11.1
www. csd3 cam ac.uk
Our experiments are variously performed on one of three sets of hardware, as detailed in Table 3. While system configurations varied between experiments, this does not impair comparability. All Penn Treebank and CIFAR-10 experiments were performed on the CSD3 Cluster, otherwise, all experiments comparing runtimes were performed on the Local Cluster. We make use of GPU acceleration throughout, with the PyTorch (Paszke et al., 2019) and Higher (Grefenstette al., 2019) libraries.
On CIFAR-10 10 only, minor bug in our data processing code meant the mean and standard deviation used to normalise the dataset were incorrect by a factor of 255. As batch normalisation in the ResNet- 18 model largely mitigates this error, and every algorithm data, this does not threaten the validity of our results. We retain the incorrect transformation in our published code for reproducibility, but have clearly annotated the affected lines.
provided with the same nal-normaliied
A.2 DATASET LICENCES
Table 4: Licences under which datasets in this work.
Dataset
Licence
Source
UCI Boston
UCI Concrete
UCI Energy
Kin8nm
Unknown; widely used
Gal & Ghahramani (2016, Github)
UCI Naval
UCI Power
UCI Wine
UCI Yacht
Fashion-MNIST
MIT
PyTorch via torchvision
Penn Treebank
Proprietary; fair use subset, widely used
CIFAR-10
No licence specified
PyTorch via torchvision
#http://www fit vutbr. wttpppp.w./...oooooo////aa//iiaa
Our datasets all standard in the ML literature. For completeness, we outline the licences under which they are used in Table 4.
A.3 EXPANDED INTUITIVE REINTERPRETATION OF ITERATIVE OPTIMISATION
In this section, we take the opportunity give more verbose elaboration on the ideas presented in Section 2.5, which seeks to address methodological concerns raised by Lorraine et al. (2020) and reinterpret iterative optimisation in light of our derived algorithm.
Lorraine et al. (2020) base their derivations on the training loss Lr, which does not depend on optimiser hyperparameters such as the learning rate or momentum coefficient. Differentiating Lt with respect to these hyperparameters thus cannot provide any useful information for computing their gradient-base baseed updates. Similarly, the Implicit Function Theorem cannot be applied to motivate their approximation in this case, since Lr is not implicit function of these hyperparameters. Consequently, Lorraine et al. declare their method is methodologically restricted to operate on hyperparameters which the training loss depends directly.
15

---

Published as a conference paper at ICLR 2022
In contrast, work with an arbitrary update u, which does then depend on the optimiser hyperpa- rameters, allowing us to take the corresponding derivatives and apply the Implicit Function Theorem. However, the optimisation objective remains the same, methodological issue raised by Lorraine et al. may still apply. To address these remaining concerns, look to recast our development in the form of Lorraine al. (2020). We do this by defining "pseudo-loss" L such that our weight updates in (4) are equivalent to
should rightly be suspicious that the
aC dw
A.w
We must acknowledge that our optimisation objective is now for the update u to zero (equivalent to stationary point of L), rather than the training loss Lr being minimum. But with that caveat, we may apply the machinery of Lorraine et al. directly: we have constructed a 'loss function' which depends directly all the hyperparameters, so may legitimately deploy their strategy. By comparison with (4), we have that, for any particular problem,
I = / (uA, dw.
Often, in simple cases, the mathematical construction in (9) has a geometric interpretation. Consider the elementary case of vanilla SGD with learning rate which gives the update rule USGD 8w The required pseudo-loss is then L = ryCr, which suggests two equivalent geometric interpretations of the optimisation problem we are solving.
&Cr
In the first (conventional) interpretation, we have fixed loss surface Lr whose minimum we seek. To optimise r) in this problem, we imagine standing on the loss surface at our current point, then consider the effect of taking different-sized steps across it. Clearly, this interpretation decouples from the underlying function Lr, so suffers from Lorraine et al. 's methodological issue.
In the second (our novel) interpretation, traverse only by taking steps of precisely the magnitude the local gradient. Now, when we optimise 7, rescaling the surface beneath our update step, and consequently also rescaling the update step size. In this way, we have coupled y and Lr into one objective Z, which varies with and so adheres to the methodological restrictions noted by Lorraine al.. The key idea is thus that we have reinterpreted the problem to allow optimiser hyperparameters to dynamically transform the objective surface, which legitimises our derivation.
seek the minimum of the loss surface Z, which may
When we consider SGD with momentum, the situation becomes more complicated, because there not an immediately obvoius closed form for C. Suppose we descending steep-sided valley of the original loss surface Cr. The momentum acts to 'pull' the update step in the direction it has accumulated in its buffer (down the axis of the valley), so acts to augment gradients in the valley's downhill direction, and diminishes the effect of gradients in other directions.
If we are working with the pseudo-loss C, we need achieve the same effect, but we do not have direct control over the update step size, which is determined by the local gradient of L. So if the update step aligned with the accumulated momentum, we must 'squash" the loss surface about our current point in this direction, such that our fixed update step lands at point further down the valley in the original, unscaled space of LT. Accordingly, if the update step is misaligned with the accumulated momentum, this squashing in the direction of the momentum buffer must be combined with a 'stretching' in the update step direction, so that we make less progress in that direction of the original space. In aggregate, this is complex and intricate transformation of the space, such that bring the 'correct' new point (as specified by the optimiser) to lie underneath the update step given by az
To summarise, the key principle we seek to convey in Section 2.5 is that of creating a new pseudo-loss surface Z. which is transformed version of Lr. such that the update steps taken by hyperparameter- free optimiser over the pseudo-loss C are equivalent to those taken by the true optimiser over the original training loss Lr.
16

---

Published as a conference paper at ICLR 2022
A.4 EXPANDED DISCUSSION OF UPDATE FUNCTION u(2, w)
Throughout our derivation, we refer to an arbitrary weight update function u(A, w). While we have expressed this in its most general form for clarity, outline here that this formulation supports wide array of non-trivial weight update optimisation algorithms beyond SGD.
u(λ, w) is precisely the quantity which added the network weights during an update step. For instance, in the PyTorch framework (Paszke et al., 2019), the pre-implemented optimisers first compute some update tensor Aw, then perform the final operation w <- w Aw w update the weights. Thus, we have u(A. w) Aw, and automatic differentiation trivially gives the necessary derivatives to apply our algorithm.
Some optimisers have internal state, for instance the momentum buffer of SGD with momentum and the two rolling average buffers of Adam. Although this dependency is not notated in our presentation of it does not invalidate our development the only extra care required is to detach these buffers from the computational graph after each hyperparameter update. For Py TyTorh'ss s implementation of SGD with learning rate 77, momentum coefficient μ and weight decay coefficient ç, we thus have
dLT Ow
V - JoV +
+ Ew
Umomentum 1/V;
(10)
and need simply take care to detach v from the computational graph after each update. For Adam, we may read the definition of u straight from its original paper (Kingma & Ba, 2015); in their notation:
UAdam
(11)
where t indexes time and vit é, are internal states, and we simply detach those states from the computational graph periodically. Those states depend directly on the additional states my, Us and ultimately the gradient V (ofe(0)-1) (which is TeL. in our notation).
w.-1
17

---

Published as a conference paper at ICLR 2022
B ADDITIONAL RESULTS
B.1 UCI ENERGY: PROOF OF CONCEPT
Our proof of concept graphic (Figure is constructed using the same experimental configuration as Section 4.1. Training 500 random initialisations of the model, weight decay and learning rate for 4.000 network weight update steps on Random (without any HPO) yields source data for the heatmap forming the background of Figure 3. The heatmap itself is the predictive mean of Gaussian process (Williams Rasmussen, 1996) using the sum of an RBF and white noise kernel. We Gaussian process in log (input and output) space using the defaults of the Scikit-learn implementation (Pedregosa et al., 2011), which automatically select hyperparameters for the kernels. Any NaN data points are replaced with large final test loss (150) for the purpose of computing this regression. We then train a small number of additional initialisations using Ours WD+LR and plot these trajectories. As always, the training set provides network weight updates, the validation set provides hyperparameter updates and our results plot final performance on the test set. While we do not expect the optimal trajectory during training to coincide with gradients of our background heatmap, the latter provides useful context.
Generally, given our limited training budget, larger learning rates improve final performance up to point, then cause instability if taken to extremes, and the movement of our trajectories reflects this. Many trajectories select large weight decay coefficients before doubling back on themselves to smaller weight decays suggestive of our algorithm using the weight decay to avoid converging to specific minima. Trajectories generally converge the valley of good test performance at learning rate of around 10-1 and weight decay below 10-2, further demonstrating appropriate behaviour. In short, we are able to make sensible and interpretable updates to the hyperparameters of this problem, which lends support the applicability of our method.
B.2
UCI ENERGY: HYPERGRADIENT STUDIES
Our sensitivity studies are based on a similar experimental configuration to Section 4.1: for each choice of update interval T and look-back distance we generate 100 random initialisations of weight decay, learning rate and momentum. Each initialisation is trained for 400 hyperparameter steps, so increasing 7 permits more network weight updates; averaging over the 100 final test losses yields each result cell in Figure 6 and Figure 7. As in Section 4.1, we consider the Ours OursWD+LR+H WD+LR+M and Safft-thrugh--pp algorithms, optimising hyperparameters using Adam with hyper-learning rate 0.05 and truncating gradient histories at the previous hyperparameter update.
18

---

Published as a conference paper at ICLR 2022
B.2.1
SENSITIVITY OF UPDATE INTERVAL AND BOOK-BACK DISTANCE
8317
(a) Random (x 1000)
525
520
452
680
435
360
384
562
420
393
388
709
41.
426
7:30
522
969
326
481
2.34
582
759
603
Update Interval 7
7-
544
703
561
419
397
497
395
S68
65.1
444
577
6
770
649
716
400
639
5
Update
2-1022
917
566
589
603
1412
503
873
506
700
717
1101
774
605
960
1247
1157
1239
1442
702
9:07
563
952
637
1108
2-3333
1264
3743
1557
1386
1741
996
1680
1355
1356
7:07
1669
0577
1686
1660
4790
Look-Back Distance
Look-Back Distance
(b) Ours WD-IR+M
(x 1000)
(c) Diff Chrough--ptt (x1000)
Figure 6: Median final test loss over 100 repetitions, after optimising UCI Energy for 400 hyperpa- rameter update steps, from variety of update intervals T and look-bace back distances i.
Figure shows our final performance results in this setting: our algorithm's strongest configurations (Figure 6b) compare favourably with results obtained using the exact hypergradients of Diff fiffuthrough- Opt (Figure 6c). Noting that the conditions necessary to guarantee our algorithm's convergence to the best-response derivative (specifically that current network weights are optimal for the current hyperparameters) almost certainly not met in practice, it is unsurprising that Diff through Opr achieves greater performance. This difference is much smaller, however, than that between both HPO algorithms and the Random base case; given substantial efficiency benefits over Diff-through-O0 we make an acceptable compromise between accuracy and scalability. Further, these results justify match the setting of Lorraine al. (2020). That said, recall these
our choice of 7 10 and figures enforce consistency of number of hyperparameter updates, not of total computational expense; for using large numbers of less precise hyperparameter updates (small T and i),
there remains which may promote faster convergence in practice.
Our results illustrate the trade-off in selecting look-back distance principle, increasing includes more terms in our Neumann series approximation to the best-response derivative (6). which should result closer convergence to the true derivative. the sequence Wu, Wi. W;-1 from (5) with w; at all time steps. Because the jth summation step of (5) involves a product of terms in W;-1 back to W;-1-j, the approximation of each summation step in (6) becomes less and less accurate as j increases, since expect earlier model weights to become more different from w,. A larger causes us to continue the summation up to larger j. so introduces progressively less accurate terms into approximations. Thus, increasing i is only of value while this inaccuracy is counteracted by the improved convergence of our summation, giving the behaviour here.
our derivation of this expression replaces
19

---

Published as a conference paper at ICLR 2022
10
0.0%
0.0%
8.5%
.2.7%%1.7%%
9.5%
8.5%
8.5%
4.25
4.25
10
866
9%
10%
1.4%
13%
2.75
2.40%6
15%
24%
0.0%
0.0%
4.2%
4.2%%
0.0%
0.0%
8.5%
0.0%
5.5%
0%
8%
1%
1.8%
2.3%
1%
2.3%
18%
1.%
8-0.0%
4.2%
0.0%
8.5%
0.0%
4.2%
1.2%
0.0%
0%
8%
12%
1.6%
15%
2.2%
2.3%
23%
0.0%
0.0%
4.2%
Update Interval
247
22%
0.0%
Update
0.0%
19%
0.0%
4.2%
8.5%
4.2%
0/6
11%
177
211
3-
0.0%
0.0%
0.0%
06C
12%
16%
0.0%
0.0%
0%
27%
0.0%
1
2
7
8
6
10
Look-Back Distance
Look-Back Distance
(a) Learning Rate
(b) Weight Decay
Figure 7: Mean absolute enror in our approximate hypergradients, based on the first hyperparameter updates of 50 repetitions for each cell, using UCI Energy. We vary the update interval T and look-back distance investigate the sensitivity the problem these meta-hyypeparrmeter.. Hypergradients are shown separately for each hyperparameter.
B.2.2 ACCURACY OF HYPERGRADIENTS
We use this same experimental setting to evaluate the accuracy of our approximate hypergradients, but disable learning rate clipping so as to allow the natural behaviour of each algorithm to be displayed. Our approximate and exact settings only guaranteed to be trying to compute the same hypergradient at the very first hyperparameter update, so we consider this time step only. Using those first hyperparameter updates from 50 random initialisations of the hyperparameters and model, compute the absolute eтror of the approximate hypergradient (Ours W0-11.4MM as percentage of the exact hypergradient (Diff-trroghh-Op)) then plot the means of these errors in Figure 7.
Notice our learning rate hypergradients do not exhibit any particularly strong trends over the meta- hyperparameters consider, but approximate weight decay hypergradients from a shorter look-back distance. Some of the latter average proportional errors are large; a closer examination of the hypothesise that the generally very small weight decay coefficients present more opportunity for numerical computational error than the generally larger learning rates, in which case hypergradients for different byperparameters may have markedly different accuracies. Indeed, the apparently quantised errors the learning rate hypergradients indicate precision truncation is influencing the results of this study. However, our previous coarser studies suggest that, despite being approximate, our method does not suffer catastrophically from inaccurate hypergradients.
to benefit
distributions reveals these cells have outlying results high errors. We
20

---

Published as a conference paper at ICLR 2022
B.3 EXPERIMENT DETAILS
Table 5: Transformation and initialisation parameters used our hyperparameter optimisation.
Initialisation Range
Initialisation
Optimisation Space
Natural Range
Hyperparameter
Space
Min
Max
Min
Max
Learning Rate
Logarithmic Logarithmic
-6
-1
Logarithmic
10 0.1
Weight Decay
-7
-2
Logarithmic
X 10
0,01
Momentum
Natural
0
Sigmoidal
Since the hyperparameters associated with SGD only take meaningful values on subsets of the real line, we apply gradient descent transformed versions of the hyperparameters. For non-negative hyperparameters, such as learning rate and weight decay, we work with the base- 10 logarithm of the actual value; for momentum, which lies in the unit interval [0. 1]. we work with the inverse- sigmoid of the actual value. These transformed search spaces mean naïve implementation of gradient descent will not update hyperparameters to nonsensical values.
inverse-sigmoid
Our hyperparameter initialisations are drawn uniformly from a broad range, intended to be superset of typical values to permit amalysis of the realistic case where we have little intuition for the optimal choices. Thus, our hyperparameter ranges include typical values for variety of applications, while giving each algorithm the opportunity to briefly stretch into more extreme values should these be useful on occasion. Where we have applied a logarithmic transformation to hyperparameter (learning rate and weight decay), we draw samples uniformly in logarithmic space; where inverse- sigmoid transforms are used (momentum), exploration of values near and 1. Table summarises our initialisation and optimisation strategy.
draw samples in natural space to
adequate
Throughout, we seek robustness to range of different initialisations, which is indicated by average final performance across a variety of initial hyperparameter choices. We include metrics of best performance show each algorithm is capable of reaching the same vicinity as the best possible case, but this is not the focus of our work. Intuitively, more naïve algorithm (e.g. Random) could stumble across the best possible final model weights, in which case no other algorithm would be able to beat it; this would not necessarily mean we would prefer the Random algorithm in general setting.
B.4 UCI AND KIN8NM DATASETS
Results from all UCI datasets we considered and Kin8nm are presented in Figures 8 and 9. These show many of the features already discussed in Section 4.1. We account for experimental runs ending in NaN losses by appropriately scaling the maximum value the CDFs in Figure 9 to be less than 1.0. For each dataset, plotted in Figure 10. Note that UCI Naval generated a large number of NaN runs, which explains the prominent failure of certain algorithms reach the top our CDF plots.
random configuration is selected, and the resulting learning rate evolutions
21

---

Published as a conference paper at ICLR 2022
10a
Test MSE (Unnormaliss lisomlllieed
102
Test MSE (Unnormalised)
Test MSE (Unnormalised)
10a
10
100
2000
4000
2000
4000
2000
4000
Network Weight Update Step
Network Weight Update Step
Network Weight Update Step
(a) UCI Boston
(b) UCI Concrete
(c) UCI Energy
Test MSE (Unnormalised)
Test MSE (Unnormalised)
Test MSE (Unnormalise)
10-4
10a
10-5
10"2
10-6
2000
4000
4000
4000 Network Weight Update Step
Network Weight Update Step
Network Weight Update Step
(d) Kin8nm
(e) UCI Naval
(l) UCI Power
Test MSE (Unnormalised)
Test MSE (Unnormalised)
6x:10 10:00
Random
Random (x LR)
Random (3-batched)
1001
Lorraine
101
Baydin
Ours WD+LR
4 10
Ours RDM
10
Ours WD+HDE
Diff Diff-through-Opt
0
2000
4000
2000
4000
Network Weight Update Step
Network Weight Update Step
+ Standard Error
(g) UCI Wine
(h) UCI Yacht
Figure 8: Evolution of test MSEs during training of UCI and Kin8nm datasets for 4 000 full-batch epochs from each of 200 random initialisations of SGD learning rate, weight decay and momentum. We bootstrap sample our results to construct median test MSE estimator at each update step and its standard error.
22

---

Published as a conference paper at ICLR 2022
1.0
1.0
1.0
0.8
0.8
0.8
Empirical CDF
Empirical CDF
Empirical CDF
0.6
0.6
0.6
0.4
0.4
0.4
0.0
0.0
10'
10a
10-1
10"
Final Test MSE (Unnormalised)
Final Test MSE (Unnormalised)
Final Test MSE (Unnormalised)
(a) UCI Boston
(b) UCI Concrete
(c) UCI Energy
1.0
1.0
Empirical CDF
0.6
0.6
0.6
Empirical
Empirical
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
10-2
10
10-?
10-4
10-5
10-4
102
Final Test MSE (Unnormalised)
Final Test MSE (Unnomalised)
Final Test MSE (Unnormalised)
(d) Kin8nm
(e) UCI Naval
(l) UCI Power
1.0
1.0
Empirical CDF
0.8
Empirical CDF
0.8
Random
Random (x LR)
0.6
Random (3-batched)
Lorraine
0.4
Baydin
Ours Ours WD+LR
Ours WD+LR+M
0.0
Ours WD-HDDR+M
4 10-1 10-1
10-1
10P
10a
102
Diff Diff-through-Opt
Final Test MSE (Unnomalisedd)
Final Test MSE (Unnormalised)
(g) UCI Wine
(h) UCI Yacht
Figure 9: Empirical CDFs of final test losses, after training UCI and Kin8nm datasets for 4 000 full-batch epochs from each of 200 random initialisations of SGD learning rate, weight decay and momentum. Runs ending with NaN losses account for the CDFs not reaching 1.0. Higher curves are better; note the logarithmic horizontal scales.
23

---

Published as a conference paper at ICLR 2022
10a1
10-1
10-2
Learning Rate
10
Learning Rate
10
Learning Rate
10
10
10-9
10
10-4
10
10
10-5
10:5
10
10
10
2000
4000
2000
4000
2000
4000
Network Weight Update Step
Network Weight Update Step
Network Weight Update Step
UCI Boston
(b) UCI Conerete
UCI Energy
10-2
10-2
10-2
Learning Rate
Learning Rate
Learning Rate
10
10-3
10
10-4
10
10a5
10-
10
10-6
10
2000
4000
2000
4000
2000
4000
Network Weight Update Step
Network Weight Update Step
Network Weight Update Step
(d) Kin8nm
(e) UCT Naval
(l) UCI Power
10
10-1
Leaming Rate
10-3
Learning Rate
Random
10-3
Random (x LR)
10
Lorraine
4
Baydin
10-5
Ours WD+LR
10.5
Ours WD+LR-M
10
10-6
tiffthhrough-pt
2000
4000
Network Weight Update Step
Network Weight Update Step
UCI Wine
(h) UCI Yacht
Figure 10: Sample learning rate evolutions after training UCI and Kin8nm datasets for 4 000 full- batch epochs; one of 200 random initialisations shown for each dataset, chosen randomly from our results.
24

---

Published as a conference paper at ICLR 2022
B.5 UCI, KIN8NM AND FASHION-MNIST: BAYESIAN OPTIMISATION BASELINES
Table 6: Repeat of Table I: final test MSE selected UCI and Kin8nm datasets. Now includes 32 repetitions of 30-sample Bayesian Optimisation, which is not considered in our emboldening.
UCI Energy
KinSnm (x I (00)
Power
Method
Mean
Median
Best
Mean
Median
Best
Mean
Median
Best
Random
24
8.3 =07
0.124
36
30
#1
5.70
70
=7
15,4
Random 1x (.))
1.5
44
1:
41
1:1
106
23
Random (3-batched)
5
+11
=1
0.104
15
=1
10
#:
6.24
17.9
=04
17.0
=0.1
15.5
Lomaine
24
8.7 =0y
0,145
36
30
#:1
6.32
69
=6
19.7
=09
15.6
Raydin
5.5
6.8
0,144
23.4
26
6.00
17.80
17.94
15.4
Ours WmlL.
2.1 =..1
1.8 =02
0.130
8.1
7,60
0007
6.21
17.26
17.21 =00
15.6
Ours DD-LR-M
0.96
0.30=am
0.112
8.1
7,10 #:08
5.90
17.19
17.192=0.04
Ours Ours"D HDLLRRM
0.6 a.22
0.28 c.m:
0.139
8.1 4:03
7.47 1:006
6.04
16.69 om
16.76 2.0.2
15.4
Diff-through Opt
0.34
0,132
7.9 2.
7.13
5.88
17.15
17.184
15.5
Bayesian Optimisation
0.4 #0.1
0.23 0.00
0.106
7.3 #:2
6.9 #:02
6.22
16.08 0.09
16.2 =022
15.0
Table 7: Partial repeat of Table 2: final test cross-entropy on Fashion-MNIST. Now includes 32
repetitions of 30-sample Bayesian Optimisation, which is not considered in our emboldening.
Fashion-MNIST
Method
Mean
Median
Best
Random
0.92
+ 0.07
0.60
t.08
0.340
Random (x LR)
1.29
+ 0.08
1.2
0.3
0.339
Random (3-batched)
0.11
0.49
# 0.09
0.349
Lorraine
0.95
1 0.07
0.61
1 0.08
0.343
Baydin
0.409
1: 0.004
0.413
1 0.002
0.337
Ours WD+LR
0.373
+ 0.002
0.375
0.003
0.336
Ours WD+LR-M
0.369
+ 0.002
0.369
0.001
0.339
Ours WD+HDLR+M
0.398
+ 0.004
0.386
0.003
0.350
Siff-throoug-Opp
0.386
1 0.001
0.385
1 0.002
0.355
Bayesian Optimisation
0.3501 + 0.0005
0.3505
0.0007
0.344
To contextualise our methods against the best possible performance, we also perform 32 repetitions of 30-sample Bayesian Optimisation (BO) on selected UCI datasets, Kin8nm and Fashion-MNIST using the same procedure as Random to train each sampled configuration (but now with an separate validation set used to compare configurations), and record these in Tables and We use the Python BO implementation of Nogueira (2014), retaining the default configuration that the first five of our 30 initialisations be drawn randomly from the space. All runtimes are measured based on 8-way parallel execution per GPU. Although BO involves much greater computational burden than the other methods we consider, should more robustly estimate the optimal hyperparameters.
Our average performance falls short of the BO benchmark, but we come substantially closer than the Random and Lorraine baselines, and similarly as close as Diff- cofff-thouuh-OP On Pashion-MNISS especially, our methods are very competitive, achieving performance in the vicinity of BO with 30 times less computation. Considering our best runs, we seem to suffer only a minor performance penalty (compared the best hyperparameters
found) by adopting Algorithm 1.
As an additional comparison, we show in Figure 11 the evolution of incumbent best test loss over wall time during our previous training of 200 (UCI and Kin8nm)/100 (Fashion-MNISTT initialisations. Clearly we would expect BO's greater computation to result in smaller final losses, which we observe, but our methods principal benefit of our algorithm: with only a single training episode and relatively small runtime penalty, we achieve meaningful HPO effect, which reaches the vicinity of the ideal performance found by much slower and more computationally onerous methods.
capable of reaching performant results much faster than BO. This underscores the
25

---

Published as a conference paper at ICLR 2022
Test MSE (Unnormalised)
10a
Test MSE (Unnormalisee) lised)
Test MSE (Unnormalised)
10
10a
100
10-2
10
10?
10
10a
10
10a
Runtime (s)
Runtime (s)
Runtime (s)
(a) UCI Energy
(b) Kin8nm
(c) UCI Power
x
Test Cross-Entropy
Random
Random (x LR)
Lorraine
10a
Baydin
Ours WD+LR
6
Ours WD+LR+M
Ours WD+HDDL+M
4
Diff-through-Opt
10a
10a
Bayesian Öptimisation
Runtime (s)
+ Standard Error
(d) Fashion-MNIST
Figure 11: Evolution of incumbent best test MSE with time, during training of selected UCI Siailstt/Kinnnmmm//hhooonn--WV
from 200/200/100 random hyperparameter initialisations, with Bayesian Optimisation for comparison. Shaded envelopes are bootstrapped standard errors of the best loss found that time. Note the logarithmic horizontal axes.
26

---

Published as a conference paper at ICLR 2022
B.6 LARGE-SCAAS DATASETS
For Fashion-MNIST, Penn Treebank and CIFAR-1O, Figure 12 shows the empirical distributions of final test performance, contextualising the values shown in Table In addition, Figure 13 and Table 8 show our results in terms of error percentages for Fashion-MNIST and CIFAR-10.
1.0
1.0
0.8
0.8
0.8
Empirical CDF
Empirical CDF
Empirical CDF
0.6
0.6
0.6
0.4
0.4
0.4
0.0
0.0
x
10-1
60-1 10"
x 10"
10
10
10
10"
2 2
Final Test Cross-Entropy
Final Test Perplexity
Final Test Cross-Entropy
(a) MASIST using an MLP (b) Penn Treebank using an LSTM
(c) CIFAR-IU using a ResNet-16 18
Figure 12: Empirical CDFs of final test losses, trained on larger-scale datasets for 50%) epochs from (50 random SGD hyperparameter initialisations. Key as in Figure 13; notes as in Figure 9.
1.0
1.0
0.8
0.8
Random
Empirical CDF
Random (x LR)
Empirical
0.6
0.6
Random (3-batched)
Lorraine
0.4
0.4
Baydin
Ours WDHLR
0.2
0.2
Ours WD+LR-M
0.0
0.0
Ours WD+HDLR-M
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Diff-through-Opt
Test Error
Test Error
(a) Fashion-MNIS using an MI.P
(b) CIFAR-10 using a ResNet-18
Figure 13: Empirical CDFs of final test errors after training on larger-scale datasets for 50 epochs from each of 150 random initialisations of SGD hyperparameters. Notes as in Figure 9.
Table 8: Quantitative analysis of final test errors from Figure 13. Bold values the lowest in class.
Pashion-MNIST MNIST
CIFAR-
Method
Mean
Median
Best
Mean
Median
Best
Random
0.31
1 0.02
0.21
4: 0.02
0.116
0.46
4 0.02
0.44
=
0.243
Random (x LR)
0.46
0.03
0.37
+ 0.06
0.115
0.50
0.0
0.46
0.244
Random (3-batched)
0.20
0.141
0.009
0.119
0.41
0.39
0.245
Lorraine
0.32
0.22
0.120
0.46
0.03
0.36
0.206
Baydin
0.27
0.03
0.1499
0.117
0.40
0.02
0.41
0.220
Ours WD-LLR
0.1329
0.0007
0.133
1: 0.001
0.118
0.393
a: 0.008
0.399
0.004
0.207
Ours OurgWD-LRAA WD+LR+M
0.1318
0.0006
0.1316
1: 0.0006
0.119
0.386
0.008
0.396
0.005
0.204
Ours WD+HIDR+M
0.143
0.1384
0.122
0.44
0.02
0.45
0.268
Diff-through-OP
0.1376
0.0005
0.1372 + 0.0008
0.125
0.420 + 0.004
0.422
0.004
0.331
27

---

Published as a conference paper at ICLR 2022
B.6.1 RUNTIMES
600
Experiment Duration (s)
45000
20000
Experiment Duration
550
40000
Experiment Duration
15000
30000
450
25000
400
10000
20000
7500
15000
300
10000
5000
250
(a) Beshion-MMNSSY
(b) Penn Treebank
(c) CIFAR-10 -
Random
Random
Lorraine
Baydin
(x LR)
Diff-
Ours WD+LR
Ours WD+LR-M
Ours WD+HDLR-M
through-Opt
Mean Runtime
Median Runtime
Figure 14: Single-pas. runtime distributions for our larger-scale experiments. Worst-case complexities are dominated by second derivative computations, but remain competitive with conventional multi- pass HPO techniques, which scale our Random results by the number of configurations sampled.
For our larger-scale experiments, we illustrate comparative runtimes in Figure 14. More complex model architectures, with more learnable parameters, suffer greater computational cost from taking second derivatives with respect to each model weight, which appears more prominently Penn Treebank and CIFAR-10 10) experiments. However, our extension of Lorraine et al. (2020)'s method to additional hyperparameters doesn't dramatically increase runtimes: second derivative computations themselves responsible for most added complexity. In all three cases, scalar algorithms have runtimes within that of naïvely training two fixed hyperparameter initialisations (such those considered by Random), comparing extremely favourably HPO methods requiring repeated retraining. Naturally, the massive increase in the number of hyperparameters optimised by Ours HDLR- WD-HRR-- causes prominent jump in runtimes, but even this algorithm remains within practical factor of the Random baseline.
our
28

---

Published as a conference paper at ICLR 2022
B.6.2
BATCH NORMALISATION AND FASHION-MNIST
0.8
Empirical CDF
Random
Random LR)
Empirical
0.6
0.6
Random (3-batched)
Lorraine
0.4
0.4
Baydin
Ours WD+LR
0.2
0.2
Ours WD+LR-M
Ours WD+HDLRMM
10-1
10a
2x
x 10-1
109
2x100
6
10-1
6
10-1
Diff-through-Opp
Final Test Cross-Entropy
Final Test Cross-Entropy
(a) Without Batch Normalisation
(b) With Batch Normalisation
Figure 15: Comparing CDFs of final test cross-entropy from our Fashion-MNIST experiments of
Section 4.2: (a) as before, without batch normalisation; (b) with batch normalisation in our simple MLP model.
Table 9: Quantitative analysis of final test cross-entropies from Figure 15 - investigating the use of batch normalisation on Fashion-MNIST. Bold values are the lowest in class.
Without Batch Normalisation
With Batch Normalisation
Method
Mean
Median
Best
Mean
Median
Best
Random
0.92
1007
0.60
1008
0.340
0.88
1006
0.6
=011
0.333
Random (x LR)
1.29
+: 0.088
1:3
0.339
1.21
+: 0.08
1.1
=02
0.338
Random (3-batched)
0.8
+01
0.49
:009
0.349
0.42
0.02
0.37
= =0.01
0.340
Lorraine
0.95
0.61
1008
0.343
0.89
+
0.58
0.343
Baydin
0.409 0084
0.413
0.002
0.337
0.404
0.005
0.404
0.000
0.335
Ours WD
0.373 0.002
0.375
0003
0.336
0.380
0.002
0.381
0.004
0.338
Ours WD RIM
0.369 :: 0.002
0.369 +: 0.001
0.339
0.371
0.002
0.368
0.003
0.337
Ours WD+HDLRAN
0.398 0.004
0.386
0.003
0.350
0.41
0.01
0.388
0.002
0.348
Diff-through-Opt
0.386 J: 0.001
0.385 0.002
0.355
0.388
0.002
0.388
0.004
0.348
As batch normalisation rescales the parameter gradients for each training step, it is capable of further influencing how final performance is governed by learning rates and their variations. To study this effect, we repeat the FasHion-MNIST experiments described in Section 4.2 using batch normalisation in our simple MLP model. Our results are plotted alongside the non-batch normalised CDFs in Figure 15, with averages summarised in Table 9.
Subjectively, performance does not seem dramatically change when batch normalisation is invoked, with CDFs having broadly the same shape. Considering means and medians as our figures of merit (Table 9) suggests the same general pattern: generally, our algorithms benefit slightly from the absence of batch normalisation, and other algorithms benefit slightly from its presence, but there is not a unanimous trend. We conclude that, the context of this work, batch normalisation does not substantially improve hinder performance.
29

---

Published as a conference paper at ICLR 2022
B.7 EFFECT OF SHORT-HORIZON BIAS
Attempts quantify the effect of short-horizon bias in our experiments are frustrated by the need to perform computationaaly-intnnsii longer-horizon experiments, which has limited the scope of evaluations perform. However, we are able study the potential improvements of longer horizons three experimental settings.
B.7.1
TRUNCATED PROBLEM, FULL HORIZON
0.8
0.8
Empirical CDF
Empirical CDF
0.6
0.6
0.6
Empirical
0.4
0.4
0.4
0.2
0.2
0.2
10a
10
10-1
10a
Final Test (Unnormalised)
Final Test MSE (Unnormalised)
Final Test (Unnormalised)
(a) CDF: UCI Energy
(b) CDF: Kin8nm
(c) CDF: UCI Power
Test MSE (Unnormaiised)
102
Test MSE (Unnormalised)
Test MSE (Unnormalised)
10-2
10a
10-2
10a
x
10
10
109
10a
10P
10a
Runtime (s)
Runtime (s)
Runtime (s)
(d) Evolution: UCI Energy
(e) Evolution: Kin8nm
Evolution: UCI Power
1.0
1.0
10
0.8
Test Cross-Entropy
0.8
Empirical CDF
0.6
0.6
10a
Empirical
0.4
0.4
6 10-
0.2
4x-1-
4x
10
6x10
10a
2x
10a
10a
0.0
0.00
0.25
0.50
0.75
1.00
Final Test Cross-Entropy
Runtime
Test Error
(g) CDF: Fashion- MNIST (Loss)
(h) Evol'n n: Fashion-MNIS (Loss)
(i) CDF: Fashion -NNIST (Error)
Random Ours WD-LR+M
Diff-through-1e
Long Diff-through-Opt
Standard Error
Figure 16: CDFs of final test losses and evolutions bootstrapped median losses from 60 random initialisations shorter problem of 200 (UCI and Kin8nm) / 1000 (Fashion-MNIST) network weight updates, featuring full-horizon Long Diff-thruugh-Ot as described in Appendix B.
Firstly, consider the four study datasets UCI Energy/Power, Kin8nm and Fashion-MNIsT short- ening training so it only lasts for 200 (UCI and Kin8nm) 1000 Fashion-MNISTT network weight update steps. This shorter training episode means cannot compare results in Section 4, but
30

---

Published as a conference paper at ICLR 2022
Table 10: Quantitative analysis of UCI and Kin8nm final test performance from Figure 16, including full-horizon Long Dijf- thfouhhooghhtt on shorter problems as described in Appendix B.7.1. Bold values are the lowest in class.
UCI Energy
Kin8nm (x 000)
UCI Power
Method
Mean
Median
Best
Mean
Median
Best
Mcan
Median
Best
Random
40
17
19
3.19
56
63 =4
15.8
130 ::20
80 i: 30
18.5
Ours WD-LR+M
30
10
+3
2.24
57 +.
54
11.5
+:00
31 #
17.6
Diff- Seffthhrogh--pt
30
10
4:3
3.76
52
1:4
53
12.9
100
1:10
33 16
17.6
Long Difl-through-Op.
14
7.3
0.206
#2
=1
7.70
#
#2
15,9
Table 11: Quantitative analysis of Fashion-MNIST final test performance from Figure 16, including full-horizon Long Diffthrrugh--Ol on shorter problem as described in Appendix B.7.1. Bold values the lowest in class.
Final Test Cross-Entropy
Final Test Error
Method
Mcan
Median
Best
Mean
Median
Best
Random
0.1
1.04
0.408
0.45
1000
0.35
+ 0.09
0.146
Ours WD+LR+M
0.443
= 0.009
0.430
+: 0.033
0.401
0.156 1:2 0.002
0.155
+ 0.001
0.142
Diff- Diff-through-Opt
0.45 = 0.01
0.434
+: 0.002
0.406
0.159 0.002
0.1565
+ 0.0007
0.145
Long Diff-through-Opt
0.450 0.00s
0.436 +: 0.003
0.398
0.19 0.02
0.1574
+ 0.0009
0.140
does permit full-horizon aiffereniaaioon-rruugpppppiiiiii Long Diff-through-Ol does exactly this, performing 30 (UCI and Kin8nm) 50 (Fashion-MNIST) hyperparameter updates using the maximum look-back horizon and restarting training with the new hyperparameters after each update. In this sense, we use 30 or 50 times as much computation as in our other algorithms (here: Random, Oury WD+LR+M and Diff-through-Oit The latter update their hyperparameters at the same intervals as before, giving 20 (UCI and Kin8nm)/ 100 Frashoon-MNIS" updates overall. We take 60 random hyperparameter initialisations and run each of these four methods on them.
Our results are shown in Figure 16 and Tables 10 and 11. They show a stark contrast between datasets on UCI and Kin8nm trials, Long Diff-through-Oi manages, as expected, to achieve substantially improved final performance over its short-horizon competition, but on Fashion-MNIST, performance is much more similar between HPO algorithms. Wu et al. (2018) intuit short-horizon bias by describing the simple setting of a quadratic with different curvature magnitudes in each dimension, and expect the simpler UCI/Kin8nm datasets match this clean depiction of the optimisation space more closely than Rashion-MNIST Thus, we speculate the space of non-trivial datasets, such as Fashion-MNIST, is sufficiently complicated that merely eliminating short-horizon bias is insufficient to prevent the optimiser from getting stuck in memilarly-peffommnn local optima.
31

---

Published as a conference paper at ICLR 2022
B.7.2
FASHION-MNIST, MEDIUM HORIZON
2 10
0.8
Test Cross-Entropy
Empirical CDF
0.6
109
0.4
6 6000
0.2
4x10-
10-1
10"
2x
101
102
6 10-1
Runtime (s)
Final Test Cross-Entropy
(a) CDF (Loss)
(b) Evolution (Loss)
1.0
Random
Empirical CDF
0.8
Random (x LR)
Lorraine
0.6
Baydin
Ours WD+LR
0.4
Ours WDHLR+M
0.2
Ours WD+HDLR-M
Diff-through-Opp
Medium Diff- teff-ttrrugh-Opp
0.25
0.50
0.75
1.00
Test Error
+ Standard Error
CDF (Error)
Figure 17: CDFs of final test losses and evolutions of bootstrapped median losses from 100 random initialisations Fashion-MNIST, featuring Medium Diff-through-Opt with 200-step look-back horizon as described in Appendix B.7.2.
Table 12: Quantitative analysis of Fashion-MNIST final test performance from Figure 17, including Medium Diff-through-Op with a 200-step look-back horizon as described in Appendix B.7.2. Bold values are the lowest in class.
Final Test Cross-Entropy
Final Test Error
Method
Mean
Median
Best
Mean
Median
Best
Random
0.92
0.07
0.60
10.
0.340
0.31
2002
0.21
=002
0.116
Random (x LR)
1.29
+ 1.08
1.2
203
0.339
0.46
= 0.05
0.37
-0066
0.115
Random (3-batched)
0.1.
0.49
+000
0.349
0.20
= 0003
0.141
-0.099
0.119
Lorraine
0.95
0.07
0.61
0.343
0.32
0,02
0.22
0.120
Baydin
0.409 0.004
0.413
0.002
0.337
0.27
0.03
0.1499
0.0008
0.117
Ours WD+LR
0.373 0.002
0.375
0.003
0.336
0.1329
0.0007
0.133
0.118
Ours WD+LR-M
0.369 0.002
0.369 0.001
0.339
0.1318
0.0006
0.1316
0.0006
0.119
Ours WD-HDLR-M
0.398 + 0.004
0.386
0.003
0.350
0.143
+ 0.001
0.1384
0,000R
0.122
Diff Diff-through-Op
0.386
0.385
0.355
0.1376
0.1372
0.125
Medium Diff-through-Opt
0.400 +: 0.005
0.399 0.004
0.338
0.16
0.141 0.002
0.116
Next, we note our Fashion-MNIST experiments Section 4 run for 000 network weight steps, which can accommodate longer look-back horizon for the purposes of our study. We introduce a new algorithm, Medium Diff-through-pp which is identical to our previous Fashion-MNIST configuration, except the look-back horizon is now 200 steps, and the number of hyperparameter updates reduced to 50 to keep the same computational burden. This setting explores the trade-off between hypergradient accuracy and number of hypergradients computed. We apply this new configuration to the same 100 iterations as before, plotting combined results in Figure 17 and Table 12.
32

---

Published as a conference paper at ICLR 2022
Again, that Fashion-MNIST seems resilient to the short-horizon bias, with this medium- horizon configuration unable to substantially improve on our existing results. Naturally, since Medium Diff- Siff-thhoughOO Opr performs fewer hyperparameter updates, its performance may suffer if the hyperparameters have not converged, which we expect to be the likely cause here. However, is reassuring that methods are capable of performing well despite their short-horizon foundations.
33

---

Published as a conference paper at ICLR 2022
B.7.3
UCI ENERGY, FULL HORIZON
1.0
Test MSE (Unnormalised)
Random
0.8
Empirical CDF
Random (x LR)
104
Lorraine
Baydin
Ours WD+LR
Ours WD+LR-M
0.2
Ours WDHHDLR-M
Diff-through-Ope
0.0
10-1
10
10'
102
10
102
10
Full Diff-through-Opp
Final Test MSE (Unnormalised)
Runtime (s)
Standard Error
(a) CDF (Loss)
(b) Evolution (Loss)
Figure 18: CDF of final test losses and evolution of bootstrapped median losses from 200 random initialisations on UCI Energy, featuring 36 initialisations Full hiff-through-Op Opr with 4 000-step look-back horizon as described in Appendix B.7.3.
Table 13: Quantitative analysis of UCI Energy final test performance from Figure 18, including Full Diff- teff-through--oe Opt with 000-step look-back horizon as described in Appendix B.7.3. Bold values the lowest class.
Final Test MSE
Method
Mean
Median
Best
Random
24
4
8.3
0.7
0.124
Random (x LR)
35
13
13
1
0.113
Random (3-batched)
+
+
0.104
Lorraine
24
1.2
8.7
1.09
0.145
Baydin
5.5
1.0.2
6.8
1011
0.144
Ours WD+LR
2.1
+0.1
1.8
+02
0.130
Ours Ours WDDLLR+M
0.96
0.08
0.30
+000
0.112
Ours WD+HDLRMM
0.6
+02
0.28
1001
0.139
Diff-through-Opt
0.93
1.0.08
0.34
1.004
0.132
Full Diff-through-Opt
5.2
0.0
12
0.138
Finally, consider UCI Energy, whose size is more amenable to full-horizon studies. Our setting here, Full Diff-through-Opt extends the Diff-through-Ot configuration from Section by using full look-back horizon of 4 000 steps, restarting training after each hyperparameter update and performing 30 such updates. This permits full-horizon study on the same problem as before, using similar computational footprint to our Bayesian Optimisation trials of Appendix B.5 (that is. 30 times the cost of our original experiments). We consider 36 random initialisations for this algorithm, and combine the results with our original UCI Energy experiments, showing both in Figure 18 and Table 13.
Curiously, while Full Diff- through-Opt outclasses naïve Random approaches, is very uncompetitive with its short-horizon counterparts, achieving much higher average final losses (the larger variance being, of course, expected due smaller number of repetitions). The principal difference between Full Diff- siff-through--ee Opt and number of hyperparameter updates performed, since these are far more expensive in the former case. While more hyperparameter updates would likely cause Full Diff-throghh-Opp improve, the computational impact would be massive, with such a setting unlikely to be desired in practical applications. Again, we conclude that it is simplistic to claim noot-hooiioon bias renders an algorithm ill-suited to HPO - in reality, it is one of many factors worthy of consideration in the selection of approach. In this case, the larger number of updates we able perform by sacrificing horizon length leads to favourable performance improvements, even though this optimisation technically 'biased" as result.
Oott, apart from the different look-back distances, is the
performance
34

---

Published as a conference paper at ICLR 2022
Table 14: Final test MSEs after training UCI Energy as Table with dataset splits modified the indicated training/validationn/ proportions. Uncertainties are standard errors, and the values may be directly compared Table 1.
Detault (00)))
67.5% 5%/10%
36.25% 75%/00
45%M5%/O00
Mean
Median
Best
Mean
Median
Best
Mean
Median
Best
Mean
Median
Best
Ouns W
0.96 are
2.30
0.112
0.81
0.34
0.127
1.01 4:0
0.47 2:15
0.184
1.04 www
0.52
0.304
Ours MONHHROM
B.8 UCI ENERGY: FURTHER ANALYSIS
In light of our main results, we perform several additional experiments investigate particular aspects of our algorithm. These are conducted on the UCI Energy dataset, using the same configuration as in Section 4.1 except where otherwise noted.
B.8.1 VALIDATION DATASET SIZE
Noting that results for Ours WD-HDLR+M did not always outperform WD+ might have been expected, and considering the risk of overfitting to validation data, we consider the role the validation dataset might have to play on final test performance. The conventional vainiingvalliattionntss dataset split sizes we use throughout this paper produce training set which is substantially larger than vali- dation test, WB.HWD-D case, we have approximately the same number of hyperparameters as model weights, which is not the case in classical training. Thus, we posit that choosing larger validation dataset may permit improved hyperparameter tuning, addressing this performance gap.
In Table 14 we show results over 200 random initialisations, with bootstrapped error bars computed as in Section 4.1 We fix the test set size our default 10% of the available data (per Gal & Ghahramani (2016)), and vary the balance between training and validation data shown.
Both scalar and high-dimensional settings clearly benefit from larger validation dataset, with 67.5%/22.55%/099 split significantly improving performance. But Oury WD+HLLRM seems to exhibit less reliable, higher-variant behaviour at even larger validation splits, with Ours ODrSWD-RR+M also suffering worse performance in these settings. The differences between best-case performance in these algorithms suggest there is yet more to be understood about Our Our WD+HDLR-M setting. However, it is clear that with larger numbers of hyperparameters, we must take balance the competing demands for training and validation data.
35

---

Published as a conference paper at ICLR 2022
10a
Test MSE (Unnormalised)
10
ASHA Random
ASHA + Ours WD+LR-M
PBT Random
109
PBT Ours WD+LR+M
10a1
109
10
10a
10a
10a
10a
Runtime (s)
Figure 19: Evolution of incumbent best test MSE with time, during training of UCI Energy ASHA (114 286 initialisations) and PBT (200 training paths), with the threshold for "fully-trained" set at 4 4,000 iterations. Note the logarithmic axes.
Table 15: Extended reprise of Table 1: final test MSEs after training UCI Energy for 4 000 iterations, averaged over 200 initialisations. Also shown are statistics for the initialisations which survive to full training ASHA (out of 14 286 considered) and the final models produced by PBT (out of 200 training paths). Uncertainties are standard errors; bold values lie in the error bars of the best algorithm.
UCI Energy
Method
Mean
Median
Best
Random
24
2
8.3
007
0.124
Random (x LR)
35
3
13
+3
0.113
Random (3-batched)
5
2
+
0.104
Lorraine
24
8.7
0.145
Baydin
5.5
+ 0.2
6.8
#0111
0.144
Ours WD-LR
2.1
0.1
1.8
+02
0.130
Ours WD+LR+M
0.96
+ 0.088
0.30
1.000
0.112
Ours WD+HDLR+M
0.6
1 0.2
0.28
1.001
0.139
Diff-through-Opt
0.93
+
0.34
0000
0.132
ASHA Random
0.29
+ 0.09
0.191
00004
0.131
ASHA + Ours WD+LR+M
0.160 + 0.004
0.162
0.003
0.104
PBT Random
0.18 + 0.03
0.
+ 0.007
0.0934
PBT + Ours WD--RR-M
0.134 + 0.005
0.126
+ 0.003
0.119
B.8.2 ASYNCHRONOUS HYPERBAND AND POPULATION-BASE TRAINING
Finally, we consider two further non-gradient-based HPO strategies: Asynchronous Hyperband (ASHA: Li al. (2020b)) and Population-Baal Based Training (PBT; Jaderberg et al. (2017)). Both approaches exploit parallel computation to consider population of hyperparameter selections, and the performance each individual selection during training is used focus computational effort on the most promising trials. Broadly speaking, ASHA does this by terminating norly-performing trials early, while PBT locally perturbs trials or replaces them entirely with cetter-performing checkpoints. In this sense, ASHA and PBT are orthogonal to the type of algorithm seeks to improve the performance obtained by single initialisations trained in isolation. However, our algorithm can readily be combined with ASHA or PBT: by training each proposed hyperparameter choice using our algorithm instead fixing the hyperparameters as is conventional, we exploit our method's benefits for each individual run, thus providing ASHA/PBT with stronger population of
propose in this paper, which
36

---

Published as a conference paper at ICLR 2022
trials from which to make optimisation decisions. We demonstrate this synergy in the experiments of this section.
Throughout, we make use of the Ray Tune (Liaw al., 2018) library's implementation of these strategics, utilising the default settings unless noted, and consider the UCI Energy dataset using the same setup as in Section 4.1. For the Random setting, we do not combine the training and validation datasets, instead training with the former and reserving the latter for the evaluation of different initialisations by ASHA/PBT. For OD- setting, the validation set is used both for gradient- based hyperparameter updates during training and for configuration evaluation by ASHA/PBT. Otherwise, both settings are the same as in Section 4, and again we quote final losses on a held-out test set, with 1 000 full-dataset bootstrap samples used to compute standard errors. We also leave the hyperparameter search space unchanged from before (see Section B.3).
Asynchronous Hyperband For ASHA, we seek to match the 4 000 x 200 weight update steps performed in Section 4.1, with 4 000 steps still required for full training. Under the default settings of Ray Tune (no grace period, reduction factor 4, one bracket), of (1, 4, 16, 64, 256, 1 1024,4 4 000) iterations, with the number of initialisations surviving to each budget step correspondingly decreasing by a factor of 4 each time. Non-parallelised Hyperband (Li et al.. 2017) uses the same total computational effort for each budget step: applying this fact to the smallest computational budget gives that we must begin with 1000x200 114 286 initialisations for computational comparability. While the asynchronous modifications of ASHA introduce additional stochasticity, we assume the expected workload to be the same as the non-parallelised case. We run eight workers in parallel to mimic the experimental setting of our earlier studies.
obtain computational budgets
7x
From the results in Table 15, we see our hypothesis largely confirmed. By virtue of curating the population of initialisations, rather than considering each one in isolation, ASHA trivially gives improved average performance over all earlier methods. However, combining ASHA with Wur. yields significantly more performant population of trials on average, which leads to low-valued, low-variance mean and median final test performance. In both ASHA settings, the best final losses in the resulting populations are towards the lower end of those found our previous results, but do not beat the especially small loss found by Random (3-baiched). From this, we suppose that the methods we consider are nearing the performance limits of the UCI Energy dataset on this model when trained in this way. But regardless, we clearly see that deploying our algorithm in particular context tends to improve avcrage-case performance, indicating a positive influence on training.
Population-Bass Based Training For PBT, we again attempt to match the earlier computational burden by training 200 initialisations for 000 iterations using 8-way parallelism, acknowledging that PBT's checkpoint restoration will cause most runs to perform more than 4 000 weight update steps. We set the perturbation interval to 100 steps, so each initialisation has 40 opportunities to be mutated or reset by PBT. In PBT + Ours WD-LR+M it is unclear how to accommodate PBT's hyperparameter mutations, as our algorithm will have updated the hyperparameters PBT associates with each trial. Where we detect PBT has mutated the hyperparameters, we compute the ratio between the new and old values as seen by PBT, then apply that same ratio to mutate the true current value of the hyperparameters.
Our PBT results (Table 15) largely continue the pattern we have discussed. Combining our algorithm with PBT achieves substantial improvements in mean and median performance, giving the lowest values seen in any of our experiments on UCI Energy. PBT uses additional internal machinery to manage the population of hyperparameter initialisations, and we found this caused the total training time to considerably increase over the non-population-basee methods of Section 4.1, so the performance improvements we see here are perhaps unsurprising (see also Figure 19 and our discussion of runtimes below). However, in situations where we have already committed to the additional cost of PBT, replacing the fxxed-hyeerparamete internal training routine with our algorithm clearly results in a superior population of models, improving the quality of the models available for downstream applications. Note that the quality of the search over hyperparameter initialisations affects our overall best loss found, so some variation in the Best column of Table 15 is to be expected.
Runtime Analysis Figure 19 shows runtime analysis of these results on ASHA and PBT. We clearly that the superior performance of Ours OurSWD WD+IR+M in isolated training of specific hyperparameter initialisations causes ASHA reach low losses faster. In PBT, there is little difference in performance
37

---

Published as a conference paper at ICLR 2022
runtime when Random Ours is used as the internal learning strategy. Subjectively, this is likely because the overhead of saving checkpoints and restarting from them dominated the overall cost of running PBT. In both cases, PBT is substantially slower than ASHA to reach the most performant losses. Note by comparison with Figure 1 that our methods alone are competitive with ASHA when compare the evolution of incumbent best performance ASHA and PBT do not have access to the intermediate test losses plotted in Figure 19, so the smallest test losses found not necessarily achievable as an output of these methods.
time. Note also that
38

---

Published as a conference paper at ICLR 2022
C COMPLETE DERIVATION
Here, we reprise the derivations of Section 2 in more verbose form. Our subsections mirror those used previously.
C.I IMPLICIT FUNCTION THEOREM IN BILEVEL OPTIMISATION
Recall that we consider some model parameterised by parameters w, which we train to minimise a training loss Lr. Our training algorithm is governed by hyperparameters X, which simultaneously train to minimise a validation loss Lv. We target optimal w" and X1, defined by the bilevel optimisation problem
(3) X
arg min (A, w (A)), such that X
(b) w (A) arg CT w) (I revisited)
w
(1b) simply reflects standard model training procedure, with fixed X, so we need only consider how to choose the X from (la).
Suppose we seek gradient-based hyperparameter optimisation method for its performance potential. We then require the total derivative of the validation objective Lv with respect to the hyperparameters X, which may be obtained by the chain rule:
dLv dLv
dLv Ow
+
(2 revisited)
Yx
Ow 0x
An exact expression for 3w" 8x can be obtained by applying Cauchy's Implicit Function Theorem (Theorem 1). Suppose that for some X' we have identified locally optimal w', and assume &Cr, continuous differeetiability of Bw Then, there exists an open subset of hyperparameter space containing X', over which we can define function w" w"(2 (A) relating locally optimal w for each by
Ow 0x
8 LT @wowT
LT
(3 revisited)
ÖwoXT
Of course, the inverse Hessian term in (3) becomes rapidly intractable for models at realistic scale.
C.2 APPROXIMATE REST-RESPONSE DERIVATIVE
To proceed, we require an approximate expression for 0x iteratively by the rule
2w
Suppose model training proceeds (4 revisited)
(A = w;-1 - u(x, (A)),
where i is the current iteration and u is an arbitrary function differentiable in both its arguments. Note that the trivial choice
u w. w. - f(A, w
(12)
allows arbitrary differentiable weight updates f to be subsumed by this framework.
Differentiating with respect to À at the current hyperparameters X', we have:
Tw::
Ow:-1
du
(13)
0x
0A
x
x
X (2
Ow:-1
Tu Ow:-1
Ou
(14)
OX
Ow
0x
Ou
Ow:-1
Ou
(15)
dw
0A
x \
Ou
du
Ou
Ow:-2
Ou
+
I
an
Ow
dw
0x
0%
A (X-I
X ((
N (
(16)
Iu
Tu
Σ
(5 revisited)
Öw
05f<i
Ookkj
X(w:
x(2))
39

---

'''w They then isolate the Published as a conference paper at ICLR 2022
To combine terms in (5), must make approximations such that all bracketed expressions evaluated at the same X, w. For network weights w. we set Wo = w, = ww for all iterations i, have been at the optimal w for some time; when come to consider finite truncations the summation, this approximation will be especially appealing. With this approximation, we may collapse the product and write
effectively assuming
Ow: 0A
= 2-
Σ
II (SSK)
I
au dw
du 0%
(17)
Osici
--
Σ DSSSi
Ou ÜW
Ōu
(6 revisited)
ax
Xww((X))
As i increases, our training algorithm should converge towards locally optimal w', and the summation in (6) will accrue more terms. Instead, we reinterpret as specifying the finite number of terms we consider as an approximation to the whole sum. With this redefined we arrive at our approximate best-response Jacobian
~
Σ O5i<i
I
du
du
(6 revisited)
Ow
X
X'w"(AA)
C.3 CONVERGENCE TO
DERIVATIVE
To informally argue the convergence properties of our method, note that (6) is truncated Neumann
series:
Ow; 0x
Σ OSJ<c
du
Ou
(18)
Ow
ax
xw
Analogously its scalar equivalent the geometric series this series converges - if the is 'contractive' in some sense. For our purposes, suffices to assume a Banach space and, for the operator norm ||-||, that || the closed-form form limit expression for the Neumann series:
multiplicative term (I- - 2w
du
du
1. In this case, we can directly apply
ow
Ow: Ox
du
3 du
lim 1-000
RS
lim 11000
Σ
(19)
Ow
ax
A
A (X)
Ou
Ou
I
(20)
Ow
0x
Ou
(7 revisited)
Ow
0x
Note that (7) is exactly the result of the Implicit Function Theorem (3) applied weight update u. Concretely, suppose for some X" and w" that u(X", w") = O: in words, that our training process does not update the network weights at this point in weight-hyperparameter space, and assume u is continuously differentiable with invertible Jacobian. Then, over some subset of hyperparameter space containing X", we can say: w*()) exists, we have u(), w w*))) throughout the subspace and (hw" given by (7) exactly.
more general
Øx
C.4 SUMMARY OF DIFFERENCES FROM LORRAINE ET AL. (2020)
In their derivation, which closely parallels, Lorraine al. (2020) replace (4) with hard-coded SGD update step; in our notation, they fix u(>, w) usGD (A, w) 1) &Cr.
40

---

Published as a conference paper at ICLR 2022
learning rate 7, insisting all hyperparameters À must be dependent variables of the training loss Cr, before further differentiating the training loss in their derivation. Consequently, their algorithm cannot optimise optimiser hyperparameters such as learning rates and momentum factors, since these come into play only after the training loss has been computed and differentiated. While a careful choice of transformed loss function may allow certain optimiser hyperparameters to be handled by the framework of Lorraine et al. (2020) (e.g. setting L = nLT to incorporate a learning rate), this (e.g. incorporate momentum).
manual rederivation is far from trivial in more complex
Instead, we define a general weight update step (4), without assuming any particular form. We may then differentiate the general update u directly, encompassing any hyperparameters appearing within it but outside the training loss, which Lorraine et al. (2020) would miss. Crucially, this includes the optimisers, including SGD. Thus, we lift Lorraine et
hyperparameters of most gradient- results from expressions about 8Cr expressions about u, then update hyperparameters inaccessible 8w
to the former. Concretely: we optimise weight decay coefficients, learning rates and momentum factors in settings where Lorraine al. can only manage the weight decay alone.
41


Reviews:
[{"review_id": "tFdTBOo7I-O", "reviewer": "Reviewer_QKup", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper starts from (Lorraine, 2019) and that it can be generalized in a rather straightforward manner. Crucially, this generalization allows to tune optimizer parameters as well, such as learning rate and momentum. It is well known, and acknowledged by the original authors, that (Lorraine, 2019) is very sensitive to the correct choice of the step size eta, and the current work claims that by including this parameter into the optimization, these problems can be circumvented. At least in the experiments presented here, this is very convincingly the case. The paper certainly excels at fixing issues with (Lorraine, 2019). I am not so sure it adds very much on top of that.\n\nFirst, while the experiments cover a good range of different setups, they are a little set up to make the proposed approach look good compared to (Lorraine, 2019). Only 3 HPs are optimized over, 2 of which are optimizer parameters which the other method cannot tune, and the authors just leave them fixed. These problems do not seem to be very hard, given that the simple baseline of training 3x with random initialisations and picking the best is very competitive on all of them. And why only go for 3 HPs if you can compute a gradient? I have comments on the experiments below.\n\nTo me, an important question is what this work adds to the HPO state of the art in general. (Lorraine, 2019) is obviously quite limited, but so is the current work and all gradient-based HPO. What do you do with integer or categorical hyperparameters? How do you make use of parallel computations (which is key in practice)? How do you support modern optimizers like Adam or AdaGrad, which are not just a simple equation like (4)? Most importantly, how do you ensure robust behaviour, and in particular avoid catastrophic failures which hypergradient approximate methods are prone to? I'd love the paper to make some statements, and in general tell the reader what is done more here than fixing (Lorraine, 2019).\n\nFor a start, I'd love a much better explanation of what you say in 2.5, which I did not fully understand, including Figure 2. What you say here seems to be key to explain the advantages over (Lorraine, 2019). Can you underline this with some analysis and experiments?\n\nNext, is there a way to make your approach \"one step more accurate\"? Right now, you just do the same as (Lorraine, 2019) in terms of the assumptions (which are strong). Why not for example take w_i and w_{i-1}, then assume that derivs at w_j, j < i, are all equal to derivs at w_{i-1}, and that w_i -> w_*? Is that still tractable? Do you need new interesting tricks to make it work? This would add something to the machinery of (Lorraine, 2019).\n\nFinally, more comments on the experiments. They do serve to show that the current approach works better than (Lorraine, 2019) and another hypergradient approximation, on a setup which mostly tunes optimizer parameters. But I feel they do not do much more. First, overall running times are missing, so it is nearly impossible to see what the results mean. Nowadays, competitive HPO experiments show curves with wall-clock time on the x axis.\nMore importantly, an obvious baseline is missing: population based training (PBT). This is also tuning models while training them, and is strictly a constant factor more expensive than training a model once. This factor is spent on parallel compute. PBT is implemented in Ray Tune and should work out of the box. If you claim your method costs 3x more than one training, just use 3 parallel workers. Another meaningful baseline would be ASHA (https://arxiv.org/abs/1810.05934), also available in Ray Tune. You can run it with a time cutoff of about 3x a single training run.\n\nFor gradient-based HPO, there are probably two ways forward. Either (a) show that a method can work robustly and better than something simple like asynchronous Hyperband (ASHA) or PBT (see below), none of which are even close in methodological complexity, work in general settings. Or (b), find a meaningful setup which has a lot of HPs (they need to be continuous, though), argue why it is important, and then apply gradient-based HPO, because other methodology will not apply. But if you evaluate your gradient-based approach on simple setups like the ones used here, with 3 HPs, then you really have to do it in a way that includes non-gradient-based SotA HPO methods.\n", "summary_of_the_paper": "This paper is concerned with tuning continuous hyperparameters of a neural network setup (model, loss function and optimizer parameters) by way of a cheap approximation to the hypergradient. It is closely related to earlier work (Lorraine, 2019), which however overlooked that the idea can be generalized to optimizer parameters (e.g., learning rate, momentum), which is effectively done here. In a range of well-done experiments, the method is shown to very convincingly outperform (Lorraine, 2019), and in some cases even the \"gold standard\" approach to differentiate through the whole learning trajectory. Code is provided.\n", "summary_of_the_review": "This work provides a simple extension of earlier work (Lorraine, 2019), which ends up being rather important, since the former simply does not work very well at all on standard HPO problems. However, the work does not do much more than that, It stays methodologically very close to this earlier work, and does not really address any of the shortcomings of gradient-based HPO.\n\nThe experiments are well designed to show superiority over (Lorraine, 2019) and other gradient-based HPO, but lack comparison to relevant other HPO baselines (ASHA, PBT), and results are not presented in terms of time spent, so they are hard to interpret.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "spxp20aFLfR", "reviewer": "Reviewer_iZEW", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "**Strengths:**\n\n- The technical deductions look correct (although I did not check every line).\n- The authors are candid about the extent of their contribution and properly cited relevant literature.\n- The writing is overall clear. A number of clarifications and illustration figures were provided.\n- There are abundant experiments, with many comparisons among different methods and ablation studies of the proposed method.\n\n**Weaknesses, and questions to authors:**\n\nDespite the above strengths, there are some vague parts in the current version. I would raise my score if the authors could properly address the questions, and would suggest the authors incorporate them into the revision.\n\n- As (honestly) claimed in Section C.4, the technical advancement from Lorraine et al. (2019) seems incremental: In the framework of Lorraine et al. (2019), $\\mathcal{L}_T(\\lambda, w)$ could still be parameterized by optimization hyperparameters in the framework of the previous work, so that $u(\\lambda, w)$ could be expressed as a closed form. \nThe authors may want to provide more details around Algorithm 1 or Section 2.5 on how $u(\\lambda, w)$ is computed, and show a table of  examples on simple tasks (e.g., SGD on ridge regression) to clarify what $u(\\lambda, w)$ would look like, so that we can see why it is different from $\\eta \\partial \\mathcal{L}_T (\\lambda, w)/ \\partial w$. \n- The mean and median performance in Table 1 and 2 may not be quite meaningful in the hyperparameter tuning context: for the methods that do not optimize over optimization hyperparameters, “Best” instead of “Mean” or “Median” may be more interesting to practitioners. The 200 random initializations can be regarded as candidates selected in random search of hyperparameters, and users would want to pick the one with the smallest error (Of course, the small variance is still a plus). Are there examples of the best models (whose performance are in the “Best” column) found by different methods, so that readers can see how different they are? And, is the proposed method stable in terms of finding more similar models from different initializations? This type of information helps to show that learning rate tuning really matters on these datasets, since the best test MSEs are often achieved by other methods.\n- Why would a large $i$ be a problem for Algorithm 1 (as described in Section 4.3), when the weight $w$ is fixed in the “for j in 1 to i” loop? In fact, the first approximately equal sign in Equation 6 would become an equal sign here. \n\nAlso, the link to the source code points to an empty GitHub account.", "summary_of_the_paper": "This paper tackles the hyperparameter optimization problem with a one-pass approach that alternatively optimizes over machine learning model parameters and hyperparameters. To optimize over a bilevel optimization problem, this paper generalizes Lorraine et al. (2019) by replacing the gradient update of parameters with a more general parametric form, thus allowing the hyperparameters to be updated alongside parameters by gradients coming from truncated Neumann series. ", "summary_of_the_review": "This paper overall does a good job in presenting the technical contribution with deductions, pseudocode and experiments. Ambiguities do exist; I would encourage the authors to address them, so as to make the paper more readable. \n\n********* Updates after the discussion period *********\n\nThis paper is a good paper. I have increased my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZNggwral0p4", "reviewer": "Reviewer_c7so", "summary": "", "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": "Comments:\n1- \"Many machine learning methods are governed by hyperparameters: quantities which, unlike model parameters or weights, control the training process itself (e.g. optimiser settings, dropout probabilities)\"\nI am not sure I fully agree with this sentence. I am not an expert, but from what I understand, the dropout parameters have a direct influence on the model: different dropout probabilities leads to different models, whereas different learning rates should yield the same results (with different time of convergence).\nDo authors agree on this? Or did I miss something?\n\n2- In my opinion part 2.1, 2.2, and 2.3 and too handy, the theoretical result should be encapsulate in one proposition.\nWhat do authors mean by the approximation sign in (7)?\n\n3- I would say that the proposed algorithm is a \"one-pass\" algorithm.\nIn algorithm 1 there are somehow hidden nested for loops with the while + for t in 1 to T. It seems that authors are not proposing a \"one-pass\" algorithm, but more a warm-restart algorithm.\nAuthors themselves wrote: \"We emphasise training is not reset after each hyperparameter update — we simply continue training from where we left off, using the new hyperparameters. Consequently, Algorithm 1 avoids the time cost of multiple training restarts\".\nDo authors consider changing the name of the paper? Maybe something in the idea of \"Implicit differentiation to jointly tune model-based and non model-based hyperparameters\" ?\n\n4- Figure shows that the learning rate seems to converge toward a value around $1O^-1$, but the weight decay does not seem to converge. Do you think that the weighted decay is not converging? Or may the stepsize is too large for the weight decay? Could authors comment on that?\n\n5- Figure 4.b is extremely interesting. Just a question to be sure, it is written 400 hyperparameter updates, does it mean that the time budget for each \"square\" is different?\n\n6- In the experiments I would like to see the exact formula of the optimization problem which is solved (either in the main paper or in appendix). In my opinion this would make the paper clearer.\n\n7- What does \"myopic convergence to the local minima\" means?\nI a more general way, I my opinion, authors make a lot of statements that could be described as \"hand wavy\", for instance\n\"Similarly, we suppose a ‘momentum’ could, at every point, locally *squash the loss surface in the negative-gradient direction* and stretch it in the positive-gradient direction.\nIn aggregate, these transformations straighten out optimisation trajectories and *bring local optima closer to the current point*.\"\nThe word \"interpret\" is present 34 times in the paper: this contrasts with the lack of theoretical results.\n", "summary_of_the_paper": "Authors propose an extension of Lorraine 2019 to handle hyperparameters that control the convergence speed of the model: Lorraine 2019 \"only\" handled hyperparameters that were part of the model.\n\nThe extension seems a little incremental, but the paper is well written (except for the theoretical part), code is provided, the bibliography is quite extensive, and experiments show interesting improvements.\n\n", "summary_of_the_review": "In conclusion I vote for week rejection because the theoretical part is too hand wavy and IMO the paper cannot be published right now. In particular, IMO, the name of the paper should be changed.\nHowever, except this part, the paper is well written, and experiments are very interesting. If authors take into account the comments, I will raise my score.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ws4BQuC7dGT", "reviewer": "Reviewer_1R41", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "**Clarity**\n\nThe paper is well written and generally easy to follow. It also includes useful visualizations, such as in Figure 1, that give the reader good intuition on the proposed derivation. It also fits the work well in the context of related work both on standard and one-pass HPO techniques (e.g., Lorraine et al. (2019)).\n\n**Reproducibility**\n\nNot only do the authors carefully provide details on the baselines, benchmarks, dataset sources, compute machines used and experimental setup, but they will also open source their code to reproduce the experiments upon acceptance. While the authors have linked to an anonymous repository, code is not visible yet. It would have been ideal to release that already, but apart from that the work meets a good bar in terms of reproducibility.\n\n**Technical**\n\nThe work is well evaluated through experiments, which are performance on a large number of repetitions and illustrated with properly defined error bars. The proposed approximations are also theoretically grounded and converge to the ground truth best-response Jacobian as the size of the look-back window grows.\n\nOne weakness of the proposed approach is that it relies on a set of meta-hyperparameters, which the authors acknowledge. Ideally, their setting should be make automatic. In the absence of that, how would the author suggest setting them on a new problem? Is tuning on validation set required, or do they recommend some default values / can they give guidance on how to set them?\n\nRelated to that, I would have liked some clarifications on the following statement \"As some settings habitually chose unstable high learning rates, we clip these to [10−10 , 1]\" Why is that the case that unstable learning rates are used? Is this clipping a general recommendation?\n\nFurther, it was unclear to me why WD+HDLR+M would not perform well against the scalar baselines. The authors hint to learning rate regularisation for the high-dimensional dynamics setting, but some early results on that front would have further strengthened the paper.\n\n**Minor**\n\nA few of the listed references are pointing to arXiv when the respective paper was also published at a peer-reviewed venue. I recommend the authors to double-check those and update accordingly.\n\n", "summary_of_the_paper": "The paper aims to accelerate HPO optimization by allowing for retraining when new hyperparameters are proposed, while being faster and more flexible that existing hypergradient-based one-pass methods. This results in a novel HPO one-pass technique that works with any continuous hyperparameter within a differentiable model weight update, such as learning rates. In a good range of experiments, the authors show that their proposal is faster than baselines.", "summary_of_the_review": "I am inclined towards acceptance, only weakly so at this stage as guidance on setting the introduced meta-hyperparameters could be improved and the unexpected results obtained with WD+HDLR+M are lacking follow-up experiments. That said, this is overall solid work which is well-evaluated both theoretically and empirically.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a method for with tuning continuous hyperparameters (HPs). It is closely related to a previous work (Lorraine, 2019) that was limited to certain HPs, and in particular could not be applied to HPs controlling the learning such as learning rate, momentum, and are known to be influential to the convergence and overall performance (for non-convex objectives). 
The reviews indicate a uniform opinion that the paper tackles an important problem, that its methods provide a non-trivial improvement over previous techniques and in particular those of (Lorrain, 2019), and that the provided experiments are extensive and convincing. The initial reviews had several concerns about technical details in the paper such as the analysis or how the meta-hyperparameters are tuned. However, in the discussions the authors provided adequate responses, resolving these concerns. I believe that with minor edits that are possible to get done by the camera-ready deadline the authors can incorporate their responses into the paper making it a welcome addition to ICLR.
Decision: Accept (Spotlight)