Efficient active learning of sparse halfspaces with arbitrary bounded noise
Efficient active learning of sparse halfspaces with arbitrary bounded noise
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Chicheng Zhang;Jie Shen;Pranjal Awasthi
中科院分区：
文献类型：
--
作者：
Chicheng Zhang;Jie Shen;Pranjal Awasthi
研究了$\mathbb{R}^d$中齐次$S稀疏半空间在标签噪声作用下的主动学习问题。即使在弱标签噪声存在的情况下，这也是一个具有挑战性的问题，直到最近才建立了形式为(S\cdot\mathrm{PolyLog}(d，FRAC{1}{\epsilon}))的标签复杂性界，用于在广泛的各向同性对数凹分布下的计算高效算法。相比之下，在高水平的标签噪声下，计算效率高的算法所获得的标签复杂性界限要差得多。当标签噪声满足{\em Massart}条件\cite{Massart2006Risk}，即对于参数$\eta\in\BIG[0，\Frag12\BIG)}，每个标签以至多$\eta的概率被翻转时，最新的结果提供了在具有标签复杂性$\tilde{\mathcal{O}}(s^{\mathrm{poly}({1/(1-2\eta)})}\mathm{Poly}的各向同性对数凹分布下计算高效的主动学习算法，FRAC{1}{\epsilon})$))$，仅当噪声率$\eta$为常量时才是标签有效的。在这项工作中，我们设计了一个多项式时间算法，用于有界噪声和各向同性对数凹分布下的$S稀疏半空间的主动学习，其标签复杂性为$\tilde{\mathcal{O}}\Big(\frac{s}{(1-2\eta)^4}\mathm{PolyLog}(d，\FRAC 1\epsilon)\Big.这是在这种情况下第一个在$FRAC{1}{1-2\ETA}$中具有标签复杂性多项式的高效算法，即使对于任意接近$\FRAN12$的$\ETA$，它也是标签有效的。对于任意有界噪声和各向同性对数凹分布下的全维主动和被动半空间学习，我们的保证也立即转化为新的最先进的标签复杂性结果。
We study active learning of homogeneous $s$-sparse halfspaces in $\mathbb{R}^d$ under label noise. Even in the presence of mild label noise this is a challenging problem and only recently have label complexity bounds of the form $\tilde{\mathcal{O}} (s \cdot \mathrm{polylog}(d, \frac{1}{\epsilon}) )$ been established in \cite{zhang2018efficient} for computationally efficient algorithms under the broad class of isotropic log-concave distributions. In contrast, under high levels of label noise, the label complexity bounds achieved by computationally efficient algorithms are much worse. When the label noise satisfies the {\em Massart} condition \cite{massart2006risk}, i.e., each label is flipped with probability at most $\eta$ for a parameter $\eta \in \big[0, \frac12\big)$, state-of-the-art result \cite{awasthi2016learning} provides a computationally efficient active learning algorithm under isotropic log-concave distributions with label complexity $\tilde{\mathcal{O}}(s^{\mathrm{poly}({1/(1-2\eta)})} \mathrm{poly}(\ln d, \frac{1}{\epsilon}) )$, which is label-efficient only when the noise rate $\eta$ is a constant. In this work, we substantially improve on it by designing a polynomial time algorithm for active learning of $s$-sparse halfspaces under bounded noise and isotropic log-concave distributions, with a label complexity of $\tilde{\mathcal{O}}\Big(\frac{s}{(1-2\eta)^4} \mathrm{polylog} (d, \frac 1 \epsilon) \Big)$. This is the first efficient algorithm with label complexity polynomial in $\frac{1}{1-2\eta}$ in this setting, which is label-efficient even for $\eta$ arbitrarily close to $\frac12$. Our guarantees also immediately translate to new state-of-the-art label complexity results for full-dimensional active and passive halfspace learning under arbitrary bounded noise and isotropic log-concave distributions.