Robust Max Entrywise Error Bounds for Tensor Estimation From Sparse Observations via Similarity-Based Collaborative Filtering

Devavrat Shah, Christina Lee YuIEEE Trans. Information Theory 2023 · OpenReview

Introduction: The Challenge of Sparse Tensor Estimation

Matrix completion—the task of filling in missing entries in a 2D grid—is a cornerstone of modern recommendation systems. However, real-world data is often higher-dimensional. An e-commerce interaction involving a user, a product, and a specific time of day is more naturally represented as a 3-order tensor.

Estimating missing entries in a tensor is significantly more complex than in a matrix. While the information-theoretic minimum number of samples scales linearly with dimension $n$, there is a conjectured computational lower bound of $\Omega(n^{3/2})$ for 3-order tensors. Most existing methods focus on minimizing Mean Squared Error (MSE), which can hide large errors in individual entries. Furthermore, many algorithms rely on the assumption that the data is exactly low-rank (as illustrated in Figure 1) or corrupted only by simple Gaussian noise.

Low-rank tensor decomposition models (CP and Tucker) represent the target structure for estimation.

This paper introduces a similarity-based collaborative filtering algorithm that achieves the $\Omega(n^{3/2})$ sample complexity, provides guarantees on the Maximum Entry-wise Error (MEE), and remains robust to arbitrary bounded noise.

Methodology: Similarity-Based Collaborative Filtering

The proposed algorithm adapts nearest-neighbor collaborative filtering to the tensor setting. Instead of relying on strict algebraic decompositions, it estimates missing entries by finding "similar" coordinates and averaging their values.

The Estimation Process

  1. Flattening: The $n \times n \times n$ tensor is unfolded into an $n \times n^2$ matrix (see Figure 2). The observed entries are then used to construct a bipartite graph.
  2. Modified Neighborhood Expansion: To identify similar coordinates, the algorithm explores the local neighborhood of each node using a modified Breadth-First Search (BFS). To avoid statistical dependencies caused by shared latent variables, the algorithm ensures no coordinate is revisited across different tree depths.
  3. Distance Estimation: Similarity scores (distances) between coordinates are computed by comparing paths within these expanded BFS neighborhoods.
  4. Nearest Neighbor Averaging: To estimate an unobserved entry $(u, v, w)$, the algorithm averages observed data from triplets $(a, b, c)$ identified as highly similar to the target.
The algorithm begins by unfolding the 3-order tensor along mode 1 to facilitate similarity calculations.

Key Insights: Connectivity and Robustness

A major contribution of this work is the intuitive link between graph theory and sample complexity. The authors show that the $\Omega(n^{3/2})$ computational threshold corresponds to the density required for the bipartite graph to become fully connected. Below this threshold, the graph shatters, making similarity computation impossible.

Furthermore, by prioritizing MEE over MSE, the authors ensure that no single prediction is wildly inaccurate. This is critical in high-stakes applications like personalized medicine. Because the algorithm uses neighborhood smoothing rather than rigid algebraic structures, it degrades gracefully under adversarial, bounded noise $\epsilon$.

Key Results

  • Optimal Sample Complexity: Recovery is successful with an observation probability of $p = \Omega(n^{-3/2+\kappa})$ for any arbitrarily small $\kappa > 0$.
  • Strong Error Convergence: Both MSE and MEE converge to zero as $n$ grows.
  • Robustness: For tensors that are only approximately low-rank, the estimation error degrades only by a polynomial factor of the noise $\epsilon$.
  • Computational Efficiency: While a naive implementation is $O(pn^6)$, the authors introduce an "anchor vertex" clustering method that reduces the cost to $O(n^{5/2+\kappa})$ without losing theoretical guarantees.

Limitations and Future Work

Despite its strengths, the algorithm's MSE convergence rate is suboptimal by a factor of $\sqrt{n}$ compared to spectral methods. Additionally, nearest-neighbor smoothing cannot achieve exact recovery in noiseless settings. Future research may explore the absolute best achievable error relative to adversarial perturbations and extend these proofs to general $d$-order asymmetric tensors.

Summary updated

Abstract

Consider the task of estimating a 3-order <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \times n \times n$ </tex-math></inline-formula> tensor from noisy observations of randomly chosen entries in the sparse regime. We introduce a similarity based collaborative filtering algorithm for estimating a tensor from sparse observations and argue that it achieves sample complexity that nearly matches the conjectured computationally efficient lower bound on the sample complexity for the setting of low-rank tensors. Our algorithm uses the matrix obtained from the flattened tensor to compute similarity, and estimates the tensor entries using a nearest neighbor estimator. We prove that the algorithm recovers a finite rank tensor with maximum entry-wise error (MEE) and mean-squared-error (MSE) decaying to 0 as long as each entry is observed independently with probability <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p = \Omega (n^{-3/2 + \kappa })$ </tex-math></inline-formula> for any arbitrarily small <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \kappa &gt; 0$ </tex-math></inline-formula> . More generally, we establish robustness of the estimator, showing that when arbitrary noise bounded by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \boldsymbol { \varepsilon }\geq 0$ </tex-math></inline-formula> is added to each observation, the estimation error with respect to MEE and MSE degrades by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\sf poly}(\boldsymbol { \varepsilon })$ </tex-math></inline-formula> . Consequently, even if the tensor may not have finite rank but can be approximated within <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \boldsymbol { \varepsilon }\geq 0$ </tex-math></inline-formula> by a finite rank tensor, then the estimation error converges to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\sf poly}(\boldsymbol { \varepsilon })$ </tex-math></inline-formula> . Our analysis sheds insight into the conjectured sample complexity lower bound, showing that it matches the connectivity threshold of the graph used by our algorithm for estimating similarity between coordinates.
BibTeX
@article{shah2023robust,
  author = {Devavrat Shah and Christina Lee Yu},
  title = {{Robust Max Entrywise Error Bounds for Tensor Estimation From Sparse Observations via Similarity-Based Collaborative Filtering}},
  journal = {IEEE Trans. Information Theory},
  year = {2023},
  url = {https://openreview.net/forum?id=4wLkg9fJwe},
}
Figure