Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence

Abstract

In this paper, we consider the estimation of a low Tucker rank tensor from a number of noisy linear measurements. The general problem covers many specific examples arising from applications, including tensor regression, tensor completion, and tensor PCA/SVD. We consider an efficient Riemannian Gauss-Newton (RGN) method for low Tucker rank tensor estimation. Different from the generic (super)linear convergence guarantee of RGN in the literature, we prove the first local quadratic convergence guarantee of RGN for low-rank tensor estimation in the noisy setting under some regularity conditions and provide the corresponding estimation error upper bounds. A deterministic estimation error lower bound, which matches the upper bound, is provided that demonstrates the statistical optimality of RGN. The merit of RGN is illustrated through two machine learning applications: tensor regression and tensor SVD. Finally, we provide the simulation results to corroborate our theoretical findings.

References in corpus (21)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tensor Regression with Applications in Neuroimaging Data Analysis
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Provable Tensor Factorization with Missing Data
• Low-rank tensor completion: a Riemannian manifold preconditioning approach
• STORE: Sparse Tensor Response Regression and Neuroimaging Analysis
• A Riemannian trust-region method for low-rank tensor completion
• Tensor Regression Using Low-rank and Sparse Tucker Decompositions
• Learning from Multiway Data: Simple and Efficient Tensor Regression
• Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
• Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Tensor Methods for Additive Index Models under Discordance and Heterogeneity
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• Second-order optimization for tensors with fixed tensor-train rank

Cited by in corpus (4)

• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Supervised tensor decomposition with features on multiple modes
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion