A Caltech Library Service

Homotopy Analysis for Tensor PCA

Anandkumar, Anima and Deng, Yuan and Ge, Rong and Mobahi, Hossein (2017) Homotopy Analysis for Tensor PCA. Proceedings of Machine Learning Research, 65 . pp. 79-104. ISSN 1938-7228.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 \em best degree-4 sum-of-squares algorithm. In addition, we prove a phase transition along the homotopy path for tensor PCA. This allows us 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2017 A. Anandkumar, Y. Deng, R. Ge & H. Mobahi.
Subject Keywords:Tensor PCA, homotopy, continuation, Gaussian smoothing, nonconvex optimization, global optimization
Record Number:CaltechAUTHORS:20190401-123333151
Persistent URL:
Official Citation:Homotopy Analysis for Tensor PCA Anima Anandkumar, Yuan Deng, Rong Ge, Hossein Mobahi ; Proceedings of the 2017 Conference on Learning Theory, PMLR 65:79-104, 2017.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94330
Deposited By: George Porter
Deposited On:01 Apr 2019 21:27
Last Modified:03 Oct 2019 21:03

Repository Staff Only: item control page