{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T19:24:50Z","timestamp":1774034690564,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":62,"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.3519950","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"846-859","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Fast rates for nonparametric online learning: from realizability to learning in games"],"prefix":"10.1145","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Noah","family":"Golowich","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/ab3988"},{"key":"e_1_3_2_1_2_1","unstructured":"Noga Alon Omri Ben-Eliezer Yuval Dagan Shay Moran Moni Naor and Eylon Yogev. 2021. Adversarial Laws of Large Numbers and Optimal Regret in Online Classification. arXiv:2101.09054 [cs math stat] Jan. arxiv:2101.09054 arXiv: 2101.09054  Noga Alon Omri Ben-Eliezer Yuval Dagan Shay Moran Moni Naor and Eylon Yogev. 2021. Adversarial Laws of Large Numbers and Optimal Regret in Online Classification. arXiv:2101.09054 [cs math stat] Jan. arxiv:2101.09054 arXiv: 2101.09054"},{"key":"e_1_3_2_1_3_1","volume-title":"March, arxiv:1806.00949 arXiv","author":"Alon Noga","year":"1806","unstructured":"Noga Alon , Roi Livni , Maryanthe Malliaris , and Shay Moran . 2019. Private PAC learning implies finite Littlestone dimension. arXiv:1806.00949 [cs, math, stat] , March, arxiv:1806.00949 arXiv : 1806 .00949 Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. 2019. Private PAC learning implies finite Littlestone dimension. arXiv:1806.00949 [cs, math, stat], March, arxiv:1806.00949 arXiv: 1806.00949"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022821128753"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000282"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00231-6"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 2009 Conference on Learning Theory. https:\/\/www.cs.huji.ac.il\/~shais\/papers\/BendavidPalShalevtech09","author":"Ben-David Shai","year":"2009","unstructured":"Shai Ben-David , David Pal , and Shai Shalev-Shwartz . 2009 . Agnostic Online Learning . In Proceedings of the 2009 Conference on Learning Theory. https:\/\/www.cs.huji.ac.il\/~shais\/papers\/BendavidPalShalevtech09 .pdf Shai Ben-David, David Pal, and Shai Shalev-Shwartz. 2009. Agnostic Online Learning. In Proceedings of the 2009 Conference on Learning Theory. https:\/\/www.cs.huji.ac.il\/~shais\/papers\/BendavidPalShalevtech09.pdf"},{"key":"e_1_3_2_1_8_1","volume-title":"Roy","author":"Bilodeau Blair","year":"2020","unstructured":"Blair Bilodeau , Dylan J. Foster , and Daniel M . Roy . 2020 . Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance . arXiv:2007.01160 [cs, stat], Aug., arxiv:2007.01160 arXiv: 2007.01160 Blair Bilodeau, Dylan J. Foster, and Daniel M. Roy. 2020. Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance. arXiv:2007.01160 [cs, stat], Aug., arxiv:2007.01160 arXiv: 2007.01160"},{"key":"e_1_3_2_1_9_1","unstructured":"Adam Block Yuval Dagan and Sasha Rakhlin. 2021. Majorizing Measures Sequential Complexities and Online Learning. arXiv:2102.01729 [cs stat] Feb. arxiv:2102.01729 arXiv: 2102.01729  Adam Block Yuval Dagan and Sasha Rakhlin. 2021. Majorizing Measures Sequential Complexities and Online Learning. arXiv:2102.01729 [cs stat] Feb. arxiv:2102.01729 arXiv: 2102.01729"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_11_1","unstructured":"Olivier Bousquet Vladimir Koltchinskii and Dmitry Panchenko. 2004. Some Local Measures of Complexity of Convex Hulls and Generalization Bounds. arXiv:math\/0405340 May arxiv:math\/0405340 arXiv: math\/0405340  Olivier Bousquet Vladimir Koltchinskii and Dmitry Panchenko. 2004. Some Local Measures of Complexity of Convex Hulls and Generalization Bounds. arXiv:math\/0405340 May arxiv:math\/0405340 arXiv: math\/0405340"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of Machine Learning Research. 21","author":"Bubeck Sebastien","year":"2019","unstructured":"Sebastien Bubeck , Yuanzhi Li , Haipeng Luo , and Chen-Yu Wei . 2019 . Improved Path-length Regret Bounds for Bandits . In Proceedings of Machine Learning Research. 21 . Sebastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen-Yu Wei. 2019. Improved Path-length Regret Bounds for Bandits. In Proceedings of Machine Learning Research. 21."},{"key":"e_1_3_2_1_13_1","volume-title":"March, arxiv:2003.00563 arXiv","author":"Bun Mark","year":"2003","unstructured":"Mark Bun , Roi Livni , and Shay Moran . 2020. An Equivalence Between Private Classification and Online Prediction. arXiv:2003.00563 [cs, stat] , March, arxiv:2003.00563 arXiv : 2003 .00563 Mark Bun, Roi Livni, and Shay Moran. 2020. An Equivalence Between Private Classification and Online Prediction. arXiv:2003.00563 [cs, stat], March, arxiv:2003.00563 arXiv: 2003.00563"},{"key":"e_1_3_2_1_14_1","volume-title":"Prediction, learning, and games","author":"Cesa-Bianchi Nicol\u00f2","year":"1917","unstructured":"Nicol\u00f2 Cesa-Bianchi and G\u00e1bor Lugosi . 2006. Prediction, learning, and games . Cambridge University Press , Cambridge; New York . isbn:978-0-511- 1917 8-7 978-0-511-54692-1 978-0-511-18995-1 978-0-511-19059-9 978-0-511-19091-9 978-0-511-19131-2 978-0-521-84108-5 http:\/\/public.eblib.com\/choice\/publicfullrecord.aspx?p=258497 OCLC: 70056026 Nicol\u00f2 Cesa-Bianchi and G\u00e1bor Lugosi. 2006. Prediction, learning, and games. Cambridge University Press, Cambridge; New York. isbn:978-0-511-19178-7 978-0-511-54692-1 978-0-511-18995-1 978-0-511-19059-9 978-0-511-19091-9 978-0-511-19131-2 978-0-521-84108-5 http:\/\/public.eblib.com\/choice\/publicfullrecord.aspx?p=258497 OCLC: 70056026"},{"key":"e_1_3_2_1_15_1","volume-title":"Oct., arxiv:2006.04953 arXiv","author":"Chen Xi","year":"2006","unstructured":"Xi Chen and Binghui Peng . 2020. Hedging in games: Faster convergence of external and swap regrets. arXiv:2006.04953 [cs] , Oct., arxiv:2006.04953 arXiv : 2006 .04953 Xi Chen and Binghui Peng. 2020. Hedging in games: Faster convergence of external and swap regrets. arXiv:2006.04953 [cs], Oct., arxiv:2006.04953 arXiv: 2006.04953"},{"key":"e_1_3_2_1_16_1","unstructured":"Amit Daniely and Shai Shalev-Shwartz. 2014. Optimal Learners for Multiclass Problems. arXiv:1405.2420 [cs] May arxiv:1405.2420 arXiv: 1405.2420  Amit Daniely and Shai Shalev-Shwartz. 2014. Optimal Learners for Multiclass Problems. arXiv:1405.2420 [cs] May arxiv:1405.2420 arXiv: 1405.2420"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.21"},{"key":"e_1_3_2_1_18_1","unstructured":"Constantinos Daskalakis Maxwell Fishelson and Noah Golowich. 2021. Near-Optimal No-Regret Learning in General Games. arXiv:2108.06924 [cs] Aug. arxiv:2108.06924 arXiv: 2108.06924  Constantinos Daskalakis Maxwell Fishelson and Noah Golowich. 2021. Near-Optimal No-Regret Learning in General Games. arXiv:2108.06924 [cs] Aug. arxiv:2108.06924 arXiv: 2108.06924"},{"key":"e_1_3_2_1_19_1","volume-title":"Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games. CoRR, abs\/2111.08911","author":"Daskalakis Constantinos","year":"2021","unstructured":"Constantinos Daskalakis and Noah Golowich . 2021. Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games. CoRR, abs\/2111.08911 ( 2021 ). Constantinos Daskalakis and Noah Golowich. 2021. Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games. CoRR, abs\/2111.08911 (2021)."},{"key":"e_1_3_2_1_20_1","unstructured":"Kefan Dong Jiaqi Yang and Tengyu Ma. 2021. Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism Embrace Virtual Curvature. arXiv:2102.04168 [cs] May arxiv:2102.04168 arXiv: 2102.04168  Kefan Dong Jiaqi Yang and Tengyu Ma. 2021. Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism Embrace Virtual Curvature. arXiv:2102.04168 [cs] May arxiv:2102.04168 arXiv: 2102.04168"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176995384"},{"key":"e_1_3_2_1_22_1","volume-title":"Oct., arxiv:1910.10906 arXiv","author":"Farina Gabriele","year":"1910","unstructured":"Gabriele Farina , Christian Kroer , and Tuomas Sandholm . 2019. Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions. arXiv:1910.10906 [cs, math] , Oct., arxiv:1910.10906 arXiv : 1910 .10906 Gabriele Farina, Christian Kroer, and Tuomas Sandholm. 2019. Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions. arXiv:1910.10906 [cs, math], Oct., arxiv:1910.10906 arXiv: 1910.10906"},{"key":"e_1_3_2_1_23_1","volume-title":"Logistic Regression: The Importance of Being Improper. arXiv:1803.09349 [cs, stat], Dec., arxiv:1803.09349 arXiv","author":"Foster Dylan J.","year":"2018","unstructured":"Dylan J. Foster , Satyen Kale , Haipeng Luo , Mehryar Mohri , and Karthik Sridharan . 2018 . Logistic Regression: The Importance of Being Improper. arXiv:1803.09349 [cs, stat], Dec., arxiv:1803.09349 arXiv : 1803.09349 Dylan J. Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. 2018. Logistic Regression: The Importance of Being Improper. arXiv:1803.09349 [cs, stat], Dec., arxiv:1803.09349 arXiv: 1803.09349"},{"key":"e_1_3_2_1_24_1","volume-title":"Foster and Akshay Krishnamurthy","author":"Dylan","year":"2018","unstructured":"Dylan J. Foster and Akshay Krishnamurthy . 2018 . Contextual bandits with surrogate losses: Margin bounds and efficient algorithms. arXiv:1806.10745 [cs, stat], Nov., arxiv:1806.10745 arXiv: 1806.10745 Dylan J. Foster and Akshay Krishnamurthy. 2018. Contextual bandits with surrogate losses: Margin bounds and efficient algorithms. arXiv:1806.10745 [cs, stat], Nov., arxiv:1806.10745 arXiv: 1806.10745"},{"key":"e_1_3_2_1_25_1","volume-title":"Foster and Alexander Rakhlin","author":"Dylan","year":"2020","unstructured":"Dylan J. Foster and Alexander Rakhlin . 2020 . Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles . arXiv:2002.04926 [cs, math, stat], Feb., arxiv:2002.04926 arXiv: 2002.04926 Dylan J. Foster and Alexander Rakhlin. 2020. Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles. arXiv:2002.04926 [cs, math, stat], Feb., arxiv:2002.04926 arXiv: 2002.04926"},{"key":"e_1_3_2_1_26_1","unstructured":"Steve Hanneke. 2016. The Optimal Sample Complexity of PAC Learning. arXiv:1507.00473 [cs stat] Feb. arxiv:1507.00473 arXiv: 1507.00473  Steve Hanneke. 2016. The Optimal Sample Complexity of PAC Learning. arXiv:1507.00473 [cs stat] Feb. arxiv:1507.00473 arXiv: 1507.00473"},{"key":"e_1_3_2_1_27_1","unstructured":"Steve Hanneke Roi Livni and Shay Moran. 2021. Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0\/1 Games. arXiv:2102.01646 [cs stat] Feb. arxiv:2102.01646 arXiv: 2102.01646  Steve Hanneke Roi Livni and Shay Moran. 2021. Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0\/1 Games. arXiv:2102.01646 [cs stat] Feb. arxiv:2102.01646 arXiv: 2102.01646"},{"key":"e_1_3_2_1_28_1","unstructured":"Moritz Hardt Benjamin Recht and Yoram Singer. 2015. Train faster generalize better: Stability of stochastic gradient descent. arXiv:1509.01240 [cs math stat] Sept. arxiv:1509.01240 arXiv: 1509.01240  Moritz Hardt Benjamin Recht and Yoram Singer. 2015. Train faster generalize better: Stability of stochastic gradient descent. arXiv:1509.01240 [cs math stat] Sept. arxiv:1509.01240 arXiv: 1509.01240"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.705569"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1097"},{"key":"e_1_3_2_1_31_1","unstructured":"Elad Hazan and Tomer Koren. 2016. The Computational Power of Optimization in Online Learning. arXiv:1504.02089 [cs] Jan. arxiv:1504.02089 arXiv: 1504.02089  Elad Hazan and Tomer Koren. 2016. The Computational Power of Optimization in Online Learning. arXiv:1504.02089 [cs] Jan. arxiv:1504.02089 arXiv: 1504.02089"},{"key":"e_1_3_2_1_32_1","unstructured":"Elad Hazan Roi Livni and Yishay Mansour. 2015. Classification with Low Rank and Missing Data. arXiv:1501.03273 [cs] Jan. arxiv:1501.03273 arXiv: 1501.03273  Elad Hazan Roi Livni and Yishay Mansour. 2015. Classification with Low Rank and Missing Data. arXiv:1501.03273 [cs] Jan. arxiv:1501.03273 arXiv: 1501.03273"},{"key":"e_1_3_2_1_33_1","unstructured":"Elad Hazan and Tengyu Ma. 2016. A Non-generative Framework and Convex Relaxations for Unsupervised Learning. arXiv:1610.01132 [cs stat] Dec. arxiv:1610.01132 arXiv: 1610.01132  Elad Hazan and Tengyu Ma. 2016. A Non-generative Framework and Convex Relaxations for Unsupervised Learning. arXiv:1610.01132 [cs stat] Dec. arxiv:1610.01132 arXiv: 1610.01132"},{"key":"e_1_3_2_1_34_1","unstructured":"Yu-Guan Hsieh Kimon Antonakopoulos and Panayotis Mertikopoulos. 2021. Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium. arXiv:2104.12761 [cs math] April arxiv:2104.12761 arXiv: 2104.12761  Yu-Guan Hsieh Kimon Antonakopoulos and Panayotis Mertikopoulos. 2021. Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium. arXiv:2104.12761 [cs math] April arxiv:2104.12761 arXiv: 2104.12761"},{"key":"e_1_3_2_1_35_1","volume-title":"Oct., arxiv:2006.01980 arXiv","author":"Jung Young Hun","year":"2006","unstructured":"Young Hun Jung , Baekjin Kim , and Ambuj Tewari . 2020. On the Equivalence between Online and Private Learnability beyond Binary Classification. arXiv:2006.01980 [cs, stat] , Oct., arxiv:2006.01980 arXiv : 2006 .01980 Young Hun Jung, Baekjin Kim, and Ambuj Tewari. 2020. On the Equivalence between Online and Private Learnability beyond Binary Classification. arXiv:2006.01980 [cs, stat], Oct., arxiv:2006.01980 arXiv: 2006.01980"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"e_1_3_2_1_37_1","unstructured":"Pieter Kleer and Hans Simon. 2021. Primal and Dual Combinatorial Dimensions. arXiv:2108.10037 [cs math] Aug. arxiv:2108.10037 arXiv: 2108.10037  Pieter Kleer and Hans Simon. 2021. Primal and Dual Combinatorial Dimensions. arXiv:2108.10037 [cs math] Aug. arxiv:2108.10037 arXiv: 2108.10037"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22147-7"},{"key":"e_1_3_2_1_39_1","unstructured":"Vladimir Koltchinskii and Dmitry Panchenko. 2004. Rademacher processes and bounding the risk of function learning. arXiv:math\/0405338 May arxiv:math\/0405338 arXiv: math\/0405338  Vladimir Koltchinskii and Dmitry Panchenko. 2004. Rademacher processes and bounding the risk of function learning. arXiv:math\/0405338 May arxiv:math\/0405338 arXiv: math\/0405338"},{"key":"e_1_3_2_1_40_1","unstructured":"Tengyuan Liang Alexander Rakhlin and Karthik Sridharan. 2015. Learning with Square Loss: Localization through Offset Rademacher Complexity. arXiv:1502.06134 [cs math stat] June arxiv:1502.06134 arXiv: 1502.06134  Tengyuan Liang Alexander Rakhlin and Karthik Sridharan. 2015. Learning with Square Loss: Localization through Offset Rademacher Complexity. arXiv:1502.06134 [cs math stat] June arxiv:1502.06134 arXiv: 1502.06134"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022869011914"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1013137"},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of The 27th Conference on Learning Theory. PMLR, 25\u201339","author":"Mendelson Shahar","year":"2014","unstructured":"Shahar Mendelson . 2014 . Learning without concentration . In Proceedings of The 27th Conference on Learning Theory. PMLR, 25\u201339 . https:\/\/proceedings.mlr.press\/v35\/mendelson14.html ISSN: 1938-7228 Shahar Mendelson. 2014. Learning without concentration. In Proceedings of The 27th Conference on Learning Theory. PMLR, 25\u201339. https:\/\/proceedings.mlr.press\/v35\/mendelson14.html ISSN: 1938-7228"},{"key":"e_1_3_2_1_44_1","volume-title":"July, arxiv:1902.04217 arXiv","author":"Montasser Omar","year":"1902","unstructured":"Omar Montasser , Steve Hanneke , and Nathan Srebro . 2019. VC Classes are Adversarially Robustly Learnable, but Only Improperly. arXiv:1902.04217 [cs, stat] , July, arxiv:1902.04217 arXiv : 1902 .04217 Omar Montasser, Steve Hanneke, and Nathan Srebro. 2019. VC Classes are Adversarially Robustly Learnable, but Only Improperly. arXiv:1902.04217 [cs, stat], July, arxiv:1902.04217 arXiv: 1902.04217"},{"key":"e_1_3_2_1_45_1","unstructured":"Alexander Rakhlin Ohad Shamir and Karthik Sridharan. 2012. Relax and Localize: From Value to Algorithms. arXiv:1204.0870 [cs stat] April arxiv:1204.0870 arXiv: 1204.0870  Alexander Rakhlin Ohad Shamir and Karthik Sridharan. 2012. Relax and Localize: From Value to Algorithms. arXiv:1204.0870 [cs stat] April arxiv:1204.0870 arXiv: 1204.0870"},{"key":"e_1_3_2_1_46_1","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2013. Optimization Learning and Games with Predictable Sequences. arXiv:1311.1869 [cs] Nov. arxiv:1311.1869 arXiv: 1311.1869  Alexander Rakhlin and Karthik Sridharan. 2013. Optimization Learning and Games with Predictable Sequences. arXiv:1311.1869 [cs] Nov. arxiv:1311.1869 arXiv: 1311.1869"},{"key":"e_1_3_2_1_47_1","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2014. Online Nonparametric Regression. arXiv:1402.2594 [cs math stat] Feb. arxiv:1402.2594 arXiv: 1402.2594  Alexander Rakhlin and Karthik Sridharan. 2014. Online Nonparametric Regression. arXiv:1402.2594 [cs math stat] Feb. arxiv:1402.2594 arXiv: 1402.2594"},{"key":"e_1_3_2_1_48_1","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2014. Statistical Learning and Sequential Prediction. http:\/\/www.mit.edu\/~rakhlin\/courses\/stat928\/stat928_notes.pdf  Alexander Rakhlin and Karthik Sridharan. 2014. Statistical Learning and Sequential Prediction. http:\/\/www.mit.edu\/~rakhlin\/courses\/stat928\/stat928_notes.pdf"},{"key":"e_1_3_2_1_49_1","volume-title":"Online Learning: Stochastic and Constrained Adversaries. arXiv:1104.5070 [cs, stat], April, arxiv:1104.5070 arXiv: 1104.5070","author":"Rakhlin Alexander","year":"2011","unstructured":"Alexander Rakhlin , Karthik Sridharan , and Ambuj Tewari . 2011 . Online Learning: Stochastic and Constrained Adversaries. arXiv:1104.5070 [cs, stat], April, arxiv:1104.5070 arXiv: 1104.5070 Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. 2011. Online Learning: Stochastic and Constrained Adversaries. arXiv:1104.5070 [cs, stat], April, arxiv:1104.5070 arXiv: 1104.5070"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2789278"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-013-0545-5"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.3150\/14-BEJ679"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Shai Shalev-Shwartz. 2011. Online Learning and Online Convex Optimization. 4 http:\/\/www.nowpublishers.com\/article\/Details\/MAL-018  Shai Shalev-Shwartz. 2011. Online Learning and Online Convex Optimization. 4 http:\/\/www.nowpublishers.com\/article\/Details\/MAL-018","DOI":"10.1561\/9781601985477"},{"key":"e_1_3_2_1_54_1","volume-title":"Proceedings of The 28th Conference on Learning Theory. PMLR, 1552\u20131563","author":"Simon Hans U.","year":"2015","unstructured":"Hans U. Simon . 2015 . An Almost Optimal PAC Algorithm . In Proceedings of The 28th Conference on Learning Theory. PMLR, 1552\u20131563 . https:\/\/proceedings.mlr.press\/v40\/Simon15a.html ISSN: 1938-7228 Hans U. Simon. 2015. An Almost Optimal PAC Algorithm. In Proceedings of The 28th Conference on Learning Theory. PMLR, 1552\u20131563. https:\/\/proceedings.mlr.press\/v40\/Simon15a.html ISSN: 1938-7228"},{"key":"e_1_3_2_1_55_1","unstructured":"Nathan Srebro Karthik Sridharan and Ambuj Tewari. 2012. Optimistic Rates for Learning with a Smooth Loss. arXiv:1009.3896 [cs] Nov. arxiv:1009.3896 arXiv: 1009.3896  Nathan Srebro Karthik Sridharan and Ambuj Tewari. 2012. Optimistic Rates for Learning with a Smooth Loss. arXiv:1009.3896 [cs] Nov. arxiv:1009.3896 arXiv: 1009.3896"},{"key":"e_1_3_2_1_56_1","volume-title":"Schapire","author":"Syrgkanis Vasilis","year":"2015","unstructured":"Vasilis Syrgkanis , Alekh Agarwal , Haipeng Luo , and Robert E . Schapire . 2015 . Fast Convergence of Regularized Learning in Games . arXiv:1507.00407 [cs], Dec., arxiv:1507.00407 arXiv: 1507.00407 Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. 2015. Fast Convergence of Regularized Learning in Games. arXiv:1507.00407 [cs], Dec., arxiv:1507.00407 arXiv: 1507.00407"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2886807"},{"key":"e_1_3_2_1_58_1","volume-title":"Estimation of dependences based on empirical data","author":"Vapnik Vladimir Naumovich","unstructured":"Vladimir Naumovich Vapnik and Samuel Kotz . 2006. Estimation of dependences based on empirical data ( 2 nd ed ed.). Springer , New York . isbn:978-0-387-34239-9 Vladimir Naumovich Vapnik and Samuel Kotz. 2006. Estimation of dependences based on empirical data (2nd ed ed.). Springer, New York. isbn:978-0-387-34239-9","edition":"2"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.2307\/1403814"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/225298.225304"},{"key":"e_1_3_2_1_61_1","volume-title":"Proceedings of Machine Learning Research. 29","author":"Wei Chen-Yu","year":"2018","unstructured":"Chen-Yu Wei and Haipeng Luo . 2018 . More Adaptive Algorithms for Adversarial Bandits . In Proceedings of Machine Learning Research. 29 . Chen-Yu Wei and Haipeng Luo. 2018. More Adaptive Algorithms for Adversarial Bandits. In Proceedings of Machine Learning Research. 29."},{"key":"e_1_3_2_1_62_1","volume-title":"Proceedings of Machine Learning Research. 52","author":"Wei Chen-Yu","year":"2020","unstructured":"Chen-Yu Wei , Haipeng Luo , and Alekh Agarwal . 2020 . Taking a hint: How to leverage loss predictors in contextual bandits? In Proceedings of Machine Learning Research. 52 . Chen-Yu Wei, Haipeng Luo, and Alekh Agarwal. 2020. Taking a hint: How to leverage loss predictors in contextual bandits? In Proceedings of Machine Learning Research. 52."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3519950","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519950","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519950"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":62,"alternative-id":["10.1145\/3519935.3519950","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519950","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"}}]}}