Inertial accelerated stochastic mirror descent for large-scale generalized tensor CP decomposition

Zehui Liu, Qingsong Wang, Chunfeng Cui, Yong XiaComput. Optim. Appl 2025 · OpenReview

TL;DR

This paper introduces iTableSMD, a novel algorithm for Generalized Tensor CP (GCP) decomposition that handles diverse data types beyond simple squared errors. By combining inertial acceleration with stochastic mirror descent and variance reduction, iTableSMD achieves faster convergence and better performance on real-world datasets compared to existing methods.

What Problem Does This Paper Address?

Tensor CP decomposition is a powerful technique for analyzing multi-way data, but traditional methods often rely on a "squared loss" and Euclidean distance. This approach is limiting because many real-world datasets (like counts or binary data) don't fit this model well. Applying these methods to generalized loss functions is challenging, especially when the data is large and the gradients aren't "well-behaved" (i.e., not Lipschitz continuous). The authors aim to bridge this gap by developing an efficient and robust algorithm for GCP decomposition that can handle these more complex, generalized loss functions and large-scale datasets.

Methods

The core of this paper is the proposed iTableSMD algorithm. It builds upon several key ideas:

  • Generalized Tensor CP Decomposition: Instead of just squared loss, it uses flexible Bregman divergences to measure proximity, making it suitable for various data distributions (Gamma, Poisson, Bernoulli).
  • Block Randomized Stochastic Mirror Descent (SMD): The algorithm processes the tensor in blocks and uses a stochastic approach, meaning it doesn't need to look at the entire dataset at once. Mirror descent is employed to handle the non-Euclidean geometry introduced by the Bregman divergences.
  • Inertial Acceleration: Inspired by Nesterov's accelerated gradient methods, iTableSMD incorporates an "inertial" component. This helps the algorithm "build momentum" and accelerate its convergence, especially in the later stages of optimization.
  • Variance Reduction: To further improve efficiency and provide theoretical guarantees, the algorithm leverages variance-reduced stochastic gradient estimators (like SAGA and SARAH). This technique helps to reduce the noise inherent in stochastic methods.

The algorithm is designed to work within a multi-block framework, allowing it to update different parts of the tensor factorization iteratively.

Datasets

The authors evaluated their iTableSMD algorithm on a variety of datasets:

  • Synthetic Datasets: Three distinct synthetic datasets were generated with Gamma, Poisson, and Bernoulli distributions to test the algorithm's performance across different data types.
  • Real-World Datasets:
    • Enron Emails Dataset: A large collection of email messages, represented as a third-order tensor with integer counts of words.
  • Uber Pickup Data: (Mentioned in the abstract and introduction, but not explicitly detailed in experiments section).
  • Flickr Dataset: A dataset of image tags, represented as a third-order binary tensor.

Key Insights and Ideas

  • Bregman Divergence is Key: The paper highlights that using Bregman divergences, rather than just Euclidean distance, is crucial for effectively handling diverse real-world data distributions in tensor decomposition.
  • Inertia Matters for Speed: The integration of inertial acceleration significantly boosts convergence speed, allowing iTableSMD to reach lower error levels much faster than methods without this feature.
  • Stochasticity + Variance Reduction = Efficiency: Combining stochastic updates with variance reduction techniques provides a powerful approach for tackling large-scale problems, offering a good balance between computational cost and convergence guarantees.
  • Unified Framework: iTableSMD provides a unified algorithmic framework that can handle various generalized loss functions and data types within the tensor CP decomposition context, which was a significant limitation of prior work.

Key Results

  • Convergence Guarantees: The paper provides theoretical guarantees for iTableSMD, proving a sublinear convergence rate for subsequential iterates and establishing global convergence. It also shows that the algorithm requires at most $O(\varepsilon^{-2})$ iterations to reach an $\varepsilon$-stationary point.
  • Performance Improvement: Numerical experiments demonstrate that iTableSMD consistently outperforms existing state-of-the-art methods (like GCP-OPT and SmartCPD) in terms of speed and achieved Mean Squared Error (MSE) or Loss value across synthetic and real-world datasets.
  • Speedup: For example, on synthetic Gamma distribution data, iTableSMD-SAGA achieved an MSE below $10^{-6}$ in under 3 seconds, significantly faster than SmartCPD (6 seconds) and GCP-OPT (over 10 seconds). Similar speedups were observed for Poisson and Bernoulli distributions.
  • Robustness: The algorithm showed robust performance across different tensor sizes, ranks, and data distributions, highlighting its versatility.

Limitations and Future Work

  • Parameter Tuning: While the paper presents theoretical convergence, the practical performance of iTableSMD, like many optimization algorithms, can be sensitive to the choice of step sizes and inertial parameters. The paper mentions that checking the inequality for inertial parameters is time-consuming in practice, suggesting a potential area for further research in adaptive parameter selection.
  • General Semialgebraic Functions: The global convergence analysis relies on the assumption that the objective function is semialgebraic and satisfies the KL property. Extending the analysis to more general function classes could be a future direction.
  • Scalability for Extremely Large Tensors: While the algorithm is designed for large-scale problems, further investigation into its scalability for extremely massive tensors, potentially involving distributed computing, could be beneficial.

Summary updated

Abstract

The majority of classic tensor CP decomposition models are designed for squared loss, utilizing Euclidean distance as a local proximal term. However, the Euclidean distance is unsuitable for the generalized loss function applicable to diverse types of real-world data, such as integer and binary data. Consequently, algorithms developed under the squared loss are not easily adaptable to handle these generalized losses, partially due to the absence of the gradient Lipschitz continuity. This paper explores generalized tensor CP decomposition, employing the Bregman distance as the proximal term and introducing an inertial accelerated block randomized stochastic mirror descent algorithm (iTableSMD). Within a broader multi-block variance reduction and inertial acceleration framework, we demonstrate the sublinear convergence rate for the subsequential sequence produced by the iTableSMD algorithm. We further show that iTableSMD requires at most \(\mathcal {O}(\varepsilon ^{-2})\) iterations in expectation to attain an \(\varepsilon \)-stationary point and establish the global convergence of the sequence. Numerical experiments on real datasets demonstrate that our proposed algorithm is efficient and achieves better performance than the existing state-of-the-art methods.
BibTeX
@inproceedings{liu2025inertial,
  author = {Zehui Liu and Qingsong Wang and Chunfeng Cui and Yong Xia},
  title = {{Inertial accelerated stochastic mirror descent for large-scale generalized tensor CP decomposition}},
  booktitle = {Comput. Optim. Appl},
  year = {2025},
  url = {https://openreview.net/forum?id=LKU79DRLu7},
}
Figure