ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding

Yibo Yang, Hongyang Li, Shan You, Fei Wang, Chen Qian, Zhouchen Lin

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.

Conceptual framework of ISTA-NAS, illustrating the search in compressed space and recovery via ISTA.

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.

We propose two variants of ISTA-NAS:

  1. Two-Stage: A rapid search on a proxy task followed by separate training of the discovered architecture.
  2. 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.

Comparison of Kendall tau correlation across different NAS methods.

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

Abstract

Neural architecture search (NAS) aims to produce the optimal sparse solution from a high-dimensional space spanned by all candidate connections. Current gradient-based NAS methods commonly ignore the constraint of sparsity in the search phase, but project the optimized solution onto a sparse one by post-processing. As a result, the dense super-net for search is inefficient to train and has a gap with the projected architecture for evaluation. In this paper, we formulate neural architecture search as a sparse coding problem. We perform the differentiable search on a compressed lower-dimensional space that has the same validation loss as the original sparse solution space, and recover an architecture by solving the sparse coding problem. The differentiable search and architecture recovery are optimized in an alternate manner. By doing so, our network for search at each update satisfies the sparsity constraint and is efficient to train. In order to also eliminate the depth and width gap between the network in search and the target-net in evaluation, we further propose a method to search and evaluate in one stage under the target-net settings. When training finishes, architecture variables are absorbed into network weights. Thus we get the searched architecture and optimized parameters in a single run. In experiments, our two-stage method on CIFAR-10 requires only 0.05 GPU-day for search. Our one-stage method produces state-of-the-art performances on both CIFAR-10 and ImageNet at the cost of only evaluation time.
BibTeX
@inproceedings{yang2020ista,
  author = {Yibo Yang and Hongyang Li and Shan You and Fei Wang and Chen Qian and Zhouchen Lin},
  title = {{ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
}
Figure