Learning arithmetic circuits in the average case via lower bounds

Computer Science/Discrete Mathematics Seminar I
Topic:Learning arithmetic circuits in the average case via lower bounds
Speaker:Ankit Garg
Affiliation:Microsoft Research
Date:Monday, October 21
Time/Room:11:00am - 12:00pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/1021-AnkitGarg

The problem of learning arithmetic circuits is the following: given a polynomial as a black box that is promised to have a small arithmetic circuit computing it, can we find this arithmetic circuit? This problem is hard in the worst case and so previous works have focused on regimes where the NP-hardness doesn’t kick in (e.g. constant top fan-in etc.). We focus on the average case where one assumes certain non-degeneracy assumptions on the circuit (formally these amount to assuming the circuit parameters lie outside a certain variety and hence if they are chosen randomly according to any reasonable distribution, the non-degeneracy condition is satisfied whp). Kayal and Saha gave a meta framework for designing these algorithms for circuit classes where we have lower bounds. They carried this out for depth 3 circuits (sums of products of linear forms) and we (in joint work with Kayal and Saha) carry it out for depth 4 powering circuits (sums of powers of low degree polynomials). I will talk about the meta framework and then about our specific results. I will also talk about a potential application to learning mixtures of general Gaussians.