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.
- 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.
- 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}$.
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.
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