# Neural Architecture Search with Random Labels

arXiv: https://arxiv.org/abs/2101.11834 · HTML: https://mlsanity.com/paper/2101.11834/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 50 references that are in the map.
- First posted on arXiv 28 Jan 2021.

## Builds on (most cited first, 30 of 39)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [The Cityscapes Dataset for Semantic Urban Scene Understanding](https://mlsanity.com/paper/1604.01685/) (2016)
- [Rethinking Atrous Convolution for Semantic Image Segmentation](https://mlsanity.com/paper/1706.05587/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Unsupervised Representation Learning by Predicting Image Rotations](https://mlsanity.com/paper/1803.07728/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles](https://mlsanity.com/paper/1603.09246/) (2016)
- [Colorful Image Colorization](https://mlsanity.com/paper/1603.08511/) (2016)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [MnasNet: Platform-Aware Neural Architecture Search for Mobile](https://mlsanity.com/paper/1807.11626/) (2018)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware](https://mlsanity.com/paper/1812.00332/) (2018)
- [Progressive Neural Architecture Search](https://mlsanity.com/paper/1712.00559/) (2017)
- [FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search](https://mlsanity.com/paper/1812.03443/) (2018)
- [Single Path One-Shot Neural Architecture Search with Uniform Sampling](https://mlsanity.com/paper/1904.00420/) (2019)
- [A Downsampled Variant of ImageNet as an Alternative to the CIFAR datasets](https://mlsanity.com/paper/1707.08819/) (2017)
- [NAS-FPN: Learning Scalable Feature Pyramid Architecture for Object Detection](https://mlsanity.com/paper/1904.07392/) (2019)
- [Designing Neural Network Architectures using Reinforcement Learning](https://mlsanity.com/paper/1611.02167/) (2016)
- [Auto-DeepLab: Hierarchical Neural Architecture Search for Semantic Image Segmentation](https://mlsanity.com/paper/1901.02985/) (2019)
- [Random Search and Reproducibility for Neural Architecture Search](https://mlsanity.com/paper/1902.07638/) (2019)
- [Neural Architecture Search without Training](https://mlsanity.com/paper/2006.04647/) (2020)
- [Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation](https://mlsanity.com/paper/1904.12760/) (2019)
- [SMASH: One-Shot Model Architecture Search through HyperNetworks](https://mlsanity.com/paper/1708.05344/) (2017)
- [Fair DARTS: Eliminating Unfair Advantages in Differentiable Architecture Search](https://mlsanity.com/paper/1911.12126/) (2019)

## Built on by (most cited first, 30 of 33)

- [BossNAS: Exploring Hybrid CNN-transformers with Block-wisely Self-supervised Neural Architecture Search](https://mlsanity.com/paper/2103.12424/) (2021)
- [ZiCo: Zero-shot NAS via Inverse Coefficient of Variation on Gradients](https://mlsanity.com/paper/2301.11300/) (2023)
- [Neural Architecture Search for Spiking Neural Networks](https://mlsanity.com/paper/2201.10355/) (2022)
- [AutoSNN: Towards Energy-Efficient Spiking Neural Networks](https://mlsanity.com/paper/2201.12738/) (2022)
- [AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search](https://mlsanity.com/paper/2403.19232/) (2024)
- [Analyzing and Mitigating Interference in Neural Architecture Search](https://mlsanity.com/paper/2108.12821/) (2021)
- [Pi-NAS: Improving Neural Architecture Search by Reducing Supernet Training Consistency Shift](https://mlsanity.com/paper/2108.09671/) (2021)
- [The Curious Case of Benign Memorization](https://mlsanity.com/paper/2210.14019/) (2022)
- [Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics](https://mlsanity.com/paper/2108.11939/) (2021)
- [β-DARTS++: Bi-level Regularization for Proxy-robust Differentiable Architecture Search](https://mlsanity.com/paper/2301.06393/) (2023)
- [Partial Fine-Tuning: A Successor to Full Fine-Tuning for Vision Transformers](https://mlsanity.com/paper/2312.15681/) (2023)
- [Observations on K-image Expansion of Image-Mixing Augmentation for Classification](https://mlsanity.com/paper/2110.04248/) (2021)
- [Unsupervised Graph Neural Architecture Search with Disentangled Self-supervision](https://mlsanity.com/paper/2403.05064/) (2024)
- [Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis](https://mlsanity.com/paper/2205.05662/) (2022)
- [Differentiable Architecture Search with Random Features](https://mlsanity.com/paper/2208.08835/) (2022)
- [DNA Family: Boosting Weight-Sharing NAS with Block-Wise Supervisions](https://mlsanity.com/paper/2403.01326/) (2024)
- [OStr-DARTS: Differentiable Neural Architecture Search based on Operation Strength](https://mlsanity.com/paper/2409.14433/) (2024)
- [When NAS Meets Trees: An Efficient Algorithm for Neural Architecture Search](https://mlsanity.com/paper/2204.04918/) (2022)
- [Automated Dominative Subspace Mining for Efficient Neural Architecture Search](https://mlsanity.com/paper/2210.17180/) (2022)
- [Revisiting Training-free NAS Metrics: An Efficient Training-based Method](https://mlsanity.com/paper/2211.08666/) (2022)
- [GeNAS: Neural Architecture Search with Better Generalization](https://mlsanity.com/paper/2305.08611/) (2023)
- [Training-free Neural Architecture Search through Variance of Knowledge of Deep Network Weights](https://mlsanity.com/paper/2502.04975/) (2025)
- [Training BatchNorm Only in Neural Architecture Search and Beyond](https://mlsanity.com/paper/2112.00265/) (2021)
- [Towards Self-supervised and Weight-preserving Neural Architecture Search](https://mlsanity.com/paper/2206.04125/) (2022)
- [Leveraging Unlabeled Data to Track Memorization](https://mlsanity.com/paper/2212.04461/) (2022)
- [One Network Doesn't Rule Them All: Moving Beyond Handcrafted Architectures in Self-Supervised Learning](https://mlsanity.com/paper/2203.08130/) (2022)
- [α DARTS Once More: Enhancing Differentiable Architecture Search by Masked Image Modeling](https://mlsanity.com/paper/2211.10105/) (2022)
- [Dextr: Zero-Shot Neural Architecture Search with Singular Value Decomposition and Extrinsic Curvature](https://mlsanity.com/paper/2508.12977/) (2025)
- [Connection Sensitivity Matters for Training-free DARTS: From Architecture-Level Scoring to Operation-Level Sensitivity Analysis](https://mlsanity.com/paper/2106.11542/) (2021)
- [Mutually-aware Sub-Graphs Differentiable Architecture Search](https://mlsanity.com/paper/2107.04324/) (2021)

## Abstract (arXiv)

In this paper, we investigate a new variant of neural architecture search (NAS) paradigm -- searching with random labels (RLNAS). The task sounds counter-intuitive for most existing NAS algorithms since random label provides few information on the performance of each candidate architecture. Instead, we propose a novel NAS framework based on ease-of-convergence hypothesis, which requires only random labels during searching. The algorithm involves two steps: first, we train a SuperNet using random labels; second, from the SuperNet we extract the sub-network whose weights change most significantly during the training. Extensive experiments are evaluated on multiple datasets (e.g. NAS-Bench-201 and ImageNet) and multiple search spaces (e.g. DARTS-like and MobileNet-like). Very surprisingly, RLNAS achieves comparable or even better results compared with state-of-the-art NAS methods such as PC-DARTS, Single Path One-Shot, even though the counterparts utilize full ground truth labels for searching. We hope our finding could inspire new understandings on the essential of NAS.