Tight query complexity lower bounds for PCA via finite sample deformed wigner law.
Max SimchowitzAhmed El AlaouiBenjamin RechtPublished in: STOC (2018)
Keyphrases
- finite sample
- query complexity
- lower bound
- vc dimension
- statistical learning theory
- uniform convergence
- upper bound
- concept class
- principal component analysis
- sample size
- worst case
- concept classes
- sample complexity
- dimensionality reduction
- generalization error
- upper and lower bounds
- face recognition
- error bounds
- np hard
- feature extraction
- lower and upper bounds
- low dimensional
- pac learning
- optimal solution
- objective function
- nearest neighbor
- learning machines
- data complexity
- membership queries
- feature space
- learning theory
- subspace methods
- high dimensional
- support vector machine
- statistical learning
- machine learning