Title: Computationally Efficient Robust Estimation of Sparse Functionals,
Abstract: Many conventional statistical procedures are extremely sensitive to seemingly
minor deviations from modeling assumptions. This problem is exacerbated in
modern high-dimensional settings, where the problem dimension can grow with and
possibly exceed the sample size. We consider the problem of robust estimation
of sparse functionals, and provide a computationally and statistically
efficient algorithm in the high-dimensional setting. Our theory identifies a
unified set of deterministic conditions under which our algorithm guarantees
accurate recovery. By further establishing that these deterministic conditions
hold with high-probability for a wide range of statistical models, our theory
applies to many problems of considerable interest including sparse mean and
covariance estimation; sparse linear regression; and sparse generalized linear
models.