  We develop minimax optimal risk bounds for the general learning task
consisting in predicting as well as the best function in a reference set
$\mathcal{G}$ up to the smallest possible additive term, called the convergence
rate. When the reference set is finite and when $n$ denotes the size of the
training data, we provide minimax convergence rates of the form
$C(\frac{\log|\mathcal{G}|}{n})^v$ with tight evaluation of the positive
constant $C$ and with exact $0<v\le1$, the latter value depending on the
convexity of the loss function and on the level of noise in the output
distribution. The risk upper bounds are based on a sequential randomized
algorithm, which at each step concentrates on functions having both low risk
and low variance with respect to the previous step prediction function. Our
analysis puts forward the links between the probabilistic and worst-case
viewpoints, and allows to obtain risk bounds unachievable with the standard
statistical learning approach. One of the key ideas of this work is to use
probabilistic inequalities with respect to appropriate (Gibbs) distributions on
the prediction function space instead of using them with respect to the
distribution generating the data. The risk lower bounds are based on
refinements of the Assouad lemma taking particularly into account the
properties of the loss function. Our key example to illustrate the upper and
lower bounds is to consider the $L_q$-regression setting for which an
exhaustive analysis of the convergence rates is given while $q$ ranges in
$[1;+\infty[$.
