{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:35:40Z","timestamp":1787340940880,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"Israel PBC-VATAT"},{"name":"Technion Center for Machine Learning and Intelligent System"},{"DOI":"10.13039\/501100005155","name":"Azrieli Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005155","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101039692"],"award-info":[{"award-number":["101039692"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1225\/20"],"award-info":[{"award-number":["1225\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018385"],"award-info":[{"award-number":["2018385"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone \u201988). We prove an analogous result for randomized learners: we show that the optimal expected mistake bound in learning a class [Formula: see text] equals its randomized Littlestone dimension, which we define as follows: it is the largest [Formula: see text] for which there exists a tree shattered by [Formula: see text] whose average depth is [Formula: see text]. We further study optimal mistake bounds in the agnostic case, as a function of the number of mistakes made by the best function in [Formula: see text], denoted by [Formula: see text]. Towards this end we introduce the [Formula: see text]-Littlestone dimension and its randomized variant, and use them to characterize the optimal deterministic and randomized mistake bounds. Quantitatively, we show that the optimal randomized mistake bound for learning a class with Littlestone dimension [Formula: see text] is [Formula: see text] (equivalently, the optimal regret is [Formula: see text]). This also implies an optimal deterministic mistake bound of [Formula: see text], thus resolving an open question which was studied by Auer and Long [\u201999]. As an application of our theory, we revisit the classical problem of prediction using expert advice: about 30 years ago Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire, and Warmuth studied prediction using expert advice, provided that the best among the [Formula: see text] experts makes at most [Formula: see text] mistakes, and asked what are the optimal mistake bounds (as a function of [Formula: see text] and [Formula: see text]). Cesa-Bianchi, Freund, Helmbold, and Warmuth [\u201993, \u201996] provided a nearly optimal bound for deterministic learners, and left the randomized case as an open problem. We resolve this question by providing an optimal learning rule in the randomized case and showing that its expected mistake bound equals half of the deterministic bound of Cesa-Bianchi et\u00a0al. [\u201993, \u201996], up to negligible additive terms. In contrast with previous works by Abernethy, Langford, and Warmuth [\u201906] and by Br\u00e2nzei and Peres [\u201919], our result applies to all pairs [Formula: see text], and does so via a unified analysis using the randomized Littlestone dimension. In our proofs we develop and use optimal learning rules, which can be seen as natural variants of the standard optimal algorithm ([Formula: see text]) of Littlestone: a weighted variant in the agnostic case, and a probabilistic variant in the randomized case. We conclude the paper with suggested directions for future research and open questions.<\/jats:p>","DOI":"10.1137\/23m159915x","type":"journal-article","created":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T07:53:43Z","timestamp":1760601223000},"page":"1386-1425","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension"],"prefix":"10.1137","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1739-0872","authenticated-orcid":true,"given":"Yuval","family":"Filmus","sequence":"first","affiliation":[{"name":"The Henry and Marilyn Taub Faculty of Computer Science, Technion, Israel."},{"name":"Faculty of Mathematics, Technion, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steve","family":"Hanneke","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Purdue University, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8751-7816","authenticated-orcid":true,"given":"Idan","family":"Mehalel","sequence":"additional","affiliation":[{"name":"The Henry and Marilyn Taub Faculty of Computer Science, Technion, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"The Henry and Marilyn Taub Faculty of Computer Science, Technion, Israel."},{"name":"Faculty of Mathematics, Technion, Israel."},{"name":"Google Research, Israels."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,10,16]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"N. Alon, O. Ben-Eliezer, Y. Dagan, S. Moran, M. Naor, and E. Yogev, Adversarial laws of large numbers and optimal regret in online classification, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 447\u2013455.","DOI":"10.1145\/3406325.3451041"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/3526074"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007614417594"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"J. Abernethy, J. Langford, and M. K. Warmuth, Continuous experts and the binning algorithm, in International Conference on Computational Learning Theory, Springer, 2006, pp. 544\u2013558.","DOI":"10.1007\/11776420_40"},{"key":"ref5","unstructured":"J. Abernethy, M. K. Warmuth, and J. Yellin, Optimal strategies from random walks, in Proceedings of The 21st Annual Conference on Learning Theory, 2008, pp. 437\u2013446."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff, A Characterization of Multiclass Learnability, https:\/\/arxiv.org\/abs\/2203.01550, 2022.","DOI":"10.1109\/FOCS54457.2022.00093"},{"key":"ref7","volume-title":"COLT","author":"Ben-David S.","year":"2009"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"ref9","first-page":"1","volume":"20","author":"Beimel A.","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1818908116"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258179"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018348209754"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921"},{"key":"ref14","volume-title":"Covering Codes","author":"Cohen G.","year":"1997"},{"key":"ref15","unstructured":"T. Cover, Behavior of sequential predictors of binary sequences, in Proc. of the 4th Prague Conference on Information Theory, Statistical Decision Functions and Random Processes, Publishing House of the Czechoslovak Academy of Sciences, 1965, pp. 263\u2013272."},{"key":"ref16","volume-title":"Stochastic Processes","author":"Doob J. L.","year":"1953"},{"key":"ref17","first-page":"287","volume-title":"COLT","author":"Daniely A.","year":"2014"},{"key":"ref18","unstructured":"V. Feldman, A general characterization of the statistical query complexity, in Proceedings of the 30th Conference on Learning Theory, COLT 2017, Proceedings of Machine Learning Research 65, S. Kale and O. Shamir, eds. PMLR, Amsterdam, The Netherlands, 2017, pp. 785\u2013830, http:\/\/proceedings.mlr.press\/v65\/feldman17c.html."},{"key":"ref19","unstructured":"Y. Filmus, S. Hanneke, I. Mehalel, and S. Moran, Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension, preprint, 2022, https:\/\/technionmail-my.sharepoint.com\/:b:\/g\/personal\/yuvalfi_technion_ac_il\/Eb0yAGvdYnBIlZl2fT0DIVIB4lFRF4MisFbcxYSa8sDXQQ?e=KHoiNS."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/140991844"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"N. Gravin, Y. Peres, and B. Sivan, Towards optimal algorithms for prediction with expert advice, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2016, pp. 528\u2013547.","DOI":"10.1137\/1.9781611974331.ch39"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1561\/2200000037"},{"key":"ref24","unstructured":"E. Hazan, Introduction to Online Convex Optimization, preprint, arXiv:1909.05207, 2019."},{"key":"ref25","first-page":"3487","volume":"16","author":"Hanneke S.","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.40"},{"key":"ref27","unstructured":"W. M. Koolen and T. van Erven, Second-order quantile methods for experts and combinatorial games, in Proceedings of the 28th Conference on Learning Theory, 2015."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022869011914"},{"key":"ref29","unstructured":"H. Luo and R. Schapire, Towards minimax online learning with unknown time horizon, in International Conference on Machine Learning, PMLR, 2014, pp. 226\u2013234."},{"key":"ref30","volume":"27","author":"Luo H.","year":"2014","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.04.004"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022605311895"},{"key":"ref34","unstructured":"A. Rakhlin and K. Sridharan, Online non-parametric regression, in Conference on Learning Theory, PMLR, 2014, pp. 1232\u20131264."},{"key":"ref35","volume":"25","author":"Rakhlin A.","year":"2012","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"ref38","volume-title":"Theory of Pattern Recognition","author":"Vapnik V.","year":"1974"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"V. G. Vovk, Aggregating strategies, in Proc. of Computational Learning Theory, 1990, 1990.","DOI":"10.1016\/B978-1-55860-146-8.50032-1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M159915X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:57Z","timestamp":1787338617000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M159915X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,16]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1137\/23M159915X"],"URL":"https:\/\/doi.org\/10.1137\/23m159915x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,16]]}}}