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{\Theta}(d/\epsilon)$, where $d$ is the dimension and $\epsilon$ is
the excess error. Our positive result is a computationally efficient learning
algorithm with sample complexity $\tilde{O}(d/\epsilon + d/(\max\{p,
\epsilon\})^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 $\Omega(d^{1/2}/(\max\{p,
\epsilon\})^2)$. Our lower bound suggests that this quadratic dependence on
$1/\epsilon$ is inherent for efficient algorithms.

研究使用高斯分布下随机分类噪声学习半空间的问题，证明算法和统计查询下限，在此基本问题中，存在令人惊讶的信息计算差距，给出了正面的结果和近乎匹配的复杂度，并展示了算法的复杂度下界