Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent
<|reference_start|>Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent: The $k$-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$-parity problem with stochastic gradient descent (SGD) on two-layer fully-connected neural networks. We demonstrate that SGD can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube ($k\le O(\sqrt{d})$) with a sample complexity of $\tilde{O}(d^{k-1})$ using $2^{\Theta(k)}$ neurons, thus matching the established $\Omega(d^{k})$ 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 SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors. Our theoretical results and findings are supported by empirical evidence, showcasing the efficiency and efficacy of our approach.<|reference_end|>
@article{kou2024matching,
    title={Matching the Statistical Query Lower Bound for k-sparse Parity Problems
  with Stochastic Gradient Descent},
    author={Yiwen Kou, Zixiang Chen, Quanquan Gu, Sham M. Kakade},
    journal={arXiv preprint arXiv:2404.12376},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.12376},
    primaryClass={cs.LG math.OC stat.ML}
}