Research map / Learning theory and algorithms / Sample complexity
Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit
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 neural networks with SGD on uniform sparse-parity data | 2-layer MLPs, Transformers, sinusoidal/oscillating neurons, and PolyNets · (n,k) sparse parity, n in {10, 20, 30}, k in {2, 3, 4} | validation accuracy: 100% accuracy; at least 20% of 25 random trials | Helped |
| Use the tested standard training and initialization configurations | neural networks for sparse parity learning · (n,k) sparse parity, n ≤ 30, k ≤ 4 | convergence iterations: t_c ≤ c · n^{αk} ≤ 10^5 steps | Helped |
| Use a smaller batch size (ablation) | barely expressive MLPs and the Transformer configuration · (n,k) sparse parity | successful learning: B ≥ 16 | Hurt |
| Use polynomial activations in configurations (v) and (vi) (ablation) | 2-layer MLPs for sparse parity · (n,k) sparse parity | training error trajectory | Mixed |
| Increase network width (ablation) | SGD on (40,3)-parity · (40,3)-parity | convergence time | No clear effect |
| Train with smaller fixed sample sizes and weight decay (ablation) | minibatch SGD for sparse parity · finite-sample parity learning | test generalization: m ≪ n^k | Mixed |
| Train layers jointly end-to-end instead of greedily layer by layer (ablation) | deeper polynomial-activation MLPs · sparse parity | accuracy | Helped |
Closest papers by meaning
- Learning High-Degree Parities: The Crucial Role of the Initialization (ICLR 2025 · similarity 0.88)
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.88)
- A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.88)
- Asymmetric Scaling Laws from Sparse Features (NeurIPS 2026 · similarity 0.87)
- DEEP NEURAL NETWORK INITIALIZATION WITH SPARSITY INDUCING ACTIVATIONS (ICLR 2024 · similarity 0.87)
- Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.87)
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.