Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
share
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 Θ(1/(γ^2 ϵ)). We start by giving a simple efficient algorithm with sample complexity 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 Ω(1/(γ^1/2ϵ^2)) on the sample complexity of any efficient SQ learner or low-degree test.
READ FULL TEXT