Projects per year
Abstract
We study highdimensional 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 highdimensional agnostic distribution learning even possible, algorithmically?
In this work, we obtain the first computationally efficient algorithms for agnostically learning several fundamental classes of highdimensional 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 nearlylinearly on the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in highdimensions, that may be applicable to many other problems.
In this work, we obtain the first computationally efficient algorithms for agnostically learning several fundamental classes of highdimensional 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 nearlylinearly on the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in highdimensions, that may be applicable to many other problems.
Original language  English 

Title of host publication  Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on 
Publisher  Institute of Electrical and Electronics Engineers (IEEE) 
Pages  655664 
Number of pages  10 
ISBN (Electronic)  9781509039333 
ISBN (Print)  9781509039340 
DOIs  
Publication status  Published  15 Dec 2016 
Event  57th Annual Symposium on Foundations of Computer Science  New Brunswick, United States Duration: 9 Oct 2016 → 11 Oct 2016 http://dimacs.rutgers.edu/archive/FOCS16/ 
Publication series
Name  

Publisher  IEEE 
ISSN (Print)  02725428 
Conference
Conference  57th Annual Symposium on Foundations of Computer Science 

Abbreviated title  FOCS 2016 
Country  United States 
City  New Brunswick 
Period  9/10/16 → 11/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.Projects
 1 Finished

Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research