PaperlayerView exact revision on arXiv

Source-linked AI summary

BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search

Colin White, Willie Neiswanger, Yash Savani

arXiv:1910.11858v3cs.LGcs.NEstat.ML

TL;DR

NAS needs methods that efficiently search increasingly complex architectures, while prior BO + neural predictor studies made component-level contributions difficult to isolate. This paper analyzes five framework components, introduces a path-based encoding, and uses the results to build BANANAS, which achieves state-of-the-art performance on NAS search spaces.

  • Problem

    Prior BO + neural predictor NAS studies often analyzed full algorithms, making it difficult to determine which individual components produce the best performance.

  • Method

    The paper tests architecture encoding, neural predictor, uncertainty calibration, acquisition function, and acquisition optimization, and develops a path-based encoding for neural architectures.

  • Results

    BANANAS achieves state-of-the-art performance on NAS search spaces, including NASBench-101, and is competitive across NASBench-201 datasets.

  • Takeaways & Limitations

    The component analysis yields a high-performance BO + neural predictor instantiation and identifies path encoding as a scalable architecture representation for accurate neural prediction.

  • Takeaways & Limitations

    The work’s indirect connection to real applications limits control over whether its methods produce beneficial or harmful societal effects.

Abstract

from arXiv · show

Over the past half-decade, many methods have been considered for neural architecture search (NAS). Bayesian optimization (BO), which has long had success in hyperparameter optimization, has recently emerged as a very promising strategy for NAS when it is coupled with a neural predictor. Recent work has proposed different instantiations of this framework, for example, using Bayesian neural networks or graph convolutional networks as the predictive model within BO. However, the analyses in these papers often focus on the full-fledged NAS algorithm, so it is difficult to tell which individual components of the framework lead to the best performance. In this work, we give a thorough analysis of the "BO + neural predictor" framework by identifying five main components: the architecture encoding, neural predictor, uncertainty calibration method, acquisition function, and acquisition optimization strategy. We test several different methods for each component and also develop a novel path-based encoding scheme for neural architectures, which we show theoretically and empirically scales better than other encodings. Using all of our analyses, we develop a final algorithm called BANANAS, which achieves state-of-the-art performance on NAS search spaces. We adhere to the NAS research checklist (Lindauer and Hutter 2019) to facilitate best practices, and our code is available at https://github.com/naszilla/naszilla.

1 Introduction

NAS seeks to automate the costly design of increasingly complex neural architectures. This work analyzes the BO + neural predictor framework component by component, introduces path encoding, and uses the findings to develop BANANAS, which performs strongly on NAS benchmarks.

  • NAS automates neural architecture design, which otherwise requires substantial engineering and domain knowledge.
  • The BO + neural predictor framework avoids architecture-distance functions and scales better than Gaussian-process models, but prior analyses obscure component-level effects.
  • The study evaluates five components: architecture encoding, neural predictor, uncertainty calibration, acquisition function, and acquisition optimization strategy.
  • The path encoding represents unique input-to-output paths in an architecture DAG and scales better than adjacency-matrix encoding while improving neural-predictor accuracy.
  • BANANAS, built from the component analyses, achieves state-of-the-art performance on NASBench-101 and is competitive on NASBench-201 datasets.
  • The experiments follow NAS research best practices, including established search spaces, statistically sufficient trials, and released code.

2 Societal Implications

The work aims to improve future deep learning research through neural architecture search, but its indirect role in applications limits control over its societal effects.

  • The method targets improved performance in future deep learning research but is one abstraction level removed from real applications.
  • Because downstream uses are varied, the authors have limited control over whether the work supports beneficial applications or harmful ones such as deepfake generation.

3 Related Work

Related NAS research includes evolutionary, reinforcement-learning, Bayesian-optimization, and gradient-descent methods. BANANAS differs by providing an in-depth component analysis of the BO + neural predictor framework rather than claiming to introduce that framework.

  • Recent NAS methods include evolutionary algorithms, reinforcement learning, Bayesian optimization, and gradient descent.
  • Earlier BO approaches required architecture-distance functions, while later work used neural models to predict validation accuracy.
  • Prior graph-neural-network BO papers did not ablate all framework components, motivating this work’s more comprehensive analysis.
  • Neural models had also been used in BO for hyperparameter optimization, primarily to reduce Gaussian-process BO complexity from cubic to linear time.
  • NASBench-101, NASBench-201, and NASBench-301 support fair and reproducible comparisons with tens of thousands of pretrained architectures; later studies found path encoding effective.

4 BO + Neural Predictor Framework

In this framework, Bayesian optimization searches for architectures minimizing validation error, while a repeatedly retrained neural predictor estimates unseen architectures’ performance.

  • Bayesian optimization seeks an architecture a* in search space A that minimizes validation error after fixed-dataset, fixed-epoch training.
  • At each iteration, a neural network trains on previously evaluated architectures and predicts validation accuracy for unseen architectures.

5 Analysis of the Framework

The section analyzes five components of the BO-plus-neural-predictor framework for NAS and combines the strongest choices into BANANAS. It introduces a path encoding, evaluates predictors and uncertainty methods, and reports component and overall NAS results.

  • Framework analysis: The framework study evaluates architecture encoding, neural predictor, uncertainty calibration, acquisition function, and acquisition optimization strategy.The experiments separately analyze these component choices before constructing the full algorithm.
  • Architecture encodings: The path encoding represents each architecture by binary features for input-to-output operation paths, avoiding arbitrary node ordering and reducing feature dependence.Unlike adjacency matrices, it maps each architecture to one encoding, although different architectures can share an encoding.
  • Architecture encodings: For DAGs sampled under the stated edge model, a set of n paths can contain all but less than 1/n^2 of the architecture probability for sufficiently large n.This theorem supports truncating the encoding to n paths with high probability.
  • Architecture encodings: 364-bit path encodings on NASBench-101 were truncated to 20 bits without performance loss, while 156-bit encodings on NASBench-201 were truncated to 30.Performance initially improved with truncation, which the authors attribute to reduced overfitting to rare paths.
  • Neural predictors: Feedforward predictors with path encodings and GCNs performed best on held-out NASBench-101 prediction, while feedforward networks ran faster than GCNs and VAEs.The held-out evaluation used MAE on 1,000 test architectures across 50 trials and multiple training-set sizes.
  • Uncertainty calibration: Ensemble-based predictors produced better uncertainty estimates than Bayesian neural networks, and the best combined NAS predictors were an ensemble of GCNs and an ensemble of feedforward networks.Uncertainty quality was assessed with RMSCE alongside predictive accuracy.
  • Acquisition: Mutation performed best for acquisition optimization, while the acquisition function had less effect on performance than other framework components and ITS performed best overall.These experiments used an ensemble of feedforward networks with path encoding and mutation-based optimization as specified in the setup.

6 BANANAS Experiments

The experiments evaluate BANANAS and its components across NASBench-101, NASBench-201, and the DARTS search space, with comparisons against diverse NAS algorithms. BANANAS ranks first on NASBench-101 and is competitive on NASBench-201, while the study also reports constraints affecting fair DARTS comparisons.

  • Acquisition optimization: Mutation performs best as the acquisition optimization strategy, suggesting that considering architectures closer by edit distance improves candidate selection.The comparison appears in the middle panel of Figure 6.1.
  • Experimental setup: The study evaluates NASBench-201 across CIFAR-10, CIFAR-100, and ImageNet-16-120 using a tabular dataset of 15625 architectures.The NASBench-201 search space uses a complete DAG on four nodes, with five possible operations per edge.
  • Performance on NASBench search spaces: The experiments compare BANANAS with NAS algorithms from evolutionary, Bayesian, reinforcement-learning, gradient-based, and other paradigms.The comparison includes random search, regularized evolution, BOHB, NASBOT, local search, TPE, BOHAMIANN, BONAS, REINFORCE, GP-based BO, AlphaX, GCN Predictor, and DNGO.
  • Performance on NASBench search spaces: BANANAS ranks first on NASBench-101, followed by local search and BONAS.The results are shown in Figure 6.1 (right), with additional NASBench-201 results reported in Appendix D.
  • Performance on the DARTS search space: On the DARTS search space, BANANAS is evaluated with 100 evaluations and 50 training epochs per selected architecture under a common test pipeline.The reported comparison uses mean test error over five random seeds for the best architecture found by each method, but other methods may use different evaluation settings.

7 Conclusion and Future Work

The paper analyzes the BO-plus-neural-predictor framework and uses that analysis to design BANANAS, including a path-based encoding and evaluations across NAS search spaces. It identifies multi-fidelity and successive-halving extensions as follow-up directions for reducing runtime without sacrificing accuracy.

  • Conclusion: The study analyzes five framework components: architecture encoding, neural predictor, uncertainty calibration, acquisition function, and acquisition optimization strategy.It tests several methods for each component within the BO-plus-neural-predictor framework.
  • Conclusion: The paper proposes a path-based encoding scheme that improves neural-predictor performance and uses the analysis to develop BANANAS.BANANAS is presented as an instantiation of the BO-plus-neural-predictor framework.
  • Conclusion: BANANAS achieves state-of-the-art performance on popular NAS search spaces.The conclusion states this as the outcome of combining the analyses into a final algorithm.
  • Future work: Multi-fidelity or successive-halving versions of BANANAS are proposed as follow-up ideas that could reduce runtime without sacrificing accuracy.The text presents these as future work rather than evaluated results in this paper.
  • Scope: The paper focuses on convolutional cell-based search spaces, although it states that the method can apply more broadly.These search spaces represent architectures as cells formed from DAGs and operations such as convolutions and pooling.

C Path Encoding Theory

The path encoding represents architectures through paths in their DAGs and can be truncated because long, rare paths contribute little under the random architecture procedure. This yields linear scaling in cell size while retaining essentially all relevant information.

  • Path Encoding: The path encoding records unique paths from the input node to the output node, with each path determined by node operations.The encoding contains one feature for each possible path, unlike the adjacency matrix’s edge-based representation.
  • Path Encoding: Adjacency-matrix features are highly dependent, whereas the path encoding is designed to provide a more interpretable representation for neural predictors.The adjacency matrix also scales quadratically in the number of nodes.
  • Truncation Argument: Random architecture generation makes most possible paths extremely unlikely, so the least-likely paths can be removed with arbitrarily small information loss.The procedure samples node operations and edges, then rejects graphs without an input-to-output path.
  • Caveats: The theorem does not establish that mutated architectures preserve the random-path distribution, and common paths may not be the most informative for accuracy prediction.Experiments are reported as evidence that truncation remains reasonable despite these caveats.
  • Theorem 5.1: The theorem’s proof uses the fact that short paths are much more likely than long paths and bounds the n shortest paths by length at most log_r n − 1.The argument compares expected path counts across lengths in the random DAG model.

D.2 Exhaustive Framework Experiment

The exhaustive experiment tests combinations of the strongest component choices rather than evaluating each component in isolation. Path-ITS-Mutation performs best, supporting the conclusions from the individual analyses.

  • Experimental Design: The experiment evaluates 18 configurations formed from acquisition functions, acquisition strategies, and neural predictors, using 500 trials per algorithm.The tested choices are {UCB, EI, ITS}, {mutation, mutation+random}, and {GCN, path encoding, truncated path encoding}.
  • Results: Path-ITS-Mutation is the overall best-performing configuration, matching the conclusion from the individual component experiments.Path-ITS-Mut+Rand and Trunc-ITS-Mut+Rand are the next best combinations.
  • Results: Mutation outperforms mutation+random, ITS outperforms UCB and EI, and path-based encodings outperform GCN in these combinations.The reported ordering suggests each tested component has a fairly linear relationship with performance.

D.3 Results on NASBench-201

NASBench-201 contains three image datasets but far fewer unique architectures than NASBench-101, and validation and test errors can diverge. BANANAS ties for best performance on CIFAR-10 and CIFAR-100 and eventually on ImageNet16-120 without retuning.

  • Dataset: NASBench-201 has 6,466 unique architectures after isomorphism removal, compared with about 423,000 in NASBench-101, and spans three image datasets.The datasets are CIFAR-10, CIFAR-100, and ImageNet16-120.
  • Evaluation Caveat: Validation and test errors are less correlated on NASBench-201, allowing validation-based search to overfit, especially on ImageNet16-120.On ImageNet16-120, the best-validation architecture has test error 53.8833, while the lowest overall test error is 53.1556.
  • Evaluation Caveat: The evaluation focuses on validation-error curves because test performance over time need not decrease strictly on NASBench-201.The reported curves average the best-test-error architecture found so far over 200 trials.
  • Results: Because the search space is extremely small, several algorithms tie for best performance on NASBench-201.This limits how distinctly the benchmark separates methods.
  • Results: BANANAS ties for best performance on CIFAR-10 and CIFAR-100, and ties after 40 GPU hours on ImageNet16-120.NASBOT and Gaussian-process BO reach top performance more quickly on ImageNet16-120.

D.4 NASBench-101 API

NASBench-101’s API does not support the most realistic evaluation protocol, so the authors compare two imperfect alternatives. Figure D.4 uses random validation errors, while overall trends remain consistent with earlier results.

  • The most realistic protocol pairs each architecture’s random validation error with its corresponding test error, but the NASBench-101 API does not support it.
  • The authors therefore choose either random validation errors with mean test error or mean validation errors with mean test error.
  • Figure D.4 uses random validation errors, and BANANAS still distinctly outperforms all other algorithms after 40 iterations.

D.5 Path encoding length

The authors test whether truncating the path encoding preserves BANANAS performance. On NASBench-201 CIFAR-10, reducing the encoding from 155 to 30 paths does not decrease performance and can improve it.

  • BANANAS is evaluated for 150 evaluations on NASBench-201 CIFAR-10 using path-encoding truncation lengths from 1 to 155.
  • Reducing the NASBench-201 path encoding from 155 to 30 paths causes no performance decrease.
  • Performance can improve after truncation, which the authors attribute to reduced overfitting to very rare paths in the full encoding.

E Best practices checklist for NAS research

The authors address the NAS research checklist through common benchmarks, shared evaluation settings, multiple experimental checks, and reported implementation details. They also acknowledge reproducibility limitations for DARTS experiments.

  • Benchmarks and code: The study uses NASBench-101, NASBench-201, and DARTS, with precomputed architecture accuracies for the NASBench benchmarks.
  • Fair comparisons: All compared methods use the same NAS benchmarks, training code, hyperparameters, and controlled experimental setup.
  • Experimental evaluation: The experiments report performance over time, compare against random search, and include ablation studies guiding BANANAS’s construction.
  • Reproducibility: DARTS experiments use four BANANAS trials without a fully deterministic implementation, although average final error differed by at most 0.1%.
  • Reporting: The authors report end-to-end NAS time, experimental details, and initial hyperparameter tuning, while leaving final-evaluation hyperparameters unchanged.
Loading 1910.11858v3…