Learning Polynomial Transformations via Generalized Tensor Decompositions
Learning Polynomial Transformations via Generalized Tensor Decompositions
复制标题
DOI：
10.1145/3564246.3585209
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Sitan Chen;Jungshian Li;Yuanzhi Li;Anru R. Zhang
中科院分区：
文献类型：
--
作者：
Sitan Chen;Jungshian Li;Yuanzhi Li;Anru R. Zhang
我们考虑学习高维高斯多项式变换的问题。给定f(X)形式的样本，其中x∼N(0，ir)是隐藏的，并且f：ℝr→ℝd是其中每个输出坐标都是低次多项式的函数，目标是学习f(X)上的分布。人们可以将其视为学习深度生成模型的简单模型，即在具有多项式激活的双层神经网络下的高斯推进，尽管学习问题本身在数学上是自然的。我们的第一个主要结果是一个多项式时间算法，用于在平滑的设置下学习高斯的二次变换。我们的第二个主要结果是一个多项式时间算法，当相关张量的阶数很小时，在光滑的设置下学习高斯的常次多项式变换。事实上，我们的结果扩展到任何旋转不变的输入分布，而不仅仅是高斯分布。这些是在多层神经网络下学习推进的第一个端到端保证。虽然我们的工作旨在向理解为什么生成模型在实践中表现如此之好迈出了第一步，但我们在此过程中解决的算法问题也是独立的兴趣。我们给出了张量环分解的第一个可证明的有效算法，张量分解是张量分解的一种流行的非交换推广，在实践中被用于隐式存储大张量，以及一种新的矩阵因式分解，其中因子来自低秩张量。
We consider the problem of learning high dimensional polynomial transformations of Gaussians. Given samples of the form f(x), where x∼N(0,Ir) is hidden and f: ℝr → ℝd is a function where every output coordinate is a low-degree polynomial, the goal is to learn the distribution over f(x). One can think of this as a simple model for learning deep generative models, namely pushforwards of Gaussians under two-layer neural networks with polynomial activations, though the learning problem is mathematically natural in its own right. Our first main result is a polynomial-time algorithm for learning quadratic transformations of Gaussians in a smoothed setting. Our second main result is a polynomial-time algorithm for learning constant-degree polynomial transformations of Gaussian in a smoothed setting, when the rank of the associated tensors is small. In fact our results extend to any rotation-invariant input distribution, not just Gaussian. These are the first end-to-end guarantees for learning a pushforward under a neural network with more than one layer. While our work aims to take an initial step towards understanding why generative models perform so well in practice, the algorithmic problems that we solve along the way are also of independent interest. We give the first provably efficient algorithms for tensor ring decomposition, a popular non-commutative generalization of tensor decomposition that is used in practice to implicitly store large tensors, as well as for a new variant of matrix factorization where the factors arise from low-rank tensors.