# Lab Lunch by Ilias Diakonikolas

A Complexity-Theoretic View on Unsupervised Learning

Valiant's Probably Approximately Correct (PAC) learning model brought a computational complexity perspective to the study of machine learning. The PAC framework deals with *supervised* learning problems, where data points are labeled by some target function and the goal is to infer a high-accuracy hypothesis that is close to the target function. A large portion of contemporary machine learning deals with *unsupervised* learning problems. In problems of this sort data points are unlabeled, so there is no "target function" to be learned; instead the goal is to infer some structure from a sample of unlabeled data points. I will focus on the problem of learning an unknown probability distribution given access to independent samples drawn from it. Analogous to the PAC model for learning Boolean functions, the broad goal here is to understand how the complexity of learning different types of distributions scales with the complexity of the distributions being learned. I will survey recent results in this area and identify questions for future work.