Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law

We prove a query complexity lower bound for approximating the top r dimensional eigenspace of a matrix. We consider an oracle model where, given a symmetric matrix M ∈ ℝd × d, an algorithm mathsfAlg is allowed to make mathsfT exact queries of the form mathsfw(i) = M mathsfv(i) for i in 1,...,mathsfT, where mathsfv(i) is drawn from a distribution which depends arbitrarily on the past queries and measurements mathsfv(j),mathsfw(i)1 ≤ j ≤ i-1. We show that for every mathttgap ∈ (0,1/2], there exists a distribution over matrices M for which 1) gapr(M) = Omega(mathttgap) (where gapr(M) is the normalized gap between the r and r+1-st largest-magnitude eigenvector of M), and 2) any algorithm mathsfAlg which takes fewer than const × fracr log d√mathttgap queries fails (with overwhelming probability) to identity a matrix widehatmathsfV ∈ ℝd × r with orthonormal columns for which langle widehatmathsfV, M widehatmathsfVrangle ≥ (1 - const × mathttgap)sumi=1r λi(M). Our bound requires only that d is a small polynomial in 1/mathttgap and r, and matches the upper bounds of Musco and Musco '15. Moreover, it establishes a strict separation between convex optimization and randomized, "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.