Research map / Optimization / Implicit bias and generalization
Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Train a classifier with gradient descent on square loss | Polynomial-size classifiers learning one-layer ReLU or sigmoid networks · Standard Gaussian N(0, I_n), regression | test square-loss | Hurt |
| Use a general statistical-query algorithm for classification | One-layer ReLU or sigmoid networks · Standard Gaussian N(0, I_n), classification | classification error | Hurt |
| Construct networks by alternating parity-signed activations over coordinate masks | One-layer neural networks with an odd outer activation · Sign-symmetric distributions | pairwise correlation: 0 | Helped |
| Train an overparameterized network with gradient descent on the constructed targets | Tanh and ReLU networks · Gaussian regression and classification experiments | test error | Hurt |
Closest papers by meaning
- Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks (NeurIPS 2022 · similarity 0.89)
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.88)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.87)
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.86)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.86)
- A Universal Growth Rate for Learning with Smooth Surrogate Losses (NeurIPS 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.