AMS Special Seminar Series | Ankit Pensia

Location: Clark 110

When: February 6th at 9:30 p.m.

Title: Modern Algorithmic Statistics: Reliability with Minimal Resources

Abstract: 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.

Bio: Ankit Pensia is a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley. Previously, he was a Herman Goldstine Postdoctoral fellow at IBM Research. He obtained his PhD in Computer Science at the University of Wisconsin-Madison under the supervision of Po-Ling Loh, Varun Jog, and Ilias Diakonikolas. His current research interests include algorithmic robust statistics, high-dimensional probability, decentralized detection, and differential privacy.

Zoom link: https://wse.zoom.us/j/92755277282?pwd=iULpLaFnWAcWl6tQYUbeyZaN3zwBzn.1