{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:36Z","timestamp":1787340576795,"version":"build-2736575974"},"reference-count":61,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the $L_{0}$ norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to that of the convex integer formulation proposed in recent work. We also show that the convex hull of the constraint system of the MISOC formulation is equal to its continuous relaxation. Based upon these two formulations (i.e., the MISOC formulation and convex integer formulation), we analyze two scalable algorithms, the greedy and randomized algorithms, for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. We further propose integrating the greedy algorithm with the randomized algorithm, which can greedily search the features from the nonzero subset identified by the continuous relaxation of the MISOC formulation. The merits of the proposed methods are illustrated through numerical examples in comparison with several existing ones.<\/jats:p>","DOI":"10.1137\/19m1245414","type":"journal-article","created":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T14:36:30Z","timestamp":1608215790000},"page":"3359-3386","source":"Crossref","is-referenced-by-count":33,"title":["Scalable Algorithms for the Sparse Ridge Regression"],"prefix":"10.1137","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5157-1194","authenticated-orcid":true,"given":"Weijun","family":"Xie","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1560-2405","authenticated-orcid":true,"given":"Xinwei","family":"Deng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,12,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1029-z"},{"key":"atypb2","unstructured":"A. Atamturk and A. Gomez,\n                      Rank-One Convexification for Sparse Regression\n                      , preprint,https:\/\/arxiv.org\/abs\/1901.10334, 2019."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal and A. Nemirovski,\n                      Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications\n                      , MOS-SIAM Ser. Optim. 2, SIAM, 2001,https:\/\/doi.org\/10.1137\/1.9780898718829.","DOI":"10.1137\/1.9780898718829"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1388"},{"key":"atypb5","unstructured":"D. Bertsimas and B. Van Parys,\n                      Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions\n                      , preprint,https:\/\/arxiv.org\/abs\/1709.10029, 2017."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592208"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1017\/jpr.2019.49"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"P. B\u00fchlmann and S. Van De Geer,\n                      Statistics for High-Dimensional Data: Methods, Theory and Applications\n                      , Springer Ser. Statist., Springer-Verlag, 2011.","DOI":"10.1007\/978-3-642-20192-9"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2011.tm10155"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1214\/009053606000001523"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2008.03.014"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050106"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"atypb14","first-page":"45","author":"Das A.","year":"2008","journal-title":"ACM"},{"key":"atypb15","unstructured":"A. Das and D. Kempe,\n                      Submodular Meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection\n                      , preprint,https:\/\/arxiv.org\/abs\/1102.3975, 2011."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2009.01.002"},{"key":"atypb17","unstructured":"H. Dong,\n                      On the Exact Recovery of Sparse Signals via Conic Relaxations\n                      , preprint,https:\/\/arxiv.org\/abs\/1603.04572, 2016."},{"key":"atypb18","unstructured":"H. Dong, K. Chen, and J. Linderoth,\n                      Regularization vs. Relaxation: A Conic Optimization Perspective of Statistical Variable Selection\n                      , preprint,https:\/\/arxiv.org\/abs\/1510.06083, 2015."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1979.10489815"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2158486"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0594-3"},{"key":"atypb22","unstructured":"J. N. Franklin,\n                      Matrix Theory\n                      , Courier Corporation, 1968."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijforecast.2012.05.001"},{"key":"atypb24","unstructured":"R. Gao, X. Chen, and A. J. Kleywegt,\n                      Wasserstein Distributional Robustness and Regularization in Statistical Learning\n                      , preprint,https:\/\/arxiv.org\/abs\/1712.06050v1, 2017."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176348380"},{"key":"atypb26","first-page":"61","volume":"154","author":"G\u00fcnl\u00fck O.","year":"2012","journal-title":"IMA"},{"key":"atypb27","first-page":"485","author":"Hastie T.","year":"2009","journal-title":"Springer"},{"key":"atypb28","unstructured":"T. Hastie, R. Tibshirani, and R. J. Tibshirani,\n                      Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso\n                      , preprint,https:\/\/arxiv.org\/abs\/1707.08692, 2017."},{"key":"atypb29","unstructured":"H. Hazimeh and R. Mazumder,\n                      Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms\n                      , preprint,https:\/\/arxiv.org\/abs\/1803.01454, 2018."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1214\/009053607000000875"},{"key":"atypb31","unstructured":"R. Khanna, E. Elenberg, A. G. Dimakis, S. Negahban, and J. Ghosh,\n                      Scalable Greedy Feature Selection via Weak Submodularity\n                      , preprint,https:\/\/arxiv.org\/abs\/1703.02723, 2017."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2009.05.006"},{"key":"atypb33","first-page":"65","volume":"60","author":"Kuo L.","year":"1998","journal-title":"Sankhy\u0101 Ser. B"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0684-6"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2018.1448828"},{"key":"atypb36","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/00031305.1975.10479105","volume":"29","author":"Marquardt D. W.","year":"1975","journal-title":"Amer. Statist."},{"key":"atypb37","first-page":"3053","volume":"63","author":"Mazumder R.","year":"2017","journal-title":"IEEE Trans. Inform. Theory"},{"key":"atypb38","unstructured":"R. Mazumder, P. Radchenko, and A. Dedieu,\n                      Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low\n                      , preprint,https:\/\/arxiv.org\/abs\/1708.03288, 2017."},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"A. Miller,\n                      Subset Selection in Regression\n                      , CRC Press, 2002.","DOI":"10.1201\/9781420035933"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.06.081"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2014.07.056"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240406"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/050622328"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1057\/s41274-017-0197-4"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0894-1"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2013.0582"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1339"},{"key":"atypb48","unstructured":"M. Seeger, C. Williams, and N. Lawrence,\n                      Fast Forward Selection to Speed Up Sparse Gaussian Process Regression\n                      , Technical report, University of Edinburgh, 2003."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729893"},{"key":"atypb50","unstructured":"A. J. Smola and P. L. Bartlett,\n                      Sparse greedy Gaussian process regression\n                      , in Advances in Neural Information Processing Systems 13, MIT Press, 2001, pp. 619-625."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2014.0595"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"atypb54","unstructured":"W. N. van Wieringen,\n                      Lecture Notes on Ridge Regression\n                      , preprint,https:\/\/arxiv.org\/abs\/1509.09169, 2015."},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.2307\/1924340"},{"key":"atypb56","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1093\/genetics\/153.2.773","volume":"153","author":"Weber K.","year":"1999","journal-title":"Genetics"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456804"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOS580"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS729"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2146690"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2005.00503.x"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1245414","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:09Z","timestamp":1787337609000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1245414"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M1245414"],"URL":"https:\/\/doi.org\/10.1137\/19m1245414","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}