Computationally Efficient Robust Estimation of Sparse Functionals

Complex high-dimensional datasets pose a variety of computational and statistical challenges. In attempts to address these challenges, the past decade has witnessed a significant amount of research on sparsity constraints in statistical models. Sparsity constraints have practical and theoretical benefits: often they lead to more interpretable models, that can be estimated efficiently even in the high-dimensional regime where the sample size n can be dwarfed by the model dimension d. In addition to being convenient from a methodological and theoretical standpoint, sparse models have also had enormous practical impact, for instance in computational biology, neuroscience and applied machine learning. On the other hand, much of the theoretical literature on sparse estimation has focused on providing guarantees under strong, often impractical, generative assumptions.