Introduction
Neural Architecture Search (NAS) has revolutionized the design of deep learning models by automating the discovery of high-performance architectures. However, the computational cost of "conventional" NAS—often requiring thousands of GPU hours—remains a significant barrier. To address this, One-shot NAS was introduced. This approach utilizes a "supernet" containing all possible architectures in a search space, where weights are shared across different models. While efficient, one-shot NAS frequently suffers from poor ranking correlation: the architectures that perform best within the supernet often fail to maintain their lead when trained from scratch.
The Ranking Correlation Problem
The fundamental challenge in one-shot NAS is ensuring that the performance of a sub-network within the supernet accurately reflects its true potential. As illustrated below, there is often a significant mismatch between the ranking of architectures during the search phase and their final performance after full training. This discrepancy is particularly pronounced in one-shot settings compared to conventional NAS.
Identifying "Small Model Bias"
The authors identify a specific phenomenon called Small Model Bias as a primary driver of this ranking failure. Because one-shot training cycles are typically very short, smaller architectures—which converge quickly—appear much more capable than larger, more complex ones that require more optimization to reach their performance ceiling. These "quick learners" often contain many parameter-free operations like skip connections or pooling, which provide high initial accuracy but lower eventual performance. When the search space contains models of diverse sizes, the ranking accuracy drops significantly (e.g., from 73% for similar-sized models to 62% for diverse ones).
Optimization as a Bottleneck
Empirical analysis reveals that ranking reliability is directly tied to the duration of the one-shot training process. As shown in the table below, increasing the number of training epochs significantly improves the pairwise ranking accuracy, suggesting that the "one-shot" budget is often insufficient for larger models to demonstrate their value.
Balanced NAO: Proportional Sampling
To level the playing field, the authors propose Balanced NAO. Instead of the standard uniform sampling—where every architecture has an equal chance of being updated—Balanced NAO employs Proportional Sampling. The probability $P(x_i)$ of sampling an architecture $x_i$ is set proportional to its parameter count:
$$P(x_i) = \frac{\text{model\_size}(x_i)}{\sum_{x_j \in \mathcal{X}} \text{model\_size}(x_j)}$$
By allocating more gradient updates to larger architectures, the method ensures that their optimization state is balanced against smaller models. This prevents the search algorithm from being misled by the rapid convergence of simplistic architectures.
Experimental Results
Balanced NAO achieves state-of-the-art results across standard benchmarks while demonstrating superior stability:
- CIFAR-10: The method discovered an architecture with a 2.60% test error (3.8M parameters), outperforming popular baselines like DARTS (2.83%) and ENAS (2.89%).
- ImageNet: In a mobile setting, the discovered architecture reached 74.4% top-1 accuracy, proving its transferability to large-scale datasets.
- Search Stability: In five independent runs, Balanced NAO showed a tight performance range (2.60% to 2.77% error), whereas DARTS exhibited much higher variance (2.82% to 3.02%).
Conclusion
The success of Balanced NAO suggests that the limitations of one-shot NAS are not inherent to weight-sharing itself, but rather to how the training budget is distributed. By accounting for the different learning speeds of architectures based on their size, Balanced NAO restores ranking reliability and enables the robust discovery of high-performance deep learning models.
Summary updated