Fitting Low-Rank Tensors in Constant Time

Kohei Hayashi, Yuichi YoshidaNeurIPS 2017 · OpenReview

TL;DR

This paper introduces a sampling-based algorithm that estimates the residual error of Tucker decomposition in "constant time"—meaning the runtime depends on the desired accuracy, not the size of the input tensor. By analyzing a tiny "mini-tensor" sampled from the original, researchers can quickly navigate the computationally expensive search for the optimal Tucker rank in massive datasets.

What Problem Does This Paper Address?

Tensor decomposition is a cornerstone of multi-dimensional data analysis, used to compress data and uncover latent structures. Tucker decomposition is one of the most popular methods, acting as a higher-order generalization of Singular Value Decomposition (SVD). However, it has a major practical bottleneck: rank selection.

To use Tucker decomposition, you must first specify a "Tucker rank" (a tuple of integers representing the dimensions of the core tensor). If the rank is too low, you lose vital information; if it's too high, you waste memory and computation. Finding the "sweet spot" usually requires a grid search, but evaluating even a single rank candidate on a massive tensor is incredibly slow. As the number of dimensions (modes) increases, the search space grows exponentially, making traditional methods like Higher-Order Orthogonal Iteration (HOOI) unfeasible for large-scale rank tuning.

Methods

The authors propose a remarkably simple sampling strategy backed by sophisticated theoretical guarantees:

  1. Sampling: For an order-$K$ tensor $X$, the algorithm randomly samples a small, constant number of indices $s$ for each mode.
  2. Construction: It creates a "mini-tensor" $\tilde{X}$ of size $s \times s \times \dots \times s$ using the intersections of these sampled indices.
  3. Estimation: It computes the residual error of the Tucker decomposition on this mini-tensor using a standard solver (like HOOI).

The "magic" lies in the proof of correctness. The authors utilize graph limit theory and a weak version of Szemerédi’s regularity lemma. They treat tensors as "dikernels" (continuous functions) to prove that as long as the sample size $s$ is large enough, the normalized residual error of the mini-tensor will be very close to the error of the original large tensor with high probability. Crucially, the required $s$ depends on the desired error tolerance ($\epsilon$) and the number of modes ($K$), but not on the actual dimensions of the input tensor.

Key Insights and Ideas

  • Constant Time Complexity: The most significant insight is that we don't need to look at the whole tensor to know how well a specific rank will fit it. This shifts the complexity from $O(N^K)$ to $O(s^K)$, where $s \ll N$.
  • Rank Selection as a Pre-processing Step: The authors emphasize that this isn't meant to replace the final decomposition, but to act as a "scout" that quickly identifies which ranks are worth pursuing with full-scale computation.
  • Theoretical Bridge: The paper successfully bridges deep combinatorial mathematics (Regularity Lemmas) with practical machine learning problems (tensor fitting), providing a provable guarantee for a heuristic-looking sampling approach.

Key Results

The algorithm was evaluated on both synthetic and real-world datasets, ranging from video and image data to biological and chemical measurements.

Residual error across different Tucker ranks for various datasets
  • High Accuracy and Reliable Ranking: As seen in the figure above, despite only looking at a tiny fraction of the data, the sampling methods (sample40, sample80) closely track the true residual error curve of the full HOOI method across various datasets. This allows the algorithm to correctly identify the relative quality of different Tucker ranks.
  • Massive Speedups: The computational savings are staggering. On the visor dataset (1.8 billion elements), the standard HOOI method took over 10,000 seconds. The proposed sampling method (with $s=40$) took only 0.13 seconds—a speedup of several orders of magnitude.
Computation times (in seconds) across different methods and datasets

Limitations and Future Work

  • Sparsity Issues: The method struggled with the wine dataset, which is highly sparse. Because the algorithm uses uniform random sampling, it may miss the few non-zero "signal" elements in highly sparse tensors, leading to an underestimation of the error.
  • Underestimation at Small $s$: The experiments showed that very small sample sizes tend to underestimate the residual error. Users must balance the sample size $s$ against the desired precision.
  • Training vs. Generalization: The authors acknowledge that this method estimates residual (training) error, not generalization error. It cannot be directly used for cross-validation because it doesn't provide the factor matrices (minimizers) for the full tensor, only the minimum value of the objective function.

Summary updated

Abstract

In this paper, we develop an algorithm that approximates the residual error of Tucker decomposition, one of the most popular tensor decomposition methods, with a provable guarantee. Given an order-$K$ tensor $X\in\mathbb{R}^{N_1\times\cdots\times N_K}$, our algorithm randomly samples a constant number $s$ of indices for each mode and creates a ``mini'' tensor $\tilde{X}\in\mathbb{R}^{s\times\cdots\times s}$, whose elements are given by the intersection of the sampled indices on $X$. Then, we show that the residual error of the Tucker decomposition of $\tilde{X}$ is sufficiently close to that of $X$ with high probability. This result implies that we can figure out how much we can fit a low-rank tensor to $X$ \emph{in constant time}, regardless of the size of $X$. This is useful for guessing the favorable rank of Tucker decomposition. Finally, we demonstrate how the sampling method works quickly and accurately using multiple real datasets.
BibTeX
@inproceedings{hayashi2017fitting,
  author = {Kohei Hayashi and Yuichi Yoshida},
  title = {{Fitting Low-Rank Tensors in Constant Time}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=SyVo1YZ_-r},
}
Figure