mlsanityData to 7 Oct 2026

Learning Polynomials of Few Relevant Dimensions

arXiv 2004.13748 ↗First posted 28 Apr 2020cs.DS cs.LG stat.MLcited by 34

Not on the map. Why?

Abstract (arXiv)

Polynomial regression is a basic primitive in learning and statistics. In its most basic form the goal is to fit a degree d polynomial to a response variable y in terms of an n-dimensional input vector x. This is extremely well-studied with many applications and has sample and runtime complexity Theta(nd). Can one achieve better runtime if the intrinsic dimension of the data is much smaller than the ambient dimension n? Concretely, we are given samples (x,y) where y is a degree at most d polynomial in an unknown r-dimensional projection (the relevant dimensions) of x. This can be seen both as a generalization of phase retrieval and as a special case of learning multi-index models where the link function is an unknown low-degree polynomial. Note that without distributional assumptions, this is at least as hard as junta learning. In this work we consider the important case where the covariates are Gaussian. We give an algorithm that learns the polynomial within accuracy ε with sample complexity that is roughly N = Or,d(n log2(1/ε) (log n)d) and runtime Or,d(N n2). Prior to our work, no such results were known even for the case of r=1. We introduce a new filtered PCA approach to get a warm start for the true subspace and use geodesic SGD to boost to arbitrary accuracy; our techniques may be of independent interest, especially for problems dealing with subspace recovery or analyzing SGD on manifolds.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Apr 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 3; 2023: 10; 2024: 12; 2025: 5; 2026: 1.

34 papers.

Sort:

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  3. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  4. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  5. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  6. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  7. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
  8. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 35
  9. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  10. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 29
  11. 2024Provably learning a multi-head attention layercited by 21
  12. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
22 more
  1. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  2. 2025Survey on Algorithms for multi-index modelscited by 15
  3. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  4. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 14
  5. 2023Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luckcited by 13
  6. 2022List-Decodable Sparse Mean Estimationcited by 11
  7. 2023Nonlinear Meta-Learning Can Guarantee Faster Ratescited by 8
  8. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 8
  9. 2023Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Productscited by 7
  10. 2021Efficiently Learning Any One Hidden Layer ReLU Network From Queriescited by 6
  11. 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 6
  12. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 6
  13. 2023Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passingcited by 5
  14. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  15. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  16. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  17. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  18. 2023Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noisecited by 3
  19. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  20. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1
  21. 2021Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuitscited by 0
  22. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0