Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise
This work addresses a fundamental problem in computational learning theory for researchers, showing an inherent quadratic dependence on error for efficient algorithms, which is incremental in refining bounds for noisy halfspace learning.
The paper tackles the problem of learning general halfspaces with random classification noise under Gaussian distributions, establishing nearly-matching algorithmic and lower bound results that reveal an information-computation gap, with sample complexity of Θ̃(d/ε) and efficient algorithms requiring at least Ω(d^{1/2}/(max{p, ε})^2).
We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces with Random Classification Noise under the Gaussian distribution. We establish nearly-matching algorithmic and Statistical Query (SQ) lower bound results revealing a surprising information-computation gap for this basic problem. Specifically, the sample complexity of this learning problem is $\widetildeΘ(d/ε)$, where $d$ is the dimension and $ε$ is the excess error. Our positive result is a computationally efficient learning algorithm with sample complexity $\tilde{O}(d/ε+ d/(\max\{p, ε\})^2)$, where $p$ quantifies the bias of the target halfspace. On the lower bound side, we show that any efficient SQ algorithm (or low-degree test) for the problem requires sample complexity at least $Ω(d^{1/2}/(\max\{p, ε\})^2)$. Our lower bound suggests that this quadratic dependence on $1/ε$ is inherent for efficient algorithms.