Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements
Not on the map. Why?
Abstract (arXiv)
In this paper, we investigate the sample complexity of recovering tensors with low symmetric rank from symmetric rank-one measurements. This setting is particularly motivated by the study of higher-order interactions and the analysis of two-layer neural networks with polynomial activations (polynomial networks). Using a covering numbers argument, we analyze the performance of the symmetric rank minimization program and establish near-optimal sample complexity bounds when the underlying distribution is log-concave. Our measurement model involves random symmetric rank-one tensors, which lead to involved probability calculations. To address these challenges, we employ the Carbery-Wright inequality, a powerful tool for studying anti-concentration properties of random polynomials, and leverage orthogonal polynomials. Additionally, we provide a sample complexity lower bound based on Fano's inequality, and discuss broader implications of our results for two-layer polynomial networks.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 12 of its 30 references that are in the map. First posted on arXiv 7 Feb 2025.
Builds on
12 of 30 references.
References · 12
- 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
- 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
- 2020Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functionscited by 50
- 2017Iterative Random Forests to detect predictive and stable high-order interactionscited by 42
- 2013Square Deal: Lower Bounds and Improved Relaxations for Tensor Recoverycited by 37
- 2023On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensionscited by 21
- 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
- 2018Sparse and Low-rank Tensor Estimation via Cubic Sketchingscited by 11
- 2019Tensor Regression Using Low-rank and Sparse Tucker Decompositionscited by 10
- 2019Iterative Hard Thresholding for Low CP-rank Tensor Modelscited by 9
- 2023Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applicationscited by 8
- 2020Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomenacited by 5
Built on by
Not cited yet.