Homotopy Analysis for Tensor PCA

Abstract

Developing efficient and guaranteed nonconvex algorithms has been an important challenge in modern machine learning. Algorithms with good empirical performance such as stochastic gradient descent often lack theoretical guarantees. In this paper, we analyze the class of homotopy or continuation methods for global optimization of nonconvex functions. These methods start from an objective function that is efficient to optimize (e.g. convex), and progressively modify it to obtain the required objective, and the solutions are passed along the homotopy path. For the challenging problem of tensor PCA, we prove global convergence of the homotopy method in the "high noise" regime. The signal-to-noise requirement for our algorithm is tight in the sense that it matches the recovery guarantee for the best degree-4 sum-of-squares algorithm. In addition, we prove a phase transition along the homotopy path for tensor PCA. This allows to simplify the homotopy method to a local search algorithm, viz., tensor power iterations, with a specific initialization and a noise injection procedure, while retaining the theoretical guarantees.

arXiv commentAccepted to COLT 2017

References in corpus (12)

• Message Passing Algorithms for Compressed Sensing
• The Loss Surfaces of Multilayer Networks
• Optimal detection of sparse principal components in high dimension
• Matrix Completion has No Spurious Local Minimum
• Limits of spiked random matrices I
• A statistical model for tensor PCA
• On Graduated Optimization for Stochastic Non-Convex Problems
• Tensor principal component analysis via sum-of-squares proofs
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Complete Dictionary Recovery over the Sphere
• Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
• Closed Form for Some Gaussian Convolutions

Cited by in corpus (6)

• Binary MIMO Detection via Homotopy Optimization and Its Deep Adaptation
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• Finding the Needle in the Haystack with Convolutions: on the benefits of architectural bias
• Tensor SVD: Statistical and Computational Limits
• Optimal Sparse Singular Value Decomposition for High-dimensional High-order Data