2016

Robust Estimators in High Dimensions without the Computational Intractability

Diakonikolas, Ilias, Kamath, Gautam, Kane, Daniel et al.

Understand

We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an $\varepsilon$-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.

Built on

The behavior of maximum likelihood estimates under nonstandard conditions
P. J. Huber · 1967
Earlier work this paper cites.
Statistical Inference under Order Restrictions
R.E. Barlow, D.J. Bartholomew, J.M. Bremner, and H.D. Brunk · 1972
Earlier work this paper cites.
Mathematics and picturing of data
J.W. Tukey · 1975
Earlier work this paper cites.
The densest hemisphere problem
D. S. Johnson and F. P. Preparata · 1978
Earlier work this paper cites.
Maximum likelihood estimation of misspecified models
H. White · 1982
Earlier work this paper cites.
Nonparametric Density Estimation: The L 1 L_{1} View
L. Devroye and L. Györfi · 1985
Earlier work this paper cites.
Learning disjunctions of conjunctions
L. Valiant · 1985
Earlier work this paper cites.
Rates of convergence of minimum distance estimators and Kolmogorov’s entropy
Y. G. Yatracos · 1985
Earlier work this paper cites.
Robust statistics. The approach based on influence functions
F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel · 1986
Earlier work this paper cites.
Density Estimation
B. W. Silverman · 1986
Earlier work this paper cites.
Geometric Algorithms and Combinatorial Optimization
M. Grötschel, L. Lovász, and A. Schrijver · 1988
Earlier work this paper cites.
Decision theoretic generalizations of the PAC model for neural net and other learning applications
D. Haussler · 1992
Earlier work this paper cites.
Multivariate Density Estimation: Theory, Practice and Visualization
D.W. Scott · 1992
Earlier work this paper cites.
Learning in the presence of malicious errors
M. J. Kearns and M. Li · 1993
Earlier work this paper cites.
On the learnability of discrete distributions
M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
Toward Efficient Agnostic Learning
M. Kearns, R. Schapire, and L. Sellie · 1994
Earlier work this paper cites.
A universally acceptable smoothing factor for kernel density estimates
L. Devroye and G. Lugosi · 1996
Earlier work this paper cites.
Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes
L. Devroye and G. Lugosi · 1997
Earlier work this paper cites.
Learning mixtures of Gaussians
S. Dasgupta · 1999
Earlier work this paper cites.
Estimating a mixture of two product distributions
Y. Freund and Y. Mansour · 1999
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
B. Laurent and P. Massart · 2000
Earlier work this paper cites.
Learning mixtures of arbitrary Gaussians
S. Arora and R. Kannan · 2001
Earlier work this paper cites.
Distributional and L q L^{q} norm inequalities for polynomials over convex bodies in R n R^{n}
A. Carbery and J. Wright · 2001
Earlier work this paper cites.
Combinatorial methods in density estimation
L. Devroye and G. Lugosi · 2001
Earlier work this paper cites.
Smooth boosting and learning with malicious noise
R. Servedio · 2001
Earlier work this paper cites.
Evolutionary trees can be learned in polynomial time in the two state general Markov model
M. Cryan, L. Goldberg, and P. Goldberg · 2002
Earlier work this paper cites.
A spectral algorithm for learning mixtures of distributions
S. Vempala and G. Wang · 2002
Earlier work this paper cites.
Smooth boosting and learning with malicious noise
R. Servedio · 2003
Earlier work this paper cites.
Learning nonsingular phylogenies and Hidden Markov Models
E. Mossel and S. Roch · 2005
Earlier work this paper cites.
Robust estimators are hard to compute
T. Bernholt · 2006
Earlier work this paper cites.

Similar

Elements of Information Theory
T. Cover and J. Thomas · 2006
Cited alongside, same era.
Isotropic PCA and Affine-Invariant Clustering
S. C. Brubaker and S. Vempala · 2008
Cited alongside, same era.
Learning mixtures of product distributions over discrete domains
J. Feldman, R. O’Donnell, and R. A. Servedio · 2008
Cited alongside, same era.
Extensions of Principle Components Analysis
S. C. Brubaker · 2009
Cited alongside, same era.
Robust statistics
P. J. Huber and E. M. Ronchetti · 2009
Cited alongside, same era.
Learning halfspaces with malicious noise
A. Klivans, P. Long, and R. Servedio · 2009
Cited alongside, same era.
Polynomial learning of distribution families
M. Belkin and K. Sinha · 2010
Cited alongside, same era.
Efficiently learning mixtures of two Gaussians
A. T. Kalai, A. Moitra, and G. Valiant · 2010
Cited alongside, same era.
Settling the polynomial learnability of mixtures of Gaussians
A. Moitra and G. Valiant · 2010
Cited alongside, same era.
Introduction to the non-asymptotic analysis of random matrices, 2010
R. Vershynin · 2010
Cited alongside, same era.
Robust principal component analysis?
E. J. Candès, X. Li, Y. Ma, and J. Wright · 2011
Cited alongside, same era.
Learning topic models - going beyond SVD
S. Arora, R. Ge, and A. Moitra · 2012
Cited alongside, same era.

Then

Sharp bounds for learning a mixture of two Gaussians
M. Hardt and E. Price · 2015
Later among the works it cites.
Robust computation of linear models by convex relaxation
Gilad Lerman, Michael B McCoy, Joel A Tropp, and Teng Zhang · 2015
Later among the works it cites.
High-dimensional robust precision matrix estimation: Cellwise corruption under ε \varepsilon -contamination
Original
P. L. Loh and X. L. Tan · 2015
Later among the works it cites.
Geometric median in nearly linear time
M. B. Cohen, Y. T. Lee, G. L. Miller, J. W. Pachocki, and A. Sidford · 2016
Closest in time.
A size-free CLT for Poisson multinomials and its applications
C. Daskalakis, A. De, G. Kamath, and C. Tzamos · 2016
Closest in time.
Robust estimators in high dimensions without the computational intractability
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2016
Closest in time.
The fourier transform of Poisson multinomial distributions and its algorithmic applications
I. Diakonikolas, D. M. Kane, and A. Stewart · 2016
Closest in time.
Optimal learning via the Fourier transform for sums of independent integer random variables
I. Diakonikolas, D. M. Kane, and A. Stewart · 2016
Closest in time.
Robust learning of fixed-structure Bayesian networks
Original
I. Diakonikolas, D. M. Kane, and A. Stewart · 2016
Closest in time.
Agnostic estimation of mean and covariance
K. A. Lai, A. B. Rao, and S. Vempala · 2016
Closest in time.
The power of localization for efficiently learning linear separators with noise
P. Awasthi, M. F. Balcan, and P. M. Long · 2017
Closest in time.
Sample-optimal density estimation in nearly-linear time
J. Acharya, I. Diakonikolas, J. Li, and L. Schmidt · 2017
Closest in time.
Computationally efficient robust sparse estimation in high dimensions
S. Balakrishnan, S. S. Du, J. Li, and A. Singh · 2017
Closest in time.
Learning from untrusted data
M. Charikar, J. Steinhardt, and G. Valiant · 2017
Closest in time.
Computationally efficient robust estimation of sparse functionals
Original
S. S. Du, S. Balakrishnan, and A. Singh · 2017
Closest in time.
Being robust (in high dimensions) can be practical
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2017
Closest in time.
Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures
I. Diakonikolas, D. M. Kane, and A. Stewart · 2017
Closest in time.
Robust sparse estimation tasks in high dimensions
Original
J. Li · 2017
Closest in time.
Robust proper learning for mixtures of Gaussians via systems of polynomial inequalities
J. Li and L. Schmidt · 2017
Closest in time.
A data prism: Semi-verified learning in the small-alpha regime
Original
M. Meister and G. Valiant · 2017
Closest in time.
High-dimensional statistics, 2017
Phillippe Rigollet and Jan-Christian Hütter · 2017
Closest in time.
Sever: A robust meta-algorithm for stochastic optimization
Original
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, J. Steinhardt, and A. Stewart · 2018
Closest in time.
Learning geometric concepts with nasty noise
I. Diakonikolas, D. M. Kane, and A. Stewart · 2018
Closest in time.
List-decodable robust mean estimation and learning mixtures of spherical Gaussians
I. Diakonikolas, D. M. Kane, and A. Stewart · 2018
Closest in time.
Mixture models, robustness, and sum of squares proofs
S. B. Hopkins and J. Li · 2018
Closest in time.
Efficient algorithms for outlier-robust regression
Original
A. Klivans, P. K. Kothari, and R. Meka · 2018
Closest in time.
Robust moment estimation and improved clustering via sum of squares
P. K. Kothari, J. Steinhardt, and D. Steurer · 2018
Closest in time.
Robust estimation via robust gradient estimation
Original
A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar · 2018
Closest in time.
Learning discrete distributions from untrusted batches
M. Qiao and G. Valiant · 2018
Closest in time.
Resilience: A criterion for learning in the presence of arbitrary outliers
J. Steinhardt, M. Charikar, and G. Valiant · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…