Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion

Abstract

This paper is concerned with the low Tucker-rank tensor completion problem, which is about reconstructing a tensor $T\in {\mathbb{R}}^{n\times n\times n}$ of low multilinear rank from partially observed entries. Riemannian optimization algorithms are a class of efficient methods for this problem, but the theoretical convergence analysis is still lacking. In this manuscript, we establish the entrywise convergence of the vanilla Riemannian gradient method for low Tucker-rank tensor completion under the nearly optimal sampling complexity $O(n^{3/2})$. Meanwhile, the implicit regularization phenomenon of the algorithm has also been revealed. As far as we know, this is the first work that has shown the entrywise convergence and implicit regularization property of a non-convex method for low Tucker-rank tensor completion. The analysis relies on the leave-one-out technique, and some of the technical results developed in the paper might be of broader interest in investigating the properties of other non-convex methods for this problem.

References in corpus (24)

• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• A Simpler Approach to Matrix Completion
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Parallel matrix factorization for low-rank tensor completion
• Guaranteed Matrix Completion via Non-convex Factorization
• 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
• Incoherence-Optimal Matrix Completion
• A Spectral Algorithm for Latent Dirichlet Allocation
• Estimation of low-rank tensors via convex optimization
• Provable Tensor Factorization with Missing Data
• Near-optimal bounds for phase synchronization
• Low-rank tensor completion: a Riemannian manifold preconditioning approach
• Geometry of Optimization and Implicit Regularization in Deep Learning
• A Riemannian trust-region method for low-rank tensor completion
• Tensor Completion by Alternating Minimization under the Tensor Train (TT) Model
• A New Sampling Technique for Tensors
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery