Learning Mixtures of Gaussians via Arithmetic Circuits

We give an efficient algorithm to solve the moment problem for mixtures of zero-mean Gaussians (in the non-degenerate case). Our algorithm is based on a novel scheme for  btaining a learning algorithm for depth-4 arithmetic circuits from lower bounds for the same circuit  model. The scheme reduces the learning problem to decomposing two vector spaces under the action of a set of linear operators. The spaces and the operators are derived from the input circuit and a new complexity measure for depth-4 circuits. If our scheme is made robust to noise, it will lead to major progress in learning mixtures of Gaussians.

This is joint work with Neeraj Kayal and Ankit Garg from Microsoft Research India.

References:

Neeraj Kayal, Ankit Garg, and Chandan Saha, “Learning sums of powers of low-degree polynomials in the non-degenerate case,” Proceedings of FOCS 2020, pages 889–899.

https://www.csa.iisc.ac.in/~chandan/research/learning_sums_of_powers.pdf

Neeraj Kayal and Chandan Saha, “Reconstruction of non-degenerate homogeneous depth three circuits,” Proceedings of STOC 2019, pages 413–424.

https://www.csa.iisc.ac.in/~chandan/research/Reconstruction_of_homog_depth_3.pdf