Introduction
Designing high-performing neural network architectures is a complex task that traditionally requires significant expert intuition and computational resources. While Neural Architecture Search (NAS) aims to automate this process, early iterations were computationally expensive, often requiring thousands of GPU days.
Recent "one-shot" NAS methods have mitigated these costs by using a single "super-graph" with shared weights. However, the search strategy—the method for identifying the optimal sub-graph within that super-graph—remains a significant bottleneck. Many current strategies rely on heuristics or struggle with efficient exploration. This paper introduces CoNAS (Compressive sensing-based Neural Architecture Search), a mathematically grounded approach that treats architecture performance as a sparse signal to be recovered.
The CoNAS Framework
CoNAS reframes the NAS problem through the lens of signal processing and Boolean algebra. The core idea is that the performance of an architecture can be modeled as a sparse Boolean function, where only a few low-degree interactions between edges significantly impact final accuracy.
The methodology follows four primary steps:
- Architecture Encoding: Sub-graphs are represented as binary strings $\alpha$, where 1 indicates an active edge and -1 indicates an inactive one.
- Fourier Analysis: The validation performance $f(\alpha)$ is treated as a real-valued Boolean function, representable via a Fourier basis of multilinear polynomials.
- Sparsity Assumption: The authors hypothesize that the Fourier spectrum of architecture performance is sparse, meaning only a few components drive the model's success.
- Sparse Recovery via Lasso: After training a one-shot model with weight sharing, the algorithm randomly samples a small set of sub-architectures. It then uses Lasso (sparse recovery) to estimate the Fourier coefficients, effectively reconstructing the performance landscape from minimal data.
Unlike purely empirical NAS methods, CoNAS provides theoretical guarantees (Theorem 2.4) regarding the number of measurements required to reliably identify the best architecture, provided the performance function satisfies the "Restricted Isometry Property" (RIP).
Experimental Evaluation
The researchers validated CoNAS on two major benchmarks: the DARTS search space for CIFAR-10 and the diagnostic NAS-Bench-201, which includes precomputed data for CIFAR-10, CIFAR-100, and ImageNet-16-120.
Key Results
- Superior Accuracy: On the DARTS search space, CoNAS achieved a 2.59% test error, outperforming the original DARTS (2.76%) and Random Search with Parameter Sharing (2.71%).
- Efficiency: CoNAS completed its search in just 0.35 GPU days. This is a massive speedup compared to the 4 days required by standard DARTS or the 2,000 days for original NASNet-A.
- Robustness: As shown in the performance table, CoNAS consistently outperformed standard one-shot baselines like DARTS and ENAS on the NAS-Bench-201 benchmark, where some traditional methods struggle to generalize.
Discussion and Limitations
While CoNAS represents a significant step forward in search efficiency, it is not without limitations. The authors noted a "correlation gap" in one-shot models; the performance of a sub-graph with shared weights does not always correlate perfectly with its performance when trained from scratch (Kendall-tau correlation of 0.15). This suggests that CoNAS is a highly effective searcher, but its ultimate success is still bounded by the quality of the underlying one-shot model.
Additionally, the final step of the algorithm involves a brute-force search over the identified important components. While manageable for current sparsity levels, this could become a computational hurdle in more complex, less sparse search spaces. Future work may focus on simplifying the iterative restriction process and improving the correlation between shared-weight performance and standalone accuracy.
Summary updated