Fall 2020

Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models

Friday, December 18th, 2020 9:00 am9:30 am

Add to Calendar


Daniel Kane (UCSD)

We present a new technique for learning latent variable models with many parameters. The basic idea is to use the method of moments to find a large vector space of polynomials which nearly vanish on all of the parameters of the problem and to use this along with a new structural result to find a small cover of the set of relevant parameters after which exhaustive algorithms can be applied. Using this technique we develop substantially improved algorithms for learning mixtures of spherical Gaussians, mixtures of linear regressions and non-negative linear combinations of ReLUs.