论文标题
具有恶意噪声的半空间的属性学习：近乎最佳的标签复杂性和噪声耐受性
Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
论文作者
论文摘要
本文涉及$ \ mathbb {r}^d $在噪声下的均匀稀疏半空间的计算有效学习。尽管最近的作品已经在各种类型的标签噪声（例如有限的噪声）下建立了属性效率的学习算法，但在充满挑战的恶意噪声模型下，$ s $ s $ s $ -s-s $ -s-s $ s $ -s-s $ s的半空间仍然是一个悬而未决的问题，在这个挑战性的恶意噪声模型下，对手可能会损坏两个未经保证的示例和标签。我们通过设计一种具有$ \ tilde {o} \ big（{s \ log^4 \ frac diam} \ big）$和噪声容忍度$ n =ω（ε）$的$ huse（ε）$，在$ pressive $ pressive $ pressive的情况下，我们在（0）$ pressivation $下，（n in IS n in IS 0），我们在$ big（0）$ε （未腐烂的）未标记的例子是各向同性对数洞穴。我们的算法可以直接定制为被动学习设置，我们表明样品复杂性为$ \ tilde {o} \ big（{\ frac1εs^2 \ log^5 d} \ big）$，也享受属性效率。我们的主要技术包括属性有效的范例，例如重新加权和经验风险最小化，以及对无限数据的均匀浓度进行的新分析 - 所有这些都至关重要的是考虑到基础半空间的结构。
This paper is concerned with computationally efficient learning of homogeneous sparse halfspaces in $\mathbb{R}^d$ under noise. Though recent works have established attribute-efficient learning algorithms under various types of label noise (e.g. bounded noise), it remains an open question when and how $s$-sparse halfspaces can be efficiently learned under the challenging malicious noise model, where an adversary may corrupt both the unlabeled examples and the labels. We answer this question in the affirmative by designing a computationally efficient active learning algorithm with near-optimal label complexity of $\tilde{O}\big({s \log^4 \frac d ε} \big)$ and noise tolerance $η= Ω(ε)$, where $ε\in (0, 1)$ is the target error rate, under the assumption that the distribution over (uncorrupted) unlabeled examples is isotropic log-concave. Our algorithm can be straightforwardly tailored to the passive learning setting, and we show that the sample complexity is $\tilde{O}\big({\frac 1 εs^2 \log^5 d} \big)$ which also enjoys the attribute efficiency. Our main techniques include attribute-efficient paradigms for instance reweighting and for empirical risk minimization, and a new analysis of uniform concentration for unbounded data -- all of them crucially take the structure of the underlying halfspace into account.
