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

arXiv: https://arxiv.org/abs/1704.04548 · HTML: https://mlsanity.com/paper/1704.04548/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2017.

## Built on by (most cited first, 2 of 2)

- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Resource-Efficient Invariant Networks: Exponential Gains by Unrolled Optimization](https://mlsanity.com/paper/2203.05006/) (2022)

## Abstract (arXiv)

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(i) = Mv(i) for i ∈ 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 ≤ j ≤ i-1. We show that for a small constant ε, any adaptive, randomized algorithm which can find a unit vector widehatv for which widehatvtopMwidehatv ≥ (1-ε)|M|, 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 chi2 Bayes-risk lower bound of Chen et al.