Efficient active learning of sparse halfspaces with arbitrary bounded noise

Chicheng Zhang, Jie Shen, Pranjal Awasthi

Introduction

Learning linear classifiers, or halfspaces, is a cornerstone of machine learning. In practical scenarios, however, we often face three simultaneous challenges: high-dimensional data where only a few features are relevant (sparsity), the high cost of obtaining labels (necessitating active learning), and the presence of label noise. This work addresses the bounded noise model (Massart noise), where the probability of a label being flipped is at most $\eta < 1/2$.

Historically, computationally efficient active learning algorithms struggled with high noise levels. While they performed well for very small $\eta$, their label complexity exploded exponentially as $\eta$ approached $1/2$. We bridge this gap by introducing a polynomial-time algorithm that maintains label efficiency even under high noise.

Methodology: From Online Learning to Active Learning

Our approach utilizes a two-stage strategy to achieve noise tolerance and sample efficiency.

  1. Averaging-based Initialization: We begin with a small batch of random samples to establish a coarse initial classifier. This stage uses an averaging scheme combined with hard-thresholding to identify the relevant features in the sparse setting.
  2. Refinement via Online Mirror Descent: The core of our algorithm is a refinement phase that treats active learning as an online regret minimization problem. We selectively query labels for examples near the current decision boundary.

Crucially, we move beyond mistake-driven updates like the Perceptron. We introduce a noise-tolerant gradient update that incorporates the noise rate $\eta$. This rule updates the model even when the current prediction is correct, a counter-intuitive step that mathematically counteracts the drift caused by asymmetric noise distributions. By employing online mirror descent with $p$-norm regularizers, the algorithm naturally adapts to the underlying sparsity $s$ of the problem.

Key Insights

  • Correcting for Asymmetric Drift: In the presence of noise and asymmetric data distributions, standard mistake-driven updates can lead to biased models. Our update rule ensures the expected update direction remains aligned with the true classifier.
  • Regret-to-Active Learning Pipeline: We provide a novel interpretation of online learning regret inequalities. We demonstrate that bounding the regret of a sequence of adaptively sampled loss functions allows for the extraction of a highly accurate final classifier.
  • Attribute Efficiency: The use of sparsity-inducing regularizers ensures that the label complexity depends primarily on the number of relevant features $s$ and only logarithmically on the total dimension $d$.

Key Results

Our algorithm establishes new state-of-the-art bounds for both sparse and non-sparse halfspace learning.

Sparse Halfspaces

For $s$-sparse halfspaces, we achieve a label complexity of $\tilde{O}\big(\frac{s}{(1-2\eta)^4} \text{polylog}(d, \frac{1}{\epsilon})\big)$. This represents the first efficient algorithm where complexity scales polynomially with $\frac{1}{1-2\eta}$.

Comparison of label complexity for sparse halfspaces under bounded noise.

General (Non-Sparse) Halfspaces

Even in the general case where $s=d$, our algorithm provides a significant improvement over previous methods, reducing the dependence on the noise rate from exponential to polynomial.

Comparison of label complexity for general (non-sparse) halfspaces under bounded noise.

Beyond active learning, these results also translate to improved sample complexity for passive (standard supervised) learning under bounded noise.

Limitations and Future Directions

While this work marks a significant step forward, several avenues for future research remain:

  • Initialization Gap: The initialization phase currently requires $\tilde{O}(s/(1-2\eta)^4)$ labels, which is slightly higher than the information-theoretic lower bound of $\tilde{O}(s/(1-2\eta)^2)$.
  • Distributional Constraints: Our theoretical guarantees assume the unlabeled data follows an isotropic log-concave distribution. Relaxing these assumptions for more complex distributions is a key goal.
  • Broader Noise Models: The online-learning-to-active-learning framework developed here may be applicable to other challenging noise models, such as Tsybakov or adversarial noise.

Summary updated

Abstract

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 $\eta$ for a parameter $\eta \in \big[0, \frac12\big)$, known as the bounded noise. Even in the presence of mild label noise, i.e. $\eta$ 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}{\epsilon})\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}{\epsilon})^{2^{\mathrm{poly}(1/(1-2\eta))}} \big)$, which is label-efficient only when the noise rate $\eta$ 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\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 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.
BibTeX
@inproceedings{zhang2020efficient,
  author = {Chicheng Zhang and Jie Shen and Pranjal Awasthi},
  title = {{Efficient active learning of sparse halfspaces with arbitrary bounded noise}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=SAxW6l1ulZ5},
}
Figure