%AZhang, A.%ALuo, Y%ARaskutti, G%AYuan, M.%BJournal Name: SIAM journal on mathematics of data science; Journal Volume: 2; Journal Issue: 2 %D2020%I %JJournal Name: SIAM journal on mathematics of data science; Journal Volume: 2; Journal Issue: 2 %K %MOSTI ID: 10164437 %PMedium: X %TISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching %XIn this paper, we develop a novel procedure for low-rank tensor regression, namely Importance Sketching Low-rank Estimation for Tensors (ISLET). The central idea behind ISLET is importance sketching, i.e., carefully designed sketches based on both the responses and low-dimensional structure of the parameter of interest. We show that the proposed method is sharply minimax optimal in terms of the mean-squared error under low-rank Tucker assumptions and under the randomized Gaussian ensemble design. In addition, if a tensor is low-rank with group sparsity, our procedure also achieves minimax optimality. Further, we show through numerical study that ISLET achieves comparable or better mean-squared error performance to existing state-of-the-art methods while having substantial storage and run-time advantages including capabilities for parallel and distributed computing. In particular, our procedure performs reliable estimation with tensors of dimension $p = O(10^8)$ and is 1 or 2 orders of magnitude faster than baseline methods. %0Journal Article