text: We present Nesterov-type acceleration techniques for Alternating Least Squares (ALS) methods applied to canonical tensor decomposition. While Nesterov acceleration turns gradient descent into an optimal first-order method for convex problems by adding a momentum term with a specific weight sequence, a direct application of this method and weight sequence to ALS results in erratic convergence behaviour or divergence. This is so because the tensor decomposition problem is non-convex and ALS is accelerated instead of gradient descent. We investigate how line search or restart mechanisms can be used to obtain effective acceleration. We first consider a cubic line search (LS) strategy for determining the momentum weight, showing numerically that the combined Nesterov-ALS-LS approach is competitive with or superior to other recently developed nonlinear acceleration techniques for ALS, including acceleration by nonlinear conjugate gradients (NCG) and LBFGS. As an alternative, we consider various restarting techniques, some of which are inspired by previously proposed restarting mechanisms for Nesterov's accelerated gradient method. We study how two key parameters, the momentum weight and the restart condition, should be set. Our extensive empirical results show that the Nesterov-accelerated ALS methods with restart can be dramatically more efficient than the stand-alone ALS or Nesterov accelerated gradient method, when problems are ill-conditioned or accurate solutions are required. The resulting methods perform competitively with or superior to existing acceleration methods for ALS, and additionally enjoy the benefit of being much simpler and easier to implement. On a large and ill-conditioned 71 x 1000 x 900 tensor consisting of readings from chemical sensors used for tracking hazardous gases, the restarted Nesterov-ALS method outperforms any of the existing methods by a large factor.
  @cite_5: We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's scheme. As a byproduct, we obtain a family of schemes with similar convergence rates. The ODE interpretation also suggests restarting Nesterov's scheme leading to an algorithm, which can be rigorously proven to converge at a linear rate whenever the objective is strongly convex.
  @cite_9: We present accelerated residual methods for the iterative solution of systems of equations by leveraging recent developments in accelerated gradient methods for convex optimization. The stability p...
  @cite_17: 
summary: Nesterov's accelerated gradient method is known to exhibit oscillatory behavior on convex problems. An interesting discussion on this is provided in @cite_5 which formulates an ODE as the continuous time analogue of Nesterov's method. Such oscillatory behavior happens when the method approaches convergence, and can be alleviated by restarting the algorithm using the current iterate as the initial solution, usually resetting the sequence of momentum weights to its initial state close to 0. In @cite_5 an explanation is provided of why resetting the momentum weight to a small value is effective using the ODE formulation of Nesterov's accelerated gradient descent. In @cite_17 the use of adaptive restarting was explored for convex problems, and @cite_9 explored the use of adaptive restarting and adaptive momentum weight for nonlinear systems of equations resulting from finite element approximation of PDEs. Our work is the first study of a general Nesterov-accelerated ALS scheme.