Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
This addresses a fundamental limitation in machine learning theory for researchers, revealing inherent computational barriers in learning noisy halfspaces, which is incremental as it builds on prior tradeoff studies.
The paper tackles the problem of PAC learning margin halfspaces with random classification noise, establishing an information-computation tradeoff where the optimal sample complexity is Θ̃(1/(γ²ε)), but efficient algorithms require at least Ω̃(1/(γ¹/²ε²)), showing a quadratic gap in 1/ε for computational efficiency.
We study the problem of PAC learning $γ$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms. Concretely, the sample complexity of the problem is $\widetildeΘ(1/(γ^2 ε))$. We start by giving a simple efficient algorithm with sample complexity $\widetilde{O}(1/(γ^2 ε^2))$. Our main result is a lower bound for Statistical Query (SQ) algorithms and low-degree polynomial tests suggesting that the quadratic dependence on $1/ε$ in the sample complexity is inherent for computationally efficient algorithms. Specifically, our results imply a lower bound of $\widetildeΩ(1/(γ^{1/2} ε^2))$ on the sample complexity of any efficient SQ learner or low-degree test.