Research map / Learning theory and algorithms / Sample complexity
Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
Surbhi Goel, Adam Klivans
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require only a marginal-distribution eigenvalue-decay assumption | Agnostic learning of ReLU networks · Networks of ReLUs on the unit sphere | runtime: \mathsf{poly}(n, 1/\epsilon, \log(1/\delta)) | Improved |
| Assume polynomial eigenvalue decay i^{-\ell / \epsilon} | Compressed Kernel Regression · One-hidden-layer ReLU network on \mathbb{S}^{n-1} | learnability: i^{-\ell / \epsilon} | Improved |
| Assume polynomial eigenvalue decay i^{-\sqrt{\ell} \log(\sqrt{\ell}/\epsilon)} | Compressed Kernel Regression · One-hidden-layer sigmoid network on \mathbb{S}^{n-1} | learnability: i^{-\sqrt{\ell} \log(\sqrt{\ell}/\epsilon)} | Improved |
Closest papers by meaning
- The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks (NeurIPS 2025 · similarity 0.87)
- Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction (AAAI 2024 · similarity 0.86)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.86)
- Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions (AAAI 2024 · similarity 0.86)
- Position: Spectral GNNs Rely Less on Graph Fourier Basis than Conceived (ICML 2025 · similarity 0.86)
- Symmetric Single Index Learning (ICLR 2024 · similarity 0.85)
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.
