论文标题
在非分类情况下，低级多项式的幂总和
Learning sums of powers of low-degree polynomials in the non-degenerate case
论文作者
论文摘要
我们开发算法编写多项式作为低度多项式的力量的总和。考虑一个$ n $ - 变量 - $ d $多项式$ f $，可以写为$$ f = c_1q_1^{m} + \ ldots + c_s q_s q_s q_s^{m}，$ $ $ c_i \ in \ c_i \ in \ mathbb in \ nathbb {f}^f}^{\ times $ n $ q_ $，$ q_I $ = D $。在本文中，我们给出了$ \ text {poly}（（（ns）^t）$ - 时间学习算法，用于查找$ q_i $的给定（黑盒访问）$ f $，如果$ q_i的$满足某些非限制条件，并且$ n $ $ n $大于$ d^2 $。一组退化$ q_i $（即，该算法不起作用的输入）形成非平凡的品种，因此，如果根据任何合理的（全维）分布选择$ q_i $的s，那么它们具有很高的可能性（如果$ s $不太大）。 我们的算法基于一种方案，该方案是从同一模型的下限中获得算术电路模型的学习算法，但前提是某些非分类条件的存在。该方案将学习问题减少到在一组线性操作员的作用下分解两个向量空间的问题，其中空间和操作员是从输入电路派生的，以及在典型的下限证明中使用的复杂性度量。非分类条件是对空间分解方式的某些限制。
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} + \ldots + c_s Q_s^{m},$$ where each $c_i\in \mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m = d$. In this paper, we give a $\text{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.
