Efficient Forward Architecture Search

Hanzhang Hu, John Langford, Rich Caruana, Saurajit Mukherjee, Eric Horvitz, Debadeepta Dey

TL;DR

Petridish is a novel Neural Architecture Search (NAS) algorithm that grows networks forward by iteratively adding shortcut connections, much like gradient boosting. By treating NAS as a feature selection problem and using $L_1$ regularization to pick the best connections, it finds competitive models in just a few GPU-days and excels at "warm-starting" from existing architectures.

What Problem Does This Paper Address?

Designing neural network architectures is traditionally a manual, "trial and error" process for experts. While Neural Architecture Search (NAS) aims to automate this, existing methods often fall into two expensive camps:

  1. Sample-based methods (RL/Evolution): These train hundreds or thousands of models from scratch, often requiring hundreds or thousands of GPU-days.
  2. Weight-sharing/Backward methods: These start with a massive "super-graph" containing all possible connections and prune them down. While faster, they require significant domain knowledge to build the initial graph and cannot easily expand an existing model if more compute becomes available.

The authors identify a critical gap: the field needs an efficient forward search that can grow a model from small to large, or take a pre-existing model and make it better without starting over.

Methods: The Petridish Algorithm

The authors introduce Petridish, an algorithm inspired by forward stage-wise linear regression and gradient boosting.

  • The Boosting Analogy: In gradient boosting, you add "weak learners" to correct the errors of the current model. Petridish does this by adding shortcut connections between existing layers. These shortcuts act as weak learners that help reduce the gradient of the loss.
  • Joint Weak Learning: To avoid the cost of training every possible connection combination separately, Petridish trains a "union" of all possible shortcuts at once.
  • Sparsity-Inducing Selection: They apply $L_1$ regularization (Lasso) to the weights of these candidate shortcuts. This encourages the network to "pick" only the most useful connections. After a few epochs, the top $I_{max}$ connections are kept, and the rest are discarded.

To ensure that searching for new connections doesn't break the already-trained "parent" model, the authors implement two custom operations:

Petridish architecture search using stop-gradient (sg) and stop-forward (sf) operations.
  • Stop-gradient (sg): Prevents the weak learners from affecting the weights of the parent model during the selection phase.
  • Stop-forward (sf): Ensures the parent model's output remains unchanged until the new connections are finalized.

The algorithm was tested on both cell-search (finding a repeatable block) and macro-search (growing a general, non-repeating network).

Key Insights and Ideas

  • NAS as Feature Selection: The paper's most elegant insight is framing NAS as a generalization of feature selection for linear regression. This allows them to borrow proven mathematical techniques like forward stage-wise regression.
  • Amortized Growth: By training the parent model and the candidate shortcuts concurrently, the "search" cost is just a constant factor of the training cost.
  • Macro-Search is Underrated: Traditionally, NAS researchers focused on "cells" because macro-search was thought to be too difficult. Petridish shows that macro-search can actually be highly competitive and cost-effective.
  • Warm-Starting: Unlike pruning methods, Petridish is uniquely suited for "lifelong learning." If you have a model in production and suddenly get a more powerful GPU, Petridish can grow that specific model further rather than starting a new search from scratch.

Key Results

The researchers evaluated Petridish on standard benchmarks including CIFAR-10, ImageNet (ILSVRC), and Penn Tree Bank (PTB).

  • Efficiency: Petridish found competitive models on CIFAR-10 in only 5 GPU-days (using a single GTX 1080). For context, early NAS methods took 1,800+ GPU-days.
  • Accuracy:
    • On CIFAR-10, it achieved a test error of 2.83% - 2.87% with roughly 2.5M parameters.
  • When transferred to ImageNet, the cell-search model achieved a 26.0% top-1 error, putting it on par with state-of-the-art human-designed and NAS-generated models like NASNet-A and DARTS.
  • Pareto Front: The algorithm naturally produces a "gallery" of models at different stages of growth, allowing users to choose the best trade-off between computational cost and accuracy.
Pareto front comparing Petridish models against other NAS methods on Test Error vs. Multi-adds.

Limitations and Future Work

  • Search Variance: Because the model grows based on noisy training signals, it can sometimes pick sub-optimal shortcuts. The authors mitigated this by running multiple parallel "workers," which adds some computational overhead.
  • Macro-Search Transfer: While macro-search performed excellently on CIFAR-10, its performance gap widened slightly compared to cell-search when transferred to ImageNet. The authors suggest this might be because the default "transition cells" (used for down-sampling) weren't optimized for the more complex ImageNet dataset.
  • Language Modeling: On the PTB dataset, the authors noted that no NAS algorithm (including theirs) significantly outperformed a well-tuned random search, suggesting that PTB might not be the best benchmark for evaluating NAS efficiency.

Summary updated

Abstract

We propose a neural architecture search (NAS) algorithm, Petridish, to iteratively add shortcut connections to existing network layers. The added shortcut connections effectively perform gradient boosting on the augmented layers. The proposed algorithm is motivated by the feature selection algorithm forward stage-wise linear regression, since we consider NAS as a generalization of feature selection for regression, where NAS selects shortcuts among layers instead of selecting features. In order to reduce the number of trials of possible connection combinations, we train jointly all possible connections at each stage of growth while leveraging feature selection techniques to choose a subset of them. We experimentally show this process to be an efficient forward architecture search algorithm that can find competitive models using few GPU days in both the search space of repeatable network modules (cell-search) and the space of general networks (macro-search). Petridish is particularly well-suited for warm-starting from existing models crucial for lifelong-learning scenarios.
BibTeX
@inproceedings{hu2019efficient,
  author = {Hanzhang Hu and John Langford and Rich Caruana and Saurajit Mukherjee and Eric Horvitz and Debadeepta Dey},
  title = {{Efficient Forward Architecture Search}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure