Statistical Query Lower Bounds for Tensor PCA.
Rishabh DudejaDaniel HsuPublished in: J. Mach. Learn. Res. (2021)
Keyphrases
- lower bound
- statistical queries
- principal component analysis
- dimensionality reduction
- upper bound
- noise tolerant
- concept class
- principal components
- lower and upper bounds
- np hard
- face recognition
- face images
- learning theory
- uniform distribution
- feature extraction
- worst case
- low dimensional
- concept classes
- optimal solution
- objective function
- feature space
- vc dimension
- small number
- machine learning
- semi supervised
- high dimensional
- sample complexity
- dnf formulas