Abstract
A recent line of work shows how to construct well-concentrated estimators (giving sharp confidence intervals) for high-dimensional quantities (mean, covariance, etc) when the underlying samples are drawn from a heavy-tailed distribution. Naively, most of these estimators require exponential time to compute -- the quest for polynomial-time alternatives has resulted in significant algorithmic innovation for high-dimensional heavy-tailed statistics. I will survey some of this recent progress, then focus on one of the key techniques: new applications of some classical tools from concentration of measure (bounded-difference inequalities and the matrix Bernstein inequality) to prove concentration bounds for the optima of convex programs whose constraints are formed by samples from heavy-tailed distributions.