MICS Seminar: El Mehdi Saad

Model selection aggregation problem consists in combining predictions from a family of K experts, in a way to guarantee a performance as good as the best expert in the finite family up to a small remainder additive term known as the excess generalization error. We consider the last problem in two primary settings. First, We investigate the problem of minimizing the excess generalization error, in the stochastic setting, under limited access to information. We assume that the learner only has access to a limited number of expert advice per training round, as well as for prediction. Given that the loss function satisfies a convexity assumption, we show that if we are allowed to see the advice of only one expert per round for T rounds in the training phase, or to use the advice of only one expert for prediction in the test phase, the worst-case excess risk is O((1/\sqrt(T)) with probability lower bounded by a constant. However, if we are allowed to see at least two actively chosen expert advice per training round and use at least two experts for prediction, the fast rate of O(1/T) can be achieved.

Secondly, We investigate the problem of cumulative regret minimization for individual sequence prediction with respect to the best expert in a finite family of size K under limited access to information. We assume that in each round, the learner can predict using a convex combination of at most p experts for prediction, then they can observe a posteriori the losses of at most m experts. We show that achieving a constant cumulative regret bound requires combining at least two experts per round for prediction and observing the feedback of at least two experts.