mlsanityData to 14 Oct 2026

SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem

arXiv 2309.15111 ↗First posted 26 Sep 2023cs.LG stat.MLcited by 39

Not on the map. Why?

Abstract (arXiv)

In this work, we consider the optimization process of minibatch stochastic gradient descent (SGD) on a 2-layer neural network with data separated by a quadratic ground truth function. We prove that with data drawn from the d-dimensional Boolean hypercube labeled by the quadratic ``XOR'' function y = -xixj, it is possible to train to a population error o(1) with d :polylog(d) samples. Our result considers simultaneously training both layers of the two-layer-neural network with ReLU activations via standard minibatch SGD on the logistic loss. To our knowledge, this work is the first to give a sample complexity of tildeO(d) for efficiently learning the XOR function on isotropic data on a standard neural network with standard training. Our main technique is showing that the network evolves in two phases: a textitsignal-finding phase where the network is small and many of the neurons evolve independently to find features, and a textitsignal-heavy phase, where SGD maintains and balances the features. We leverage the simultaneous training of the layers to show that it is sufficient for only a small fraction of the neurons to learn features, since those neurons will be amplified by the simultaneous growth of their second layer weights.

Key facts. Cited by 39 papers in the map (data through 14 Oct 2026). Builds on 39 of its 46 references that are in the map. First posted on arXiv 26 Sep 2023.

Builds on

39 of 46 references.

References · 39

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018On Lazy Training in Differentiable Programmingcited by 675
  3. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  4. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  5. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  6. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  7. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  8. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  9. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  10. 2019Linearized two-layers neural networks in high dimensioncited by 155
  11. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
  12. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
27 more
  1. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  2. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  3. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  4. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  5. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  6. 2021Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsitycited by 85
  7. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 83
  8. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  9. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  10. 2020Learning Parities with Neural Networkscited by 78
  11. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 70
  12. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 69
  13. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  14. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  15. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  16. 2018Gradient Descent Quantizes ReLU Network Featurescited by 61
  17. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 57
  18. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  19. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 35
  20. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  21. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  22. 2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 28
  23. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  24. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  25. 2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 14
  26. 2022Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomialscited by 13
  27. 2020Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methodscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 8; 2025: 15; 2026: 15.

39 papers.

Sort:

By area:

  1. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  2. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  3. 2025RL for Reasoning by Adaptively Revealing Rationalescited by 16
  4. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 15
  5. 2025Survey on Algorithms for multi-index modelscited by 15
  6. 2025Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architecturescited by 15
  7. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 14
  8. 2024Complexity Matters: Dynamics of Feature Learning in the Presence of Spurious Correlationscited by 12
  9. 2024Shallow diffusion networks provably learn hidden low-dimensional structurecited by 12
  10. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 9
  11. 2024Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methodscited by 7
  12. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
27 more
  1. 2024When Are Bias-Free ReLU Networks Effectively Linear Networks?cited by 4
  2. 2025Learning a Single Index Model from Anisotropic Data with vanilla Stochastic Gradient Descentcited by 4
  3. 2025How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?cited by 4
  4. 2025Transformers Provably Learn Sparse XOR with Polylogarithmic Parameterscited by 3
  5. 2025On the Theory of Continual Learning with Gradient Descent for Neural Networkscited by 3
  6. 2025Universality of high-dimensional scaling limits of stochastic gradient descentcited by 3
  7. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  8. 2026Neural Networks Provably Learn Spectral Representations for Group Compositioncited by 3
  9. 2025Linearly Separable Features in Shallow Nonlinear Networks: Width Scales Polynomially with Intrinsic Data Dimensioncited by 2
  10. 2025Convergence of Shallow ReLU Networks on Weakly Interacting Datacited by 2
  11. 2025Favorability of Loss Landscape with Weight Decay Requires Both Large Overparametrization and Initializationcited by 1
  12. 2025Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learningcited by 1
  13. 2026The two clocks and the innovation window: When and how generative models learn rulescited by 1
  14. 2026The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficientlycited by 1
  15. 2026Learning with Shallow Neural Networks on Cluster-Structured Featurescited by 1
  16. 2026A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernelcited by 1
  17. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  18. 2025Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attentioncited by 0
  19. 2026Neuron Block Dynamics for XOR Classification with Zero-Margincited by 0
  20. 2026Over-Alignment vs Over-Fitting: The Role of Feature Learning Strength in Generalizationcited by 0
  21. 2026Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Ratecited by 0
  22. 2026Eigen-Spike Emergence and Quadratic Equivalents for Conjugate Kernels on Nonlinearly Separable Datacited by 0
  23. 2026Singular perturbations and hierarchical learning in two-layer neural networkscited by 0
  24. 2026The Kinetics of Training: A Driven-Nucleation Rate Law for Emergence, Plasticity Loss, and Circuit Control in Language Modelscited by 0
  25. 2026Non-asymptotic implicit bias of logistic regression at early-stage gradient descent dynamicscited by 0
  26. 2026Learning Orthogonal Multi-Index Models Beyond Small Initialization: Incremental Learning, Competitive Dynamics and Symmetrycited by 0
  27. 2026The Conflict Between Logic and Memory: Training Conditions for Optimizer-Dependent Rule Acquisitioncited by 0