Skip to main content

High-dimensional robust mean estimation via gradient descent

Publication ,  Conference
Cheng, Y; Diakonikolas, I; Ge, R; Soltanolkotabi, M
Published in: 37th International Conference on Machine Learning, ICML 2020
January 1, 2020

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 Scholars

Published In

37th International Conference on Machine Learning, ICML 2020

Publication Date

January 1, 2020

Volume

PartF168147-3

Start / End Page

1746 / 1756
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Cheng, Y., Diakonikolas, I., Ge, R., & Soltanolkotabi, M. (2020). High-dimensional robust mean estimation via gradient descent. In 37th International Conference on Machine Learning, ICML 2020 (Vol. PartF168147-3, pp. 1746–1756).
Cheng, Y., I. Diakonikolas, R. Ge, and M. Soltanolkotabi. “High-dimensional robust mean estimation via gradient descent.” In 37th International Conference on Machine Learning, ICML 2020, PartF168147-3:1746–56, 2020.
Cheng Y, Diakonikolas I, Ge R, Soltanolkotabi M. High-dimensional robust mean estimation via gradient descent. In: 37th International Conference on Machine Learning, ICML 2020. 2020. p. 1746–56.
Cheng, Y., et al. “High-dimensional robust mean estimation via gradient descent.” 37th International Conference on Machine Learning, ICML 2020, vol. PartF168147-3, 2020, pp. 1746–56.
Cheng Y, Diakonikolas I, Ge R, Soltanolkotabi M. High-dimensional robust mean estimation via gradient descent. 37th International Conference on Machine Learning, ICML 2020. 2020. p. 1746–1756.

Published In

37th International Conference on Machine Learning, ICML 2020

Publication Date

January 1, 2020

Volume

PartF168147-3

Start / End Page

1746 / 1756