{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,4]],"date-time":"2026-08-04T03:28:37Z","timestamp":1785814117398,"version":"3.56.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["10100521"],"award-info":[{"award-number":["10100521"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The problem of best subset selection in linear regression is considered with the aim to find a fixed size subset of features that best fits the response. This is particularly challenging when the total available number of features is very large compared to the number of data samples. Existing optimal methods for solving this problem tend to be slow while fast methods tend to have low accuracy. Ideally, new methods perform best subset selection faster than existing optimal methods but with comparable accuracy, or, being more accurate than methods of comparable computational speed. Here, we propose a novel continuous optimization method that identifies a subset solution path, a small set of models of varying size, that consists of candidates for the single best subset of features, that is optimal in a specific sense in linear regression. Our method turns out to be fast, making the best subset selection possible when the number of features is well in excess of thousands. Because of the outstanding overall performance, framing the best subset selection challenge as a continuous optimization problem opens new research directions for feature extraction for a large variety of regression models.<\/jats:p>","DOI":"10.1007\/s11222-024-10387-8","type":"journal-article","created":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T02:02:02Z","timestamp":1707703322000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["COMBSS: best subset selection via continuous optimization"],"prefix":"10.1007","volume":"34","author":[{"given":"Sarat","family":"Moka","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benoit","family":"Liquet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Houying","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel","family":"Muller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,2,12]]},"reference":[{"key":"10387_CR1","volume-title":"Basic topology. Undergraduate texts in mathematics","author":"MA Armstrong","year":"1983","unstructured":"Armstrong, M.A.: Basic topology. Undergraduate texts in mathematics. Springer, Berlin (1983)"},{"issue":"2","key":"10387_CR2","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1214\/15-AOS1388","volume":"44","author":"D Bertsimas","year":"2016","unstructured":"Bertsimas, D., King, A., Mazumder, R.: Best subset selection via a modern optimization lens. Ann. Stat. 44(2), 813\u2013852 (2016)","journal-title":"Ann. Stat."},{"key":"10387_CR3","first-page":"421","volume-title":"Stochastic Gradient Descent Tricks","author":"L Bottou","year":"2012","unstructured":"Bottou, L.: Stochastic Gradient Descent Tricks, pp. 421\u2013436. Springer, Berlin (2012)"},{"issue":"1","key":"10387_CR4","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1214\/10-AOAS388","volume":"5","author":"P Breheny","year":"2011","unstructured":"Breheny, P., Huang, J.: Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection. Ann. Appl. Stat. 5(1), 232\u2013253 (2011)","journal-title":"Ann. Appl. Stat."},{"key":"10387_CR5","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/j.laa.2015.01.003","volume":"471","author":"N Castro-Gonz\u00e1lez","year":"2015","unstructured":"Castro-Gonz\u00e1lez, N., Mart\u00ednez-Serrano, M., Robles, J.: Expressions for the Moore-Penrose inverse of block matrices involving the Schur complement. Linear Algebra Appl. 471, 353\u2013368 (2015)","journal-title":"Linear Algebra Appl."},{"key":"10387_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-031-00832-0_3","volume-title":"High-dimensional optimization and probability","author":"M Danilova","year":"2022","unstructured":"Danilova, M., Dvurechensky, P., Gasnikov, A., et al.: Recent theoretical advances in non-convex optimization. In: Nikeghbali, A., Pardalos, P.M., Raigorodskii, A.M., Rassias, M.T. (eds.) High-dimensional optimization and probability, pp. 79\u2013163. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-00832-0_3"},{"key":"10387_CR7","unstructured":"Efroymson, M.A.: Stepwise regression-a backward and forward look. Presented at the Eastern Regional Meetings of of the Institute of Mathematical Statistics, Florham Park, New Jersey (1966)"},{"key":"10387_CR8","doi-asserted-by":"crossref","unstructured":"Fan, J., Li, R.: Statistical challenges with high dimensionality: feature selection in knowledge discovery. In: International Congress of Mathematicians, vol. III, pp. 595\u2013622. Eur. Math. Soc, Z\u00fcrich (2006)","DOI":"10.4171\/022-3\/31"},{"issue":"1","key":"10387_CR9","first-page":"101","volume":"20","author":"J Fan","year":"2010","unstructured":"Fan, J., Lv, J.: A selective overview of variable selection in high dimensional feature space. Stat. Sin. 20(1), 101\u2013148 (2010)","journal-title":"Stat. Sin."},{"issue":"544","key":"10387_CR10","first-page":"1","volume":"118","author":"J Fan","year":"2022","unstructured":"Fan, J., Yang, Z., Yu, M.: Understanding implicit regularization in over-parameterized single index model. J. Am. Stat. Assoc. 118(544), 1\u201337 (2022)","journal-title":"J. Am. Stat. Assoc."},{"key":"10387_CR11","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1080\/00401706.2000.10485982","volume":"42","author":"GM Furnival","year":"2000","unstructured":"Furnival, G.M., Wilson, R.W.: Regressions by leaps and bounds. Technometrics 42, 69\u201379 (2000)","journal-title":"Technometrics"},{"key":"10387_CR12","unstructured":"Golub, G.H., Van\u00a0Loan, C.F.: Matrix computations, 3rd edn. Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore (1996)"},{"key":"10387_CR13","unstructured":"Gurobi Optimization, limited liability company: Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com (2022)"},{"key":"10387_CR14","unstructured":"Hastie, T., Tibshirani, R., Tibshirani, R.: Bestsubset: tools for best subset selection in regression. R package version 1, 10 (2018)"},{"issue":"4","key":"10387_CR15","first-page":"579","volume":"35","author":"T Hastie","year":"2020","unstructured":"Hastie, T., Tibshirani, R., Tibshirani, R.: Best subset, forward stepwise or lasso? Analysis and recommendations based on extensive comparisons. Stat. Sci. 35(4), 579\u2013592 (2020)","journal-title":"Stat. Sci."},{"issue":"5","key":"10387_CR16","doi-asserted-by":"publisher","first-page":"1517","DOI":"10.1287\/opre.2019.1919","volume":"68","author":"H Hazimeh","year":"2020","unstructured":"Hazimeh, H., Mazumder, R.: Fast best subset selection: coordinate descent and local combinatorial optimization algorithms. Oper. Res. 68(5), 1517\u20131537 (2020)","journal-title":"Oper. Res."},{"key":"10387_CR17","unstructured":"Hazimeh, H., Mazumder, R., Nonet, T.: L0Learn: fast algorithms for best subset selection. R package version 2.1.0 (2023)"},{"key":"10387_CR18","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1080\/00401706.1967.10490502","volume":"9","author":"RR Hocking","year":"1967","unstructured":"Hocking, R.R., Leslie, R.N.: Selection of the best subset in regression analysis. Technometrics 9, 531\u2013540 (1967)","journal-title":"Technometrics"},{"key":"10387_CR19","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.csda.2017.06.007","volume":"115","author":"PD Hoff","year":"2017","unstructured":"Hoff, P.D.: Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization. Comput. Stat. Data Anal. 115, 186\u2013198 (2017)","journal-title":"Comput. Stat. Data Anal."},{"issue":"519","key":"10387_CR20","doi-asserted-by":"publisher","first-page":"1323","DOI":"10.1080\/01621459.2016.1215989","volume":"112","author":"FK Hui","year":"2017","unstructured":"Hui, F.K., M\u00fcller, S., Welsh, A.: Joint selection in mixed models using regularized PQL. J. Am. Stat. Assoc. 112(519), 1323\u20131333 (2017)","journal-title":"J. Am. Stat. Assoc."},{"key":"10387_CR21","volume-title":"Algorithms for optimization","author":"MJ Kochenderfer","year":"2019","unstructured":"Kochenderfer, M.J., Wheeler, T.A.: Algorithms for optimization. Massachusetts Institute of Technology Press, Cambridge (2019)"},{"issue":"1","key":"10387_CR22","first-page":"4661","volume":"23","author":"DR Kowal","year":"2022","unstructured":"Kowal, D.R.: Bayesian subset selection and variable importance for interpretable prediction and classification. J. Mach. Learn. Res. 23(1), 4661\u20134698 (2022)","journal-title":"J. Mach. Learn. Res."},{"key":"10387_CR23","doi-asserted-by":"crossref","unstructured":"Mathur, A., Moka, S., Botev, Z.: Column subset selection and Nystr\u00f6m approximation via continuous optimization. arXiv preprint https:\/\/arxiv.org\/abs\/2304.09678 (2023)","DOI":"10.1109\/WSC60868.2023.10407416"},{"key":"10387_CR24","volume-title":"Subset selection in regression, monographs on statistics and applied probability","author":"A Miller","year":"2019","unstructured":"Miller, A.: Subset selection in regression, monographs on statistics and applied probability, vol. 95. Chapman & Hall\/CRC, Boca Raton (2019)"},{"issue":"2","key":"10387_CR25","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1111\/j.1751-5823.2010.00108.x","volume":"78","author":"S M\u00fcller","year":"2010","unstructured":"M\u00fcller, S., Welsh, A.H.: On model selection curves. Int. Stat. Rev. 78(2), 240\u2013256 (2010)","journal-title":"Int. Stat. Rev."},{"issue":"2","key":"10387_CR26","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/S0097539792240406","volume":"24","author":"BK Natarajan","year":"1995","unstructured":"Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2), 227\u2013234 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10387_CR27","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/s00041-008-9030-4","volume":"15","author":"T Strohmer","year":"2009","unstructured":"Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15(2), 262\u2013278 (2009)","journal-title":"J. Fourier Anal. Appl."},{"key":"10387_CR28","doi-asserted-by":"publisher","DOI":"10.1201\/9781003089018","volume-title":"Handbook of Bayesian Variable Selection","author":"MG Tadesse","year":"2021","unstructured":"Tadesse, M.G., Vannucci, M.: Handbook of Bayesian Variable Selection. Chapman & Hall, Boca Raton (2021)"},{"issue":"9","key":"10387_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v083.i09","volume":"83","author":"G Tarr","year":"2018","unstructured":"Tarr, G., Muller, S., Welsh, A.H.: MPLOT: an R package for graphical model stability and variable selection procedures. J. Stat. Softw. 83(9), 1\u201328 (2018)","journal-title":"J. Stat. Softw."},{"key":"10387_CR30","doi-asserted-by":"publisher","first-page":"405","DOI":"10.13001\/1081-3810.1171","volume":"13","author":"Y Tian","year":"2005","unstructured":"Tian, Y., Takane, Y.: Schur complements and Banachiewicz-Schur forms. Electron. J. Linear Algebra 13, 405\u2013418 (2005)","journal-title":"Electron. J. Linear Algebra"},{"issue":"1","key":"10387_CR31","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. Roy. Stat. Soc. B 58(1), 267\u2013288 (1996)","journal-title":"J. Roy. Stat. Soc. B"},{"key":"10387_CR32","unstructured":"Vaskevicius, T., Kanade, V., Rebeschini, P.: Implicit regularization for optimal sparse recovery. Adv. Neural Inf. Proc. Syst. 32 (2019)"},{"key":"10387_CR33","volume-title":"Inverting modified matrices","author":"MA Woodbury","year":"1950","unstructured":"Woodbury, M.A.: Inverting modified matrices, vol. 42. Princeton University, Princeton (1950)"},{"key":"10387_CR34","unstructured":"Zhao, P., Yang, Y., He, Q.C.: Implicit regularization via Hadamard product over-parametrization in high-dimensional linear regression. arXiv preprint arXiv:1903.09367 2(4):8 (2019)"},{"issue":"4","key":"10387_CR35","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1093\/biomet\/asac010","volume":"109","author":"P Zhao","year":"2022","unstructured":"Zhao, P., Yang, Y., He, Q.C.: High-dimensional linear regression via implicit regularization. Biometrika 109(4), 1033\u20131046 (2022)","journal-title":"Biometrika"},{"key":"10387_CR36","doi-asserted-by":"crossref","unstructured":"Zhu, J., Wen, C., Zhu, J., et\u00a0al.: A polynomial algorithm for best-subset selection problem. In: Proceedings of the National Academy of Sciences of the United States of America 117(52), 33117\u201333123 (2020)","DOI":"10.1073\/pnas.2014241117"}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-024-10387-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11222-024-10387-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-024-10387-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,10]],"date-time":"2024-11-10T20:52:09Z","timestamp":1731271929000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11222-024-10387-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,12]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10387"],"URL":"https:\/\/doi.org\/10.1007\/s11222-024-10387-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3077764\/v1","asserted-by":"object"}]},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"value":"0960-3174","type":"print"},{"value":"1573-1375","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,12]]},"assertion":[{"value":"18 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"75"}}