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

2019/11/09 by Anru R. Zhang, Yuetian Luo, Zhang, Anru +5 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Methodology (stat.ME) #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.1911.03804

openalex publication_date 2019/11/09 · openalex created_date 2019/11/22 · openalex updated_date 2026/07/28

Abstract

In this paper, we develop a novel procedure for low-rank tensor regression, namely \emph\underlineImportance \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(10⁸) and is 1 or 2 orders of magnitude faster than baseline methods.

Citations

• Fast and Guaranteed Tensor Decomposition via Sketching
• Finding frequent items in data streams
• Score Function Features for Discriminative Learning: Matrix and Tensor Framework
• Some Mathematical Notes on Three-Mode Factor Analysis
• Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement
• Tensor Decompositions and Applications
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tensor Regression with Applications in Neuroimaging Data Analysis
• Tensor Decomposition for Signal Processing and Machine Learning
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Optimal link prediction with matrix logistic regression
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

• Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold

Related

• Sparse and Low-rank Tensor Estimation via Cubic Sketchings
• Boosted Sparse and Low-Rank Tensor Regression
• Near Optimal Sketching of Low-Rank Tensor Regression
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation