# Matching the Statistical Query Lower Bound for k-Sparse Parity Problems with Sign Stochastic Gradient Descent

arXiv: https://arxiv.org/abs/2404.12376 · HTML: https://mlsanity.com/paper/2404.12376/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2024.

## Built on by (most cited first, 7 of 7)

- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [RL for Reasoning by Adaptively Revealing Rationales](https://mlsanity.com/paper/2506.18110/) (2025)
- [Qsharp: Provably Optimal Distributional RL for LLM Post-Training](https://mlsanity.com/paper/2502.20548/) (2025)
- [Tuning the Implicit Regularizer of Masked Diffusion Language Models: Enhancing Generalization via Insights from k-Parity](https://mlsanity.com/paper/2601.22450/) (2026)
- [The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently](https://mlsanity.com/paper/2605.10237/) (2026)
- [Learning with Shallow Neural Networks on Cluster-Structured Features](https://mlsanity.com/paper/2605.14927/) (2026)
- [Neuron Block Dynamics for XOR Classification with Zero-Margin](https://mlsanity.com/paper/2602.00172/) (2026)

## Abstract (arXiv)

The k-sparse parity problem is a classical problem in computational complexity and algorithmic theory, serving as a key benchmark for understanding computational classes. In this paper, we solve the k-sparse parity problem with sign stochastic gradient descent, a variant of stochastic gradient descent (SGD) on two-layer fully-connected neural networks. We demonstrate that this approach can efficiently solve the k-sparse parity problem on a d-dimensional hypercube (k≤ O(√d)) with a sample complexity of tildeO(dk-1) using 2Theta(k) neurons, matching the established Omega(dk) lower bounds of Statistical Query (SQ) models. Our theoretical analysis begins by constructing a good neural network capable of correctly solving the k-parity problem. We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the k-parity problem with small statistical errors. To the best of our knowledge, this is the first result that matches the SQ lower bound for solving k-sparse parity problem using gradient-based methods.