Scheduling the Learning Rate Via Hypergradients: New Insights and a New Algorithm
Authors: Michele Donini
Luca Franceschi
Orchid Majumder
Massimiliano Pontil
Paolo Frasconi
Venue:  (2020)
Keywords: automl
hyperparameter optimization
learning rate
deep learning

Abstract: We study the problem of fitting task-specific learning rate schedules from the perspective of hyperparameter optimization.  This allows us to explicitly search for schedules that achieve good generalization. We describe the structure of the gradient of a validation error w.r.t. the learning rates, the hypergradient, and based on this we introduce a novel online algorithm. Our method adaptively interpolates between two recently proposed techniques (Franceschi et al., 2017; Baydin et al.,2018), featuring increased stability and faster convergence. We show empirically that the proposed technique compares favorably with baselines and related methodsin terms of final test accuracy.

Under review as a conference paper at ICLR 2020
SCHEDULING THE LEARNING RATE VIA HYPERGRA- DIENTS: NEW INSIGHTS AND A NEW ALGORITHM
Anonymous authors Paper under double-blind review
ABSTRACT
We study the problem of fitting task-specific learning rate schedules from the perspective of hyperparameter optimization. This allows us to explicitly search for schedules that achieve good generalization. We describe the structure of the gradient of a validation error w.r.t the learning rate, the hypergradient, and based on this we introduce novel online algorithm. Our method adaptively interpolates between the recently proposed techniques of Franceschi et al. (2017) and Baydin et al. (2018), featuring increased stability and faster convergence. We show empirically that the proposed method compares favorably with baselines and related methods in terms of final test accuracy.
INTRODUCTION
Learning rate (LR) adaptation for first-order optimization methods is one of the most widely studied aspects optimization for learning methods - in particular neural networks with early work dating back to the origins of connectionism (Jacobs, 1988; Vogl et al., 1988). More recent work focused on developing complex schedules that depend on a small number of hyperparameters (Loshchilov & Hutter, 2017: Orabona & Pál, 2016). Other papers in this area have focused on the optimization of the (regularized) training loss (Schaul et al., 2013; Baydin et al., 2018; Wu et al., 2018). While quick optimization is desirable, the true goal of supervised learning which is commonly estimated by holding out part of the available data for validation. Hyperparameter optimization (HPO), related but distinct branch of the literature, specifically focuses on this aspect, with less emphasis on the goal of rapid convergence on a single task. Research in this direction is vast (see Hutter al. (2019) for an overview) and includes model-based (Snock et al., 2012; Hutter et al., 2015), model-free (Bergstra & Bengio, 2012; Hansen, 2016), and gradient- based (Domke, 2012; Maclaurin al., 2015) approaches. Additionally, works in the area of learning to optimize (Andrychowicz et al., 2016 Wichrowska et al., 2017) have focused on the problem of tuning parameterized optimizers on whole classes of learning problems but require prior expensive optimization and are not designed to speed up training on a single specific task.
minimize the generalization error,
The goal of this paper is to automatically compute an online fashion a learning rate schedule for stochastic optimization methods (such as SGD) only the basis of the given learning task, aiming at producing models with associated small validation error. We study the problem of finding a LR schedule under the framework of gradient- 2017): we consider as an optimal schedule 17" = (No...., -) E IR. a solution to the following constrained optimization problem
hyperparameter optimization (Franceschi et al.,
min (fr (1) = F(wr(1)) : 17 IR. s.t. Wo = w, w++1(1) (w Bt)
(1)
for = f0 ",....,T--1... 13 [T]. where E Rd - R is an objective function, 4, Rd x R, Rd (possibly stochastic) weight update dynamics, w Rd represents the initial model weights (parameters) and finally w/ are the weights after t iterations. We can think of E as either the training or the validation loss of the model, while the dynamics & describe the update rule (such as SGD, SGD-Momentum, Adam etc.). For example in the case of SGD, (,W,, (t) = we nh V (ww.) with (w)) the (possibly regularized) training loss on the t-th minibatch. The horizon T should be large enough that the training error can be effectively minimized, in order to avoid underfitting.
Note that a too large value of T does not necessarily harm since 7) = 0 for k > still a feasible solution, implementing early stopping in this setting.

---

Under review as a conference paper at ICLR 2020
Problem (1) can be in principle solved by any HPO technique. However, most HPO techniques, including those based on hypergradients Maclaurin et al. (2015) or on bilevel programming formulation (Franceschi et al., 2018; MacKay et al., 2019) would not be suitable for the present purpose since they require multiple evaluations of f (which, in turn, require executions of the weight optimization routine), thus defeating one of the main goals of determining LR schedules, i.e. speed. In fact, several other researchers (Almeida et al., 1999; Schraudolph, 1999; Schaul et al., 2013; Franceschi et al., 2017; Baydin et al., 2018; Wu et al., 2018) have investigated related solutions for deriving greedy update rules for the learning rate. A common characteristic of methods in this family is that the LR update rule does not take into account information from the future. At a high level, we argue that any method should attempt to produce updates that approximate the true and computationally unaffordable hypergradient of the final objective with respect the current learning rate (in relation to this, Wu et al. (2018) 18) discusses the bias deriving from greedy or short-horizon optimization). In practice, different methods resort to different approximations or explicitly consider greedily minimizing the performance after a single parameter update (Almeida et al., 1999; Schaul et al., 2013; Baydin et al., 2018). The type of approximation and the type of objective (i.e. the training or the validation loss) in principle separate issues although comparative experiments with both objectives and the same approximation are never reported in the literature and validation loss is only used in the experiments reported in Franceschi al. (2017).
One additional aspect needs to be taken into account: even when the (true or approximate) hypergra- dient is available, one still needs to introduce additional hpperaryperprraeetees in the design of the online learning rate adaptation algorithm. For example in Baydin et al. (2018), hyper-hypepprranetess include initial value of the learning rate Th and the hypergradient learning rate We find in our experiments that results can be quite sensitive to the choice of these constants.
In this work, we make a step forward in understanding the behavior of online gradient- hyperparameter optimization techniques by (i) analyzing in Section 2 the structure of the true hypergradient that could be used to solve Problem (1) if wall-clock time was not a concern, and (ii) by studying in Section 3 some failure modes of previously proposed methods along with detailed discussion of the type of approximations that these methods exploit. In Section 4, based on these algorithm which reliably produces competitive
considerations, we develop a new hypergradient-baat learning rate schedules aimed at lowering the final validation error. The algorithm, which we call MARTHE (Moving Average Real-Time Hyperparameter Estimation), has a moderate computational cost and can be interpreted as a generalization of the algorithms described in Baydin et al. (2018) and Franceschi al. (2017). Unlike previous proposals, MARTHE is almost parameter-free in that incorporates heuristics to automatically tune its configuration parameters (i.e. hyper-typerparameters)) In Section 5, we empirically compare the quality of different hypergradient approximations in small scale task where true hypergradient can be exactly computed. In Section 6, we present a set of real world experiments showing the validity of our approach. We finally discuss potential future applications and research directions in Section 7.
2 STRUCTURE OF THE HYPERGRADIENT
We study the optimization problem (1) under the perspective of gradient-based hyperparameter optimization, where the learning rate schedule (No..... .pr.......p... -1) is treated as a vector of hyperpa- rameters and T is a fixed horizon. Please refer to Appendix A for summary of the main notation used throughout the paper. Since the learning rates are positive real-valued quantities, assuming both E and are smooth functions, we can compute the gradient of ʃ E R²", which is given by dwr
fr(()) = ob VE()), where tby = dn
E dRx
(2)
where "T" means transpose. The total derivative urt can be computed iteratively with forward-mode algorithmic differentiation (Griewank & Walther, 2008; Franceschi et al., 2017) as
with A = ÖD, m.).
B, = DD, m7.)
w = 0, úi+11 = Anir + Br,
(3)
Ow:
On
The Jacobian matrices A, and B, depend on We and n). but we will leave these dependencies implicit ease our notation. In the case of SGD!. A.
and [Br], = -.g V L. where
'Throughout we use SGD to simplify the discussion, however, similar arguments hold for any smooth optimization dynamics such as those including momentum terms.
2

---

Under review as a conference paper at ICLR 2020
subscripts denote columns (starting from 0), 6t, = = and otherwise and He is the Hessian of the training emror on the t-th mini-batch 2. We also note that, given the high dimensionality of reverse-mode differentiation would result in a more efficient (running-time) implementation. We use here forward-mode both because it is easier to interpret and visualize and also because it is closely related to the computational scheme behind MARTHE, as we will show in Section 4. Finally, we note that stochastic approximations of Eq. (2) may be obtained with randomized telescoping sums (Beatson & Adams, 2019) or hyper-networks based stochastic approximations (MacKay et al., 2019).
Eq. describes the so-called tangent system (Griewank & Walther, 2008) which is discrete affine time-variant dynamical system that measures how the parameters of the model would change for infinitesimal variations of the learning rate schedule, after iterations of the optimization dynamics. Notice that the "translation matrices"' B, are very sparse, having, at any iteration, only one non-zero column. This means that [itl] remains for all j 2 t: T) affects only the future parameters trajectory. Finally, for a learning rate the derivative (a scalar) is
0fr(n) [VT(())) On
[
Ao s-1+1
II
Be
VE(WT) VL,,w,, V VE(TT)
(4)
where the last equality holds true for SGD. Eq. (4) can be read as the scalar product between the gradients the training error at the (-th step and the objective E at the final iterate, transformed by the accumulated (transposed) Jacobians of the optimization dynamics, shorthanded by p As apparent from Eq. (4), given wt, the hypergradient of 77 is affected only by the future trajectory and does not depend explicitly on 7/--
:+1
In its original form, where each learning rate is left free to take any permitted value, Eq. (1) represents a highly nonlinear setup. Although, in principle, it could be solved by projected gradient descent, in practice it is unfeasible even for small problems: evaluating the gradient with forward-mods is inefficient in time, since requires maintaining a (large) matrix tangent system. Evaluating it with reverse-mon mode is inefficient in memory, since the entire weight trajectory (w:) should be stored. Furthermore, it can be expected that several updates of 1) are necessary to reach convergence where each update requires computation of fr and the entire parameter trajectory in the weight space. Since this approach is computationally very expensive, we turn out attention to online updates where n) is required to be updated online based only on trajectory information up to time
ONLINE GRADIENT-BASED ADAPTIVE SCHEDULES
Before developing and motivating our proposed technique, we discuss two previous methods to compute the learning rate schedule online. The real-time hyperparameter optimization (RTHO) algorithm suggested in (Franceschi et al., 2017), reminiscent of stochastic meta-descent (Schraudolph, 1999), is based on forward-mode differentiation and uses information from the entire weight trajectory by accumulating partial hypergradients. Hypergradient descent (HD), proposed in (Baydin et al., 2018) and closely related the earlier work of Almeida et (1999), aims minimizing the loss w.r.t. the learning rate after one step of optimization dynamics. It uses information only from the past and current iterate.
Both methods implement update rules of the type
T/ = max |M- 3An), 0],
(5)
where An, is online estimate of the hypergradient, 3 > 0 is step-size or hyper-learning rate and the max ensures positivity². To ease the discussion, we omit the stochastic (mini-batch) evaluation of the training error L and possibly of the objective E.
Note that techniques based on implicit differentiation (Pedregosa, 2016; Agarwal et al., 2017) or fixed-port point equations (Griewank & Faure, 2002) (also known recurrent backpropagation (Pineda, 1988)) cannot be readily applied compute fr since the training loss J. does not depend explicitly on 17. Updates could be also considered in the logarithmic space as done e.g. by Schraudolph (1999); we find it useful, however, to let 77 reach ( whenever needed, offering natural way implement early stopping in this context.
3

---

Under review as a conference paper at ICLR 2020
Learning rate scheduies
Best obj value varying e Beale
Learming rate schedules
150
10t
10th
Best dby value vayyng B Bukin
10
1.0
0.00
MBn RTRO
10
0.07
3
Figure 1: Loss surface and trajectories for 500 steps of gradient descent with HD and RTHO for Beale function (left) and (smoothed and simplified) Bukin N. 6 (right), Center: best objective value reached within 500 iterations for various values of / that do not lead to divergence.
The update rules* are given by
A
ARTH TJ:
Σ
1+1 Bi
V((w));
A HD T/ = B V((w)
(6)
for RTHO and HD respectively, where P T. As it can be seen A ARTHO = ADD +r((+r my a the correction term can be interpreted as an "oo-trajectory approximations" of longer horizon objectives as we will discuss in Section 4.
Although successful in some learning scenarios, we argue that both these update rules suffer from (different) pathological behaviors, as HD may be "shortsighted", being prone to underestimate the learning rate (as noted by Wu al. (2018)), while RTHO may be too slow to adapt sudden changes of the loss surface or, worse, may be unstable, with updates growing exponentially in magnitude. We exemplify these behaviors in Fig. 1, using two bidimensional test functions" from the optimization literature, where we set = L. and we perform 500 steps of gradient descent, from a fixed initial point. The Beale function, on the left, presents sharp peaks and large plateaus. RTHO consistently outperforms HD for all probed values of 3 that do not lead to divergence (Fig. 3 upper center). This can be easily explained by the fact that in flat regions gradients are small in magnitude, leading to A HD to be small as well. RTHO, on the other hand, by accumulating all available partial hypergradients and exploiting second order information, is capable of making faster progress. We use simplified and smoothed version of the Bukin function N. 6 to show the opposite scenario (Fig. 3 lower center and right). Once the optimization trajectory closes the valley of minimizers y = 0.01ær, RTHO fails to discount outdated information, bringing the learning rate first to grow exponentially, and then to suddenly vanish to O, as the gradient changes direction. HD, on the other hand, correctly damps and is able to maintain the trajectory close to the valley.
These considerations suggest that neither A RTHO nor A HD provide globally usefuu update directions, as large plateaus and sudden changes the loss surface are common features of the optimization landscape of neural networks (Bengio et al., 1994; Glorot & Bengio, 2010). Our proposed algorithm smoothly and adaptively interpolates between these two methods, as we will present next.
OUR PROPOSAL: MARTHE
In this section, we develop and motivate MARTHE, an algorithm for computing LR schedule online during single training run. This method maintains an adaptive moving-average over approximations of Eq. (4) of increasingly longer horizon, using the past trajectory and gradients to retain a low computational overhead. Further, we show that RTHO (Franceschi et al., 2017) and HD (Baydin et al., 2018 8) outlined above, can be interpreted as special cases of MARTHE, shedding further light on their behaviour and shortcomings.
(Franceschi et al., 2017) the authors the hyperparameter updated every K iterations. Here we focus on the case K = 1 which better allows for a unifying treatment. HDD is developed using as objective the training loss L rather than the validation loss E. We consider here without loss of generality the case of optimizing E.
We use the Beale function defined as L(x, w) = (1.5 x ry)² (2.25 x 22 (2.625 + xy 2 and a simplified smoothed version of Buking N. 6: T(x, v) = / V(y 0.01z)² + E, with
4

---

Under review as a conference paper at ICLR 2020
Shorter horizon auxiliary objectives. For K > 0, define 9x E), with & E R as
gK(u, E) = EE) s.t. ug = u, U4+1 = (u,, E.) for i i= [K]. The 9k's define class of shorter horizon objective functions, indexed by K, which correspond to the evaluation of E. after K steps of optimization, starting from u E TRe and using & as the L.R schedule Now, the derivative of 9K w.r.t. Eo. denoted 9x. is given by
(7)
gK (n,, 5) Ogk {) = |Bol Pf-IVE((x) = PP
(8)
aEo
where the last equality holds for SGD dynamics. Once computed on subsets of the original optimiza- tion dynamics (w:))[o- the derivative reduces for K to s (ure. 7/.)
VV (for SGD dynamics), and for K = T - t to fr-e(we: (1), ( = [V(()). Intermediate values of K yield cheaper, shorter horizon approximations of (4).
Approximating the future trajectory with the past. Explicitly using any of the approximations given by 9K (w) 1) AT) is, however, still largely impractical, especially for K >>>>> 1. Indeed, it would be necessary to iterate the map + for K steps in the future, with the resulting (w++)))
iterations discarded after a single update of the learning rate. For K E [t], we may then consider evaluating 5'k exactly K steps in the past, that is evaluating dxx (W;-x, K; -x)= Selecting K = indeed equivalent to A HD, which is computationally inexpensive. However, when past iterates are close to future ones (such as in the case of large plateaus), using larger K"s would allow in principle to capture longer horizon dependencies present in the hypergradient structure of Eq. 4. Unfortunately the computational efficiency of K does not generalize to K > since setting An. I'x would require maintaining K different tangent systems.
Discounted accumulation of g.s.. The definition of the gKs, however, allows one highlight the recursive nature of the accumulation of 9K- Indeed, by maintaining the vector tangent system
Zo = [Bo(uo Eo)lo Z1+1 = H4, 2 + [B, for i2 0, Z: E R
(9)
computing (u. EkS1 / 1oK-1-'gx-- (", (5, (() Z VE(K)) from SK-1 requires only updating (9) and recomputing the gradient of E for a total cost of O(c()) per step both in time and memory using fast Jacobians vector products (Pearlmutter, 1994) where c(() is the cost of computing the optimization dynamics (typically c( O(d). The parameter μ E [0, 1] allows to control how quickly past history is forgotten. One can notice that A ARTHO,, nRe = S,, (ny (m))) while μ 0 recovers A HD TJc. Values of μ < 1 help discounting outdated information, while as μ increases so does the horizon of the hypergradient approximations. The computational scheme of Eq. is quite similar to that of forward-mode algorithmic differentiation for computing ú (see Section 2 and Eq. 3); we note, however, that the "tangent system" in Eq. 9, exploiting the sparsity of the matrices B,, only keeps track of the variations w.r.t the first component Çu. drastically reducing the running time.
Adapting/ μ and 3 online. We may set Ar,. = S (wa, (1)) This still would require choosing a fixed value of μ., which should be validated on separate set of held-out data. This may add an undesirable overhead on the optimization procedure. Furthermore, as discussed in Section 3, different regions of the loss surface may benefit from different effective approximation horizons. To address these issues, we propose to compute μ online. Ideally, we would like to verify that An, VV [f)] > 0, ie. whether the proposed update is descent direction w.r.t. the true hypergradient. While this is unfeasible (since V fn) is unavailable), we can cheaply compute, after the update W++1 = T (ww,, mp), the quantity
q(ue) = Am-1 gi (we, Te) = (H:A,Zi11 +
(10)
which, post, relates μe, to the one-step descent condition for gi. We set P++1 hy (g(uz) where h1 is monotone scalar function with range in [0, 1] (note that if #4 = 0 then Eq. 10 is non-negative).
For space limitations, defer the discussion of the choice of h, and the effect of adapting online the approximation horizons to the Appendix. We can finally define the update rule for MARTHE as
Am
11
pg
gi- (wi, (1))
(11)
6 Note that, formally, and are different from 17 and from the previous sections; later, however, we will evaluate the gæ's 's on subsequences of the optimization trajectory.
5

---

Under review as a conference paper at ICLR 2020
We further propose adapt 3 online, implementing with this work a suggestion from Baydin et al. (2018). We regard the LR schedule as a function of 3 and apply the same reasoning done for n, keeping μl 0, to avoid maintaining an additional tangent system which would involve third order derivatives of the training loss L. We then set / = 3 - BBrj++ 1 Ant, where, with a little notation override, B becomes fixed step-size for adapting the hyper-learning rate. This may seem useless trade-off at first; yet, as we observed experimentally. one major advantage of lifting the adaptive dynamics by one more level is that it injects additional stability in the learning system, in the sense that good values of this last parameter of MARTHE lays in much broader range range than those of good hyper-learning rates. In fact, we observe that when 3 is too high, the dynamics diverges within the first few optimization steps, whereas, when it does not, the final performances are rather stable.
Algorithm presents the pseudocode of MARTHE. The runtime and memory requirements of the algorithm are dominated by the computation of the variables Z. Being these structurally identical to the tangent propagation of forward mode algorithmic differentiation, we conclude that the runtime complexity is up to four times that of the underlying optimization dynamics & and the memory requirement up to two times (see Griewank & Walther, 2008, See. 4). We suggest the default values of BB 0 and n7u 0 when prior knowledge of the task at hand is available. Finally, we suggest to wrap Algorithm in a selection procedure for B, where one may start with a high enough 3 and aggressively diminish it (e.g. decimating it) until the learning system does not diverge.
Algorithm 1 MARTHE; requires B. no. 8
Initialization of w. 17 and Zo <- O, Po < 0 for t T do
T f- max [77 B, Am 0]
{Update LR if > 0)
7++1 <- 14 Zz + [Br(wr, mele
(Tangentt system update] )
Wr+1 +- D, me)
(Parameter update]
Me+1 f (g((e(
(Compute μr, see Eq. 10) { (Update hyper-LR)
Bi+1 + Be BAT++1 Ant
end for
5 OPTIMIZED AND ONLINE SCHEDULES
In this section, we empirically compare the optimized LR schedules found by approximately solving Problem by gradient descent (denoted LRS-OPT), where the hypergradient is given by Eq. 4, against HD, RTHO MARTHE schedules where for MARTHE we consider both the adaptation schemes for μ and 3 presented in the previous section as well as fixed hyper-leaming rate and discount factor μ. We are interested in understanding and visualizing the qualitative similarities among the schedules, as well as the effect of and 3 and the adaptation strategies on the final performance measure. To this end, we trained feedforward neural networks, with three layers of 500 hidden units each, on a subset of 7000 MNIST (LeCun al., 1998) images. We used the cross-entropy loss and SGD the optimization dynamics 4. with a mini-batch size of 100. We further sampled 700 images to form the validation set and defined E to be the validation loss after T 512 optimization steps (about 7 epochs). For LRS-OPT, we randomly generated different mini-batches at each iteration to prevent the schedule from unnaturally adapting
specific sample progression" We initialized 1/ 0.01 1312 for ORS- and set nu = 0.01 for all adaptive methods, and repeated the experiments for 20 random seeds (except LRS- OPT. repeated only for seeds). Results are visualized in Figure
Figure 2 (left) shows the LRS-OPT schedules found after 5000 iterations of gradient descent: the plot reveals a strong initialization (random seed) specific behavior of 17" for approximately the first 100 steps. The LR schedule then stabilizes or slowly decreases up until around 50 iterations before the final time, at which point it quickly decreases (recall that with LRS-OPT all 7hs including no. are optimized "independently" and may take any permitted value). Figure 2 (center) present qualitative comparison between the offline LRS-OPT schedule and the online ones. HD generates schedules that quickly decay to very small values, while RTHO schedule linger or fail to decrease, possibly causing instability and divergence in certain cases. Fixing μ = 0.99 seems to produce schedules that
We retained, however, the random initialization of the network weights, to account for the impact that this may have on the initial part of the trajectory (see Figure 2 (left).. This is done to offer more fair comparison between IRS-OPT and online methods, which compute the trajectory only once.

---

Under review as a conference paper at ICLR 2020
LRS-OF
MARTHE
0.96
HD
0.99
0.94
0.4
PV
HD
0.2
100 200
300
400
500
10-
1.00 200
400
Isorationn
Figure 2: Left: schedules found by LRS-OPT (after 5000 iterations of SGD) on 4 different random seeds. Center: qualitative comparison between offline and online schedules for one random seed. For MARTHE with fixed μa, we report the best performing one, For each method, we report the schedule generated with the value of | that achieves the best average final validation accuracy. Plots for the remaining random seeds can be found in the appendix. Right: Average validation accuracy of over 20 random seeds, for various values of 3. When no point is reported means that the achieved average accuracy for that configuration falls below 88% (or diverged). For reference, the average validation accuracy of the network trained with = 0.01 1512 87.5%, while LRS-OPT attains 96.2%.
remarkably mimic the the optimized one; yet, unfortunately, this happens only for a small range of values of μ which expect to be task dependent. Using both the adaptation schemes for μ and (curve named MARTHE in the plots), allows to reliably find highly non-trivial schedules that capture the general behavior of the optimized one (additional plots in the Appendix).
Figure 2 (right) shows the average validation accuracy over 20 runs (rather than loss, for easier interpretation) of the online methods, varying 3 and discarding values below 88% of validation accuracy. In particular, fixing > 0 seems to have a beneficial impact for all tried values of the hyper-leaming rate 3. Using only the heuristic for adapting μ online (blue line, named hy in the plot) further helps, but is somewhat sensitive to the choice of 3. Using both the adaptive mechanisms, beside improving the final validation accuracy, seems to drastically lower the sensitivity on the choice of this parameter, provided that the learning system does not diverge. Finally, we note that even with this very simple sctup, a single run of LRS-OPT (which comprises 5000 optimization steps) takes more than 2 hours an M-40 NVIDIA GPU. In contrast, all adaptive methods requires less than minute to conclude (HD being even faster).
6 EXPERIMENTS
We run experiments with an extensive set of learning rate scheduling techniques. Specifically, we compare MARTHE against the following fixed LR scheduling strategies: (i) exponential decay (ED) where the LR schedule is defined by Th- 71 (ii) staircase decay and (iii) stochastic gradient descent with restarts (SGDR) by Loshchilov & Hutter (2017). Moreover, we compare against online strategies such HD and RTHO For all the experiments, we used single Volta V100 GPU (AWS P3.2XL). We fix the batch-size at 128 samples for all the methods, and terminate the training procedure after a fixed number of epochs (200). We set L the cross entropy loss with weight-decay regularization (with factor of 5- 10-2) and set E as the unregularized cross entropy loss on validation data. All the experiments with SGDM have initial learning rate (71) of 0.1 and for Adam, we set it 3 10-1 For staircase. we decay the learning rate by 90% after every 60 epochs. For exponential decay, we fix decay factor of 0.99 per epoch, and for SGDR we use To 10 and Tmuit 2. For HD and RTHO, we set the 3 as 10 - and 10 respectively. Momentum for SGDM is kept constant to 0.9, For Adam we used the standard values for the remaining configuration parameters. We run all the experiments with 5 different seeds reporting average and standard deviation, recording accuracy, loss value and generated learning rate schedules.
We trained image classification models two different datasets commonly used to benchmark optimization algorithms for deep neural networks: CIFAR-10 (Krizhevsky et al., 2014) where we trained VGG-11 11 (Simonyan & Zisserman, 2014) network with BatchNorm (loffe & Szegedy, 2015) using SGDM as the inner optimizer, and CIFAR- 100 (Krizhevsky et al., 2014) where we trained a ResNet- 18 (He et al., 2016) using Adam (Kingma & Ba, 2014). The source code in PyTorch and TensorFlow to reproduce the experiments will be made publicly available.
In Figures 3 and 4, we report the results of experiments for CIFAR-10 with VGG- 11 and CIFAR- 100 with ResNet- 18 respectively. For both figures, we report from left to right: accuracy in percentage, validation loss value, and example of generated learning rate schedule.
7

---

Under review as a conference paper at ICLR 2020
Volidation
VGG
70
0.30
Exponential
0.06
RTHO
0.02
MARTHE
25
50
79
100
125
150
175
200
29
30
75
100 125
150
375
200
25
30
75
300
125
150
179
200
Figure 3: Results of VGG-11 CIFAR-I0, and SGDM as the inner optimizer concerning: (Left) accuracy, (Center) loss of objective function on validation set and (Right) generated learning rate schedule for each method.
Learning Curve CO Roo
1.00
Validaton Loss
CIFARLOO Rustett
Ie-4
Learning
120
2.5
1.0
2.0
1.3
Stalrcase
EODR
100-
1.0
0.3
0.8
Eseen
Spech
100
200
Figure 4: Results of ResNet-18 on CIFAR-100, and Adam the inner optimizer concerning: (Left) accuracy, (Center) loss of the objective function on the validation set and (Right) generated learning rate schedule for cach method.
MARTHE produces LR schedules that lead to trained models with very competitive final validation accuracy in both the experimental settings, virtually requiring tuning. For setting the hyper-learning rate step-size of MARTHE we followed the simple procedure outlined at the end of Section 4, while for the other methods we performed grid search select the best value of the respective algorithmic parameters. On CIFAR-10 10, MARTHE obtains a best average accuracy of 92.79% statistically on with SGDR (92.54%), while clearly outperforming the other two adaptive algorithms. On CIFAR- 100, MARTHE leads to faster convergence during then whole training compared to all the other methods, reaching an accuracy of 76.68% comparable to staircase schedule with 76.40%. We were not able to achieve competitive results with SGDR in this setting, despite trying several values of the two main configuration parameters within the suggested range. Further, MARTHE produces aggressive schedules (see Figure 3 and 4 right, for an example) that increase the LR at the beginning of the training, sharply decreasing it after few epochs. We observe empirically that this leads to improved convergence speed and competitive final accuracy.
Additional experimental validation is reported Appendix D and includes results for MARTHE with an initial learning rate 1jo- O.
CONCLUSION
Finding good learning rate schedule an old but crucially important issue in machine learning. This paper makes a step forward, proposing an automatic method to obtain performing LR schedules that uses an adaptive moving average over increasingly long hypergradient approximations. MARTHE interpolates between HD and RTHO taking the best of the two worlds. The implementation of our algorithm is fairly simple within modern automatic differentiation and deep learning environments, adding only moderate computational overhead over the underlying optimizer complexity.
In this work, we studied the case optimizing the learning rate schedules for image classification tasks; we note, however, that MARTHE is general technique for finding online hyperparameter schedules (albeit scales linearly with the number of hyperparameters), possibly implementing competitive alternative in other application scenarios, such as tuning regularization parameters (Luketina et al., 2016). We plan to further validate the method both in other learning domains for adapting the LR and also to automatically tune other crucial hyperparameters. We believe that another interesting future research direction could be to learn the adaptive rules for μ and / in a meta learning fashion.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning in linear time. The Journal of Machine Learning Research, 18(1):4148 2017.
Luís B Almeida, Thibault Langlois. José D Amaral, and Alexander Plakhov. Parameter adaptation in stochastic optimization. In On-line learning in neural networks, pp. 111-134. Cambridge University Press, 1999.
Marein Andrychowiez, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, pp. 3981-3989, 2016.
Atilim Gunes Baydin, Robert Cornish, David Martínez-Rubio, Mark Schmidt, and Frank D. Wood. Online learning rate adaptation with hypergradient descent. Proc. of the 6th Conf. on Learning Representations (ICLR), 2018. URL http: / /ttp:////xxvv..m/ www.v.owgg.ooo..o..ooooo..oo.oor org/ abs 1701 04782.
Alex Beatson and Ryan P. Adams. Efficient optimization of loops and limits with randomized telescoping sums, ArXiv, 2019.
Yoshua Bengio, Patrice Simard, Paolo Frasconi, et al. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13(Feb):281-305 2012. URL http:// //www jmlr.org/
html.
Justin Domke. Generic Methods for Optimization Modeling, AISTATS, volume 22, pp. 318- 326, 2012. URL http://www. jmlr. http:///www.klpccccc/ccccoce//// /atppppps/////ttmmee/2222 1 domke1 1.w.e......f...... pdf.
I Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1165-1173, 2017. URL https: / waw.iiiiivvo.oo/..aa//aa org.iiiiioooooooooooooooooo wwwg/aaao abs/ 1703. 01785.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, and Massimilano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In Proceedings of the 35th International Conference on Machine Learning- Volume 70, pp. 1568-1577, 2018. URL https: /arxiv. orq/ abs//bb/// 1806 04910.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Andreas Griewank and Christele Faure. Reduced functions, gradients and hessians from fixed-point iterations for state equations. Numerical Algorithms, 30(2):113-139, 2002.
Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation, volume 105. Siam, 2008
Samantha Hansen. Using deep g-learning to control optimization hyperparameters, arXiv preprint arXiv:1602.04002. 04000004462,,.. 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708. 2017.

---

Under review as a conference paper at ICLR 2020
Frank Hutter, Jörg Lücke, and Lars Schmidt-Thieme. Beyond Manual Tuning of Hyperparam- eters. KI Kimsstliche Intelligenz, 29(4):329-333 November 2015. ISSN 0933-1875, 1610- 1987. doi: 10. 10.10077s13211-01155111 s s1321 8- 015-005111111
URL attp://lingg http:///w......iie..e.eoo
Frank Hutter, Lars Kotthoff, and J. Vanschoren. Automatic machine learning: methods, systems. challenges. Springer. 2019. URL https: htpps://www /wwww www.aaa..oooggaa.......... htw.a//m...///ooooooottttt/a/.pa 201 ///2//aau/// htt//autommlboooe pdff.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXivv1502.03167, 2015.
Robert A Jacobs. Increased rates of convergence through learning rate adaptation. Neural networks, 1(4):295-307, 1988.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. online: http://www. cs. toronto. edu/kriz/cifar haml, pp. 4, 2014.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86:1)):277-22324 1998.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. ICLR, 2017.
Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient- based tuning of continuous regularization hyperparameters, In International conference machine learning, pp. 2952-2960, 2016.
Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprint arXiv:1903.0330 2019.
Dougal Maclaurin, David Duvenaud, and Ryan P. Adams. Gradient-based hyperparameter opti- mization through reversible learning. Proceedings of the 32nd International Conference on Machine Learning, 2015. URL http: //ww: jmlr wwtpp//occeeeiggs....ooooo http:////g/ppppp/////////
maclaurin15.c .pd...
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training learned optimizers. In International Conference on Machine Learning, pp. 1556-4565 2019.
Francesco Orabona and Dávid Pál. Coin betting and parameter-free free online learning. In Advances in Neural Information Processing Systems, pp. 577-585, 2016.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
Fabian Pedregosa.
Hyperparameter optimization with approximate gradient. In Proceedings of the 33rd International Conference on Machine Learning, 2016.
Fernando J Pineda. Generalization of back propagation to recurrent and higher order neural networks. In Neural information processing systems, pp. 602-611, 1988.
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. In International Conference on Machine Learning, pp. 343-351, 2013.
NN Schraudolph. Local gain adaptation in stochastic gradient descent. In 1999 Ninth International Conference on Artificial Newral Networks ICANN 99. Publ. No. 470), volume 2, ppppp.5. 569 5694574. IET, 1999.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
10

---

Under review as a conference paper at ICLR 2020
Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In Advances in neural information processing systems, pp. 2951-2959, 2012.
Thomas P Vogl, JK Mangis, AK Rigler, WT Zink, and DL Alkon. Accelerating the convergence of the back-propagation method. Biological cybernetics, 59(4-5):257-23,, 1988.
Olga Wichrowska, Niru Maheswaranathan, Matthew W Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Nando Freitas, and Jascha Sohl-Dickstein. Learned optimizers that scale and generalize. In International Conference Machine Learning, pp. 3751-3760, 2017.
Yuhuai Wu, Mengye Ren, Renjie Liao, and Roger Grosse. Understanding short-horizon bias in stochastic meta-optimization. arXiv preprint arXiv: 2018.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:/605.077 2016.

---

Under review as a conference paper at ICLR 2020
A
TABLE OF NOTATION
Please refer to Table for a summary and description the notation used throughout the paper.
Table I: Notation, with description and examples when appropriated, in order of appearance.
Notation
Description
Examples and notes
T E N
Total number of iterations, horizon
E Rd
Model parameters, inner optimization vari- ables
Weights of a neural net- work
7 (no. ................................ 71-1)
Learning rate schedule (LRS), hyperparam- eter
(r( e IR+
Response function after T iterations (w.r.t. the LRS)
E(w) E R+
Response function (w.r.t. the parameters) Training loss
Validation error
L((w)& E R
(2r, Th) E Rdd
Optimization (weight update) dynamics
SGD: By Me) = w. 1): (w+)
i RdxT
Total derivative of w.r.t 7) variable of the tangent system
A,
ab: (w)
Jacobian of the dynamics w.r.t the weights Jacobian of the dynamics w.r.t. the LRS
SGD: A, = 1 nHH
ow,
B.
aN (1)
SGD:
On
[Bi] = -es (L((w,
P Iii A
Product of Jacobians from iteration to Update for the learning rate at iteration t Hyper-learning rate HD update RTHO update
An
3 R
A HD
See (Baydin et al., 2018)
A ARTHO
See (Franceschi et al., 2017)
gA (u, E R+
Shorter horizon objectives, with horizon K, u starting point and & 2 0 R LRS Derivative of 9ж w.r.t. &1 Dampring factor
g' (((
4
7 E Rd
Variables of the vector tangent system Online accumulation shorter horizon derivatives d'x
Cf. tangent matrix ú
Sk, m) ER
hp
Heuristics for dampening factor μ
See Appendix B
B CHOICE OF HEURISTIC FOR ADAPTING μ
We introduced Section a method to compute online the dampening factor based on the quantity
q(ux) A o' (wr, We) (HAAZ VV [B:]] ((:41)).
We recall that if q((a) is positive then the update 27)+1 is descent direction for the one step approximation of the objective fr. We describe here the precise heuristic rule that use in our experiments. Call q(u)) = max(min(q(pe) gí (We, m)) 1), 0) E [0, 1] the normalized, thresholded 4(44). We propose set
M++1 (ux) ((1)) with = 0, C++1 11 ct).
where et acts as multiplicative counter, measuring the effective approximation horizon. The resulting heuristics is independent on the initialization of μ since Zo O. We note that whenever is set to 0, the previous hypergradient history is forgotten. Applying this heuristic to the optimization of the two test functions of Sec. 3 reveals to be successful: for the Beale function, h2 selects μ4 for all while for the smoothed Bukin. it selects μ4 = for around 40% the iterations, bringing down the minimum optimality gap 10-0 for 0.0005.
12

---

Under review as a conference paper at ICLR 2020
We conducted exploratory experiments with variants of h, which include thresholding between -1 and and "penalizing" updates larger than gi without observing statistically significant differences. We also verified that randomly setting (4 0 does not implement successful heuristics, while introducing another undesirable configuration parameter. We believe, however that there is further space of improvement for b (and possibly to adapt the hyper-learning rate), since oi does not necessarily capture the long term dependencies of Problem 1. Meta-lcarning these update rules could be an interesting direction that we leave future investigation.
C OPTIMIZED AND ONLINE SCHEDULES: ADDITIONAL DETAILS
We show in Figure 5 the LR schedules for the experiments described in Section 5 for the remaining random seeds. The random seed controls the different initial points wp. which is the same for all online methods and for LRS-OPT, and determines the mini-batch progression for the online methods (while for LRS-OPT the batch progression is randomized at each outer iteration).
0.8
LRS-OPT
0.8
LRS-OPT
0.8
UNS-OPT
WARTHE
MARTHE
MARTHE
0.8
0.4
0.2
300
300
400
100
300
400
500
300
200
300
580
Figure 5: Comparison between optimized and online schedules for the remaining three seeds. For each method, we report the schedule generated with the hyper-learning rate (or step-size for adapting it) that achieves the best final validation accuracy.
D ADDITIONAL EXPERIMENTAL RESULTS
We report in this section additional experimental results to complement the analysis of Section 6.
Figure 6 shows accuracy, validation loss and learning rates schedules for CIFAR-100 dataset with a ResNet-18 18 model and SGDM as (inner) optimization methods. accordance with previous experimental validation (Zagoruyko & Komodakis, 2016; Huang et al., 2017) we set the initial learning rate 77u to 0.1 for all methods. We include also relevant statistics for MARTHE,- that is MARTHE obtained by letting the schedule start (cyan lines in the plots). Setting Y/o is clearly not an optimal choice, nevertheless MARTHE is able to obtain competitive results also in this disadvantaged scenario, producing schedules that quickly reach high values and then sharply decrease within the first 40 epochs. Figure (left) reports sample of generated schedule. It is important highlight how the heuristic methods, such exponential decay, are able to handle 7uu O. In fact, for non adaptive methods, To is indeed another configuration parameter that must be tuned. MARTHE,, on the other hand, constitute a virtually parameterless method (3 can be quickly found with the strategy outlined at the end of Section 4) that can be employed in situations where we have no prior knowledge the task at hand. Conversely as noted by Maclaurin al. (2015) and Metz al. (2019), too high (initial) learning rates not well suited for gradient-based adaptive strategies: instability of the inner optimization dynamics indeed propagates to the hypergradient computation, possibly leading "exploding" hypergradients.
Finally, we tried another configuration of parameters for SGDR, in order to make the last restart completing the training exactly after 200 epochs. We selected TĄ 10 and Traat 2.264 (i.e. restarts at 10, 33, 84, 200). Figure 7 and Figure report the same experiments of Section with this slightly different baseline. We note that the performance of SGDR remains similar.
13

---

Under review as a conference paper at ICLR 2020
Leaminn Curve
CIFARLCO Restiit
Validation Loss
CIFARLOO RecNect
Learting Rate CIFAR100 Restet
120
0.08
Expemential
100
RTTO
MARTHE
0.09
30
75
100
200
Fpech
Figure 6: Results ResNet-18 on CIFAR-100, and SGDM as inner optimizer concerning: (Left) accuracy, (Center) loss of the objective function on the validation set and (Right) generated learning rate schedule for each method. In cyan we report the results for MARTHE with 0.
Learning Curve
CARRO VGG
Val dation Less
CIFARLO VGG
Learning Rate CIFARLO VGG
60
0.32
60
0.08
Exposential
0.04
MARTHE
300
125
10
150 375
209
100
225
190
Spoch
Epoch
Sparch
Figure 7: Results of VGG-11 CIFAR-I0, and SGDM as the inner optimizer concerning: (Left) accuracy. (Center) loss of objective function validation set and (Right) generated learning rate schedule for each method.
E SENSITIVITY ANALYSIS OF INADAPTIVE MARTHE WITH RESPECT TO 7J0+ 1 AND
In this section, we study the impact of To- μ and 3 for MARTHE, when our proposed online adaptive methodologies for and 3 are not applied. We think that the sensitivity of the methods is very important for the HPO algorithms to work well in practice, especially when they depend on the choice of some (new) hyperparameters such as μ and B.
We show the sensitivity of inadaptive MARTHE with respect do and μr, fixing 3. We used VGG-11 on CIFAR-10 with SGDM as optimizer, but similar results can be obtained in the other cases. Figure shows the obtained test accuracy fixing 3 to 10-7 (Left) and 10- (Right). The plots show certain degree of sensitivity, especially with respect to the choice of a (fixed) This suggest that implementing adaptive strategies to compute online the dampening factor and the hyper-learning rate constitute an essential factor to achieve the competitive results reported in Section 6 and Appendix D.
Hate C1 AlLEc Hachwl
2.0
70
7.0
130
scon
1.5
HD
RIHO
90
100
200
150
Epoch
Figure 8: Results ResNet-18 18 on CIFAR-100, Adam as the inner optimizer concerning: (Left) accuracy. (Center) loss of the objective function on validation set and (Right) generated learning rate schedule for cach method.
14

---

Under review as a conference paper at ICLR 2020
16-07
1e-08
85
0.999
75
70
0.99999
16-05
0.0001
0.001
0.01
0.1
1e-05
0.0001
0.001
mp
0.01
0.1
60
Figure 9: Sensitivity analysis of inadaptive MARTHE with respect to no and μ fixing the value of to 10-7 (Left) and 10 (Right). We used VGG-11 on CIFAR-10 with SGDM optimizer. Darker colors mean lower final accuracy.
15


Reviews:
[{"review_id": "SkgnLRm0tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The results are given only for the CIFAR datasets. Even for these two datasets the authors use very outdated networks, e.g., the best error rate for CIFAR-10 is in order of 6 percent. One should use contemporary/bigger networks, e.g., WRNs published in 2016 would give you about 4 percent. \n1) The initial learning rate for CIFAR-10 and CIFAR-100 are different, respectively 0.1 and 0.0003. The use of such small initial learning rate for CIFAR-100 is not motivated especially given that it is usually in order of 0.05 or 0.1 when resnets are considered. \n2) The authors don't compare to cosine annealing without restarts which is a pretty strong baseline. \n3) The authors compare to SGDR but don't set its initial number of epochs in a way that its last restart convergences at around 200 epochs. \n4) The proposed method has its own hyperparameters which greatly influence the results as shown in the appendix. I suspect that setting these hyperparameters is exactly what controls the slope of the learning schedule. \n\nOverall, the results are not convincing. The authors show that the previous adaptive approaches don't work well on the CIFAR datasets (despite the fact that their authors claimed the oppositve) and I don't think that the paper contains enough material to avoid the situation that futures approaches will claim similar things about the current study. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxaEj1zqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors introduce a hypergradient optimization algorithm for finding learning rate schedules that maximize test set accuracy. The proposed algorithm adaptively interpolates between two recently proposed hyperparameter optimization algorithms and performs comparably in terms of convergence and generalization with these baselines.\n\nOverall the paper is interesting, although I found it a bit dense and hard to read. I frequently found myself having to scroll to different parts of the paper to remind myself of the notation used and the definition of the different matrices. This makes it harder to evaluate the paper properly. The proposed algorithm seems interesting however, and the experimental results look quite impressive.\n\nI have a few concerns regarding the experiments however, which explains my score:\n\n1. In figure 2, does MARTHE diverge for values of beta greater than 1e-4? This seems to indicate that MARTHE is somehow more sensitive to beta than the other variations used. Do the authors have any intuition about what might be causing this behavior?\n\n2. The initial learning rate for SGDM and Adam was fixed at certain values for all experiments. Why is this a reasonable thing to do? It feels like MARTHE should be compared to SGDM and Adam at least when the initial learning rate is tuned for these properly. Otherwise, it doesn't feel like a fair evaluation? To the best of my knowledge, the final achieved accuracies achieved with MARTHE however seem quite competitive with the best results typically reached with tuned SGDM on the convolutional nets used in the paper.\n\n3. The learning rate schedules found by MARTHE seem to be somewhat counterintuitive. While an initial increase matches the heuristic of warmup learning rates frequently used when training convnets, the algorithms seems to decrease down the learning rate after that even quicker than what the greedy algorithm HD does. Do the authors have any intuition why this can lead to such a big improvement in performance over HD?\n\n4. Is it possible to provide some sort of estimate of how much computation MARTHE requires compared to a single SGDM run? How feasible is to test this algorithm on a bigger classification model on ImageNet?\n\nI think this paper is borderline, although I am leaning towards accepting it given the impressive empirical results. It would really improve the paper if the readability was improved, as well as if larger experimental results were included.\n\n====================================\n\nEdit after rebuttal:\nI thank the authors for their response. I am happy with their response and am sticking to my score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: First, I'd like to apologize once again for failing to secure a third reviewer for this paper. To compensate, I checked the paper more thoroughly than standard.

The area of online adaptation of the learning rate is of great importance and I appreciate the authors' effort in that direction. The authors carefully abundantly cite the research on gradient-based hyperparameter optimization but I would have appreciated to also see past works on stochastic line search (for instance  "A stochastic line-search method with convergence rate") or statistical methods ("Using Statistics to Automate Stochastic Optimization").

The issue with these methods is that, despite usually very positive claims in the paper, they are not that competitive against a carefully tuned fixed schedule and end up not being used in practice. Hence, it is critical to develop a convincing experimental section to assuage doubts. Unfortunately, the experimental section of this work is a bit lacking, as pointed by both reviewers. I would like to comment on two points specifically:
- First, no plot uses wall-clock time as the x-axis. Since the authors state that it can be up to 4 times as slow per iteration, the gains compared to a carefully tuned schedule are unclear.
- Second, the use of a single (albeit two variants) dataset also leads to skepticism. Datasets have vastly different optimization properties and, by not using a wide range of them, one can miss the true sensitivity of the proposed algorithm.

While I do not think that the paper is ready for publication, I feel like there is a clear path to an improved version that could be submitted to a later conference.
Decision: Reject