Abstract:

The Sum-of-Squares (SoS) paradigm is an interplay that connects the proof systems and algorithms. It can be viewed as a translation from a proof that a solution exists into an algorithm for finding the solution itself. More specifically, the SoS paradigm develops efficient algorithms by searching for low-degree sum-of-squares proofs.

In recent years, the SoS paradigm has provided a powerful framework for both algorithm design and analysis in many fields: robust and stochastic optimization, statistics and machine learning, etc.

In this talk, we will introduce some applications of the SoS paradigm in algorithmic statistics, including tensor decomposition, clustering, robust estimation, and robust regression.