  Online Tensor Factorization (OTF) is a fundamental tool in learning
low-dimensional interpretable features from streaming multi-modal data. While
various algorithmic and theoretical aspects of OTF have been investigated
recently, a general convergence guarantee to stationary points of the objective
function without any incoherence or sparsity assumptions is still lacking even
for the i.i.d. case. In this work, we introduce a novel algorithm that learns a
CANDECOMP/PARAFAC (CP) basis from a given stream of tensor-valued data under
general constraints, including nonnegativity constraints that induce
interpretability of the learned CP basis. We prove that our algorithm converges
almost surely to the set of stationary points of the objective function under
the hypothesis that the sequence of data tensors is generated by an underlying
Markov chain. Our setting covers the classical i.i.d. case as well as a wide
range of application contexts including data streams generated by independent
or MCMC sampling. Our result closes a gap between OTF and Online Matrix
Factorization in global convergence analysis \commHL{for CP-decompositions}.
Experimentally, we show that our algorithm converges much faster than standard
algorithms for nonnegative tensor factorization tasks on both synthetic and
real-world data. Also, we demonstrate the utility of our algorithm on a diverse
set of examples from image, video, and time-series data, illustrating how one
may learn qualitatively different CP-dictionaries from the same tensor data by
exploiting the tensor structure in multiple ways.
