mlsanityData to 14 Oct 2026

Learning Hierarchical Polynomials with Three-Layer Neural Networks

arXiv 2311.13774 ↗First posted 23 Nov 2023cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning hierarchical polynomials over the standard Gaussian distribution with three-layer neural networks. We specifically consider target functions of the form h = g circ p where p : ℝd rightarrow ℝ is a degree k polynomial and g: ℝ rightarrow ℝ is a degree q polynomial. This function class generalizes the single-index model, which corresponds to k=1, and is a natural class of functions possessing an underlying hierarchical structure. Our main result shows that for a large subclass of degree k polynomials p, a three-layer neural network trained via layerwise gradient descent on the square loss learns the target h up to vanishing test error in widetildeO(dk) samples and polynomial time. This is a strict improvement over kernel methods, which require widetilde Theta(dkq) samples, as well as existing guarantees for two-layer networks, which require the target function to be low-rank. Our result also generalizes prior works on three-layer neural networks, which were restricted to the case of p being a quadratic. When p is indeed a quadratic, we achieve the information-theoretically optimal sample complexity widetildeO(d2), which is an improvement over prior work~citepnichani2023provable requiring a sample size of widetildeTheta(d4). Our proof proceeds by showing that during the initial stage of training the network performs feature learning to recover the feature p with widetildeO(dk) samples. This work demonstrates the ability of three-layer neural networks to learn complex features and as a result, learn a broad class of hierarchical functions.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 26 of its 38 references that are in the map. First posted on arXiv 23 Nov 2023.

Builds on

26 of 38 references.

References · 26

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2021Convex optimizationcited by 2,515
  4. 2018On Lazy Training in Differentiable Programmingcited by 675
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  7. 2019Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networkscited by 368
  8. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  9. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  10. 2020Finite Versus Infinite Neural Networks: an Empirical Studycited by 157
  11. 2019Linearized two-layers neural networks in high dimensioncited by 155
  12. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
14 more
  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  2. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  3. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  4. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  5. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  6. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  7. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  8. 2021Learning with invariances in random features and kernel modelscited by 89
  9. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  10. 2019A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamicscited by 49
  11. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  12. 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 19
  13. 2021Optimization-Based Separations for Neural Networkscited by 17
  14. 2023Depth Separation with Multilayer Mean-Field Networkscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 0; 2026: 4.

9 papers.

  1. 2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinationscited by 13
  2. 2024How Transformers Get Rich: Approximation and Dynamics Analysiscited by 8
  3. 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 6
  4. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  5. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 5
  6. 2024Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokenscited by 3
  7. 2024Generalization for Least Squares Regression With Simple Spiked Covariancescited by 2
  8. 2026Scaling Laws from Sequential Feature Recovery: A Solvable Hierarchical Modelcited by 0
  9. 2026Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descentcited by 0