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

Abstract

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.

References in corpus (19)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• A note on the group lasso and a sparse group lasso
• Tensor Regression with Applications in Neuroimaging Data Analysis
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Optimal Algorithms for $L_1$-subspace Signal Processing
• Efficient L1-Norm Principal-Component Analysis via Bit Flipping
• Convex Tensor Decomposition via Structured Schatten Norm Regularization
• STORE: Sparse Tensor Response Regression and Neuroimaging Analysis
• Fast and Guaranteed Tensor Decomposition via Sketching
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Score Function Features for Discriminative Learning: Matrix and Tensor Framework
• Wedderburn rank reduction and Krylov subspace method for tensor approximation. Part 1: Tucker case
• Regularized Tensor Factorizations and Higher-Order Principal Components Analysis
• Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving
• Tensor Methods for Additive Index Models under Discordance and Heterogeneity
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Optimal link prediction with matrix logistic regression