论文标题
与Massart噪声学习半空间的加密硬度
Cryptographic Hardness of Learning Halfspaces with Massart Noise
论文作者
论文摘要
我们研究了Massart噪声存在下PAC学习半空间的复杂性。在这个问题中，我们得到了I.I.D.标记的示例$（\ Mathbf {x}，y）\ in \ Mathbb {r}^n \ times \ times \ {\ pm 1 \} $，其中$ \ mathbf {x} $的分布是任意的\ Mathbb {r}^n \ to \ {\ pm 1 \} $，带有翻转概率$η（\ mathbf {x}）\ leq leqη<1/2 $。学习者的目的是计算一个以较小0-1误差的假设。我们的主要结果是该学习问题的第一个计算硬度结果。具体而言，假设学习错误（LWE）问题（LWE）问题的（被广泛相信）的超额指定时间硬度，我们表明，即使最佳的0-1错误很小，也没有多项式时间弥撒半空间学习者可以更好地达到误差，即使最佳0-1错误是小的，也就是$ \ nmatrm {opt} = 2^= 2^= 2^{c} ncortion n countion n counce n nustrucation n compand^n countion n counce^{c} （0，1）$。先前的工作在统计查询模型中提供了定性相似的硬度证据。我们的计算硬度结果基本上可以解决Massart Halfspaces的多项式PAC可学习性，这表明对该问题的已知有效学习算法几乎是最好的。
We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i.i.d. labeled examples $(\mathbf{x}, y) \in \mathbb{R}^N \times \{ \pm 1\}$, where the distribution of $\mathbf{x}$ is arbitrary and the label $y$ is a Massart corruption of $f(\mathbf{x})$, for an unknown halfspace $f: \mathbb{R}^N \to \{ \pm 1\}$, with flipping probability $η(\mathbf{x}) \leq η< 1/2$. The goal of the learner is to compute a hypothesis with small 0-1 error. Our main result is the first computational hardness result for this learning problem. Specifically, assuming the (widely believed) subexponential-time hardness of the Learning with Errors (LWE) problem, we show that no polynomial-time Massart halfspace learner can achieve error better than $Ω(η)$, even if the optimal 0-1 error is small, namely $\mathrm{OPT} = 2^{-\log^{c} (N)}$ for any universal constant $c \in (0, 1)$. Prior work had provided qualitatively similar evidence of hardness in the Statistical Query model. Our computational hardness result essentially resolves the polynomial PAC learnability of Massart halfspaces, by showing that known efficient learning algorithms for the problem are nearly best possible.
