2018/04/04 by Simchowitz, Max, Alaoui, Ahmed El, Recht, Benjamin · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1804.01221
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 Alg is allowed to make T exact queries of the form w(i) = M v(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 \mathttgap ∈ (0,1/2], there exists a distribution over matrices M for which 1) gapr(M) = Ω(\mathttgap) (where gapr(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 × \fracr log d√\mathttgap queries fails (with overwhelming probability) to identity a matrix \widehatV ∈ ℝd × r with orthonormal columns for which ⟨ \widehatV, M \widehatV⟩ ≥ (1 - const × \mathttgap)∑i=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.