{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T14:56:01Z","timestamp":1782312961879,"version":"3.54.5"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,3,31]],"date-time":"2015-03-31T00:00:00Z","timestamp":1427760000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s10107-015-0894-1","type":"journal-article","created":{"date-parts":[[2015,3,30]],"date-time":"2015-03-30T06:22:27Z","timestamp":1427696547000},"page":"63-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":42,"title":["Sparse learning via Boolean relaxations"],"prefix":"10.1007","volume":"151","author":[{"given":"Mert","family":"Pilanci","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin J.","family":"Wainwright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laurent","family":"El Ghaoui","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,3,31]]},"reference":[{"issue":"3","key":"894_CR1","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1109\/18.985947","volume":"48","author":"R Ahlswede","year":"2002","unstructured":"Ahlswede, R., Winter, A.: Strong converse for identification via quantum channels. IEEE Trans. Inf. Theory 48(3), 569\u2013579 (2002)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"894_CR2","unstructured":"Akaike, H.: Information theory and an extension of the maximum likelihood principle. In: Proceedings of the 2nd international symposium on information theory, Tsahkadsor, Armenia, USSR (September 1971)"},{"issue":"4","key":"894_CR3","doi-asserted-by":"crossref","first-page":"1705","DOI":"10.1214\/08-AOS620","volume":"37","author":"PJ Bickel","year":"2009","unstructured":"Bickel, P.J., Ritov, Y., Tsybakov, A.: Simultaneous analysis of Lasso and Dantzig selector. Ann. Stat. 37(4), 1705\u20131732 (2009)","journal-title":"Ann. Stat."},{"key":"894_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, UK (2004)"},{"key":"894_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-20192-9","volume-title":"Statistics for High-Dimensional Data. Springer Series in Statistics","author":"P B\u00fchlmann","year":"2011","unstructured":"B\u00fchlmann, P., van de Geer, S.: Statistics for High-Dimensional Data. Springer Series in Statistics. Springer, Berlin (2011)"},{"issue":"12","key":"894_CR6","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"EJ Candes","year":"2005","unstructured":"Candes, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Info. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Info. Theory"},{"key":"894_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801389","volume-title":"An Introduction to Support Vector Machines (and Other Kernel Based Learning Methods)","author":"N Cristianini","year":"2000","unstructured":"Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines (and Other Kernel Based Learning Methods). Cambridge University Press, Cambridge (2000)"},{"key":"894_CR8","unstructured":"Inc. CVX Research. CVX: Matlab software for disciplined convex programming, version 2.0 (August 2012)"},{"key":"894_CR9","doi-asserted-by":"crossref","unstructured":"d\u2019Aspremont, A., El Ghaoui, L.: Testing the nullspace property using semidefinite programming. Technical report, Princeton (2009)","DOI":"10.1007\/s10107-010-0416-0"},{"key":"894_CR10","first-page":"317","volume-title":"Handbook of Banach Spaces","author":"KR Davidson","year":"2001","unstructured":"Davidson, K.R., Szarek, S.J.: Local operator theory, random matrices and Banach spaces. Handbook of Banach Spaces, vol. 1, pp. 317\u2013336. Elsevier, Amsterdam (2001)"},{"key":"894_CR11","first-page":"345","volume":"19","author":"O Dekel","year":"2007","unstructured":"Dekel, O., Singer, Y.: Support vector machines on a budget. Adv. Neural Inf. Process. Syst. 19, 345 (2007)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"4","key":"894_CR12","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compress. sensing. IEEE Trans. Info. Theory 52(4), 1289\u20131306 (2006)","journal-title":"Compress. sensing. IEEE Trans. Info. Theory"},{"issue":"1","key":"894_CR13","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1109\/TIT.2005.860430","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L., Elad, M., Temlyakov, V.M.: Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inf. Theory 52(1), 6\u201318 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"894_CR14","first-page":"533","volume":"2","author":"JJ Fuchs","year":"2004","unstructured":"Fuchs, J.J.: Recovery of exact sparse representations in the presence of noise. ICASSP 2, 533\u2013536 (2004)","journal-title":"ICASSP"},{"key":"894_CR15","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-1-84800-155-8_7","volume-title":"Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences","author":"M Grant","year":"2008","unstructured":"Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Blondel, V., Boyd, S., Kimura, H. (eds.) Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pp. 95\u2013110. Springer, Berlin (2008)"},{"key":"894_CR16","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0\u20131 programs. In: Aardal K., and Gerads A.M.H., (eds.) Lecture Notes in Computer Science, 2081:293\u2013303 (2001)"},{"key":"894_CR17","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver and Lasserre relaxations for 0\u20131 programming. Math. Oper. Res. 28, 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"key":"894_CR18","volume-title":"The Concentration of Measure Phenomenon","author":"M Ledoux","year":"2001","unstructured":"Ledoux, M.: The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI (2001)"},{"key":"894_CR19","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Optim. 1, 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"key":"894_CR20","volume-title":"Portf. Sel.","author":"HM Markowitz","year":"1959","unstructured":"Markowitz, H.M.: Portf. Sel. Wiley, New York (1959)"},{"key":"894_CR21","volume-title":"Generalized Linear Models. Monographs on Statistics and Applied Probability 37","author":"P McCullagh","year":"1989","unstructured":"McCullagh, P., Nelder, J.A.: Generalized Linear Models. Monographs on Statistics and Applied Probability 37. Chapman and Hall\/CRC, New York (1989)"},{"key":"894_CR22","doi-asserted-by":"crossref","first-page":"1436","DOI":"10.1214\/009053606000000281","volume":"34","author":"N Meinshausen","year":"2006","unstructured":"Meinshausen, N., B\u00fchlmann, P.: High-dimensional graphs and variable selection with the Lasso. Ann. Stat. 34, 1436\u20131462 (2006)","journal-title":"Ann. Stat."},{"key":"894_CR23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge, UK (1995)"},{"key":"894_CR24","unstructured":"Negahban, S., Ravikumar, P., Wainwright, M.J., Yu, B.: Restricted strong convexity and generalized linear models. Technical report, UC Berkeley, Department of Statistics (August 2011)"},{"key":"894_CR25","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.: Primal-dual subgradient methods for convex problems. Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (UCL) (2005)","DOI":"10.2139\/ssrn.912637"},{"key":"894_CR26","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1214\/ECP.v15-1544","volume":"15","author":"RI Oliveira","year":"2010","unstructured":"Oliveira, R.I.: Sums of random Hermitian matrices and an inequality by Rudelson. Elec. Comm. Prob. 15, 203\u2013212 (2010)","journal-title":"Elec. Comm. Prob."},{"key":"894_CR27","unstructured":"Pilanci, M., El Ghaoui, L., Chandrasekaran, V.: Recovery of sparse probability measures via convex programming. In: Pereira, F., Burges, C.J.C., Bottou, L., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems 25, pp. 2420\u20132428. Curran Associates, Inc. (2012)"},{"key":"894_CR28","unstructured":"Schmidt, M., van den Berg, E., Friedlander, M., Murphy, K.: Optimizing costly functions with simple constraints: A limited-memory projected quasi-newton algorithm. AISTATS 2009, 5 (2009)"},{"key":"894_CR29","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3, 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"894_CR30","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1996","unstructured":"Tibshirani, R.: Regression shrinkage and selection via the Lasso. J. R. Stat. Soc. Ser. B 58(1), 267\u2013288 (1996)","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"894_CR31","unstructured":"Tropp, J.A.: Just relax: Convex programming methods for subset selection and sparse approximation. ICES Report 04\u201304, UT-Austin, February (2004)"},{"key":"894_CR32","doi-asserted-by":"crossref","first-page":"5728","DOI":"10.1109\/TIT.2009.2032816","volume":"55","author":"MJ Wainwright","year":"2009","unstructured":"Wainwright, M.J.: Information-theoretic bounds on sparsity recovery in the high-dimensional and noisy setting. IEEE Trans. Info. Theory 55, 5728\u20135741 (2009)","journal-title":"IEEE Trans. Info. Theory"},{"key":"894_CR33","doi-asserted-by":"crossref","first-page":"2183","DOI":"10.1109\/TIT.2009.2016018","volume":"55","author":"MJ Wainwright","year":"2009","unstructured":"Wainwright, M.J.: Sharp thresholds for high-dimensional and noisy sparsity recovery using $$\\ell _1$$ \u2113 1 -constrained quadratic programming (Lasso). IEEE Trans. Inf. Theory 55, 2183\u20132202 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"894_CR34","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev-statistics-022513-115643","volume":"1","author":"MJ Wainwright","year":"2014","unstructured":"Wainwright, M.J.: Structured regularizers: statistical and computational issues. Annu. Rev. Stat. Appl. 1, 233\u2013253 (2014)","journal-title":"Annu. Rev. Stat. Appl."},{"key":"894_CR35","unstructured":"Wainwright, M.J., Jordan, M.I.: Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations. Technical report, UC Berkeley, Department of Statistics, No. 671 (September 2004)"},{"issue":"1","key":"894_CR36","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1006\/jmps.1999.1278","volume":"44","author":"Larry Wasserman","year":"2000","unstructured":"Wasserman, Larry: Bayesian model selection and model averaging. J. Math. Psychol. 44(1), 92\u2013107 (2000)","journal-title":"J. Math. Psychol."},{"key":"894_CR37","unstructured":"Zhang, Y., Wainwright, M.J., Jordan, M.I.: Lower bounds on the performance of polynomial-time algorithms for sparse linear regression. In COLT conference, Barcelona, Spain, (June 2014). Full length version at http:\/\/arxiv.org\/abs\/1402.1918"},{"key":"894_CR38","first-page":"2541","volume":"7","author":"P Zhao","year":"2006","unstructured":"Zhao, P., Yu, B.: On model selection consistency of Lasso. J. Mach. Learn. Res. 7, 2541\u20132567 (2006)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"894_CR39","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1111\/j.1467-9868.2005.00503.x","volume":"67","author":"H Zou","year":"2005","unstructured":"Zou, H., Hastie, T.J.: Regularization and variable selection via the elastic net. J. R. Stat. Soc. Ser. B 67(2), 301\u2013320 (2005)","journal-title":"J. R. Stat. Soc. Ser. B"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0894-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-015-0894-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-015-0894-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,8]],"date-time":"2024-06-08T03:04:12Z","timestamp":1717815852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-015-0894-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,31]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["894"],"URL":"https:\/\/doi.org\/10.1007\/s10107-015-0894-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,31]]}}}