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

arXiv: https://arxiv.org/abs/1911.03804 · HTML: https://mlsanity.com/paper/1911.03804/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2019.

## Built on by (most cited first, 14 of 14)

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [On High-dimensional and Low-rank Tensor Bandits](https://mlsanity.com/paper/2305.03884/) (2023)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Comfetch: Federated Learning of Large Networks on Constrained Clients via Sketching](https://mlsanity.com/paper/2109.08346/) (2021)
- [Multi-dimensional domain generalization with low-rank structures](https://mlsanity.com/paper/2309.09555/) (2023)
- [A Minimax Lower Bound for Low-Rank Matrix-Variate Logistic Regression](https://mlsanity.com/paper/2105.14673/) (2021)
- [Structured Low-Rank Tensors for Generalized Linear Models](https://mlsanity.com/paper/2308.02922/) (2023)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Low-Rank Phase Retrieval with Structured Tensor Models](https://mlsanity.com/paper/2202.08260/) (2022)
- [Bayesian Additive Main Effects and Multiplicative Interaction Models using Tensor Regression for Multi-environmental Trials](https://mlsanity.com/paper/2301.03655/) (2023)
- [Matrix Completion via Residual Spectral Matching](https://mlsanity.com/paper/2412.10005/) (2024)
- [Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold](https://mlsanity.com/paper/2510.00569/) (2025)

## Abstract (arXiv)

In this paper, we develop a novel procedure for low-rank tensor regression, namely emphunderlineImportance underlineSketching underlineLow-rank underlineEstimation for underlineTensors (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 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(108) and is 1 or 2 orders of magnitude faster than baseline methods.