Methods, and systems, including computer programs encoded on computer storage media for neural network architecture search. A method includes defining a neural network computational cell, the computational cell including a directed graph of nodes representing respective neural network latent representations and edges representing respective operations that transform a respective neural network latent representation; replacing each operation that transforms a respective neural network latent representation with a respective linear combination of candidate operations, where each candidate operation in a respective linear combination has a respective mixing weight that is parameterized by one or more computational cell hyper parameters; iteratively adjusting values of the computational cell hyper parameters and weights to optimize a validation loss function subject to computational resource constraints; and generating a neural network for performing a machine learning task using the defined computational cell and the adjusted values of the computational cell hyper parameters and weights.