AF:Small:Learning from Dynamics

Over recent years, there has been remarkable progress in providing algorithms with provable guarantees for various fundamental machine learning problems. These problems are often of an unsupervised flavor (i.e., are given unlabeled data and look for patterns and insights without any explicit guidance), and the samples come from some unknown but fixed distribution.

Yet, there are important problems coming from signal processing, control theory, and natural language processing that do not fit into this mold because the data arrives in a sequence with a rich dependency structure. The goal of this project is to design better algorithms for such problems by building the appropriate bridges to the tools and perspectives in more classic settings.

This project will also involve training the next generation of graduate students and equipping them with the technical tools to work at the cutting edge of theoretical machine learning. The investigator will also revise his free online graduate textbook with material from recent progress related to this project.

This project explores learning problems for linear dynamical systems, graphical models, and hidden Markov models. The team will prove rigorous guarantees for methods like prefiltered least squares as well as study what happens when our observations are intermittent and the usual algebraic structure is unavailable. They will also show how learning from the Glauber dynamics makes it possible to circumvent known computational lower bounds for learning higher-order graphical models.

And, finally, the team will study how hidden Markov models can be learned using a conditional sampling oracle. As a byproduct, this project will export technical ideas from theoretical computer science into areas where there are currently wide gaps in our algorithmic understanding.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.