Learning geometric concepts with nasty noise

By Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. 2017

108 citations recorded by the source corpus.

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 training 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. At the core of our results is an efficient algorithm to approximate the low-degree Chow-parameters of any bounded function in the presence of nasty noise. Our robust approximation algorithm for the Chow parameters provides near-optimal error guarantees for a range of distribution families satisfying mild concentration bounds and moment conditions. At the technical level, this algorithm employs an iterative “spectral” technique for outlier detection and removal inspired by recent work in robust unsupervised learning, which makes essential use of low-degree multivariate polynomials. Our robust learning algorithm for low-degree PTFs provides dimension-independent error guarantees for a class of tame distributions, including Gaussians and, more generally, any logconcave distribution with (approximately) known low-degree moments. For LTFs under the Gaussian distribution, using a refinement of the localization technique, we give a polynomial-time algorithm that achieves a near-optimal error of O(є), where є is the noise rate. Our robust learning algorithm for intersections of halfspaces proceeds by projecting down to an appropriate low-dimensional subspace. Its correctness makes essential use of a novel robust inverse independence lemma that is of independent interest.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “There has since been considerable study of algorithmic robust estimation in high dimensions, including learning graphical models [DKS16], understanding computation-robustness tradeoffs [DKS17c, DKK18], establishing connections to PAC learning [DKS17a], tolerating more noise by outputting a list of h”
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, methodology): “This includes robust estimation of graphical models [DKS16a], handling a large fraction of corruptions in the list-decodable model [CSV17, SCV17], developing robust algorithms under sparsity assumptions [BDLS17], obtaining optimal error guarantees [DKK+17b], establishing computational lower bounds f”
A Data Prism: Semi-verified learning in the small-alpha regime (2018, background): “The works (Steinhardt et al., 2016) and (Charikar et al., 2017) and the very recent work (Diakonikolas et al., 2017b) consider the setting where a minority of the data is “good” (i.e. α 1/2), with (Charikar et al., 2017) formally proposing the “semi-verified” learning model where one may obtain a…”
Mixture models, robustness, and sum of squares proofs (2017, background): “There has been a long line of work on making algorithms tolerant to error in supervised settings [41, 66], especially for learning halfspaces [4, 28, 42, 60], and for problems such as PCA [15, 16, 47, 70].”