# Homotopy Analysis for Tensor PCA

arXiv: https://arxiv.org/abs/1610.09322 · HTML: https://mlsanity.com/paper/1610.09322/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2016.

## Built on by (most cited first, 12 of 12)

- [ConViT: Improving Vision Transformers with Soft Convolutional Inductive Biases](https://mlsanity.com/paper/2103.10697/) (2021)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [Continuation Path Learning for Homotopy Optimization](https://mlsanity.com/paper/2307.12551/) (2023)
- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models](https://mlsanity.com/paper/2411.05708/) (2024)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging](https://mlsanity.com/paper/2603.06028/) (2026)
- [A Homotopy Algorithm for Optimal Transport](https://mlsanity.com/paper/2112.06763/) (2021)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)
- [Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation](https://mlsanity.com/paper/2509.17382/) (2025)
- [Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruption](https://mlsanity.com/paper/2605.29497/) (2026)

## Abstract (arXiv)

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.