Robust Sparse Estimation Tasks in High Dimensions

Abstract

In this paper we initiate the study of whether or not sparse estimation tasks can be performed efficiently in high dimensions, in the robust setting where an $\eps$-fraction of samples are corrupted adversarially. We study the natural robust version of two classical sparse estimation problems, namely, sparse mean estimation and sparse PCA in the spiked covariance model. For both of these problems, we provide the first efficient algorithms that provide non-trivial error guarantees in the presence of noise, using only a number of samples which is similar to the number required for these problems without noise. In particular, our sample complexities are sublinear in the ambient dimension $d$. Our work also suggests evidence for new computational-vs-statistical gaps for these problems (similar to those for sparse PCA without noise) which only arise in the presence of noise.

References in corpus (8)

• Detection of an anomalous cluster in a network
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Algorithms and Hardness for Robust Subspace Recovery
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Computationally Efficient Robust Estimation of Sparse Functionals
• Learning from Untrusted Data
• Convex programming approach to robust estimation of a multivariate Gaussian model
• Statistical Limits of Convex Relaxations

Cited by in corpus (10)

• Being Robust (in High Dimensions) Can Be Practical
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Robust estimation via generalized quasi-gradients
• Computationally Efficient Robust Estimation of Sparse Functionals
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
• Estimating Principal Components under Adversarial Perturbations
• Logspace Reducibility From Secret Leakage Planted Clique
• Efficient Statistics for Sparse Graphical Models from Truncated Samples