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/

Zendy Plus

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

Zendy Tools

Zendy Open

We study the efficient learnability of geometric concept classes -specifically, low-degree polynomial threshold functions (PTFs) andintersections of halfspaces - when a fraction of the data is adversariallycorrupted. We give the first polynomial-time PAC learning algorithms for theseconcept classes with dimension-independent error guarantees in the presence ofnasty noise under the Gaussian distribution. In the nasty noise model, anomniscient adversary can arbitrarily corrupt a small fraction of both theunlabeled data points and their labels. This model generalizes well-studiednoise models, including the malicious noise model and the agnostic (adversariallabel noise) model. Prior to our work, the only concept class for whichefficient malicious learning algorithms were known was the class oforigin-centered halfspaces.  Specifically, our robust learning algorithm for low-degree PTFs succeedsunder a number of tame distributions -- including the Gaussian distributionand, more generally, any log-concave distribution with (approximately) knownlow-degree moments. For LTFs under the Gaussian distribution, we give apolynomial-time algorithm that achieves error $O(\epsilon)$, where $\epsilon$is the noise rate. At the core of our PAC learning results is an efficientalgorithm to approximate the low-degree Chow-parameters of any bounded functionin the presence of nasty noise. To achieve this, we employ an iterativespectral method for outlier detection and removal, inspired by recent work inrobust unsupervised learning. Our aforementioned algorithm succeeds for a rangeof distributions satisfying mild concentration bounds and moment assumptions.The correctness of our robust learning algorithm for intersections ofhalfspaces makes essential use of a novel robust inverse independence lemmathat may be of broader interest.

Learning Geometric Concepts with Nasty Noise