Research map / Optimization / Implicit bias and generalization
Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent
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 online sign SGD with a large batch (~d^{k-1}) on a two-layer polynomial-activation (x^k) network of width 2^{Θ(k)} solves k-sparse parity in O(log d) iterations, matching the SQ/CSQ sample lower bound up to logs.
Problem
Learning the k-sparse parity on the uniform hypercube with gradient-based methods at sample complexity matching the statistical query lower bound (~d^k queries, ~d^{k-1} samples).
Approach
Uses a polynomial activation sigma(z)=z^k with fixed second layer, correlation loss, binary initialization, and a thresholded sign SGD update with weight decay; large batches make the stochastic sign gradient match the population sign gradient so that good neurons keep their feature coordinates while noise and bad neurons decay.
Key results
- Sample complexity Õ(d^{k-1}) with 2^{Θ(k)} neurons and O(k log d) sign SGD iterations, matching the SQ lower bound up to log factors (improving prior Õ(d^{k+1})).
- Synthetic experiments give test accuracy 99.69% (k=2), 97.75% (k=3), 96.89% (k=4), averaged over 10 runs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use online sign SGD with a two-layer network of width 2^{Θ(k)} | k-sparse parity learning · General k-parity | sample complexity: d^{k+1}·log(d/ε)/ε^2 -> d^{k-1}· polylog(d) | Helped |
| use sign SGD with polynomial activation and the stated training setup | two-layer fully-connected neural network · k-sparse parity, k=2 (d=8) | test accuracy: 99.69% ± 0.29% | Helped |
| use sign SGD with polynomial activation and the stated training setup | two-layer fully-connected neural network · k-sparse parity, k=3 (d=16) | test accuracy: 97.75% ± 1.37% | Helped |
| use sign SGD with polynomial activation and the stated training setup | two-layer fully-connected neural network · k-sparse parity, k=4 (d=20) | test accuracy: 96.89% ± 0.44% | Helped |
Limitations
- Analysis restricted to polynomial activation sigma(z)=z^k and fixed second layer in main theorem
- Relies on the standard basis (isotropic/coordinate-aligned) structure; non-standard coordinates may hurt sign SGD
- Experiments are small synthetic settings (d up to 20) and only validate k up to 4
Experimental setup
Datasets: synthetic k-parity data on uniform hypercube
Benchmarks: synthetic k-parity (k=2,3,4)
Metrics: test accuracy
Baselines: Abbe et al. leap-k SGD Barak et al. SGD k-parity mean-field Langevin dynamics (Suzuki et al.) NTK-based methods (Ghorbani et al.) Daniely & Malach SGD for XOR
Builds on: Statistical Query lower bounds leap complexity (Abbe et al.) Sign SGD
Closest papers by meaning
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.89)
- Learning High-Degree Parities: The Crucial Role of the Initialization (ICLR 2025 · similarity 0.87)
- A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.87)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.86)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.86)
- When and Why SignSGD Outperforms SGD: A Theoretical Study Based on $\ell_1$-norm Lower Bounds (NeurIPS 2026 · similarity 0.86)
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.