# Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials

arXiv: https://arxiv.org/abs/2307.12840 · HTML: https://mlsanity.com/paper/2307.12840/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 33 references that are in the map.
- First posted on arXiv 24 Jul 2023.

## Builds on (most cited first, 22 of 22)

- [Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity](https://mlsanity.com/paper/1602.05897/) (2016)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Learning Deep ReLU Networks Is Fixed-Parameter Tractable](https://mlsanity.com/paper/2009.13512/) (2020)
- [Learning Two-layer Neural Networks with Symmetric Inputs](https://mlsanity.com/paper/1810.06793/) (2018)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds](https://mlsanity.com/paper/1805.02677/) (2018)
- [ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time](https://mlsanity.com/paper/1510.03528/) (2015)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)

## Built on by (most cited first, 4 of 4)

- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Gradient dynamics for low-rank fine-tuning beyond kernels](https://mlsanity.com/paper/2411.15385/) (2024)
- [Agnostically Learning Multi-index Models with Queries](https://mlsanity.com/paper/2312.16616/) (2023)

## Abstract (arXiv)

We study the problem of PAC learning a linear combination of k ReLU activations under the standard Gaussian distribution on ℝd with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity (dk/ε)O(k), where ε>0 is the target accuracy. Prior work had given an algorithm for this problem with complexity (dk/ε)h(k), where the function h(k) scales super-polynomially in k. Interestingly, the complexity of our algorithm is near-optimal within the class of Correlational Statistical Query algorithms. At a high-level, our algorithm uses tensor decomposition to identify a subspace such that all the O(k)-order moments are small in the orthogonal directions. Its analysis makes essential use of the theory of Schur polynomials to show that the higher-moment error tensors are small given that the lower-order ones are.