Alex Gittens, Rensselaer Polytechnic Institute (RPI)

Abstract

We consider the application of sketching to low CP-rank approximation of tensors. Prior works have introduced novel forms of sketching that are well-suited to this setting from the computational perspective, but have left open the question of whether the resulting heuristics converge. In this work, we provide generic conditions under which sketched, regularized alternating least squares algorithms guarantee convergence to a stationary point. Our results imply that the sketching rate must vary during the optimization procedure to ensure convergence. Based on this insight, we introduce CPD-MWU, an algorithm that predicts and tracks the best choice of sketching rate over the course of the optimization, and show empirically that CPD-MWU performs as well as other sketched ALS algorithms while also being much more robust to the selection of the sketching rate hyperparameter.

Video