Speeding up NAS with Adaptive Subset Selection

Authors: vishak  prasad
colin  white
sibasis  nayak
paarth  jain
aziz  shameem
prateek  garg
ganesh  ramakrishnan
Venue: automl_cc_AutoML_2024_Conference
Published: 2024-02-20 20:18:48

Abstract: A majority of recent developments in neural architecture search (NAS) have been aimed at decreasing the computational cost of various techniques without affecting their final performance. Towards this goal, several low-fidelity and performance prediction methods have been considered, including those that train only on subsets of the training data. In this work, we present an adaptive subset selection approach to NAS and present it as complementary to state-of-the-art NAS approaches. We uncover a natural connection between one-shot NAS algorithms and adaptive subset selection and devise an algorithm that makes use of state-of-the-art techniques from both areas. We use these techniques to substantially reduce the runtime of DARTS-PT (a leading one-shot NAS algorithm), as well as BOHB and DEHB (leading multi-fidelity optimization algorithms), with minimal sacrifice to accuracy. In experiments, we find architectures on CIFAR-10 that give 5\% increase in performance over DARTS-PT while reducing the time required by more than 8 times. Our results are consistent across multiple datasets, and towards full reproducibility, we release all our code at \url{https://anonymous.4open.science/r/SubsetSelection_NAS-87B3}

Main paper: 
 introduction: 
 Neural architecture search (NAS), the process of automating the design of high-performing neural architectures, has been used to discover architectures that outpace the best human-designed neural networks (Dai et al., 2020; Real et al., 2019; Tan and Le, 2019) . Early NAS algorithms used black-box optimization methods such as reinforcement learning (Pham et al., 2018; Zoph and Le, 2017) and Bayesian optimization (Kandasamy et al., 2018) . A majority of recent developments have focused on decreasing the cost of NAS without sacrificing performance.Toward this direction, 'one-shot' methods improve the search efficiency by training just a single over-parameterized neural network (supernetwork) (Bender et al., 2018; Liu et al., 2019) . For example, the popular DARTS (Liu et al., 2019) algorithm applies a continuous relaxation to the architecture parameters, allowing the architecture parameters and the weights to be simultaneously optimized via gradient descent. While many follow-up works have improved the performance of DARTS (Laube and Zell, 2019; Wang et al., 2021; Zela et al., 2020) , the algorithms are still slow and require computational resources that are expensive in terms of budget and CO2 emissions (Tornede et al., 2021) .On the other hand, the field of subset selection for efficient machine learning-based model training has seen a flurry of activity. In this area of study, facility location (Mirzasoleiman et al., 2020) , clustering (Clark et al., 2020) , and other subset selection algorithms are used to select a representative subset of the training data, substantially reducing the runtime of model training. Recently, adaptive subset selection algorithms have been used to speed up model training even further (Killamsetty et al., 2021 (Killamsetty et al., , 2020)) . Adaptive subset selection is a powerful technique which regularly updates the current subset of the data as the search progresses, to ensure that the performance of the model is maintained.Figure 1 : Overview of Adaptive-Dpt. The algorithm starts with the initial set of weights 𝜃 (0) , architecture-parameters 𝛼 (0) , and subset of the training data 𝑆 (0) . Throughout the search, the weights 𝜃 (𝑖 ) and architecture-parameters 𝛼 (𝑖 ) are updated with SGD, and the subset 𝑆 (𝑖 ) is updated with Glister, according to different time schedules. Then the final architecture 𝛼 (𝑓 ) is discretized and returned. 
related work: 
 Neural architecture search. NAS has been studied since the 1980s (Angeline et al., 1994; Dress, 1987; Kitano, 1990; Tenorio and Lee, 1988) and has been revitalized in recent years (Liu et al., 2019; Zoph and Le, 2017) . The initial set of approaches focused on evolutionary search (Real et al., 2019; Stanley and Miikkulainen, 2002) , reinforcement learning (Pham et al., 2018; Zoph and Le, 2017) , and Bayesian optimization (Kandasamy et al., 2018; White et al., 2021) . More recent trends have focused on reducing the computational complexity of NAS using various approaches. One line of work aims to predict the performance of neural architectures before they are fully trained, through low-fidelity estimates such as training for fewer epochs (Ru et al., 2020; Zhou et al., 2020) , learning curve extrapolation (Domhan et al., 2015; Yan et al., 2021) , or 'zero-cost proxies' (Abdelfattah et al., 2021; Mellor et al., 2020) .Another line of work takes a one-shot approach by representing the entire space of neural architectures by a single 'supernetwork', and then performing gradient descent to efficiently converge to a high-performing architecture (Liu et al., 2019) . Since the release of the original differentiable architecture search method (Liu et al., 2019) , several follow-up works have attempted to improve its performance (Laube and Zell, 2019; Li et al., 2021; Liang et al., 2019; Xu et al., 2019; Zela et al., 2020) . Recently, Wang et al. (2021) introduced a more reliable perturbation-based operation scoring technique while computationally returning the final architecture, yielding more accurate models compared to DARTS.Subset selection. Several approaches have been developed in the field of subset selection for efficient model training. Popular fixed subset selection methods include coreset algorithms (Har-Peled and Mazumdar, 2004; Mirzasoleiman et al., 2020) , facility location (Mirzasoleiman et al., 2020) , and entropy-based methods (Na et al., 2021) . Recently, Killamsetty et al. (2020) proposed GLISTER as an adaptive subset selection method based on a greedy search; an adaptive gradient-matching algorithm for subset selection was also subsequently proposed (Killamsetty et al., 2021) .Subset selection in NAS. A few existing works have applied fixed (non-adaptive) subset selection to the field of NAS. Na et al. (2021) consider three subset selection approaches: forgetting events, 𝑘-center, and entropy-based techniques, showing that the entropy-based approaches result in the best speedup in the case of DARTS. Shim et al. (2021) consider core-set sampling to speed up PC-DARTS by a factor of 8. Some more recent work (Killamsetty et al., 2022) employs subset selection algorithms to obtain greater speed-ups over multi-fidelity methods such as Hyperband (Li et al., 2018) and ASHA (Li et al., 2020) . Another league of recent work uses a generative model to create a small set of synthetic training data, which in turn is used to efficiently train architectures during NAS (Rawal et al., 2020; Such et al., 2019) .Very recently, there has been more work on subset selection for NAS (Lu et al., 2024; Tu et al., 2023; Xie et al., 2024) . We refer to Bartoldson et al. (2023) ; Lei and Tao (2023) for comprehensive surveys, and we discuss the most relevant works below. The most similar technique to our approach is perhaps Yao et al. (2023) , recent subsequent work, which proposes a framework for bi-level adaptive subset selection for one-shot NAS. However, they use an mixture of objectives for subset selection rather than directly integrating the subset selection optimization into the existing architecture parameter optimization. Furthermore, they do not test their method with DARTS-PT (Wang et al., 2021) . Finally, Jain et al. (2023) devise SubSelNet, a subset selection framework that uses a fast neural surrogate alongside an optimization routine in order to efficiently find the best subset of training data for new architectures. However, their method requires an initial surrogate model which uses additional computational resources. 
methodology: 
 In this section, we first present the requisite background on supernet-based NAS algorithms and adaptive subset selection algorithms. Then, we introduce our approach, which combines these two techniques.We begin by reviewing the ideas behind DARTS and DARTS-PT. The DARTS search space consists of cells, with each cell expressed as a directed acyclic graph, where each edge (𝑖, 𝑗) can take on choices of operations 𝑜 (𝑖,𝑗 ) such as max_pool_3x3 or sep_conv_5x5. Let us denote the entire set of possible operations by O. Each choice of operation for a given edge (𝑖, 𝑗), has a corresponding continuous valued variable 𝛼 (𝑖,𝑗 ) . Let U and V denote the training and validation sets respectively. Further, let us denote the training and validation losses by L train and L val , respectively. For any given dataset, these losses are a function of the architecture parameters and the architecture itself.DARTS and DARTS-PT are both gradient-based optimization methods that train a supernetwork consisting of weights 𝜃 and architecture-parameters 𝛼. We will hereafter refer to 𝛼's as NAS parameters. Each edge in the DARTS search space can assume any of the operations from the set of choices (O), resulting in a mixed output defined byEQUATIONwhere 𝑜 (𝑥 𝑖 ) denotes the output of operation 𝑜 applied to feature map 𝑥 𝑖 . DARTS and DARTS-PT both attempt to solve the following expression via alternating gradient updates:EQUATIONIn particular, the gradient with respect to 𝛼 can be approximated viaEQUATIONwhich can then be optimized using alternating gradient descent updates, according to a hyperparameter 𝜁 (learning rate).Once the supernetwork finishes training via gradient descent, the continuous NAS parameters 𝛼 must be discretized. In the original DARTS algorithm, this is achieved by taking the largest 𝛼 𝑜 on each edge. However, Wang et al. (2021) showed that this approach may not perform well. Instead, at each edge, DARTS-PT directly evaluates the strength of each operation by its contribution to the supernetwork's performance, using a perturbation-based scoring technique (Wang et al., 2021) . Now that we have given an overview of one-shot methods, in the next section we give an overview of adaptive subset selection methods, before combining them in Sec. 3.3Glister. (GeneraLIzation based data Subset selecTion for Efficient and Robust learning), is a subset selection algorithm that adaptively selects a subset of the training data that maximizes the log-likelihood on a held-out validation set. This problem is formulated as a mixed discretecontinuous bi-level optimization problem. Glister approximately solves the following expression by first approximating the bi-level optimization expression using a single gradient step, and then using a greedy data subset selection procedure (Killamsetty et al., 2020) . (4)In particular, the validation loss is approximated as follows:EQUATIONThereafter, a simple greedy dataset subset selection procedure is employed to find the subset 𝑆 which approximately minimizes the validation loss (Killamsetty et al., 2020) . Now that we have gone over the preliminaries of one-shot NAS and adaptive subset selection, we combine them in the next section. Our main approach makes use of Glister, but we also consider Grad-Match, another adaptive subset selection approach, as an ablation study in Appendix A.4.4.Adaptive-Dpt. There exist multiple possibilities for applying adaptive subset selection to one-shot NAS. We present Glister here (the best-performing method in our experiments) and Grad-Match in Appendix A.4.4. Specifically, we now present a formulation that organically combines Equation (2) and Equation ( 4) into a single mixed discrete and continuous bi-level optimization problem. The inner optimization is the minimization (over model weights 𝜃 ) of training loss during architecture training, on a subset of the training data of size 𝑘. In the outer optimization, we minimize the validation loss by simultaneously optimizing over the NAS parameters 𝛼 as well as over the subset of the training data 𝑆. This optimization problem is aimed at efficiently determining the best (or, at least, an effective) neural architecture:EQUATIONEvaluating this expression is computationally prohibitive because of the expensive inner optimization problem. Instead, we iteratively perform a joint optimization of the weights 𝜃 from the inner optimization as well as the training subset 𝑆 and NAS parameters 𝛼 from the outer optimization. In order to iteratively update the training subset and architecture, we compute meta-approximations of the inner optimization. As for the architecture, we computeEQUATIONFor the subset selection optimization problem, following Killamsetty et al. (2020) , we run a greedy algorithm on a similar approximation to the inner optimization:EQUATION)The above equations form the basis of our method: we iteratively update the outer parameters (architecture and subset) using the approximations above, and the inner parameters (weights) using standard gradient descent; also see Algorithm 1 for the details of our approach. Following prior work (Killamsetty et al., 2020; Liu et al., 2019) , we only update the architecture and subset every 𝑡 1 and 𝑡 2 steps, respectively, for efficiency (𝑡 1 << 𝑡 2 ). 
experiments: 
 In this section, we describe our experimental setup and results.Search spaces. We perform experiments on NAS-Bench-201 with CIFAR-10, CIFAR-100, and ImageNet16-120, DARTS with CIFAR-10, and DARTS-S4 with CIFAR-10. See Appendix A.3 for more information on the search spaces. -1) , 𝛼 (𝑡 -1) ) 5:𝑆 (𝑡 ) = GreedyDSS(U, V, 𝜃 (𝑡else:6: 𝑆 (𝑡 ) = 𝑆 (𝑡 -1) 7: if 𝑡 mod 𝑇 2 == 0: 8:Perform one step of SGD to update 𝛼 (𝑡 ) using 𝑉 9: else: 10:𝛼 (𝑡 ) = 𝛼 (𝑡 -1) 11:Perform one step of SGD to update 𝜃 (𝑡 ) using 𝑆 (𝑡 ) and 𝛼 (𝑡 ) . 12: Discretize the supernet, based on NAS parameters 𝛼 (𝑇 ) obtained using 𝑆 (𝑇 ) , to return final architecture 13: Train 𝛼 using SGD with the full training set U 14: Return: Final architecture (discretized 𝛼 (𝑇 ) ) Baselines and approaches tested. We perform experiments with DARTS-PT, Adaptive-Dpt, and three other (non-adaptive) data subset selection methods applied to DARTS-PT (Wang et al., 2021) . We describe the details of each approach below.• Darts-pt: We use the original implementation of DARTS-PT, as described in Sec. 3.• Darts-pt-rand: This is similar to Darts-pt, but the supernetwork is trained and discretized using a random subset of the training data.• Darts-pt-fl: While similar to Darts-pt, the supernetwork is trained and discretized using a subset of the training data, selected using facility location. The facility location function attempts to find a representative subset of items. The function is similar to k-medoid clustering: for each data point 𝑖 in the ground set 𝑉 , we compute the representative from subset 𝑋 which is closest to 𝑖 and add these similarities for all data points.EQUATIONThe facility location algorithm was implemented using the naive greedy algorithm and ran on each class separately, using a dense Euclidean metric. For this, we employed the submodlib library (Kaushal et al., 2022) .• Darts-pt-entropy (Na et al., 2021) : again, this bears similarity to Darts-pt but using a nonadaptive subset selection procedure. Specifically, the subset of the training data is selected using a combination of high and low-entropy datapoints. Unlike the other existing zero cost subset selection methods for NAS, this approach is specifically tailored for NAS and accelerates neural architecture search using proxy data. The entropy of a datapoint is calculated by training a base neural architecture from the search space, and determining whether the output probability is low or high. This approach was adopted by Na et al. (2021) , to speed up DARTS.• Adaptive-Dpt: This is one of our key approaches, as described in Algorithm 1.Experimental setup. Following Wang et al. (2021) , we use 50% of the full training dataset for supernet training and 50% for validation. We report the accuracy of the finally obtained architecture on the held-out test set. In our primary experiments, for each (adaptive or non-adaptive) subset selection method, we set the subset size to 10% of the training dataset. We run the same experimental procedure for each method: select a size-10% subset of the full training dataset, train and discretize the supernet on the subset, and train the final architecture using the full training dataset. For Darts-pt, we run the same procedure using the full training dataset at each step. We otherwise use the exact same training pipeline as in Wang et al. (2021) , i.e, batch size of 64, learning rate of 0.025, momentum of 0.9, and cosine annealing. We run all experiments on an NVIDIA Tesla V100 GPU. We run each algorithm with 5 random seeds, reporting the mean and standard deviation of each method, with the exception of Darts-pt; due to its extreme runtime and availability of existing results, we perform the experiment once and verify that the result is nearly identical to published results (Wang et al., 2021) . We also report the time it takes to output the final architecture.In this section, we give results for Adaptive-Dpt across the search spaces and baselines described above. We start with the core results, then we present ablations, and then we describe the key takeaways.In Tab. 1, Tab. 2, and Tab. 3, we report the results on NAS-Bench-201. On CIFAR-10 and ImageNet16-120, Adaptive-Dpt yields higher accuracy than all other algorithms tested, and on CIFAR-100, Adaptive-Dpt is essentially tied with Darts-pt-fl for the highest accuracy. Furthermore, all NAS algorithms that use subset selection have significantly decreased runtime -Adaptive-Dpt sees a factor of 9 speedup compared to Darts-pt. Note that Darts-pt-fl takes more time when the number of examples per class in the dataset is higher, so it sees comparatively higher runtimes on CIFAR-10.Next, in Tab. 4 and Tab. 5, we report the results on S4 CIFAR-10 and DARTS CIFAR-10. Once again, the runtime of Adaptive-Dpt is significantly faster than Darts-pt -a factor of 7 speedup. On these search spaces, the performances of the subset-based methods are more similar when compared to NAS-Bench-201, and on the DARTS search space, Adaptive-Dpt does not outperform Darts-pt. A possible explanation is that S4 and DARTS are significantly larger search spaces than NAS-Bench-201 and require more training data to distinguish between architectures. To test this, we included an additional experiment in Tab. 5, giving Adaptive-Dpt 20% and 30% training data instead of 10%. We find that the accuracy significantly increases, moving within one standard deviation of the accuracy of Darts-pt for 20% and slightly better than Darts-pt for 30%.Additionally, since Jain et al. (2023) ran the same experiment as us on the DARTS CIFAR-10, we compare our results in Tab. 5 to their Table 4 . Adaptive-Dpt achieves 96.73 ± 0.29%, 96.97 ± 0.24%, and 97.30 ± 0.05% on 10%, 20%, and 30% data, compared to SubSelNet's 97.18%, 97.24%, and 97.32% across 10%, 20%, and 40% data. Note a caveat: since we are comparing to results in their paper, we only accuracy with respect to subset size, and although the experimental setup appears to be similar, we cannot guarantee it is a fully apples-to-apples comparison. That said, Adaptive-Dpt performs within the standard deviation of the accuracy of SubSelNet, and achieves near-identical performance with 30% data vs. their 40% data. Overall, Adaptive-Dpt achieves near-top performance across all search spaces, while also achieving no less than a seven-fold increase in runtime compared to Darts-pt.Ablation study. Next, we briefly describe three ablation studies: using Grad-Match rather than Glister, computing the accuracy of Adaptive-Dpt as a function of subset sizes, and performing the projection step with/without the full training dataset. We present these ablation studies in Appendix A.1, and we summarize the results here.In Appendix A.4.4, we report the results of DARTS-PT with adaptive subset selection using Grad-Match (Killamsetty et al., 2021) on NAS-Bench-201 with datasets CIFAR-10 and CIFAR-100. Although DARTS-PT with Grad-Match could not outperform Adaptive-Dpt, it outperformed most non-adaptive subset selection methods.In Appendix A.1, we test the performance of Adaptive-Dpt using different percentages of the training data, ranging from 1% to 50%, on NAS-Bench-201 CIFAR10. Interestingly, we see a U-shape: the highest accuracy with Adaptive-Dpt is at 20%, achieving accuracy higher than the standard setting of 100% data. Since the supernetwork is an over-parameterized model of weights and architecture parameters, and Adaptive-Dpt regularly updates the training subset to maximize validation accuracy, Adaptive-Dpt may help prevent the supernetwork from overfitting. Finally, we compare Adaptive-Dpt with and without using the full training dataset for the projection (perturbation) step of DARTS-PT, where the default for Adaptive-Dpt is to use a subset of the data. We find that there is high increase in the runtime, and accuracy is moderately improved on DARTS CIFAR10, and remains similar for S4. We present the full details in Appendix A.1. Key takeaways. Overall, we find that across many settings, Adaptive-Dpt improves the runtime by roughly an order of magnitude, without sacrificing accuracy. While using 10% of the training data is a strong default, the user may decide their desired tradeoff between performance and accuracy, and choose the subset size in the supernetwork training accordingly.In this section, we discuss additional extensions beyond our core results and ablations above. Specifically, we consider experiments with additional NAS algorithms (DEHB and BOHB), and additional regularisation with other subset selection methods.Adaptive-DEHB and Adaptive-BOHB. To show the generality of our approach, we combine DEHB (Awad et al., 2021) and BOHB (Falkner et al., 2018b) with adaptive subset selection (Glister). These are (efficient) iterative algorithms, meaning that we can simply run DEHB and BOHB as normally, while iteratively selecting the best subset using Equation (4) and Equation ( 5), rather than the more involved optimization procedure that we used for one-shot methods. See Appendix A.5 for more details. We use the same search space as Awad et al. (2021) : a configuration sampled from a parameter space (with parameters such as kernel size, channel size, and stride) is used to instantiate a base CNN architecture. On this architecture, we trained DEHB on the MNIST dataset for 100 epochs with and without subset selection. Across 5 seeds, DEHB trained without adaptive subset selection took 0.91 hours and gave 0.96 ± 0.03 accuracy whereas Adaptive-DEHB using 20% data and selecting subset at every 10 epochs took 0.85 hours and yielded 0.99 ± 0.00 accuracy. For Fashion-MNIST (Xiao et al., 2017) , across 3 seeds, DEHB took 1.43 hours and gave 0.85 ± 0.03, while Adaptive-DEHB using 20% data took 0.98 hours and yielded 0.94 ± 0.03.For BOHB on the MNIST dataset, one set of experiments was done with this complete data and another with a subset of these selected by Glister every 10 epochs. BOHB without adaptive subset selection gave an accuracy of 0.99 ± 0.00 and took 2.43 hours on MNIST dataset whereas Adaptive-BOHB gave an accuracy of 0.98 ± 0.00 and took 1.16 hours with 20% data.Regularisation with fixed subset selection functions. In Sec. 4.2, we showed that Adaptive-Dpt can sometimes outperform DARTS-PT, due to a (likely) regularization effect. Now, we push this further by applying additional fixed subset selection. Specifically, we add a fixed subset selection function, 𝑅(𝑆) to our original objective, along with a 𝜆 tradeoff parameter:EQUATIONThen, we run the method the same way as before (Algorithm 1). We considered two regularization functions. First is a random function, Adaptive-Dpt(R) (selecting 10% random data) and second is supervised facility location, Adaptive-Dpt(F) which is NN-submodular function on the training set features. We tested on CIFAR-100 and found that adaptive subset selection using regularised (supervised facility location) Glister outperforms all models on CIFAR-100 with a tradeoff on time. For Adaptive-Dpt(R) and Adaptive-Dpt(F), on CIFAR-100, we used 10% fixed subset selection and 10% adaptive subset selection. Adaptive-Dpt(R) achieved an accuracy of 60.40 ± 2.60 in 0.88 hours, while Adaptive-Dpt(F) achieved an accuracy of 65.41 ± 2.57 in 1.1 hours. This approach shows that we can use non-adaptive subset selection algorithms as regularization functions for adaptive subset selection algorithms to achieve better test accuracy. 
conclusions, future work, and impact: 
 In this work, we used a connection between one-shot NAS algorithms and adaptive subset selection to devise an algorithm that makes use of state-of-the-art techniques from both areas. Specifically, we build on state-of-the-art approaches to one-shot NAS and adaptive subset selection and pose a bi-level optimization problem on the training and validation sets. This leads us to the formulation of a combined approach, Adaptive-Dpt, as a mixed discrete and continuous bi-level optimization problem. We empirically demonstrated that the resulting algorithm is able to train on an (adaptive) dataset that is 10% of the size of the full training set, without sacrificing accuracy, resulting in an order of magnitude decrease in runtime. We also show how this method can be extended to hyperparameter optimization algorithms, in general, using Adaptive-DEHB and Adaptive-BOHB. We also release a codebase consisting of four different subset selection techniques.Future work. An interesting direction for future work is to use an adaptive subset of the data even when training the final architecture, which may lead to even faster runtime, perhaps at a small cost to performance. Another interesting direction for future work is to apply adaptive subset selection to other NAS algorithms such as regularized evolution (Real et al., 2019) or additional supernet-based algorithms (see, e.g., (Heuillet et al., 2023) ). Another interesting direction is to apply Adaptive-Dpt to a transformer-based search space such as in Section 7.4 in White et al. (2023) .Broader impact. Our work combines techniques from two different areas: adaptive subset selection for machine learning, and neural architecture search. The goal of our work is to make it easier and quicker to develop high-performing architectures on new datasets. Our work also helps to unify two sub-fields of machine learning that had thus far been disjoint. There may be even more opportunity to use tools from one sub-field to make progress in the other sub-field, and our work is the first step at bridging these subfields.Since the end product of our work is a NAS algorithm, it is not itself meant for one application but can be used in any end-application. Our hope is that future AI models discovered by our work will have a net positive impact, due to the push for the AI community to be more conscious about the societal impact of its work (Hecht et al., 2018) . 
 
 Appendix: 1. For all authors. . . In this section, we give additional results and analyses to supplement Sec. 4.First, we describe the ablation studies (which were summarized in Sec. 4.2).To explore the effect of the percentage of data used, in Figure 2 (left), we run Adaptive-Dpt with different percentages of the training data, ranging from 1% to 50%. In Figure 2 (right), we run the same experiment using the full training data in the projection step of Adaptive-Dpt. Interestingly, we see a definitive U-shape in the first experiment: the highest accuracy with Adaptive-Dpt is at 20%, achieving accuracy higher than the standard setting of 100% data. Since the supernetwork is an over-parameterized model of weights and architecture parameters, and Adaptive-Dpt regularly updates the training subset to maximize validation accuracy, Adaptive-Dpt may help prevent the supernetwork from overfitting. Furthermore, in the second experiment, we see that relatively, the accuracies are much more consistent when varying the percentage of the training set used, when the projection step is allowed to use the full training dataset. Therefore, keeping the full training dataset for the projection step leads to higher and more consistent performance, at the expense of more GPU-hours.Overall, based on the ablation studies in Figure 2 , the user may decide their desired tradeoff between performance and accuracy, and choose the subset size in the supernetwork training accordingly. For example, with a budget of 1 GPU hour, the best approach is to use a 10% subset of the training data for the supernet training and projection, but with a budget of 2.5 GPU hours, the best approach is to use a 10% subset of the training data for the supernet and the full training data for the projection.In Tab. 6, we give the results of Adaptive-Dpt with the full data for the DARTS-PT projection step for search spaces DARTS and S4. Although we were able to get better accuracy (when compared 10% data on projection step) on DARTS space, the accuracy stayed similar for S4.In Tab. 7 and Tab. 8, we give the tables to match the plots in Figure 2 . For Darts-pt-fl, we used the implementation of Facility Location as present in submodlib. This subset selection algorithm was used in the dense Euclidean setting. The algorithm is used separately for each class so as to keep the representation across classes the same as original. It was optimised using the 'NaiveGreedy' algorithm, For the experiments, 10% data was used.For Darts-pt-rand and Darts-pt-entropy, we combined Darts-pt with proxy data using two methods of subset selection techniques for dataset, one a random subset selection and other an entropy based subset selection technique (Na et al., 2021) . For random subset data was chosen randomly from the dataset. For the entropy based selection, we used the entropy files for CIFAR-10 and CIFAR-100 from Na et al. (2021) which was obtained by training a baseline network of ResNet20 and ResNet56 respectively. For ImageNet16-120, we trained a ResNet-50 model from the PyTorch model zoo.For S4 and the DARTS search space, we used the same configuration as for NAS-Bench-201. Since S4 and DARTS are non-tabular, we used a separate evaluation code for computing the performance of the selected architecture. We used the same evaluation code given in Darts-pt. The code uses a batch size of 96, learning rate of 0.025, momentum of 0.9 and weight decay of 0.025. The architecture is trained for 600 epochs. (1) zeroize (dropping the associated edge) (2)skip connection (3) 1-by-1 convolution (4) 3x3 convolution (5) 3x3 average pooling layer. Each convolution operation is a sequence of ReLU, convolution and batch normalization. The input of each node includes the sum of all the feature maps transformed using the respective edge operations. Each candidate architecture is trained using Nestorov momentum SGD using cross entropy loss for 200 epochs.A.3.2 DARTS-CNN search space. The search space is represented using cell based architectures (Liu et al., 2019) . Each cell is a DAG with feature maps as nodes and edges as operations. The operations included are 3x3 and 5x5 separable convolutions, 3x3 and 5x5 dilated separable convolutions, 3x3 max pooling, 3x3 average pooling, identity and zero. Each cell consists of 7 nodes where output node is depth-wise concatenation of all the intermediate nodes.A.3.3 DARTS S4. S1-S4 are four different search spaces proposed by Zela et al. (2020) . These search spaces were proposed to demonstrate the failure of standard DARTS. The same micro-architecture as the original DARTS paper with normal and reduction cells is used but only a subset of operators are allowed for the search spaces. The representative set of operations for S4 is {3x3 SepConv, Noise}. SepConv is chosen since it is one of the most common operation in the discovered cells reported by Liu et al. (2019) . Noise operation plugs in the noise values 𝜖 ∼ 𝑁 (0, 1) for every value from the input feature map.In this section, we give more details for GLISTER and the baselines used in Sec. 4.A.4.1 Details of GLISTER. The optimization that we are trying to solve for GLISTER, equation ( 4), can be written asEQUATIONwhere 𝐺 𝜃 𝑡 (𝑆) is Equation ( 5). Since equation ( 11) is an instance of submodular optimization (as proven in Theorem 1 of Killamsetty et al. (2020) ), it can be regularized using another function such as supervised facility location. The regularized objective can be written asEQUATION)where 𝜆 is a trade-off parameter. GreedyDSS refers to the set of greedy algorithms and approximations that solves Equation ( 12). Greedy Taylor Approximation algorithm (GreedyTaylorApprox(U, V, 𝜃 0 , 𝜂, k, r, 𝜆, R), described as Algorithm 2 in where 𝑉 is the ground set. If the ground set of items are assumed clustered, an alternative clustered implementation of facility location is computed over the clusters as where norm() is a normalizer such that the probability terms add to 1. 𝑊 {1,2,3} are selected such that the tail end entropy data are likely to be selected over the middle entropy data points.In Na et al. (2021) , 𝑃 1 (𝑥) was the highest performer. We have used 𝑃 1 (𝑥) in our experiments.A.4.4 Details of Grad-Match. In Killamsetty et al. (2021) , it is proved that the convergence bounds of adaptive subset selection algorithms critically depends on an additive error term that depends on how well the subset's gradients match the full training/validation gradient. The Error term E is defined as: w ∈ R 𝑘 represents the weight coefficient attached to each point in the coreset. Essentially, the formulation selects a subset whose weighted sum of gradients match the average training gradient.In Table 11 , we give performance of DARTS-PT + Grad-Match on NAS-Bench-201.A.5 Adaptive-DEHB and Adaptive-BOHB Adaptive-DEHB. Differential evolution hyperband (DEHB) (Awad et al., 2021 ) is a leading algorithm for mutli-fidelity optimization which has been applied to both hyperparameter optimization (HPO) and NAS. The approach combines differential evolution (Storn and Price, 1997) , a populationbased evolutionary algorithm, with hyperband (Li et al., 2018) , a bandit-based multi-fidelity optimization routine which rules out poor hyperparameter settings before they are trained for too long. Unlike DARTS-based approaches, DEHB does not use a supernetwork -each architecture is trained separately. Therefore, to devise Adaptive-DEHB, we incorporate adaptive subset selection simply by running Glister for each individual architecture trained throughout the algorithm.AutoML 2024© 2024 the authors, released under CC BY 4.0 


Decision: This paper is a follow-up of earlier work presented at the AutoML workshop 2022. The extension is quite considerable and well executed. The reviewers acknowledge the good fit to the conference. It's a clear case in my opinion, the paper should be accepted to the main track. I thank reviewers and authors for their constructive discussions.

Reviews: review: paper_summary: paper_summary: This paper introduces a novel approach to Neural Architecture Search (NAS) by integrating adaptive subset selection, significantly reducing the computational cost of finding high-performing architectures without sacrificing accuracy. The key contributions include the development of Adaptive-Dpt, the first NAS algorithm employing adaptive subset selection, and the extension of this concept to enhance hyperparameter optimization algorithms, resulting in Adaptive-BOHB and Adaptive-DEHB. These methods demonstrate substantial runtime reductions across multiple datasets and search spaces while maintaining or improving accuracy. Furthermore, the paper promotes research reproducibility by releasing all experimental codes and introduces a comprehensive codebase that integrates various subset selection algorithms into one-shot NAS. The work opens up new directions for future research in NAS and presents broader implications for the development of efficient architecture search methods.
main_review: main_review: Strength:
* The paper's core strength lies in its novel integration of adaptive subset selection with Neural Architecture Search (NAS), tackling the critical issue of computational efficiency. 
* The paper did extensive experiments across multiple datasets, providing a robust evaluation of the effectiveness.

Weakness:
* The paper's main baseline is DARTS. It's better to include other NAS algorithms to make the baseline more comprehensive.
review_summary: review_summary: This paper presents an innovative approach by integrating adaptive subset selection into Neural Architecture Search (NAS), addressing the crucial issue of computational efficiency in AutoML. Its strength lies in the comprehensive experimental validation across multiple datasets, showcasing the method's effectiveness. However, the study's reliance on DARTS as the primary baseline limits the breadth of its comparative analysis. Including a wider array of NAS algorithms could enhance the evaluation, offering a clearer perspective on the proposed method's relative performance. Expanding the comparison would underscore the innovation and efficiency of the approach, solidifying its contributions to the NAS and AutoML fields.
paper_summary: paper_summary: This paper introduces an adaptive subset selection approach to neural architecture search (NAS), which significantly reduces the computational cost of leading NAS algorithms, including DARTS-PT, BOHB, and DEHB, while maintaining or even improving their performance.
main_review: main_review: # Strengths:
- Paper is well-written and addresses important research questions. 
# Weaknesses:
- The novelty of the paper is under question. 
    - Prasad, V., White, C., Jain, P., Nayak, S., Iyer, R. K., & Ramakrishnan, G. (2022, May). Speeding up NAS with Adaptive Subset Selection. In First Conference on Automated Machine Learning (Late-Breaking Workshop).
- Results are limited to CNN models. I would like to see if (and how) the proposed method could be extended to transformers.
- Compare the results of the proposed method with:
    - (Table 5) Jain, Eeshaan, et al. "Efficient Data Subset Selection to Generalize Training Across Models: Transductive and Inductive Networks." Advances in Neural Information Processing Systems 36 (2024).
review_summary: review_summary: The paper would strongly benefit from extending results to 
- transformers,
- evaluating memory and bandwidth usage of GPU, and 
- comparison with SoTA methods published in 2023 and 2024.
paper_summary: paper_summary: This paper combines subset selection of training datasets with both ero-shot NAS and black box algorithms for more efficient architecture search.
main_review: main_review: The combination of subset selection and NAS is very relevant in my opinion. The paper shows nicely how much faster NAS can be done with subset selection compared to using the full training set, whether using DARTS-PT or black box optimizers. Overall, I think it's a good paper with an important contribution even if the combination of two existing approaches is relatively "simple". I recommend accepting it.

Nevertheless, I have a few comments:
- I don't think it's correct to say that Adaptive-DPT has "the highest performance across all search spaces" (l. 231) - it's not true in Table 4 and generally there's often a tie. That is perfectly fine since performance improvements in terms of test accuracy are not the target of the paper anyway, so this sentence feels like an unnecessary overclaim.
- Do you have an intuition why on all search spaces but NAS-Bench 201 ImageNet, the random and entropy variants have DARTS-PT within their standard deviation? That seems incredibly good for this sort of sampling, does that mean we need to evaluate such methods on harder datasets?
review_summary: review_summary: A good paper providing big compute time savings for NAS with surprisingly well-performing random baselines. Should be accepted in my opinion.
paper_summary: paper_summary: This paper introduces an algorithm (Adaptive-DPT) that combines one-shot NAS with an adaptive subset selection algorithm to reduce the overall runtime of the NAS process. Empirical evaluations on the NAS-Bench-201 benchmark show that Adaptive-DPT runs on subsets as small as 10% of the original training set, achieving an order of magnitude speed-ups compared to training on the full dataset while maintaining test set accuracy.
main_review: main_review: Pros:
- The main idea of combining one-shot NAS and adaptive subset selection is sound.
- The proposed method achieves good results (large reduction in runtime, almost no loss of accuracy) on the NAS-Bench-201 benchmark against a leading one-shot NAS method.
- The proposed method is also benchmarked against several other subset selection algorithms (such as random sampling or facility location) and does fairly well. 

Cons:
- In contrast to the one-shot evaluation, the empirical evaluations of the proposed method in combination with BOHB and DEHB are very limited, as it is just one dataset (MNIST) with just a single search space. This is not enough to support the claims from the abstract in this regard. 
- Several important parts of the paper miss an in-depth explanation and instead refer the reader to the appendix, which hinders coherency.
review_summary: review_summary: In summary, the method presented in this paper and most of the results are sound, but it is missing some clarity in its presentation.