# Learning Polynomial Transformations

arXiv: https://arxiv.org/abs/2204.04209 · HTML: https://mlsanity.com/paper/2204.04209/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 120 references that are in the map.
- First posted on arXiv 8 Apr 2022.

## Builds on (most cited first, 22 of 22)

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Variational Autoencoders and Nonlinear ICA: A Unifying Framework](https://mlsanity.com/paper/1907.04809/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [How Well Generative Adversarial Networks Learn Distributions](https://mlsanity.com/paper/1811.03179/) (2018)
- [Many Paths to Equilibrium: GANs Do Not Need to Decrease a Divergence At Every Step](https://mlsanity.com/paper/1710.08446/) (2017)
- [Wasserstein GANs Work Because They Fail (to Approximate the Wasserstein Distance)](https://mlsanity.com/paper/2103.01678/) (2021)
- [Statistical guarantees for generative models without domination](https://mlsanity.com/paper/2010.09237/) (2020)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Distribution Approximation and Statistical Estimation Guarantees of Generative Adversarial Networks](https://mlsanity.com/paper/2002.03938/) (2020)
- [Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning](https://mlsanity.com/paper/2002.05378/) (2020)
- [Understanding GANs: the LQG Setting](https://mlsanity.com/paper/1710.10793/) (2017)
- [Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms](https://mlsanity.com/paper/1504.05287/) (2015)
- [Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions](https://mlsanity.com/paper/2106.02619/) (2021)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Sample-Optimal and Efficient Learning of Tree Ising models](https://mlsanity.com/paper/2010.14864/) (2020)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [The Sparse Hausdorff Moment Problem, with Application to Topic Models](https://mlsanity.com/paper/2007.08101/) (2020)
- [Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs](https://mlsanity.com/paper/2201.07206/) (2022)
- [Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations](https://mlsanity.com/paper/1706.04097/) (2017)
- [Making Method of Moments Great Again? -- How can GANs learn distributions](https://mlsanity.com/paper/2003.04033/) (2020)

## Built on by (most cited first, 3 of 3)

- [The Mechanism of Prediction Head in Non-contrastive Self-supervised Learning](https://mlsanity.com/paper/2205.06226/) (2022)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)

## Abstract (arXiv)

We consider the problem of learning high dimensional polynomial transformations of Gaussians. Given samples of the form p(x), where x~ N(0, Idr) is hidden and p: ℝr → ℝd is a function where every output coordinate is a low-degree polynomial, the goal is to learn the distribution over p(x). This problem is natural in its own right, but is also an important special case of learning deep generative models, namely pushforwards of Gaussians under two-layer neural networks with polynomial activations. Understanding the learnability of such generative models is crucial to understanding why they perform so well in practice. 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. Along the way, we also give the first polynomial-time algorithms with provable guarantees for tensor ring decomposition, a popular generalization of tensor decomposition that is used in practice to implicitly store large tensors.