Timezone: »
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.
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
-
2020 : Contributed Talk: Classification with Few Tests through Self-Selection »
Hanrui Zhang · Yu Cheng · Vincent Conitzer -
2023 : The Role of Linguistic Priors in Measuring Compositional Generalization of Vision-language Models »
Chenwei Wu · Li Li · Stefano Ermon · Patrick Haffner · Rong Ge · Zaiwei Zhang -
2023 : Don’t Memorize; Mimic The Past: Federated Class Incremental Learning Without Episodic Memory »
Sara Babakniya · Zalan Fabian · Chaoyang He · Mahdi Soltanolkotabi · Salman Avestimehr -
2023 Poster: Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regression »
Mo Zhou · Rong Ge -
2023 Poster: On the Role of Attention in Prompt-tuning »
Samet Oymak · Ankit Singh Rawat · Mahdi Soltanolkotabi · Christos Thrampoulidis -
2023 Poster: Hiding Data Helps: On the Benefits of Masking for Sparse Coding »
Muthu Chidambaram · Chenwei Wu · Yu Cheng · Rong Ge -
2023 Poster: Provably Learning Diverse Features in Multi-View Data with Midpoint Mixup »
Muthu Chidambaram · Xiang Wang · Chenwei Wu · Rong Ge -
2022 Poster: Online Algorithms with Multiple Predictions »
Keerti Anand · Rong Ge · Amit Kumar · Debmalya Panigrahi -
2022 Spotlight: Online Algorithms with Multiple Predictions »
Keerti Anand · Rong Ge · Amit Kumar · Debmalya Panigrahi -
2022 Poster: Streaming Algorithms for High-Dimensional Robust Statistics »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas -
2022 Poster: Extracting Latent State Representations with Linear Dynamics from Rich Observations »
Abraham Frandsen · Rong Ge · Holden Lee -
2022 Spotlight: Streaming Algorithms for High-Dimensional Robust Statistics »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas -
2022 Spotlight: Extracting Latent State Representations with Linear Dynamics from Rich Observations »
Abraham Frandsen · Rong Ge · Holden Lee -
2021 Poster: Guarantees for Tuning the Step Size using a Learning-to-Learn Approach »
Xiang Wang · Shuai Yuan · Chenwei Wu · Rong Ge -
2021 Spotlight: Guarantees for Tuning the Step Size using a Learning-to-Learn Approach »
Xiang Wang · Shuai Yuan · Chenwei Wu · Rong Ge -
2020 Poster: Efficiently Learning Adversarially Robust Halfspaces with Noise »
Omar Montasser · Surbhi Goel · Ilias Diakonikolas · Nati Srebro -
2020 Poster: Customizing ML Predictions for Online Algorithms »
Keerti Anand · Rong Ge · Debmalya Panigrahi -
2019 Poster: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
2019 Oral: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
2018 Poster: Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator »
Maryam Fazel · Rong Ge · Sham Kakade · Mehran Mesbahi -
2018 Oral: Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator »
Maryam Fazel · Rong Ge · Sham Kakade · Mehran Mesbahi -
2018 Poster: Stronger Generalization Bounds for Deep Nets via a Compression Approach »
Sanjeev Arora · Rong Ge · Behnam Neyshabur · Yi Zhang -
2018 Oral: Stronger Generalization Bounds for Deep Nets via a Compression Approach »
Sanjeev Arora · Rong Ge · Behnam Neyshabur · Yi Zhang -
2017 Poster: How to Escape Saddle Points Efficiently »
Chi Jin · Rong Ge · Praneeth Netrapalli · Sham Kakade · Michael Jordan -
2017 Talk: How to Escape Saddle Points Efficiently »
Chi Jin · Rong Ge · Praneeth Netrapalli · Sham Kakade · Michael Jordan -
2017 Poster: No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis »
Rong Ge · Chi Jin · Yi Zheng -
2017 Poster: Generalization and Equilibrium in Generative Adversarial Nets (GANs) »
Sanjeev Arora · Rong Ge · Yingyu Liang · Tengyu Ma · Yi Zhang -
2017 Talk: No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis »
Rong Ge · Chi Jin · Yi Zheng -
2017 Talk: Generalization and Equilibrium in Generative Adversarial Nets (GANs) »
Sanjeev Arora · Rong Ge · Yingyu Liang · Tengyu Ma · Yi Zhang