Fast Rate Conditions in Statistical Learning (MSc Practice talk) ---- Muriel Perez

We study conditions under which the order of convergence of
algorithms in statistical learning can be improved from
$O_P(n^{-1/2})$ to $O_P(n^{-1})$ (up to logarithmic factors)
in the number of data points. If excess losses are bounded, it is
known that two conditions, called Bernstein's and strong central
condition, are equivalent and lead to fast rates both for Empirical
Risk Minimization and for randomized algorithms. If the excess
losses are unbounded, they are no longer equivalent and are known to
lead to faster rates either under additional assumptions or for
specific randomized algorithms. We investigate their relation in the
unbounded case and show weak, realistic assumptions under which they
become equivalent. Furthermore, in this regime we show tighter
bounds than those presented in the literature.