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

Abstract

We prove a \emph{query complexity} lower bound on rank-one principal component analysis (PCA). We consider an oracle model where, given a symmetric matrix $M\in {\mathbb{R}}^{d\times d}$, an algorithm is allowed to make $T$ \emph{exact} queries of the form $w^{(i)}=M{v}^{(i)}$ for $i\in \{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\le j\le i-1}$. We show that for a small constant $\epsilon$, any adaptive, randomized algorithm which can find a unit vector $\hat{v}$ for which ${\hat{v}}^{\top }M\hat{v}\ge (1-\epsilon )\Vert M\Vert$, 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 ${\chi }^2$ Bayes-risk lower bound of Chen et al.

References in corpus (16)

• Neural Machine Translation by Jointly Learning to Align and Translate
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• How to Escape Saddle Points Efficiently
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• On combinatorial testing problems
• When Are Nonconvex Problems Not Scary?
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Distance-based and continuum Fano inequalities with applications to statistical estimation
• On Bayes Risk Lower Bounds
• Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• On Approximating Functions of the Singular Values in a Stream
• Optimal lower bounds for universal relation, samplers, and finding duplicates
• Time lower bounds for nonadaptive turnstile streaming algorithms

Cited by in corpus (4)

• Escaping Saddles with Stochastic Gradients
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Communication-Efficient Distributed SVD via Local Power Iterations