High-dimensional robust mean estimation in nearly-linear time

Conference Paper

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 Rd, an -fraction of which may be arbitrarily corrupted, our algorithms run in time Oe(Nd)/poly() 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 Ω(eNd2), for = Ω(1). Our algorithms rely on a natural family of SDPs parameterized by our current guess ν for the unknown mean µ?. We give a win-win analysis establishing the following: either a near-optimal solution to the primal SDP yields a good candidate for µ?— independent of our current guess ν — or a near-optimal solution to the dual SDP yields a new guess ν0whose distance from µ?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.

Full Text

Duke Authors

Cited Authors

  • Cheng, Y; Diakonikolas, I; Ge, R

Published Date

  • January 1, 2019

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 2755 - 2771

Digital Object Identifier (DOI)

  • 10.1137/1.9781611975482.171

Citation Source

  • Scopus