Budgeted Training: Rethinking Deep Neural Network Training Under Resource Constraints
Authors: Mengtian Li
Ersin Yumer
Deva Ramanan
Venue:  (2020)
Keywords: budgeted training
learning rate schedule
linear schedule
annealing
learning rate decay

Abstract: In most practical settings and theoretical analyses, one assumes that a model can be trained until convergence. However, the growing complexity of machine learning datasets and models may violate such assumptions. Indeed, current approaches for hyper-parameter tuning and neural architecture search tend to be limited by practical resource constraints. Therefore, we introduce a formal setting for studying training under the non-asymptotic, resource-constrained regime, i.e., budgeted training. We analyze the following problem: "given a dataset, algorithm, and fixed resource budget, what is the best achievable performance?" We focus on the number of optimization iterations as the representative resource. Under such a setting, we show that it is critical to adjust the learning rate schedule according to the given budget. Among budget-aware learning schedules, we find simple linear decay to be both robust and high-performing. We support our claim through extensive experiments with state-of-the-art models on ImageNet (image classification), Kinetics (video classification), MS COCO (object detection and instance segmentation), and Cityscapes (semantic segmentation). We also analyze our results and find that the key to a good schedule is budgeted convergence, a phenomenon whereby the gradient vanishes at the end of each allowed budget. We also revisit existing approaches for fast convergence and show that budget-aware learning schedules readily outperform such approaches under (the practical but under-explored) budgeted training setting.

Published as a conference paper at ICLR 2020
BUDGETED TRAINING:
RETHINKING DEEP NEURAL NETWORK TRAINING UNDER RESOURCE CONSTRAINTS
Mengtian Lit Carnegie Mellon University mt mtlii cmu. edu
Ersin Yumer!
Deva Ramanan CMU & Argo Al
Uber ATG Deyymeer@gmall com
deva@cs. cmu, edu
ABSTRACT
In most practical settings and theoretical analyses, one assumes that a model can be trained until convergence. However, the growing complexity of machine learning datasets and models may violate such assumptions. Indeed, current ap- proaches for hyper-parameter tuning and neural architecture search tend to be limited by practical resource constraints. Therefore, we introduce a formal set- ting for studying training under the non-asymptotic, resource-constraiiee i.e., budgeted training. We analyze the following problem: "given a dataset, algo- rithm, and fixed resource budget, what is the best achievable performance?" We focus on the number of optimization iterations as the representative resource. Un- der such a setting, we show that it is critical adjust the learning rate schedule according to the given budget. Among budget-aware learning schedules, we find simple linear decay to be both robust and bigh-performing.. We support our claim through extensive experiments with state-of-the- models on ImageNet (image classification), Kinetics (video classification), MS COCO (object detection and instance segmentation). and Cityscapes (semantic segmentation). We also ana- lyze our results and find that the key to good schedule budgeted convergence, phenomenon whereby the gradient vanishes at the end of each allowed budget. We also revisit existing approaches for fast convergence and show that budget- aware learning schedules readily outperform such approaches under (the practical but under-explored) budgeted training setting.
regime,
INTRODUCTION
Deep neural networks have made undeniable impact in advancing the state-of-the-art for many machine learning tasks. Improvements have been particularly transformative in computer vi- sion (Huang et al. 2017b He et al. 2017). Much of these performance improvements were enabled by an ever-increasing amount of labeled visual data (Russakovsky et al. 2015] Kuznetsova et al.
2018) and innovations in training architectures (Krizhevsky et al. 2012 He al. 2016).
However, as training datasets continue to grow in size, we argue that an additional limiting factor is that of resource constraints for training. Conservative prognostications of dataset sizes particularly for practical endeavors such as self-driving cars (Bojarski et al.) (016), assistive medical robots TTylor al.] 2008), and medical analysis (Fatima & Pashal (017)) suggest one will train on datasets orders of magnitude larger than those that are publicly available today. Such planning efforts will become more and more crucial, because in the limit, it might not even be practical to
visit every training example before rumning out of resources (Bottou 1998 Rai et al. 2009).
We note that resource constraieed training already is implicitly widespread, as the vast majority of practitioners have access to limited compute. This is particularly true for those pursuing research directions that require a massive number of training runs, such as hyper-parameter tuning (Li al.)
2017) and neural architecture search (Zoph & Le 2017
Cao et al. 2019 Liu et al. 2019)
Work done while Argo AT.

---

Published as a conference paper at ICLR 2020
100
Off-the-shelf
Val Itllttvv Accu (%)
Training Loss
Our
80
90
Our (Envelape)
Off-the-shelf
60-
Ours
Budget
Ours [Erielopel)
100
Training Budget Epoch
Tralining Budget Epoch
We formalize the problem of budgeted training, in which one maximizes performance subject to a fixed training budget. We find that simple and effective solution is to adjust the learning rate schedule accordingly and anneal it to O at the end of the training budget. This significantly outperforms off-the-shell schedules, particularly for small budgets. This plot shows several training schemes (solid curves) for ResNet- 18 on ImageNet. The vertical axis in the right plot is normalized by the validation accuracy achieved by the full budget training. The dotted green curve indicates an efficient way of trading off computation with performance.
Figure I:
Instead of asking "what is the best performance one can achieve given this data and algorithm?"' which has been the primary focus in the field far, we decorate this question with budgeted training constraints as follows: "what is the best performance one can achieve given this data and algorithm within the allowed budget?". Here, the allowed budget refers to limitation on the total time, compute, or cost spent on training. More specifically, we focus on limiting the number of iterations. This allows us to abstract out the specific constraint without loss of generality since any one of the aforementioned constraints could be converted to finite iteration limit. We make the underlying assumption that the network architecture is constant throughout training, though it may be interesting to entertain changes in architecture during training (Rusu et al. 2016 Wang et al. 2017).
Much of the thcoretical analysis of optimization algorithms focuses on asymptotic convergence and optimality (Robbins& & Monro 1951 Nemirovski et al. 2009 Bottou al., 2018), which implicitly makes use of an infinite compute budget. That said, there exists a wide body of work (Zinkevich) 2003 Kingma& & Ba 2015; Reddi et al.) 2018: [uo et al. 2019) that provide performance bounds which depend on the iteration number, which apply even in the non-asymptotic regime. Our work differs in its exploration of maximizing performance for a fixed number of iterations. Importantly, the globally optimal solution may not even be achievable in our budgeted setting.
Given limited budget, one obvious strategy might be data subsampling (Bachem al. 2017 Sener & Savarese, (2018). However, we discover that a much more effective, simpler, and under-explored strategy is adopting budget-aware learning rate schedules - if we know that we are limited to a single epoch, one should tune the learning schedule accordingly. Such budget- budret-aware schedules have been proposed in previous work (Feyzmahdavian et al., 2016, Lian et al., 2017). but often for a fixed learning rate that depends on dataset statistics. In this paper, we specifically point out linearly decaying the learning rate to 0 at the end of the budget, may be more robust than more complicated strategies suggested in prior work. Though are motivated by budget-aware training, we find that a linear schedule is quite competitive for general learning settings as well. We verify our findings with state-of of- models ImageNet (image classification), Kinetics (video classification), MS COCO (object detection and instance segmentation), and Cityscapes (semantic segmentation).
We conduct several diagnostic experiments that analyze learning rate decays under the budgeted setting. We first observe a statistical correlation between the learning rate and the full gradient magnitude (over the entire dataset). Decreasing the learning rate empirically results in decrease in the full gradient magnitude. Eventually, as the former goes to zero, the latter vanishes as well, suggesting that the optimization has reached a critical point, if not a local minimun We call this phenomenon budgeted convergence and we find it generalizes across budgets. On one hand, implies that one should decay the learning rate to zero at the end of the training, even given a small budget. On the other hand, it implies one should not aggressively decay the learning rate early in the optimization (such as the case with an exponential schedule) since this may slow down later progress. Finally, we show that linear budget-aware schedules outperform recently-proposed fast-converging methods that make use of adaptive learning rates and restarts.
Our main contributions are follows:
Whether such solution exactly a local minimum or is dehatable (sce See
2

---

Published as a conference paper at ICLR 2020
We introduce formal setting for budgeted training based training iterations and provide an alternative perspective for existing learning rate schedules.
We discover that budget-aware schedules are handy solutions to budgeted training. Specif- ically, our proposed linear schedule is more simple, robust, and effective than prior ap- proaches, for both budgeted and general training.
We provide an empirical justification of the effectiveness of learning rate decay based on the correlation between the learning rate and the full gradient norm.
2 RELATED WORK
Learning rates. Stochastic gradient descent dates back to Robbins & Monro 1951). The core its update step: Wy Wt-1 Otgtt. where (from 1 to T) is the iteration, w the parameters to be learned, is the gradient estimator for the objective function F" and a₁ is the learning rate, also known as step size. Given base learning rate og, we can define the ratio 3, = Oke 0z/ag. Then the set of {3:)2=1 is called the learning rate schedule, which specifies how the learning rate should vary over the course of training. Our definition differs slighter from prior art as separates the base learning rate and learning rate schedule. Learning rates are well studied for (strongly) convex cost surfaces and we include brief review Appendix H
Learning rate schedule for deep learning. In deep learning, there is no consensus on the exact role of the learning rate. Most theoretical analysis makes the assumption of small and constant learning rate (Du al.) [2018a b. Hardt et al. (016). For variable rates, one hypothesis is that large rates help move the optimization over large energy barriers while small rates help converge to a local minimum (Loshchilov & Hutter 2017: Huang et al.) 2017a; Kleinberg al. 2018). Such hypothesis is questiinne by recent analysis on mode connectivity, which has revealed that there does exist descent path between solutions that were previously thought to be isolated local minima Garrpov et al.] 2018: Dräxler et al. 2018 Gotmare et al., (219). Despite a lack of theoretical explanation, the community has adopted variety of heuristic schedules for practical purposes, two of which are particularly common:
step decay: drop the learning rate by a multiplicative factor 7 after every d epochs. The default for 7 is 0.1, but d varies significantly across tasks.
exponential: Bg = 7 There is no default parameter for y and it requires manual tuning.
State-of-the-art codebases for standard vision benchmarks tend to employ step decay (Xie & Tu
2015 Huang et al.
20176 He et al. 2017] Carreira & Zisserman, 2017 Wang et al. 2018 Yin
et al. 2019 Ma et al. a [2019] whereas exponential decay has been successfully used to train Inception networks (Szegedy et al.][ 2015 2016 2017). In spite of their prevalence, these heuristics have not been well studied. Recent work proposes several new schedules (Loshchilov & Hutter] 2017 Smith 2017 Hsueh al. 2019), but much of this past work limits their evaluation to CIFAR and ImageNet. For example, SGDR (Loshchilov & Hutter 2017) advocates for learning-rate restarts based on the results on CIFAR, however, we find the unexplained form of cosine decay in SGDR is more effective than the restart technique. Notably, Mishkin et al. (017) demonstrate the effectiveness of linear rate decay with CaffeNet on downsized ImageNet. In our work, we rigorously evaluate on 5 standard vision benchmarks with tfat-of--the-rr networks and under various budgets. [oommre et al. (2019) also analyze learning rate restarts and in addition, the warm-up technique, but do not analyze the specific form of learning rate decay.
Adaptive learning rates. Adaptive learning rate methods (Tieleman & Hinton 2012 Kingma & Ba 20155 Reddi et al. 2018 Luo et al. 2019) adjust the learning rate according to the local statistics of the cost surface. Despite having better theoretical bounds under certain conditions, they do not generalize as well as momentum SGD for benchmark tasks that are much larger than CIFAR (Wilson et al. 2017). We offer new insights by evaluating them under the budgeted setting. We show fast descent can trivially achieved through budget-aware schedules and aggressive early descent not desirable for achieving good performance in the end.
Note that can he based on single example, mini-batch, the full training set, or the true data distribution. In most practical settings, momentum SGD is used, but we omit the momentum here for simplicity.
3

---

Published as a conference paper at ICLR 2020
3 LEARNING RATES AND BUDGETS
3.1 BUDGET-AWARE SCHEDULES
Learning rate schedules are often defined assuming unlimited resources. As we argue, resource constraints are an undeniable practical aspect of learning. One simple approach for modifying an existing learning rate schedule to a budgeted setting early-stopping. Fig I shows that one can dramatically improve results of early stopping by more than 60% by tuning the learning rate for the appropriate budget. To do so, we simply reparameterize the learning rate sequence with a quantity not only dependent on the absolute iteration I, but also the training budget
Definition (Budget-Aware Schedule). Let T be the training budget, be the current step, then a training progress p is t/T. A budget-aware learning rate schedule is
Bp : f(p),
where (p) is the ratio of learning rate at step to the base learning rate og.
At first glance, it might be intuitree for schedule to nor depend on T. For example, for task that is usually trained with 200 epochs, training epochs will end up at solution very distant from the global optimal no matter the schedule. In such cases, conventional wisdom from convex optimization suggests that one should employ a large learning rate (constant schedule) that efficiently descends towards the global optimal. However, in the non-convex case, observe empirically that a better strategy is to systematically decay the learning rate in proportion to the total iteration budget.
Budge-Aware Conversion (BAC). Given particular rate schedule 3, ft)., one simple method for making it budget-aware is to rescale it, f.e., 3p = fpTTb), where To is the budget used for the original schedule. For instance, step decay for 90 epochs with two drops at epoch 30 and epoch 60 will convert to a schedule that drops at 1/3 and 2/3 training progress. Analogously, an exponential schedule 0.99* for 200 epochs will be converted into (0.99200)r.
It is worth noting that such an adaptation strategy already exists in well-known codebases (He et al, 2017) for training with limited schedules. Our experiments confirm the effectiveness of BAC general strategy for converting many standard schedules to be budget-aware (Tab I For our re- maining experiments, we regard BAC as known technique and apply it to our baselines by default.
Budget
1%
5%
10%
25%
50%
100%
exp .99
.5888
.0300
.3522
.8888
.9022
.9320
BAC
.6086
.8560
.996
.9288
.9722
N/A
step-d1 BAC
.5700
.0588
8422
.8702
.8746
.9334
.5880
.8662
.9066
.9312
.9392
N/A
Table 1: Effectiveness of budget-aware conversion (BAC) on CIFAR-10 for image classification with R8 (He al. 2016). The numbers are classification accuracy the validation set. The 100% budget refers to training for 200 epochs. "step-d1" " denotes step decay dropping once at training progress 50%. Please refer to Sec 4.1 for the complete setup.
Recent schedules:
Interestingly, several recent learning rate schedules are implicitly defined as function of progress p = 1 and so are budget-aware by our definition:
poly (Jia et al. 2014): Bp (1- " No parameter other than 0.9 is used in published work.
cosine (Loshchilov & Hutter 2017 3, = 17 + {(1 (1 + cos(TT)) 17 specify lower
bound for the learning rate, which defaults to zero.
htd (Hsuch et al. 2019) 3, 17 + [1
tanh(L + (U L)p)). Here has the same representation as in cosine. It is reported that L 6 and U = performs the best.
(1 (1
The poly schedule is feature in Caffe (Jia et al. 2014) and adopted by the semantic segmentation community (Chen et al. 2018 Zhao et al., (017)) The cosine schedule a byproduct in work that promotes learning rate restarts Loshchilov & Hutter, 2017). The htd schedule is recently proposed (Hsuch et al. 2019), which however, contains only limited empirical evaluation. None these ana- lyze their budget-aware property or provides intuition for such forms of decay. These schedules were
4

---

Published as a conference paper at ICLR 2020
100
iiner step
budget th
Budpet 10%
1/t
Dudpet
60
eap
40-
50%
pdy
Lomning
60
Froctin of
22
20 40
62
30
105
Trainin Progress (5)
Traiing Budget Ezech
Figure 2: We normalize various learning rate schedules by training progress (left). Our solution to budgeted training is simple and universal decrease the learning rate linearly across the entire given budget (right).
Budget
1%
5%
10%
25%
50%
100%
const
.5748 + .0377
.7989 +: .0003
.8350 +: .0122
.8658 +: .007
.8723
.0044
.8767
.0066
exp
.4834 +: 0125
.7575
+ .053
.8567 +:2 4027
.9147
+ 0030
.9295
0006
.9468 +: 0021
exp .97
.5467 + .0222
.8448 +: .0166
.8936 + .0030
.9294
0024
.9413
.0015
.9551
0004
exp .99
.6069 + .2119
1857
+ .037
.9013 + .0036
.9227
#: .0033
.9268
.0026
.9310
.0023
step-dl
.5853 + .1134
8643 + .027
.9063 + .0233
.9307
+ 0020
.9423 + .0027
.9426
.031
step-d2
.5487 + .0156
88442
+ .052
.943 + .033
.9319
0037
.9461
.0199
.9529
.009
step-d3
.4879 +: .0066
.7929 + 0061
.8644 + .0227
.9259
+ 0006
.9437
.0011
.9527
htd
.450 + .0070
8899 + .0013
.9219 + .0011
.9499 + .031
.9520
.0023
.9554
.0133
cosine
.6343 + ,0080
.8811 + .024
.9223 + .0024
.9432 + 0024
.9520 + 0026
.9552 + 0021
poly
6595 + .0886
8905 + .0177
.9247
+: .0008
9421
0019
.994
.0034
.9540 .012
lincar
.6617 + .0099
8915 + 0011
.9217 + .0028
.9412 + 0018
.9537
3000
.9563 .009
Table 2: Comparison of learning rate schedules on CIFAR-10. The stt, 2nd and the 3rd place under each budget are color coded. The number here is the classification accuracy and each one is the average of 3 independent runs. "step-dr" denotes decay times at even intervals with 7 = 0.1. For "exp" and "step" schedules, BAC (See 3.Ip is applied in place of early stopping. We can see linear schedule surpasses other schedules under almost all budgets.
treated as "yet another schedule". However, our definition of budget-aware makes these schedules stand out general family.
3.2 LINEAR SCHEDULE
Inspired by existing budget-aware schedules, we borrow even simpler schedule from the simu- lated annealing literature (Kirkpatrick et al.] 1983] McAllester al.) 1997 Nourani & Andresen 1998
linear 8, = p.
In Fig2, we compare linear schedule with various existing schedules under the budget-aware setting. Note that this linear schedule is completely parameter-free. This property is particularly desirable in budgeted training, where little budget exists for tuning such parameter. The excellent gener- alization of linear schedule across budgets (shown in the next section) might imply that the cost surface of deep learning is to some degree simflsimilar. Note that a linear schedule, together with
A link between SGD and simulated annealing has been recognized decades ago, where learning rate plays the role of temperature control (Bottou 1991). Therefore, cooling schedules in simulated annealing can be transferred into learning schedules for SGD.
5

---

Published as a conference paper at ICLR 2020
other recent budget-awas schedules, produces constant learning rate in the asymptotic limit i.e, - (1 101-t/ t/T) = 1. Consequently, such practically nigh-performing schedules tend to be ig- nored in theoretical convergence analysis (Robbins & Monro [951 Bottou al. 2018).
4 EXPERIMENTS
In this section, we first compare linear schedule against other existing schedules on the small CIFAR- 10 dataset and then on broad suite of vision benchmarks. The CIFAR-10 experiment is designed to extensively evaluate each learning schedule while the vision benchmarks are used to verify the observation on CIFAR-10. We provide important implementation settings in the main text while leaving the rest of the details to Appendix K In addition, we provide in Appendix [A the evaluation with a large number random architectures in the setting of neural architecture search.
4.1 CIFAR
CIFAR-10 (Krizhevsky & Hinton 2009) is dataset that contains 70,000 tiny images (32 x 32). Given its small size, is widely used for validating novel architectures. We follow the standard setup for dataset split (Huang et al. (017b), which is randomly holding out 5,000 from the 50,000 training images to form the validation set. For each budget, we report the best validation accuracy among epochs up till the end of the budget. We use ResNet-18 (He et al.! 2016) as the backbone architecture and utilize SGD with base learning rate 0.1, momentum 0.9, weight decay 0.0005 and a batch size 128.
We study learning schedules in several groups: (a) constant (cquivalent to not using any schedule). (b) & exponential and step decay, both of which are commonly adopted schedules. (d) htd (Hsueh et al. 2019). quite recent addition and not yet adopted in practice We take the parameters with the best-reported performance (-6,3). Note that this schedule decays much slower initially than the linear schedule (Fig 2 (e) the smooth-decaying schedules (small curvature), which consists of cosine (Loshchilov & Hutter 2017), poly (Jia et al. 2014) and the linear schedule.
As shown in Tab 2 the group of schedules that are budget-aware by our definition, outperform other schedules under all budgets. The linear schedule in particular, performs best most of the time including the typical full budget case. Noticeably, when exponential schedule is well-tuned for this task (7 = 0.97), it fails to generalize across budgets. In comparison, the budget-aware group does not require tuning but generalizes much better.
Within the budget-aware schedules, cosine, poly and linear achieve very similar results. This is expected due to the fact that their numerical similarity at each step (Fig 2 These results might indicate that the key for a robust budgeted-schedut is to decay smoothly to zero. Based on these observations and results, we suggest linear schedule should be the "go-to" budget-aware schedule.
4.2 VISION BENCHMARKS
In the previous section, we showed that linear schedule achieves excellent performance on CIFAR- 10, in a relatively toy setting. In this section, we study the comparison and its generalization to practical large scale datasets with various state-of-the-art architectures. In particular, we set up experiments to validate the performance of linear schedule across tasks and budgets.
Ideally, one would like to see the performance of all schedules in Fig Z on vision benchmarks. Due to resource constraints, we include only the off-the-shelf step decay and the linear schedule. Note our CIFAR-10 experiment suggests that using cosine and poly will achieve similar performance as linear, which are already budget-aware schedules given our definition, so we focus on linear schedule in this section. More evaluation between cosine, poly and linear can be found in Appendix A & D
We consider the following suite of benchmarks spanning many flagship vision challenges:
Image classification on ImageNet. ImageNet (Russakovsky et al. 2015) is a widely adopted stan- dard for image classification task. We use ResNet-18 (He et al. (016) and report the top-1 accuracy on the validation set with the best epoch. We follow the step decay schedule used in (Huang et al. 2017b, Py Torch 2019). which drops twice at uniform interval (y = 0.1 at p E { 2 D) We set the Tull budget 100 epochs (10 epochs longer than typical) for easier computation of the budget.

---

Published as a conference paper at ICLR 2020
Budget
1%
5%
10%
25%
50%
100%
Image classification ImageNet with ResNet
step
.2039 + 0029
55194 + .048
.5951
0021
.6555 + 0018
.67%6
omn8
.6934
0018
linear
.3633 + .006
.5726 + .0244
.6232
0004
.6634 .020
.6818-
0013
.6933
.0012
Object detection on COCO with Mask -CCNN
step
.0486 + .004
.2003 = .008
.2511
0005
.3149 + 0015
.3530
0005
.3767
00099
lincar
.0513 + 0012
.2090 + .016
2626 = 0008
.3222 = 0014
.3572
0003
.3795
.0122
Instance segmentation on COCO with Mask-RCNN
step
00487 + 0029
.1925 + 0004
.2388 = 0007
.2977 0003
.3202
0000
.3395
0009
linear
.0507 +: 0040
.1986 + .0122
.255
.007
.242 + 0002
.3242
.008
.3396
.0099
Semantic segmentation on Cityscppes with PSPNet
step
.4941 +: .0011
.6358 + .0522
.6800
0010
.7250 + .0199
.7423
.0044
.7651
+: .002
linear
.5424 +: .0044
.6654 + .0144
.7076
0047
.7399
.7575
.7633
Video classification on Kinetics with I3D
step
.2941 + .0288
.4981 + .0299
.5674
.0133
.6459
.0023
.6870
.7134
linear
.3286 + 1042
.5297 + 2014
.5967 0030
.6634 + 0020
.6995
0011
.7223 + 0031
Table 3: Robustness of linear schedule across budgets, tasks and architectures. Linear schedule significantly outperforms step decay given limited budgets. Note that the off-the-shed decay for each dataset has different parameters optimized for the specific dataset. For all step decay schedules, BAC (Sec is applied to boost their budgeted performance. To reduce stochastic noise, we report the average and the standard deviation of 3 independent runs. See See 4.2 for the metrics of each task (the higher the better for all tasks).
Object detection and instance segmentation on MS COCO. MS COCO (Lin et al. 2014 is widely recognized benchmark for object detection and instance segmentation. We use the standard COCO AP (averaged over loU thresholds) metric for evaluating bounding box output and instance mask output. The AP of the final model on the validation set is reported in our experiment. We use the challenge winner Mask R-CNN (He et al., 2017) with ResNet-50 backbone and follow its setup. For training, we adopt the Ix schedule (90k iterations), and the off-the-shelf (He et al. 2017) step decay that drops 2 times with 7 = 0.1 at p E ()
Semantic segmentation on Cityscapes. Cityscapes (Cordts et al. 2016) is a dataset commonly used for evaluating semantic segmentation algorithms. It contains high quality pixel-level annotations of 5k images in urban scenarios. The default evaluation metric is the mIoU (averaged across class) of the output segmentation map. We state-of-the-an model PSPNet (Zhao et al.) 2017) with ResNet-50 backbone and the full budget is 400 epochs as in standard set up. The mloU of the best epoch is reported. Interestingly, unlike other tasks in this series, this model by default uses the poly schedule, For complete evaluation, we add step decay that is the same in our ImageNet experiment in Tab 3 and include the off-the-shelf poly schedule in Tab E
Video classification on Kinetics with I3D. Kinetics (Kyy et al. 2017) is a large-scale dataset of YouTube videos focusing on human actions. We use the 400-category version of the dataset and a variant of I3D (Carreira & Zisserman 2017) with training and data processing code publicly available (Wang et al., 2018). The top-1 accuracy of the final model used for evaluating the performance. We follow the 4-GPU 300k iteration schedule (Wang et al. 2018), which features a step decay that drops 2 times with 7 = 0.1 at p E { 8)
If we factor in the dimension of budgets. Tab 3 shows a clear advantage of linear schedule over step decay. For example, on ImageNet, línear achieves 51.5% improvement at 1% of the budget. Next, consider the full budget setting, where simply swap out the off-the-shelf schedule with linear schedule. We observe better (vidco classification) or comparable (other tasks) performance after the swap. This is surprising given the fact that linear schedule is parameter-fre free and thus not optimized for the particular task or network.
In summary, the smoothly decaying linear schedule is simple and effective strategy for budgeted training. It significantly outperforms traditional step decay given limited budgets, while achieving comparable performance with the normal full budget setting.
7

---

Published as a conference paper at ICLR 2020
(a) Constart
(b) Step Decay
[<] Exponential
(d) Poly
10-
0.15
Norm
0.15
0.15
0.15
3.10
Leaniigg
Grodeett
0.10
0.10
0.05
0.05
0.00
0.00
50
100
150
200
50
100
1.50
200
50
100
150
200
50
100 Epech
1.50
200
Epech
Epech
Epoch
(e)
10%
(f) Linear
(o)
(h) (Across Budggets)
0.15
0.15
0:15
Guadien
0.10
Loarning hall
Gradinn
0.10
0.10
Gradent
0.10
0.05
3.05
0.05
0.05
0.00
0.00
0.00
0.00
50
150
50
100
150
200
25
50
75
100
Epoch
Epoch
Epoch
Training Progress
Figure 3: Budgeted convergence: full gradient norm |[g vanishes over time (color curves) as learning rate at (black curves) decays. The first shows that the dynamics of full gradient norm correlate with the corresponding learning rate schedule while the second row shows that such phe- nomena generalize across budgets for aware schedules. Such generalization is most obvious in plot (h), which overlays the full gradient norm across different budgets. If a schedule does not decay to 0, the gradient norm does not vanish. For example, if train budget-unaware exponen- tial schedule for 50 epochs (c), the full gradient norm at that time is around 1.5, suggesting this is schedule with insufficient final decay learning rate.
DISCUSSION
In this section, we summarize our empirical analysis with a desiderata of properties for effective budget-aware learning schedules. We highlight those are inconsistent with conventional wisdom and follow the experimental setup in Sec 4.1 Jnless otherwise stated.
Desideratum: budgeted convergence. Convergence of SGD under non-convex objectives is mea- sured by ii [B[||| F = 0 (Bottou et al., 2018). Intuitively, one should terminate the op- timization when no further local improvement can be made. What the natural counterpart for "convergence" within budget? For a dataset of N examples {(z,, M let us write the full gradient Of N Σ V.( We empirically find that the dynamics of |lo"' || over time highly correlates with the learning rate ae (Fig (3). As the learning rate vanishes for budget-aware schedules, so does the gradient magnitude. We call this "vanishing gradient" phenomenon budgeted convergence. This correlation suggests that decaying schedules to near-zero rates (and using BAC) may be more effective than early stopping. As side note, budgeted convergence resonates with classic literature that argues that SGD behaves similar to simulated annealing (Bottou 1991). Given that a and ||9;| || decrease, the overall update - also decrease In other words, large moves are more likely given large learning rates in the beginning, while small moves are more likely given small learning rates the end. However, the exact mechanism by which the learning rate influences the gradient magnitude remains unclear.
Desideratum: don't waste the budget. Common machine learning practise often produces multi- ple checkpointed models during training run, where validation set is used to select the best one. Such additional optimization is wasteful in our budgeted setting. Tab 4 summarizes the progress point at which the best model tends to be found. Step decay produces
optimal model somewhat towards the end of the training, while linear and poly are almost always optimal at the precise end of the training. This is especially helpful for state-of-the-art models where evaluation can be expen- sive. For example, validation for Kinetics video classification takes several hours. Budget-aware schedules require validation on only the last few epochs, saving additional compute.
'Note that the momentum in SGD is used, but we assume vanilla SGD to simplify the discussion, without losing generality.
8

---

Published as a conference paper at ICLR 2020
Schedule
Best Progress
Schedule
Best Progress
const
81.2% 4: 16.1%
step-d2
90.5% 1: 9.0%
linear
98.6% 1.6%
poly
99.1% % 1.3%
Table 4: Where does one expect to find the model with the highest validation accuracy within the training progress? Here show the best checkpoint location measured in training progress p and averaged for each schedule across budgets greater or equal than 10% and 3 different runs.
Aggressive early descent. Guided by asymptotic convergence analysis, faster descent the objec- tive might be apparent desideratum of an optimizer. Many prior optimization methods explicitly call for faster decrease of the objective (Kingma & Ba 2015 Clevert et al.] 2016 Reddi et al., 2018). In contrast, we find that one should not employ aggressive early descent because large learn- ing rates can prevent budgeted convergence. Consider AMSGrad (Reddi et al. 2018). an adaptive learning rate that addresses convergence issue with the widely-used Adam optimizer (Kingma & Ba 2015). Fig 4 shows that while AMSGrad does quickly descend over the training objective, it still underperforms budget-aware linear schedules over any given training budget. To examine why, we derive the equivalent rate 3g for AMSGrad (Appendix B and show that it is dramatically larger than our defaults, suggesting the optimizer is too aggressive. We include more adaptive methods for evaluation in Appendix
explores periodic schedules, in which each period is a cosine scaling. The schedule is intended to escape local minima, but its effectiveness has been questioned (Gotmare et al., 2019). Fig 5 shows that SDGR has faster descent but is inferior to budget-awer -ware schedules for any budget (similar to the adaptive optimizers above). Additional comparisons can be found in Appendix FF) Whether there exists method that achieves promising anytime performance and budgeted performance at the same time remains an open question.
Warm restarts. SGDR (Loshchilov & Hutter 2017)
Training
Grad Noem & Equivalent
Training Loss
(b)
1.0
3.0
-250
0.0
Liner 182%
Liear 10%
-225
5:5
Lnnwar 15's
Linear 72%
Lnear 39%
10-
Live 15's
0.6
6.6
0.4
6-
5/4
0.2
0.2
0.0
1.2
130
200
150
50
1.50
20.0
250
Epech
baathh
Figure 4: Comparing AMSGrad (Reddi et al. 2018 with linear schedule. (a) while AMSGrad makes fast initial descent of training loss, is surpassed each given budget by the linear schedule. (b) bud- geted convergence is not observed for AMSGrad - the full gradient norm ||gil| does not vanish (color curves). Comparing to momentum SGD, AMS- Grad recommends magnitudes larger learning rate Be (black curve).
Figure 5:
Comparing SGDR (Loshhhlovv & Hut-
ter 2017) with linear schedules. (a) SGDR makes slightly faster initial descent of training loss, but is surpassed at each given budget by the lincar sched- ule. (b) for SGDR, the correlation between full gradi- ent norm |g || and learning rate o, is also observed. Warm restart does not help to achieve better budgeted performance.
CONCLUSION
This paper introduces formal setting for budgeted training. Under this setup, we observe that sim- ple linear schedule, or any other smooth-decaying schedules can achieve much better performance. Moreover, the linear schedule tasks for the typical full budget case. addition, we analyze the intriguing properties learning rate schedules under budgeted training. We find that the learning rate schedule controls the gradi- ent magnitude regardless of training stage. This further suggests that SGD behaves like simulated annealing and the purpose of a learning rate schedule is to control the stage of optimization.
offers comparable performance on existing visual recognition
Acknowledgements: We thank Xiaofang Wang, Simon S. Du, Leonid Keselman, Chen-Hase Hhen-Hsuann Lin and David McAllester for insightful discussions and comments.

---

Published as a conference paper at ICLR 2020
REFERENCES
Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning, arXiv preprint
2017.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firerr, Beat Flepp, Pra- soon Goyal, Lawrence D. Jackel, Miguel Pozuelo Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Junbo Jake Zhao, and Karol Zieba. End end learning for self-driving cars. CoRR, abs/1604.0731e 2016.
Léon Bottou. Stochastic gradient learning in neural networks. In Proceedings of Newro-Nimes 91, Nimes, France, 1991. EC2. URL
Léon Bottou. Online algorithms and stochastic approximations. In David Saad (ed.), Online Learning and Neural Networks, Cambridge University Press, Cambridge, UK, 1998. URL
http::/ www.n.oottou..mm orq wttp:o/gg//ggpooteeeeoeeee 98x, revised, oct 2012.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60:223-31 1-1--11,,,, 2018.
Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang. Efficient architecture search by network transformation. In AAAI, 2018.
Shengcao Cao, Xiaofang Wang, and Kris M Kitani. Learnable embedding space for efficient neural architecture compression. ICLR, 2019.
João Carreira and Andrew Zisserman. Quo vadis, action recognition? new model and the kinetics dataset. CVPR, pp. 4724 4733, 2017.
Liang-Chiee Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L. Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and 2018.
fully connected crfs. TPAMI,
Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (clus). ICLR, 2016.
Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. In CVPR, 2016.
Felix Dräxler, Kambis Veschgini, Manfred Salmhofer, and Fred A. Hamprecht. Essentially no bar- riers in neural network energy landscape. In ICML, 2018.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint 1r1i 03804, 2018a.
Simon S. Du, Jason D. Lee, Yuandong Tian, Barnabás Péczos, and Aarti Singh. Gradient descent learns one-hidden-layer enn: Don't 't't be afraid of spurious local minima. In ICML, 2018b.
Meherwar Fatima and Maruf Pasha. Survey of machine learning algorithms for disease diagnostic.
Journal of Intelligent Learning Systems and Applications. 9001):1, 2017.
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61 (12):3740-3754, 2016.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P. Vetrov, and Andrew Gordon Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In NewrIPS, 2018.
Akhilesh Gotmare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. A closer look at deep learning heuristics: Learning rate restarts, warmup and distillation. ICLR, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arxiv: 2017.
10

---

Published as a conference paper at ICLR 2020
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. ICML, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, pp. 770-778, 2016.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick. Mask r-cnn. ICCV, pp- 2980- 2988, 2017.
Bo Yang Hsueh, Wei Li, and I-Chen Wu. Stochastic gradient descent with hyperholic-tangent decay classification. WACV, 2019.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E. Hopcroft, and Kilian Q. Weinberger. Snapshot ensembles: Train 1, get m for free. ICLR, 2017a.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. CVPR, pp. 2261-2269, 2017b.
Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan Long, Ross Girshick, Ser- gio Guadarrama, and Trevor Darrell. Caffe: Convolutional architecture for fast feature embed- ding. ACM Multimedia, pp. 675-678, 2014.
Will Kay, João Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijaya- narasimhan, Fabio Viola, Tim Green, Trevor Back, Apostol Natsev, Mustafa Suleyman, and An- drew Zisserman. The kinetics human action video dataset. CoRR, abs/1705.06995 06950, 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.
Scott Kirkpatrick, Daniel Gelatt, and Mario Vecchi. science, 220(4598);671-680, 1983.
Optimization by simulated annealing.
Robert D. Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? JCML, 2018.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. NIPS, 00:84-90, 2012.
Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Sha- hab Kamali, Stefan Popov, Matteo Malloci, Tom Duerig, and Vittorio Ferrari. The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale. 18Xiv:181I.00 1.00922, 2018.
Lisha Li. Kevin G. Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet S. Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. JMLR, 18:185:1- 185:52, 2017.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In NIPS, pp. 5330-5340, 2017.
Tsung-Y Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft COCO: Common objects in context. In ECCV, pp- 740-755, 2014.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. ICLR, 2019.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In ICLR, 2017.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. ICLR, 2019.

---

Published as a conference paper at ICLR 2020
W. Ma, S. Wang, R. Hu, Y. Xiong, and R. Urtasun. Deep rigid instance scene flow. In CVPR, pp- 1-9,201 2019.
David McAllester, Bart Selman, and Henry Kautz. Evidence for invariants in local search. AAAI, pp. 321-326, 1997.
Dmytro Mishkin, Nikolay Sergievskiy, and Jiri Matas. Systematic evaluation of convolution neural network advances on the imagenet. Computer Vision and Image Understanding, 161:11-19 2017.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal on Optimization, 15:1 1609, 2009.
Yaghout Nourani and Bjarne Andresen. A comparison of simulated annealing cooling strategies. Journal of Physics A: Mathematical and General, 3 31(41):8373, 1998.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. ICML, 2018
PyTorch. ImageNet training in PyTorrc v1.0.1, 2019. Retrieved from http:: https::/gtthtbb. com/ eyyorchhexamgy les /tte///teee//tttte///a/eaeeeeee on Mar 4, 2019.
Piyush Rai, Hal Daumé, and Suresh Venkatasuubramanian. Streamed learning: one-pass svms. In IJCAI, 2009.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. AAAI, 2019.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In ICLR, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. IJCV, 115(3):11--25,, 2015.
Andrei Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv: 10tv:/666..e 04671, 2016.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. ICLR, 2018.
Leslie N. Smith. Cyclical learning rates for training neural networks. WACV, pp. 464-472, 2017.
Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In CVPR, pp. 1-9, 2015.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shiens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In CVPR, pp. 2818-2826, 2016.
Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception-resned and the impact of residual connections on learning. AAAI, 2017.
Russell H Taylor, Arianna Menciassi, Gabor Fichtinger, and Paolo Dario. Medical robotics and computer-integrater surgery. Springer handbook of robotics, pp. 1199-1222, 2008.
T. Tieleman and G. Hinton. RMSProp: Divide the gradient by running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. CVPR, 2018.
12

---

Published as a conference paper at ICLR 2020
Yu- Yu-Xiong Wang. Deva Ramanan, and Martial Hebert. Growing brain: Fine-tuning increasing model capacity. In CVPR, pp. 2471-2480, 2017.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In NIPS, pp. 4148-4158. 2017.
Saining Xie and Zhuowen Tu. Holistically-nested edge detection. In ICCV, 2015.
Zhichao Yin, Trevor Darrell, and Fisher Yu. Hierarchical discrete distribution decomposition for match density estimation. CVPR, 2019.
Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia. Pyramid scene parsing network. CVPR, pp. 6230-6239, 2017.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pp. 928 936, 2003.
Barret Zoph and Quoe Le. Neural architecture search with reinforcement learning. ICLR, 2017.
13

---

Published as a conference paper at ICLR 2020
A BUDGETED TRAINING FOR NEURAL ARCHITECTURE SEARCH
A.1 RANK PREDICTION
In the main text, we list neural architecture search as an application of budgeted training. Due to resource constraint, these methods usually train models with small budget (10-25 epochs) to evaluate their relative performance (Cao et al, 2019 Cai al. 2018; Real et al., 2019). Under this setting, the goal is to rank the performance of different architctuures instead of obtaining the best possible accuracy as in the regular case of budgeted training. Then one could ask the question that whether budgeted training techniques help in better predicting the relative rank. Unfortunately, budgeted training has not been studied or discussed in the neural architecture search literature, is unknown how well models only trained with 10 epochs can tell the relative performance of the same ones that are trained with 200 epochs. Here we conduct a controlled experiment and show that proper adjustment of learning schedule, specifically the linear schedule, indeed improves the accuracy of rank prediction.
We adapt the code in (Cao al. 2019) generate 100 random architectures, which obtained by random modifications (adding skip connection, removing layer, changing filter numbers) on top of ResNet-18 (He et al. 2017). First, we train these architectures on CIFAR-10 given full budget (200 epochs), following the setting described in Sec 4.1 This produces relative rank between all pairs of random architectures based on the validation accuracy and this rank is considered as the target to predict given limited budget. Next, every random architecture is trained with various learning schedules under various small budgets. For each schedule and each budget, this generates a complete rank. We treat this rank as the prediction and compare it with the target full-budget rank. The metric we adopt is Kendall's rank correlation coefficient (T), a standard statistics metric for measuring rank similarity. It is based on counting the inversion pairs in the two ranks and (r 1)/2 is approximately the probability of estimating the rank correctly for a pair.
We consider the following schedules: (1) constant, it might be possible that no learning rate schedule
is reguired if only the relative performance is considered. (2) step decay ( = 0.1, decay at p e
( { 1)a schedule commonly used both in regular training and neural architecture search (Zoph &
Le. 2017: Pham et al. 2018). (3) cosine, a schedule often used in neural architecture search (Cai
al. [2018] Real al. 2019). (4) linear, our proposed schedule. The results of their rank prediction
capability can be seen in Tab A
The results suggest that with more budget, we can better estimate the full-budget rank between architectures. And even if only relative performance is considered, learning rate decay should be applied. Specifically, smooth-decaying schedule, such as linear or cosine, are preferred over step decay.
We list some additional details about the experiment. To reduce stochastic noise, each configuration under both the small and full budget is repeated 3 times and the median accuracy is taken. The full- budget model is trained with linear schedule, similar results are expected with other schedules as evidenced by the CIFAR-10 results in the main text (Tab 2). Among the 100 random architectures, 21 cannot be trained, the rest of 79 models have validation accuracy spanning from 0.37 to 0.94, with the distribution mass centered at 0.91. Such skewed and widespread distribution is the typical case in neural architecture search. We remove the 21 models that cannot be trained for our experiments. We take the epoch with the best validation accuracy for each configuration, so the drawback of constant or step decay not having the best model at the very end does not affect this experiment (see Sec
Epoch (Budget)
(0.5%)
2 (1%)
10 (5%)
20 (10%)
const
0.3451
0.4595
0.6720
0.6926
step-d2
0.2746
0.3847
0.6651
0.7279
cosine
0.3211
0.4847
0.7023
0.7563
linear
0.3409
0.4348
0.7398
0.7351
Table A: Small-budget and full-budget model rank correlation measured in Kendall's tau. Smooth- decaying schedules like lincar and cosine can more accurately predict the true rank of different architectures given limited budget.
14

---

Published as a conference paper at ICLR 2020
Epoch (Budget)
(0.5%)
(1%)
10 (5%)
20 (10%)
0.3892
0.4699
0.6689
0.7061
step-d2
0.4014
0.4780
0.6980
0.7754
cosine
0.4616
0.5498
0.7530
0.8029
linear
0.4759
0,5745
0.7652
0.8192
Table B: Small-budget validation accuracy averaged across random architectures. Linear schedule is the most robust under small budgets.
Epnnc (Budget)
(0.5%)
2 (1%)
10 (5%)
20 (10%)
const
0.4419
0,5343
0.7550
0.8015
step-d2
0.4590
0.5455
0.7894
0.8848
cosine
0.5326
0.6265
0.8615
0.9087
linear
0.5431
0.6626
0.8644
0.9305
Table C: Tab B normalized by the full-budget accuracy and then averaged across architectures. Linear schedule achieves solutions closer their full-budget performance than the of schedules under small budgets.
A.2 BUDGETED PERFORMANCE ACROSS ARCHITECTURES
To reinforce claim that linear schedule generalizes across different settings, compare bud- geted performance of various schedules on random architectures generated the previous section. We present two versions of the results. The first is to directly average the validation accuracy of different architecture with each schedule and under each budget (Tab B). The second to normalize by dividing the budgeted accuracy by the full-budget accuracy of the same architecture and then average across different architectures (Tab C.. The second version assumes all architectures enjoy equal weighting. Under both cases, linear schedule is the most robust schedule across architectures under various budgets.
B EQUIVALENT LEARNING RATE FOR AMSGRAD
In Sec we use equivalent learning rate to compare AMSGrad (Reddi et al. 2018) with momentum SGD. Here we present the derivation for the equivalent learning rate 3r.
Let 1/, 722 and be hyper-parameters, then the momentum SGD update rule is:
m: = Ti 7- + (1 - m))..
(3)
W; = Wi - (10 3.me:
(4)
while the AMSGrad update rule is:
my 1-m4-111 + (1 711 (1))
0t 1/24/11 (1 172 72)9r
(6)
m m4
r/i
0: Ut
1/2
mmax
max
02)
(9)
= Wi-1
an
(2)
m
(10)
V
7max +
Comparing equation 4 with 10
we obtain the equivalent learning rate:
(2)
a
B,
(11)
(1) (1 - (1-1/) amaa + +c)
a
15

---

Published as a conference paper at ICLR 2020
Budget
1%
5%
10%
25%
50%
100%
Subset
.3834
6446
.7848
.8586
.9244
N/A
Full
.5544
.8328
.9042
.338
.9464
.9534
Table D: Comparison with offline data subsampling. "Subset" meets the budget constraint by ran- domly subsample the dataset prior to training. while "full" uses all the data, but restricting the number of iterations. Note that budget-aware schedule is used for "full""
Note that the above equation holds per each weight. For Fig 4a dimensions as a scalar summary since is skewed distribution. The mean appears to be even larger the default hyper-parameten,
take the median across all
and shares the same trend the median. In experiments, (1) = 0.1, ag = 0.001, ? = 0.9,
(which also turn out to have the best validation accuracy): ag ?/2 0.99 and 10-8.
C DATA SUBSAMPLING
Data subsampling is straight-forwan strategy for budgeted training and can be realized in several different ways. In our work, we limit the number of iterations meet the budget constraint and this effectively limits the number of data points seen during the training process. An alternative is to construct subsampled dataset offline, but keep the same number of training iterations. Such construction be done by random sampling, which might be the most effective strategy for i.id (independent and identically distributed) dataset. We show in Tab D that even our baseline budge- aware step decay, together with limitation the iterations, can significantly outperform this offline strategy. For the subset setting, we use the off-the-shelf step decay (step-d2) while for the full set the same step decay but with BAC applied (Sec 3.1 For detailed setup, follow Sec 4.1 of the main text.
setting,
Of course, more complicated subset construction methods exist, such as core-sel construction (Bachem et al.) (0077). However, such methods usually requires a feature summary of each data point and the computation of pairwise distance, making such methods unsuitable for extremely large dataset. In addition, note that our subsampling experiment is conducted on CIFAR-I0, well-constructed and balanced dataset, making smarter subsampling methods less advantageous. Consequently, the result in Tab can as well provides reasonable estimate for other complicated subsampling methods.
D ADDITIONAL EXPERIMENTS ON CITYSCAPES (SEMANTIC SEGMENTATION)
In the main text, we compare linear schedule against step decay for various tasks. However, the off the-hh schedule for PSPNet (Zhao al. [2017) is poly instead of step decay. Therefore, we include the evaluation of poly schedule on Cityscapes (Cordts et al. 2016) in Tab D Given the similarity of poly and linear (Fig 2 and the opposite results on CIFAR- 10 and Cityscapes, it
inconclusive that one is strictly better than the other within the smooth-decayin family. However,
these smooth- -eecainn methods both outperform step decay given limited budgets.
Budget
5%
10%
25%
50%
100%
poly
.5476
.0023
.6755 + .002
.7093 + 0oss
.7416
0002
.7562
.0445
.7593
+ .0043
linear
5424
.0034
.6654 + .014
.7076 + 0047
.7399
0005
.7575
.0041
.7633 .0000
Table E: Comparison with off off-the-sheef poly schedule Cityscapes Cordts et al. Net Zhao et al. (2017). Poly and linear are similar smooth-decaying schedules (Fig similar performance. The exact rank differs from task task.
2016 using PSP-
2 and thus have
16

---

Published as a conference paper at ICLR 2020
E ADDITIONAL COMPARISON WITH ADAPTIVE LEARNING RATES
(a) Training Loss
(b) Validation Accuracy
1.0
1.0
Method
Accu
Linear 25%
Linear 50%
RMSprop
.9388
Uneea
AdaBound
.9306
AMEGrad Uneer
Unear 10%
AMSGrad
.9113
AMSGrad
Uneer
Acailound
AMSGrad + Lineur
.9400
0.4
RMtiprop
Linwer
0.6
AMS Grad Linear
SGD Linear 10%
.9188
0.2
0.5
AMS Grad
AcaBound
SGD Linear 25%
.9412
pMS
SGD Linear 50%
.9546
SGD Linear 100%
.9562
100
150
150
200
Figure A: Comparison between budget-aware linear schedule and adaptive learning rate methods on CIFAR-10. see while adaptive learning rate methods appear to descent faster than full budget linear schedule, at each given budget, they are surpassed by the corresponding linear schedule.
In the main text we compare linear schedule with AMSGrad (Reddi et al. 2018) (the improved ver- sion over Adam (Kingma 2015), further include the classical method RMSprop (Tieleman & Hinton 2012) and the more recent AdaBound (Luo et al. 2019). We tune these adaptive methods for CIFAR 10 and summarize the results in Fig A We observe the similar conclusion that budget- aware linear schedule outperforms adaptive methods for all given budgets.
Like SGD, those adaptive learning rate methods also takes input parameter base learning rate, which can also be annealed using existing schedule. Although it is unclear why one needs to anneal an adaptive methods, we find that in facts boosts the performance ("AMSGrad Linear" in Fig
ADDITIONAL COMPARISON WITH SGDR
This section provides additional evaluation to show that learning rate restart produces worse results than proposed budgeted training techniques under budgeted setting. In (Loshchilov & Hutter 2017]. both a new form of decay (cosine) and the technique of learning rate restart are proposed. To avoid confusion,
"cosine schedule". just "cosine", refer to the form of decay and SGDR to a schedule of periodical cosine decays. The comparison with cosine schedule is already included in the main text. Here we focus on evaluating the periodical schedule. SGDR requires two parameters to specify the periods: To, the length of the first period; Tmmtts where i-th period has To-r length T; To mult In Fig we plot the off-the-shelf SGDR schedule with To = 10 (epoch), Tmuit 2. The validation accuracy plot (on the right) shows that might end very poor solution (0.8460) since it is not budget-aware Therefore, we consider two settings to compare
(a) Learning Rate Schedule
(b) Validation Accuracy
Fraction Base Learring Rate
SGOR (ofT-the-hheff)
SGDR-12
150
200
150
Epoch
Epoch
Figure B: One issue with off-the-shelf SGDR (To 10, Tmult 2) is that it is not budget-aware and might end at a poor solution. We convert it to a budget aware schedule by setting it to restart a times intervals across the budget and 2 is shown here (SGDR-12).
17

---

Published as a conference paper at ICLR 2020
Epoch
30
50
150
SGDR
.9320
.9458
.9510
linear
.9500
.9506
.9522
Table F: Comparison with off off-the-shelf SGDR at the end of each period after the first restart.
Budget
1%
5%
10%
25%
50%
100%
SGDR-rl
.5002
.7908
.8794
.9250
.9380
.9488
SGDR-r2
.4710
.7888
8738
.9116
.9412
.9502
lincar
.6654
.8920
.2188
.9412
.9566
.9622
Table G: Comparison with SGDR under budget-aware setting. "SGDR-r1" refers to restarting learn- ing rate once at midpoint of the training progress, and "SGDR-r2" refers to restarting twice at even interval.
linear schedule with SGDR. The first is compare only at the end of each period of SGDR, where budgeted convergence is observed. The second is to convert SGDR into a budget-aware schedule by setting the schedule to restart times even intervals across the budget. The results under the first and second setting is shown in Tab F and Tab G respectively. Under both budget-aware and budget-unaware setting. linear schedule outperforms SGDR. For detailed setup, we follow See of the main text and take the median of runs.
G ADDITIONAL ILLUSTRATIONS
In Sec we refer to validation accuracy curve for training on CIFAR-10, which we provide here in Fig
H LEARNING RATES IN CONVEX OPTIMIZATION
For convex cost surfaces, constant learning rates are guaranteed to converge when less or equal than 1/L, where L is the Lipschitz constant for the gradient of the cost function VF (Bottou al. 2018). Another well-known result ensures convergence for sequences that decay neither too fast nor slow (Robbins & Monro 1951 Σ 04 xc, Et= ag co. One common such instance in convex optimization is Og On/L. /T. For non-convex problems, similar results hold for convergence local minimum (Bottou et al. 2018). Unfortunately, there does not exist theory for learning rate schedules in the context of general non-convex optimization.
(a) Training Loss
(b) Validation Accuracy
step-d2
linear
step-dZ2
linear
Epach
Epoch
Figure C: Training loss and validation accuracy for training ResNet-18 CIFAR-10 using step decay and linear schedule. No generalization gap is observed when we only modify learning rate schedule. This figure provides details for the discussion of "don't waste budget".
18

---

Published as a conference paper at ICLR 2020
(a] Constart
(b) Step Decay
Expanential
(d) SGDR
0.11
Weights hoo
.00-
600
(leght
500
Learning
3.05
Weight
0.05
0.05
400
50
100
150
200
50
100
150
200
50
100 Epoch
150
200
100 Epech
1.50
200
Epoch
Epoch
(o)
(h)
Budggets)
35
55
50
0.10
0.10
0.10
0.10
Weight Nerm
Leariing hatu
Weight Nerm
25
0.00
25
3.00
0.00
25
0.00
50
100 Epoch
50
Epech
Epoch
Training Progress
Figure D: The corresponding weight norm plots for Fig exhibits similar trend as the gradient norm.
and Fig 5. We find that the weight norm
I FULL GRADIENT NORM AND THE WEIGHT NORM
In Sec we plot the full gradient norm of the cross-cntron cross-entropy loss, excluding the regularization part. In fact, we use L2-regularization (weight decay) of 0,0004 for these experiments. For completeness, we plot the weight norm in Fig D
J ADDITIONAL ABLATION STUDIES
Here we explore variations of batch size (Tabl HD and initial learning rate (Tab [.. Our definition of budget is the number of examples seen during training. So when the batch size increases, the number of iterations decreases. For example, on CIFAR-10, 10, the full budget is training with batch size 128 for 200 epochs. If we train with batch size 1024 for 20% of the budget, that means training for epochs.
Batch Size
Schedule
20%
50%
100%
64
step-d2
.436
.9505
.9519
64
lincar
.9473 = .020111
.9511
= .0008
.9526 :
256
step-d2
.8939
.9291
+ .9431
256
linear
.9143 + .0.08
.9415
= .0038
.9484
+ 0013
1024
step-d2
.5851
..400
.7703
.8805
1024
linear
.7415 = .0141
.8553 = .0023
.8992
:: 0042
Table H: Comparison between linear and step decay with different batch sizes. We can see that even when we vary the batch size, linear schedule outperforms step decay.
Initial LR
0.001
0.1
10
step-d2
91552
.9529
8869
N/A
linear
.9677
.0023
.9563 # .0099
.8967
.0034
N/A
Table I: Comparison between linear and step decay with different initial learning rate under full budget setting. On one hand, we that linear schedule outperforms step decay under various initial learning rate. On the other hand, we see that initial learning rate is still very important hyper-parameter that needs be tuned even with budget-aware, -neoyi-de schedules.
19

---

Published as a conference paper at ICLR 2020
K ADDITIONAL IMPLEMENTATION DETAILS
Image classification on ImageNet. We adapt both the network architecture (ResNet-18) and the data loader from the open source PyTorch ImageNet example] The base learning rate used is 0.1 and weight decay 5 x 10-4. We train using 4 GPUs with asynchronous batch normalization and batch size 128.
Video classification on Kineties with I3D. The 400-category version of the dataset is used in the evaluation. We use an open source codebase code publicly available. Note that the codebase implements a variant of standard I3D) (Car- reira & Zisserman, 2017) that has ResNet as the backbone. We follow the configuration of run_i3d_basel _aoee_30k__4_0
@ that has training and data processing
sh, which specifies a base learning rate 0.005 and a weight decay 10-4, Only learning rate schedule modified in our experiments. We train using 4 GPUs with asynchronous batch normalization and batch size 32.
Object detection and instance segmentation on MS COCO. We use the open source implemen- tation of Mask R-CNN" which is PyTorch re-implementation of the official codebase Detectron in the Caffe 2 framework. We only modify the part the code for learning rate schedule. The code- base sets base learning rate to 0.02 and weight decay 10-4 We train with 8 GPUs (batch size 16) and keep the built-in learning rate warm up mechanism, which is an implementation technique that increases learning rate for 0.5k iterations and is intended for stabilizing the initial phase of multi- GPU training (Goyal et al. 2017). The 0.5k iterations are kept fixed for all budgets and learning rate decay is applied to the rest of the training progress.
Semantic segmentation on Cityscapes. We adapt a PyTorch codebase obtained from correspon- dence with the authors of PSPNet. The base learning rate is set 0.01 with weight decay 10-4, The training time augmentation includes random resize, crop, rotation, horizontal flip and Gaussian blur. We use patch-based testing time augmentation, which cuts the input image to patches of 713 713 and processes each patch independently and then tiles the patches to form single output. For over- lapped regions, the average logits of two patches are taken. We train using 4 GPUs with synchronous batch normalization and batch size 12.
PyTorch version
0.4.1
Caffe 2 version 0.8.1. 1. http:///ftaccaaarreeessrr//rrerr version 0.4.1.
20


Reviews:
[{"review_id": "SyeXsBqpKS", "reviewer": "AnonReviewer1", "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": "This paper analyzed which learning rate schedule (LRS) should be used when the budget (number of iteration) is limited. First, the authors have introduced the concept of BAS (Budget-Aware Schedule). Various LRSs are classified, and it is experimentally shown that the LRSs based on BAS performed better. Among them, the performance of the linear decay method was shown to be simple and robust.\n\nPros\n\n1. Formally define important and well-motivated issues to improve performance on a limited budget.\n2. Various experimental results show that the simple linear decay method works well, and it might become a baseline method for future budgeted training solutions (assuming there is no similar work with the same purpose).\n3. It seems to be easy to apply to the NAS,  and the experiments in Appendix A look a big plus. This section can be put into the main paper.\n\nCons\n\n1. No sound theory as to why linear decay or other smooth decay methods work well.\n2. As Mishkin et al. [1] have already experimented with linear decay, the novelty of the methodology proposed by the authors might be limited.\n\nWhile there is some concern regarding the significance of novelty,  the paper seems meaningful enough to be accepted.\n\n[1] Dmytro Mishkin, Nikolay Sergievskiy, and Jiri Matas. Systematic evaluation of convolution neural network advances on the imagenet. Computer Vision and Image Understanding, 161: 11–19, 2017.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJgRJmmbjB", "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": "Pros:\nThe paper is clearly written. It provides an interesting perspective for training neural networks under resource constraints. The problem setting is novel. The proposed solution is simply decaying learning rate linearly from the initial value to zero during training, which is parameter free. \n\nCons:\n\n- As the authors are advocating using linear scaling schedule, I would like to see whether it has some clear advantages over other schedules, but it is not quite clear. For example, we can still see step based schedule has better performance in 2 of the 4 tasks in Table 2. Poly and Cosine schedule is also better in some of the budgets in Figure 2. \n\n- The comparison in Figure 2 and Table 2 is not very convincing without considering the variance of different trails. It is not clear whether the advantage is caused by learning rate schedule or randomness. It is better to report the mean and variance for multiple trials. Ideally, it would be better to performance significance test.\n\n- I would like to see other lr schedules in Table 2. As shown in Figure 2, step based schedule is not the top3 schedules for CIFAR-10.\n\n- As shown in Table 3, the proposed method has to wait until the end of training to get the best performing model, while step based schedule can find the best model around 90% training. The author argues that the proposed method does not need to perform validation test for each checkpoint and reduce the computation cost,  however, on the other side, this means early stopping is not able to use for linear scaling based schedule, which could be very useful when the training budget is large enough and evaluation is cheap.\n\n- My major concern for this work is a lack of deeper understanding about the reason why linear LR schedule works better, if any. It would be stronger with such understandings. The authors try to provide an explanation from the relationship between learning rate and gradient magnitudes, but no clear conclusion is given. As noted in [1,2,3], when weight decay is used in training and BN layers are used, the weight magnitude is also decreasing, so is the gradient norms. But the weight norms or gradient norms does not mean too much due to scale invariance. I would like to see when no weight decay is used and whether there is any correlation between the learning rate and gradient norms. \n\n- What is the lr decay unit for linear schedule? Is it decaying per epoch or per mini-batch? If epoch based lr decay is used, it is essentially step-based lr decay with many steps. Then when the number of epochs is three, the step decay method (lr decays at epoch 1 and 2) and the linear decay method are actually almost equivalent. \n\n- I would expect the convergence to be related with number of iterations. When the number of iterations is not long enough, neither linear lr decay or step based decay will work. It would be better if the author can investigate when linear schedule starts to outperforms step based decay in terms of epochs or iterations. Since different batch size results in different number of iterations, I would expect the difference between two schedules for small batch size at the early stage of training would be less in comparison with large batch training, especially when the number of iterations is enough.\n\n- Different initial learning rate may also results in different behaviour. We often see some learning curves with larger initial learning rate converges faster at the beginning but yields similar generalization error at the end of training. On the other hand, the author only compared different schedules with single initial learning rate. Image when the initial learning rate is small, there would not be too much difference for different schedules. Actually the linear decay schedule changes may simply find a good learning rate during training as long as the initial learning rate is larger than the optimal one.\n\n\n[1] Dinh et al, Sharp minima can generalize for deep nets, ICML 2017\n[2] Li et al, Visualizing the Loss Landscape of Neural Nets, NIPS 2018\n[3] van Laarhoven, L2 regularization versus batch and weight normalization, NIPS 2017\n\n\n----- update after rebuttal ------\nThe authors' rebuttal addressed some of my concerns.  I think early stopping is still an important feature to save compute, especially for HPO, which could limit the usage of the proposed method (cannot stop earlier). If the authors believe practitioners are used to train model in full budget without early stopping to guarantee the best performance, then why would people try budged training with worse performance? I hope the authors could make the limitation clear. My major concern about the reason for why linear scaling schedule is better is still not clear, which makes the contribution kind of weak. Nevertheless,  the problem setting and the observations could be beneficial to the community for further discussion, So I raised my score to weak accept.\n\nminor: I see exactly the same variance values for step and linear methods int the top rows of Table 12, is this a mistake?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BygJ8bHctB", "reviewer": "AnonReviewer3", "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": "This work presents a simple technique for tuning the learning rate for Neural Network training when under a \"budget\" -- the budget here is specified as a fixed number of epochs that is expected to be a small fraction of the total number of epochs required to achieve maximum accuracy. The main contribution of this paper is in showing that a simpler linear decay schedule that goes to zero at the end of the proposed budget achieves good performance. The paper proposes a framework called budget-aware schedule which represents any learning rate schedule where the ratio of learning rate at time `'t' base learning rate is only a function of the ratio of 't' to total budget 'T'. In this family of schedules, the paper shows that a simple linear decay works best for all budgets. In the appendix, the authors compare their proposed schedule with adaptive techniques and show that under a given budget, it outperforms latets adaptive techniques like adabound, amsgrad, etc.\n\nPros:\n1. This paper presents a simple technique for a problem that is impactful namely performing training under a small budget presumably as an approximation during neural architecture search or hyperparameter tuning. The technique is empirically shown to be effective for many computer vision benchmarks.\n2. The paper presents extensive experimental results comparing linear decay with other budget-aware schedules. The accuracy comparisons are performed under different budgets as well as for neural architecture ranking while selecting architecture with budgeted training.\n3. Overall, I think this paper can be generally useful for many practitioners.\n\nCons:\n1. The paper makes claims around the phenomena of gradient magnitude vanishing as well as its effectiveness. E.g. in section 5, authors state \"We call this “vanishing gradient” phenomenon budgeted convergence. This correlation suggests that decaying schedules to near-zero rates (and using BAC) may be more effective than early stopping.\". This is not clear from the paper as the paper merely shows gradient magnitude decreasing with learning rate. This claim appear like an overreach to me.\n2. The key motivating use cases for budget-aware training is providing approximations for problems like neural architecture search and hyper parameter tuning. However, for these use cases, the paper does not perform extensive comparisons for commonly used algorithms like Adam. Why?\n\nnits:\n1. In section 2, various -> varies\n2. Right above equation 1, budge -> budget\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper formalizes the problem of training deep networks in the presence of a budget, expressed here as a maximum total number of optimization iterations, and evaluates various budget-aware learning schedules, finding simple linear decay to work well. 

Post-discussion, the reviewers all felt that this was a good paper. There were some concerns about the lack of theoretical justification for linear decay, but these were overruled by the practical use of these papers to the community. Therefore I am recommending it be accepted.
Decision: Accept (Poster)