Robust Estimators in High Dimensions without the Computational\n Intractability

2016/04/21 by Ilias Diakonikolas, Gautam Kamath, Diakonikolas, Ilias +10 · 29 citations
Computer Science · Mathematics · #Adversarial Robustness in Machine Learning #Algorithm #Combinatorics #Computer science #Cryptography #Data Structures and Algorithms (cs.DS) #Dimension (graph theory) #Discrete mathematics #Distribution (mathematics) #Dot product #Estimator #FOS: Computer and information sciences #FOS: Mathematics #Fraction (chemistry) #Gaussian #Hypercube #Information Theory (cs.IT) #Learning with errors #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #Mathematical optimization #Mathematics #Product (mathematics) #Statistics #Statistics Theory (math.ST) #Theoretical computer science #cs.DS #cs.IT #cs.LG #math.IT #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.1604.06443

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2016/04/21 · arxiv created 2019/03/15 · arxiv updated 2019/03/18 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

We study high-dimensional distribution learning in an agnostic setting where\nan adversary is allowed to arbitrarily corrupt an \ε-fraction of the\nsamples. Such questions have a rich history spanning statistics, machine\nlearning and theoretical computer science. Even in the most basic settings, the\nonly known approaches are either computationally inefficient or lose\ndimension-dependent factors in their error guarantees. This raises the\nfollowing question:Is high-dimensional agnostic distribution learning even\npossible, algorithmically?\n In this work, we obtain the first computationally efficient algorithms with\ndimension-independent error guarantees for agnostically learning several\nfundamental classes of high-dimensional distributions: (1) a single Gaussian,\n(2) a product distribution on the hypercube, (3) mixtures of two product\ndistributions (under a natural balancedness condition), and (4) mixtures of\nspherical Gaussians. Our algorithms achieve error that is independent of the\ndimension, and in many cases scales nearly-linearly with the fraction of\nadversarially corrupted samples. Moreover, we develop a general recipe for\ndetecting and correcting corruptions in high-dimensions, that may be applicable\nto many other problems.\n

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
• Adversarially robust multiple testing in high dimensions
• A Practical and Secure Byzantine Robust Aggregator
• LARP: Learner-Agnostic Robust Data Prefiltering
• SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search
• Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
• Multi-level Certified Defense Against Poisoning Attacks in Offline Reinforcement Learning
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
• Adversarial Robustness of Nonparametric Regression
• Robust Simulation Based Inference Through Robust Optimal Transport
• Algorithms with Polynomially-Improved Approximation Factors for the 2 → q Norm, and Applications
• Learning High-dimensional Gaussians from Censored Data
• Robust Federated Personalised Mean Estimation for the Gaussian Mixture Model
• Spatial Sign based Direct Sparse Linear Discriminant Analysis for High Dimensional Data
• Winsorized mean estimation with heavy tails and adversarial contamination
• Gaussian Mean Testing under Truncation

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