Robustly learning a Gaussian: getting optimal error, efficiently

MaRDI QIDQ4608066zbMATH OpenFDO

Authors Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1704.03866, http://dl.acm.org/citation.cfm?id=3175475

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms (68W40)

Abstract: We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an $varepsilon$-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error $O(varepsilon)$ in the total variation distance, which is optimal up to a universal constant that is independent of the dimension. In the case where just the mean is unknown, our robustness guarantee is optimal up to a factor of $sqrt2$ and the running time is polynomial in $d$ and $1/epsilon$. When both the mean and covariance are unknown, the running time is polynomial in $d$ and quasipolynomial in $1/varepsilon$. Moreover all of our algorithms require only a polynomial number of samples. Our work shows that the same sorts of error guarantees that were established over fifty years ago in the one-dimensional setting can also be achieved by efficient algorithms in high-dimensional settings.

Recommendations

• Robust estimators in high-dimensions without the computational intractability
• Efficient algorithms and lower bounds for robust linear regression
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• High-dimensional robust mean estimation in nearly-linear time
• All-in-one robust estimator of the Gaussian mean

Cited in

(23)

• Generalized resilience and robust statistics
• Robust sub-Gaussian estimation of a mean vector in nearly linear time
• All-in-one robust estimator of the Gaussian mean
• Efficient parameter estimation of truncated Boolean product distributions
• Genuinely distributed Byzantine machine learning
• Mean estimation and regression under heavy-tailed distributions: A survey
• Robust multivariate mean estimation: the optimality of trimmed mean
• Robust Partial-Learning in Linear Gaussian Systems
• Sampling correctors
• Robust estimators in high-dimensions without the computational intractability
• Resilience: a criterion for learning in the presence of arbitrary outliers
• Robust High-Dimensional Statistics
• Best arm identification for contaminated bandits
• List-decodable robust mean estimation and learning mixtures of spherical Gaussians
• Efficient algorithms and lower bounds for robust linear regression
• High-dimensional robust mean estimation in nearly-linear time
• Corruption-tolerant bandit learning
• Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction
• Outlier robust and sparse estimation of linear regression coefficients
• CRIMED: lower and upper bounds on regret for bandits with unbounded stochastic corruption
• Stochastic dueling bandits with adversarial corruption
• Buying data over time: approximately optimal strategies for dynamic data-driven decisions
• The full landscape of robust mean testing: sharp separations between oblivious and adaptive contamination

This page was built for publication: Robustly learning a Gaussian: getting optimal error, efficiently

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608066)