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 ; 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
4. 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
5. High-Dimensional Robust Mean Estimation in Nearly-Linear Time

   Cheng, Yu ; Diakonikolas, Ilias ; Ge, Rong ( April 2019 , Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the fundamental problem of high-dimensional mean estimation in a robust model where a constant fraction of the samples are adversarially corrupted. Recent work gave the first polynomial time algorithms for this problem with dimension-independent error guarantees for several families of structured distributions. In this work, we give the first nearly-linear time algorithms for high-dimensional robust mean estimation. Specifically, we focus on distributions with (i) known covariance and sub-gaussian tails, and (ii) unknown bounded covariance. Given N samples on R^d, an \eps-fraction of which may be arbitrarily corrupted, our algorithms run in time eO(Nd)/poly(\eps) and approximate the true mean within the information-theoretically optimal error, up to constant factors. Previous robust algorithms with comparable error guarantees have running times \Omega(Nd^2), for \eps= O(1) Our algorithms rely on a natural family of SDPs parameterized by our current guess ν for the unknown mean μ. We give a win-win analysis establishing the following: either a near-optimal solution to the primal SDP yields a good candidate for μ — independent of our current guess ν — or a near-optimal solution to the dual SDP yields a new guess ν0 whose distance from μ is smaller by a constant factor. We exploit the special structure of the corresponding SDPs to show that they are approximately solvable in nearly-linear time. Our approach is quite general, and we believe it can also be applied to obtain nearly-linear time algorithms for other high-dimensional robust learning problems. 

   more » « less