Name
Abstract | ||
|---|---|---|
We develop algorithms for writing a polynomial as sums of powers of low degree polynomials in the non-degenerate case. This problem generalizes symmetric tensor decomposition which is widely studied, having many applications in machine learning. Our algorithm for this more general problem allows us to solve the moment problem for mixtures of zero-mean Gaussians in the nondegenerate case. Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from lower bound for the same model, provided certain non-degeneracy conditions hold. The scheme reduces the learning problem to the problem of decomposing two vector spaces under the action of a set of linear operators, where the spaces and the operators are derived from the input circuit and the complexity measure used in a typical lower bound proof. The non-degeneracy conditions are certain restrictions on how the spaces decompose. Such a scheme is present in a rudimentary form in an earlier work of Kayal and Saha. Here, we make it more general and detailed, and potentially applicable to learning other circuit models. An exponential lower bound on the representation above is known using the shifted partials measure. However, the number of linear operators in shifted partials is exponential and also the non-degeneracy condition emerging out of this measure is unlikely to be satisfied by a random such circuit when the number of variables is large with respect to the degree. We bypass this hurdle by proving a lower bound (which is nearly as strong as the previous bound) using a novel variant of the partial derivatives measure, namely affine projections of partials (APP). The non-degeneracy conditions appearing from this new measure are satisfied by a random circuit of the above kind. The APP measure could be of independent interest for proving other lower bounds. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/FOCS46700.2020.00087 | 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
Arithmetic circuits,Reconstruction,Mixtures of Gaussians | Conference | 27 |
ISSN | ISBN | Citations |
1523-8288 | 978-1-7281-9622-0 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ankit Garg | 1 | 125 | 16.19 |
| Neeraj Kayal | 2 | 263 | 19.39 |
| Chandan Saha | 3 | 227 | 16.91 |