Wednesday / Theory Seminar

December 7th / 2:00 PM

Hybrid / Mudd 3514

Title: Robust Sparse Mean Estimation

Speaker: Sushrut Karmalkar

Zoom: https://northwestern.zoom.us/j/95936504416?pwd=WkJpenp4SUFJWXZSSUxWNEN2N1ZRUT09

Live Stream: https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=4647c121-da04-4306-84c3-af62003b8dc9

Abstract: In this talk, we discuss the challenging problem of accurately estimating the mean of a distribution when the data contains arbitrary outliers. We would like to solve this problem under the assumption that the mean has a small number of nonzero entries (i.e. that it is sparse). The key challenge is to demonstrate an *efficient* algorithm with a sample complexity for this task that is much better than the one required when we do not make the sparsity assumption. In particular, we ask that the sample complexity scale only logarithmically in the dimension. We will discuss how to tackle this problem in increasingly general contexts, starting with the simplest case of a Gaussian with Identity covariance, then progressing to the case where the covariance is unknown but bounded and finally to the case where a majority of the samples are outliers. We will explain the algorithms developed to address these problems, and discuss their performance in the context of the existing literature. One highlight is that the algorithm for the final problem is particularly simple for the challenging setting it attempts to address.

Biography: Sushrut is a 2021 CRA/NSF-Computing Innovation Fellow working with Prof. Ilias Diakonikolas at UW-Madison. He received his PhD from UT Austin, where he was advised by Prof. Adam Klivans. His interests include the theory of machine learning, statistics and computational learning theory. Recently he has been working on expanding the existing toolkit for algorithmic robust statistics.

Website: https://sushrutk.github.io/