Deep Learning of Compositional Targets with Hierarchical Spectral Methods
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 52 of its 68 references that are in the map. First posted on arXiv 11 Feb 2026.
Builds on
52 of 68 references.
References · 52
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
- 2015Optimizing Neural Networks with Kronecker-factored Approximate Curvaturecited by 776
- 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 748
- 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
- 2018Shampoo: Preconditioned Stochastic Tensor Optimizationcited by 413
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
- 2016Benefits of depth in neural networkscited by 248
- 2018Gradient descent aligns the layers of deep linear networkscited by 182
- 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 180
- 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
- 2019Linearized two-layers neural networks in high dimensioncited by 155
- 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
38 more
- 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
- 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
- 2020Generalisation error in learning with random features and the hidden manifold modelcited by 126
- 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
- 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
- 2020The Gaussian equivalence of generative models for learning with shallow neural networkscited by 113
- 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
- 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
- 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
- 2022Universality of empirical risk minimizationcited by 73
- 2023How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Modelcited by 70
- 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 67
- 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
- 2020The Unreasonable Effectiveness of Deep Learning in Artificial Intelligencecited by 57
- 2014An exact mapping between the Variational Renormalization Group and Deep Learningcited by 52
- 2018Neural Network Renormalization Groupcited by 48
- 2017Depth Separation for Neural Networkscited by 46
- 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
- 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
- 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 39
- 2024Towards a theory of how the structure of language is acquired by deep neural networkscited by 38
- 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 35
- 2023Universality laws for Gaussian mixtures in generalized linear modelscited by 28
- 2022An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalingscited by 27
- 2017Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimationcited by 26
- 2016Deep Learning and Hierarchal Generative Modelscited by 23
- 2024Dimension-free deterministic equivalents and scaling laws for random feature regressioncited by 23
- 2024Asymptotics of Random Feature Regression Beyond the Linear Scaling Regimecited by 22
- 2020Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learningcited by 18
- 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 18
- 2025Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applicationscited by 11
- 2023Learning Hierarchical Polynomials with Three-Layer Neural Networkscited by 8
- 2023Exact threshold for approximate ellipsoid fitting of random pointscited by 7
- 2024The Role of the Time-Dependent Hessian in High-Dimensional Optimizationcited by 7
- 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 6
- 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
- 2025When does Gaussian equivalence fail and how to fix it: Non-universal behavior of random features with quadratic scalingcited by 5
- 2025Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limitcited by 3
50 most cited of 52 All 52 (JSON)
Built on by
Citing papers per year: 2026: 2.
2 papers.