{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:59Z","timestamp":1750220279895,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520069","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1158-1171","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Memory bounds for the experts problem"],"prefix":"10.1145","author":[{"given":"Vaidehi","family":"Srinivas","sequence":"first","affiliation":[{"name":"Northwestern University, USA"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Ziyu","family":"Xu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Samson","family":"Zhou","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"14315","article-title":"Prediction with Corrupted Expert Advice","author":"Amir Idan","year":"2020","unstructured":"Idan Amir , Idan Attias , Tomer Koren , Yishay Mansour , and Roi Livni . 2020 . Prediction with Corrupted Expert Advice . In Advances in Neural Information Processing Systems. 33, Curran Associates, Inc. , 14315 \u2013 14325 . https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/a512294422de868f8474d22344636f16-Paper.pdf Idan Amir, Idan Attias, Tomer Koren, Yishay Mansour, and Roi Livni. 2020. Prediction with Corrupted Expert Advice. In Advances in Neural Information Processing Systems. 33, Curran Associates, Inc., 14315\u201314325. https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/a512294422de868f8474d22344636f16-Paper.pdf","journal-title":"Advances in Neural Information Processing Systems. 33, Curran Associates, Inc."},{"unstructured":"Yossi Arjevani and Ohad Shamir. 2015. Communication Complexity of Distributed Convex Learning and Optimization. In Advances in Neural Information Processing Systems 28. 1756\u20131764.  Yossi Arjevani and Ohad Shamir. 2015. Communication Complexity of Distributed Convex Learning and Optimization. In Advances in Neural Information Processing Systems 28. 1756\u20131764.","key":"e_1_3_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.4086\/toc.2012.v008a006"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1145\/3357713.3384341"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_6_1","first-page":"1","article-title":"An optimal algorithm for \u2113 _1-heavy hitters in insertion streams and related problems","volume":"15","author":"Bhattacharyya Arnab","year":"2018","unstructured":"Arnab Bhattacharyya , Palash Dey , and David P Woodruff . 2018 . An optimal algorithm for \u2113 _1-heavy hitters in insertion streams and related problems . ACM Transactions on Algorithms (TALG) , 15 , 1 (2018), 1 \u2013 27 . Arnab Bhattacharyya, Palash Dey, and David P Woodruff. 2018. An optimal algorithm for \u2113 _1-heavy hitters in insertion streams and related problems. ACM Transactions on Algorithms (TALG), 15, 1 (2018), 1\u201327.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"volume-title":"Online Algorithms. 1442","author":"Blum Avrim","unstructured":"Avrim Blum . 1998. On-Line Algorithms in Machine Learning . In Online Algorithms. 1442 , Springer Berlin Heidelberg , 306\u2013325. Avrim Blum. 1998. On-Line Algorithms in Machine Learning. In Online Algorithms. 1442, Springer Berlin Heidelberg, 306\u2013325.","key":"e_1_3_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1109\/FOCS.2013.77"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/2897518.2897582"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1145\/3034786.3034798"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/2897518.2897558"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.5194\/egusphere-egu2020-17663"},{"volume-title":"Analysis of Production and Allocation","author":"Brown George W.","unstructured":"George W. Brown . 1951. Iterative solution of games by fictitious play . In Analysis of Production and Allocation . Wiley , 374\u2013376. George W. Brown. 1951. Iterative solution of games by fictitious play. In Analysis of Production and Allocation. Wiley, 374\u2013376.","key":"e_1_3_2_1_13_1"},{"volume-title":"Prediction, learning, and games","author":"Cesa-Bianchi Nicol\u00f2","unstructured":"Nicol\u00f2 Cesa-Bianchi and G\u00e1bor Lugosi . 2006. Prediction, learning, and games . Cambridge university press . Nicol\u00f2 Cesa-Bianchi and G\u00e1bor Lugosi. 2006. Prediction, learning, and games. Cambridge university press.","key":"e_1_3_2_1_14_1"},{"doi-asserted-by":"crossref","unstructured":"Nicol\u00f2 Cesa-Bianchi Yishay Mansour and Gilles Stoltz. 2005. Improved Second-Order Bounds for Prediction with Expert Advice. In Learning Theory. 217\u2013232. isbn:978-3-540-31892-7  Nicol\u00f2 Cesa-Bianchi Yishay Mansour and Gilles Stoltz. 2005. Improved Second-Order Bounds for Prediction with Expert Advice. In Learning Theory. 217\u2013232. isbn:978-3-540-31892-7","key":"e_1_3_2_1_15_1","DOI":"10.1007\/11503415_15"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1109\/CCC.2003.1214414"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 25th Annual Conference on Learning Theory. 6.1\u20136.20","author":"Chiang Chao-Kai","year":"2012","unstructured":"Chao-Kai Chiang , Tianbao Yang , Chia-Jung Lee , Mehrdad Mahdavi , Chi-Jen Lu , Rong Jin , and Shenghuo Zhu . 2012 . Online Optimization with Gradual Variations . In Proceedings of the 25th Annual Conference on Learning Theory. 6.1\u20136.20 . Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. 2012. Online Optimization with Gradual Variations. In Proceedings of the 25th Annual Conference on Learning Theory. 6.1\u20136.20."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1016\/j.jalgor.2003.12.001"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1109\/SFCS.1996.548512"},{"doi-asserted-by":"crossref","unstructured":"Thomas M Cover. 2011. Universal portfolios. In The Kelly Capital Growth Investment Criterion: Theory and Practice. World Scientific 181\u2013209.  Thomas M Cover. 2011. Universal portfolios. In The Kelly Capital Growth Investment Criterion: Theory and Practice. World Scientific 181\u2013209.","key":"e_1_3_2_1_21_1","DOI":"10.1142\/9789814293501_0015"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1109\/18.485708"},{"key":"e_1_3_2_1_23_1","volume-title":"Space Complexity. In 24th Annual European Symposium on Algorithms (ESA","author":"Crouch Michael","year":"2016","unstructured":"Michael Crouch , Andrew McGregor , Gregory Valiant , and David P. Woodruff . 2016. Stochastic Streams: Sample Complexity vs . Space Complexity. In 24th Annual European Symposium on Algorithms (ESA 2016 ). 32:1\u201332:15. Michael Crouch, Andrew McGregor, Gregory Valiant, and David P. Woodruff. 2016. Stochastic Streams: Sample Complexity vs. Space Complexity. In 24th Annual European Symposium on Algorithms (ESA 2016). 32:1\u201332:15."},{"key":"e_1_3_2_1_24_1","volume-title":"Detecting Correlations with Little Memory and Communication. CoRR, abs\/1803.01420","author":"Dagan Yuval","year":"2018","unstructured":"Yuval Dagan and Ohad Shamir . 2018. Detecting Correlations with Little Memory and Communication. CoRR, abs\/1803.01420 ( 2018 ), arxiv:1803.01420. arxiv:1803.01420 Yuval Dagan and Ohad Shamir. 2018. Detecting Correlations with Little Memory and Communication. CoRR, abs\/1803.01420 (2018), arxiv:1803.01420. arxiv:1803.01420"},{"key":"e_1_3_2_1_25_1","volume-title":"Advances in Neural Information Processing Systems. 28, Curran Associates","author":"Foster Dylan J","year":"2015","unstructured":"Dylan J Foster , Alexander Rakhlin , and Karthik Sridharan . 2015. Adaptive Online Learning . In Advances in Neural Information Processing Systems. 28, Curran Associates , Inc .. https:\/\/proceedings.neurips.cc\/paper\/ 2015 \/file\/19de10adbaa1b2ee13f77f679fa1483a-Paper.pdf Dylan J Foster, Alexander Rakhlin, and Karthik Sridharan. 2015. Adaptive Online Learning. In Advances in Neural Information Processing Systems. 28, Curran Associates, Inc.. https:\/\/proceedings.neurips.cc\/paper\/2015\/file\/19de10adbaa1b2ee13f77f679fa1483a-Paper.pdf"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1006\/game.1999.0740"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1006\/jcss.1997.1504"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1006\/game.1999.0738"},{"key":"e_1_3_2_1_29_1","volume-title":"Nguyen","author":"Garg Ankit","year":"2014","unstructured":"Ankit Garg , Tengyu Ma , and Huy L . Nguyen . 2014 . On Communication Cost of Distributed Statistical Estimation and Dimensionality. In Advances in Neural Information Processing Systems 27. 2726\u20132734. Ankit Garg, Tengyu Ma, and Huy L. Nguyen. 2014. On Communication Cost of Distributed Statistical Estimation and Dimensionality. In Advances in Neural Information Processing Systems 27. 2726\u20132734."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1109\/SFCS.1998.743463"},{"unstructured":"Sumegha Garg Pravesh K Kothari and Ran Raz. 2020. Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich\u2019s PRG. arXiv preprint arXiv:2002.07235.  Sumegha Garg Pravesh K Kothari and Ran Raz. 2020. Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich\u2019s PRG. arXiv preprint arXiv:2002.07235.","key":"e_1_3_2_1_31_1"},{"doi-asserted-by":"crossref","unstructured":"Sumegha Garg Ran Raz and Avishay Tal. 2017. Extractor-based time-space tradeoffs for learning. Manuscript. July.  Sumegha Garg Ran Raz and Avishay Tal. 2017. Extractor-based time-space tradeoffs for learning. Manuscript. July.","key":"e_1_3_2_1_32_1","DOI":"10.1145\/3188745.3188962"},{"key":"e_1_3_2_1_33_1","volume-title":"34th Computational Complexity Conference (CCC","author":"Garg Sumegha","year":"2019","unstructured":"Sumegha Garg , Ran Raz , and Avishay Tal . 2019 . Time-space lower bounds for two-pass learning . In 34th Computational Complexity Conference (CCC 2019). Sumegha Garg, Ran Raz, and Avishay Tal. 2019. Time-space lower bounds for two-pass learning. In 34th Computational Complexity Conference (CCC 2019)."},{"key":"e_1_3_2_1_34_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Gravin Nick","year":"2017","unstructured":"Nick Gravin , Yuval Peres , and Balasubramanian Sivan . 2017 . Tight Lower Bounds for Multiplicative Weights Algorithmic Families. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Nick Gravin, Yuval Peres, and Balasubramanian Sivan. 2017. Tight Lower Bounds for Multiplicative Weights Algorithmic Families. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.1137\/07069328X"},{"key":"e_1_3_2_1_36_1","volume-title":"Warmuth","author":"Haussler David","year":"1995","unstructured":"David Haussler , Jyrki Kivinen , and Manfred K . Warmuth . 1995 . Tight Worst-Case Loss Bounds for Predicting with Expert Advice. In Computational Learning Theory (Lecture Notes in Computer Science). Springer , 69\u201383. David Haussler, Jyrki Kivinen, and Manfred K. Warmuth. 1995. Tight Worst-Case Loss Bounds for Predicting with Expert Advice. In Computational Learning Theory (Lecture Notes in Computer Science). Springer, 69\u201383."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1561\/2400000013"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1007\/s10994-010-5175-x"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1023\/A:1007396710653"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"e_1_3_2_1_41_1","volume-title":"Karnick","author":"Kar Purushottam","year":"2013","unstructured":"Purushottam Kar , Bharath K. Sriperumbudur , Prateek Jain , and Harish C . Karnick . 2013 . On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions . arXiv:1305.2505 [cs, stat], May, arxiv:1305.2505. Purushottam Kar, Bharath K. Sriperumbudur, Prateek Jain, and Harish C. Karnick. 2013. On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions. arXiv:1305.2505 [cs, stat], May, arxiv:1305.2505."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1145\/3055399.3055430"},{"unstructured":"Wouter M Koolen Tim van Erven and Peter Gr\u00fcnwald. 2014. Learning the Learning Rate for Prediction with Expert Advice. In Advances in Neural Information Processing Systems. 27 https:\/\/proceedings.neurips.cc\/paper\/2014\/file\/3f67fd97162d20e6fe27748b5b372509-Paper.pdf  Wouter M Koolen Tim van Erven and Peter Gr\u00fcnwald. 2014. Learning the Learning Rate for Prediction with Expert Advice. In Advances in Neural Information Processing Systems. 27 https:\/\/proceedings.neurips.cc\/paper\/2014\/file\/3f67fd97162d20e6fe27748b5b372509-Paper.pdf","key":"e_1_3_2_1_43_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1109\/FOCS.2016.16"},{"key":"e_1_3_2_1_45_1","volume-title":"Stochastic Multi-armed Bandits in Constant Space. In International Conference on Artificial Intelligence and Statistics. 386\u2013394","author":"Liau David","year":"2018","unstructured":"David Liau , Zhao Song , Eric Price , and Ger Yang . 2018 . Stochastic Multi-armed Bandits in Constant Space. In International Conference on Artificial Intelligence and Statistics. 386\u2013394 . David Liau, Zhao Song, Eric Price, and Ger Yang. 2018. Stochastic Multi-armed Bandits in Constant Space. In International Conference on Artificial Intelligence and Statistics. 386\u2013394."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1109\/SFCS.1989.63487"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_47_1","DOI":"10.1006\/inco.1997.2686"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_48_1","DOI":"10.5555\/2804694.2804704"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_49_1","DOI":"10.1109\/SFCS.1991.185411"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_50_1","DOI":"10.1109\/TIT.2016.2549542"},{"key":"e_1_3_2_1_51_1","first-page":"08","article-title":"Online Learning With Predictable Sequences","volume":"30","author":"Rakhlin Alexander","year":"2012","unstructured":"Alexander Rakhlin and Karthik Sridharan . 2012 . Online Learning With Predictable Sequences . Journal of Machine Learning Research , 30 (2012), 08 . Alexander Rakhlin and Karthik Sridharan. 2012. Online Learning With Predictable Sequences. Journal of Machine Learning Research, 30 (2012), 08.","journal-title":"Journal of Machine Learning Research"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_52_1","DOI":"10.1109\/FOCS.2017.73"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_53_1","DOI":"10.1145\/3186563"},{"unstructured":"Amir Sani Gergely Neu and Alessandro Lazaric. 2014. Exploiting easy data in online optimization. In Advances in Neural Information Processing Systems. 27 https:\/\/proceedings.neurips.cc\/paper\/2014\/file\/01f78be6f7cad02658508fe4616098a9-Paper.pdf  Amir Sani Gergely Neu and Alessandro Lazaric. 2014. Exploiting easy data in online optimization. In Advances in Neural Information Processing Systems. 27 https:\/\/proceedings.neurips.cc\/paper\/2014\/file\/01f78be6f7cad02658508fe4616098a9-Paper.pdf","key":"e_1_3_2_1_54_1"},{"key":"e_1_3_2_1_55_1","volume-title":"Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization. CoRR, abs\/1603.00570","author":"Shamir Ohad","year":"2016","unstructured":"Ohad Shamir . 2016. Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization. CoRR, abs\/1603.00570 ( 2016 ). Ohad Shamir. 2016. Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization. CoRR, abs\/1603.00570 (2016)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_56_1","DOI":"10.1145\/3183713.3196930"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_57_1","DOI":"10.1016\/S0304-3975(00)00138-9"},{"key":"e_1_3_2_1_58_1","volume-title":"Aggregating Strategies. In Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT. 371\u2013386","author":"Vovk Vladimir","year":"1990","unstructured":"Vladimir Vovk . 1990 . Aggregating Strategies. In Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT. 371\u2013386 . Vladimir Vovk. 1990. Aggregating Strategies. In Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT. 371\u2013386."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_59_1","DOI":"10.1006\/jcss.1997.1556"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_60_1","DOI":"10.1023\/A:1007595032382"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_61_1","DOI":"10.1007\/11564089_34"},{"doi-asserted-by":"crossref","unstructured":"Omri Weinstein and David P Woodruff. 2015. The simultaneous communication of disjointness with applications to data streams. In International Colloquium on Automata Languages and Programming. 1082\u20131093.  Omri Weinstein and David P Woodruff. 2015. The simultaneous communication of disjointness with applications to data streams. In International Colloquium on Automata Languages and Programming. 1082\u20131093.","key":"e_1_3_2_1_62_1","DOI":"10.1007\/978-3-662-47672-7_88"},{"unstructured":"Yuchen Zhang John Duchi Michael I Jordan and Martin J Wainwright. 2013. Information-Theoretic Lower Bounds for Distributed Statistical Estimation with Communication Constraints. In Advances in Neural Information Processing Systems. 26.  Yuchen Zhang John Duchi Michael I Jordan and Martin J Wainwright. 2013. Information-Theoretic Lower Bounds for Distributed Statistical Estimation with Communication Constraints. In Advances in Neural Information Processing Systems. 26.","key":"e_1_3_2_1_63_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '22","name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520069","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":63,"alternative-id":["10.1145\/3519935.3520069","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520069","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}