Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness.

Matthew S. Brennan Guy Bresler

Published in: COLT (2019)

Keyphrases

average case
worst case
worst case analysis
upper bound
np hard
lower bound
sparse pca
computational complexity
dynamic programming
machine learning
average case complexity
approximation algorithms
vc dimension
uniform distribution
np hardness
active learning
feature selection