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

2024/04/18 by Yiwen Kou, Kou, Yiwen, Zixiang Chen +5 · 1 citation
Computer Science · #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs #Bayesian Modeling and Causal Inference

paper · pdf · doi:10.48550/arxiv.2404.12376

Abstract

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 O(d^k-1) using 2^Θ(k) neurons, matching the established Ω(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 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.

Cited by

• RL for Reasoning by Adaptively Revealing Rationales

Related

• Learning High-Degree Parities: The Crucial Role of the Initialization
• Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit
• Algorithms for Sparse LPN and LSPN Against Low-noise
• Hardness of Learning Fixed Parities with Neural Networks
• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries