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 efficient PAC learning of homogeneous halfspaces in $\mathbb{R}^d$in the presence of malicious noise of Valiant (1985). This is a challengingnoise model and only until recently has near-optimal noise tolerance bound beenestablished under the mild condition that the unlabeled data distribution isisotropic log-concave. However, it remains unsettled how to obtain the optimalsample complexity simultaneously. In this work, we present a new analysis forthe algorithm of Awasthi et al. (2017) and show that it essentially achievesthe near-optimal sample complexity bound of $\tilde{O}(d)$, improving the bestknown result of $\tilde{O}(d^2)$. Our main ingredient is a novel incorporationof a matrix Chernoff-type inequality to bound the spectrum of an empiricalcovariance matrix for well-behaved distributions, in conjunction with a carefulexploration of the localization schemes of Awasthi et al. (2017). We furtherextend the algorithm and analysis to the more general and stronger nasty noisemodel of Bshouty et al. (2002), showing that it is still possible to achievenear-optimal noise tolerance and sample complexity in polynomial time.

Sample-Optimal PAC Learning of Halfspaces with Malicious Noise