  Depth separation -- why a deeper network is more powerful than a shallower
one -- has been a major problem in deep learning theory. Previous results often
focus on representation power. For example, arXiv:1904.06984 constructed a
function that is easy to approximate using a 3-layer network but not
approximable by any 2-layer network. In this paper, we show that this
separation is in fact algorithmic: one can learn the function constructed by
arXiv:1904.06984 using an overparameterized network with polynomially many
neurons efficiently. Our result relies on a new way of extending the mean-field
limit to multilayer networks, and a decomposition of loss that factors out the
error introduced by the discretization of infinite-width mean-field networks.
