Learning sums of powers of low-degree polynomials in the non-degenerate case

04/15/2020
by   Ankit Garg, et al.
0

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 = c_1Q_1^m + … + c_s Q_s^m, where each c_i∈𝔽^×, Q_i 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 Q_i's given (black-box access to) f, if the Q_i's satisfy certain non-degeneracy conditions and n is larger than d^2. The set of degenerate Q_i's (i.e., inputs for which the algorithm does not work) form a non-trivial variety and hence if the Q_i'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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro