Stochastic Optimization for Scalable Tensor Factorization

24 concepts16 papers1 proposal

Tensors—multi-dimensional arrays—are the natural mathematical structure for representing multi-way relationships, such as user-item-time triplets in recommendation systems or subject-verb-object links in knowledge graphs. However, as the number of dimensions (the order of the tensor) and the size of those dimensions grow, standard tensor decomposition methods hit a severe bottleneck known as the curse of dimensionality.

A tensor of order $d$ and size $n$ contains $n^d$ potential entries. Attempting to compute classical decompositions—such as Canonical Polyadic (CP) or Tucker decomposition—using traditional batch algorithms requires holding the entire tensor, or large dense matricized versions of it, in memory. For billion-scale datasets, this approach quickly exhausts available hardware resources.

To break through this memory wall, a prominent research direction focuses on stochastic and mini-batch optimization. Instead of performing exact, deterministic updates over the entire multi-dimensional space, these methods sample small subsets of the tensor (entries, slices, or fibers) or process data streams incrementally. By updating factor matrices using local, randomized estimates, they reduce memory overhead from exponential to constant or linear relative to the batch size.

Streaming Entries and Stochastic Gradients

The core intuition behind stochastic tensor decomposition is that we do not need to look at every entry of a massive tensor simultaneously to learn its underlying latent factors. Just as Stochastic Gradient Descent (SGD) scales matrix factorization by sampling individual matrix entries, it can be adapted to estimate gradients for multi-way arrays.

Takanori Maehara et al. demonstrated this principle in Expected Tensor Decomposition with Stochastic Gradient Descent by reformulating the factorization of an average tensor as an optimization problem over individual data samples. Instead of constructing a dense average tensor from sparse observations—which causes massive memory overhead—their algorithm processes data samples one by one. This keeps only the current factor matrices and a single data sample in memory, enabling billion-scale analysis on standard hardware.

Batch Methods:   [ Full Tensor (n^d entries) ] ──> [ Exact Gradient ] ──> Update Factors (High Memory)
Stochastic SGD:  [ Single Entry / Slice     ] ──> [ Est. Gradient  ] ──> Update Factors (Low Memory)

This approach scales remarkably well because the cost per iteration becomes independent of the total tensor size. Tamara G. Kolda et al. formalized this advantage in Stochastic Gradients for Large-Scale Tensor Decomposition. They showed that estimating the gradient from a small subset of entries drops the computational complexity from exponential in the number of dimensions to a cost proportional to the sample size. This allows researchers to apply complex, generalized loss functions to massive datasets without compromising the interpretability or accuracy of the learned factors.

Mini-Batches and Online Expectation-Maximization

For probabilistic and Bayesian tensor models—which are highly effective at handling noise and automatically inferring the latent rank—traditional batch inference methods like Gibbs sampling or standard Expectation-Maximization (EM) are computationally prohibitive. The solution is to transition to an online learning paradigm where parameters are updated recursively using mini-batches of data.

The engine behind this scalability is the incremental tracking of sufficient statistics. Instead of remembering every data point seen so far, the algorithm maintains a compact summary of the data that is sufficient to update the model's parameters.

Piyush Rai et al. leveraged this mechanism in Scalable Probabilistic Tensor Factorization for Binary and Count Data. By processing data in mini-batches and recursively updating sufficient statistics, their online EM algorithm eliminates the need to store the entire tensor in memory, yielding massive speedups over traditional batch processing.

This mini-batch framework has proven highly versatile across various probabilistic tensor architectures:

Bypassing Tensor Construction via Implicit Gradients

In many machine learning workflows, the tensor is an intermediate mathematical object rather than an explicit input dataset. For example, calculating higher-order statistical moments (like skewness or kurtosis) or constructing high-order affinity tensors for spectral clustering requires evaluating combinations of data points that explode in size. A key insight of recent work is that we can decompose these tensors without ever actually building them in memory.

Samantha Sherman et al. bypassed this bottleneck for statistical moments in Estimating Higher-Order Moments Using Symmetric Tensor Decomposition. Instead of instantiating an $O(n^d)$ moment tensor, they applied stochastic optimization techniques directly to implicit gradient calculations. By processing small subsets of observations in each iteration, they kept the computational overhead strictly linear relative to the number of variables and observations.

Traditional: Data ──> Construct Full Affinity Tensor O(N^d) ──> Factorize (OOM Error)
Implicit:    Data ──> Sample Mini-Batch ──> Compute Sub-Tensor O(B^d) ──> Incremental Update

A parallel strategy has revolutionized high-order clustering. In Deep Tensor Spectral Clustering Network via Ensemble of Multiple Affinity Tensors, Yu Hu et al. shifted from full-tensor construction to stochastic mini-batch optimization. By only computing the necessary affinity sub-tensors for small data subsets during training, they reduced the memory complexity from polynomial relative to the total dataset size to polynomial relative to the batch size.

Similarly, Zhuwen Li et al. developed an online approach in Simultaneous Clustering and Model Selection for Tensor Affinities that processes randomly sampled slices of data incrementally, maintaining a constant memory footprint. This concept also extends to structural alignment problems: Rémi Emonet et al. demonstrated in Optimal Tensor Transport that stochastic sampling can reduce the gradient computation complexity of high-order tensor transport from exponential to quadratic relative to the number of samples.

Stochastic Projections for Tensor Recovery

The utility of stochastic optimization extends beyond decomposing known tensors to the problem of tensor recovery—reconstructing a low-rank tensor from a highly limited set of linear measurements (e.g., in image inpainting or signal compression). Traditional recovery algorithms rely on iterative hard thresholding or proximal gradients, which require expensive full-gradient evaluations over the entire high-dimensional space at every step.

To accelerate this process, researchers have integrated stochastic and block-coordinate updates into geometric thresholding algorithms. Rachel Grotheer et al. introduced this concept for Tucker-rank recovery in Stochastic Iterative Hard Thresholding for Low-Tucker-Rank Tensor Recovery. By calculating gradients based on a randomly selected subset of measurements rather than the full dataset, their algorithm takes frequent, computationally inexpensive steps. This dramatically accelerates convergence in wall-clock time compared to full-gradient methods.

The authors extended this principle to exploit low-tubal-rank structures via the algebraic t-product in Iterative singular tube hard thresholding algorithms for tensor recovery, using batched and stochastic gradient variants to keep high-dimensional data recovery computationally tractable.

When dealing with dense tensors under strict constraints (such as non-negativity), computing exact projections is equally challenging. Xiao Fu et al. addressed this in Block-Randomized Stochastic Proximal Gradient for Low-Rank Tensor Factorization by proposing a "doubly randomized" framework. Their method pairs randomized block coordinate descent with fiber-based stochastic proximal gradients. By isolating and processing small subsets of data fibers sequentially, the algorithm handles complex constraints while keeping the active memory footprint well within standard RAM limits.

Why It Works: The Intuition of Multilinear Locality

Why do these stochastic approximations succeed so well without losing structural accuracy? The answer lies in the mathematical structure of tensor factorization itself.

Tensors are multilinear. If you hold all latent factor matrices constant except for one, the relationship between that remaining factor matrix and the tensor becomes entirely linear. Stochastic and mini-batch methods exploit this property by treating global tensor optimization as a sequence of local, low-dimensional problems.

Whether an algorithm samples an individual entry, a fiber, or a slice, that small sample contains a localized reflection of the global latent factors. By continuously streaming these small samples and updating the factor matrices incrementally—either through stochastic gradients, online EM sufficient statistics, or implicit sub-tensor calculations—the errors of individual random samples average out over time. The optimization path converges to the true underlying low-rank structure, successfully trading massive, impossible batch computations for fast, memory-efficient local updates.

Key Foundational Work

Expected Tensor Decomposition with Stochastic Gradient Descent (2016) — contributed 2 concept elements to this direction.
Simultaneous Clustering and Model Selection for Tensor Affinities (2016) — contributed 2 concept elements to this direction.
Scalable Probabilistic Tensor Factorization for Binary and Count Data (2015) — contributed 2 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_mini_batch_sufficient_statistic_updates_1f8bf903,
  title = {mini-batch sufficient statistic updates},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mini-batch-sufficient-statistic-updates/rdr_1f8bf9032e724ab493583e754acedc41},
  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_mini_batch_sufficient_statistic_updates_1f8bf903_v1,
  title = {mini-batch sufficient statistic updates},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mini-batch-sufficient-statistic-updates/rdr_1f8bf9032e724ab493583e754acedc41/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