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

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2020.

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

- [Efficient reconstruction of depth three circuits with top fan-in two](https://mlsanity.com/paper/2103.07445/) (2021)
- [Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning](https://mlsanity.com/paper/2311.07284/) (2023)
- [Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits](https://mlsanity.com/paper/2105.01751/) (2021)
- [DNA-SE: Towards Deep Neural-Nets Assisted Semiparametric Estimation](https://mlsanity.com/paper/2408.02045/) (2024)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)
- [A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond](https://mlsanity.com/paper/2510.19382/) (2025)

## Abstract (arXiv)

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 + ldots + 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.