Nesterov Acceleration of Alternating Least Squares for Canonical Tensor
  Decomposition: Momentum Step Size Selection and Restart Mechanisms
  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. This is so because the tensor decomposition problem is
non-convex and ALS is accelerated instead of gradient descent. Instead, we
consider various restart mechanisms and suitable choices of momentum weights
that enable effective acceleration. 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 methods,
when problems are ill-conditioned or accurate solutions are desired. The
resulting methods perform competitively with or superior to existing
acceleration methods for ALS, including ALS acceleration by NCG, NGMRES, or
LBFGS, and additionally enjoy the benefit of being much easier to implement. We
also compare with Nesterov-type updates where the momentum weight is determined
by a line search, which are equivalent or closely related to existing line
search methods for ALS. On a large and ill-conditioned
71$\times$1000$\times$900 tensor consisting of readings from chemical sensors
to track hazardous gases, the restarted Nesterov-ALS method shows desirable
robustness properties and outperforms any of the existing methods by a large
factor. There is clear potential for extending our Nesterov-type acceleration
approach to accelerating other optimization algorithms than ALS applied to
other non-convex problems, such as Tucker tensor decomposition. Our Matlab code
is available at
https://github.com/hansdesterck/nonlinear-preconditioning-for-optimization.
