The Taub Faculty of Computer Science Events and Talks

Suppose that n forecasting experts (or functions) are providing daily rain/no-rain predictions, and the best among them is mistaken in at most k many days. For how many days will a person allowed to observe the predictions, but has no weather-forecasting prior knowledge, mispredict?

In this talk, we will discuss how such classical problems can be reduced to calculating the (average) depth of binary trees, by using newly introduced complexity measures (aka dimensions) of the set of experts/functions. All of those measures are variations of the classical Littlestone dimension (Littlestone ’88).

For the forecasting problem outlined above, Cesa-Bianchi, Freund, Helmbold, and Warmuth [’93, ’96] provided a nearly optimal bound for deterministic learners, and left the randomized case as an open problem. We resolve this problem by providing an optimal randomized learner, and showing that its expected mistake bound equals half of the deterministic bound of Cesa-Bianchi et al., up to negligible additive terms.

For general (possibly infinite) function classes, we show that the optimal expected regret (= #mistakes – k) when learning a function class with Littlestone dimension d is of order d + (kd)^0.5.

Based on a joint work with Yuval Filmus, Steve Hanneke, and Shay Moran.