Fall 2018

Computational-Statistical Tradeoffs in Robust High-Dimensional Estimation

Monday, Oct. 29, 2018 11:30 am12:10 pm PDT

Add to Calendar


Ilias Diakonikolas (University of Southern California)

What is the effect of robustness on the computational complexity of high-dimensional estimation? In this talk, I will describe a technique that establishes computational-statistical tradeoffs for a range of robust estimation problems using the lens of the Statistical Query (SQ) complexity. The prototypical applications of our technique will be for the problems of robust mean and covariance estimation. The talk will be based on joint works with Daniel Kane (UCSD) and Alistair Stewart (USC).