An optimal statistical and computational framework for generalized tensor estimation

2022/02/01 by Rungang Han, Rebecca Willett, Anru R. Zhang · 66 citations
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Blind Source Separation Techniques #Combinatorics #Computer science #Convergence (economics) #Coordinate descent #Estimator #Mathematical optimization #Mathematics #Minimax #Rank (graph theory) #Rate of convergence #Sparse and Compressive Sensing Techniques #Statistics #Tensor (intrinsic definition) #Tensor decomposition and applications

paper · pdf · doi:10.1214/21-aos2061

published in The Annals of Statistics 50(1) (Institute of Mathematical Statistics)

openalex publication_date 2022/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

This paper describes a flexible framework for generalized low-rank tensor estimation problems that includes many important instances arising from applications in computational imaging, genomics, and network analysis. The proposed estimator consists of finding a low-rank tensor fit to the data under generalized parametric models. To overcome the difficulty of nonconvexity in these problems, we introduce a unified approach of projected gradient descent that adapts to the underlying low-rank structure. Under mild conditions on the loss function, we establish both an upper bound on statistical error and the linear rate of computational convergence through a general deterministic analysis. Then we further consider a suite of generalized tensor estimation problems, including sub-Gaussian tensor PCA, tensor regression, and Poisson and binomial tensor PCA. We prove that the proposed algorithm achieves the minimax optimal rate of convergence in estimation error. Finally, we demonstrate the superiority of the proposed framework via extensive experiments on both simulated and real data.

Citations

• Tensor Decompositions and Applications
• Most Tensor Problems Are NP-Hard
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Generalized Linear Models

Cited by

• Precise sample covariance spectral norm error -- an RDT view
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• High-dimensional Autoregressive Modeling for Time Series with Hierarchical Structures
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Near-Efficient and Non-Asymptotic Multiway Inference
• High-dimensional low-rank matrix regression with unknown latent structures
• Accelerating Large-Scale Regularized High-Order Tensor Recovery
• Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold
• Functional Tensor Regression
• Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Landscape Analysis of Simultaneous Blind Deconvolution and Phase Retrieval via Structured Low-Rank Tensor Recovery
• Partially Observed Dynamic Tensor Response Regression
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• High-Dimensional Low-Rank Tensor Autoregressive Time Series Modeling
• Long Random Matrices and Tensor Unfolding
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Change Point Localization and Inference in Dynamic Multilayer Networks
• A Scalable Factorization Approach for High-Order Structured Tensor Recovery
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Statistical Limits for Finite-Rank Tensor Estimation
• Learning Good State and Action Representations via Tensor Decomposition
• Sharp Concentration of Simple Random Tensors II: Asymmetry

Related

• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimization
• Group SLOPE Penalized Low-Rank Tensor Regression
• Statistical and computational rates in high rank tensor estimation