Transferable Relativistic Predictor: Mitigating Cross-Task Cold-Start Issue in NAS

1 Introduction

Neural architecture search (NAS) [Elsken et al., 2019] has successfully emerged in automatically constructing network architectures for various tasks, including image classification [Huang et al., 2024], objective detection [Wang et al., 2020] and semantic segmentation [Zhang et al., 2021a]. Typical NAS frameworks find the best architecture in a vast search space based on a predefined performance metric (e.g., accuracy [Shen et al., 2023]), where training and evaluating candidate architectures requires substantial computational resources, limiting NAS applications in real-world scenarios [Huang et al., 2024]. To alleviate this issue, various methods are developed to reduce the overheads of architecture evaluations, such as predictor [Wen et al., 2020], parameter sharing

∗Corresponding author.

[Shen et al., 2023], and zero-shot metric [Mellor et al., 2021].

Many predictor-based NAS methods sample a set of evaluated architectures to train an accuracy predictor[Ma et al., 2024], aiming to learn the mapping relationship between architecture encodings and their corresponding absolute performance [Wen et al., 2020]. However, these predictors often face ranking issue caused by prediction biases, i.e., architectures with similar performance may be inaccurately ranked during the architecture search process, leading to suboptimal performance [Huang et al., 2022].

Recently, relativistic predictor focuses on comparing the relativistic performance of paired architectures rather than predicting their absolute performances, effectively mitigating the ranking issue [Huang et al., 2022; Xu et al., 2021]. However, such predictors still face cold-start issue: When applied to new datasets, the effective relativistic predictor needs to be trained from scratch by a large number of evaluated architectures for constructing the relativistic dataset, which remains a computationally expensive process [Zhao et al., 2023].

Typical relativistic predictors use accuracy to label architectural superior-inferior relationship. This paper exploits transferable relativistic label from the cheaper-toobtain performance estimation (i.e., zero-shot metric), which can roughly label the relativistic superiority or inferiority between architecture pairs on a proxy dataset for pretraining relativistic predictor. Learning to fit transferable relativistic label may encourage predictor to extract better ranking ability in advance, thereby facilitating a warm start on new datasets. In other words, a pretrained predictor with good ranking ability requires only a small number of evaluated architectures to achieve excellent predictive results on the new datasets. A straightforward approach is to pretrain the predictor by utilizing relativistic label of a single zero-shot metric on the proxy dataset and then finetune it on a small number of evaluated architectures from the new dataset. Table 1 presents preliminary experiments, yielding following observations.

1) Transferable relativistic label can significantly enhance ranking performance. For example, using NWOT [Mellor et al., 2021] increases Kendall's Tau by 0.3811 and 0.5062 on Ninapro and SCIFAR100, respectively.

2) Inappropriate use of transferable relativistic label may degrade ranking performance. For instance, using JACOV [Mellor et al., 2021] decreases Kendall's Tau by 0.01 and 0.0053 on ImageNet16-120 and Ninapro, respectively.

1. Different datasets exhibit varied preferences for transferable relativistic label. For example, SYNFLOW [Tanaka et al., 2020] reduces Kendall's Tau on SCIFAR100 but enhances predictions on other datasets.
2. Relativistic label is generally positively transferable across most datasets. For instance, NWOT, SYNFLOW, SNIP [Lee et al., 2018], and JACOV show positive transferability in 5, 5, 6, and 4 datasets, respectively.

Preliminary experiments demonstrate that transferable relativistic label improves ranking ability with limited evaluated architectures. This indicates that transferable relativistic label can effectively mitigate the cold-start issue. However, such a naive approach, which highly relies on selection of which single zero-shot metric, fails to fully exploit complementary knowledge from different zero-shot metrics. Therefore, integrating multiple metrics can better mitigate cold-start issue.

Accordingly, this paper proposes a transferable relativistic predictor (TRP). The proposed predictor comprises two steps. During the pretraining stage, we employ the proposed loss function, characterized by its smoothness and ease of optimization, to improve ranking ability on the relativistic dataset, which is softly labeled using multiple zero-shot metrics. During the finetuning stage, we approximate the ranking correlation function of TRP using Chebyshev interpolation. A point where the marginal benefit is less than a certain threshold value indicates the number of evaluated architectures required to finetune TRP on the target dataset. This method can adaptively determine the number of evaluated architectures. The contributions can be summarized as follows.

1. We propose a transferable relativistic predictor (TRP), which can effectively mitigate the cold-start issue by full use of the transferable relativistic label from multiple zero-shot metrics.
2. We provide theoretical analyses of the designed loss function from Bayes consistency and risk minimization, demonstrating its advantages in obtaining better ranking representation.
3. We run extensive experiments. Specifically, the number of evaluated architectures needed by TRP is fewer than that of most existing predictors. TRP can achieve good results in NAS-Bench-201, TransferNAS-Bench101-Micro, TransferNAS-Bench101-Macro, and DARTS search spaces.

2 RelatedWorks

Zero-shot metrics. These metrics eliminate the need for architecture training and can quickly quantify the performance of architectures by the theoretical-based and empirical-based methods [Chen et al., 2024]. Typically, such metrics require less than one second for architectural evaluation [Chen et al., 2021a]. In addition, numerous studies [Krishnakumar et al., 2022; Chen et al., 2024; Li et al., 2024] have observed that some training-free metrics (e.g., NWOT [Mellor et al., 2021] and FLOPS [Ning et al., 2021]) obtain better ranking correlations on different datasets with the same search space. However, there is no zero-shot metric that achieves good ranking quality in all search spaces, and the optimal zero-shot metric varies from search space [Ning et al., 2021].

Predictor-based NAS. The accuracy predictor has achieved remarkable success in performance evaluation, but expensive evaluated architectures still limit the development. Early works have attempted to fully exploit the limited evaluated architectures to improve accuracy predictor performance from the perspective of operation hierarchy [Chen et al., 2021c], spatial topology information [Lu et al., 2021a], and information flow [Ning et al., 2020], respectively. In addition, some works convert learning methods from supervised learning to semi-supervised learning [Luo et al., 2020; Liu et al., 2021] and self-supervised learning [Ji et al., 2024; Wei et al., 2021; Zheng et al., 2024], alleviating the need for evaluated architectures. However, the accuracy predictor with poor ranking correlation between ground-truth performance and the predicted performance can mislead the search algorithm leading to the selection of a low-ranking architecture.

To tackle this, the relativistic predictor is designed to learn the relativistic ranking of architectures rather than their absolute performances [Huang et al., 2022; Hu et al., 2021; Guo et al., 2024; Chen et al., 2021b]. Among these, NARQ2T [Guo et al., 2024] acquires knowledge of the performance distributions within the search space, facilitating the generalization of its ranking ability across datasets. ArchGraph [Huang et al., 2022] generalizes task embedding to predict relativistic relation between architecture pairs. Although NARQ2T and Arch-Graph achieve cross-dataset generalization, they still demand substantial evaluated architectures during training. In addition, these works use the hinge function, which is non-smooth and difficult to optimize/learn the relativistic relationship between architecture pairs, leading to poor ranking ability.

Zero-shot metrics in predictor-based NAS. Recent studies have attempted to exploit zero-shot metrics for achieving better search efficiency. For example, the work [White et al., 2021b] finds that certain zero-shot metrics can improve the predictive power of the accuracy predictor. ProxyBO [Shen et al., 2023] proposes to combine the architecture ranking given by the accuracy predictor and zero-shot metrics in the search process. AceNAS [Zhang et al., 2021b] pretrains the accuracy predictor based no FLOPS and #PARAMS. DELE [Zhao et al., 2023] dynamically integrates zero-shot metrics for pretraining accuracy predictor. However, such predictors are still subject to the ranking issue.

3 Methodology

As shown in Figure 1, the overall framework of the proposed TRP method contains three parts, i.e., building soft label proxy dataset, pretraining stage on proxy dataset, and finetuing stage on target dataset.

3.1 Building Soft Label Proxy Dataset

Given a search space, two architectures Ai and Aj are randomly sampled to construct an instance In for proxy dataset DP . The encodings Ei and Ej corresponding to Ai and Aj are concatenated to form the input feature xn. Considering the imprecision of zero-shot metrics (especially when the values of the metrics for the two architectures are close [Mellor et al., 2021]), soft label yn and confidence score cn are used to measure relativistic knowledge from K zero-shot metrics at a fine-grained level. yn is a two-dimensional vector, where the first dimension y1n denotes the probability that Ai is significantly better than Aj, and the second dimension y2n denotes the probability that Aj is significantly better than Ai. We first judge whether Ai or Aj is significantly superior or inferior than the other based on Eq. (1).

where MAi and MAj are the metric values of architectures Ai and Aj, respectively. The selection of ρ is decided by experiment instead of a statistical significance test. If ρ is greater than threshold, there is a significant superior-inferior relationship between Ai and Aj. Conversely, there is no significant superior-inferior relationship. Ni, Nj, and Nij indicate the number of metrics where Ai is significantly better than Aj, Aj is significantly better than Ai, and neither is significantly better, respectively. Based on this, y1n and y2n are equal toNi/K andNj/K, respectively. For confidence score cij, the smaller Nij indicates that the annotation is more reliable. Thus, cn is equal to 1 - (Nij/K). Repeating the above process N times, we can obtain the proxy dataset DP . Due to the architecture pair with transferable relativistic label, the pretrained predictor on DP can obtain better representations.

3.2 Pretraining Stage on Proxy Dataset

For architectural pair representation, the normal ranking loss can be defined as Eq. (2) [Xu et al., 2021; Guo et al., 2024].

where ψ (.) is a hinge function with a hyperparameter α, which is usually set to 1 to control the margin (see Eq. (3)). Unfortunately, the hinge function is non-smooth and thus is difficult to optimize for better ranking ability.

where f1(xn) and f0(xn) are the predicted values of xn, respectively. Given proxy dataset DP , we develop a smooth approximation of Eq. (2) via the log-sum-exp function,

Lsrank form is, asymptotically, an upper bound of the following hinge loss form,

where

which allows the predictor to have adaptive margins α⋆ per architecture pair. It is differentiable and smooth everywhere, which makes it easier to optimize for obtaining better ranking ability. We give theoretical analysis of Lsrank in Section 4.

To enhance the architecture pair representations, we employ contrastive learning [Xiao et al., 2024] to maximize similarity among positive data while ensuring dissimilarity for negative samples, thereby aligning architecture pair representations for semantically similar data. Our approach treats different instances with the same soft label as positive data and instances with the different soft label as negative data. We calculate the representation similarity of two instances xi and xj , where the embeddings are obtained with an encoder z (.):

The contrastive learning requires similar data to yield a larger s (.). The contrastive loss is as follows:

where τ is a temperature hyperparameter. k+ and k- denote positive and negative data, respectively. The final loss function is the combination of Eqs. 4 and 8.

where λ1 is a hyperparameter to control the importance between two different loss functions. Therefore, the proposed loss function has a twofold effect. The first is to maximize the capture of relativistic knowledge in soft labels through a smooth and easy-to-optimize loss function (i.e., Lsrank). The second is the acquisition of more discriminative ranking representations through contrastive loss (i.e., Lcont).

3.3 Finetuing Stage on Target Dataset

After pretraining stage, finetuning is required to transfer the pretrained predictor to the target task. However, how to choose the appropriate number of evaluated architectures still requires trial and error. To solve the issue, we design an interpolation-based method to select the number of evaluated architectures adaptively. Specifically, we first sample a small number of evaluated architectures (Ns) from the target dataset. Interpolated data points are denoted as DI = (mi, ri), where ri refers to Kendall's Tau correlation for Ns evaluated architectures after finetuning via mi samples. Based on DI , we fit a curve of the relationship between the number of evaluated architectures and Kendall's Tau correlation by Chebyshev interpolation polynomial (i.e., Eq. (10)) [Rivlin, 2020].

The marginal benefit is the first order derivative of Eq. (10) as follows:

The optimal number of evaluated architectures is NA = min {m ∈ N | P ′ (x) ≤ ω}. The relativistic dataset DT with size 2NA(NA-1) is constructed to finetune the predictor. Unlike DP , labels in DT are based on ground-truth performances of architecture pairs. If Ai is better than Aj, y1n and y2n are 1 and 0, respectively. Otherwise, y1n and y2n are 0 and 1. Furthermore, DT is without confidence score. The following loss function is used in finetuing stage,

where λ2 is to control the importance between two different loss functions. L∗srank is version of Eq. (4) without confidence score cn.

4 Theoretical Analysis

We prove the benefit of Eq. (4) from the point of view of Bayes consistency and risk minimization. Bayes consistency is a critical attribute of loss function for achieving the right objective [Saberian and Vasconcelos, 2011]. The output of the predictor is a two-dimensional vector [fF (x), fL(x)], where fF (x) and fL(x) are the superiority and inferiority scores in architectural pairs, respectively. Based on Bayes prediction rule, we can obtain the followings:

where Y ∈ {F, L} is the label space. F and L denote the labels in architectural pairs in which the former is superior to the latter and the latter is better than the former, respectively. The outputs to the predictor need to be satisfied:

Due to ∆f(xn) = f1(xn) - f0(xn), when sign(y1n - y2n ) = 1, exp((f1(xn) - f0(xn) ∗ sign(y1n - y2n )) = exp (∆f(xn)). When sign(y1n - y2n ) = 0, exp((f1(xn) - f0(xn) ∗ sign(y1n - y2n )) = exp (-∆f(xn)). Thus, Eq. (4) = log (1+ ∑Nn=1 cn ∗ exp (±∆f(xn)))≈ ∑Nn=1 cn ∗ exp (- 1 2 ∆f (xn)).

Considering the loss of a single architecture pair, since cn as a real number cannot affect the subsequent proof, Lsrank in Eq. (4) loss is analytically equivalent to the following loss without the logarithmic,

where ∆f(x) = fF (x) - fL(x). When ∆f(x) ≫ 0, i.e., fF (x) ≫ fL(x), it indicates that score of F is significantly higher than L, and loss approaches zero. The loss function drives predictor training, making ∆f(x) increasingly larger, aligning predictor's predictions with Bayes consistency.

Proof. Consider f(x) that minimizes the risk, The total risk function of the predictor is defined as:

The conditional risk function is defined as:

Substituting the loss function, we have:

The first and second order derivatives of Eq. (18) are

Since P(Y = F | x) and P(Y = L | x) are non-negative, and the exponential function is always greater than zero, the second-order derivative is always positive, indicating that the risk function is convex and exists a global minimum solution. Making the first order derivative equal to 0 obtains the minimum value of the risk function ∆f(x) = log P(Y=F|x) P (Y =L|x) consistent with the predictor's output. f ∗ (x) implements the Bayes prediction rule in Eq. (13). Thus, we can say that using Eq. (4) achieves the right objective and extracts better architecture pair representations for predictor.

5 Experiments and Results

The experiments contain ranking capability, search results, and ablation studies. We run experiments on three closed domain search spaces and one open domain search space.

5.1 Results on NAS Benchmarks

The experiments are conducted on NAS-Bench-201 and TransNAS-Bench-101 benchmarks. Kendall's Tau is used to evaluate the predictor's ranking capability, while a query metric represents the amount of evaluated architectures required by the predictor. TRP focuses on the relative relationship between two architectures, and an additional bubble sort is necessary to determine the predicted ranking for a set of architectures, where TRP is used to decide whether to swap the rankings of two architectures. The closer Kendall's Tau value is to 1, the higher the agreement between actual accuracy ranking and predicted ranking, indicating the better ranking capability of TRP. For the query metric, we adopt experimental results from the original literature. If the predictor has not been tested on a NAS benchmark, default settings from the source code are applied. In NAS-Bench-201, the proxy dataset is constructed using zero-shot metrics on CIFAR-10 for pretraining, followed by finetuning on CIFAR-10, CIFAR-100, and ImageNet16-120. For TransNAS-Bench-101, zero-shot metrics from the objective classification task are used to construct the proxy dataset, and finetuning is performed on all datasets. The number of queries is adaptively determined using the proposed interpolation method.

The ranking results on NAS-Bench-201 are recorded in Table 2. Compared with existing pretraining-finetuning accuracy predictors (i.e., CAP, DCLP, and DELE) and relativistic predictors (Arch-Graph and ReNAS), TRP achieves the best Kendall's Tau on the three datasets with the fewest number of evaluated architectures (CIFAR-10: 30, CIFAR-100: 34 and ImageNet16-120: 41). Notably, with only 30 evaluated architectures (1/3 of Arch-Graph), Kendall's Tau of TRP achieves 0.1805 improvement on the CIFAR-10. Moreover, we report the ranking results on TransNAS-Bench-101 in Table 3. It can be observed that TRP obtains state-of-the-art performance when compared with other competitors regardless of the datasets. Moreover, it is noteworthy that TRP surpasses the second-best predictors (i.e., DELE and ReNAS) by at least 0.22 Kendall's Tau on all tasks in the macro and micro search spaces. Compared to Arch-Graph (50), which is also tested on TransNAS-Bench-101, we are at least 10 the evaluated architectures fewer than Arch-Graph is, but obtain an improvement of at least 0.25 Kendall's Tau.

Such good results imply that the pretraining stage can fully utilize the transferable relativistic label from zero-shot metrics via the designed soft label and loss function. The pretrained predictor can learn meaningful architecture pair representations for the architectural pairs even before the finetuning stage. Thus, only a few evaluated architectures are enough for a warm start of the predictor on new datasets.

5.2 Searching on Closed Domain Search Spaces

On NAS-Bench-201, the total number of queried architectures is determined by an interpolation-based method (see Table 2). We follow the settings in [Dong and Yang, 2020] to search for architectures. Specifically, the predictor evaluates all architectures in the search space. The best performance of the first 50 evaluated architectures is reported as the search result (see Table 4). Compared with competitors, TRP completes the evaluation of all architectures using only 15 seconds. In addition, we achieve the best average accuracy on different datasets. Especially, the number of queried architectures is substantially fewer than the accuracy predictor (e.g., CAP) and relativistic predictor (e.g., ReNAS). For fair comparison on TransNAS-Bench-101, we follow the settings in [Huang et al., 2022] and the search results are shown in Table 5. On macro and micro search spaces, TRP achieves the best search results on all datasets. Compared to Arch-Graph (query = 50), TRP achieves good results by querying a small number of architectures (query range: 29-40).

These extraordinary results can be attributed to the sufficient transferable relativistic label from zero-shot metrics that the predictor learns in advance through the designed soft label and loss function. Moreover, TRP is finetuned on a small number of evaluated architectures, and obtains excellent state-of-the-art performances on different datasets across multiple search spaces, further verifying the positive effects of using transferable relativistic label. These promising experimental results demonstrate that the transferable relativistic label facilitates reducing the number of evaluated architectures and mitigating cold-start issue on new datasets.

5.3 Searching on Open Domain Search Space

We construct the proxy dataset using the zero-shot metrics on CIFAR-10 for the pretraining predictor, which is finetuned by CIFAR-10 and CIFAR-100. Following [White et al., 2021a], we randomly select a certain number of architectures in the DARTS search space and then train them from scratch to construct the evaluated architectures for the pretraining predictor, where the number of selected architectures is determined by the proposed adaptive approach. For each selected architecture, the epoch number is set to 50 with a batch size 64. As for the search method, we sample 10k architectures at random in the DARTS search space and evaluate them using our trained predictor. After that, we select the architectures with top-5 predicted performance as the search results and re-train them with common DARTS strategies. The experimental results on CIFAR-10 and CIFAR-100 are shown in Table 6.

Compared to predictor-based NAS approaches, the architectures obtained by TRP achieve minimal loss and #Param on both datasets. Regarding search cost, we outperform most predictors on CIFAR-10, second only to TNASP and PINAT. In terms of loss, the architecture obtained by TRP is less than TNASP and PINAT by 0.12 and 0.02, respectively. Regarding the number of queried architectures, on CIFAR-10 and CIFAR-100, TRP is only 1/4 of DELE. Using such a small number of queried architectures and obtaining good search results reaffirms the advantages of the proposed predictor for mitigating cold-start issue. More detailed experimental settings are reported in the supplementary materials.

5.4 Ablation Study

We conduct ablation studies for the loss function, including hyperparameters (λ1 and λ2), hinge/log-sum-exp, and with/without contrastive loss. Based on Figures 2 (a) and (b), λ1 and λ2 for pretraining and finetuning stages should be taken as 7 and 6, respectively, achieving good Kendall's Tau. Figure 2 (c) proves that the log-sum-exp learns a better representation compared to the hinge loss, facilitating the improvement of the ranking ability of the predictor. The contrastive loss can capture better architecture pair representations (see

(c) Hinge vs. log-sum-exp

Figure 2 (d)). More experiments (e.g., ① soft label/hard label, ② with/without pretraining, and ③ finetuning methods) can be found in the supplementary materials.

6 Conclusions

This paper proposes a transferable relativistic predictor to alleviate cold-start issue. The pretraining stage enhances architecture pair representation with a specialized loss function, and the finetuning stage employs interpolation to determine the amount of evaluated architectures adaptively. Experiments across four search spaces demonstrate that TRP outperforms peer predictor-based NAS methods. We further will explore more information fusion technology to boost in-depth research into the transferable relativistic label.

Acknowledgments

This work is supported in part by the National Natural Science Foundation of China under Grant 62472079, in part by the China Scholarship Council (CSC)/Victoria University Scholarship, and in part by the Special Programme for Doctoral Students under the Young Talent Support Project of CAST.