SGD_Tucker: A Novel Stochastic Optimization Strategy for Parallel Sparse Tucker Decomposition

Hao Li, Zixuan Li, Kenli Li, Jan S. Rellermeyer, Lydia Chen, Keqin Li

Research output: Contribution to journalArticleScientificpeer-review

6 Downloads (Pure)

Abstract

Sparse Tucker Decomposition (STD) algorithms learn a core tensor and a group of factor matrices to obtain an optimal low-rank representation feature for the High-Order, High-Dimension, and Sparse Tensor (HOHDST). However, existing STD algorithms face the problem of intermediate variables explosion which results from the fact that the formation of those variables, i.e., matrices Khatri-Rao product, Kronecker product, and matrix-matrix multiplication, follows the whole elements in sparse tensor. The above problems prevent deep fusion of efficient computation and big data platforms. To overcome the bottleneck, a novel stochastic optimization strategy (SGD__Tucker) is proposed for STD which can automatically divide the high-dimension intermediate variables into small batches of intermediate matrices. Specifically, SGD__Tucker only follows the randomly selected small samples rather than the whole elements, while maintaining the overall accuracy and convergence rate. In practice, SGD__Tucker features the two distinct advancements over the state of the art. First, SGD__Tucker can prune the communication overhead for the core tensor in distributed settings. Second, the low data-dependence of SGD__Tucker enables fine-grained parallelization, which makes SGD__Tucker obtaining lower computational overheads with the same accuracy. Experimental results show that SGD__Tucker runs at least 2XX faster than the state of the art.

Original languageEnglish
Article number9309187
Pages (from-to)1828-1841
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Volume32
Issue number7
DOIs
Publication statusPublished - 2021

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • High-order, high-dimension and sparse tensor
  • low-rank representation learning
  • machine learning algorithm
  • parallel strategy
  • sparse tucker decomposition
  • stochastic optimization

Fingerprint

Dive into the research topics of 'SGD_Tucker: A Novel Stochastic Optimization Strategy for Parallel Sparse Tucker Decomposition'. Together they form a unique fingerprint.

Cite this