Abstract: We consider the problem of estimating a large rank-one tensor $u^{\otimes k} \in (\mathbb{R}^n)^{\otimes k}, k \geq 3$, in Gaussian noise. Earlier work characterized a critical signal-to-noise ratio $\lambda_{\text{Bayes}} = O(1)$ above which an ideal estimator achieves strictly positive correlation with the unknown vector of interest. Remarkably, no polynomial-time algorithm is known that achieved this goal unless $\lambda \geq Cn^{(k-2)/4}$, and even powerful semidefinite programming relaxations appear to fail for $1 \ll \lambda \ll n^{(k-2)/4}$. In order to elucidate this behavior, we consider the maximum likelihood estimator, which requires maximizing a degree-$k$ homogeneous polynomial over the unit sphere in $n$ dimensions. We compute the expected number of critical points and local maxima of this objective function and show that it is exponential in the dimensions $n$, and give exact formulas for the exponential growth rate. We show that (for $\lambda$ larger than a constant) critical points are either very close to the unknown vector $u$ or are confined in a band of width $\Theta(\lambda^{-1/(k-1)})$ around the maximum circle that is orthogonal to $u$. For local maxima, this band shrinks to be of size $\Theta(\lambda^{-1/(k-2)})$. These “uninformative” local maxima are likely to cause the failure of optimization algorithms.
Introduction
In high-dimensional statistics, a significant gap often exists between information-theoretic limits and computational feasibility. The Spiked Tensor Model serves as a canonical example of this "computational-statistical gap." For a $k$-order tensor, while recovery is theoretically possible at constant signal-to-noise ratios (SNR), practical algorithms typically require the SNR to scale with the dimension $n$. This study investigates the root of this difficulty by analyzing the optimization landscape of the Maximum Likelihood Estimator (MLE).
Geometric Analysis of the MLE Landscape
The MLE objective function involves maximizing a degree-$k$ homogeneous polynomial over an $n$-dimensional unit sphere. To characterize this landscape, the authors employ the Kac-Rice formula and random matrix theory, specifically analyzing the Hessian of the objective function as a spiked random matrix.
A key metric derived is the complexity function $S(m)$, which represents the exponential growth rate of the expected number of critical points as a function of their correlation $m$ with the true signal. This complexity indicates that the number of critical points grows exponentially with the dimension $n$.
The "Minefield" of Local Maxima
The analysis reveals an "exponential explosion of traps." The landscape is populated by exponentially many local maxima that are "uninformative"---they possess nearly zero correlation with the true signal. These traps are concentrated in a narrow band around the sphere's equator, orthogonal to the signal.
As the SNR ($\lambda$) increases, the landscape evolves through three phases:
- Low SNR: Only uninformative maxima exist.
- Intermediate SNR: Informative local maxima emerge but are rare and have lower values than the spurious ones.
- High SNR: Informative maxima become global, but the numerous spurious traps persist.
Results and Computational Implications
The authors provide exact formulas for the width of the uninformative band, showing it scales as $\Theta(\lambda^{-1/(k-2)})$ for local maxima. This geometric structure explains why standard optimization algorithms, like gradient descent or power iteration, fail without a very precise initialization. A random start typically has a correlation of $O(n^{-1/2})$, which is insufficient to escape the uninformative band in the "hard" regime. The "population risk" is very flat near the equator, allowing random noise to create many sharp local peaks that trap algorithms.
Conclusion
By providing a rigorous geometric explanation for the computational-statistical gap in tensor PCA, this work highlights how the proliferation of spurious local maxima creates a rugged landscape that traps optimization algorithms. Future work may extend this analysis to multi-spike models and further explore the dynamics of gradient-based methods within these complex landscapes.
Summary updated