Approximate Neural Architecture Search via Operation Distribution Learning

Xingchen Wan, Binxin Ru, Pedro M. Esperança, Fabio M. Carlucci

Neural Architecture Search (NAS) has long been a quest for the "perfect blueprint"—the exact combination of operations and connections that yields the highest accuracy. But what if we’re over-engineering the search? A new paper, "Approximate Neural Architecture Search via Operation Distribution Learning," suggests that the specific wiring of a network might matter far less than the "recipe" of operations used.

By shifting the focus from deterministic architectures to operation distributions, the authors introduce a framework called ANASOD that slashes search times and simplifies optimization without sacrificing performance.

TL;DR

Instead of searching for a single, exact neural architecture, ANASOD searches for the optimal distribution of operations (e.g., the ratio of 3x3 convolutions to max-pooling). This approach compresses astronomical search spaces by orders of magnitude, leading to massive speedups across various NAS algorithms while remaining highly predictive of final model performance.

What Problem Does This Paper Address?

The standard NAS paradigm is a combinatorial nightmare. In a typical search space like DARTS, there are roughly $10^{12}$ possible architectures. Finding the global optimum in this haystack is computationally expensive and often unnecessary.

The authors identify a key inefficiency: most NAS algorithms treat architectures with the same operations but slightly different wiring as completely distinct entities. However, empirical evidence suggests these "neighbors" often perform almost identically. By insisting on finding one specific deterministic graph, we waste resources exploring redundant regions of the search space.

Figure 1: Three architecture cells from NAS-Bench-201 (NB201) [11] giving very similar validation performance. Each edge represents an operation: either conv1×1 or conv3×3. From the viewpoint of existing encodings, they represent three distinct architectures which all need to be evaluated. The ANASOD framework assumes that they all belong to the same operation distribution (4×conv3×3 and 2×conv1×1 in 6 operations) and does not repeatedly re-evaluate each one.

Methods

The core innovation is the ANASOD encoding. Instead of representing a cell as an adjacency matrix or a set of paths, ANASOD represents it as a $k$-dimensional vector on a probability simplex, where each dimension corresponds to the relative frequency of a specific operation.

Key aspects of the method include:

  • Search Space Compression: In a DARTS-like cell, the number of unique architectures is $\approx 4.3 \times 10^{12}$, but the number of unique ANASOD distributions is only $\approx 1.2 \times 10^5$.
  • Orthogonality: ANASOD isn't a new search algorithm; it's a new representation that can be plugged into existing ones:
  • ANASOD-BO: Uses Bayesian Optimization on the simplex space, which is much easier for Gaussian Processes to handle than high-dimensional discrete graphs.
  • ANASOD-DNAS: A differentiable version where all edges share the same categorical distribution, acting as a natural regularizer.
  • Biased Random Search: A simple but effective modification that progressively biases sampling toward the best-performing distributions found so far.

Datasets

The authors validated ANASOD across several standard benchmarks and open-domain tasks:

  • NAS-Bench-201: Evaluated on CIFAR-10, CIFAR-100, and ImageNet16-120.
  • NAS-Bench-301: A surrogate benchmark for the massive DARTS search space.
  • Open-Domain Tasks: Searching on the popular NASNet-style search space using CIFAR-10 and transferring the results to CIFAR-100.

Key Insights and Ideas

  • Operations > Wiring: The "aha moment" is that the operation mix is a surprisingly strong proxy for performance. As shown in Figure 2, architectures sampled from the same distribution have very low variance in validation error.
  • Smoothing the Landscape: By moving from a discrete graph space to a continuous simplex, the search landscape becomes smoother and easier for gradient-based or kernel-based optimizers to navigate.
  • Implicit Regularization: In differentiable NAS, forcing all edges to share a distribution prevents the common "collapse" where the search quickly settles on poor-performing architectures dominated by skip-connections.
Figure 2: To what extent does the ANASOD encoding determine performance? We randomly draw 200 ANASOD encodings in 4 tasks. Within each, we draw 5 architectures for each encoding and show the mean ± 1 standard deviation (black and gray, respectively) of the top-100 encodings vs those of all 1,000 sampled architectures (red). Architectures sampled from the same encoding usually perform similarly and encodings that on average perform better also have smaller variability.

Key Results

  • Efficiency: ANASOD-BO achieved a massive speedup over traditional adjacency or path-based Bayesian Optimization. In open-domain experiments, it found competitive architectures in just 0.6 wall-clock days on 4 GPUs.
  • Performance: On NAS-Bench-201 (CIFAR-10), ANASOD-BO achieved a validation error of 8.41%, outperforming SOTA baselines like BANANAS (8.51%) and NAS-BOWL (8.50%).
  • Robustness: The "Biased Random Search" variant, despite its simplicity, often matched or exceeded the performance of much more complex NAS methods.
  • Transferability: A distribution optimized on CIFAR-10 transferred successfully to CIFAR-100, achieving a 13.76% error rate, which is competitive with methods that searched on CIFAR-100 directly.

Limitations and Future Work

While powerful, the authors note a few areas for further exploration:

  • Search Space Scope: The current work focuses on cell-based search spaces in computer vision. It remains to be seen how well operation distribution learning translates to non-cell-based spaces or other domains like Natural Language Processing.
  • Ensemble Potential: Since ANASOD defines a distribution, it naturally lends itself to creating ensembles of related, high-performing architectures rather than just one. The authors suggest this as a promising direction for improving model robustness and uncertainty quantification.
  • Interpretability: The encoding is human-interpretable (e.g., "this task needs more convolutions than pooling"), which could help researchers understand why certain architectures work better for specific datasets.

Summary updated

Abstract

The standard paradigm in Neural Architecture Search (NAS) is to search for a fully deterministic architecture with specific operations and connections. In this work, we instead propose to search for the optimal operation distribution, thus providing a stochastic and approximate solution, which can be used to sample architectures of arbitrary length. We propose and show, that given an architectural cell, its performance largely depends on the ratio of used operations, rather than any specific connection pattern in typical search spaces; that is, small changes in the ordering of the operations are often irrelevant. This intuition is orthogonal to any specific search strategy and can be applied to a diverse set of NAS algorithms. Through extensive validation on 4 data-sets and 4 NAS techniques (Bayesian optimisation, differentiable search, local search and random search), we show that the operation distribution (1) holds enough discriminating power to reliably identify a solution and (2) is significantly easier to optimise than traditional encodings, leading to large speed-ups at little to no cost in performance. Indeed, this simple intuition significantly reduces the cost of current approaches and potentially enable NAS to be used in a broader range of applications.
BibTeX
@inproceedings{wan2022approximate,
  author = {Xingchen Wan and Binxin Ru and Pedro M. Esperança and Fabio M. Carlucci},
  title = {{Approximate Neural Architecture Search via Operation Distribution Learning}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2022},
  doi = {10.1109/wacv51458.2022.00360},
}
Figure