LayerNAS: Neural Architecture Search in Polynomial Complexity

With the surge of ever-growing neural models used across all ML-based disciplines, the efficiency of neural networks is becoming a fundamental factor in their success and applicability. A carefully crafted architecture can achieve good quality while maintaining efficiency during inference. However, designing optimized architectures is a complex and time-consuming process – this is especially true when multiple objectives are involved, including the model’s performance and one or more cost factors reflecting the model’s size, Multiply-Adds (MAdds) and inference latency. Neural Architecture Search (NAS), is a highly effective paradigm for dealing with such complexities. NAS automates the task and discovers more intricate and complex architectures than those that can be found by humans. Additionally, recent literature shows that NAS allows to search for optimal models under specific constraints (e.g., latency), with remarkable applications on architectures such as MobileNetV3  (Howard et al., 2019), EfficientNet  (Tan & Le, 2019) and FBNet  (Wu et al., 2019).

Most NAS algorithms encode model architectures using a list of integers, where each integer represents a selected search option for the corresponding layer. In particular, notice that for a given model with $L$ layers, where each layer is selected from a set of search options $\mathbb{S}$, the search space contains $O(|\mathbb{S}|^{L})$ candidates with different architectures. This exponential complexity presents a significant efficiency challenge for NAS algorithms.

In this paper, we present LayerNAS, an algorithm that addresses the problem of Neural Architecture Search (NAS) through the framework of combinatorial optimization. The proposed approach decouples the constraints of the model and the evaluation of its quality, and explores the factorized search space more effectively in a layerwise manner, reducing the search complexity from exponential to polynomial.

LayerNAS operates on search spaces that satisfy the following assumption: optimal models when searching for $layer_{i}$ can be constructed from one of the models in $layer_{i-1}$. Based on this assumption, LayerNAS enforces a directional search process from the first layer to the last layer. The directional layerwise search makes the search complexity $O(C\cdot|\mathbb{S}|\cdot L$), where $C$ is the number of candidates to search per layer. Although this complexity is polynomial, $C=O(|\mathbb{S}|^{L})$ is exponential in the last layer, unless we keep only a limited number of candidates.

For multi-objective NAS problems, LayerNAS treats model constraints and model quality as separate metrics. Rather than utilizing a single objective function that combines multi-objectives, LayerNAS stores model candidates by their constraint metric value. Let $\mathcal{M}_{i,h}$ be the best model candidate for $layer_{i}$ with $\textrm{cost}=h$. LayerNAS searches for optimal models under different constraints in the next layer by adding the cost of the selected search option for next layer to the current layer, i.e., $\mathcal{M}_{i,h}$. This transforms the problem into the following combinatorial optimization problem: for a model with $L$ layers, what is the optimal combination of options for all layers needed to achieve the best quality under the cost constraint? If we bucketize the potential model candidates by their cost, the search space is limited to $O(H\cdot|\mathbb{S}|\cdot L)$, where $H$ is number of buckets per layer. In practice, capping the search at 100 buckets achieves reasonable performance. Since this holds $H$ constant, it makes the search complexity polynomial.

Our contributions can be summarized as follows:

• •

  We propose LayerNAS, an algorithm that transforms the multi-objective NAS problem to a Combinatorial Optimization problem. This is a novel formulation of NAS.

• •

  LayerNAS is directly designed to tackle the search complexity of NAS, and reduce the search complexity from $O(|\mathbb{S}|^{L})$ to $O(H\cdot|\mathbb{S}|\cdot L)$, where $H$ is a constant defined in the algorithm.

• •

  We demonstrate the effectiveness of LayerNAS by identifying high-performing model architectures under various Multiply-Adds (MAdds) constraints, by searching through search spaces derived from MobileNetV2 (Sandler et al., 2018) and MobileNetV3 (Howard et al., 2019).

The survey by (Elsken et al., 2019) categorizes methods for Neural Architecture Search into three dimensions: search space, search strategy, and performance estimation strategy. The formulation of NAS as different problems has led to the development of a diverse array of search algorithms. Bayesian Optimization is first adopted for hyper-parameter tuning (Bergstra et al., 2013; Domhan et al., 2015; Falkner et al., 2018; Kandasamy et al., 2018). Reinforcement Learning is utilized for training an agent to interact with a search space (Zoph & Le, 2017; Pham et al., 2018; Zoph et al., 2018; Jaafra et al., 2019). Evolutionary algorithms (Liu et al., 2021; Real et al., 2019) have been employed by encoding model architectures to DNA and evolving the candidate pool. ProgressiveNAS (Liu et al., 2018a) uses heuristic search to gradually build models by starting from simple and shallow model architectures and incrementally adding more operations to arrive at deep and complex final architectures. This is in contrast to LayerNAS, which iterates over changes in the layers of a full complex model.

Recent advancements in mobile image models, such as MobileNetV3 (Howard et al., 2019), EfficientNet (Tan & Le, 2019), FBNet (Wu et al., 2019), are optimized by NAS. The search for these models is often constrained by metrics such as FLOPs, model size, latency, and others. To solve this multi-objective problem, most NAS algorithms (Tan et al., 2019; Cai et al., 2018) design an objective function that combines these metrics into a single objective. LEMONADE (Elsken et al., 2018) proposes a method to split two metrics, and searches for a Pareto front of a family of models. Once-for-All (Cai et al., 2020) proposes progressive shrinking algorithm to efficiently find optimal model architectures under different constraints.

Larger models tend to have better performance compared to smaller models. However, the increased size of models also means increased computational resource requirement. As a result, the optimization of neural architectures within constrained resources is an important and meaningful aspect of NAS problems, which can be solved as multi-objective optimization (Hsu et al., 2018). There is increasing interest in treating NAS as a compression problem (Zhou et al., 2019; Yu & Huang, 2019) from an over-sized model. These works indicate that compressing with different configurations on each layer leads to a model better than uniform compression. Here, NAS can be used to search for optimal configurations (He et al., 2018; Liu et al., 2019; Wang et al., 2019).

The applicability of NAS is significantly influenced by the efficiency of its search process. One-shot algorithms (Liu et al., 2018b; Cai et al., 2018; Bender et al., 2018, 2020) provide a novel approach by constructing a supernet from the search space to perform more efficient NAS. However, this approach has limit on number of branches in supernet due to the constraints of supernet size. The search cost is not only bounded by the complexity of search space, but also the cost of training under ”train-and-eval” paradigm. Training-free NAS (Mellor et al., 2021; Chen et al., 2021; Zhu et al., 2022; Shu et al., 2021) breaks this paradigm by estimating the model quality with other metrics that are fast to compute. However, the search quality heavily relies on the effectiveness of the metrics.

Most NAS algorithms do not differentiate the various types of NAS problems. Rather, they employ a single encoding of the search space with a general solution for the search process. However, the unique characteristics of NAS problems can be leveraged to design a tailored approach. We categorize NAS problems into three major types:

• •

  Topology search: the search space defines a graph with multiple nodes. The objective is to identify an optimal topology for connecting nodes with different operations. This task allows for the exploration of novel architectures that could not be found through other methods.

• •

  Size search or compression search: the search occurs on a predefined model architecture with multiple layers. Each layer can be selected from as a set of search options. Empirically, the best-performing model is normally the one with the most parameters per layer. Therefore, in practice, we aim to search for the optimal model under certain constraints. NATSBench size search (Dong et al., 2021) provides a public dataset for this type of task. MobilNetV3 (Howard et al., 2019), EfficientNet (Tan & Le, 2019), FBNet (Wu et al., 2019) also establish the search space in this manner. This problem can also be viewed as a compression problem (He et al., 2018), as reducing the layer size serves as a means of compression by decreasing the model size, FLOPs and latency.

• •

  Scale search: model architectures are uniformly configured by hyper-parameters, such as altering number of layers or the size of fully-connected layers. This task views the model as a holistic entity and uniformly scales it up or down, rather than adjusting individual layers or components.

This taxonomy illustrates the significant variation among NAS problems. Rather than proposing a general solution to address all of them, we propose to tackle each problem with specific approaches. We will delve into more details in Section 4 and Section 5

In this work, we construct the search space in a layerwise manner. Specifically, we aim to find a model with $L$ layers. For each $layer_{i}$, we select from a set of search options $\mathbb{S}_{i}$. A model candidate $\mathcal{M}$ can be represented as a tuple with size $L$: $(s_{1},s_{2},...,s_{L})$. $s_{i}\in\mathbb{S}_{i}$ is a selected search option on $layer_{i}$. The objective is to find an optimal model architecture $\mathcal{M}=(s_{1},s_{2},...,s_{L})$ with the highest accuracy:

We propose LayerNAS as an algorithm that leverages layerwise attributes. When searching models $\mathcal{M}_{i}$ on $layer_{i}$, we are searching for architectures in the form of $(s_{1..i-1},x_{i},o_{i+1..L})$. $s_{1..i-1}$ are the selected options for $layer_{1..i-1}$, and $o_{i+1..L}$ are the default, predefined options. $x_{i}$ is the search option selected for $layer_{i}$, which is the current layer in the search. In this formulation, only $layer_{i}$ can be changed, all preceding layers are fixed, and all succeeding layers are using the default option. In topology search, the default option is usually no-op; in size search, the default option can be the option with most computation.

LayerNAS operates on a search space that meets the following assumption, which has been implicitly utilized by past chain-structured NAS techniques (Liu et al., 2018a; Tan et al., 2019; Howard et al., 2019).

This assumption implies:

• •

  Enforcing a sequential search process is possible when exploring $layer_{i}$ because improvements to the model cannot be achieved by modifying $layer_{i-1}$. We delve deeper into the sequential nature of the search process and examine the underlying reasons in Section E.2.

• •

  The information for finding an optimal model architecture on $layer_{i}$ was collected when searching for model architectures on $layer_{i-1}$.

• •

  Search spaces that are constructed in a layerwise manner, such as those in size search problems discussed in Section 3, can usually meet this assumption. Each search option can completely define how to construct a succeeding layer, and does not depend on the search options in previous layers.

• •

  It’s worth noting that not all search spaces can meet the assumption. Succeeding layers may be coupled with or affect preceding layers in some cases. In practice, we transform the search space in Section 5 to ensure that it meets the assumption. In Section E.3, the limit of the assumption is further discussed.

In this research, we propose LayerNAS that formulates Multi-objective Neural Architecture Search to Combinatorial Optimization. By decoupling multi-objectives into cost and accuracy, and leverages layerwise attributes, we are able to reduce the search complexity from $O(|\mathbb{S}|^{L})$ to $O(H\cdot|\mathbb{S}|\cdot L)$.

Our experiment results demonstrate the effectiveness of LayerNAS in discovering models that achieve superior performance compared to both baseline models and models discovered by other NAS algorithms under various constraints of MAdds. Specifically, models discovered through LayerNAS achieve top-1 accuracy on ImageNet of 69% for 61M MAdds, 75.6% for 229M MAdds, 77.1% for 322M MAdds, 78.6% for 627M MAdds. Furthermore, our analysis reveals that LayerNAS outperforms other NAS algorithms on NATS-Bench in all aspects including best model quality, stability and efficiency.

We hope this work motivates additional efforts to better utilize a priori information and design NAS algorithms tailored to different types of NAS problems.

While the current implementation of LayerNAS has shown promising results, several current limitations that can be addressed by future work:

• •

  LayerNAS is not designed to solve scale search problems mentioned in Section 3, because many hyper-parameters of model architecture are interdependent in scale search problem, which contradicts the statement in 4.1.

• •

  One-shot NAS algorithms have been shown to be more efficient. We aim to investigate the potential of applying LayerNAS to One-shot NAS algorithms.