Abstract
Gradient-based Neural Architecture Search (NAS) often suffers from a "consistency gap" between the dense super-net used during search and the sparse target-net used for evaluation. We present ISTA-NAS, a novel framework that reformulates NAS as a sparse coding problem. By searching in a compressed space and employing the Iterative Shrinkage-Thresholding Algorithm (ISTA), we ensure architectural sparsity throughout the search process. Our method achieves state-of-the-art results on ImageNet and CIFAR-10 while significantly reducing search costs to as low as 0.05 GPU-days. Crucially, ISTA-NAS demonstrates a high positive correlation between search and evaluation performance, addressing the reliability issues of previous methods.
Introduction
Most contemporary gradient-based NAS methods, such as DARTS, rely on training a dense "super-net" containing all possible architectural connections. After training, this super-net is pruned to a sparse "target-net" for final evaluation. This approach introduces a significant "consistency gap": the optimal dense architecture is not necessarily the optimal sparse one. Additionally, searching on small proxy networks often fails to generalize to larger target models. These discrepancies lead to poor correlation between search-phase performance and final evaluation accuracy.
Methodology: NAS as Sparse Coding
ISTA-NAS rethinks the search for an optimal architecture by treating it as a sparse signal recovery problem.
Sparse Coding Formulation
Instead of directly optimizing a high-dimensional architecture variable $z$, we project it into a lower-dimensional compressed space $b$. This leverages the principles of compressed sensing, specifically the Restricted Isometry Property (RIP), which suggests that sparse signals can be efficiently recovered from a small number of projections.
Architecture Recovery via ISTA
To maintain sparsity during search, we use the Iterative Shrinkage-Thresholding Algorithm (ISTA). During each update step, ISTA recovers the sparse architecture $z$ from the compressed variables $b$. This ensures that the network remains sparse and computationally efficient throughout the entire search process, directly minimizing the gap between search and evaluation.
One-Stage vs. Two-Stage Search
We propose two variants of ISTA-NAS:
- Two-Stage: A rapid search on a proxy task followed by separate training of the discovered architecture.
- One-Stage: Search and evaluation occur simultaneously on the final target-net scale. Once the architecture stabilizes, the architecture variables are integrated into the Batch Normalization (BN) layers, making the search cost nearly equivalent to standard training.
Experimental Results
We evaluated ISTA-NAS on CIFAR-10 and ImageNet benchmarks, focusing on efficiency, accuracy, and consistency.
Efficiency and Accuracy
ISTA-NAS demonstrates extreme efficiency. The two-stage variant completes its CIFAR-10 search in just 0.05 GPU-days—approximately 20x faster than DARTS. Despite this speed, it achieves top-tier accuracy: a 2.36% error rate on CIFAR-10 and a 24.0% top-1 error on ImageNet, outperforming established methods like PC-DARTS.
Consistency Analysis
A key advantage of ISTA-NAS is its reliability. We measured the Kendall $\tau$ correlation between search-phase validation accuracy and final test accuracy.
As shown in the table, DARTS exhibits a negative correlation (-0.36), indicating that its search process is often misleading. In contrast, ISTA-NAS achieves a strong positive correlation (up to 0.57), proving that its search process consistently identifies high-performing architectures.
Conclusion and Future Work
ISTA-NAS effectively addresses the consistency and efficiency challenges in NAS by integrating sparsity constraints directly into the optimization process via sparse coding. While highly effective, future work could explore optimizing the measurement matrix $A$ or extending the search space beyond cell-based structures to global macro-architectures.
Summary updated