Fast rates for prediction with costly or limited expert advice | Prof. Gilles Blanchard, Université Paris Saclay

Organizer : Prof. Dr. Thorsten Dickhaus
Location : MZH 5600
Start Time : 13. June 2023, 16:00
End Time : 13. June 2023, 18:00

We consider the problem of prediction with the help of experts: given a finite family of experts, or predictors, for forecasting a target variable of interest, we consider the problem of minimizing the excess error with respect to the best expert, also called /regret/. The prediction skills of the individual experts may be very variable and are not known a priori. We will first review classical results under full information in the stochastic setting (repeated target variable and expert predictions are assumed random and independent across time), and when the goal concerns prediction of a single new instance ("test phase") after a certain number of "training" or "learning" rounds. It is known in this case that under some suitable assumptions on the prediction loss, it is possible to get "fast" decay of the regret (in expectation and with large probability), namely of order 1/N where N is the number of observations (training rounds). We will study the possibility of fast rates under the additional constraint that the number of experts consulted each round is limited, or that there is a limited total "expert query budget" for the learning phase. We show that if we are allowed to pick and see the advice of only a single expert per round for N rounds in the training phase, or to use the advice of only one expert for prediction in the test phase, the worst-case regret in the prediction phase must have a "slow rate" (1/sqrt(N)) at best. However, it is sufficient that we are allowed to observe at least two actively chosen experts per training round and use at least two experts for prediction, for the "fast rate" of order 1/N to be achievable. Given time, we will also discuss a similar question in the setting of individual sequence prediction, the goal then being to minimize cumulated regret over a sequence of observation/prediction rounds. This is joint work with El Mehdi Saad.

Link to the original post.