Matching the Statistical Query Lower Bound for k-sparse Parity Problems
  with Stochastic Gradient Descent
Yiwen Kou Zixiang Chen Quanquan Gu Sham M. Kakade
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.