论文标题
有效地学习具有任意有界噪声的稀疏半空间
Efficient active learning of sparse halfspaces with arbitrary bounded noise
论文作者
论文摘要
我们在$ \ mathbb {r}^d $中的同质$ s $ s $ s $ s $ s-sparse Halfspaces在未标记的数据分布的设置下是各向同性的log-concave，并且每个标签都以$η$的概率为$η$，用于参数$η\ in \ big big [0，\ big frac12 $ hig y hig frac12 $ big）$ big big y Big），即使存在温和的标签噪音，即$η$也是一个小的常数，这是一个具有挑战性的问题，直到最近才具有$ \ tilde {o} \ big（s \ cdot \ cdot \ cdot \ cdot \ mathrm {polylog}（d，d，d，\ frac {1}}} frac {1}ε）\ big）的标签复杂性范围。相比之下，在高水平的标签噪声下，通过计算有效算法实现的标签复杂性界限要糟糕得多：[Awasthi等人，2016]的最著名结果提供了一种计算上有效的算法，具有标签复杂性$ \ tilde $ \ tilde {o} {o} {o} \ big（（\ freac） d}ε）^{2^{\ mathrm {poly}（1/（1-2η））}}} \ big）$，仅当噪声率$η$是固定常数时，它才能有效。在这项工作中，我们通过设计一种多项式时间算法来进行重大改进这是在$ \ frac {1} {1} {1-2η} $中使用标签复杂性多项式的第一种有效算法，在此设置中，它的标签有效，即使对于$η$，任意接近$ \ frac12 $。我们的主动学习算法及其理论保证也立即转化为新的最新标签和样品复杂性结果，以在任意有界噪声下进行全维活动和被动的半空间学习。我们算法和分析的主要见解是对在线学习遗憾不平等的新解释，这可能具有独立的兴趣。
We study active learning of homogeneous $s$-sparse halfspaces in $\mathbb{R}^d$ under the setting where the unlabeled data distribution is isotropic log-concave and each label is flipped with probability at most $η$ for a parameter $η\in \big[0, \frac12\big)$, known as the bounded noise. Even in the presence of mild label noise, i.e. $η$ is a small constant, this is a challenging problem and only recently have label complexity bounds of the form $\tilde{O}\big(s \cdot \mathrm{polylog}(d, \frac{1}ε)\big)$ been established in [Zhang, 2018] for computationally efficient algorithms. In contrast, under high levels of label noise, the label complexity bounds achieved by computationally efficient algorithms are much worse: the best known result of [Awasthi et al., 2016] provides a computationally efficient algorithm with label complexity $\tilde{O}\big((\frac{s \ln d}ε)^{2^{\mathrm{poly}(1/(1-2η))}} \big)$, which is label-efficient only when the noise rate $η$ is a fixed constant. In this work, we substantially improve on it by designing a polynomial time algorithm for active learning of $s$-sparse halfspaces, with a label complexity of $\tilde{O}\big(\frac{s}{(1-2η)^4} \mathrm{polylog} (d, \frac 1 ε) \big)$. This is the first efficient algorithm with label complexity polynomial in $\frac{1}{1-2η}$ in this setting, which is label-efficient even for $η$ arbitrarily close to $\frac12$. Our active learning algorithm and its theoretical guarantees also immediately translate to new state-of-the-art label and sample complexity results for full-dimensional active and passive halfspace learning under arbitrary bounded noise. The key insight of our algorithm and analysis is a new interpretation of online learning regret inequalities, which may be of independent interest.
