BUDGETED TRAINING: RETHINKING DEEP NEURAL NETWORK TRAINING UNDER RESOURCE CONSTRAINTS
Year: 2020

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 budgetaware learning schedules readily outperform such approaches under (the practical but under-explored) budgeted training setting.

text: 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 budgetaware learning schedules readily outperform such approaches under (the practical but under-explored) budgeted training setting.

heading: 1 INTRODUCTION
text: Deep neural networks have made an undeniable impact in advancing the state-of-the-art for many machine learning tasks. Improvements have been particularly transformative in computer vision (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 et 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., 2016), assistive medical robots (Taylor et al., 2008), and medical analysis (Fatima & Pasha, 2017) – 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 running out of resources (Bottou, 1998; Rai et al., 2009).
We note that resource-constrained 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 et al., 2017) and neural architecture search (Zoph & Le, 2017; Cao et al., 2019; Liu et al., 2019).
†Work done while at Argo AI.
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 so 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 a 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 a 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 theoretical analysis of optimization algorithms focuses on asymptotic convergence and optimality (Robbins & Monro, 1951; Nemirovski et al., 2009; Bottou et 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; Luo 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 a limited budget, one obvious strategy might be data subsampling (Bachem et 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-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 we 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-the-art models on 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 a 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 minimum1. We call this phenomenon budgeted convergence and we find it generalizes across budgets. On one hand, it 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 as follows:
1Whether such a solution is exactly a local minimum or not is debatable (see Sec 2).
• We introduce a formal setting for budgeted training based on 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 approaches, 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.

heading: 2 RELATED WORK
text: Learning rates. Stochastic gradient descent dates back to Robbins & Monro (1951). The core is its update step: wt = wt−1 − αtgt, where t (from 1 to T ) is the iteration, w are the parameters to be learned, g is the gradient estimator for the objective function2 F , and αt is the learning rate, also known as step size. Given base learning rate α0, we can define the ratio βt = αt/α0. Then the set of {βt}Tt=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 it separates the base learning rate and learning rate schedule. Learning rates are well studied for (strongly) convex cost surfaces and we include a brief review in 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 a small and constant learning rate (Du et al., 2018a;b; Hardt et al., 2016). 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 et al., 2018). Such hypothesis is questioned by recent analysis on mode connectivity, which has revealed that there does exist a descent path between solutions that were previously thought to be isolated local minima (Garipov et al., 2018; Dräxler et al., 2018; Gotmare et al., 2019). Despite a lack of theoretical explanation, the community has adopted a variety of heuristic schedules for practical purposes, two of which are particularly common:
• step decay: drop the learning rate by a multiplicative factor γ after every d epochs. The default for γ is 0.1, but d varies significantly across tasks.
• exponential: βt = γt. There is no default parameter for γ 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., 2017b; He et al., 2017; Carreira & Zisserman, 2017; Wang et al., 2018; Yin et al., 2019; Ma et al., 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 et 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. (2017) demonstrate the effectiveness of linear rate decay with CaffeNet on downsized ImageNet. In our work, we rigorously evaluate on 5 standard vision benchmarks with state-of-the-art networks and under various budgets. Gotmare 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, 2015; 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 be trivially achieved through budget-aware schedules and aggressive early descent is not desirable for achieving good performance in the end.
2Note that g can be based on a single example, a 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.

heading: 3 LEARNING RATES AND BUDGETS

heading: 3.1 BUDGET-AWARE SCHEDULES
text: 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 is early-stopping. Fig 1 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 t, but also the training budget T :
Definition (Budget-Aware Schedule). Let T be the training budget, t be the current step, then a training progress p is t/T . A budget-aware learning rate schedule is
βp : p 7→ f(p), (1) where f(p) is the ratio of learning rate at step t to the base learning rate α0.
At first glance, it might be counter-intuitive for a schedule to not depend on T . For example, for a task that is usually trained with 200 epochs, training 2 epochs will end up at a 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, we 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 a particular rate schedule βt = f(t), one simple method for making it budget-aware is to rescale it, i.e., βp = f(pT0), where T0 is the budget used for the original schedule. For instance, a 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.99t for 200 epochs will be converted into (0.99200)p.
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 as a general strategy for converting many standard schedules to be budget-aware (Tab 1). For our remaining experiments, we regard BAC as a known technique and apply it to our baselines by default.
Recent schedules: Interestingly, several recent learning rate schedules are implicitly defined as a function of progress p = tT , and so are budget-aware by our definition:
• poly (Jia et al., 2014): βp = (1−p)γ . No parameter other than γ = 0.9 is used in published work. • cosine (Loshchilov & Hutter, 2017): βp = η + 12 (1− η)(1 + cos(πp)). η specify a lower
bound for the learning rate, which defaults to zero. • htd (Hsueh et al., 2019): βp = η + 12 (1 − η)(1 − tanh(L + (U − L)p)). Here η has the
same representation as in cosine. It is reported that L = −6 and U = 3 performs the best. The poly schedule is a feature in Caffe (Jia et al., 2014) and adopted by the semantic segmentation community (Chen et al., 2018; Zhao et al., 2017). The cosine schedule is a byproduct in work that promotes learning rate restarts (Loshchilov & Hutter, 2017). The htd schedule is recently proposed (Hsueh et al., 2019), which however, contains only limited empirical evaluation. None of these analyze their budget-aware property or provides intuition for such forms of decay. These schedules were
treated as “yet another schedule”. However, our definition of budget-aware makes these schedules stand out as a general family.

heading: 3.2 LINEAR SCHEDULE
text: Inspired by existing budget-aware schedules, we borrow an even simpler schedule from the simulated annealing literature (Kirkpatrick et al., 1983; McAllester et al., 1997; Nourani & Andresen, 1998)3:
linear : βp = 1− p. (2)
In Fig 2, 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 a parameter. The excellent generalization of linear schedule across budgets (shown in the next section) might imply that the cost surface of deep learning is to some degree self-similar. Note that a linear schedule, together with
3A 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 rate schedules for SGD.
other recent budget-aware schedules, produces a constant learning rate in the asymptotic limit i.e., limT→∞(1 − t/T ) = 1. Consequently, such practically high-performing schedules tend to be ignored in theoretical convergence analysis (Robbins & Monro, 1951; Bottou et al., 2018).

heading: 4 EXPERIMENTS
text: In this section, we first compare linear schedule against other existing schedules on the small CIFAR10 dataset and then on a 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 of random architectures in the setting of neural architecture search.

heading: 4.1 CIFAR
text: CIFAR-10 (Krizhevsky & Hinton, 2009) is a dataset that contains 70,000 tiny images (32 × 32). Given its small size, it is widely used for validating novel architectures. We follow the standard setup for dataset split (Huang et al., 2017b), 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 (equivalent to not using any schedule). (b) & (c) exponential and step decay, both of which are commonly adopted schedules. (d) htd (Hsueh et al., 2019), a 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 (γ = 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-schedule is to decay smoothly to zero. Based on these observations and results, we suggest linear schedule should be the “go-to” budget-aware schedule.

heading: 4.2 VISION BENCHMARKS
text: In the previous section, we showed that linear schedule achieves excellent performance on CIFAR10, 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 2 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 standard for image classification task. We use ResNet-18 (He et al., 2016) 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; PyTorch, 2019), which drops twice at uniform interval (γ = 0.1 at p ∈ { 13 , 2 3}). We set the full budget to 100 epochs (10 epochs longer than typical) for easier computation of the budget.
Object detection and instance segmentation on MS COCO. MS COCO (Lin et al., 2014) is a widely recognized benchmark for object detection and instance segmentation. We use the standard COCO AP (averaged over IoU 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 a ResNet-50 backbone and follow its setup. For training, we adopt the 1x schedule (90k iterations), and the off-the-shelf (He et al., 2017) step decay that drops 2 times with γ = 0.1 at p ∈ { 23 , 8 9}.
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 use state-of-the-art model PSPNet (Zhao et al., 2017) with a ResNet-50 backbone and the full budget is 400 epochs as in standard set up. The mIoU 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 (Kay 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 is 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 γ = 0.1 at p ∈ { 12 , 5 6}.
If we factor in the dimension of budgets, Tab 3 shows a clear advantage of linear schedule over step decay. For example, on ImageNet, linear achieves 51.5% improvement at 1% of the budget. Next, we consider the full budget setting, where we simply swap out the off-the-shelf schedule with linear schedule. We observe better (video classification) or comparable (other tasks) performance after the swap. This is surprising given the fact that linear schedule is parameter-free and thus not optimized for the particular task or network.
In summary, the smoothly decaying linear schedule is a 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.

heading: 5 DISCUSSION
text: 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 unless otherwise stated.
Desideratum: budgeted convergence. Convergence of SGD under non-convex objectives is measured by limt→∞ E[||∇F ||2] = 0 (Bottou et al., 2018). Intuitively, one should terminate the optimization when no further local improvement can be made. What is the natural counterpart for “convergence” within a budget? For a dataset of N examples {(xi, yi)}Ni=1, let us write the full gradient as g∗t = 1 N ∑N i=1∇F (xi, yi). We empirically find that the dynamics of ||g∗t || over time highly correlates with the learning rate αt (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 a side note, budgeted convergence resonates with classic literature that argues that SGD behaves similar to simulated annealing (Bottou, 1991). Given that αt and ||g∗t || decrease, the overall update ||−αtgt|| also decreases4. 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 in 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 multiple checkpointed models during a training run, where a 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 an 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 expensive. For example, validation for Kinetics video classification takes several hours. Budget-aware schedules require validation on only the last few epochs, saving additional compute.
4Note that the momentum in SGD is used, but we assume vanilla SGD to simplify the discussion, without losing generality.
Aggressive early descent. Guided by asymptotic convergence analysis, faster descent of the objective might be an 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 learning rates can prevent budgeted convergence. Consider AMSGrad (Reddi et al., 2018), an adaptive learning rate that addresses a 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 β̃t 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 E.
Warm restarts. SGDR (Loshchilov & Hutter, 2017) 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-aware schedules for any budget (similar to the adaptive optimizers above). Additional comparisons can be found in Appendix F. Whether there exists a method that achieves promising anytime performance and budgeted performance at the same time remains an open question.

heading: 6 CONCLUSION
text: This paper introduces a formal setting for budgeted training. Under this setup, we observe that a simple linear schedule, or any other smooth-decaying schedules can achieve much better performance. Moreover, the linear schedule even offers comparable performance on existing visual recognition tasks for the typical full budget case. In addition, we analyze the intriguing properties of learning rate schedules under budgeted training. We find that the learning rate schedule controls the gradient 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.
Acknowledgements: We thank Xiaofang Wang, Simon S. Du, Leonid Keselman, Chen-Hsuan Lin and David McAllester for insightful discussions and comments.

heading: A BUDGETED TRAINING FOR NEURAL ARCHITECTURE SEARCH
text: 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 a small budget (10-25 epochs) to evaluate their relative performance (Cao et al., 2019; Cai et al., 2018; Real et al., 2019). Under this setting, the goal is to rank the performance of different architectures 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, it 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 et al., 2019) to generate 100 random architectures, which are 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 a 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 (τ ), a standard statistics metric for measuring rank similarity. It is based on counting the inversion pairs in the two ranks and (τ +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 required if only the relative performance is considered. (2) step decay (γ = 0.1, decay at p ∈ { 13 , 2 3}), 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 et al., 2018; Real et 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 fullbudget 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 5).
Epoch (Budget) 1 (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. Smoothdecaying schedules like linear and cosine can more accurately predict the true rank of different architectures given limited budget.
Epoch (Budget) 1 (0.5%) 2 (1%) 10 (5%) 20 (10%)
const 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.
Epoch (Budget) 1 (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 to their full-budget performance than the rest of schedules under small budgets.
A.2 BUDGETED PERFORMANCE ACROSS ARCHITECTURES
To reinforce our claim that linear schedule generalizes across different settings, we compare budgeted performance of various schedules on random architectures generated in 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 is 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.

heading: B EQUIVALENT LEARNING RATE FOR AMSGRAD
text: In Sec 5, 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 β̃t.
Let η1, η2 and be hyper-parameters, then the momentum SGD update rule is:
mt = η1mt−1 + (1− η1)gt, (3)
wt = wt−1 − α(1)0 βtmt, (4) while the AMSGrad update rule is:
mt = η1mt−1 + (1− η1)gt, (5) vt = η2vt−1 + (1− η2)g2t , (6) m̂t = mt
1− ηt1 , (7)
v̂t = vt
1− ηt2 , (8)
v̂maxt = max(v̂ max t , v̂t) (9)
wt = wt−1 − α(2)0 m̂t√ v̂maxt + . (10)
Comparing equation 4 with 10, we obtain the equivalent learning rate:
β̃t = α (2) 0
α (1) 0
1 (1− ηt1)( √ v̂maxt + ) , (11)
Budget 1% 5% 10% 25% 50% 100%
Subset .3834 .6446 .7848 .8586 .9234 N/A Full .5544 .8328 .9042 .9338 .9464 .9534
Table D: Comparison with offline data subsampling. “Subset” meets the budget constraint by randomly 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, we take the median across all dimensions as a scalar summary since it is a skewed distribution. The mean appears to be even larger and shares the same trend as the median. In our experiments, we use the default hyper-parameters (which also turn out to have the best validation accuracy): α(1)0 = 0.1, α (2) 0 = 0.001, η1 = 0.9, η2 = 0.99 and = 10−8.

heading: C DATA SUBSAMPLING
text: Data subsampling is a straight-forward strategy for budgeted training and can be realized in several different ways. In our work, we limit the number of iterations to meet the budget constraint and this effectively limits the number of data points seen during the training process. An alternative is to construct a subsampled dataset offline, but keep the same number of training iterations. Such construction can be done by random sampling, which might be the most effective strategy for i.i.d (independent and identically distributed) dataset. We show in Tab D that even our baseline budgeaware step decay, together with a limitation on 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 setting, we use the same step decay but with BAC applied (Sec 3.1). For detailed setup, we follow Sec 4.1, of the main text.
Of course, more complicated subset construction methods exist, such as core-set construction (Bachem et al., 2017). 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-10, a well-constructed and balanced dataset, making smarter subsampling methods less advantageous. Consequently, the result in Tab D can as well provides a reasonable estimate for other complicated subsampling methods.

heading: D ADDITIONAL EXPERIMENTS ON CITYSCAPES (SEMANTIC SEGMENTATION)
text: In the main text, we compare linear schedule against step decay for various tasks. However, the off-the-shelf schedule for PSPNet (Zhao et al., 2017) is poly instead of step decay. Therefore, we include the evaluation of poly schedule on Cityscapes (Cordts et al., 2016) in Tab E. Given the similarity of poly and linear (Fig 2), and the opposite results on CIFAR-10 and Cityscapes, it is inconclusive that one is strictly better than the other within the smooth-decaying family. However, these smooth-decaying methods both outperform step decay given limited budgets.
Budget 1% 5% 10% 25% 50% 100%
poly .5476 ± .0023 .6755 ± .0012 .7093 ± .0058 .7416 ± .0028 .7562 ± .0045 .7593 ± .0043 linear .5424 ± .0034 .6654 ± .0014 .7076 ± .0047 .7399 ± .0005 .7575 ± .0041 .7633 ± .0008
Table E: Comparison with off-the-shelf poly schedule on Cityscapes Cordts et al. (2016) using PSPNet Zhao et al. (2017). Poly and linear are similar smooth-decaying schedules (Fig 2) and thus have similar performance. The exact rank differs from task to task.

heading: E ADDITIONAL COMPARISON WITH ADAPTIVE LEARNING RATES
text: 0 50 100 150 200 Epoch
0.0
0.2
0.4
0.6
0.8
1.0 (a) Training Loss
Linear 10% Linear 25% Linear 50% Linear 100% AMSGrad + Linear AMSGrad AdaBound RMSprop
0 50 100 150 200 Epoch
0.4
0.5
0.6
0.7
0.8
0.9
1.0 (b) Validation Accuracy
Linear 10% Linear 25% Linear 50% Linear 100% AMSGrad + Linear AMSGrad AdaBound RMSprop
Method Val Accu
RMSprop .9258 AdaBound .9306 AMSGrad .9113
AMSGrad + Linear .9340
SGD + Linear 10% .9218 SGD + Linear 25% .9412 SGD + Linear 50% .9546 SGD + Linear 100% .9562
Figure A: Comparison between budget-aware linear schedule and adaptive learning rate methods on CIFAR-10. We 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 version over Adam (Kingma & Ba, 2015)), we 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 budgetaware linear schedule outperforms adaptive methods for all given budgets.
Like SGD, those adaptive learning rate methods also takes input a parameter of base learning rate, which can also be annealed using an existing schedule. Although it is unclear why one needs to anneal an adaptive methods, we find that it in facts boosts the performance (“AMSGrad + Linear” in Fig A).

heading: F ADDITIONAL COMPARISON WITH SGDR
text: This section provides additional evaluation to show that learning rate restart produces worse results than our 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, we use “cosine schedule”, or just “cosine”, to 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: T0, the length of the first period; Tmult, where i-th period has length Ti = T0T i−1mult . In Fig B, we plot the off-the-shelf SGDR schedule with T0 = 10 (epoch), Tmult = 2. The validation accuracy plot (on the right) shows that it might end at a very poor solution (0.8460) since it is not budget-aware. Therefore, we consider two settings to compare
0 50 100 150 200 Epoch
0
20
40
60
80
100
Fr ac
tio n
of B
as e
Le ar
ni ng
R at
e (%
) (a) Learning Rate Schedule
0 50 100 150 200 Epoch
0.5
0.6
0.7
0.8
0.9
1.0
Ac cu
ra cy
(b) Validation Accuracy
SGDR (off-the-shelf) SGDR-r2
Figure B: One issue with off-the-shelf SGDR (T0 = 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 n times at even intervals across the budget and n = 2 is shown here (SGDR-r2).
Epoch 30 50 150
SGDR .9320 .9458 .9510 linear .9350 .9506 .9532
Table F: Comparison with off-the-shelf SGDR at the end of each period after the first restart.
Budget 1% 5% 10% 25% 50% 100%
SGDR-r1 .5002 .7908 .8794 .9250 .9380 .9488 SGDR-r2 .4710 .7888 .8738 .9216 .9412 .9502 linear .6654 .8920 .9218 .9412 .9546 .9562
Table G: Comparison with SGDR under budget-aware setting. “SGDR-r1” refers to restarting learning 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 to 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 n times at 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 Sec 4.1, of the main text and take the median of 3 runs.

heading: G ADDITIONAL ILLUSTRATIONS
text: In Sec 5, we refer to validation accuracy curve for training on CIFAR-10, which we provide here in Fig C.

heading: H LEARNING RATES IN CONVEX OPTIMIZATION
text: 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 ∇F (Bottou et al., 2018). Another well-known result ensures convergence for sequences that decay neither too fast nor too slow (Robbins & Monro, 1951): ∑∞ t=1 αt =∞, ∑∞ t=1 α 2 t <∞. One common such instance in convex optimization is αt = α0/t. For non-convex problems, similar results hold for convergence to a local minimum (Bottou et al., 2018). Unfortunately, there does not exist a theory for learning rate schedules in the context of general non-convex optimization.
0 50 100 150 200 Epoch
0.0
0.3
0.6
0.9
1.2
1.5 (a) Training Loss
step-d2 linear
0 50 100 150 200 Epoch
0.5
0.6
0.7
0.8
0.9
1.0 (b) Validation Accuracy
step-d2 linear
Figure C: Training loss and validation accuracy for training ResNet-18 on 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”.
0 50 100 150 200 Epoch
30
40
50
60
70
W ei
gh t N
or m
(a) Constant
0 50 100 150 200 Epoch
20
30
40
50
W ei
gh t N
or m
(b) Step Decay
0 50 100 150 200 Epoch
20
30
40
50
W ei
gh t N
or m
(c) Exponential
0 50 100 150 200 Epoch
20
30
40
50
W ei
gh t N
or m
(d) SGDR
0 5 10 15 20 Epoch
25
35
45
55
W ei
gh t N
or m
(e) Linear 10%
0 25 50 75 100 Epoch
25
35
45
55
W ei
gh t N
or m
(f) Linear 50%
0 50 100 150 200 Epoch
25
35
45
55
W ei
gh t N
or m
(g) Linear 100%
0 25 50 75 100 Training Progress (%)
25
35
45
55
W ei
gh t N
or m
(h) Linear (Across Budgets)
0.07
0.11
0.15
Le ar
ni ng
R at
e
0.00
0.05
0.10
Le ar
ni ng
R at
e
0.00
0.05
0.10
Le ar
ni ng
R at
e
0.00
0.05
0.10
Le ar
ni ng
R at
e
0.00
0.05
0.10
Le ar
ni ng
R at
e
0.00
0.05
0.10
Le ar
ni ng
R at
e
0.00
0.05
0.10
Le ar
ni ng
R at
e
0.00
0.05
0.10
Le ar
ni ng
R at
e
Figure D: The corresponding weight norm plots for Fig 3 and Fig 5. We find that the weight norm exhibits a similar trend as the gradient norm.

heading: I FULL GRADIENT NORM AND THE WEIGHT NORM
text: In Sec 5, we plot the full gradient norm of the cross-entropy loss, excluding the regularization part. In fact, we use an L2-regularization (weight decay) of 0.0004 for these experiments. For completeness, we plot the weight norm in Fig D.

heading: J ADDITIONAL ABLATION STUDIES
text: Here we explore variations of batch size (Tab H) and initial learning rate (Tab I). 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, 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 5 epochs.
Batch Size Schedule 20% 50% 100%
64 step-d2 .9436 ± .0037 .9505 ± .0009 .9519 ± .0009 64 linear .9473 ± .0021 .9511 ± .0008 .9526 ± .0020
256 step-d2 .8939 ± .0027 .9291 ± .0021 .9431 ± .0008 256 linear .9143 ± .0018 .9415 ± .0038 .9484 ± .0013
1024 step-d2 .5851 ± .0460 .7703 ± .0121 .8805 ± .0007 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.

heading: K ADDITIONAL IMPLEMENTATION DETAILS
text: Image classification on ImageNet. We adapt both the network architecture (ResNet-18) and the data loader from the open source PyTorch ImageNet example5. The base learning rate used is 0.1 and weight decay 5 × 10−4. We train using 4 GPUs with asynchronous batch normalization and batch size 128.
Video classification on Kinetics with I3D. The 400-category version of the dataset is used in the evaluation. We use an open source codebase6 that has training and data processing code publicly available. Note that the codebase implements a variant of standard I3D (Carreira & Zisserman, 2017) that has ResNet as the backbone. We follow the configuration of run i3d baseline 300k 4gpu.sh, which specifies a base learning rate 0.005 and a weight decay 10−4. Only learning rate schedule is 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 implementation of Mask R-CNN7, which is a PyTorch re-implementation of the official codebase Detectron in the Caffe 2 framework. We only modify the part of the code for learning rate schedule. The codebase 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 multiGPU 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 correspondence with the authors of PSPNet. The base learning rate is set to 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 a single output. For overlapped regions, the average logits of two patches are taken. We train using 4 GPUs with synchronous batch normalization and batch size 12.
5https://github.com/pytorch/examples/tree/master/imagenet. PyTorch version 0.4.1.
6https://github.com/facebookresearch/video-nonlocal-net. Caffe 2 version 0.8.1. 7https://github.com/roytseng-tw/Detectron.pytorch. PyTorch version 0.4.1.

Review summaries:
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.

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.