  We investigate the problem of minimizing the excess generalization error with
respect to the best expert prediction in a finite family in the stochastic
setting, under limited access to information. We assume that the learner only
has access to a limited number of expert advices per training round, as well as
for prediction. Assuming that the loss function is Lipschitz and strongly
convex, 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
$\Omega$(1/ $\sqrt$ T) with probability lower bounded by a constant. However,
if we are allowed to see at least two actively chosen expert advices per
training round and use at least two experts for prediction, the fast rate
O(1/T) can be achieved. We design novel algorithms achieving this rate in this
setting, and in the setting where the learner has a budget constraint on the
total number of observed expert advices, and give precise instance-dependent
bounds on the number of training rounds and queries needed to achieve a given
generalization error precision.
