High-dimensional robust mean estimation via gradient descent

Conference Paper

We study the problem of high-dimensional robust mean estimation in the presence of a constant fraction of adversarial outliers. A recent line of work has provided sophisticated polynomial-time algorithms for this problem with dimension-independent error guarantees for a range of natural distribution families. In this work, we show that a natural non-convex formulation of the problem can be solved directly by gradient descent. Our approach leverages a novel structural lemma, roughly showing that any approximate stationary point of our non-convex objective gives a near-optimal solution to the underlying robust estimation task. Our work establishes an intriguing connection between algorithmic high-dimensional robust statistics and non-convex optimization, which may have broader applications to other robust estimation tasks.

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2020

Published In

  • 37th International Conference on Machine Learning, Icml 2020

Volume / Issue

  • PartF168147-3 /

Start / End Page

  • 1746 - 1756

International Standard Book Number 13 (ISBN-13)

  • 9781713821120

Citation Source

  • Scopus