Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints

Shai Shalev-Shwartz, Nathan Srebro, Tong Zhang

Abstract

We study the problem of minimizing the expected loss of a linear predictor while constraining its sparsity, i.e., bounding the number of features used by the predictor. While the resulting optimization problem is generally NP-hard, several approximation algorithms are considered. We analyze the performance of these algorithms, focusing on the characterization of the trade-off between accuracy and sparsity of the learned predictor in different scenarios.
BibTeX
@article{shalevshwartz2010trading,
  author = {Shai Shalev-Shwartz and Nathan Srebro and Tong Zhang},
  title = {{Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints}},
  journal = {SIAM J. Optim.},
  year = {2010},
  doi = {10.1137/090759574},
}

Loading related content...

Figure