Events for 07/02/2020 from all calendars

Seminar in Random Tensors

Time: 04:00AM - 05:00AM

Location: zoom

Speaker: Pravesh Kothari, CMU

Title: The Sum-of-Squares Approach to Clustering Gaussian Mixtures

Abstract: Sum-of-Squares is a systematic proof system for reasoning about real solutions to systems of multivariate polynomial inequalities over the reals. In the last few years, this proof system has been used to develop a principled method for designing efficient algorithms for average-case algorithmic problems - problems where the inputs are chosen according to some natural probability distribution. By relying on the relationship between sum-of-squares proofs and semidefinite programming, this method reduces designing an efficient algorithm for a given problem to giving a low-degree sum-of-squares certificate of the correctness of a purported solution. In this talk, I'll give an overview of this method by focusing on two recent works on designing algorithms for the problem of clustering mixtures of k Gaussians in d dimensions: 1) A d^( O(log^2 k) ) time algorithm for clustering mixtures of k Gaussians with spherical covariances that succeeds whenever the mixture is information-theoretically clusterable. This algorithm relies on using sum-of-squares certificates of subgaussian moments. 2) A $d^O(k^(O(k)))$ time algorithm for clustering mixtures of k arbitrary Gaussians that succeeds whenever the mixture is clusterable. This algorithm relies on sum-of-squares certificates of hypercontractivity of degree 2 polynomials and anti-concentration of linear projections of Gaussians. The talk should be accessible to a broad audience and should not require any prior knowledge of the problems/techniques. The talk is based on joint works with Jacob Steinhardt and Ainesh Bakshi.