2020/04/15 by Garg, Ankit, Kayal, Neeraj, Saha, Chandan · 3 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2004.06898
We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an n-variate degree-d polynomial f which can be written as f = c1Q1m + … + cs Qsm, where each ci∈ \mathbbF×, Qi is a homogeneous polynomial of degree t, and t m = d. In this paper, we give a poly((ns)t)-time learning algorithm for finding the Qi's given (black-box access to) f, if the Qi's satisfy certain non-degeneracy conditions and n is larger than d2. The set of degenerate Qi's (i.e., inputs for which the algorithm does not work) form a non-trivial variety and hence if the Qi's are chosen according to any reasonable (full-dimensional) distribution, then they are non-degenerate with high probability (if s is not too large). Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a 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.