Efficient active learning of sparse halfspaces with arbitrary bounded noise

We study active learning of homogeneous s-sparse halfspaces in ℝ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 η ∈ big[0, frac12big), 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 tildeObig(s · polylog(d, frac1ε)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 tildeObig((fracs ln dε)^2poly(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 tildeObig(fracs(1-2η)4 polylog (d, frac 1 ε) big). This is the first efficient algorithm with label complexity polynomial in frac11-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.