Fast learning rates with heavy-tailed losses
We study fast learning rates when the losses are not necessarily bounded and may have a distribution with heavy tails. To enable such analyses, we introduce two new conditions: (i) the envelope function sup f ∈F | • f |, where is the loss function and F is the hypothesis class, exists and is L r -integrable, and (ii) satisfies the multi-scale Bernstein's condition on F. Under these assumptions, we prove that learning rate faster than O(n −1/2 ) can be obtained and, depending on r and the multi-scale Bernstein's powers, can be arbitrarily close to O(n −1 ). We then verify these assumptions and derive fast learning rates for the problem of vector quantization by k-means clustering with heavy-tailed distributions. The analyses enable us to obtain novel learning rates that extend and complement existing results in the literature from both theoretical and practical viewpoints.
This paper gives learning bounds with heavy-tailed losses in hypothesis classes with logarithmic entropy numbers. If the r-th moment of the supremum loss over all hypotheses in the class is integrable  and a  'multiscale Bernstein condition' holds then fast rates ( close to O(n^{-1}) ) can be obtained. 
This paper provides some new results in an important area which is receiving more and more attention: fast rates when loss functions are unbounded and heavy-tailed. Existing results based on empirical process theory often rely on bounded or sub-Gaussian loss, and the heavy tails (hence non-sub-Gaussian) case is considerably harder.  The results presented seem sound and are definitely novel. They rely on results of Sara van de Geer and collaborators on concentration inequalities for unbounded empirical processes. The  material is very technical and I would suggest moving even some more material to the appendix. This would allow you to include more extensive discussion of some points:   The multiscale Bernstein condition is novel and crucial and I would like to see a simple example to explain the difference between the microscopic and macroscopic scales that the authors talk about (the k-means example is nice and really illustrates that the approach is useful,  but it didn't really make the intuition of/need for  multiscale Bernstein clear to me). In this respect it is of interest that Audibert (Fast Learning Rates..., Annals of Statistics, 2009) shows that a simple , standard Bernstein condition is enough to get fast rates, even for unbounded losses (and it appears even for heavy-tailed losses), if one uses a pseudo-Bayesian estimator with online-to-batch conversion. The authors of the present  paper essentially prove uniform convergence rates for the whole class {\cal F}, which implies that e.g. ERM will attain these rates, so it's different from Audibert who uses a very specific  randomized estimator and measures error by the expected error according to the predictor's randomization. Nevertheless, it suggests that the multi-scale may perhaps not be necessary, so I would like to some more (informal) explanation of why the authors need it. Do they think it may be dispensed with? (the authors should most definitely check out Audibert's paper. Note that with 'improper learners' that adopt a hypothesis outside the assumed class one can often get better rates, but Audibert 'merely' randomizes estimators).  There's also a very recent paper by Mehta and Grunwald (Fast Rates for Unbounded Losses, Arxiv, 2016) where results are proved that are similar in spirit, although the conditions are quite different (yet they seem 'analogous'): instead of the existence-of-moments-of-envelope condition, there is a 'witness condition',  and instead of a multiscale Bernstein condition, there is the v-PPC condition (for bounded losses, both multiscale Bernstein and v-PPC  conditions are equivalent to the standard Bernstein/central condition; for unbounded losses they seem VERY different). It would be good if the authors could provide some discussion on the relation between these papers (though I concede this does not seem easy; proof techniques are quite different).   I would also like to see an explanation of why the approach does not immediately generalize to polynomial entropy numbers. You use chaining in the proofs, so superficially it seems as if the approach would be amenable to larger entropy numbers. You very briefly say in the conclusion that you expect that you can extend it (BTW 'polynomial' there should be 'logarithmic'!)  but why isn't the generalization immediate?   It should also be pointed out explicitly that the in-probablity results are polynomial and not logarithmic in \delta. This is presumably unavoidable with heavy tails, but it  is different from what's normally proved in learning theory - see also the paper by Sabato and Hsu (2015).   But let me emphasize that the main results here are quite different from those by Audibert/Grunwald&Mehta/Sabato&Su, and given the challenging nature of this area I do recommend acceptance.    Minor issues:  The abstract is longer than necessary 'weak-tailed' (beneath Lemma 2.1) is not standard terminology Section 3.4: \gamma-stochastic mixability should be 1-\gamma stochastic mixability (at least that's what I get form Van Erven et al. 2015, I did not check the Mehta&Williamson paper).  Thm 4.2, fine -> finite, minimizer -> minimizesrs References: many et al's which should not be there