Back to Upcoming EventsThis Event has Passed

S&DS Seminar: Santosh Vempala (Georgia Tech), “Robust Statistics in High Dimension”

Monday, April 8, 2024    
4:00PM to 5:00PM
Yale Institute for Foundations of Data Science
Kline Tower 13th Floor, Room 1327
New Haven, CT 06511

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.

Click for more information


Submit an Event

Interested in creating your own event, or have an event to share? Please fill the form if you’d like to send us an event you’d like to have added to the calendar.

Submit an Event

Share your event ideas with us using the form below.

"*" indicates required fields

MM slash DD slash YYYY
Start Time*
:
End Time*
: