Robust Estimators in High-Dimensions Without the Computational Intractability

DOI10.1137/17M1126680zbMath1421.68149arXiv1604.06443OpenAlexW2942689850WikidataQ127954343 ScholiaQ127954343MaRDI QIDQ4634036

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

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.06443

zbMATH Keywords

Gaussian distributionmixture modelshigh-dimensionsrobust learningproduct distributions

Mathematics Subject Classification ID

Density estimation (62G07) Nonparametric robustness (62G35) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (27)

Robust sub-Gaussian estimation of a mean vector in nearly linear time ⋮ A shrinkage principle for heavy-tailed data: high-dimensional robust low-rank matrix recovery ⋮ Stronger data poisoning attacks break data sanitization defenses ⋮ All-in-one robust estimator of the Gaussian mean ⋮ Efficient parameter estimation of truncated Boolean product distributions ⋮ Robust multivariate mean estimation: the optimality of trimmed mean ⋮ Confidence regions and minimax rates in outlier-robust estimation on the probability simplex ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ Robust supervised learning with coordinate gradient descent ⋮ On robustness and local differential privacy ⋮ Learning under \(p\)-tampering poisoning attacks ⋮ Robust classification via MOM minimization ⋮ Unnamed Item ⋮ ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels ⋮ Robust high dimensional expectation maximization algorithm via trimmed hard thresholding ⋮ Robust Estimators in High-Dimensions Without the Computational Intractability ⋮ Corruption-tolerant bandit learning ⋮ Nearly optimal robust mean estimation via empirical characteristic function ⋮ Robust regression via mutivariate regression depth ⋮ Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence ⋮ Unnamed Item ⋮ Multidimensional linear functional estimation in sparse Gaussian models and robust estimation of the mean ⋮ Mean estimation and regression under heavy-tailed distributions: A survey ⋮ Unnamed Item ⋮ Generalized resilience and robust statistics ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Graph Powering and Spectral Robustness

Uses Software

• Sever

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On estimation of the diagonal elements of a sparse precision matrix
• Rates of convergence of minimum distance estimators and Kolmogorov's entropy
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Geometric algorithms and combinatorial optimization
• The densest hemisphere problem
• Toward efficient agnostic learning
• A universally acceptable smoothing factor for kernel density estimates
• Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes
• Adaptive estimation of a quadratic functional by model selection.
• Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders
• Learning Poisson binomial distributions
• Robust computation of linear models by convex relaxation
• Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model
• On the learnability of discrete distributions
• Efficiently learning mixtures of two Gaussians
• A Novel M-Estimator for Robust PCA
• Tight Bounds for Learning a Mixture of Two Gaussians
• Learning mixtures of spherical gaussians
• Robust principal component analysis?
• Learning in the Presence of Malicious Errors
• The Power of Localization for Efficiently Learning Linear Separators with Noise
• Learning Mixtures of Product Distributions over Discrete Domains
• Learning Halfspaces with Malicious Noise
• Sample-Optimal Density Estimation in Nearly-Linear Time
• Robust Estimators in High-Dimensions Without the Computational Intractability
• 10.1162/153244304773936072
• Learning from untrusted data
• Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
• Learning mixtures of arbitrary gaussians
• Mixture models, robustness, and sum of squares proofs
• Robust moment estimation and improved clustering via sum of squares
• List-decodable robust mean estimation and learning mixtures of spherical gaussians
• Learning geometric concepts with nasty noise
• Efficient density estimation via piecewise polynomial approximation
• Geometric median in nearly linear time
• The fourier transform of poisson multinomial distributions and its algorithmic applications
• A size-free CLT for poisson multinomials and its applications
• Learning from satisfying assignments
• Elements of Information Theory
• Learning mixtures of structured distributions over discrete domains
• Learning nonsingular phylogenies and hidden Markov models
• Robust Statistics
• Maximum Likelihood Estimation of Misspecified Models
• Combinatorial methods in density estimation
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)

This page was built for publication: Robust Estimators in High-Dimensions Without the Computational Intractability