Trading accuracy for sparsity in optimization problems with sparsity constraints

Shai Shalev-Shwartz, Nathan Srebro, Tong Zhang

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)2807-2832
Number of pages26
JournalSIAM Journal on Optimization
Issue number6
StatePublished - 2010
Externally publishedYes


  • Linear prediction
  • Sparsity

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Applied Mathematics


Dive into the research topics of 'Trading accuracy for sparsity in optimization problems with sparsity constraints'. Together they form a unique fingerprint.

Cite this