{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T13:43:38Z","timestamp":1791035018181,"version":"4.1.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/090759574","type":"journal-article","created":{"date-parts":[[2010,8,19]],"date-time":"2010-08-19T18:11:22Z","timestamp":1282241482000},"page":"2807-2832","source":"Crossref","is-referenced-by-count":79,"title":["Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints"],"prefix":"10.1137","volume":"20","author":[{"given":"Shai","family":"Shalev-Shwartz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan","family":"Srebro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,8,19]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1080\/10556780701589669"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/18.256500"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"J. Borwein and A. Lewis,\n                      Convex Analysis and Nonlinear Optimization\n                      , Springer, New York, 2006.","DOI":"10.1007\/978-0-387-31256-9"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"R5","unstructured":"E. J. Candes,\n                      Compressive sampling\n                      , in Proceedings of the International Congress of Math., Madrid, Spain, 2006."},{"key":"R6","unstructured":"K. L. Clarkson,\n                      Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm\n                      , in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008, pp. 922\u2013931."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02678430"},{"key":"R8","unstructured":"D. L. Donoho,\n                      Compressed Sensing\n                      , Technical report, Stanford University, Palo Alto, CA, 2006."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20131"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"R11","first-page":"771","volume":"14","author":"Freund Y.","year":"1999","journal-title":"J. Japanese Soc. Artif. Intell."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1013203451"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589445"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176348546"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0315"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/18.556601"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022869011914"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/78.258082"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240406"},{"key":"R20","unstructured":"A. Y. Ng,\n                      Feature selection, $l_1$ vs. $l_2$ regularization, and rotational invariance\n                      , in Proceedings of the Twenty-First International Conference on Machine Learning, 2004."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"K. Oleszkiewicz,\n                      On a Nonsymmetric Version of the Khinchine-Kahane Inequality\n                      , Progr. Probab. 56, Birkhauser, Boston, 2003.","DOI":"10.1007\/978-3-0348-8069-5_11"},{"key":"R22","unstructured":"G. Pisier,\n                      Remarques sur un r\u00e9sultat non publi\u00e9 de B. Maurey\n                      , 1980\u20131981."},{"key":"R23","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1024691352"},{"key":"R25","unstructured":"S. Shalev-Shwartz,\n                      Online Learning: Theory, Algorithms, and Applications\n                      , Ph.D. thesis, The Hebrew University, Jerusalem, 2007."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5173-z"},{"key":"R27","unstructured":"S. Shalev-Shwartz and N. Srebro,\n                      Low $\\ell_1$ norm and guarantees on sparsifiability\n                      , in Sparse Optimization and Variable Selection, Joint ICML\/COLT\/UAI Workshop, 2008."},{"key":"R28","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"Tibshirani R.","year":"1996","journal-title":"J. Roy. Statist. Soc B.","ISSN":"https:\/\/id.crossref.org\/issn\/0035-9246","issn-type":"print"},{"key":"R29","unstructured":"V. N. Vapnik,\n                      Statistical Learning Theory\n                      , Wiley, New York, 1998."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"M. Warmuth, K. Glocer, and S. V. N. Vishwanathan,\n                      Entropy regularized lpboost\n                      , in Proceedings of the Algorithmic Learning Theory (ALT) 19th International Conference, 2008.","DOI":"10.1007\/978-3-540-87987-9_23"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"M. Warmuth, J. Liao, and G. Ratsch,\n                      Totally corrective boosting algorithms that maximize the margin\n                      , in Proceedings of the 23rd International Conference on Machine Learning, 2006.","DOI":"10.1145\/1143844.1143970"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.808136"},{"key":"R33","unstructured":"T. Zhang,\n                      Adaptive forward-backward greedy algorithm for sparse learning with linear models\n                      , in Proceedings of the 22nd Annual Conference on Neural Information Processing Systems, 2008."},{"key":"R34","first-page":"2541","volume":"7","author":"Zhao P.","year":"2006","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090759574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:19:34Z","timestamp":1787332774000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090759574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090759574"],"URL":"https:\/\/doi.org\/10.1137\/090759574","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}