Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for training neural networks. In one aspect, a system includes a neural network shrinking engine that is configured to receive a neural network being trained and generate a reduced neural network by a shrinking process. The shrinking process includes training the neural network based on a shrinking engine loss function that includes terms penalizing active neurons of the neural network and removing inactive neurons from the neural network. The system includes a neural network expansion engine that is configured to receive the neural network being trained and generate an expanded neural network by an expansion process including adding new neurons to the neural network and training the neural network based on an expanding engine loss function. The system includes a training subsystem that generates reduced neural networks and expanded neural networks.