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:
- Sample-based methods (RL/Evolution): These train hundreds or thousands of models from scratch, often requiring hundreds or thousands of GPU-days.
- 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:
- 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.
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