Recovery Guarantees for Quadratic Tensors with Sparse Observations

Hongyang R. Zhang, Vatsal Sharan, Moses Charikar, Yingyu Liang

TL;DR

Standard tensor completion (the CP model) is notoriously data-hungry, often requiring $O(d^{1.5})$ samples for efficient recovery. This paper proves that an alternative class of quadratic tensor models can be perfectly recovered with only linear sample complexity ($O(d)$) using simple non-convex optimization, because their optimization landscape contains no "bad" local minima when over-parameterized.

What Problem Does This Paper Address?

Tensors (multi-dimensional arrays) are the natural way to represent complex data like user-item-tag interactions or word tri-occurrences. However, these tensors are usually mostly empty. The goal of tensor completion is to fill in these missing entries.

The "gold standard" model for this is the CP decomposition, which represents a tensor as a sum of triple products. The catch? While information theory says we should only need a number of samples linear in the dimension ($d$) to recover a low-rank tensor, current polynomial-time algorithms for CP models require significantly more data—roughly $d^{1.5}$ samples. In sparse real-world settings, we simply don't have that much data.

This paper looks at quadratic models (or pairwise interaction models). Instead of a triple product, these models define each tensor entry as a sum of pairwise inner products between embeddings. While these models are popular in recommendation systems, we didn't previously know if non-convex solvers (like Gradient Descent) were guaranteed to find the right answer, or how much data they actually needed.

Methods

The authors analyze a non-convex least-squares objective for learning quadratic tensors. Their approach relies on three key technical pillars:

  1. Over-parameterization: They show that by searching in a space with rank $R \approx \sqrt{m}$ (where $m$ is the number of samples), the optimization landscape simplifies.
  2. Random Perturbation: They add a small random positive semi-definite (PSD) matrix to the objective function. This "smooths" the landscape, ensuring that the solver doesn't get stuck in unlikely, non-optimal corners of the search space.
  3. Incoherence Regularization: They include a penalty term to prevent any single row of the embedding matrices from becoming too large. This ensures the model generalizes well from the observed entries to the hidden ones.

The core theoretical contribution is a proof that under these conditions, all local minima are global minima. If your algorithm reaches a local minimum, you have successfully recovered the original tensor.

Datasets

The authors validated their theory and the model's performance using:

  • Synthetic Data: Randomly generated quadratic tensors to test recovery thresholds.
  • MovieLens-10M: A classic recommendation dataset containing 10 million ratings (user-movie-time).
  • Word Tri-occurrence Tensor: A tensor built from the 2,000 most frequent English words in a 1.5-billion-word Wikipedia corpus.
  • Riberia Hyperspectral Image: A spatial-spatial-wavelength tensor ($1017 \times 1340 \times 33$) used to test image completion.

Key Insights and Ideas

  • The Power of Pairwise: By shifting from triple products (CP) to pairwise interactions (Quadratic), the model becomes much more "data-efficient." It captures the essential correlations with far fewer observations.
  • Landscape Geometry: The most surprising finding is that the non-convex landscape of quadratic tensor completion is "benign." Unlike many non-convex problems that are riddled with traps, this one allows simple local search algorithms (like Gradient Descent or Alternating Least Squares) to succeed.
  • Linear is Enough: The paper bridges the gap between what is theoretically possible and what is computationally feasible, showing that $O(d)$ samples are sufficient for both.

Key Results

  • Sample Complexity: Experiments confirmed that both Alternating Least Squares (ALS) and Semidefinite Programming (SDP) recover quadratic tensors with only $2dr$ to $3dr$ samples—a strictly linear relationship with dimension.
  • Movie Recommendations: On the MovieLens-10M dataset, the quadratic model outperformed the standard CP model by 10% and even beat a standard matrix factorization baseline by 4%.
  • Natural Language Processing: Word embeddings learned via the quadratic model were 20% more accurate on syntactic and semantic analogy tasks compared to those from the CP model.
  • Image Recovery: In extreme sparsity (observing only 0.1% of pixels), the quadratic model's error was less than half that of the CP model.

Limitations and Future Work

  • Representational Limits: Quadratic models are a subset of CP models. Specifically, a quadratic model can be represented as a CP model with rank at most $3d$. This means for very complex, high-rank tensors where data is abundant (e.g., observing 10% of an image), the CP model will eventually win because it has higher "representational power."
  • Over-parameterization Degree: The current theory requires the search rank $R$ to scale with $\sqrt{m}$. The authors suggest it might be possible to reduce this to a much smaller rank related to the true rank $r$, but this remains an open mathematical challenge linked to the concept of "matrix rigidity."
  • Convergence Speed: While the paper proves local minima are global, it doesn't provide a formal bound on how many iterations it takes for Gradient Descent to get there.

Summary updated

Abstract

We consider the tensor completion problem of predicting the missing entries of a tensor. The commonly used CP model has a triple product form, but an alternate family of quadratic models, which are the sum of pairwise products instead of a triple product, have emerged from applications such as recommendation systems. Non-convex methods are the method of choice for learning quadratic models, and this work examines their sample complexity and error guarantee. Our main result is that with the number of samples being only linear in the dimension, all local minima of the mean squared error objective are global minima and recover the original tensor. We substantiate our theoretical results with experiments on synthetic and real-world data, showing that quadratic models have better performance than CP models where there are a limited amount of observations available.
BibTeX
@inproceedings{zhang2019recovery,
  author = {Hongyang R. Zhang and Vatsal Sharan and Moses Charikar and Yingyu Liang},
  title = {{Recovery Guarantees for Quadratic Tensors with Sparse Observations}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=gmtj2oAJvIG},
}

Loading related content...

Figure