Timezone: »
We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks. The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work.
Author Information
Yu Cheng (Brown University)
Ilias Diakonikolas (University of Wisconsin-Madison)
Rong Ge (Duke University)
Shivam Gupta (University of Texas, Austin)
Daniel Kane (UCSD)
Mahdi Soltanolkotabi (University of Southern California)
More from the Same Authors
-
2022 Poster: SQ Lower Bounds for Learning Single Neurons with Massart Noise »
Ilias Diakonikolas · Daniel Kane · Lisheng Ren · Yuxin Sun -
2022 Poster: Finite-Sample Maximum Likelihood Estimation of Location »
Shivam Gupta · Jasper Lee · Eric Price · Paul Valiant -
2022 Poster: Nearly-Tight Bounds for Testing Histogram Distributions »
Clément L Canonne · Ilias Diakonikolas · Daniel Kane · Sihan Liu -
2022 Poster: HUMUS-Net: Hybrid Unrolled Multi-scale Network Architecture for Accelerated MRI Reconstruction »
Zalan Fabian · Berk Tinaz · Mahdi Soltanolkotabi -
2022 Poster: List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Ankit Pensia · Thanasis Pittas -
2022 Poster: Cryptographic Hardness of Learning Halfspaces with Massart Noise »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi · Lisheng Ren -
2022 Poster: Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions »
Ilias Diakonikolas · Daniel Kane · Jasper Lee · Ankit Pensia -
2021 Poster: Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction »
Dominik Stöger · Mahdi Soltanolkotabi -
2021 Poster: Understanding Deflation Process in Over-parametrized Tensor Decomposition »
Rong Ge · Yunwei Ren · Xiang Wang · Mo Zhou -
2021 Poster: A Regression Approach to Learning-Augmented Online Algorithms »
Keerti Anand · Rong Ge · Amit Kumar · Debmalya Panigrahi -
2020 Poster: List-Decodable Mean Estimation via Iterative Multi-Filtering »
Ilias Diakonikolas · Daniel Kane · Daniel Kongsgaard -
2020 Poster: Beyond Lazy Training for Over-parameterized Tensor Decomposition »
Xiang Wang · Chenwei Wu · Jason Lee · Tengyu Ma · Rong Ge -
2020 Poster: Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals »
Ilias Diakonikolas · Daniel Kane · Nikos Zarifis -
2020 Poster: The Power of Comparisons for Actively Learning Linear Classifiers »
Max Hopkins · Daniel Kane · Shachar Lovett -
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: Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets »
Rohith Kuditipudi · Xiang Wang · Holden Lee · Yi Zhang · Zhiyuan Li · Wei Hu · Rong Ge · Sanjeev Arora -
2019 Poster: The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares »
Rong Ge · Sham Kakade · Rahul Kidambi · Praneeth Netrapalli -
2019 Spotlight: Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin »
Ilias Diakonikolas · Daniel Kane · Pasin Manurangsi -
2019 Poster: Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Eric Price · Alistair Stewart -
2018 Poster: On the Local Minima of the Empirical Risk »
Chi Jin · Lydia T. Liu · Rong Ge · Michael Jordan -
2018 Poster: Robust Learning of Fixed-Structure Bayesian Networks »
Yu Cheng · Ilias Diakonikolas · Daniel Kane · Alistair Stewart -
2018 Spotlight: On the Local Minima of the Empirical Risk »
Chi Jin · Lydia T. Liu · Rong Ge · Michael Jordan -
2018 Poster: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2018 Poster: Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo »
Holden Lee · Andrej Risteski · Rong Ge -
2018 Poster: Testing for Families of Distributions via the Fourier Transform »
Alistair Stewart · Ilias Diakonikolas · Clément L Canonne -
2018 Spotlight: Sharp Bounds for Generalized Uniformity Testing »
Ilias Diakonikolas · Daniel M. Kane · Alistair Stewart -
2017 Poster: On the Optimization Landscape of Tensor Decompositions »
Rong Ge · Tengyu Ma -
2017 Oral: On the Optimization Landscape of Tensor Decompositions »
Rong Ge · Tengyu Ma -
2014 Poster: Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms »
Siu On Chan · Ilias Diakonikolas · Rocco A Servedio · Xiaorui Sun