Robust Estimators in High Dimensions without the Computational Intractability

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

568 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training, Statistical Learning Theory

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

In Statistics and Probability

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Robust Aggregation for Federated Learning (2019, background): “Robust mean estimation, in particular, received much attention [18, 21, 50].”
Stronger data poisoning attacks break data sanitization defenses (2018, background): “sication algorithms that avoid the poor dimension-dependence of traditional estimators, although only under strong distributional assumptions such as log-concavity. Separately, Lai et al. (2016) and Diakonikolas et al. (2016) designed robust procedures for mean estimation, which again required stron”
Spectral Signatures in Backdoor Attacks (2018, background): “Another line of work focuses on applying the robust statistics tools developed in [8, 22, 5, 9] to robust stochastic optimization problems [2, 5, 10, 17, 27].”
Byzantine Stochastic Gradient Descent (2018, background): “Recently, efficient algorithms for high dimensional optimization which are tolerant to a small fraction of adversarial corruptions have been developed [1, 7, 11, 16, 24], building on new algorithms for high dimensional robust statistics [5, 7, 9, 18].”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “On the other hand, [DKK17] provide a practical implementation of the robust mean and covariance estimation algorithms of [DKK16], but do not consider more general learning tasks.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “…non-distributed settings, much progress has been made recently in terms of improved performance in high-dimensional problems (Bhatia et al., 2015, Diakonikolas et al., 2016, Lai et al., 2016) as well as developing list-decodable and semi-veriﬁed learning schemes when a majority of the data…”
Certified Defenses for Data Poisoning Attacks (2017, methodology): “Robust algorithms have been exhibited for mean and covariance estimation and clustering (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017), classiﬁcation (Klivans et al., 2009; Awasthi et al., 2014), regression (Nasrabadi et al., 2011; Nguyen and Tran, 2013; Chen et al., 2013;…”
Distributed Statistical Machine Learning in Adversarial Settings (2017, background): “A recent line of work [8, 15] presents polynomial algorithms to consistently estimate the mean and covariance of a distribution from N i.”
Learning Discrete Distributions from Untrusted Batches (2017, background): “These recent works include [LRV16, DKK + 16, DKK + 17] who consider the problem of robustly estimating the mean and covariance of high-dimensional Gaussians (and other distributions such as product distributions), and [SVC16] who consider a sparse ratings aggregation setting.”
Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, background): “The theoretical error bound and sample complexity 1 of the existing robust aggregation algorithms [13], [37], [16], [17], [15], [33] depend on the dimensionality of model parameters.”
Being Robust (in High Dimensions) Can Be Practical (2017, methodology): “Our estimators rely on the ﬁltering technique introduced in [DKK + 16].”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “These works led to an active line of work (e.g., see (Charikar, Steinhardt, and Valiant 2017; Diakonikolas, Kane, and Stewart 2017; 2018; Diakonikolas et al. 2018; Prasad et al. 2018; Diakonikolas, Kong, and Stewart 2018) and references therein) exploring the possibility of robust statistics over po”
Efficient Algorithms for Outlier-Robust Regression (2018, background): “It has led to important achievements such as eﬃcient algorithms for robust clustering and estimation of moments [LRV16, DKK + 16, CSV17, KS17c, KS17a] in unsupervised learning and eﬃcient learning of halfspaces [KLS09, DKS17] with respect to malicious or “nasty noise” in classiﬁcation.”
Private Hypothesis Selection (2019, background): “mation [68]–[78], proper learning [7], [8], [10], [79]–[81], and improper learning [52].”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “Various different models have been introduced, see Charikar, Steinhardt, and Valiant [17], Diakonikolas, Kamath, Kane, Li, Moitra, and Stewart [23, 24, 25], Diakonikolas, Kane, and Stewart [26], Diakonikolas, Kong, and Stewart [27], Hopkins and Li [34], Klivans, Kothari, and Meka [42], Kothari, Stei”
Private Mean Estimation of Heavy-Tailed Distributions (2020, background): “In order to assuage these concerns, we consider the problem of mean estimation under the constraint of differential privacy (DP) Dwork et al. (2006), considered by many to be the gold standard of data privacy. Informally, an algorithm is said to be differentially private if its distribution over out”
Privately Learning High-Dimensional Distributions (2018, background): “Recently, there has been significant interest in the computer science community in robustly estimating distributions (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017; Diakonikolas et al., 2017, 2018; Steinhardt et al., 2018), where the goal is to estimate some distribution from sa”