Robust estimators in high-dimensions without the computational intractability
From MaRDI portal
Abstract: We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an -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. Our algorithms achieve error that is independent of the dimension, and in many cases scales nearly-linearly with 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.
Recommendations
- Robustly learning a Gaussian: getting optimal error, efficiently
- High-dimensional robust mean estimation in nearly-linear time
- List-decodable robust mean estimation and learning mixtures of spherical Gaussians
- Efficient algorithms and lower bounds for robust linear regression
- All-in-one robust estimator of the Gaussian mean
Cites work
- 10.1162/153244304773936072
- A novel M-estimator for robust PCA
- A size-free CLT for Poisson multinomials and its applications
- A universally acceptable smoothing factor for kernel density estimates
- Adaptive estimation of a quadratic functional by model selection.
- Combinatorial methods in density estimation
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)
- Efficient density estimation via piecewise polynomial approximation
- Efficiently learning mixtures of two Gaussians
- Elements of Information Theory
- Evolutionary trees can be learned in polynomial time in the two-state general Markov model
- Geometric algorithms and combinatorial optimization
- Geometric median in nearly linear time
- scientific article; zbMATH DE number 1804119 (Why is no real title available?)
- scientific article; zbMATH DE number 3870398 (Why is no real title available?)
- scientific article; zbMATH DE number 3954047 (Why is no real title available?)
- scientific article; zbMATH DE number 3541764 (Why is no real title available?)
- scientific article; zbMATH DE number 4001209 (Why is no real title available?)
- scientific article; zbMATH DE number 837911 (Why is no real title available?)
- scientific article; zbMATH DE number 3336465 (Why is no real title available?)
- scientific article; zbMATH DE number 3390139 (Why is no real title available?)
- Learning \(k\)-modal distributions via testing
- Learning discrete distributions from untrusted batches
- Learning from satisfying assignments
- Learning from untrusted data
- Learning geometric concepts with nasty noise
- Learning Halfspaces with Malicious Noise
- Learning in the Presence of Malicious Errors
- Learning mixtures of arbitrary Gaussians
- Learning Mixtures of Product Distributions over Discrete Domains
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Learning mixtures of structured distributions over discrete domains
- List-decodable robust mean estimation and learning mixtures of spherical Gaussians
- Maximum Likelihood Estimation of Misspecified Models
- Mixture models, robustness, and sum of squares proofs
- Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes
- On estimation of the diagonal elements of a sparse precision matrix
- On the learnability of discrete distributions
- Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders
- Rates of convergence of minimum distance estimators and Kolmogorov's entropy
- Resilience: a criterion for learning in the presence of arbitrary outliers
- Robust computation of linear models by convex relaxation
- Robust estimators in high-dimensions without the computational intractability
- Robust moment estimation and improved clustering via sum of squares
- Robust principal component analysis?
- Robust Statistics
- Sample-optimal density estimation in nearly-linear time
- The densest hemisphere problem
- The Fourier transform of Poisson multinomial distributions and its algorithmic applications
- Tight bounds for learning a mixture of two Gaussians (extended abstract)
- Toward efficient agnostic learning
Cited in
(59)- Nearly optimal robust mean estimation via empirical characteristic function
- Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence
- Generalized resilience and robust statistics
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- Robust sub-Gaussian estimation of a mean vector in nearly linear time
- 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
- Confidence regions and minimax rates in outlier-robust estimation on the probability simplex
- Mean estimation with sub-Gaussian rates in polynomial time
- Learning under \(p\)-tampering poisoning attacks
- Robust classification via MOM minimization
- 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 regression via mutivariate regression depth
- Multidimensional linear functional estimation in sparse Gaussian models and robust estimation of the mean
- Mean estimation and regression under heavy-tailed distributions: A survey
- Robust multivariate mean estimation: the optimality of trimmed mean
- Robust inference and local algorithms
- Robustly learning a Gaussian: getting optimal error, efficiently
- Maximum selection and sorting with adversarial comparators
- Robust estimators in high-dimensions without the computational intractability
- Learning from untrusted data
- Resilience: a criterion for learning in the presence of arbitrary outliers
- Low rank approximation in the presence of outliers
- Graph powering and spectral robustness
- Robust High-Dimensional Statistics
- Robustness and Tractability for Non-convex M-estimators
- scientific article; zbMATH DE number 7306864 (Why is no real title available?)
- 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
- Robust supervised learning with coordinate gradient descent
- On robustness and local differential privacy
- Robust estimation of covariance matrices: adversarial contamination and beyond
- Improved covariance estimation: optimal robustness and sub-Gaussian guarantees under heavy tails
- Corruption-tolerant bandit learning
- Distributed robust estimation and inference with contaminated data
- Information theoretic limits of robust sub-Gaussian mean estimation under star-shaped constraints
- Robust Mean estimation by all means (short paper)
- Outlier-robust nonsmooth stochastic optimization
- Robust and computationally efficient gradient-based estimation
- Trimmed sample means for robust uniform mean estimation and regression
- Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction
- Distributionally robust optimization and robust statistics
- An \(\mathcal{O} (n)\) algorithm for generating uniform random vectors in \(n\)-dimensional cones
- Outlier robust and sparse estimation of linear regression coefficients
- On deviation probabilities in non-parametric regression with heavy-tailed noise
- Distributionally robust optimization
- Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions
- Computationally efficient and statistically optimal robust high-dimensional linear regression
- Stochastic dueling bandits with adversarial corruption
- Understanding simultaneous train and test robustness
- Robustly learning general mixtures of Gaussians
- Uniform mean estimation via generic chaining
- The full landscape of robust mean testing: sharp separations between oblivious and adaptive contamination
- Distributed learning with adversarial contamination: an efficient and optimal approach based on dynamic regularization
- Winsorized mean estimation with heavy tails and adversarial contamination
- A shrinkage principle for heavy-tailed data: high-dimensional robust low-rank matrix recovery
This page was built for publication: Robust estimators in high-dimensions without the computational intractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634036)
