{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:33Z","timestamp":1750220973702,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1704417, AF-1813049"],"award-info":[{"award-number":["CCF-1704417, AF-1813049"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316403","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"890-901","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Memory-sample tradeoffs for linear regression with small error"],"prefix":"10.1145","author":[{"given":"Vatsal","family":"Sharan","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Gregory","family":"Valiant","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"first-page":"275","volume-title":"Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on","author":"Raz Ran","key":"e_1_3_2_1_1_1"},{"first-page":"742","volume-title":"Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on","author":"Raz Ran","key":"e_1_3_2_1_2_1"},{"key":"e_1_3_2_1_3_1","first-page":"856","volume-title":"Conference On Learning Theory","author":"Beame Paul","year":"2018"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055430"},{"key":"e_1_3_2_1_5_1","first-page":"1566","volume-title":"Conference on Learning Theory","author":"Moshkovitz Dana","year":"2017"},{"volume-title":"9th Innovations in Theoretical Computer Science Conference (ITCS)","year":"2018","author":"Moshkovitz Dana","key":"e_1_3_2_1_6_1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188962"},{"key":"e_1_3_2_1_8_1","first-page":"1516","volume-title":"Conference on Learning Theory","author":"Steinhardt Jacob","year":"2016"},{"key":"e_1_3_2_1_9_1","unstructured":"A.S. Nemirovski and D.B Yudin. Problem complexity and method efficiency in optimization. 1983.  A.S. Nemirovski and D.B Yudin. Problem complexity and method efficiency in optimization. 1983."},{"key":"e_1_3_2_1_10_1","unstructured":"Yurii Nesterov. Introductory lectures on convex optimization: A basic course. 2014.   Yurii Nesterov. Introductory lectures on convex optimization: A basic course. 2014."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1025"},{"key":"e_1_3_2_1_13_1","unstructured":"Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex optimization: Adaptivity lower bounds for non-smooth convex minimization. CoRR abs\/1808.03880 2018.  Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex optimization: Adaptivity lower bounds for non-smooth convex minimization. CoRR abs\/1808.03880 2018."},{"key":"e_1_3_2_1_14_1","unstructured":"Jelena Diakonikolas and Crist\u00f3bal Guzm\u00e1n. Lower bounds for parallel and randomized convex optimization. CoRR abs\/1811.01903 2018.  Jelena Diakonikolas and Crist\u00f3bal Guzm\u00e1n. Lower bounds for parallel and randomized convex optimization. CoRR abs\/1811.01903 2018."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_45"},{"key":"e_1_3_2_1_16_1","first-page":"789","volume-title":"Advances in Neural Information Processing Systems","author":"Hu Chonghai","year":"2009"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0434-y"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/110848876"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.24"},{"key":"e_1_3_2_1_20_1","first-page":"763","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015","author":"Frostig Roy","year":"2015"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/2971"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0864-7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3122009.3176845"},{"key":"e_1_3_2_1_24_1","first-page":"604","volume-title":"Conference On Learning Theory, COLT 2018","author":"Jain Prateek","year":"2018"},{"key":"e_1_3_2_1_25_1","unstructured":"Weihao Kong. Personal communication. 2018.  Weihao Kong. Personal communication. 2018."},{"key":"e_1_3_2_1_26_1","first-page":"1587","volume-title":"Conference on Learning Theory","author":"Steinhardt Jacob","year":"2015"},{"key":"e_1_3_2_1_27_1","first-page":"171","volume-title":"Advances in Neural Information Processing Systems","author":"Shamir Ohad","year":"2014"},{"volume-title":"Conference on Learning Theory (COLT)","year":"2018","author":"Dagan Yuval","key":"e_1_3_2_1_28_1"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897582"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_32_1","first-page":"3647","volume-title":"Advances in Neural Information Processing Systems","author":"Blake","year":"2016"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2701343"},{"key":"e_1_3_2_1_34_1","first-page":"10","article-title":"How to make the gradients small","volume":"88","author":"Nesterov Yurii","year":"2012","journal-title":"Optima"},{"volume-title":"Science and Technology Facilities Council Swindon","year":"2012","author":"Cartis Coralia","key":"e_1_3_2_1_35_1"},{"key":"e_1_3_2_1_36_1","unstructured":"Coralia Cartis Nick IM Gould and Philippe L Toint. Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization. arXiv preprint arXiv:1709.07180 2017.  Coralia Cartis Nick IM Gould and Philippe L Toint. Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization. arXiv preprint arXiv:1709.07180 2017."},{"key":"e_1_3_2_1_37_1","unstructured":"Yair Carmon John C. Duchi Oliver Hinder and Aaron Sidford. Lower bounds for finding stationary points I. CoRR abs\/1710.11606 2017.  Yair Carmon John C. Duchi Oliver Hinder and Aaron Sidford. Lower bounds for finding stationary points I. CoRR abs\/1710.11606 2017."},{"key":"e_1_3_2_1_38_1","unstructured":"Yair Carmon John C Duchi Oliver Hinder and Aaron Sidford. Lower bounds for finding stationary points II: First-order methods. arXiv preprint arXiv:1711.00841 2017.  Yair Carmon John C Duchi Oliver Hinder and Aaron Sidford. Lower bounds for finding stationary points II: First-order methods. arXiv preprint arXiv:1711.00841 2017."},{"key":"e_1_3_2_1_39_1","first-page":"2013016","article-title":"First-order methods with inexact oracle: the strongly convex case","author":"Devolder Olivier","year":"2013","journal-title":"CORE Discussion Papers"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0677-5"},{"volume-title":"COLT 2013 - The 26th Annual Conference on Learning Theory","year":"2013","author":"Shamir Ohad","key":"e_1_3_2_1_41_1"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2409256"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Sergey G Bobkov. On concentration of distributions of random weighted sums. Annals of probability pages 195\u2013215 2003.  Sergey G Bobkov. On concentration of distributions of random weighted sums. Annals of probability pages 195\u2013215 2003.","DOI":"10.1214\/aop\/1046294309"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-03-03085-X"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Heinrich von Weizs\u00e4cker. Sudakov\u2019s typical marginals random linear functionals and a conditional central limit theorem. Probability theory and related fields 107 (3):313\u2013324 1997.  Heinrich von Weizs\u00e4cker. Sudakov\u2019s typical marginals random linear functionals and a conditional central limit theorem. Probability theory and related fields 107 (3):313\u2013324 1997.","DOI":"10.1007\/s004400050087"},{"first-page":"121","volume-title":"Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence","author":"Dasgupta Sanjoy","key":"e_1_3_2_1_46_1"},{"key":"e_1_3_2_1_47_1","first-page":"1338","volume-title":"Annals of Statistics","author":"Laurent Beatrice","year":"2000"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316403","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":47,"alternative-id":["10.1145\/3313276.3316403","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316403","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}