The Statistical Computational Gap in Tensor Completion

21 concepts13 papers1 proposal

When we transition from matrices to higher-order tensors, data analysis problems often undergo a dramatic transformation. In matrix completion—the task of filling in missing entries of a two-dimensional grid from a sparse sample—statistical limits and computational limits are beautifully aligned. If an $n \times n$ matrix has rank $r$, it possesses roughly $O(nr)$ degrees of freedom. Remarkably, standard convex optimization algorithms can perfectly reconstruct the matrix using just a few more samples than this information-theoretic minimum.

For tensors, however, this harmony shatters. Consider a 3-order tensor of size $n \times n \times n$ with rank $r$. The number of parameters needed to describe it remains low—$O(nr)$—meaning that a tiny number of observed entries theoretically contains enough information to uniquely identify the entire tensor. Yet, if you attempt to recover the tensor using efficient, polynomial-time algorithms, you will find they require vastly more data: typically on the order of $\Omega(n^{1.5}r)$ samples.

This discrepancy is known as the statistical-computational gap. It represents a fundamental barrier where a problem is statistically solvable but computationally intractable. Understanding why this gap exists, where its boundaries lie, and how to design algorithms that reach the edge of tractability is one of the most active frontiers in high-dimensional data recovery.

The Matrix-Tensor Divergence

To understand why tensors are inherently more difficult than matrices, it helps to look at how traditional convex relaxations fail. For matrices, minimizing the nuclear norm (the sum of singular values) serves as a powerful proxy for minimizing rank. When extended to tensors, a common approach is to flatten the tensor along its different modes and minimize the Sum of Nuclear Norms (SNN).

However, as shown by Cun Mu et al. in Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery, these straightforward convex relaxations are highly inefficient. They treat the multi-way array as a collection of independent matrices, failing to capture the joint, low-rank structure inherent to tensors. As a result, standard SNN approaches demand up to $O(n^2)$ samples for a 3-tensor, completely missing the true information-theoretic limit. While the authors demonstrated that reshaping the tensor into a more balanced "square" matrix can reduce the sample requirement, a substantial gap still remains between these tractable convex methods and the non-convex ideal.

The Hardness Frontier: Why Tensors Are Intractable

Why can we not simply engineer a more sophisticated convex relaxation to close this gap entirely? The barrier is not a lack of algorithmic ingenuity, but rather a deep connection to structural hardness in complexity theory.

In Noisy Tensor Completion via the Sum-of-Squares Hierarchy, Boaz Barak et al. established a formal mapping between tensor completion and the problem of refuting random constraint satisfaction problems (CSPs), such as 3-SAT or 3-XOR. Refuting a random CSP requires proving that a randomly generated formula has no satisfying assignment. In complexity theory, this task is widely conjectured to be computationally hard when the number of constraints is small.

By treating the observed entries of a sparse tensor as clauses in a random formula, the authors demonstrated that recovering a tensor from fewer than $O(n^{1.5}r)$ samples is equivalent to refuting a random CSP below its hardness threshold. If an algorithm could efficiently complete a tensor in the sparse regime, it would simultaneously break long-standing hardness assumptions in computer science. This foundational link was reinforced by Guy Bresler et al. in Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations, who provided reductions from lattice-based problems (like Learning Parity with Noise) to establish tight computational lower bounds for noisy tensor recovery. The $\Omega(n^{1.5}r)$ boundary is therefore a fundamental computational wall for 3-tensors.

Sample Complexity Scale for a 3-Order Tensor (n x n x n)
|-------------------|--------------------------|-------------------|
O(nr)               O(n^1.5 r)                 O(n^2)              O(n^3)
Information-        Conjectured Computational  Standard Convex     Full Tensor
Theoretic Limit     Boundary (SoS, Filtering)  Relaxations (SNN)   Size
(Hard to compute)   [Tractable Frontier]       [Inefficient]

Faced with this fundamental barrier, the goal shifts: how do we design algorithms that push all the way to the $O(n^{1.5}r)$ computational boundary?

The first breakthrough to achieve this optimal polynomial-time sample complexity came from the Sum-of-Squares (SoS) hierarchy. In Exact tensor completion with sum-of-squares, Aaron Potechin et al. proved that higher-level semidefinite programming relaxations can perfectly reconstruct a tensor from $r \cdot \tilde{O}(n^{1.5})$ entries. In subsequent work published in Mathematical Programming, Boaz Barak et al. extended this to the noisy regime using the 6th level of the SoS hierarchy, demonstrating that this bound holds even for "overcomplete" tensors where the rank $r$ exceeds the dimension $n$.

Bridging Theory and Practice

While the SoS hierarchy provides an elegant theoretical proof that the $O(n^{1.5}r)$ boundary is reachable, it requires solving massive semidefinite programs that are too slow for real-world datasets. To bridge this gap, researchers have developed alternative algorithmic paradigms that achieve near-optimal sample complexity while running in nearly linear time.

Similarity-Based Collaborative Filtering

Instead of solving a global optimization problem, one can exploit local similarities. In Iterative Collaborative Filtering for Sparse Noisy Tensor Estimation, Devavrat Shah et al. introduced a method that estimates tensor entries by computing similarities between slices. As further detailed by the authors in the IEEE Transactions on Information Theory, this approach achieves the conjectured $\Omega(n^{3/2})$ sample complexity barrier while remaining robust to arbitrary bounded noise and providing strong entry-wise error guarantees.

Non-Convex Optimization and Gradient Descent

Another highly successful strategy is to optimize the low-rank factor matrices directly via non-convex optimization. While non-convex landscapes are generally plagued by local minima, tensor completion exhibits favorable geometry when the sample size is sufficiently large.

  • Two-Stage Non-Convex Optimization: Changxiao Cai et al. in Nonconvex Low-Rank Tensor Completion from Noisy Data introduced a two-stage algorithm that matches the best-known statistical accuracy limits while running in nearly linear time. Similarly, Rungang Han et al. developed a projected gradient descent framework in An Optimal Statistical and Computational Framework for Generalized Tensor Estimation that provides simultaneous statistical and computational optimality across generalized tensor estimation tasks.
  • Condition-Number Invariance: A common failure mode for gradient descent on ill-conditioned data is that convergence slows down dramatically if the tensor's singular values are highly unbalanced. To solve this, Tian Tong et al. introduced ScaledGD in Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Completion. By incorporating a clever preconditioning step into each gradient update, the authors showed that the algorithm converges at a linear rate completely independent of the tensor's condition number, maintaining near-optimal sample complexity.
  • Handling Correlation: In practical settings, the underlying components of a tensor are often highly correlated rather than orthogonal. In Tensor Completion Made Practical, Allen Liu et al. introduced Kronecker Alternating Minimization, a scalable approach that achieves exact recovery even under heavy correlation, bypassing the limitations of standard alternating minimization techniques.

Bypassing the Barrier

Can we ever escape the $O(n^{1.5}r)$ computational constraint and achieve near-linear sample complexity? The short answer is no—unless we alter the problem structure by introducing additional constraints or information.

One way to bypass the gap is by leveraging side information. In Tensor Completion with Nearly Linear Samples Given Weak Side Information, Christina Lee Yu et al. demonstrated that if an algorithm has access to even weak, noisy features indicating similarities along the tensor modes, the sample complexity requirement drops precipitously to a nearly linear regime. This side information effectively breaks the random CSP reduction, allowing polynomial-time algorithms to operate near the information-theoretic limit.

Alternatively, changing the mathematical lens can reveal new pathways. In Nonnegative Tensor Completion via Integer Optimization, Caleb Bugg et al. focused on nonnegative tensors. By defining a tensor norm based on a 0-1 polytope and utilizing integer linear optimization within a Frank-Wolfe framework, the authors provided a practical numerical approach that achieves the information-theoretic sample complexity rate, demonstrating that structural constraints like nonnegativity can alter the computational landscape of tensor recovery.

Key Foundational Work

Noisy Tensor Completion via the Sum-of-Squares Hierarchy (2016) — contributed 5 concept elements to this direction.
Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_statistical_gap_statistica_6bb2bf6e,
  title = {computational-statistical gap (statistical-computational gap)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-statistical-gap-statistical-computational-gap/rdr_6bb2bf6e05f946688abef3a7b000ca3a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_statistical_gap_statistica_6bb2bf6e_v1,
  title = {computational-statistical gap (statistical-computational gap)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-statistical-gap-statistical-computational-gap/rdr_6bb2bf6e05f946688abef3a7b000ca3a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake