Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law.
Max SimchowitzAhmed El AlaouiBenjamin RechtPublished in: CoRR (2018)
Keyphrases
- finite sample
- query complexity
- lower bound
- vc dimension
- statistical learning theory
- upper bound
- uniform convergence
- sample size
- concept class
- principal component analysis
- worst case
- concept classes
- sample complexity
- data complexity
- generalization error
- feature extraction
- lower and upper bounds
- learning machines
- optimal solution
- upper and lower bounds
- face recognition
- pac learning
- nearest neighbor
- np hard
- objective function
- dimensionality reduction
- membership queries
- error bounds
- subspace methods
- inductive inference
- pairwise
- feature selection