CSE 544T Special Topics in Computer Science Theory


Fall 2019, Section 1: Convex optimization hierarchies for probabilistic inference and machine learning
Instructor: Brendan Juba
Tuesday/Thursday 11:30am-12:50pm, Cupples I 115


Course Piazza board. Please ask all questions that are not of a personal nature in a public post to the Piazza board.

Description: An introduction to the "sum-of-squares" hierarchy of semidefinite program relaxations for probabilistic inference problems. We will see how these methods can be used to obtain state-of-the-art guarantees for some fundamental machine learning tasks.

Prerequisites: CSE 347 or CSE 541T; Math 309 or equivalent. CSE 417T and/or ESE 326/Math 3200 recommended.

Grades and assignments: Each week, a student will select and present one of the papers from the list below over the course of two meetings. Grades will be based on these presentations, and it is expected that each student will present one paper. It is expected that students will attend others' presentations and participate in discussion of the presentations/Q&A.

Additional background reading: The first two lectures will give an overview of the sum-of-squares framework for algorithms. Additional details can be found in the following books and survey articles.

Schedule

To be filled in as the semester progresses:

List of Papers

dictionary learning & tensor decomposition tensor PCA tensor completion general inference robust learning weaknesses via pseudocalibration, conversion to spectral algorithms