Learning geometric concepts with nasty noise

DOI10.1145/3188745.3188754MaRDI QIDQ5230362zbMATH OpenOpenAlexFDO

Authors Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.01242

zbMATH Keywords

intersections of halfspacesmalicious noisenasty noisePAC learningpolynomial threshold functions

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We study the efficient learnability of geometric concept classes - specifically, low-degree polynomial threshold functions (PTFs) and intersections of halfspaces - when a fraction of the data is adversarially corrupted. We give the first polynomial-time PAC learning algorithms for these concept classes with dimension-independent error guarantees in the presence of nasty noise under the Gaussian distribution. In the nasty noise model, an omniscient adversary can arbitrarily corrupt a small fraction of both the unlabeled data points and their labels. This model generalizes well-studied noise models, including the malicious noise model and the agnostic (adversarial label noise) model. Prior to our work, the only concept class for which efficient malicious learning algorithms were known was the class of origin-centered halfspaces. Specifically, our robust learning algorithm for low-degree PTFs succeeds under a number of tame distributions -- including the Gaussian distribution and, more generally, any log-concave distribution with (approximately) known low-degree moments. For LTFs under the Gaussian distribution, we give a polynomial-time algorithm that achieves error $O(epsilon)$, where $epsilon$ is the noise rate. At the core of our PAC learning results is an efficient algorithm to approximate the low-degree Chow-parameters of any bounded function in the presence of nasty noise. To achieve this, we employ an iterative spectral method for outlier detection and removal, inspired by recent work in robust unsupervised learning. Our aforementioned algorithm succeeds for a range of distributions satisfying mild concentration bounds and moment assumptions. The correctness of our robust learning algorithm for intersections of halfspaces makes essential use of a novel robust inverse independence lemma that may be of broader interest.

Recommendations

• Learning Halfspaces with Malicious Noise
• Learning halfspaces with malicious noise
• scientific article; zbMATH DE number 1453040
• PAC learning with nasty noise.

Cited in

(8)

• Generalized resilience and robust statistics
• Stronger data poisoning attacks break data sanitization defenses
• Learning halfspaces with malicious noise
• Robust estimators in high-dimensions without the computational intractability
• Distributionally robust optimization and robust statistics
• Attribute-efficient learning of halfspaces with malicious noise: near-optimal label complexity and noise tolerance
• Understanding simultaneous train and test robustness
• The full landscape of robust mean testing: sharp separations between oblivious and adaptive contamination

This page was built for publication: Learning geometric concepts with nasty noise

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230362)