High-dimensional robust mean estimation in nearly-linear time

DOI10.1137/1.9781611975482.171MaRDI QIDQ5236362zbMATH OpenOpenAlexFDO

Authors Yu Cheng, Ilias Diakonikolas, Rong Ge

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Robustness and adaptive procedures (parametric inference) (62F35) Analysis of algorithms (68W40)

Abstract: We study the fundamental problem of high-dimensional mean estimation in a robust model where a constant fraction of the samples are adversarially corrupted. Recent work gave the first polynomial time algorithms for this problem with dimension-independent error guarantees for several families of structured distributions. In this work, we give the first nearly-linear time algorithms for high-dimensional robust mean estimation. Specifically, we focus on distributions with (i) known covariance and sub-gaussian tails, and (ii) unknown bounded covariance. Given $N$ samples on $mathbb{R}^d$, an $epsilon$-fraction of which may be arbitrarily corrupted, our algorithms run in time $ildeO(Nd)/mathrmpoly(epsilon)$ and approximate the true mean within the information-theoretically optimal error, up to constant factors. Previous robust algorithms with comparable error guarantees have running times $ildeOmega(N{d}^2)$, for $epsilon=Omega(1)$. Our algorithms rely on a natural family of SDPs parameterized by our current guess $u$ for the unknown mean $m{u}^{s}tar$. We give a win-win analysis establishing the following: either a near-optimal solution to the primal SDP yields a good candidate for $m{u}^{s}tar$ -- independent of our current guess $u$ -- or the dual SDP yields a new guess $u^{\prime }$ whose distance from $m{u}^{s}tar$ is smaller by a constant factor. We exploit the special structure of the corresponding SDPs to show that they are approximately solvable in nearly-linear time. Our approach is quite general, and we believe it can also be applied to obtain nearly-linear time algorithms for other high-dimensional robust learning problems.

Recommendations

• Robust sub-Gaussian estimation of a mean vector in nearly linear time
• Efficient algorithms and lower bounds for robust linear regression
• Robustly learning a Gaussian: getting optimal error, efficiently
• Robust estimators in high-dimensions without the computational intractability
• Mean estimation with sub-Gaussian rates in polynomial time

Cited in

(20)

• Nearly optimal robust mean estimation via empirical characteristic function
• High-dimensional robust approximated M-estimators for mean regression with asymmetric data
• Robust sub-Gaussian estimation of a mean vector in nearly linear time
• All-in-one robust estimator of the Gaussian mean
• Robust classification via MOM minimization
• Excess-risk consistency of group-hard thresholding estimator in robust estimation of Gaussian mean
• ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels
• Robustly learning a Gaussian: getting optimal error, efficiently
• Robust estimators in high-dimensions without the computational intractability
• Robust High-Dimensional Statistics
• Efficient algorithms and lower bounds for robust linear regression
• Mean estimation in high dimension
• Robust subgaussian estimation with VC-dimension
• Outlier-robust nonsmooth stochastic optimization
• Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction
• Statistically optimal robust mean and covariance estimation for anisotropic gaussians
• Outlier robust and sparse estimation of linear regression coefficients
• Sample efficient identity testing and independence testing of quantum states
• Adaptive robust confidence intervals
• Winsorized mean estimation with heavy tails and adversarial contamination

This page was built for publication: High-dimensional robust mean estimation in nearly-linear time

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