Accelerated Doubly Stochastic Gradient Descent for Tensor CP Decomposition

In this paper, we focus on the acceleration of doubly stochastic gradient descent method for computing the CANDECOMP/PARAFAC (CP) decomposition of tensors. This optimization problem has N blocks, where N is the order of the tensor. Under the doubly stochastic framework, each block subproblem is solved by the vanilla stochastic gradient method. However, the convergence analysis requires that the variance converges to zero, which is hard to check in practice and may not hold in some implementations. In this paper, we propose accelerating the stochastic gradient method by the momentum acceleration and the variance reduction technique, denoted as DS-MVR. Theoretically, the convergence of DS-MVR only requires the variance to be bounded. Under mild conditions, we show DS-MVR converges to a stochastic $$\varepsilon $$ ε -stationary solution in $$\tilde{\mathcal {O}}(N^{3/2}\varepsilon ^{-3})$$ O ~ ( N 3 / 2 ε - 3 ) iterations with varying stepsizes and in $$\mathcal {O}(N^{3/2}\varepsilon ^{-3})$$ O ( N 3 / 2 ε - 3 ) iterations with constant stepsizes, respectively. Numerical experiments on four real-world datasets show that our proposed algorithm can get better results compared with the baselines.