The Landscape of the Spiked Tensor Model

Source abstract

We consider the problem of estimating a large rank‐one tensor u ⊗ k ∈ ( ℝ n ) ⊗ k , k ≥ 3 , in Gaussian noise. Earlier work characterized a critical signal‐to‐noise ratio λ 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 λ ≥ Cn ( k − 2)/4 , and even powerful semidefinite programming relaxations appear to fail for 1 ≪ λ ≪ 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 λ larger than a constant) critical points are either very close to the unknown vector u or are confined in a band of width Θ( λ −1/( k − 1) ) around the maximum circle that is orthogonal to u . For local maxima, this band shrinks to be of size Θ( λ −1/( k − 2) ) . These “uninformative” local maxima are likely to cause the failure of optimization algorithms. © 2019 Wiley Periodicals, Inc.