PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Architecture Search with Bayesian Optimisation and Optimal Transport

Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, Eric Xing

arXiv:1802.07191v3cs.LGstat.ML

TL;DR

Neural architecture search requires Bayesian optimisation methods that can handle expensive evaluations over structured architecture spaces. The paper introduces NASBOT, a Gaussian-process BO framework built around the efficiently computable OTMANN optimal-transport distance. NASBOT outperforms other alternatives on model-selection tasks involving MLPs and CNNs, although the reported CIFAR10 experiments remain below current state-of-the-art results obtained with substantially more computation.

  • Problem

    Conventional Bayesian optimisation mainly targets Euclidean or categorical domains, limiting model selection while neural architecture evaluations require expensive training and validation.

  • Method

    NASBOT applies Gaussian-process Bayesian optimisation to neural architectures using OTMANN, an efficiently computable optimal-transport distance, plus evolutionary acquisition optimisation.

  • Results

    NASBOT outperforms other alternatives on model-selection tasks for multi-layer perceptrons and convolutional neural networks.

  • Takeaways & Limitations

    OTMANN may have applications beyond Bayesian optimisation, while NASBOT finds better MLP and CNN architectures more efficiently than other baselines across several datasets.

  • Takeaways & Limitations

    The CIFAR10 experiments fall short of current state-of-the-art results, whose competing studies use several orders of magnitude more computation and CNN-specialised search spaces.

Abstract

from arXiv · show

Bayesian Optimisation (BO) refers to a class of methods for global optimisation of a function $f$ which is only accessible via point evaluations. It is typically used in settings where $f$ is expensive to evaluate. A common use case for BO in machine learning is model selection, where it is not possible to analytically model the generalisation performance of a statistical model, and we resort to noisy and expensive training and validation procedures to choose the best model. Conventional BO methods have focused on Euclidean and categorical domains, which, in the context of model selection, only permits tuning scalar hyper-parameters of machine learning algorithms. However, with the surge of interest in deep learning, there is an increasing demand to tune neural network \emph{architectures}. In this work, we develop NASBOT, a Gaussian process based BO framework for neural architecture search. To accomplish this, we develop a distance metric in the space of neural network architectures which can be computed efficiently via an optimal transport program. This distance might be of independent interest to the deep learning community as it may find applications outside of BO. We demonstrate that NASBOT outperforms other alternatives for architecture search in several cross validation based model selection tasks on multi-layer perceptrons and convolutional neural networks.

1 Introduction

Bayesian optimisation is well suited to expensive, noisy model-selection evaluations, but conventional methods do not directly address neural architecture spaces. NASBOT extends GP-based BO to neural architectures using an efficiently computable optimal-transport distance and evaluates it against existing search approaches.

  • Motivation: Bayesian optimisation uses Bayesian models to infer unexplored function values and guide evaluations when black-box evaluations are noisy and expensive.Its machine-learning use case includes selecting hyper-parameters by training models and measuring validation accuracy.
  • Motivation: Neural architecture search requires model selection over architecture spaces, where training and validation evaluations are particularly expensive.Most BO work had focused on Euclidean or categorical domains, which primarily support scalar hyper-parameter tuning.
  • Challenges: GP-based BO requires both a similarity kernel over candidate architectures and a method for maximising the acquisition function.These requirements are straightforward in conventional domains but challenging when each candidate is a neural network architecture.
  • Contributions: OTMANN defines an efficiently computable pseudo-distance for neural network architectures using an optimal transport program.The distance is designed to compare architectural structure and computation for use in a GP kernel.
  • Contributions: NASBOT combines Bayesian optimisation for neural architectures with an evolutionary algorithm that optimises the acquisition function.The framework targets architecture-search model-selection tasks for both multi-layer perceptrons and convolutional neural networks.
  • Empirical evaluation: NASBOT is reported to outperform other baselines on model-selection tasks for multi-layer perceptrons and convolutional neural networks.The paper contrasts this with prior BO architecture-search methods applied only to feed-forward structures.

2 Set Up

The paper formulates architecture search as noisy optimisation over neural-network graphs and reviews GP-based BO as sequential posterior-guided evaluation. It then defines architecture similarity through distances that can be converted into GP kernels.

  • Set Up: Architecture search maximises validation performance over neural-network architectures observed through potentially noisy evaluations.The target is to make the gap between the optimal architecture and the best evaluated architecture vanish as evaluations increase.
  • Gaussian-process BO: A Gaussian process models the unknown objective using a mean function and covariance kernel, with posterior quantities computed from observed evaluations.The observations include additive Gaussian noise, and the posterior is updated from the evaluation data.
  • Gaussian-process BO: Bayesian optimisation selects each next architecture by maximising an acquisition function derived from the posterior model.Expected improvement measures improvement over the current best value and is the acquisition used in this work.
  • Architecture search: In architecture search, the kernel encodes architectural similarity, while BO balances exploitation of promising networks against exploration of less-known ones.Similarity allows performance on one network to inform beliefs about another network.
  • Architecture representation: Neural networks are represented as directed graphs whose vertices are layers and whose edges specify how layer outputs feed subsequent layers.Layer labels identify operations, inputs from multiple parents are concatenated, and decision layers produce or aggregate predictions.
  • Architecture similarity: The architecture distance is converted into a kernel using κ(x, x′) = e^−βd(x,x′)^p, generalising familiar distance-based kernels.For Euclidean domains with L2 distance, p = 1 and p = 2 correspond to Laplacian and Gaussian kernels, respectively.

3 The OTMANN Distance

OTMANN compares neural-network architectures by optimally matching layer masses while penalizing label mismatches, structural differences, and non-assignment. Its formulation is efficiently solvable as an optimal-transport program and is a pseudo-distance under mild conditions.

  • OTMANN construction: OTMANN defines architecture distance by matching computation-associated layer masses while penalizing operation-label and structural-position mismatches.Layer masses quantify layer significance, with processing-layer mass based on computation and incoming units.
  • OTMANN construction: Layer masses represent computation for processing layers, while input and output masses are set as a fraction ζ of total processing-layer mass; experiments use ζ = 0.1.Decision layers receive significant mass because they directly influence network outputs.
  • Matching objective: The matching objective combines label-mismatch, non-assignment, and structural penalties, with costs chosen so similar layers are preferred over non-assignment when structurally compatible.The label matrix assigns zero cost to identical layers, less than one to similar layers, and infinite cost to disparate layers.
  • Structural penalty: Structural penalties use shortest, longest, and random-walk path lengths to capture information flow and identify layers occupying similar network positions.Similar path lengths imply similar structural positions and support efficient optimal-transport computation.
  • Properties and interpretation: Architectures with small OTMANN distance tend to have similar validation performance, while t-SNE places similar architectures close together.These illustrations are reported as additional evidence that OTMANN is meaningful for architecture search.

4 NASBOT

NASBOT applies Gaussian-process Bayesian optimisation to neural architectures using an OTMANN-based distance kernel and an evolutionary search over the acquisition function. The framework trades higher selection overhead for judicious architecture evaluations when model evaluations are expensive.

  • NASBOT framework: NASBOT specifies a neural-architecture kernel and an acquisition-function optimiser to implement Bayesian optimisation over architectures.The method uses a negative exponentiated combination of OTMANN distance and normalized distance as its kernel form.
  • NASBOT framework: The kernel combines OTMANN distance d and normalized distance d̄, although the authors do not establish that this function is a valid kernel.No negative kernel-matrix eigenvalues were encountered in the experiments.
  • Acquisition optimisation: An evolutionary algorithm selects previously evaluated networks with probability increasing in acquisition value, mutates them, and iterates over the resulting candidate pool.Mutations can alter layer units, add or delete layers, or change existing connectivity.
  • Acquisition optimisation: Evolutionary search is used for the analytically available acquisition function, while expensive neural-network evaluations motivate Bayesian optimisation’s more selective point choices.The paper contrasts cheap acquisition evaluations with costly training evaluations.
  • Extensions: The framework can incorporate dropout, regularization, batch normalization, and other scalar hyperparameters by augmenting layer labels or combining kernels.These extensions are described as additional flexibility of NASBOT/OTMANN.

5 Experiments

Experiments compare NASBOT with random search, an evolutionary algorithm, and TreeBO across regression MLP and image-classification CNN model-selection tasks. NASBOT is reported as the most consistent method, while the Cifar10 results remain below current state of the art under a much smaller computational budget.

  • Methods and datasets: NASBOT is compared with RAND, EA, and TreeBO using matched architecture-search spaces, with RAND differing only by replacing the GP acquisition with random samples.The comparison covers six regression datasets using MLPs and Cifar10 image classification using CNNs.
  • Experimental setup: The evaluation uses asynchronously parallel 2–4 GPU setups, allowing each method to redeploy a job when a model evaluation finishes.The first six datasets use train-validation-test splits of 0.6–0.2–0.2.
  • Results: NASBOT is the most consistent method across the reported cross-validation experiments.Figure 2 plots each method’s best validation score against time, with lower MSE or classification error being better.
  • Results: 46.13s was NASBOT’s average time to select the next architecture, compared with 26.43s for RAND, 0.19s for EA, and 7.83s for TreeBO.Model training and validation took approximately 10–40 minutes depending on model size, making selection overhead relevant to the comparison.
  • Results: The best architectures commonly included long skip connections and multiple decision layers across many datasets.These are recurring architectural features among the illustrated architectures found by the search.
  • Scope and limitations: Cifar10 results fall short of current state of the art, whose computation for training individual models and the number of trained models were several orders of magnitude greater.The authors also note that those methods use CNN-specialized search spaces, whereas NASBOT uses a general model space.

6 Conclusion

The paper introduces OTMANN, an efficiently computable optimal-transport architecture distance, and NASBOT, a Bayesian-optimisation framework for neural architecture search. NASBOT finds better architectures for MLPs and CNNs more efficiently than other baselines on several datasets.

  • 6 Conclusion: OTMANN is an efficiently computable distance for neural network architectures formulated through optimal transport.The optimal-transport formulation provides an efficient way to solve the architecture-matching program.
  • 6 Conclusion: NASBOT is a Bayesian-optimisation framework for searching neural network architectures.
  • 6 Conclusion: NASBOT finds better architectures for MLPs and CNNs more efficiently than other baselines on several datasets.
  • A.1 Optimal Transport Reformulation: The OT program represents layer masses as supplies and demands, augments the cost matrices with non-assignment layers, and minimises total transport cost.The added row and column encode non-assignment, with transport costs controlling whether masses are matched or left unassigned.
  • A.1 Optimal Transport Reformulation: Theorem 2 establishes that the original architecture-matching problem and its optimal-transport formulation have the same minimum and recoverable solutions.

A.2 Distance Properties of OTMANN

The OTMANN solution is a pseudo-distance under a triangle-inequality condition on the mislabel costs. Its zero-distance equivalence is intentional for some functionally equivalent networks, but the induced topology may also equate functionally dissimilar networks and is not Wasserstein.

  • A.2 Distance Properties of OTMANN: If the mislabel cost matrix satisfies the triangle inequality, OTMANN is nonnegative, symmetric, zero on identical networks, and obeys the triangle inequality.
  • A.2 Distance Properties of OTMANN: OTMANN is a pseudo-distance rather than a true distance because distinct network descriptors can have zero distance.Figure 3 gives networks with different descriptors and zero distance despite matching functionality.
  • A.2 Distance Properties of OTMANN: The zero-distance example is desirable because both differently described CNNs implement the same sequence of convolutional operations.
  • A.2 Distance Properties of OTMANN: The authors leave open whether OTMANN’s induced topology can equate functionally dissimilar networks, deferring equivalence-class analysis to future work.
  • A.2 Distance Properties of OTMANN: OTMANN is not a Wasserstein distance because the compared networks determine both the mass supports and the cost matrices.

A.3 Implementation & Design Choices

The implementation specifies architecture-label costs, structural path penalties, and OTMANN validation through visual topology and distance–performance relationships.

  • Label Penalty Matrices: OTMANN uses label mismatch penalties for transporting mass between CNN layer types, with unshown input/output layers matching only their counterparts.The matrix covers conv3, conv5, conv7, max-pool, avg-pool, fc, and softmax labels; blank entries represent infinite cost.
  • Path Computation: Algorithm 1 computes all path lengths in O(|E|) time, with topological sorting also taking O(|E|) time.The topological ordering ensures child path quantities are computed after their predecessors.
  • Structural Penalties: The CNN structural penalty averages four path-based cost matrices, while the MLP version averages costs for all layers, rectifiers, and sigmoidal layers.Considering layer types separately accounts for different information flow due to different operations.
  • Distance Validation: OTMANN assigns similar architectures nearby in t-SNE embeddings, indicating a meaningful topology over neural network architectures.The visualization compares embeddings from the OTMANN distance and its normalised version.
  • Distance Validation: When OTMANN distance is small, validation-error differences are close to zero; larger distances correspond to greater variance in those differences.The analysis uses 300 networks and approximately 45K pairwise points for each dataset scatter plot.

B Implementation of NASBOT

NASBOT combines an ensemble of distance-based GP kernels with evolutionary acquisition optimisation to search neural-network architectures efficiently.

  • B.1 The Kernel: NASBOT uses a negative exponentiated OTMANN distance as its kernel, combining distances and normalised distances computed with multiple structural-cost settings.The reported settings use νstr values {0.1, 0.2, 0.4, 0.8}, p = 1, and p̄ = 2.
  • B.1 The Kernel: The kernel ensemble weights individual distance contributions while combining multiple topology choices instead of selecting one best distance.This lets NASBOT account for different topologies induced by the distance variants.
  • B.1 The Kernel: NASBOT samples its 11 hyper-parameters from their posterior under the GP likelihood rather than relying solely on marginal-likelihood maximisation.The authors motivate this choice by possible over-fitting and the small number of observations available for expensive neural-network training.
  • B.2 Optimising the Acquisition Function: An evolutionary algorithm optimises the acquisition function by selecting high-acquisition evaluated networks and mutating them into candidate architectures.The mutations can alter units, layers, or connectivity, and the acquisition is cheap enough to evaluate over many candidates.
  • B.2 Optimising the Acquisition Function: Candidate-selection probabilities are proportional to exp(g(zi)/σ), making higher-valued previously evaluated architectures more likely mutation sources.The standard deviation σ normalises for different ranges of function values.
  • B.2 Optimising the Acquisition Function: NASBOT expands its evolutionary search from a small initial neighborhood toward a larger region as the Bayesian-optimisation process advances.The implementation increases the total evolutionary budget and sets Nmut to O(√nEA).

B.3 Other Implementation Details

The experiments constrain the architecture domain, initialise all methods identically, and use parallel evaluation plus specified baseline procedures.

  • Initialisation: All methods start with the same initial pool of 10 feed-forward networks, including VGG-like and blocked feed-forward CNN structures.The same initial networks also initialise the evolutionary acquisition optimiser.
  • Search Domain: NASBOT and competing methods search architectures constrained to at most 60 layers, degree 5, 200 edges, and 1024 units per layer.Each layer must contain at least 8 units, and violating candidate architectures are skipped.
  • Layer Types: CNNs use stride-2 pooling, stride-1 or stride-2 convolutions, and relu activations across all layers.These choices define the CNN layer-type and operation settings used in the search.
  • Parallel BO: Parallel Bayesian optimisation evaluates multiple models concurrently using the hallucination technique.The technique is applied to handle parallel BO in the experiments.
  • Implementation Caveat: Many NASBOT parameter and specification choices were made arbitrarily, although the reported implementation worked efficiently with the authors’ first choices.This is an implementation-design caveat rather than a comparison result.
  • Baselines: RAND preserves NASBOT’s evolutionary schedule and search space but replaces GP-acquisition values with random samples for selecting evaluations.EA fixes Nmut at 10, while the custom TreeBO implementation uses a depth of 60 and the stated domain constraints.

C.2 Details on Training

Training and evaluation use periodic validation during optimisation, followed by retraining selected architectures and measuring held-out test performance.

  • MLP Training: MLP architectures are trained with stochastic gradient descent using step size 10^-5, batch size 256, and 20,000 iterations.Validation MSE is computed every 100 iterations, and the minimum achieved validation MSE is returned.
  • Final Evaluation: After architecture selection, each optimal network is retrained and its test MSE or classification error is computed.The selected iteration is determined from the minimum validation performance during retraining.
  • CNN Training: CNN final training runs for 120,000 iterations and reports test classification error at the iteration with minimum validation classification error.This evaluation follows the same general optimisation procedure used during model selection, with the longer CNN training schedule.

C.3 Optimal Network Architectures and Initial Pool

NASBOT-generated architectures commonly used long skip connections and multiple decision layers. The initial architecture pools included VGG-19 among the CNN candidates, while shorter-training validation rankings did not always predict longer-training performance.

  • Optimal Network Architectures: NASBOT’s optimal architectures consistently contained long skip connections and multiple decision layers.
  • Initial Pool: The initial pools comprised CNN and MLP architectures, with VGG-19 included among the CNN candidates.
  • Initial Pool: After 24K training iterations, every method surpassed VGG-19, but TreeBO and RAND fell below VGG-19 when evaluated under the reported comparison.The authors suggest shorter-training performance may not correlate exactly with longer-training performance.

C.4 Ablation Studies and Design Choices

The ablations evaluate NASBOT’s distance kernel, evolutionary acquisition modifiers, and hyperparameter choices. The combined distance and modifier configurations performed best in their comparisons, while performance was relatively insensitive to p and p̄.

  • Experimental Setting: The synthetic ablations evaluated NASBOT design choices because computational constraints prevented conducting them directly on the model-selection tasks.
  • Distance Design: The combined normalised and unnormalised distance kernel outperformed either distance used individually.
  • Evolutionary Acquisition: Using all nine evolutionary modifiers outperformed using only computational-unit modifiers or only network-structure modifiers.
  • Kernel Parameters: Performance was not particularly sensitive to the tested choices of p and p̄.
  • Related Work: The study’s related-work discussion contrasts evolutionary and reinforcement-learning search with Bayesian optimisation for expensive architecture evaluations.
Loading 1802.07191v3…