ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching

• Activity Number: 588 - Statistical Analysis of Tensor Data
• Type: Invited
• Date/Time: Thursday, August 1, 2019 : 8:30 AM to 10:20 AM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Anru Zhang* and Yuetian Luo and Garvesh Raskutti and Ming Yuan
• Companies: University of Wisconsin-Madison and University of Wisconsin-Madison and University of Wisconsin-Madison and Columbia University

Abstract

We develop a novel procedure for low-rank tensor regression, namely \emph{Importance Sketching Low-rank Estimation for Tensors} (ISLET). The central idea behind ISLET involves constructing specifically designed structural sketches, named \emph{importance sketching} based on Higher Order Orthogonal Iteration of Tensors (HOOI) and combining sketched estimated components using the recently developed Cross procedure. We show that our algorithm achieves minimax optimal mean-squared error under low-rank tucker and group sparsity assumptions. For low-rank tensors without sparsity, we prove that our procedure also achieves minimax optimal constants. Further, we show through an extensive numerical study that our ISLET procedure achieves comparable mean-squared error performance to existing state-of-the-art methods whilst having substantial storage and run-time advantages. In particular, our procedure performs reliable tensor estimation with tensors of with dimension p = O(10^8) and is 2 or 3 orders of magnitude faster than existing state-of-the-art methods.