Timezone: »
We study the problem of outlier robust high-dimensional mean estimation under a finite covariance assumption, and more broadly under finite low-degree moment assumptions. We consider a standard stability condition from the recent robust statistics literature and prove that, except with exponentially small failure probability, there exists a large fraction of the inliers satisfying this condition. As a corollary, it follows that a number of recently developed algorithms for robust mean estimation, including iterative filtering and non-convex gradient descent, give optimal error estimators with (near-)subgaussian rates. Previous analyses of these algorithms gave significantly suboptimal rates. As a corollary of our approach, we obtain the first computationally efficient algorithm for outlier robust mean estimation with subgaussian rates under a finite covariance assumption.
Author Information
Ilias Diakonikolas (UW Madison)
Daniel M. Kane (UCSD)
Ankit Pensia (University of Wisconsin-Madison)
More from the Same Authors
-
2021 Spotlight: List-Decodable Mean Estimation in Nearly-PCA Time »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard · Jerry Li · Kevin Tian -
2021 Spotlight: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2021 Spotlight: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2023 Poster: Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas -
2023 Poster: A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm »
Ilias Diakonikolas · Daniel Kane · Jasper Lee · Ankit Pensia · Thanasis Pittas -
2022 Poster: List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Ankit Pensia · Thanasis Pittas -
2022 Poster: Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions »
Ilias Diakonikolas · Daniel Kane · Jasper Lee · Ankit Pensia -
2021 Poster: ReLU Regression with Massart Noise »
Ilias Diakonikolas · Jong Ho Park · Christos Tzamos -
2021 Poster: Statistical Query Lower Bounds for List-Decodable Linear Regression »
Ilias Diakonikolas · Daniel Kane · Ankit Pensia · Thanasis Pittas · Alistair Stewart -
2021 Poster: Forster Decomposition and Learning Halfspaces with Noise »
Ilias Diakonikolas · Daniel Kane · Christos Tzamos -
2021 Poster: List-Decodable Mean Estimation in Nearly-PCA Time »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard · Jerry Li · Kevin Tian -
2020 Poster: List-Decodable Mean Estimation via Iterative Multi-Filtering »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard -
2020 Poster: Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals »
Ilias Diakonikolas · Daniel Kane · Nikos Zarifis -
2020 Poster: Non-Convex SGD Learns Halfspaces with Adversarial Label Noise »
Ilias Diakonikolas · Vasilis Kontonis · Christos Tzamos · Nikos Zarifis -
2020 Poster: Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient »
Ankit Pensia · Shashank Rajput · Alliot Nagle · Harit Vishwakarma · Dimitris Papailiopoulos -
2020 Poster: The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise »
Ilias Diakonikolas · Daniel M. Kane · Pasin Manurangsi -
2020 Spotlight: Optimal Lottery Tickets via Subset Sum: Logarithmic Over-Parameterization is Sufficient »
Ankit Pensia · Shashank Rajput · Alliot Nagle · Harit Vishwakarma · Dimitris Papailiopoulos -
2019 Poster: Private Testing of Distributions via Sample Permutations »
Maryam Aliakbarpour · Ilias Diakonikolas · Daniel Kane · Ronitt Rubinfeld -
2019 Poster: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Poster: Distribution-Independent PAC Learning of Halfspaces with Massart Noise »
Ilias Diakonikolas · Themis Gouleakis · Christos Tzamos -
2019 Poster: Equipping Experts/Bandits with Long-term Memory »
Kai Zheng · Haipeng Luo · Ilias Diakonikolas · Liwei Wang -
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Oral: Distribution-Independent PAC Learning of Halfspaces with Massart Noise »
Ilias Diakonikolas · Themis Gouleakis · Christos Tzamos -
2019 Poster: Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Eric Price · Alistair Stewart -
2019 Poster: A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families »
Brian Axelrod · Ilias Diakonikolas · Alistair Stewart · Anastasios Sidiropoulos · Gregory Valiant -
2018 Poster: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2018 Spotlight: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart