Research map / Optimization / Implicit bias and generalization
SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that minibatch SGD on a two-layer ReLU network trained on logistic loss learns the Boolean XOR (quadratic) function with O~(d) samples, via a signal-finding phase followed by a signal-heavy phase.
Problem
Sample complexity of learning multi-index/XOR functions with standard two-layer neural networks trained by standard minibatch SGD, where prior guarantees of near-optimal O~(d) required modified architectures, layer-wise training, or non-rotationally-invariant algorithms.
Approach
Analyze simultaneous training of both layers of a ReLU network under minibatch SGD in two phases: a signal-finding phase where neurons evolve approximately independently (as if the output were zero), and a signal-heavy phase where an inductive hypothesis keeps signal components dominant; joint growth of second-layer weights amplifies the few neurons that learn features.
Key results
- Theorem: with minibatch size m >= d/theta, width polynomial in d, and step size eta=theta, SGD reaches population logistic loss o(1) within C log(d)/eta steps, i.e., Theta(d polylog d) samples.
- Phase 1 shows a 0.1 fraction of neurons per cluster direction grow their signal component exponentially, while the non-signal mass remains O(theta^2).
- Under rotation-invariant SGD and initialization, the analysis holds for any Boolean basis, unlike prior layer-wise methods requiring known coordinates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train both layers simultaneously with minibatch SGD | Two-layer ReLU network · Boolean XOR | population loss: o(1) | Helped |
| Use standard minibatch SGD on a two-layer ReLU network rather than the neural tangent kernel | Learning Boolean XOR · Boolean XOR | sample complexity: \Theta(d^2) -> \Theta\left(d \pl(d)\right) | Helped |
Surprising findings
- Joint training of both layers is needed: without training second-layer weights, non-signal neurons could grow at a comparable rate to signal neurons, so the signal-heavy hypothesis would fail.
Limitations
- Results hold only for Boolean (hypercube) data, not Gaussian data.
- Analysis uses minibatch SGD with large batches (m >= d polylog d), not batch size 1.
- Extension to regression and to Gaussian data is not established.
Experimental setup
Datasets: synthetic Boolean hypercube XOR data
Metrics: population logistic loss
Baselines: neural tangent kernel layer-wise SGD quadratic NTK methods
Builds on: neural tangent kernel mean-field analysis layer-wise training
Closest papers by meaning
- Neural Networks Efficiently Learn Low-Dimensional Representations with SGD (ICLR 2023 · similarity 0.89)
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.88)
- Emergence and scaling laws in SGD learning of shallow neural networks (NeurIPS 2025 · similarity 0.88)
- Online Learning and Information Exponents: The Importance of Batch size & Time/Complexity Tradeoffs (ICML 2024 · similarity 0.87)
- The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents (ICML 2024 · similarity 0.86)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (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.