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

It has been a long-standing problem to efficiently learn a halfspace using asfew labels as possible in the presence of noise. In this work, we propose anefficient Perceptron-based algorithm for actively learning homogeneoushalfspaces under the uniform distribution over the unit sphere. Under thebounded noise condition~\cite{MN06}, where each label is flipped withprobability at most $\eta < \frac 1 2$, our algorithm achieves a near-optimallabel complexity of$\tilde{O}\left(\frac{d}{(1-2\eta)^2}\ln\frac{1}{\epsilon}\right)$ in time$\tilde{O}\left(\frac{d^2}{\epsilon(1-2\eta)^3}\right)$. Under the adversarialnoise condition~\cite{ABL14, KLS09, KKMS08}, where at most a $\tilde\Omega(\epsilon)$ fraction of labels can be flipped, our algorithm achieves anear-optimal label complexity of $\tilde{O}\left(d\ln\frac{1}{\epsilon}\right)$in time $\tilde{O}\left(\frac{d^2}{\epsilon}\right)$. Furthermore, we show thatour active learning algorithm can be converted to an efficient passive learningalgorithm that has near-optimal sample complexities with respect to $\epsilon$and $d$.

Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces