mlsanityData to 13 Oct 2026

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

arXiv 2307.12840 ↗First posted 24 Jul 2023cs.LG cs.DS math.STcited by 4

Not on the map. Why?

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.

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

Builds on

22 of 33 references.

References · 22

  1. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  2. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  3. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  4. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  5. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  6. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  7. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  8. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  9. 2020Approximation Schemes for ReLU Regressioncited by 34
  10. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  11. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  12. 2020Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Modelscited by 28
10 more
  1. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  2. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  3. 2018Learning Two-layer Neural Networks with Symmetric Inputscited by 22
  4. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  5. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  6. 2015ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Timecited by 16
  7. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  8. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  9. 2021ReLU Regression with Massart Noisecited by 10
  10. 2022SQ Lower Bounds for Learning Single Neurons with Massart Noisecited by 5

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 3.

4 papers.

  1. 2024Provably learning a multi-head attention layercited by 21
  2. 2024Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Modelscited by 6
  3. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  4. 2023Agnostically Learning Multi-index Models with Queriescited by 1