3:30pm – Pre-talk meet and greet teatime – 219 Prospect Street, 13 floor, there will be light snacks and beverages in the kitchen area.
Information and Abstract: The goal of robust statistics is to find accurate estimates of statistical parameters despite adversarial corruptions of data (an \eps fraction of data is arbitrarily corrupted by an adversary). For example, the median is a robust estimator of the mean for a Gaussian distribution. While this topic has been studied since at least 1960 (Huber; Tukey), proposed solutions either had error that scaled polynomially with the dimension or had running times that scaled exponentially. In 2016, concurrent papers [DKKLMS; LRV] gave efficient, robust algorithms for mean and covariance estimation of high-dimensional Gaussians (and generalizations). Since then, there has been steady progress on robust estimation and learning algorithms. In this talk, we will discuss two results for classical statistics problems: (1) a polynomial-time algorithm for robustly learning a mixture of k arbitrary Gaussians (with Bakshi, Diakonikolas, Jia, Kane and Kothari, 2022), which relies on a robust partial clustering algorithm and robust tensor decomposition, both of independent interest as algorithmic tools and (2) a polynomial-time algorithm for learning an affine transformation of a unit hypercube, a basic setting of Independent Component Analysis (with Jia and Kothari, 2023). The latter is a problem that information-theoretically cannot be solved from robust estimates of moments (unlike essentially all known solvable robust estimation problems), and our algorithm provides new certificates for affine transformations, immune to adversarial noise; the main idea is a robust version of gradient descent.
