  Tensor regression has shown to be advantageous in learning tasks with
multi-directional relatedness. Given massive multiway data, traditional methods
are often too slow to operate on or suffer from memory bottleneck. In this
paper, we introduce subsampled tensor projected gradient to solve the problem.
Our algorithm is impressively simple and efficient. It is built upon projected
gradient method with fast tensor power iterations, leveraging randomized
sketching for further acceleration. Theoretical analysis shows that our
algorithm converges to the correct solution in fixed number of iterations. The
memory requirement grows linearly with the size of the problem. We demonstrate
superior empirical performance on both multi-linear multi-task learning and
spatio-temporal applications.
