Adaptive Sketching for the Low-rank Tensor Approximation Problem

September 16, 2019, 11:30 AM - 12:10 PM


Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

Alex Gittens, Rensselaer Polytechnic Institute (RPI)

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.