Deep Learning of Compositional Targets with Hierarchical Spectral Methods

Why depth yields a genuine computational advantage over shallow methods remains a central open question in learning theory. We study this question in a controlled high-dimensional Gaussian setting, focusing on compositional target functions. We analyze their learnability using an explicit three-layer fitting model trained via layer-wise spectral estimators. Although the target is globally a high-degree polynomial, its compositional structure allows learning to proceed in stages: an intermediate representation reveals structure that is inaccessible at the input level. This reduces learning to simpler spectral estimation problems, well studied in the context of multi-index models, whereas any shallow estimator must resolve all components simultaneously. Our analysis relies on Gaussian universality, leading to sharp separations in sample complexity between two and three-layer learning strategies.

Deep neural networks often outperform simpler models, but it is still hard to explain precisely why adding layers can make learning easier. We study this question in a controlled mathematical setting where the data is generated in stages, like a hierarchy of hidden features. For a shallow method, the final structure looks like one complicated high-degree relationship, so it must try to learn all parts of the structure at once. Our approach instead learns the hidden structure layer by layer. It uses spectral methods, which are linear-algebra tools that identify important directions in data and are often more tractable, in order to first recover an intermediate representation and then learn the remaining simpler rule on top of it. We prove that this staged strategy can need far fewer training examples than shallow approaches for the same target. Numerical experiments confirm the predicted transition in performance, even at moderate problem sizes. The results give a clean theoretical example of how depth can provide a real computational advantage: it can turn one hard learning problem into a sequence of easier ones.