Source-linked AI summary
GreedyNAS: Towards Fast One-Shot NAS with Greedy Supernet
Shan You, Tao Huang, Mingmin Yang, Fei Wang, Chen Qian, Changshui Zhang
TL;DR
One-shot NAS supernets must estimate architectures across enormous search spaces, but treating every path equally makes accurate ranking difficult and training expensive. GreedyNAS filters weak paths using surrogate validation loss and maintains a candidate pool to focus training and search on promising paths. On ImageNet, it improves accuracy under matched resource constraints while reducing supernet training cost, and it also finds state-of-the-art architectures in a larger search space.
Problem
One-shot NAS supernets are expected to rank all paths accurately, but huge search spaces make this difficult and costly.
Method
GreedyNAS uses multi-path sampling with rejection to filter weak paths and an exploration-exploitation candidate pool to focus training on potentially good paths.
Results
GreedyNAS achieves higher Top-1 accuracy under matched FLOPs or latency while reducing supernet training cost by approximately 40%, and finds new state-of-the-art architectures in a larger search space.
Takeaways & Limitations
GreedyNAS improves both accuracy performance and supernet training efficiency by shrinking training and search toward promising paths.
Takeaways & Limitations
Path ranking relies on loss over a surrogate validation subset, whose consistency with full-validation accuracy is reported empirically rather than guaranteed.
Abstract
from arXiv · showhide
Training a supernet matters for one-shot neural architecture search (NAS) methods since it serves as a basic performance estimator for different architectures (paths). Current methods mainly hold the assumption that a supernet should give a reasonable ranking over all paths. They thus treat all paths equally, and spare much effort to train paths. However, it is harsh for a single supernet to evaluate accurately on such a huge-scale search space (e.g., $7^{21}$). In this paper, instead of covering all paths, we ease the burden of supernet by encouraging it to focus more on evaluation of those potentially-good ones, which are identified using a surrogate portion of validation data. Concretely, during training, we propose a multi-path sampling strategy with rejection, and greedily filter the weak paths. The training efficiency is thus boosted since the training space has been greedily shrunk from all paths to those potentially-good ones. Moreover, we further adopt an exploration and exploitation policy by introducing an empirical candidate path pool. Our proposed method GreedyNAS is easy-to-follow, and experimental results on ImageNet dataset indicate that it can achieve better Top-1 accuracy under same search space and FLOPs or latency level, but with only $\sim$60\% of supernet training cost. By searching on a larger space, our GreedyNAS can also obtain new state-of-the-art architectures.
1. Introduction
NAS automates architecture design, but one-shot methods face a difficult supernet-training trade-off: evaluating every path in a huge search space is costly and may degrade ranking quality. GreedyNAS addresses this by filtering weak paths, focusing training on potentially good paths, and improving ImageNet accuracy and training efficiency.
- Motivation: Earlier NAS approaches required enormous computation budgets, including 2000 GPU days for reinforcement learning and 3150 GPU days for evolution.
- Background: One-shot NAS reduces search cost by training an over-parameterized supernet whose architectures share weights.Parameterized methods learn operation distributions, whereas single-path methods separate supernet training from architecture sampling.
- Motivation: A single supernet may struggle to rank all paths because the search space is huge and includes architectures with sharply different accuracy.The same supernet can contain a MobileNetV2 path achieving 72.0% Top-1 accuracy and an almost-all-identity path achieving 24.1%.
- Contribution: GreedyNAS filters weak paths so the supernet focuses on evaluating potentially good architectures rather than ranking every path.It uses multi-path sampling with rejection and a candidate pool to progressively shrink the training space.
- Results: GreedyNAS achieves higher Top-1 accuracy at comparable FLOPs or latency while reducing supernet training cost by approximately 40%.The comparison is reported on ImageNet under the same search space and matched resource constraints.
2. Related Work
One-shot NAS methods commonly represent many architectures in a shared-weight supernet. They either learn architecture parameters for gradient-based search or sample discrete single-path architectures and search them afterward.
- Overview: One-shot NAS trains an over-parameterized supernet containing architectures that share weights, from which an optimal path can be searched.
- Parameterized architectures: Parameterized methods introduce real-valued categorical distributions and jointly learn architecture parameters with supernet weights.DARTS, FBNet, and MdeNAS use this formulation, while ProxylessNAS factorizes selection into binary tasks to reduce memory use.
- Sampled single-path architectures: Sampled single-path methods train the supernet by optimizing sampled paths, then use random search or evolutionary algorithms to find an architecture.Sampling may be uniform or multi-path with fairness.
3. Rethinking path training of supernet
One-shot NAS supernets traditionally train all paths uniformly, but their enormous search spaces make accurate ranking difficult. GreedyNAS instead filters weak paths using multi-path rejection and surrogate validation loss, then trains primarily on potentially-good paths.
- Motivation: Uniformly training all paths is demanding because the supernet must rank architectures across a huge discrete search space, while weak paths can disturb evaluation of potentially-good paths.The search space contains O^L architectures, exemplified as 7^21, and shared weights allow weak-path training to influence stronger paths.
- Reshaping sampling distribution: GreedyNAS reshapes sampling toward potentially-good paths, using the current supernet as a proxy for an unknown oracle and progressively updating this focused training distribution.The intended effect is to train potentially-good paths more thoroughly and improve their relative performance ranking.
- Candidate path pool: A candidate path pool supports the greedy training loop by mixing pool sampling with uniform sampling, enabling repeated filtering, pool updates, and optimization of retained paths.The algorithm initializes a pool, schedules its sampling probability, retains k paths from each m-path sample, updates the pool, and trains the retained paths.
- Greedy path filtering: Multi-path rejection samples m paths, ranks them by validation loss, keeps the Top-k paths, and rejects the remainder to approximate sampling from the potentially-good subset.Theorem 1 motivates this procedure through the probability that at least k of m uniformly sampled paths belong to the good subset.
- Greedy path filtering: The filtering decision uses a randomly sampled surrogate validation subset rather than the full validation set, because ranking on the full set is computationally intensive.The paper reports that ranking by loss on a surrogate subset, such as 1k ImageNet images, is sufficiently consistent with full-validation accuracy ranking.
4. Proposed Approach: GreedyNAS
GreedyNAS trains a greedy supernet that concentrates on potentially good paths rather than evaluating all paths equally. It combines weak-path filtering, an exploration–exploitation candidate pool, candidate-pool-based stopping, and candidate-pool initialization for evolutionary search.
- Supernet training: GreedyNAS filters weak paths during supernet training so the training space shifts from all paths toward potentially good paths.The method uses multi-path sampling with rejection and evaluates paths on a surrogate validation subset.
- Exploration and exploitation: The candidate pool stores promising paths with evaluation losses and supports exploitation while uniform sampling preserves exploration of the broader search space.The pool is maintained as an ordered fixed-size queue, while pool sampling is annealed from zero because early priorities may be unreliable.
- Exploration and exploitation: Sampling from the candidate pool raises the probability of selecting good paths, increasing the chance of obtaining at least 5 good paths in 10 from 83.38% to 99.36% when ε = 0.5.The pool improves filtering confidence while requiring only a min-heap to maintain.
- Stopping principle via candidate pool: GreedyNAS stops supernet training adaptively when the candidate pool’s update frequency falls below a preset tolerance, indicating that the pool has become steady.The update frequency measures how many new paths enter the pool over a fixed interval.
- Searching with candidate pool: During evolutionary search, GreedyNAS initializes the population with the candidate pool’s Top-Npop paths rather than random paths.The candidate-pool initialization supplies a stronger starting population for subsequent mutation and crossover.
- Searching with candidate pool: Table 1 compares classification performance and supernet training efficiency across searching methods on ImageNet under the same search space.The table reports optimization, evaluation, and corrected optimization costs.
5. Experimental Results
Experiments show that GreedyNAS improves searched-model accuracy while reducing supernet training cost, and that greedy filtering remains effective with surrogate validation evaluation.
- Searching on same search space: 74.93% Top-1 ACC at similar 80 ms latency improves over uniform sampling by 0.43%.At similar 320M FLOPs, GreedyNAS also achieves the highest Top-1 accuracy among the compared methods.
- Searching on same search space: GreedyNAS reduces supernet training cost and achieves almost 1% higher accuracy than reduced-training uniform and random baselines.The method learns a decent supernet with much fewer training iterations by shrinking training toward potentially good paths.
- Searching on augmented search space: GreedyNAS-C exceeds SCARLET by 0.6% Top-1 accuracy at similar FLOPs and latency, achieving new state-of-the-art performance in the augmented space.GreedyNAS also significantly reduces training time compared with other NAS methods; smaller and larger variants differ in identity-block and SE-module usage.
- Effect of evaluation in path filtering: Using 1000 validation images yields rank correlations of 0.997 and 0.961 with full-dataset rankings for the greedy supernet.The correlations indicate that surrogate evaluation using 1000 images is consistent with ranking based on all 50K validation images.
- Effect of evaluation in path filtering: A 10K-iteration uniform-sampling warm-up is used because uniform-supernet Kendall tau reaches about 0.81 and then becomes steady.Too few evaluation images weaken correlation, while too many increase evaluation cost; 1000 images provide a reported balance.
- Effect of path filtering and candidate pool: Greedy filtering improves searched accuracy by 0.28% or 0.41% over corresponding baselines, while candidate-pool initialization adds a 0.18% gain.Stopping with the candidate pool balances exploration and exploitation, whereas full candidate-pool training slightly reduces accuracy by 0.05%.
6. Conclusion
GreedyNAS improves supernet training by focusing on potentially good paths rather than treating all paths equally, while using evolutionary search to identify high-accuracy architectures under constraints.
- 6. Conclusion: GreedyNAS filters weak paths during supernet training and uses an exploration–exploitation candidate pool to improve training efficiency.The method uses multi-path sampling with rejection and an empirical candidate pool.
- 6. Conclusion: The evolutionary algorithm uses a population of 50 architectures over 20 generations.
- 6. Conclusion: The evolutionary search takes a supernet, candidate pool, validation data, and constraints as input, returning the highest-validation-accuracy architecture under those constraints.NSGA-II maintains populations through selection, recombination, mutation, nondominated sorting, and validation-based ranking.
B.1. Details of (augmented) search space
The augmented search space is organized around MobileNetV2-based choice blocks, with operation configurations specified by the supernet macro-structure and implementation details for training-cost correction and ranking evaluation.
- B.1. Details of (augmented) search space: The macro-structure specifies feature-map inputs, output channels, repeated blocks, strides, and MobileNetV2-based choice-block operations.Operation choices for each choice block are provided separately, including identity mappings.
- B.1. Details of (augmented) search space: GreedyNAS evaluates 10 paths on 1000 validation images and selects 5 paths for training with batch size 1024.
- B.1. Details of (augmented) search space: The corrected optimization count uses the empirical finding that one optimization step costs approximately 3.33 forward evaluations.
- B.1. Details of (augmented) search space: Spearman rho and Kendall tau compare rankings produced with 1000 versus 50K validation images.Spearman measures correlation between ranking vectors, while Kendall tau evaluates pairwise ranking agreement.
B.4.1 Performance of trained supernet
A greedy supernet consistently helps searchers identify better architectures than uniform supernets, and its selected paths achieve higher retraining accuracy on average.
- B.4.1 Performance of trained supernet: Greedy supernets consistently improve classification accuracy across different searchers compared with uniform supernets.The comparison covers random and evolutionary search on greedy, fully trained uniform, and cost-matched uniform supernets.
- B.4.1 Performance of trained supernet: Greedy-supernet paths have higher average retraining Top-1 accuracy than paths found with a uniform supernet.The comparison uses systematically sampled paths from architectures discovered by evolutionary search.
B.5. Visualization of searched architectures
The paper visualizes the architectures searched by GreedyNAS in Figure 6.
- B.5. Visualization of searched architectures: Figure 6 visualizes the architectures searched by GreedyNAS.