einspace: Searching for Neural Architectures from Fundamental Operations

Linus Ericsson, Miguel Espinosa, Chenhongyi Yang, Antreas Antoniou, Amos J. Storkey, Shay B. Cohen, Steven McDonagh, Elliot J. Crowley

TL;DR

This paper introduces "einspace," a novel and highly expressive search space for neural architecture search (NAS) built from fundamental operations using a probabilistic context-free grammar. This allows NAS to discover a wider range of architectures, including shifts between different paradigms like CNNs and Transformers, moving beyond the limitations of current NAS methods.

What Problem Does This Paper Address?

Neural Architecture Search (NAS) aims to automate the design of high-performing neural networks. However, existing NAS methods often rely on search spaces that are too restrictive, limiting their ability to discover fundamentally new architectures. These spaces are typically designed around specific building blocks (e.g., convolutions) and struggle to represent diverse architectural families like transformers or to facilitate significant design shifts. This has led to a situation where manually designed architectures still dominate, despite the promise of NAS. The authors argue that to unlock the full potential of NAS for transformative design, we need more expressive search spaces built from more fundamental operations.

Methods

The core contribution is einspace, a search space defined by a parameterized probabilistic context-free grammar (PCFG). This approach allows for:

  • Fundamental Operations: Architectures are built from a set of basic operations (branching, aggregation, routing, computation) rather than high-level blocks.
  • Expressive Grammar: The PCFG allows for unbounded derivations, enabling the representation of diverse network sizes, depths, and macro/micro structures.
  • Parameterization: Rules are parameterized to ensure valid architecture generation and to incorporate priors (e.g., feature modes like "Im" for CNNs and "Col" for Transformers).
  • Probabilistic Nature: Probabilities are assigned to production rules to balance search space complexity and guide the sampling process.
  • Derivation Trees: Architectures are represented as derivation trees, facilitating mutations that can alter both macro structure and individual components.

The authors also explore simple search strategies like random sampling, random search, and regularized evolution, finding that in such an expressive space, the choice of strategy is crucial. They highlight the benefit of initializing search with existing state-of-the-art architectures as priors.

Datasets

The paper evaluates einspace on the Unseen NAS datasets, which comprise eight diverse classification tasks across vision, language, audio, and chess. They also conduct experiments on the NASBench360 benchmark.

Key Insights and Ideas

  • Expressivity is Key: The paper strongly advocates for the importance of search space expressivity in enabling NAS to discover novel and transformative architectures, rather than just incremental improvements within existing paradigms.
  • Fundamental Operations Unlock Diversity: Building architectures from basic operations, rather than pre-defined blocks, is crucial for representing a wide range of existing and potentially new architectural families (CNNs, Transformers, MLPs) within a single search space.
  • Priors Still Matter: While einspace is highly expressive, initializing the search with strong, human-designed architectures significantly boosts performance, demonstrating the value of incorporating prior knowledge.
  • Search Strategy is Crucial: In a large and expressive search space like einspace, simple search strategies like random search perform poorly, underscoring the need for more sophisticated search algorithms to effectively navigate the space.

Key Results

  • Competitive Performance: Using simple search strategies (random search, regularized evolution), einspace achieves competitive results across a diverse set of tasks, often outperforming baseline NAS methods.
  • Architectural Improvements: When initializing search with existing architectures (ResNet18, WideResNet-16-4, ViT, MLP-Mixer), einspace consistently finds improved versions of these architectures, and in some cases, surpasses existing state-of-the-art results. For example, on the Language dataset, RE(Mix) found an architecture with a 5.76% improvement over ResNet18.
  • Flexibility Demonstrated: The paper shows that einspace can represent diverse architectures like ResNets, Transformers, and MLP-Mixer within a single framework.
  • Runtime Trade-offs: While gradient-based NAS methods are faster, einspace's evolutionary search, though longer, can find more diverse and potentially better architectures.

Limitations and Future Work

  • Search Space Size: The immense size and unbounded nature of einspace make one-shot NAS methods challenging.
  • Efficiency of Search: The evolutionary search strategy used is computationally expensive. Future work could focus on developing more efficient search algorithms.
  • Ambiguity in Derivations: Multiple derivation trees can lead to the same architecture, posing a challenge for search space size reduction.
  • Limited Operation Set: The current einspace does not support recurrent computations (RNNs) or state-space models like Mamba. Integrating these would further enhance its expressivity.
  • Parameterization Complexity: While parameterization helps ensure valid architectures, managing these parameters during sampling can be complex.

The authors suggest future work on developing intelligent search strategies, exploring recurrent modules, and further refining the parameterization and probabilistic aspects of the grammar.

Summary updated

Abstract

Neural architecture search (NAS) finds high performing networks for a given task. Yet the results of NAS are fairly prosaic; they did not e.g. create a shift from convolutional structures to transformers. This is not least because the search spaces in NAS often aren't diverse enough to include such transformations a priori. Instead, for NAS to provide greater potential for fundamental design shifts, we need a novel expressive search space design which is built from more fundamental operations. To this end, we introduce einspace, a search space based on a parameterised probabilistic context-free grammar. Our space is versatile, supporting architectures of various sizes and complexities, while also containing diverse network operations which allow it to model convolutions, attention components and more. It contains many existing competitive architectures, and provides flexibility for discovering new ones. Using this search space, we perform experiments to find novel architectures as well as improvements on existing ones on the diverse Unseen NAS datasets. We show that competitive architectures can be obtained by searching from scratch, and we consistently find large improvements when initialising the search with strong baselines. We believe that this work is an important advancement towards a transformative NAS paradigm where search space expressivity and strategic search initialisation play key roles.
BibTeX
@inproceedings{ericsson2024einspace,
  author = {Linus Ericsson and Miguel Espinosa and Chenhongyi Yang and Antreas Antoniou and Amos J. Storkey and Shay B. Cohen and Steven McDonagh and Elliot J. Crowley},
  title = {{einspace: Searching for Neural Architectures from Fundamental Operations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=qf1ncViBr5},
}
Figure