{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,20]],"date-time":"2026-10-20T16:30:51Z","timestamp":1792513851608,"version":"4.5.0"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-11- 1-0688"],"award-info":[{"award-number":["N00014-11- 1-0688"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CIF-31712-23800"],"award-info":[{"award-number":["CIF-31712-23800"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1107000"],"award-info":[{"award-number":["DMS-1107000"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We propose a randomized second-order method for optimization known as the Newton sketch: it is based on performing an approximate Newton step using a randomly projected Hessian. For self-concordant functions, we prove that the algorithm has superlinear convergence with exponentially high probability, with convergence and complexity guarantees that are independent of condition numbers and related problem-dependent quantities. Given a suitable initialization, similar guarantees also hold for strongly convex and smooth objectives without self-concordance. When implemented using randomized projections based on a subsampled Hadamard basis, the algorithm typically has substantially lower complexity than Newton's method. We also describe extensions of our methods to programs involving convex constraints that are equipped with self-concordant barriers. We discuss and illustrate applications to linear programs, quadratic programs with convex constraints, logistic regression, and other generalized linear models, as well as semidefinite programs.<\/jats:p>","DOI":"10.1137\/15m1021106","type":"journal-article","created":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T10:22:12Z","timestamp":1487758932000},"page":"205-245","source":"Crossref","is-referenced-by-count":116,"title":["Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence"],"prefix":"10.1137","volume":"27","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"}]}],"member":"351","published-online":{"date-parts":[[2017,2,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"atypb2","first-page":"557","author":"Ailon N.","year":"2006","journal-title":"New York"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9110-x"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000282"},{"key":"atypb5","first-page":"1737","volume":"10","author":"Bordes A.","year":"2009","journal-title":"J. Mach. Learn. Res."},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/10079923X"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/140954362"},{"key":"atypb9","first-page":"341","author":"Dasgupta A.","year":"2010","journal-title":"New York"},{"key":"atypb10","first-page":"317","author":"Davidson K. R.","year":"2001","journal-title":"Amsterdam"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/0719025"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592055"},{"key":"atypb13","first-page":"3475","volume":"13","author":"Drineas P.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1214\/009053604000000067"},{"key":"atypb16","unstructured":"G. Golub and C. V. Loan,\n                      Matrix Computations\n                      , Johns Hopkins University Press, Baltimore, 1996."},{"key":"atypb17","unstructured":"T. Hastie and B. Efron,\n                      LARS: Least Angle Regression, Lasso and Forward Stagewise\n                      , R package version 0.9-7, 2007."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"T. Hastie, R. Tibshirani, and M. J. Wainwright,\n                      Statistical Learning with Sparsity: The Lasso and Generalizations\n                      , Boca Raton, FL, 2015.","DOI":"10.1201\/b18401"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/2559902"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2007.910971"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"M. Ledoux and M. Talagrand,\n                      Probability in Banach Spaces: Isoperimetry and Processes\n                      , Springer, New York, 1991.","DOI":"10.1007\/978-3-642-20212-4"},{"key":"atypb22","unstructured":"H. M. Markowitz,\n                      Portfolio Selection\n                      , Wiley, New York, 1959."},{"key":"atypb23","first-page":"735","author":"Martens J.","year":"2010","journal-title":"WI"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"P. McCullagh and J. Nelder,\n                      Generalized Linear Models\n                      , Monogr. Statist. Appl. Probab. 37, Chapman and Hall\/CRC, New York, 1989.","DOI":"10.1007\/978-1-4899-3242-6"},{"key":"atypb25","first-page":"117","author":"Nelson J.","year":"2013","journal-title":"NJ"},{"key":"atypb26","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Sov. Math. Dokl."},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization\n                      , Kluwer, New York, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovski,\n                      Interior-Point Polynomial Algorithms in Convex Programming\n                      , SIAM Stud. Appl. Math. 13, SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"atypb29","first-page":"319","volume":"2","author":"Osborne M. R.","journal-title":"J. Comput. Graph. Statist."},{"key":"atypb30","first-page":"1842","volume":"17","author":"Pilanci M.","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2450722"},{"key":"atypb32","first-page":"167","author":"Pisier G.","year":"1986","journal-title":"Berlin"},{"key":"atypb33","first-page":"436","volume":"2","author":"Schraudolph N. N.","year":"2007","journal-title":"J. Mach. Learn. Res. W&P"},{"key":"atypb34","unstructured":"K. Sjo\u0308strand,\n                      MATLAB implementation of lasso, lars, the elastic net and SPCA\n                      , Technical report, Informatics and Mathematical Modelling, Technical University of Denmark (DTU), Lyngby, 2005."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"atypb37","first-page":"210","author":"Vershynin R.","year":"2012","journal-title":"Cambridge"},{"key":"atypb38","unstructured":"S. Wright and J. Nocedal,\n                      Numerical Optimization\n                      , Vol. 2, Springer New York, 1999."},{"key":"atypb39","first-page":"239","author":"Yamashita N.","year":"2001","journal-title":"Vienna"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1021106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:28:32Z","timestamp":1787336912000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1021106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1021106"],"URL":"https:\/\/doi.org\/10.1137\/15m1021106","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}