{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:52:32Z","timestamp":1791323552693,"version":"4.3.1"},"reference-count":42,"publisher":"Institute of Mathematical Statistics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2026,6,1]]},"abstract":"We consider the sparse principal component analysis (SPCA) problem under the well-known spiked covariance model. Recent work has shown that the SPCA problem can be reformulated as a mixed integer program (MIP) and can be solved to global optimality, leading to estimators that are known to enjoy optimal statistical properties. However, prior MIP algorithms for SPCA appear to be limited in terms of scalability to up to a thousand features or so. In this paper we propose a new estimator for SPCA which can be formulated as a MIP. Different from earlier work, we make use of the underlying spiked covariance model and properties of the multivariate Gaussian distribution to arrive at our estimator. We establish statistical guarantees for our proposed estimator in terms of estimation error and support recovery. We derive guarantees under departures from the spiked covariance model and for approximate solutions to the optimization problem. We propose a custom algorithm to solve the MIP, which scales better than off-the-shelf solvers, and demonstrate that our approach can be much more computationally attractive compared to earlier exact MIP-based approaches for the SPCA problem. Our numerical experiments on synthetic and real datasets show that our algorithms can address problems with up to 20,000 features in minutes; and generally result in favorable statistical properties compared to existing popular approaches for SPCA.<\/jats:p>","DOI":"10.1214\/25-aos2551","type":"journal-article","created":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T13:49:36Z","timestamp":1782395376000},"page":"1101-1127","source":"Crossref","is-referenced-by-count":1,"title":["Sparse PCA: A new scalable estimator based on integer programming"],"prefix":"10.1214","volume":"54","author":[{"given":"Kayhan","family":"Behdin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Mazumder","sequence":"additional","affiliation":[{"name":"Sloan School of Management, Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"2","doi-asserted-by":"crossref","unstructured":"AMINI, A. A.<\/small> and WAINWRIGHT, M. J.<\/small> (2009). High-dimensional analysis of semidefinite relaxations for sparse principal components. Ann. Statist.<\/i> 37<\/b> 2877\u20132921.","DOI":"10.1214\/08-AOS664"},{"key":"38","doi-asserted-by":"publisher","unstructured":"WANG, T.<\/small>, BERTHET, Q.<\/small> and SAMWORTH, R. J.<\/small> (2016). Statistical and computational trade-offs in estimation of sparse principal components. Ann. Statist.<\/i> 44<\/b> 1896\u20131930.","DOI":"10.1214\/15-AOS1369"},{"key":"9","doi-asserted-by":"publisher","unstructured":"BERTSIMAS, D.<\/small> and VAN PARYS, B.<\/small> (2020). Sparse high-dimensional regression: Exact scalable algorithms and phase transitions. Ann. Statist.<\/i> 48<\/b> 300\u2013323.","DOI":"10.1214\/18-AOS1804"},{"key":"42","doi-asserted-by":"publisher","unstructured":"ZOU, H.<\/small>, HASTIE, T.<\/small> and TIBSHIRANI, R.<\/small> (2006). Sparse principal component analysis. J. Comput. Graph. Statist.<\/i> 15<\/b> 265\u2013286.","DOI":"10.1198\/106186006X113430"},{"key":"18","doi-asserted-by":"publisher","unstructured":"FRANGIONI, A.<\/small> and GENTILE, C.<\/small> (2006). Perspective cuts for a class of convex 0-1 mixed integer programs. Math. Program.<\/i> 106<\/b> 225\u2013236.","DOI":"10.1007\/s10107-005-0594-3"},{"key":"20","doi-asserted-by":"publisher","unstructured":"G\u00dcNL\u00dcK, O.<\/small> and LINDEROTH, J.<\/small> (2010). Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program.<\/i> 124<\/b> 183\u2013205.","DOI":"10.1007\/s10107-010-0360-z"},{"key":"23","doi-asserted-by":"crossref","unstructured":"HAZIMEH, H.<\/small> and MAZUMDER, R.<\/small> (2020). Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms. Oper. Res.<\/i> 68<\/b> 1517\u20131537.","DOI":"10.1287\/opre.2019.1919"},{"key":"24","doi-asserted-by":"publisher","unstructured":"HAZIMEH, H.<\/small>, MAZUMDER, R.<\/small> and SAAB, A.<\/small> (2022). Sparse regression at scale: Branch-and-bound rooted in first-order optimization. Math. Program.<\/i> 196<\/b> 347\u2013388.","DOI":"10.1007\/s10107-021-01712-4"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Meinshausen, N.<\/small> and B\u00fchlmann, P.<\/small> (2006). High-dimensional graphs and variable selection with the lasso. Ann. Statist.<\/i> 34<\/b> 1436\u20131462.","DOI":"10.1214\/009053606000000281"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Bertsimas, D.<\/small>, King, A.<\/small> and Mazumder, R.<\/small> (2016). Best subset selection via a modern optimization lens. Ann. Statist.<\/i> 44<\/b> 813\u2013852.","DOI":"10.1214\/15-AOS1388"},{"key":"25","doi-asserted-by":"crossref","unstructured":"Hotelling, H.<\/small> (1933). Analysis of a complex of statistical variables into principal components. J. Educ. Psychol.<\/i> 24<\/b> 417.","DOI":"10.1037\/h0071325"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Johnstone, I. M.<\/small> and Lu, A. Y.<\/small> (2009). On consistency and sparsity for principal components analysis in high dimensions. J. Amer. Statist. Assoc.<\/i> 104<\/b> 682\u2013693.","DOI":"10.1198\/jasa.2009.0121"},{"key":"35","unstructured":"Paul, D.<\/small> (2007). Asymptotics of sample eigenstructure for a large dimensional spiked covariance model. Statist. Sinica<\/i> 17<\/b> 1617\u20131642."},{"key":"37","unstructured":"Stewart, G. W.<\/small> and Sun, J. G.<\/small> (1990). Matrix Perturbation Theory<\/i>. Computer Science and Scientific Computing<\/i>. Academic Press, Boston, MA."},{"key":"39","doi-asserted-by":"publisher","unstructured":"Wedin, P.<\/small> (1972). Perturbation bounds in connection with singular value decomposition. BIT<\/i> 12<\/b> 99\u2013111.","DOI":"10.1007\/bf01932678"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Berthet, Q.<\/small> and Rigollet, P.<\/small> (2013). Optimal detection of sparse principal components in high dimension. Ann. Statist.<\/i> 41<\/b> 1780\u20131815.","DOI":"10.1214\/13-AOS1127"},{"key":"22","unstructured":"Hastie, T.<\/small>, Tibshirani, R.<\/small> and Wainwright, M.<\/small> (2015). Statistical Learning with Sparsity<\/i>: The Lasso and Generalizations<\/i>. Monographs on Statistics and Applied Probability<\/i> 143<\/b>. CRC Press, Boca Raton, FL."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Cai, T. T.<\/small> and Zhou, H. H.<\/small> (2012). Optimal rates of convergence for sparse covariance matrix estimation. Ann. Statist.<\/i> 40<\/b> 2389\u20132420.","DOI":"10.1214\/12-AOS998"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Johnstone, I. M.<\/small> (2001). On the distribution of the largest eigenvalue in principal components analysis. Ann. Statist.<\/i> 29<\/b> 295\u2013327.","DOI":"10.1214\/aos\/1009210544"},{"key":"41","unstructured":"YUAN, X.-T.<\/small> and ZHANG, T.<\/small> (2013). Truncated power method for sparse eigenvalue problems. J. Mach. Learn. Res.<\/i> 14<\/b> 899\u2013925."},{"key":"30","doi-asserted-by":"publisher","unstructured":"LEI, J.<\/small> and VU, V. Q.<\/small> (2015). Sparsistency and agnostic inference in sparse PCA. Ann. Statist.<\/i> 43<\/b> 299\u2013322.","DOI":"10.1214\/14-AOS1273"},{"key":"14","doi-asserted-by":"publisher","unstructured":"D\u2019ASPREMONT, A.<\/small>, EL GHAOUI, L.<\/small>, JORDAN, M. I.<\/small> and LANCKRIET, G. R. G.<\/small> (2007). A direct formulation for sparse PCA using semidefinite programming. SIAM Rev.<\/i> 49<\/b> 434\u2013448.","DOI":"10.1137\/050645506"},{"key":"1","doi-asserted-by":"publisher","unstructured":"AKT\u00dcRK, M. S.<\/small>, ATAMT\u00dcRK, A.<\/small> and G\u00dcREL, S.<\/small> (2009). A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett.<\/i> 37<\/b> 187\u2013191.","DOI":"10.1016\/j.orl.2008.12.009"},{"key":"3","unstructured":"BEHDIN, K.<\/small> and MAZUMDER, R.<\/small> (2024). Sparse NMF with archetypal regularization: Computational and robustness properties. J. Mach. Learn. Res.<\/i> 25<\/b> Paper No. [36], 62."},{"key":"4","doi-asserted-by":"crossref","unstructured":"BEHDIN, K.<\/small> and MAZUMDER, R.<\/small> (2026). Supplement to \u201cSparse PCA: A new scalable estimator based on integer programming.\u201d https:\/\/doi.org\/10.1214\/25-AOS2551SUPP<\/a>","DOI":"10.1214\/25-AOS2551SUPP"},{"key":"5","doi-asserted-by":"publisher","unstructured":"BERK, L.<\/small> and BERTSIMAS, D.<\/small> (2019). Certifiably optimal sparse principal component analysis. Math. Program. Comput.<\/i> 11<\/b> 381\u2013420.","DOI":"10.1007\/s12532-018-0153-6"},{"key":"7","unstructured":"BERTSIMAS, D.<\/small>, CORY-WRIGHT, R.<\/small> and PAUPHILET, J.<\/small> (2022). Solving large-scale sparse PCA to certifiable (near) optimality. J. Mach. Learn. Res.<\/i> 23<\/b> Paper No. [13], 35."},{"key":"10","unstructured":"BRESLER, G.<\/small>, PARK, S. M.<\/small> and PERSU, M.<\/small> (2018). Sparse PCA from sparse linear regression. In Proceedings of the<\/i> 32nd International Conference on Neural Information Processing Systems. NIPS\u2019<\/i>18 10965\u201310975. Curran Associates, Red, Hook, NY, USA."},{"key":"12","doi-asserted-by":"publisher","unstructured":"CORNU\u00c9JOLS, G.<\/small> (2008). Valid inequalities for mixed integer linear programs. Math. Program.<\/i> 112<\/b> 3\u201344.","DOI":"10.1007\/s10107-006-0086-0"},{"key":"13","unstructured":"D\u2019ASPREMONT, A.<\/small>, BACH, F.<\/small> and EL GHAOUI, L.<\/small> (2008). Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res.<\/i> 9<\/b> 1269\u20131294."},{"key":"15","unstructured":"DESHPANDE, Y.<\/small> and MONTANARI, A.<\/small> (2016). Sparse PCA via covariance thresholding. J. Mach. Learn. Res.<\/i> 17<\/b> Paper No. 141, 41."},{"key":"16","unstructured":"DEY, S. S.<\/small>, MAZUMDER, R.<\/small> and WANG, G.<\/small> (2018). A convex integer programming approach for optimal sparse PCA. Preprint. Available at arXiv:1810.09062<\/a>."},{"key":"17","doi-asserted-by":"publisher","unstructured":"DURAN, M. A.<\/small> and GROSSMANN, I. E.<\/small> (1986). An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program.<\/i> 36<\/b> 307\u2013339.","DOI":"10.1007\/BF02592064"},{"key":"19","doi-asserted-by":"publisher","unstructured":"GATARIC, M.<\/small>, WANG, T.<\/small> and SAMWORTH, R. J.<\/small> (2020). Sparse principal component analysis via axis-aligned random projections. J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> 82<\/b> 329\u2013359.","DOI":"10.1111\/rssb.12360"},{"key":"21","unstructured":"GUYON, I.<\/small>, GUNN, S.<\/small>, BEN-HUR, A.<\/small> and DROR, G.<\/small> (2005). Result analysis of the NIPS 2003 feature selection challenge. In Advances in Neural Information Processing Systems<\/i> 17<\/b>. MIT Press, Cambridge."},{"key":"28","doi-asserted-by":"publisher","unstructured":"JOLLIFFE, I. T.<\/small>, TRENDAFILOV, N. T.<\/small> and UDDIN, M.<\/small> (2003). A modified principal component technique based on the LASSO. J. Comput. Graph. Statist.<\/i> 12<\/b> 531\u2013547.","DOI":"10.1198\/1061860032148"},{"key":"29","doi-asserted-by":"publisher","unstructured":"KRAUTHGAMER, R.<\/small>, NADLER, B.<\/small> and VILENCHIK, D.<\/small> (2015). Do semidefinite relaxations solve sparse PCA up to the information limit? Ann. Statist.<\/i> 43<\/b> 1300\u20131322.","DOI":"10.1214\/15-AOS1310"},{"key":"31","doi-asserted-by":"crossref","unstructured":"LI, Y.<\/small> and XIE, W.<\/small> (2025). Exact and approximation algorithms for sparse principal component analysis. INFORMS J. Comput.<\/i> 37<\/b> 582\u2013602.","DOI":"10.1287\/ijoc.2022.0372"},{"key":"32","doi-asserted-by":"publisher","unstructured":"LUSS, R.<\/small> and TEBOULLE, M.<\/small> (2013). Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint. SIAM Rev.<\/i> 55<\/b> 65\u201398.","DOI":"10.1137\/110839072"},{"key":"34","unstructured":"MOGHADDAM, B.<\/small>, WEISS, Y.<\/small> and AVIDAN, S.<\/small> (2006). Spectral bounds for sparse PCA: Exact and greedy algorithms. In Advances in Neural Information Processing Systems<\/i> 915\u2013922."},{"key":"36","doi-asserted-by":"publisher","unstructured":"RICHT\u00c1RIK, P.<\/small>, JAHANI, M.<\/small>, AHIPA\u015eAO\u011eLU, S. D.<\/small> and TAK\u00c1\u010c, M.<\/small> (2021). Alternating maximization: Unifying framework for 8 sparse PCA formulations and efficient parallel codes. Optim. Eng.<\/i> 22<\/b> 1493\u20131519.","DOI":"10.1007\/s11081-020-09562-3"},{"key":"40","doi-asserted-by":"crossref","unstructured":"WITTEN, D. M.<\/small>, TIBSHIRANI, R.<\/small>, and HASTIE, T.<\/small>, (2009). A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics<\/i> 10<\/b> 515\u2013534.","DOI":"10.1093\/biostatistics\/kxp008"}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:19:11Z","timestamp":1791321551000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-54\/issue-3\/Sparse-PCA--A-new-scalable-estimator-based-on-integer\/10.1214\/25-AOS2551.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,1]]},"references-count":42,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2026,6,1]]}},"URL":"https:\/\/doi.org\/10.1214\/25-aos2551","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,1]]}}}