Abstract
The $k$-parity problem is a classical problem in computational complexity andalgorithmic theory, serving as a key benchmark for understanding computationalclasses. In this paper, we solve the $k$-parity problem with stochasticgradient descent (SGD) on two-layer fully-connected neural networks. Wedemonstrate 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 theestablished $\Omega(d^{k})$ lower bounds of Statistical Query (SQ) models. Ourtheoretical analysis begins by constructing a good neural network capable ofcorrectly solving the $k$-parity problem. We then demonstrate how a trainedneural network with SGD can effectively approximate this good network, solvingthe $k$-parity problem with small statistical errors. Our theoretical resultsand findings are supported by empirical evidence, showcasing the efficiency andefficacy of our approach.