Optimal randomized proper online learning

Seminar
Speaker
Idan Mehalel (Hebrew University of Jerusalem)
Date
22/11/2026 - 15:15 - 14:05Add to Calendar 2026-11-22 14:05:00 2026-11-22 15:15:00 Optimal randomized proper online learning Littlestone's realizable online learning model is fundamental in learning theory. It asks what is the number of mistakes that an optimal learner makes in the following simple game. Given a public class H of functions from a domain X to {0,1}, an adversary secretly chooses a single target h* from H and a sequence x_1,x_2,...,x_T of instances from X. In every round t, the learner picks a function f_t from X to {0,1} with the goal of satisfying f_t(x_t) = h*(x_t). Only after choosing f_t, the labeled example (x_t ,h*(x_t)) is revealed to the learner.It is well-known that the optimal mistake bound in this setting is L(H), where L(H) denotes the Littlestone dimension of H. Perhaps surprisingly, the known optimal learner achieving this mistake bound is improper: it may choose f_t that does not belong to H. Even more surprisingly, proper online learning, in which f_t must belong to H, is known to be impossible for some classes when using deterministic learners. While proper learning is well-understood in the statistical PAC learning setting, this was not the case for (randomized) proper online learning -- until recently. The best known upper bound on the expected mistake bound, given in [Daskalakis and Golowich, STOC 2022], was O(L(H) log^6 (T)), and the best known lower bound was of order L(H).In this talk, I will present a new upper bound of O(L(H) log (T)), which is also proved to be tight for worst-case classes. The result hinges on a novel combinatorial dichotomy for Littlestone classes: every class either admits a good approximation of the known improper optimal learner, or can be covered by a small collection of lower dimensional classes.Based on a joint work with Zachary Chase. zoom אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
zoom
Abstract

Littlestone's realizable online learning model is fundamental in learning theory. It asks what is the number of mistakes that an optimal learner makes in the following simple game. Given a public class H of functions from a domain X to {0,1}, an adversary secretly chooses a single target h* from H and a sequence x_1,x_2,...,x_T of instances from X. In every round t, the learner picks a function f_t from X to {0,1} with the goal of satisfying f_t(x_t) = h*(x_t). Only after choosing f_t, the labeled example (x_t ,h*(x_t)) is revealed to the learner.

It is well-known that the optimal mistake bound in this setting is L(H), where L(H) denotes the Littlestone dimension of H. Perhaps surprisingly, the known optimal learner achieving this mistake bound is improper: it may choose f_t that does not belong to H. Even more surprisingly, proper online learning, in which f_t must belong to H, is known to be impossible for some classes when using deterministic learners. While proper learning is well-understood in the statistical PAC learning setting, this was not the case for (randomized) proper online learning -- until recently. The best known upper bound on the expected mistake bound, given in [Daskalakis and Golowich, STOC 2022], was O(L(H) log^6 (T)), and the best known lower bound was of order L(H).

In this talk, I will present a new upper bound of O(L(H) log (T)), which is also proved to be tight for worst-case classes. The result hinges on a novel combinatorial dichotomy for Littlestone classes: every class either admits a good approximation of the known improper optimal learner, or can be covered by a small collection of lower dimensional classes.

Based on a joint work with Zachary Chase.

תאריך עדכון אחרון : 17/11/2026