On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise

Abstract

We study {\em online} active learning of homogeneous halfspaces in ${\mathbb{R}}^d$ with adversarial noise where the overall probability of a noisy label is constrained to be at most $\nu$. Our main contribution is a Perceptron-like online active learning algorithm that runs in polynomial time, and under the conditions that the marginal distribution is isotropic log-concave and $\nu =\Omega (\epsilon )$, where $\epsilon \in (0,1)$ is the target error rate, our algorithm PAC learns the underlying halfspace with near-optimal label complexity of $\tilde{O}(d\cdot polylog(\frac{1}{\epsilon }))$ and sample complexity of $\tilde{O}\left(\frac{d}{\epsilon }\right)$. Prior to this work, existing online algorithms designed for tolerating the adversarial noise are subject to either label complexity polynomial in $\frac{1}{\epsilon }$, or suboptimal noise tolerance, or restrictive marginal distributions. With the additional prior knowledge that the underlying halfspace is $s$-sparse, we obtain attribute-efficient label complexity of $\tilde{O}(s\cdot polylog(d,\frac{1}{\epsilon }))$ and sample complexity of $\tilde{O}(\frac{s}{\epsilon }\cdot polylog(d))$. As an immediate corollary, we show that under the agnostic model where no assumption is made on the noise rate $\nu$, our active learner achieves an error rate of $O(OPT)+\epsilon$ with the same running time and label and sample complexity, where $OPT$ is the best possible error rate achievable by any homogeneous halfspace.

V2 and V3 polished writing; accepted to ICML 2021

References in corpus (6)

• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional classification using features annealed independence rules
• Agnostic Active Learning Without Constraints
• Beyond Disagreement-based Agnostic Active Learning
• Learning Halfspaces with Massart Noise Under Structured Distributions
• Efficient Learning of Linear Separators under Bounded Noise

Cited by in corpus (1)

• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise