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

arXiv: https://arxiv.org/abs/2104.14562 · HTML: https://mlsanity.com/paper/2104.14562/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 59 references that are in the map.
- First posted on arXiv 29 Apr 2021.

## Builds on (most cited first, 23 of 23)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Generalized Canonical Polyadic Tensor Decomposition](https://mlsanity.com/paper/1808.07452/) (2018)
- [A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization](https://mlsanity.com/paper/1506.04209/) (2015)
- [Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms](https://mlsanity.com/paper/1909.12325/) (2019)
- [On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1806.04781/) (2018)
- [Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2010.01935/) (2020)
- [Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random Vectors](https://mlsanity.com/paper/1712.00205/) (2017)
- [Stochastic Gradients for Large-Scale Tensor Decomposition](https://mlsanity.com/paper/1906.01687/) (2019)
- [A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data](https://mlsanity.com/paper/1511.02746/) (2015)
- ["Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent](https://mlsanity.com/paper/1710.04718/) (2017)
- [Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality](https://mlsanity.com/paper/1811.05076/) (2018)
- [Fastest Rates for Stochastic Mirror Descent Methods](https://mlsanity.com/paper/1803.07374/) (2018)
- [Learning Mixtures of Smooth Product Distributions: Identifiability and Algorithm](https://mlsanity.com/paper/1904.01156/) (2019)
- [Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective](https://mlsanity.com/paper/2006.08183/) (2020)
- [Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1309.2249/) (2013)
- [Block-Randomized Stochastic Proximal Gradient for Low-Rank Tensor Factorization](https://mlsanity.com/paper/1901.05529/) (2019)
- [Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals](https://mlsanity.com/paper/2006.16912/) (2020)
- [Stochastic model-based minimization under high-order growth](https://mlsanity.com/paper/1807.00255/) (2018)
- [Kullback-Leibler Principal Component for Tensors is not NP-hard](https://mlsanity.com/paper/1711.07925/) (2017)
- [Link Prediction Under Imperfect Detection: Collaborative Filtering for Ecological Networks](https://mlsanity.com/paper/1910.03659/) (2019)

## Built on by (most cited first, 4 of 4)

- [Joint Majorization-Minimization for Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2106.15214/) (2021)
- [Personalized Coupled Tensor Decomposition for Multimodal Data Fusion: Uniqueness and Algorithms](https://mlsanity.com/paper/2412.01102/) (2024)
- [Under-Counted Tensor Completion with Neural Incorporation of Attributes](https://mlsanity.com/paper/2306.03273/) (2023)
- [Generalized Canonical Polyadic Tensor Decompositions with General Symmetry](https://mlsanity.com/paper/2601.05335/) (2026)

## Abstract (arXiv)

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.