Across species, neural circuits show remarkable regularity, suggesting that their structure has been driven by underlying optimality principles. Here, we ask whether we can predict the neural circuitry of diverse species by optimizing the neural architecture to make learning as efficient as possible. We focus on the olfactory system, primarily because it has a relatively simple evolutionarily conserved structure, and because its input and intermediate layer sizes exhibits a tight allometric scaling. In mammals, it has been shown that the number of neurons in layer 2 of piriform cortex scales as the number of glomeruli (the input units) to the 3/2 power; in invertebrates, we show that the number of mushroom body Kenyon cells scales as the number of glomeruli to the 7/2 power. To understand these scaling laws, we model the olfactory system as a three layered nonlinear neural network, and analytically optimize the intermediate layer size for efficient learning from a limited number of samples. We find that the 3/2 scaling observed in mammals emerges naturally, both in full batch optimization and under stochastic gradient learning. We extended the framework to the case where a fraction of the olfactory circuit is genetically specified, not learned. We show numerically that this makes the scaling law steeper when the number of glomeruli is small, and we are able to recover the 7/2 scaling law observed in invertebrates. This study paves the way for a deeper understanding of the organization of brain circuits from an evolutionary perspective.