Algorithmic Statistics and Machine Learning

3-0-9 units · Graduate

Introduction to algorithms and computational complexity for high-dimensional statistical inference problems, with focus on provable polynomial-time guarantees. Covers modern algorithm design techniques via convex programming and Sum of Squares method; graphical models as a language to describe complex but tractable high-dimensional learning problems and associated learning algorithms; and basics of complexity for statistical problems, including statistical query and low-degree lower bounds and reductions. Mathematical maturity is recommended.