Timezone: »

 
Poster
High-dimensional Robust Mean Estimation via Gradient Descent
Yu Cheng · Ilias Diakonikolas · Rong Ge · Mahdi Soltanolkotabi

Thu Jul 16 08:00 AM -- 08:45 AM & Thu Jul 16 07:00 PM -- 07:45 PM (PDT) @
in Poster Session 43 »

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.

Keywords: Computational Learning Theory · Learning Theory · Non-convex Optimization

Author Information

Yu Cheng (University of Illinois at Chicago)
Ilias Diakonikolas (University of Wisconsin-Madison)
Rong Ge (Duke University)
Mahdi Soltanolkotabi (University of Southern California)

More from the Same Authors