Abstract
I will discuss recent algorithmic advances for some elementary high-dimensional estimation problems, estimation of the mean and covariance of a random vector, focusing on the setting that the random vector may be heavy tailed but sharp confidence intervals are desired. In this setting, standard estimators such as empirical mean and covariance suffer from badly-suboptimal confidence intervals, but more robust estimators can achieve information-theoretically optimal confidence interval width. However, these may be hard to compute: I will highlight a potential information-computation gap in heavy-tailed covariance estimation which, if not closed by further algorithmic innovations, seems to be a qualitatively distinct type of gap from those appearing in widely-studied planted problems (planted clique, etc.).
Based on joint work with Yeshwanth Cherapanamjeri, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni