Academic

Modern data science pipelines are often severely constrained in resources, both statistical (e.g., poor-quality input data due to outliers) as well as computational (e.g., limited runtime or memory). Simultaneously adapting to these constraints necessitates new algorithmic solutions for even basic statistical tasks. In this talk, I will present two such results in the field of high-dimensional statistics.

First, I will discuss parameter estimation for sub-Gaussian data in the presence of arbitrary outliers. For many important problems in this class, existing algorithms were either robust or polynomial-time, but not both. We resolve this issue by providing the first polynomial-time robust algorithms for covariance estimation, linear regression, and covariance-aware mean estimation. Our results are obtained via new structural results about semidefinite relaxations. Next, I will discuss the problem of robust sparse mean estimation. Moving beyond polynomial runtime as the benchmark, I will show how to bridge the gap, in fine-grained runtime, between robust and non-robust algorithms.

I will conclude with connections to other notions of resource constraints, such as privacy and communication budget.