Research map / Learning theory and algorithms / Sample complexity
Learning Hierarchical Polynomials with Three-Layer Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that a three-layer residual network trained with layerwise gradient descent learns hierarchical polynomials g∘p with O~(d^k) samples, and O~(d^2) for quadratic p, improving on kernel methods and prior three-layer analyses.
Problem
Learning hierarchical targets h = g∘p (p a degree-k polynomial, g a degree-q polynomial) over Gaussian inputs; kernel methods need d^{kq} samples and two-layer networks need low-rank targets, so efficient learning of such compositional functions by neural networks is open.
Approach
A three-layer residual network with bottleneck is trained layerwise: first the outer weights of the intermediate layer are fit (stage 1, learning the degree-k projection of h, which approximates the hidden feature p), then the link-function layer is fit by random-feature regression (stage 2). An approximate Stein's lemma shows P_k(g∘p) ≈ E[g'(z)] p, so the degree-k projection recovers the feature
Key results
- Theory: a three-layer network with layerwise GD learns g∘p to vanishing error with n = O~(d^k) samples, versus d^{kq} for kernel methods.
- For quadratic p, the algorithm achieves O~(d^2) sample and width complexity, matching the information-theoretic bound and improving over the O~(d^4) of prior three-layer work.
- Experiments with k=3 show test loss drops to near zero at roughly d^3 samples for d in {16,24,32,40}, and feature correlation approaches 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use layerwise gradient descent on a three-layer network instead of a kernel method | Learning h = g ∘ p with a degree-k feature · Hierarchical polynomials | sample complexity: \widetilde{\Omega}(d^{kq}) -> \widetilde{\mathcal{O}}(d^k) | Helped |
| Run gradient descent for multiple steps during feature learning rather than using a single large gradient step | Three-layer network learning a quadratic-feature target · Quadratic feature h(x) = g(xᵀAx) | sample complexity: \widetilde\Theta(d^4) -> \widetilde{\mathcal{O}}(d^2) | Helped |
| Train all network parameters jointly with Adam | ResNet-like three-layer network · Degree-3 hierarchical polynomial | test loss | Helped |
| Increase sample size past d^3 | ResNet-like three-layer network · Degree-3 hierarchical polynomial | feature correlation | Helped |
Limitations
- Analysis restricted to Gaussian inputs and to a large but restricted subclass of degree-k polynomial features with balanced coefficients (L = Theta(d)).
- Layerwise training with frozen first layer differs from standard joint training; full joint training only checked empirically.
- Target depends on a single hidden feature p; multi-feature targets not covered.
Experimental setup
Datasets: synthetic Gaussian samples with hierarchical targets h = g∘p
Benchmarks: synthetic hierarchical polynomial targets h = g∘p
Metrics: test square loss correlation between learned feature and true feature sample complexity scaling in d
Baselines: kernel methods (NTK) Damian et al. three-layer quadratic analysis
Builds on: Stein's lemma neural tangent kernel single-index model feature learning analyses muP initialization
Closest papers by meaning
- Learning Hierarchical Polynomials of Multiple Nonlinear Features (ICLR 2025 · similarity 0.94)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.88)
- Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance (ICLR 2024 · similarity 0.85)
- TMPNN: High-Order Polynomial Regression Based on Taylor Map Factorization (AAAI 2024 · similarity 0.84)
- Mean-Field Analysis for Learning Subspace-Sparse Polynomials with Gaussian Input (NeurIPS 2024 · similarity 0.84)
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.