{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T19:30:33Z","timestamp":1778268633628,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188796","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1249-1259","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Tight query complexity lower bounds for PCA via finite sample deformed wigner law"],"prefix":"10.1145","author":[{"given":"Max","family":"Simchowitz","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ahmed","family":"El Alaoui","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Recht","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"A lower bound for the optimization of finite sums. arXiv preprint arXiv:1410.0723","author":"Agarwal Alekh","year":"2014"},{"key":"e_1_3_2_2_2_1","unstructured":"Alekh Agarwal Martin J Wainwright Peter L Bartlett and Pradeep K Ravikumar. 2009. Information-theoretic lower bounds on the oracle complexity of convex optimization. In Advances in Neural Information Processing Systems. 1\u20139.   Alekh Agarwal Martin J Wainwright Peter L Bartlett and Pradeep K Ravikumar. 2009. Information-theoretic lower bounds on the oracle complexity of convex optimization. In Advances in Neural Information Processing Systems. 1\u20139."},{"key":"e_1_3_2_2_3_1","unstructured":"Zeyuan Allen-Zhu and Yuanzhi Li. 2016.  Zeyuan Allen-Zhu and Yuanzhi Li. 2016."},{"key":"e_1_3_2_2_4_1","volume-title":"Gap-Free, and Near-Optimal Rate. arXiv preprint arXiv:1607.07837","author":"First Efficient","year":"2016"},{"key":"e_1_3_2_2_5_1","unstructured":"Zeyuan Allen-Zhu and Yuanzhi Li. 2016. LazySVD: Even faster SVD decomposition yet without agonizing pain. In Advances in Neural Information Processing Systems. 974\u2013982.   Zeyuan Allen-Zhu and Yuanzhi Li. 2016. LazySVD: Even faster SVD decomposition yet without agonizing pain. In Advances in Neural Information Processing Systems. 974\u2013982."},{"key":"e_1_3_2_2_6_1","unstructured":"Greg W Anderson Alice Guionnet and Ofer Zeitouni. 2010.  Greg W Anderson Alice Guionnet and Ofer Zeitouni. 2010."},{"key":"e_1_3_2_2_7_1","unstructured":"An introduction to random matrices. Vol. 118. Cambridge university press.  An introduction to random matrices. Vol. 118. Cambridge university press."},{"key":"e_1_3_2_2_8_1","unstructured":"Anurag Anshu Naresh B Goud Rahul Jain Srijita Kundu and Priyanka Mukhopadhyay. 2017.  Anurag Anshu Naresh B Goud Rahul Jain Srijita Kundu and Priyanka Mukhopadhyay. 2017."},{"key":"e_1_3_2_2_9_1","volume-title":"arXiv preprint arXiv:1703.07521","author":"Lifting","year":"2017"},{"key":"e_1_3_2_2_10_1","unstructured":"Ery Arias-Castro Emmanuel J Candes and Mark A Davenport. 2013.  Ery Arias-Castro Emmanuel J Candes and Mark A Davenport. 2013."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2215837"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1025"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.02.007"},{"key":"e_1_3_2_2_14_1","unstructured":"Mireille Capitaine Catherine Donati-Martin and Delphine F\u00e9ral. 2009.  Mireille Capitaine Catherine Donati-Martin and Delphine F\u00e9ral. 2009."},{"key":"e_1_3_2_2_15_1","volume-title":"convergence and nonuniversality of the fluctuations. Annals of Probability","author":"The","year":"2009"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.3150\/13-BEJ555"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2653802"},{"key":"e_1_3_2_2_18_1","unstructured":"Xi Chen Adityanand Guntuboyina and Yuchen Zhang. 2016.  Xi Chen Adityanand Guntuboyina and Yuchen Zhang. 2016."},{"key":"e_1_3_2_2_19_1","volume-title":"Journal of Machine Learning Research 17","author":"Risk Lower Bounds On Bayes","year":"2016"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018661"},{"key":"e_1_3_2_2_21_1","unstructured":"James W Demmel. 1997.  James W Demmel. 1997."},{"key":"e_1_3_2_2_22_1","unstructured":"Applied numerical linear algebra. SIAM.  Applied numerical linear algebra. SIAM."},{"key":"e_1_3_2_2_23_1","volume-title":"The largest eigenvalue of rank one deformation of large Wigner matrices. Communications in mathematical physics 272, 1","author":"F\u00e9ral Delphine","year":"2007"},{"key":"e_1_3_2_2_24_1","volume-title":"Proceedings of the 33nd International Conference on Machine Learning, ICML. 2626\u20132634","author":"Garber Dan","year":"2016"},{"key":"e_1_3_2_2_25_1","unstructured":"Roger A Horn and Charles R Johnson. 2012.  Roger A Horn and Charles R Johnson. 2012."},{"key":"e_1_3_2_2_26_1","unstructured":"Matrix analysis. Cambridge university press.  Matrix analysis. Cambridge university press."},{"key":"e_1_3_2_2_27_1","unstructured":"Kevin G Jamieson Robert Nowak and Ben Recht. 2012.  Kevin G Jamieson Robert Nowak and Ben Recht. 2012."},{"key":"e_1_3_2_2_28_1","unstructured":"Query complexity of derivative-free optimization. In Advances in Neural Information Processing Systems. 2672\u20132680.   Query complexity of derivative-free optimization. In Advances in Neural Information Processing Systems. 2672\u20132680."},{"key":"e_1_3_2_2_29_1","volume-title":"How to Escape Saddle Points Efficiently. arXiv preprint arXiv:1703.00887","author":"Jin Chi","year":"2017"},{"key":"e_1_3_2_2_30_1","unstructured":"Ian Jolliffe. 2002.  Ian Jolliffe. 2002."},{"key":"e_1_3_2_2_31_1","unstructured":"Principal component analysis. Wiley Online Library.  Principal component analysis. Wiley Online Library."},{"key":"e_1_3_2_2_32_1","unstructured":"Olav Kallenberg. 2006.  Olav Kallenberg. 2006."},{"key":"e_1_3_2_2_33_1","volume-title":"Springer Science &amp","author":"Foundations"},{"key":"e_1_3_2_2_34_1","unstructured":"Cameron Musco and Christopher Musco. 2015. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems. 1396\u20131404.   Cameron Musco and Christopher Musco. 2015. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems. 1396\u20131404."},{"key":"e_1_3_2_2_35_1","unstructured":"Jelani Nelson Jakub Pachocki and Zhengyu Wang. 2017.  Jelani Nelson Jakub Pachocki and Zhengyu Wang. 2017."},{"key":"e_1_3_2_2_36_1","volume-title":"samplers, and finding duplicates. arXiv preprint arXiv:1703.08139","author":"Optimal","year":"2017"},{"key":"e_1_3_2_2_37_1","volume-title":"David Borisovich Yudin, and Edgar Ronald Dawson","author":"Nemirovskii Arkadii","year":"1983"},{"key":"e_1_3_2_2_38_1","unstructured":"Problem complexity and method efficiency in optimization. (1983).  Problem complexity and method efficiency in optimization. (1983)."},{"key":"e_1_3_2_2_39_1","unstructured":"Andrew Y Ng Michael I Jordan etal {n. d.}. On spectral clustering: Analysis and an algorithm.  Andrew Y Ng Michael I Jordan et al. {n. d.}. On spectral clustering: Analysis and an algorithm."},{"key":"e_1_3_2_2_40_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999.  Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627864"},{"key":"e_1_3_2_2_43_1","unstructured":"Ohad Shamir. 2014. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems. 163\u2013171.   Ohad Shamir. 2014. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems. 163\u2013171."},{"key":"e_1_3_2_2_44_1","volume-title":"Fast stochastic algorithms for SVD and PCA: Convergence properties and convexity. arXiv preprint arXiv:1507.08788","author":"Shamir Ohad","year":"2015"},{"key":"e_1_3_2_2_45_1","volume-title":"Ahmed El Alaoui, and Benjamin Recht","author":"Simchowitz Max","year":"2018"},{"key":"e_1_3_2_2_46_1","volume-title":"arXiv preprint (to appear)","author":"Complexity Lower Tight Query","year":"2018"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_3_2_2_48_1","unstructured":"Jacob Steinhardt and John C Duchi. 2015. Minimax rates for memory-bounded sparse linear regression.. In COLT. 1564\u20131587.  Jacob Steinhardt and John C Duchi. 2015. Minimax rates for memory-bounded sparse linear regression.. In COLT. 1564\u20131587."},{"key":"e_1_3_2_2_49_1","first-page":"1","article-title":"Memory, Communication, and Statistical Queries","volume":"22","author":"Steinhardt Jacob","year":"2015","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_50_1","unstructured":"Roman Vershynin. {n. d.}. High Dimensional Probability. ({n. d.}).  Roman Vershynin. {n. d.}. High Dimensional Probability. ({n. d.})."},{"key":"e_1_3_2_2_51_1","unstructured":"Blake E Woodworth and Nati Srebro. 2016. Tight complexity bounds for optimizing composite objectives. In Advances in neural information processing systems. 3639\u20133647.   Blake E Woodworth and Nati Srebro. 2016. Tight complexity bounds for optimizing composite objectives. In Advances in neural information processing systems. 3639\u20133647."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188796","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188796","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188796"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":50,"alternative-id":["10.1145\/3188745.3188796","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188796","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}