Optimization Landscape of Tucker Decomposition

Abstract

Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gradient descent have become popular in practice. In this paper, we characterize the optimization landscape of the Tucker decomposition problem. In particular, we show that if the tensor has an exact Tucker decomposition, for a standard nonconvex objective of Tucker decomposition, all local minima are also globally optimal. We also give a local search algorithm that can find an approximate local (and global) optimal solution in polynomial time.

References in corpus (10)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Matrix Completion has No Spurious Local Minimum
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Understanding Composition of Word Embeddings via Tensor Decomposition

Cited by in corpus (3)

• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
• The loss landscape of deep linear neural networks: a second-order analysis