Regularized Evolution for Image Classifier Architecture Search

Esteban RealA. AggarwalYanping HuangQuoc V. Le

article2019AAAI3,428 citationsOutstanding Paper Award

Demonstrates that a simple evolutionary algorithm using aging tournament selection finds high-performing image classifiers faster than reinforcement learning, producing the state-of-the-art AmoebaNet architecture.

Listen

Researchers have long relied on expert hand-design to create high-accuracy convolutional neural networks for image classification, a process that is slow and difficult to scale. Automated architecture search offers a way to accelerate discovery, yet evolutionary methods had consistently produced models inferior to both human designs and those found by reinforcement learning. This paper set out to test whether a simple modification to evolutionary search could close that gap while remaining computationally practical.

The authors introduced aging evolution, a variant of tournament selection in which the oldest model in a fixed-size population is removed at each step rather than the weakest performer. They applied this algorithm, along with two basic mutations, inside the established NASNet search space. Controlled experiments evaluated 20 000 architectures on CIFAR-10 using identical training code and hardware for evolution, reinforcement learning, and random search; the resulting architectures were then enlarged and retrained on ImageNet.

Evolution reached competitive accuracy earlier than reinforcement learning and matched its final quality after the full search budget. The best architecture found, AmoebaNet-A, achieved 82.8 % top-1 accuracy on ImageNet at roughly 87 million parameterson par with the best reinforcement-learning result of similar sizeand set a new state-of-the-art of 83.9 % top-1 when scaled to 469 million parameters. Models discovered by evolution also required fewer floating-point operations than those found by reinforcement learning at comparable accuracy. Aging proved advantageous over standard tournament selection across multiple small-scale settings.

These outcomes show that evolution can be both simpler to implement and faster under resource constraints than reinforcement learning, while still producing deployable classifiers that exceed prior human-designed and automatically discovered networks. The approach therefore provides a practical alternative when compute budgets are limited or when rapid early progress matters. Further work could test the method on larger or different search spaces, quantify speed advantages more precisely, and examine whether the discovered connectivity patterns generalize to other vision tasks. Results are tied to the NASNet space and the CIFAR-10/ImageNet regime; broader validation would strengthen confidence in wider applicability.

arXiv: 1802.01548
  • Paper: Neural Architecture Search with Reinforcement Learning, Barret Zoph et al. (2016). This foundational paper introduces neural architecture search with reinforcement learning, directly establishing the methodology and search spaces that the source paper adapts and improves upon through evolutionary algorithms.
  • Paper: Learning Transferable Architectures for Scalable Image Recognition, Barret Zoph et al. (2018). Reading this work on NASNet provides critical context on cell-based architecture search and reinforcement learning baselines that the source paper evaluates and surpasses using regularized evolution.
Cover for Regularized Evolution for Image Classifier Architecture Search

Abstract

The effort devoted to hand-crafting neural network image classifiers has motivated the use of architecture search to discover them automatically. Although evolutionary algorithms have been repeatedly applied to neural network topologies, the image classifiers thus discovered have remained inferior to human-crafted ones. Here, we evolve an image classifierAmoebaNet-Athat surpasses hand-designs for the first time. To do this, we modify the tournament selection evolutionary algorithm by introducing an age property to favor the younger genotypes. Matching size, AmoebaNet-A has comparable accuracy to current state-of-the-art ImageNet models discovered with more complex architecture-search methods. Scaled to larger size, AmoebaNet-A sets a new state-of-the-art 83.9% top-1 / 96.6% top-5 ImageNet accuracy. In a controlled comparison against a well known reinforcement learning algorithm, we give evidence that evolution can obtain results faster with the same hardware, especially at the earlier stages of the search. This is relevant when fewer compute resources are available. Evolution is, thus, a simple method to effectively discover high-quality architectures.

Table of Contents

  • Introduction
  • Related Work
  • Methods
  • Search Space
  • Evolutionary Algorithm
  • Results
  • Comparison With RL and RS Baselines
  • ImageNet Results
  • Discussion
  • Supplements
  • Conclusion
  • Acknowledgments
  • References

Knowls

  1. Knowl 1 — Regularized Evolution (Aging Evolution) for Neural Architecture Search

    algorithm

    Regularized evolution (also termed aging evolution) is an asynchronous population-based evolutionary algorithm that introduces an age-based culling mechanism to standard tournament selection. The population of architectures is managed as a first-in, first-out (FIFO) queue of constant capacity PP. In each evolutionary cycle, a tournament sample of size SS is drawn uniformly at random with replacement from the population. The candidate with the highest validation accuracy in this sample is selected as the parent. A single mutation operator is applied to the parent architecture to produce a child architecture. The child is trained, evaluated on validation data, and pushed to the back of the queue (as well as recorded in a global history). To maintain a constant population size PP, the oldest individual in the population—the one located at the front of the queue—is removed and discarded, regardless of its performance.

    Input: Population size PP, tournament sample size SS, total search cycles CC
    Output: Architecture with the highest validation accuracy found in history
    population = empty_queue()
    history = empty_set()
    while size(population) < P:
        arch = RANDOM_ARCHITECTURE()
        accuracy = TRAIN_AND_EVAL(arch)
        model = (arch, accuracy)
        push_back(population, model)
        add(history, model)
    while size(history) < C:
        sample = empty_set()
        while size(sample) < S:
            candidate = UNIFORM_RANDOM_SAMPLE(population)
            add(sample, candidate)
        parent = MODEL_WITH_HIGHEST_ACCURACY(sample)
        child_arch = MUTATE(parent.arch)
        child_accuracy = TRAIN_AND_EVAL(child_arch)
        child_model = (child_arch, child_accuracy)
        push_back(population, child_model)
        add(history, child_model)
        dead_model = pop_front(population)
        discard(dead_model)
    return MODEL_WITH_HIGHEST_ACCURACY(history)

    The algorithm is parallelized asynchronously across multiple compute workers processing the main loop. In architecture search on CIFAR-10, the population size is set to P=100P=100, the sample size is set to S=25S=25, and the search terminates after C=20,000C=20{,}000 models are evaluated.

  2. Knowl 2 — Mechanism of Aging Evolution as Noise Regularization

    model/method

    In neural architecture search, individual model training is stochastic due to random parameter initialization, data shuffling, and stochastic regularization. Consequently, the observed validation accuracy reflects both the intrinsic fitness of the architecture and training noise. In standard non-aging tournament selection, an architecture that achieves high accuracy due to positive noise (a 'lucky' training run) can remain in the population indefinitely, continuously producing offspring and biasing the search away from broader exploration.

    Under aging evolution (regularized evolution), every model has a strictly bounded lifespan equal to PP cycles, where PP is the population size. An architecture genotype cannot persist indefinitely through a single lucky model; it can only remain in the population across multiple generations if its mutated offspring repeatedly achieve high accuracy upon re-initialization and re-training. This requirement biases selection toward architectures that reliably train well across independent runs rather than individual models that were fortuitously trained, serving as a form of mathematical regularization against evaluation noise.

  3. Knowl 3 — ImageNet Classification Benchmark Results for AmoebaNet-A

    data/table

    The top architecture discovered through regularized evolution on CIFAR-10, named AmoebaNet-A, was scaled up and evaluated on the ImageNet dataset (1.2M training images, 50k validation images, resized to 331×331331\times 331). The scaled models were trained using distributed synchronous SGD across 100 P100 GPUs with RMSProp, label smoothing, auxiliary classifiers, and ScheduledDropPath.

    Model # Parameters # Multiply-Adds Top-1 / Top-5 Accuracy (%)
    Inception-ResNet V2 55.8M 13.2B 80.4 / 95.3
    ResNeXt-101 83.6M 31.5B 80.9 / 95.6
    PolyNet 92.0M 34.7B 81.3 / 95.8
    Dual-Path-Net-131 79.5M 32.0B 81.5 / 95.8
    GeNet-2 (Evolution) 156M 72.1 / 90.4
    Block-QNN-B 75.7 / 92.6
    Hierarchical (Evolution) 64M 79.7 / 94.8
    NASNet-A (RL) 88.9M 23.8B 82.7 / 96.2
    PNASNet-5 (SMBO) 86.1M 25.0B 82.9 / 96.2
    AmoebaNet-A (N=6,F=190N=6, F=190) 86.7M 23.1B 82.8 / 96.1
    AmoebaNet-A (N=6,F=448N=6, F=448) 469M 104B 83.9 / 96.6

    At comparable model size (N=6,F=190N=6, F=190, 86.7M parameters, 23.1B multiply-adds), AmoebaNet-A matches the state-of-the-art accuracy of models generated by reinforcement learning (NASNet-A) and progressive neural architecture search (PNASNet-5). When scaled to a large parameter capacity (N=6,F=448N=6, F=448, 469M parameters, 104B multiply-adds), AmoebaNet-A achieves 83.9% top-1 and 96.6% top-5 accuracy, establishing a new state of the art and outperforming all prior human-designed and automatically searched architectures.

  4. Knowl 4 — NASNet Search Space and Cell Mutation Operators

    model/method

    The neural network search space is parameterized by two modular cells: a normal cell (which preserves spatial resolution) and a reduction cell (which reduces spatial resolution by a factor of 2 via stride 2 operations). The overall network consists of a stem followed by three stacks of NN normal cells separated by reduction cells. The search algorithm determines the internal topology of both the normal cell and the reduction cell independently.

    Each cell is a directed acyclic graph receiving two input hidden states (the outputs of the previous two cells, labeled 00 and 11) and constructing 5 successive hidden states via pairwise combinations. A pairwise combination selects two existing hidden states j,k<ij, k < i, applies an operation to each, and sums the results: hi=opA(hj)+opB(hk)h_i = \text{op}_A(h_j) + \text{op}_B(h_k). Any hidden states that are not consumed as an input to another combination are concatenated to form the final cell output.

    Architecture mutation operates via three stochastic transformations:

    1. Hidden state mutation: Randomly chooses either the normal or reduction cell, selects one of the 5 pairwise combinations, selects one of its two input branches, and reassigns its input hidden state to any existing hidden state within the cell such that no recurrent cycles are created.
    2. Op mutation: Randomly chooses a cell, combination, and branch, and replaces the existing operation with an operation chosen uniformly at random from the candidate pool: identity (none), 3×33\times 3, 5×55\times 5, or 7×77\times 7 separable convolutions, 3×33\times 3 average pooling, 3×33\times 3 max pooling, 3×33\times 3 dilated separable convolution, or 1×71\times 7 followed by 7×17\times 1 separable convolution.
    3. Identity mutation: Leaves the architecture unchanged, chosen with a fixed probability of 0.050.05.
  5. Knowl 5 — Search Efficiency and Computational Complexity: Evolution vs. Reinforcement Learning and Random Search

    empirical result

    In controlled side-by-side experiments on CIFAR-10 evaluating 20,00020{,}000 small candidate models (N=3,F=24N=3, F=24, trained for 25 epochs across 450 K40 GPUs for ~7 days), regularized evolution, reinforcement learning (RL with an LSTM controller), and random search (RS) were evaluated under identical training and evaluation code:

    • Search speed: Regularized evolution reaches half-maximum validation accuracy in approximately half the time (or number of evaluated models) required by RL, indicating superior efficiency in compute-constrained scenarios where early stopping is required.
    • Asymptotic accuracy: When allowed to run for the full 20,00020{,}000 evaluations, evolution and RL converge to comparable validation accuracy, and both outperform random search.
    • Computational complexity of discovered architectures: When top-performing architectures from each search method are augmented to full size (N=6,F=32N=6, F=32), evolved architectures achieve lower FLOPs and parameter counts than RL models for equivalent test accuracy, and achieve higher test accuracy than random search for equivalent FLOPs.
  6. Knowl 6 — CIFAR-10 Architecture Augmentation and Test Results

    data/table

    To evaluate discovered cell topologies at full capacity, architectures found during the small-model search phase (N=3,F=24N=3, F=24, 25 epochs) undergo model augmentation: the number of cell stacks is increased to N=6N=6, the filter count is increased to F=32F=32 or F=36F=36, and the network is trained on CIFAR-10 for 600 epochs using SGD with momentum (0.9), cosine learning rate decay (initial rate 0.024), weight decay (5×1045\times 10^{-4}), ScheduledDropPath (survival probability scaling to 0.7), and an auxiliary softmax classifier weighted at 0.5.

    Model # Parameters Test Error (%)
    NASNet-A (baseline) 3.3 M 3.41
    AmoebaNet-A (N=6,F=32N=6, F=32) 2.6 M 3.40 ±\pm 0.08
    AmoebaNet-A (N=6,F=36N=6, F=36) 3.2 M 3.34 ±\pm 0.06

    AmoebaNet-A achieves lower error (3.34%) than the baseline NASNet-A (3.41%) while using fewer parameters (3.2M vs. 3.3M), and matches NASNet-A accuracy (3.40%) with a 21% parameter reduction (2.6M parameters).

  7. Knowl 7 — Emergence of High Output Vertex Fan-In in Evolved Architectures

    empirical result

    Analysis of the architectural topologies produced across evolutionary search experiments revealed a consistent structural property: evolved cells exhibit an abnormally high output vertex fan-in (the number of intermediate hidden state tensors that remain unused in subsequent pairwise combinations and are therefore concatenated to form the cell output).

    The mean output fan-in of cells in final evolved populations is 3 standard deviations above the mean fan-in of randomly generated valid architectures. Controlled ablation experiments varying the fan-in of candidate architectures confirmed that higher output fan-in directly correlates with improved validation and test accuracy, mirroring the multi-branch aggregation benefits observed in hand-designed networks such as ResNeXt.

  8. Knowl 8 — AmoebaNet Architecture Variants: AmoebaNet-B, AmoebaNet-C, and AmoebaNet-D

    model/method

    Beyond AmoebaNet-A, the regularized evolution framework yielded three specialized architectural variants:

    • AmoebaNet-B: Discovered through platform-aware evolutionary architecture search over an expanded search space including additional candidate operation types.
    • AmoebaNet-C: An architecture identified during search iterations characterized by high classification accuracy relative to a small parameter count.
    • AmoebaNet-D: Constructed by extrapolating structural patterns observed in evolved populations and explicitly optimizing the architecture for training throughput on hardware accelerators, achieving the lowest training cost to reach target accuracy on ImageNet in the Stanford DAWNBench competition.

Coverage note — Deliberately omitted auxiliary toy-model CPU experiments across SP-I, SP-II, and SP-III search spaces on grayscale CIFAR-10/MNIST from the supplementary discussion, as they serve as preliminary validation for the main GPU search results.

References

  1. 1.Angeline, P. J.; Saunders, G. M.; and Pollack, J. B. 1994. An evolutionary algorithm that constructs recurrent neural networks. IEEE transactions on Neural Networks.
  2. 2.Baker, B.; Gupta, O.; Naik, N.; and Raskar, R. 2017a. Designing neural network architectures using reinforcement learning. In ICLR.
  3. 3.Baker, B.; Gupta, O.; Raskar, R.; and Naik, N. 2017b. Accelerating neural architecture search using performance prediction. ICLR Workshop.
  4. 4.Bergstra, J., and Bengio, Y. 2012. Random search for hyperparameter optimization. JMLR.
  5. 5.Brock, A.; Lim, T.; Ritchie, J. M.; and Weston, N. 2018. Smash: one-shot model architecture search through hypernetworks. In ICLR.
  6. 6.Cai, H.; Chen, T.; Zhang, W.; Yu, Y.; and Wang, J. 2018. Efficient architecture search by network transformation. In AAAI.
  7. 7.Chen, Y.; Li, J.; Xiao, H.; Jin, X.; Yan, S.; and Feng, J. 2017. Dual path networks. In NIPS.
  8. 8.Ciregan, D.; Meier, U.; and Schmidhuber, J. 2012. Multi-column deep neural networks for image classification. In CVPR.
  9. 9.Coleman, C.; Kang, D.; Narayanan, D.; Nardi, L.; Zhao, T.; Zhang, J.; Bailis, P.; Olukotun, K.; Re, C.; and Zaharia, M. 2018. Analysis of dawnbench, a time-to-accuracy machine learning performance benchmark. arXiv preprint arXiv:1806.01427.
  10. 10.Cortes, C.; Gonzalvo, X.; Kuznetsov, V.; Mohri, M.; and Yang, S. 2017. Adanet: Adaptive structural learning of artificial neural networks. In ICML.
  11. 11.Cubuk, E. D.; Zoph, B.; Mane, D.; Vasudevan, V.; and Le, Q. V. 2018. Autoaugment: Learning augmentation policies from data. arXiv.
  12. 12.Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009. Imagenet: A large-scale hierarchical image database. In CVPR.
  13. 13.Domhan, T.; Springenberg, J. T.; and Hutter, F. 2017. Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves. In IJCAI.
  14. 14.Elsken, T.; Metzen, J.-H.; and Hutter, F. 2017. Simple and efficient architecture search for convolutional neural networks. ICLR Workshop.
  15. 15.Elsken, T.; Metzen, J. H.; and Hutter, F. 2018. Neural architecture search: A survey. arXiv.
  16. 16.Fahlman, S. E., and Lebiere, C. 1990. The cascade-correlation learning architecture. In NIPS.
  17. 17.Feurer, M.; Klein, A.; Eggensperger, K.; Springenberg, J.; Blum, M.; and Hutter, F. 2015. Efficient and robust automated machine learning. In NIPS.
  18. 18.Floreano, D.; Dürr, P.; and Mattiussi, C. 2008. Neuroevolution: from architectures to learning. Evolutionary Intelligence.
  19. 19.Goldberg, D. E., and Deb, K. 1991. A comparative analysis of selection schemes used in genetic algorithms. FOGA.
  20. 20.He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016. Deep residual learning for image recognition. In CVPR.
  21. 21.Henderson, P.; Islam, R.; Bachman, P.; Pineau, J.; Precup, D.; and Meger, D. 2018. Deep reinforcement learning that matters. AAAI.
  22. 22.Hornby, G. S. 2006. Alps: the age-layered population structure for reducing the problem of premature convergence. In GECCO.
  23. 23.Hu, J.; Shen, L.; and Sun, G. 2018. Squeeze-and-excitation networks. CVPR.
  24. 24.Huang, G.; Liu, Z.; Weinberger, K. Q.; and van der Maaten, L. 2017. Densely connected convolutional networks. In CVPR.
  25. 25.Klein, A.; Falkner, S.; Springenberg, J. T.; and Hutter, F. 2017. Learning curve prediction with bayesian neural networks. ICLR.
  26. 26.Krizhevsky, A., and Hinton, G. 2009. Learning multiple layers of features from tiny images. Master’s thesis, Dept. of Computer Science, U. of Toronto.
  27. 27.Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012. Imagenet classification with deep convolutional neural networks. In NIPS.
  28. 28.Liu, C.; Zoph, B.; Shlens, J.; Hua, W.; Li, L.-J.; Fei-Fei, L.; Yuille, A.; Huang, J.; and Murphy, K. 2018a. Progressive neural architecture search. ECCV.
  29. 29.Liu, H.; Simonyan, K.; Vinyals, O.; Fernando, C.; and Kavukcuoglu, K. 2018b. Hierarchical representations for efficient architecture search. In ICLR.
  30. 30.Mendoza, H.; Klein, A.; Feurer, M.; Springenberg, J. T.; and Hutter, F. 2016. Towards automatically-tuned neural networks. In Workshop on Automatic Machine Learning.
  31. 31.Miikkulainen, R.; Liang, J.; Meyerson, E.; Rawal, A.; Fink, D.; Francon, O.; Raju, B.; Navruzyan, A.; Duffy, N.; and Hodjat, B. 2017. Evolving deep neural networks. arXiv.
  32. 32.Miller, G. F.; Todd, P. M.; and Hegde, S. U. 1989. Designing neural networks using genetic algorithms. In ICGA.
  33. 33.Negrinho, R., and Gordon, G. 2017. Deeparchitect: Automatically designing and training deep architectures. arXiv.
  34. 34.Pham, H.; Guan, M. Y.; Zoph, B.; Le, Q. V.; and Dean, J. 2018. Faster discovery of neural architectures by searching for paths in a large model. ICLR Workshop.
  35. 35.Real, E.; Moore, S.; Selle, A.; Saxena, S.; Suematsu, Y. L.; Le, Q.; and Kurakin, A. 2017. Large-scale evolution of image classifiers. In ICML.
  36. 36.Salimans, T.; Ho, J.; Chen, X.; and Sutskever, I. 2017. Evolution strategies as a scalable alternative to reinforcement learning. arXiv.
  37. 37.Saxena, S., and Verbeek, J. 2016. Convolutional neural fabrics. In NIPS.
  38. 38.Simmons, J. P.; Nelson, L. D.; and Simonsohn, U. 2011. False-positive psychology: Undisclosed flexibility in data collection and analysis allows presenting anything as significant. Psychological Science.
  39. 39.Srivastava, N.; Hinton, G.; Krizhevsky, A.; Sutskever, I.; and Salakhutdinov, R. 2014. Dropout: A simple way to prevent neural networks from overfitting. JMLR.
  40. 40.Stanley, K. O., and Miikkulainen, R. 2002. Evolving neural networks through augmenting topologies. Evol. Comput.
  41. 41.Stanley, K. O.; Bryant, B. D.; and Miikkulainen, R. 2005. Real-time neuroevolution in the nero video game. TEVC.
  42. 42.Suganuma, M.; Shirakawa, S.; and Nagao, T. 2017. A genetic programming approach to designing convolutional neural network architectures. In GECCO.
  43. 43.Szegedy, C.; Liu, W.; Jia, Y.; Sermanet, P.; Reed, S.; Anguelov, D.; Erhan, D.; Vanhoucke, V.; and Rabinovich, A. 2015. Going deeper with convolutions. In CVPR.
  44. 44.Szegedy, C.; Ioffe, S.; Vanhoucke, V.; and Alemi, A. A. 2017. Inception-v4, inception-resnet and the impact of residual connections on learning. In AAAI.
  45. 45.Wan, L.; Zeiler, M.; Zhang, S.; Le Cun, Y.; and Fergus, R. 2013. Regularization of neural networks using dropconnect. In ICML.
  46. 46.Xie, L., and Yuille, A. 2017. Genetic CNN. In ICCV.
  47. 47.Xie, S.; Girshick, R.; Dollár, P.; Tu, Z.; and He, K. 2017. Aggregated residual transformations for deep neural networks. In CVPR.
  48. 48.Yao, X. 1999. Evolving artificial neural networks. IEEE.
  49. 49.Zagoruyko, S., and Komodakis, N. 2016. Wide residual networks. In BMVC.
  50. 50.Zhang, X.; Li, Z.; Loy, C. C.; and Lin, D. 2017. Polynet: A pursuit of structural diversity in very deep networks. In CVPR.
  51. 51.Zhong, Z.; Yan, J.; and Liu, C.-L. 2018. Practical network blocks design with q-learning. In AAAI.
  52. 52.Zoph, B., and Le, Q. V. 2016. Neural architecture search with reinforcement learning. In ICLR.
  53. 53.Zoph, B.; Vasudevan, V.; Shlens, J.; and Le, Q. V. 2018. Learning transferable architectures for scalable image recognition. In CVPR.

Citation

MLA
Real, E., et al. “Regularized Evolution for Image Classifier Architecture Search”. arXiv, 2018, http://arxiv.org/abs/1802.01548v7.
APA
Real, E., Aggarwal, A., Huang, Y., & Le, Q. V. (2018). Regularized Evolution for Image Classifier Architecture Search. arXiv. http://arxiv.org/abs/1802.01548v7
Chicago
Real, E., A. Aggarwal, Y. Huang, and Q. V. Le. 2018. “Regularized Evolution for Image Classifier Architecture Search”. arXiv. http://arxiv.org/abs/1802.01548v7.
Harvard
Real, E. et al. (2018) “Regularized Evolution for Image Classifier Architecture Search”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1802.01548v7.
Vancouver
1. Real E, Aggarwal A, Huang Y, Le QV (2018) Regularized Evolution for Image Classifier Architecture Search. arXiv

BibTeX

@article{real2018regularized,
  title = {Regularized Evolution for Image Classifier Architecture Search},
  author = {Real, Esteban and Aggarwal, Alok and Huang, Yanping and Le, Quoc V},
  year = {2018},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1802.01548v7},
  eprint = {1802.01548}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF