{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T11:52:09Z","timestamp":1776081129144,"version":"3.50.1"},"reference-count":84,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"5","license":[{"start":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T00:00:00Z","timestamp":1651363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T00:00:00Z","timestamp":1651363200000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T00:00:00Z","timestamp":1651363200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T00:00:00Z","timestamp":1651363200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1838179"],"award-info":[{"award-number":["IIS-1838179"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ECCS-2037304"],"award-info":[{"award-number":["ECCS-2037304"]}],"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-2134248"],"award-info":[{"award-number":["DMS-2134248"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1109\/tit.2022.3146206","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T20:55:58Z","timestamp":1643057758000},"page":"3281-3303","source":"Crossref","is-referenced-by-count":5,"title":["Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds"],"prefix":"10.1109","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2041-9311","authenticated-orcid":false,"given":"Jonathan","family":"Lacotte","sequence":"first","affiliation":[{"name":"Electrical Engineering Department, Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0870-9992","authenticated-orcid":false,"given":"Mert","family":"Pilanci","sequence":"additional","affiliation":[{"name":"Electrical Engineering Department, Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref1","first-page":"10847","article-title":"High-dimensional optimization in adaptive random subspaces","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"32","author":"Lacotte"},{"key":"ref2","first-page":"1177","article-title":"Random features for large-scale kernel machines","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"2008","author":"Rahimi"},{"key":"ref3","first-page":"3320","article-title":"How transferable are features in deep neural networks?","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Yosinski"},{"key":"ref4","first-page":"1","article-title":"When do neural networks outperform kernel methods?","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"33","author":"Ghorbani"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1561\/2400000003"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1311-3"},{"key":"ref7","first-page":"7695","article-title":"Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks","volume-title":"Proc. ICML","author":"Pilanci"},{"key":"ref8","article-title":"Implicit convex regularizers of CNN architectures: Convex optimization of two- and three-layer networks in polynomial time","volume-title":"Proc. Int. Conf. Learn. Represent.","author":"Ergen"},{"key":"ref9","first-page":"4024","article-title":"Convex geometry of two-layer ReLU networks: Implicit autoencoding and interpretable models","volume-title":"Proc. Int. Conf. Artif. Intell. Statist.","author":"Ergen"},{"key":"ref10","first-page":"3004","article-title":"Revealing the structure of deep neural networks via convex duality","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Ergen"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/065"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/2842602"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/090767911"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/120866580"},{"key":"ref16","article-title":"Fast randomized algorithms for convex optimization and statistical estimation","author":"Pilanci","year":"2016"},{"issue":"1","key":"ref17","first-page":"1842","article-title":"Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares","volume":"17","author":"Pilanci","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref18","article-title":"Faster least squares optimization","volume-title":"arXiv:1911.02675","author":"Lacotte","year":"2019"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2019.8682720"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/15M1021106"},{"key":"ref21","article-title":"Distributed sketching methods for privacy preserving regression","volume-title":"arXiv:2002.06538","author":"Bartan","year":"2020"},{"key":"ref22","article-title":"Distributed averaging methods for randomized second order optimization","volume-title":"arXiv:2002.06540","author":"Bartan","year":"2020"},{"key":"ref23","first-page":"6684","article-title":"Debiasing distributed second order optimization with surrogate sketching and scaled regularization","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"33","author":"Derezinski"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"ref25","first-page":"1823","article-title":"SDNA: Stochastic dual Newton ascent for empirical risk minimization","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Qu"},{"key":"ref26","first-page":"1290","article-title":"Randomized block cubic Newton method","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Doikov"},{"key":"ref27","first-page":"902","article-title":"Efficient second order online learning by sketching","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Luo"},{"key":"ref28","first-page":"616","article-title":"RSN: Randomized subspace Newton","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Gower"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"ref31","first-page":"135","article-title":"Recovering the optimal solution by dual random projection","volume-title":"Proc. Conf. Learn. Theory","author":"Zhang"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2359204"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10845"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1214\/17-EJS1334SI"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2450722"},{"key":"ref36","first-page":"305","article-title":"Theory of dual-sparse regularized randomized reduction","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Yang"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/417"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/11752790_3"},{"key":"ref39","first-page":"643","article-title":"Is margin preserved after random projection?","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Shi"},{"key":"ref40","first-page":"498","article-title":"Random projections for support vector machines","volume-title":"Proc. Int. Conf. Artif. Intell. Statist.","author":"Paul"},{"key":"ref41","article-title":"Random projections for trust region subproblems","volume-title":"arXiv:1706.02730","author":"Vu","year":"2017"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/15M1025487"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1472"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/120874540"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9891-7"},{"key":"ref47","first-page":"1","article-title":"Precise expressions for random projections: Low-rank approximation and randomized newton","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"33","author":"Derezinski"},{"key":"ref48","first-page":"682","article-title":"Using the Nystr\u00f6m method to speed up kernel machines","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Williams"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1023\/B:STCO.0000035301.49549.88"},{"key":"ref50","first-page":"2153","article-title":"On the Nystr\u00f6m method for approximating a Gram matrix for improved kernel-based learning","volume":"6","author":"Drineas","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"ref51","first-page":"981","article-title":"Sampling methods for the Nystr\u00f6m method","volume":"13","author":"Kumar","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"ref52","first-page":"476","article-title":"Nystr\u00f6m method vs random Fourier features: A theoretical and empirical comparison","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Yang"},{"key":"ref53","first-page":"185","article-title":"Sharp analysis of low-rank kernel matrix approximations","volume-title":"Proc. Conf. Learn. Theory","author":"Bach"},{"issue":"1","key":"ref54","first-page":"853","article-title":"Reverse iterative volume sampling for linear regression","volume":"19","author":"Derezi\u0144ski","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1090\/noti2202"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"ref57","volume-title":"Convex Analysis","author":"Rockafellar","year":"2015"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.37"},{"key":"ref60","first-page":"3675","article-title":"Asymptotics for sketching in least squares regression","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Dobriban"},{"key":"ref61","first-page":"1","article-title":"Optimal iterative sketching methods with the subsampled randomized Hadamard transform","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"33","author":"Lacotte"},{"key":"ref62","first-page":"775","article-title":"Fast randomized kernel ridge regression with statistical guarantees","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Alaoui"},{"key":"ref63","first-page":"989","article-title":"An iterative, sketching-based framework for ridge regression","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Chowdhury"},{"key":"ref64","first-page":"19377","article-title":"Effective dimension adaptive sketching methods for faster regularized least-squares optimization","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","volume":"33","author":"Lacotte"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-5369-7"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9096-9"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970128"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(71)90184-3"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2019.8919769"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1515\/9781400831050"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2009.4960320"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2010.2041279"},{"key":"ref73","first-page":"5587","article-title":"Optimal randomized first-order methods for least-squares problems","volume-title":"Proc. Int. Conf. Mach. Learn.","author":"Lacotte"},{"key":"ref74","first-page":"315","article-title":"Accelerating stochastic gradient descent using predictive variance reduction","volume-title":"Proc. Adv. Neural Inf. Process. Syst.","author":"Johnson"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/dry009"},{"key":"ref76","first-page":"3052","article-title":"Convergence rates of sub-sampled Newton methods","volume-title":"Proc. 28th Int. Conf. Neural Inf. Process. Syst.","volume":"2","author":"Erdogdu"},{"issue":"10","key":"ref77","first-page":"2825","article-title":"Scikit-learn: Machine learning in Python","volume":"12","author":"Pedregosa","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.2307\/3318568"},{"key":"ref79","article-title":"Large scale kernel learning using block coordinate descent","volume-title":"arXiv:1602.05310","author":"Tu","year":"2016"},{"key":"ref80","article-title":"Do CIFAR-10 classifiers generalize to CIFAR-10?","volume-title":"arXiv:1806.00451","author":"Recht","year":"2018"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000282"},{"key":"ref82","volume-title":"Empirical Processes in M-Estimation","volume":"6","author":"Van de Geer","year":"2000"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.4064\/sm210-1-3"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielam\/18\/9760494\/9691364-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9760494\/09691364.pdf?arnumber=9691364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,13]],"date-time":"2024-01-13T22:29:27Z","timestamp":1705184967000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9691364\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5]]},"references-count":84,"journal-issue":{"issue":"5"},"URL":"https:\/\/doi.org\/10.1109\/tit.2022.3146206","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5]]}}}