Pravesh Kothari

Average-Case Algorithm Design Using Sum-of-Squares

I will explain how a primal-dual viewpoint on Sum-of-Squares method and its proof-complexity interpretation provides a general blueprint for parameter estimation problems arising in machine learning/average-case complexity. As a consequence, we will be able to obtain state-of-the-art algorithms for basic problems in theoretical machine learning/statistics including estimating components of gaussian mixtures, robust estimation of moments of distributions, robust independent component analysis and regression, tensor decomposition, tensor completion and dictionary learning.

Amir Ali Ahmadi

joint work with Bachir El Khadir

Learning Dynamical Systems with Side Information

We present a mathematical framework for learning a dynamical system from a limited number of trajectory observations but subject to contextual information. We show that sum of squares optimization is a particularly powerful tool for this task.