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

2017/04/14 by Simchowitz, Max, Alaoui, Ahmed El, Recht, Benjamin
#Combinatorics (math.CO) #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)

paper · doi:10.48550/arxiv.1704.04548

Abstract

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⁽ⁱ⁾ = Mv⁽ⁱ⁾ for i ∈ \1,…,T\, where v⁽ⁱ⁾ 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 \widehatv^\topM\widehatv ≥ (1-ε)‖M‖, with even small probability, must make T = Ω(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 χ² Bayes-risk lower bound of Chen et al.

Related

• Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
• Sum-of-Squares Lower Bounds for Sparse PCA
• Fast Algorithms for Robust PCA via Gradient Descent
• Fast and Simple PCA via Convex Optimization
• Hidden Convexity of Fair PCA and Fast Solver via Eigenvalue Optimization