English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study {\em online} active learning of homogeneous halfspaces in$\mathbb{R}^d$ with adversarial noise where the overall probability of a noisylabel is constrained to be at most $\nu$. Our main contribution is aPerceptron-like online active learning algorithm that runs in polynomial time,and under the conditions that the marginal distribution is isotropiclog-concave and $\nu = \Omega(\epsilon)$, where $\epsilon \in (0, 1)$ is thetarget error rate, our algorithm PAC learns the underlying halfspace withnear-optimal label complexity of $\tilde{O}\big(d \cdotpolylog(\frac{1}{\epsilon})\big)$ and sample complexity of$\tilde{O}\big(\frac{d}{\epsilon} \big)$. Prior to this work, existing onlinealgorithms designed for tolerating the adversarial noise are subject to eitherlabel complexity polynomial in $\frac{1}{\epsilon}$, or suboptimal noisetolerance, or restrictive marginal distributions. With the additional priorknowledge that the underlying halfspace is $s$-sparse, we obtainattribute-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 immediatecorollary, we show that under the agnostic model where no assumption is made onthe 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.

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