Take a function of many inputs. To learn a generic one to a fixed accuracy, a shallow network needs a number of parameters that grows exponentially with the number of inputs. This is the curse of dimensionality. Now suppose the function is a tree of smaller functions that each read only two inputs. A deep network whose layers follow the tree only has to learn the small pieces, so its cost grows only polynomially with the number of inputs. In this position paper, written with Tomaso Poggio’s group at MIT, we argue that this property, compositional sparsity, is what lets deep networks succeed.
We show that every efficiently Turing-computable function has a compositionally sparse form, so the property is very likely present in every current learning problem. There are results on approximation and generalization for such functions; what is still missing is an account of how they are learned and optimized, and the paper lays out those open questions. We also conjecture that chain-of-thought helps language models for the same reason: it breaks a hard function into a sequence of simple steps, each of which can be learned.