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.
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
- 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.
- 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.
- Distance Estimation: Similarity scores (distances) between coordinates are computed by comparing paths within these expanded BFS neighborhoods.
- 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.
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