# Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law

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

## Key facts

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

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

- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Simultaneous analysis of approximate leave-one-out cross-validation and mean-field inference](https://mlsanity.com/paper/2501.02624/) (2025)
- [Improved analysis of randomized SVD for top-eigenvector approximation](https://mlsanity.com/paper/2202.07992/) (2022)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)

## Abstract (arXiv)

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 mathsfAlg is allowed to make mathsfT exact queries of the form mathsfw(i) = M mathsfv(i) for i in 1,...,mathsfT, where mathsfv(i) is drawn from a distribution which depends arbitrarily on the past queries and measurements mathsfv(j),mathsfw(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) = Omega(mathttgap) (where gapr(M) is the normalized gap between the r and r+1-st largest-magnitude eigenvector of M), and 2) any algorithm mathsfAlg which takes fewer than const × fracr log d√mathttgap queries fails (with overwhelming probability) to identity a matrix widehatmathsfV ∈ ℝd × r with orthonormal columns for which langle widehatmathsfV, M widehatmathsfVrangle ≥ (1 - const × mathttgap)sumi=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.