Nesterov acceleration of alternating least squares for canonical tensor decomposition: momentum step size selection and restart mechanisms.
From MaRDI portal
Publication:5122239
Abstract: 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 711000900 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.
Recommendations
- Nonlinearly preconditioned L-BFGS as an acceleration mechanism for alternating least squares with application to tensor decomposition.
- A nonlinear GMRES optimization algorithm for canonical tensor decomposition
- A nonlinearly preconditioned conjugate gradient algorithm for rank-R canonical tensor approximation.
- On accelerating the regularized alternating least-squares algorithm for tensors
- Local convergence of the alternating least squares algorithm for canonical tensor approximation
Cited in
(11)- On the convergence of a class of inertial dynamical systems with Tikhonov regularization
- On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM
- Nonlinearly preconditioned L-BFGS as an acceleration mechanism for alternating least squares with application to tensor decomposition.
- A nonlinearly preconditioned conjugate gradient algorithm for rank-R canonical tensor approximation.
- Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
- On the asymptotic linear convergence speed of Anderson acceleration, Nesterov acceleration, and nonlinear GMRES
- An AO-ADMM Approach to Constraining PARAFAC2 on All Modes
- Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
- Accelerated doubly stochastic gradient descent for tensor CP decomposition
- Quasi-orthogonalization for alternating non-negative tensor factorization
- Accelerating the computation of tensor Z-eigenvalues
This page was built for publication: Nesterov acceleration of alternating least squares for canonical tensor decomposition: momentum step size selection and restart mechanisms.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5122239)
