Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
arXiv:2104.12031
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 (10)
- Provable Tensor Factorization with Missing Data
- Learning from Multiway Data: Simple and Efficient Tensor Regression
- Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
- Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection
- Rank 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