More Like this

1. High-Dimensional Robust Mean Estimation via Gradient Descent

   Cheng, Yu ; Diakonikolas, Ilias ; Ge, Rong ; Soltanolkotabi, Mahdi ( July 2020 , International Conference on Machine Learning 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 polynomialtime 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. 

   more » « less
2. Outlier-Robust Sparse Estimation via Non-Convex Optimization

   Cheng, Yu ; Diakonikolas, Ilias ; Ge, Rong ; Gupta, Shivam ; Kane, Daniel M. ; Soltanolkotabi, Mahdi ( January 2022 , Conference on Neural Information Processing Systems)

   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.1 The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work. 

   more » « less
3. Outlier-Robust Sparse Estimation via Non-Convex Optimization

   Cheng, Yu ; Diakonikolas, Ilias ; Ge, Rong ; Gupta, Shivam ; Kane, Daniel M. ; Soltanolkotabi, Mahdi ( January 2022 , Proceedings of the 36th Conference on Neural Information Processing Systems)

   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. 

   more » « less
4. Outlier-Robust Sparse Estimation via Non-Convex Optimization

   Cheng, Yu ; Diakonikolas, Ilias ; Ge, Rong ; Gupta, Shivam ; Kane, Daniel ; Soltanolkotabi, Mahdi ( January 2022 , Advances in neural information processing systems)

   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. 

   more » « less
5. On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation

   https://doi.org/10.1109/CVPR52729.2023.01708  

   Peng, Liangzu ; Kümmerle, Christian ; Vidal, René ( June 2023 , IEEE)

   Outlier-robust estimation involves estimating some parameters (e.g., 3D rotations) from data samples in the presence of outliers, and is typically formulated as a non-convex and non-smooth problem. For this problem, the classical method called iteratively reweighted least-squares (IRLS) and its variants have shown impressive performance. This paper makes several contributions towards understanding why these algorithms work so well. First, we incorporate majorization and graduated non-convexity (GNC) into the IRLS framework and prove that the resulting IRLS variant is a convergent method for outlier-robust estimation. Moreover, in the robust regression context with a constant fraction of outliers, we prove this IRLS variant converges to the ground truth at a global linear and local quadratic rate for a random Gaussian feature matrix with high probability. Experiments corroborate our theory and show that the proposed IRLS variant converges within 5-10 iterations for typical problem instances of outlier-robust estimation, while state-of-the-art methods need at least 30 iterations. A basic implementation of our method is provided: https: //github.com/liangzu/IRLS-CVPR2023 

   more » « less