Good Performance Estimation Strategies are All You Need in Neural Architecture Search

Recent advances in Neural Architecture Search (NAS) are essentially attributed to Performance Estimation (PE), i.e., a method aims to effectively estimate an architecture. Meanwhile, Kendall's $\tau$τ is well recognized as the principled evaluation criteria for PE strategies in the literature. We argue that Kendall's $\tau$τ is not the optimal solution. Through extensive experiments and theoretical analysis, we take the initiative to reveal the problem behind the Kendall's $\tau$τ and propose a novel criterion named Minimum Keeping Ratio (MKR), which is closely connected to the final performance of NAS. It allows us to compare different PE approaches in a unified perspective, and use effective ablation studies to verify common beliefs and key differences of PE strategies. Based on the findings from MKR, we are able to derive a simple NAS method by integrating different PE strategies with random sampling. Such a method shows very strong performance in efficiency and effectiveness through extensive experiments on different challenging benchmarks. In particular, our simple random sampling NAS finds the optimal architecture in NASbenchMacro, NASbench201, and NASbench301. It is also well generalized to different search spaces (MobileNet) and tasks (semantic segmentation), finding an architecture surpasses the previous state-of-the-art architectures by 4.25 mIoU under $ 600M$600M FLOPs on ADE20K. Codes are available at https://anonymous.4open.science/r/Anonymization11264.