Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
share
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∈R^d × d, an algorithm Alg is allowed to make T exact queries of the form w^(i) = Mv^(i) for i in {1,...,T}, where v^(i) is drawn from a distribution which depends arbitrarily on the past queries and measurements {v^(j),w^(i)}_1 < j < i-1. We show that for every gap∈ (0,1/2], there exists a distribution over matrices M for which 1) gap_r(M) = Ω(gap) (where gap_r(M) is the normalized gap between the r and r+1-st largest-magnitude eigenvector of M), and 2) any algorithm Alg which takes fewer than const×r d/√(gap) queries fails (with overwhelming probability) to identity a matrix V∈R^d × r with orthonormal columns for which 〈V, MV〉> (1 - const×gap)∑_i=1^r λ_i(M). Our bound requires only that d is a small polynomial in 1/gap 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.
READ FULL TEXT