Robust Estimators in High Dimensions without the Computational Intractability

Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an epsilon fraction of the samples. Such questions have a rich history spanning statistics, machine learning and theoretical computer science. Even in the most basic settings, the only known approaches are either computationally inefficient or lose dimension dependent factors in their error guarantees. This raises the following question: Is high-dimensional agnostic distribution learning even possible, algorithmically?
In this work, we obtain the first computationally efficient algorithms for agnostically learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of k Gaussians with identical spherical covariances. All our algorithms achieve error that is independent of the dimension, and in many cases depends nearly-linearly on the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in high-dimensions, that may be applicable to many other problems.
Original languageEnglish
Title of host publicationFoundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages655-664
Number of pages10
ISBN (Electronic)978-1-5090-3933-3
ISBN (Print)978-1-5090-3934-0
DOIs
Publication statusPublished - 15 Dec 2016
Event57th Annual Symposium on Foundations of Computer Science - New Brunswick, United States
Duration: 9 Oct 201611 Oct 2016
http://dimacs.rutgers.edu/archive/FOCS16/

Publication series

Name
PublisherIEEE
ISSN (Print)0272-5428

Conference

Conference57th Annual Symposium on Foundations of Computer Science
Abbreviated titleFOCS 2016
CountryUnited States
CityNew Brunswick
Period9/10/1611/10/16
Internet address

Fingerprint

Dive into the research topics of 'Robust Estimators in High Dimensions without the Computational Intractability'. Together they form a unique fingerprint.

Cite this