ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
复制标题
DOI：
10.1137/19m126476x
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Anru R. Zhang;Yuetian Luo;Garvesh Raskutti;M. Yuan
中科院分区：
文献类型：
--
作者：
Anru R. Zhang;Yuetian Luo;Garvesh Raskutti;M. Yuan
在本文中，我们开发了一个新的低秩张量回归过程，即 \emph{\underline{I}重要性 \underline{s}涂漆 \underline{l}低级别的 \underline{e}预估 \underline{t}传感器} （小岛）。ISLET背后的核心思想是 \emph{重要性素描}即根据感兴趣参数的响应和低维结构精心设计草图。结果表明，在低秩Tucker假设和随机高斯集合设计条件下，所提出的方法在均方误差方面是极大极小最优的。此外，如果张量是低秩且具有群稀疏性的张量，我们的过程也实现了极大极小最优性。此外，我们通过数值研究表明，ISLET实现了与现有最先进方法相当或更好的均方误差性能，同时具有大量的存储和运行时优势，包括并行和分布式计算的能力。特别地，我们的程序使用维度张量进行可靠的估计 $p = O(10^8)$ 是 $1$ 或 $2$ 比基线方法快几个数量级。
In this paper, we develop a novel procedure for low-rank tensor regression, namely \emph{\underline{I}mportance \underline{S}ketching \underline{L}ow-rank \underline{E}stimation for \underline{T}ensors} (ISLET). The central idea behind ISLET is \emph{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 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.