On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation

We prove a query complexity lower bound on rank-one principal component analysis (PCA). We consider an oracle model where, given a symmetric matrix M ∈ ℝd × d, an algorithm is allowed to make T exact queries of the form w(i) = Mv(i) for i ∈ 1,dots,T, where v(i) is drawn from a distribution which depends arbitrarily on the past queries and measurements v(j),w(j)1 ≤ j ≤ i-1. We show that for a small constant ε, any adaptive, randomized algorithm which can find a unit vector widehatv for which widehatvtopMwidehatv ≥ (1-ε)|M|, with even small probability, must make T = Omega(log d) queries. In addition to settling a widely-held folk conjecture, this bound demonstrates a fundamental gap between convex optimization and "strict-saddle" non-convex optimization of which PCA is a canonical example: in the former, first-order methods can have dimension-free iteration complexity, whereas in PCA, the iteration complexity of gradient-based methods must necessarily grow with the dimension. Our argument proceeds via a reduction to estimating the rank-one spike in a deformed Wigner model. We establish lower bounds for this model by developing a "truncated" analogue of the chi2 Bayes-risk lower bound of Chen et al.