Average-Case Integrality Gap for Non-Negative Principal Component Analysis.
Afonso S. BandeiraDmitriy KuniskyAlexander S. WeinPublished in: MSML (2021)
Keyphrases
- average case
- principal component analysis
- integrality gap
- worst case
- linear programming relaxation
- uniform distribution
- approximation algorithms
- lower bound
- linear program
- agnostic learning
- valid inequalities
- dimensionality reduction
- dnf formulas
- mixed integer programming
- feature space
- lp relaxation
- branch and bound
- low dimensional
- linear programming
- vc dimension
- arbitrarily close
- knapsack problem
- pac learning
- column generation
- machine learning
- computational complexity
- feature extraction
- feature selection
- learning algorithm