Neural Architecture Search by Learning a Hierarchical Search Space

We thank the reviewer for their insightful review. We did our best to answer in a meaningful and honest way to all comments and misunderstandings. We believe that because of reviewer's comments, the new version of the manuscript is in a much better shape and hope the reviewer would give us a chance to read and discuss our answers and revise their score.

In parts 1 and 2 we address the weaknesses of the paper and will answer the questions shortly.

Novelty and Significance

this work improves previous works (Wang et al., 2021a; Zhao et al., 2021b) by replacing the model accuracy with the output vector. While the output vector provides more information for clustering architectures, the novelty is limited.

We would like to clarify some points about the comparison of our work with Wang et al., 2021a and Zhao et al. 2021b. In the related work of the main paper, we did not explain explicitly the differences between our paper and those two “similar” works. The most relevant difference is that in our work, we aim at training a deep learning model (in particular a CNN), while jointly learning its best architecture. This is quite a challenging task, because it requires using an algorithm for finding promising architectures that should work online and with partially trained models.

Therefore, the estimations of the architecture likelihoods are extremely noisy. Additionally, If the model samples the wrong configuration, this would influence the rest of the training and lead to worse results. In this setting, it is of paramount importance to quickly find promising architectures, as this will avoid sampling bad architectures which will negatively impact the training and potentially without any possibility of back-tracking.

In contrast, the two papers mentioned above tackle the easier problem of finding the best architectures with a reduced set of samples, assuming that the recognition model is given, either with a supernet trained uniformly with all architectures (for Wang et al. 2021a), which we show does not perform well on our benchmarks, or by precomputed models as in BenchNAS-201 (for Zhao at al. 2021b). The only paper that does a joint training of the model and finds the most promising architecture with MCTS is Su et al., 2021a, and that’s the reason we compare directly and thoroughly with it, showing the advantages of our approach.

Furthermore, the results only slightly outperform previous works (Su et al., 2021a; You et al. 2020; …), which is insignificant.

Our CIFAR and ImageNet tests show either better accuracy or lower computational cost or both compared to other methods. While the gains may seem small, the distribution of architecture performances for CIFAR10 benchmarks is narrow with many architectures performing well (e.g. for distribution of architectures in NAS-Bench-Macro see figure 7.c in [Su et al., 2021a]). In this sense, it is impossible to significantly improve the performance of the best final architecture numerically even if we find the best architecture benchmark. For example in table 4, while the best accuracy for our method is numerically close to MCTS + Reg, we are able to find the best architecture in the benchmark and our method consistently shows higher performance when considering the average accuracy and ranking.

In addition, making early tree nodes more discriminative is highly relevant to the partitioning or splitting problems in decision tree learning, which has been studied by many in the past

We believe that also this point is due to the previous misunderstanding. For methods in which the estimation of the probabilities of each architecture is accurate, using a discriminative approach makes sense. Here, however, at the beginning of the training the estimation of the quality of each architecture is noisy, as the model has not been fully trained on that. Thus, directly using that to drive the sampling would lead to poor results (for instance the results of the uniformly sampled model). In contrast, a method that only considers the similarity of architecture outputs is not affected by the specific quality of the model. It considers only the semantic similarity among architectures on the output space and can lead to better performance. We are currently running experiments to show empirically that and will update the answer with results when available.

Presentation and Proposed Method

Second, the presentation has a lot of improvements, especially the approach. The proposed method is ambiguous and does not seem like MCTS. MCTS uses UCT to select child modes; however, the proposed method uses Boltzmann sampling with a UCB-like score as the parameter.

The reviewer is correct that our method is not the typical MCTS as it skips the expansion stage. However, we followed the naming of previous works, such as [Su et al., 2021a, Wang et al., 2021a], that do not include the expansion stage due to the fact that the connection of nodes in the hierarchy is static and known prior. In addition, we introduce stochasticity with Boltzmann sampling, to allow a faster exploration of different configurations, to not bias the model to similar configurations multiple times.

Thus, overall, we agree with the reviewer that there are quite some differences from the commonly used MCTS. However in our opinion the spirit of MCTS is maintained, and the name could help readers to situate the paper. We are open to changing the naming if reviewer think that this could improve the quality and readability of the paper.

Most importantly, using Acc(a_i)/n_i in Eq. 4 is weird....

Thank you very much for pointing this out. We apologize for the typo. We corrected it and double checked the other equations.

We thank the reviewer and appreciate their insightful comments and suggestions. Below, we address the concerns and questions raised:

Weaknesses

The abstract may benefit from significant revision. Currently, it primarily highlights MCTS fundamentals and suggests general applicability, but the paper is focused on a NAS-specific task that utilizes MCTS and related techniques to enhance NAS performance. The abstract and introduction appear inconsistent in conveying the core contribution and scope.

We refined the abstract to clarify the goal and the scope of the paper and make it more consistent with the rest of the paper. While the paper focuses on the specific application of NAS, the learning meaningful ordering of data is general and beneficial in many domains where training data is sequential but the order of which the data is sampled vary.

The rationale behind using model output distances to construct the tree structure and improve NAS is not clearly discussed, and the method itself lacks detail. This part should be the core of the paper, yet there is minimal explanation in the main text.

While the ultimate objective of NAS is to find the model with the highest accuracy, when naively using the supernet, the accuracy of architectures can have low correlation with ground truth accuracy. This makes it an unreliable metric for tree construction. The output vector on the other hand is a more informative summary metric for an architecture than the accuracy, as it defines a semantic relationship between architectures that is independent from the actual accuracy of the model. The key idea is to build a hierarchy in which distances between architectures have semantic meaning in the class space. This is also reflected in the fact that using encodings (table 3) shows better results than using uniform sampling. We added more details to section 4.(Tree Design) about tree design.

While resource constraints may be a factor, it remains unclear whether the method scales well for large networks, which are particularly relevant in NAS applications. The experiments mainly validate that the learned tree provides slight improvements but do not assess scalability in larger search spaces.

It is true that using our method in the current form works best in smaller search spaces. However, there are possible ways to deal with larger search spaces, such as using FLOPs as a training-free proxy that we used for ImageNet (similar to [Su et al., 2021a]) or using other zero-cost proxies [Abdelfattah et al, 2021] to prune the search space. Our results on ImageNet shows that our method can still be feasible in larger search spaces with these techniques. To add more clarity to the paper, we included this limitation to the conclusion.

minor comment: Line 306: check around "Fig.3.4(a)"

Corrected.

Questions

How does this method compare with other state-of-the-art NAS techniques, such as those in the Neural Architecture Transfer (NAT) series?

In general, although both NAS and NAT aim to automate the design of neural architecture, they have different approaches and goals. NAS focuses on discovering novel architectures for a task from scratch, while NAT focuses on adapting a pre-trained architecture to a new task and leveraging the knowledge for more efficiency. This makes direct comparison of them difficult.

The motivation of the work was not to outperform the state-of-the-art, rather to provide a new understanding of NAS sampling approaches and highlight the advantages of hierarchical search spaces for NAS and propose solutions to challenges in their design, showing good performance in a limited amount of time/computation. In this sense, we have included the methods that are highly relevant to ours in our comparisons.

What insights or theoretical basis underlie the decision to use model output distances for improving NAS performance? (I already assume this will be addressed in a revision in my score.)

Addressed above in weaknesses.

references

[Abdelfattah et al, 2021]: Zero-Cost Proxies for Lightweight NAS, ICLR 2022.

We thank the reviewer for their valuable comments and suggestions. We are thrilled that the reviewer found our work well written and promising. We address the concerns and questions below:

Weaknesses

The method still requires initial supernet training using uniform sampling before being able to build the tree, which is known to be computationally heavy

While it is true that our method requires pre-training the supernet to construct the tree, full training is not required. In Figure 3 we show that training until convergence is not required to get the best results and training for 1/2 of iterations outperforms MCTS+reg and 2/3 of iterations already achieves the same result as full training (Figure 2 (left)). Furthermore, even with the pre-training we obtain a lower search time than several other methods (e.g. Table 5 for ImageNet) .

We tested several potential ways to build the tree without supernet pre-training in our “ablation-alternative branching” by using untrained supernet, and various encodings to calculate distances for clustering. While they don’t perform as well as using supernet outputs, using weighted encodings still outperform uniform, Boltzmann and vanilla MCTS (comparing table 3 with table 1). Finding better ways to reduce the computational cost of building the tree, while obtaining a high performance will be explored in future work.

The overall contribution seems incremental, as it is mainly a new way to construct a Monte-Carlo tree for supernet sampling

We believe that our contribution is not incremental because:

We are the first to learn the tree structure for Monte-Carlo sampling during the joint training of the sampling probabilities (to focus the training on the best configuration) and the recognition model (a deep convolutional neural network). Previous methods were learning the tree structure (Wang et al. 2021a, Zhao at al. 2021b) while assuming the recognition model given (either a supernet pre-trained uniformly or models precomputed in BenchNAS-201 ). The only method that learns both recognition model and tree probabilities is Su et al., 2021a, which does not learn the tree structure.

Learning the structure of the tree in such a joint learning is quite challenging because, in the beginning of the training all estimations are extremely noisy and using directly the model accuracy to separate the search space would not work. Instead, using a hierarchical clustering on the output representation just measures the similarity of different architectures and works well even in such challenging settings. We added a paragraph in section 5.2 (Tree partitioning with accuracy) that shows that accuracy is not a good metric for building the tree structure when the recognition model is poor.

These two contributions are quite new, and can foster research in this challenging but very useful setting. We are aware that we did not explain those points clearly enough in the original version paper, but we believe they are important and should be considered by reviewers.

For the experiment on the pooling dataset... Given that the proposed method discriminates architectures by comparing the outputs after supernet pre-training, I wonder how the method is able to find a more efficient representation of the tree if the weights themselves are not optimal.

In general, weight sharing (used in popular one-shot NAS methods such as DARTS and its variants), while very efficient, can have a negative effect on the outcome of the NAS, due to interference among architectures. In this particular benchmark, the weight sharing is full (all architectures always share 100% of weights). To tackle this, [Javan et al., 2023] uses multiple supernets to reduce the weight sharing from the start; instead, our method also reduces the weight sharing, but gradually with a single model. By being able to focus on high performing architectures, the weights will be effectively only shared by smaller and smaller numbers of architectures.

Even if the supernet has poor correlation with the optimal architecture due to the full weight sharing, the supernet is still used only to cluster similar architectures and not to rank those architectures. This is the very reason why methods based directly on the accuracy of the supernet would not work as well as ours. To show this empirically, we ran a basic experiment to recursively partition search space based on accuracy. More specifically to design the binary tree by halving the search space into “good” and “bad” regions and performing the search. The results we obtained (best 90.85, avg. 90.49) is significantly diminished compared to our method.