AutoML-Zero: Evolving Machine Learning Algorithms From Scratch

Machine learning research has advanced in multiple aspects, including model structures and learning methods. The effort to automate such research, known as AutoML, has also made significant progress. However, this progress has largely focused on the architecture of neural networks, where it has relied on sophisticated expertdesigned layers as building blocks—or similarly restrictive search spaces. Our goal is to show that AutoML can go further: it is possible today to automatically discover complete machine learning algorithms just using basic mathematical operations as building blocks. We demonstrate this by introducing a novel framework that significantly reduces human bias through a generic search space. Despite the vastness of this space, evolutionary search can still discover two-layer neural networks trained by backpropagation. These simple neural networks can then be surpassed by evolving directly on tasks of interest, e.g. CIFAR- 10 variants, where modern techniques emerge in the top algorithms, such as bilinear interactions, normalized gradients, and weight averaging. Moreover, evolution adapts algorithms to different task types: e.g., dropout-like techniques appear when little data is available. We believe these preliminary successes in discovering machine learning algorithms from scratch indicate a promising new direction for the field.

Introduction. In recent years, neural networks have reached remarkable performance on key tasks and seen a fast increase in their popularity [e.g. He et al., 2015; Silver et al., 2016; Wu et al., 2016]. This success was only possible due to decades of machine learning (ML) research into many aspects of the field, ranging from learning strategies to new architectures [Rumelhart et al., 1986; LeCun et al., 1995; Hochreiter & Schmidhuber, 1997, among many others]. The length and difficulty of ML research prompted a new field, named AutoML, that aims to automate such progress by spending machine compute time instead of human research time (Fahlman & Lebiere, 1990; Hutter et al., 2011; Finn et al., 2017). This endeavor has been fruitful but, so far, modern studies have only employed constrained search spaces heavily reliant on human design. A common example is architecture search, which typically constrains the space by only employing sophisticated expert-designed layers as building blocks and by respecting the rules of backpropagation (Zoph & Le, 2016; Real et al., 2017; Tan et al., 2019). Other AutoML studies similarly have found ways to constrain their search spaces to isolated algorithmic aspects, such as the learning rule used during backpropagation (Andrychowicz et al., 2016; Ravi & Larochelle, 2017), the data augmentation (Cubuk et al., 2019a; Park et al., 2019) or the intrinsic curiosity reward in reinforcement learning (Alet et al., 2019); in these works, all other algorithmic aspects remain hand-designed. This approach may save compute time but has two drawbacks. First, human-designed components bias the search results in favor of human-designed algorithms, possibly reducing the innovation potential of AutoML. Innovation is also limited by having fewer options (Elsken et al., 2019b). Indeed, dominant aspects of performance are often left out (Yang et al., 2020). Second, constrained search spaces need to be carefully composed (Zoph et al., 2018; So et al., 2019; Negrinho et al., 2019), thus creating a new burden on researchers and undermining the purported objective of saving their time.

To address this, we propose to automatically search for whole ML algorithms using little restriction on form and only simple mathematical operations as building blocks. We call this approach AutoML-Zero, following the spirit of previous work which aims to learn with minimal human participation [e.g. Silver et al., 2017]. In other words, AutoML-Zero aims to search a fine-grained space simultaneously for the model, optimization procedure, initialization, and so on, permitting much less human-design and even allowing the discovery of non-neural network algorithms. To demonstrate that this is possible today, we present an initial solution to this challenge that creates algorithms competitive The genericity of the AutoML-Zero space makes it more difficult to search than existing AutoML counterparts. Existing AutoML search spaces have been constructed to be dense with good solutions, thus deemphasizing the search method itself. For example, comparisons on the same space found that advanced techniques are often only marginally superior to simple random search (RS) (Li & Talwalkar, 2019; Elsken et al., 2019b; Negrinho et al., 2019). AutoML-Zero is different: the space is so generic that it ends up being quite sparse. The framework we propose represents ML algorithms as computer programs comprised of three component functions, Setup, Predict, and Learn, that performs initialization, prediction and learning. The instructions in these functions apply basic mathematical operations on a small memory. The operation and memory addresses used by each instruction are free parameters in the search space, as is the size of the component functions. While this reduces expert design, the consequent sparsity means that RS cannot make enough progress; e.g. good algorithms to learn even a trivial task can be as rare as 1 in 1012. To overcome this difficulty, we use small proxy tasks and migration techniques to build highly-optimized open-source infrastructure capable of searching through 10,000 models/second/cpu core. In particular, we present a variant of functional equivalence checking that applies to ML algorithms. It prevents re-evaluating algorithms that have already been seen, even if they have different implementations, and results in a 4x speedup. More importantly, for better efficiency, we move away from RS.1 Perhaps surprisingly, evolutionary methods can find solutions in the AutoML-Zero search space despite its enormous size and sparsity. By randomly modifying the programs and periodically selecting the best performing ones on given tasks/datasets, we discover reasonable algorithms. We will first show that starting from empty programs and using data labeled by “teacher” neural networks with random weights, evolution can discover neural networks trained by gradient descent (Section 4.1).

Related work. AutoML has utilized a wide array of paradigms, including growing networks neuron-by-neuron (Stanley & Miikkulainen, 2002), hyperparameter optimization (Snoek et al., 2012; Loshchilov & Hutter, 2016; Jaderberg et al., 2017) and, neural architecture search (Zoph & Le, 2016; Real et al., 2017). As discussed in Section 1, AutoML has targeted many aspects of neural networks individually, using sophisticated coarse-grained building blocks. Mei et al. (2020), on the other hand, perform a fine-grained search over the convolutions of a neural network. Orthogonally, a few studies benefit from extending the search space to two such aspects simultaneously (Zela et al., 2018; Miikkulainen et al., 2019; Noy et al., 2019). In our work, we perform a fine-grained search over all aspects of the algorithm.

An important aspect of an ML algorithm is the optimization of its weights, which has been tackled by AutoML in the form of numerically discovered optimizers (Chalmers, 1991; Andrychowicz et al., 2016; Vanschoren, 2019). The output of these methods is a set of coefficients or a neural network that works well but is hard to interpret. These methods are sometimes described as “learning the learning algorithm”. However, in our work, we understand algorithm more broadly, including the structure and initialization of the model, not just the optimizer. Additionally, our algorithm is not discovered numerically but symbolically. A symbolically discovered optimizer, like an equation or a computer program, can be easier to interpret or transfer. An early example of a symbolically discovered optimizer is that of Bengio et al. (1994), who optimize a local learning rule for a 4-neuron neural network using genetic programming (Holland, 1975; Forsyth et al., 1981; Koza & Koza, 1992). Our search method is similar but represents the program as a sequence of instructions. While they use the basic operations {+, −, ×, ÷}, we allow many more, taking advantage of dense hardware computations. Risi & Stanley (2010) tackle the discovery of a biologically informed neural network learning rule too, but with a very different encoding.

More recently, Bello et al. (2017) also search for a symbolic optimizer, but in a restricted search space of hand-tuned operations (e.g. “apply dropout with 30% probability”, “clip at 0.00001”, etc.). Our search space, on the other hand, aims to minimize restrictions and manual design. Unlike these three studies, we do not even assume the existence of a neural network or of gradients.

Method. AutoML-Zero concerns the automatic discovery of algorithms that perform well on a given set of ML tasks T . First, search experiments explore a very large space of algorithms A for an optimal and generalizable a∗∈A. The quality of the algorithms is measured on a subset Tsearch ⊂T , with each search experiment producing a candidate algorithm. In this work, we apply random search as a baseline and evolutionary search as the main search method due to their simplicity and scalability. Once the search experiments are done, we select the best candidate by measuring their performances on another subset of tasks Tselect ⊂T (analogous to standard ML model selection with a validation set). Unless otherwise stated, we use binary classification tasks extracted from CIFAR-10, a collection of tiny images each labeled with object classes (Krizhevsky & Hinton, 2009), and we calculate the average accuracy across a set of tasks to measure the quality of each algorithm. To lower compute costs and achieve higher throughput, we create small proxy tasks for Tsearch and Tselect by using one random matrix for each task to project the input features to lower dimensionality. The projected dimensionality is 8 ≤F ≤256. Finally, we compare the best algorithm’s performance against handdesigned baselines on the CIFAR-10 data in the original dimensionality (3072), holding out the CIFAR-10 test set for the final evaluation. To make sure the improvement is not specific to CIFAR-10, we further show the gain generalizes to other datasets: SVHN (Netzer et al., 2011), ImageNet (Chrabaszcz et al., 2017), and Fashion MNIST (Xiao et al., 2017). The Experiment Details paragraphs in Section 4 contain the specifics of the tasks. We now describe the search space and search method with sufficient detail to 3.1. Search Space We represent algorithms as computer programs that act on a small virtual memory with separate address spaces for scalar, vector and matrix variables (e.g. s1, v1, m1), all of which are floating-point and share the dimensionality of the task’s input features (F). Programs are sequences of instructions. Each instruction has an operation—or op— that determines its function (e.g. “multiply a scalar with a vector”). To avoid biasing the choice of ops, we use a simple criterion: those that are typically learned by high-school level. We purposefully exclude machine learning concepts, matrix decompositions, and derivatives. Instructions have op-specific arguments too. These are typically addresses in the memory (e.g. “read the inputs from scalar address 0 and vector address 3; write the output to vector address 2”). Some ops also require real-valued constants (e.g. μ and σ for a random Gaussian sampling op), which are searched for as well. Suppl. Section S2 contains the full list of 65 ops.

Inspired by supervised learning work, we represent an algorithm as a program with three component functions that we call Setup, Predict, and Learn (e.g. Figure 5). The algorithm is evaluated as in Fig 1. There, the two for-loops implement the training and validation phases, processing 3.2. Search Method Search experiments must discover algorithms by modifying the instructions in the component functions (Setup, Predict, and Learn; e.g. Figure 5). Unless otherwise stated, we use the regularized evolution search method because of its simplicity and recent success on architecture search benchmarks (Real et al., 2019; Ying et al., 2019; So et al., 2019). This method is illustrated in Figure 2. It keeps a population of P algorithms, all initially empty—i.e. none of the three component functions has any instructions/code lines. The population is then improved through cycles. Each cycle picks T < P algorithms at random and selects the best performing one as the parent, i.e. tournament selection (Goldberg & Deb, 1991). This parent is then copied and mutated to produce a child algorithm that is added to the population, while the oldest algorithm in the population is removed.

Discussion. Teacher datasets and carefully chosen ops bias the results in favor of known algorithms, so in this section we replace them with more generic options. We now search among a long list of ops selected based on the simplicity criterion described in Section 3.1. The increase in ops makes the search more difficult but allows the discovery of solutions other than neural networks. For more realistic datasets, we use binary classification tasks extracted from CIFAR-10 and MNIST.

AutoML-Zero tic in non-convex optimization (Hazan et al., 2015; Levy, 2016). (4) The weight matrix W′ used during inference is the accumulation of all the weight matrices {Wt} after each training step t, i.e.: W′ = P t Wt. This is reminiscent of the averaged perceptron (Collins, 2002) and neural network weight averaging during training (Polyak & Juditsky, 1992; Goodfellow et al., 2016). Unlike these studies, the evolved algorithm accumulates instead of averaging, but this difference has no effect when measuring the accuracy of classification tasks (it does not change the prediction). As in those techniques, different weights are used at training and validation time. The evolved algorithm achieves this by setting the weights W equal to W′ at the end of the Predict component function and resetting them to Wt right after that, at the beginning of the Learn component function. This has no effect during training, when Predict and Learn alternate in execution. However, during validation, Learn is never called and Predict is executed repeatedly, causing W to remain as W′.

In conclusion, even though the task used during search is simple, the results show that our framework can discover commonly used algorithms from scratch.

Few training examples. We use only 80 of the training examples and repeat them for 100 epochs. Under these conditions, algorithms evolve an adaptation that augments the data through the injection of noise (Figure 7a). This is referred to in the literature as a noisy ReLU (Nair & Hinton, 2010; Bengio et al., 2013) and is reminiscent of Dropout (Srivastava et al., 2014). Was this adaptation a result of the small number of examples or did we simply get lucky? To answer this, we perform 30 repeats of this experiment and of a control experiment. The control has 800 examples/100 epochs. We find that the noisy ReLU is reproducible and arises preferentially in the case of little data (expt: 8/30, control: 0/30, p<0.0005).

Fast training. Training on 800 examples/10 epochs leads to the repeated emergence of learning-rate decay, a wellknown strategy for the timely training of an ML model (Bengio, 2012). An example can be seen in Figure 7b. As a control, we increase the number of epochs to 100. With overwhelming confidence, the decay appears much more often in the cases with fewer training steps (expt: 30/30, control: 3/30, p<10−14).

Multiple classes. When we use all 10 classes of the CIFAR- 10 dataset, evolved algorithms tend to use the transformed mean of the weight matrix as the learning rate (Figure 7c). (Note that to support multiple classes, labels and outputs are now vectors, not scalars.) While we do not know the reason, the preference is statistically significant (expt: 24/30, control: 0/30, p<10−11).

Altogether, these experiments show that the resulting algorithms seem to adapt well to the different types of tasks.

Conclusion. and Discussion In this paper, we proposed an ambitious goal for AutoML: the automatic discovery of whole ML algorithms from basic operations with minimal restrictions on form. The objective was to reduce human bias in the search space, in the hope that this will eventually lead to new ML concepts. As a start, we demonstrated the potential of this research direction by constructing a novel framework that represents an ML algorithm as a computer program comprised of three component functions (Setup, Predict, Learn). Starting from empty component functions and using only basic mathematical operations, we evolved neural networks, gradient descent, multiplicative interactions, weight averaging, normalized gradients, and the like. These results are promising, but there is still much work to be done. In the remainder of this section, we motivate future work with concrete observations.

The search method was not the focus of this study but to reach our results, it helped to (1) add parallelism through migration, (2) use FEC, (3) increase diversity, and (4) apply hurdles, as we detailed in Section 3.2. The effects can be seen in Figure 8. Suppl. Section S9 shows that these improvements work across compute scales (today’s highcompute regime is likely to be tomorrow’s low-compute regime, so ideas that do not scale with compute will be shorter-lived). Preliminary implementations of crossover and geographic structure did not help in our experiments. The silver lining is that the AutoML-Zero search space provides ample room for algorithms to distinguish themselves (e.g. Section 4.1), allowing future work to attempt more sophisticated evolutionary approaches, reinforcement learning, Bayesian optimization, and other methods that have helped AutoML before.

Limitations. Evaluating evolved algorithms on new tasks requires hyperparameter tuning, as is common for machine learning algorithms, but without inspection we may not know what each variable means (e.g. “Is s7 the learning rate?”). Tuning all constants in the program was insufficient due to hyperparameter coupling, where an expression happens to produce a good value for a hyperparameter on a specific set of tasks but won’t generalize.