Robust Estimators in High Dimensions without the Computational Intractability

2016/04/21 by Diakonikolas, Ilias, Kamath, Gautam, Kane, Daniel +3 · 14 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1604.06443

Abstract

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an ε-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 with dimension-independent error guarantees 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 spherical Gaussians. Our algorithms achieve error that is independent of the dimension, and in many cases scales nearly-linearly with 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.

Cited by

• Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery
• Robust and Sparse Estimation of Unbounded Density Ratio under Heavy Contamination
• Shadow Tomography Against Adversaries
• High-Accuracy List-Decodable Mean Estimation
• Watermark Robustness and Radioactivity May Be at Odds in Federated Learning
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
• Agnostic Product Mixed State Tomography via Robust Statistics
• On the Optimality of the Median-of-Means Estimator under Adversarial Contamination
• Linear Regression under Missing or Corrupted Coordinates
• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
• On the Learnability of Distribution Classes with Adaptive Adversaries
• Robust Estimation Under Heterogeneous Corruption Rates
• Adversarially robust quantum state learning and testing
• Distributionally Robust Optimization with Adversarial Data Contamination

Related

• Being Robust (in High Dimensions) Can Be Practical
• Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
• High-Dimensional Robust Mean Estimation in Nearly-Linear Time
• Privately Learning High-Dimensional Distributions
• A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube