Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses

Abstract

This work considers low-rank canonical polyadic decomposition (CPD) under a class of non-Euclidean loss functions that frequently arise in statistical machine learning and signal processing. These loss functions are often used for certain types of tensor data, e.g., count and binary tensors, where the least squares loss is considered unnatural.Compared to the least squares loss, the non-Euclidean losses are generally more challenging to handle. Non-Euclidean CPD has attracted considerable interests and a number of prior works exist. However, pressing computational and theoretical challenges, such as scalability and convergence issues, still remain. This work offers a unified stochastic algorithmic framework for large-scale CPD decomposition under a variety of non-Euclidean loss functions. Our key contribution lies in a tensor fiber sampling strategy-based flexible stochastic mirror descent framework. Leveraging the sampling scheme and the multilinear algebraic structure of low-rank tensors, the proposed lightweight algorithm ensures global convergence to a stationary point under reasonable conditions. Numerical results show that our framework attains promising non-Euclidean CPD performance. The proposed framework also exhibits substantial computational savings compared to state-of-the-art methods.

arXiv commentSubmitted to Transaction on Signal Processing

References in corpus (17)

• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• On Tensors, Sparsity, and Nonnegative Factorizations
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• A Practical Randomized CP Tensor Decomposition
• Generalized Canonical Polyadic Tensor Decomposition
• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• Stochastic Gradients for Large-Scale Tensor Decomposition
• Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random Vectors
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms
• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
• Learning Mixtures of Smooth Product Distributions: Identifiability and Algorithm
• Stochastic model-based minimization under high-order growth
• Link Prediction Under Imperfect Detection: Collaborative Filtering for Ecological Networks

Cited by in corpus (2)

• Personalized Coupled Tensor Decomposition for Multimodal Data Fusion: Uniqueness and Algorithms
• Joint Majorization-Minimization for Nonnegative Matrix Factorization with the $\beta$-divergence