Abstract
We consider the tensor completion problem of predicting the missing entries of a tensor. The commonly used CP (CANDECOMP/PARAFAC) model has a triple product form, but an alternate family of quadratic models based on pairwise inner products offers a more data-efficient alternative. This paper provides the first theoretical guarantee that non-convex optimization can perfectly recover quadratic tensors from a limited number of observations. We prove that with only a linear number of samples relative to the dimension, the optimization landscape becomes "well-behaved"—meaning every local minimum is a global minimum—allowing simple algorithms like gradient descent to succeed where traditional models fail.
Introduction: The Challenge of Sparse Tensors
Tensors are multi-dimensional generalizations of matrices, essential for modeling complex data such as movie ratings (user × movie × time) or knowledge bases. A primary challenge in this field is tensor completion: accurately filling in missing entries when the vast majority of the data is unobserved.
For years, the CP model has been the standard, representing a tensor as a sum of triple products. However, CP models are notoriously data-hungry. Reconstructing a $d$-dimensional tensor in polynomial time typically requires $O(d^{1.5})$ samples. In many real-world applications, data is so sparse that only $O(d)$ samples are available, causing CP models to fail. This paper investigates quadratic tensor models, which use sums of pairwise inner products. While empirically successful in recommendation systems, these models previously lacked a rigorous theoretical foundation explaining their reliability in non-convex training.
Theoretical Framework and Methods
The authors analyze a non-convex least-squares objective function. To ensure the optimization landscape is tractable, they introduce several key technical components:
- Over-parameterization: By searching in a space with a rank $R$ slightly larger than the true rank $r$ (specifically $R \approx \sqrt{\text{samples}}$), "bad" local minima are eliminated.
- Regularization: Specific regularizers enforce "incoherence," preventing any single row of the factor matrices from dominating, and weight decay is applied to stabilize the factors.
- Random Perturbation: Adding a small, random positive semi-definite (PSD) matrix to the objective "smooths" the landscape, preventing the algorithm from stalling in non-optimal regions.
- Symmetric Reduction: The three factor matrices ($A, B, C$) are mathematically reduced to a symmetric problem by vertical stacking, simplifying the global optimality analysis.
A core insight is that the non-convex approach inherits the global optimality of Semidefinite Programming (SDP) without the prohibitive computational overhead, effectively bridging the gap between SDP and the efficient Burer-Monteiro factorization method.
Experimental Validation
The theory was validated across synthetic and real-world datasets, confirming that the required sample count for recovery scales linearly ($O(d)$) with dimension.
Key Results in NLP and Recommendation Systems
On the Movielens-10M dataset, the quadratic model outperformed CP decomposition by 10% in Mean Squared Error (MSE). Furthermore, in word embedding experiments using a 1.5 billion-word Wikipedia corpus, the quadratic model was 20% more accurate than the CP model across standard NLP benchmarks, including word analogy and similarity tasks. This suggests that quadratic models better capture the underlying structure of natural language than traditional triple-product models.
Discussion and Future Work
The research establishes that for quadratic tensors, the optimization landscape is devoid of spurious local minima under slight over-parameterization. However, some challenges remain:
- Convergence Rate: While local minima are proven to be global, the specific speed at which gradient descent reaches these points is not yet strictly defined.
- Rank Gap: The theory currently requires a search rank $R \approx \sqrt{m}$, whereas empirical results suggest success even with much smaller $R$.
- Representational Power: While highly efficient for sparse data, quadratic models may have less expressive power than CP models for dense datasets with complex three-way interactions.
Future work will focus on closing the theoretical rank gap and exploring the limits of quadratic representations in denser data regimes.
Summary updated