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

Jie Shen
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:9503-9514, 2021.

Abstract

We study {\em online} active learning of homogeneous halfspaces in Rd with adversarial noise where the overall probability of a noisy label is constrained to be at most ν. 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 ν=Ω(ϵ), where ϵ∈(0,1) is the target error rate, our algorithm PAC learns the underlying halfspace with near-optimal label complexity of ˜O(d⋅\polylog(1ϵ)) and sample complexity of ˜O(dϵ). Prior to this work, existing online algorithms designed for tolerating the adversarial noise are subject to either label complexity polynomial in 1ϵ, 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 ˜O(s⋅\polylog(d,1ϵ)) and sample complexity of ˜O(sϵ⋅\polylog(d)). As an immediate corollary, we show that under the agnostic model where no assumption is made on the noise rate ν, our active learner achieves an error rate of O(OPT)+ϵ with the same running time and label and sample complexity, where OPT is the best possible error rate achievable by any homogeneous halfspace.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-shen21a, title = {On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise}, author = {Shen, Jie}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {9503--9514}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/shen21a/shen21a.pdf}, url = {https://proceedings.mlr.press/v139/shen21a.html}, 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}\big(d \cdot \polylog(\frac{1}{\epsilon})\big)$ and sample complexity of $\tilde{O}\big(\frac{d}{\epsilon} \big)$. 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}\big( s \cdot \polylog(d, \frac{1}{\epsilon}) \big)$ and sample complexity of $\tilde{O}\big(\frac{s}{\epsilon} \cdot \polylog(d) \big)$. 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.} }
Endnote
%0 Conference Paper %T On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise %A Jie Shen %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-shen21a %I PMLR %P 9503--9514 %U https://proceedings.mlr.press/v139/shen21a.html %V 139 %X 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}\big(d \cdot \polylog(\frac{1}{\epsilon})\big)$ and sample complexity of $\tilde{O}\big(\frac{d}{\epsilon} \big)$. 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}\big( s \cdot \polylog(d, \frac{1}{\epsilon}) \big)$ and sample complexity of $\tilde{O}\big(\frac{s}{\epsilon} \cdot \polylog(d) \big)$. 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.
APA
Shen, J.. (2021). On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:9503-9514 Available from https://proceedings.mlr.press/v139/shen21a.html.

Related Material