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 @math , where @math is the loss function and @math is the hypothesis class, exists and is @math -integrable, and (ii) @math satisfies the multi-scale Bernstein's condition on @math . Under these assumptions, we prove that learning rate faster than @math can be obtained and, depending on @math and the multi-scale Bernstein's powers, can be arbitrarily close to @math . We then verify these assumptions and derive fast learning rates for the problem of vector quantization by @math -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.
Theorem @math dictates that under our settings, the problem of learning with heavy-tailed losses can obtain convergence rates up to order where @math is the multi-scale Bernstein's order and @math is the degree of integrability of the loss. We recall that convergence rate of @math is obtained in @cite_10 under the same setting but for bounded losses. (The analysis there was done under the @math -weakly stochastic mixability condition, which is equivalent with the standard @math -Bernstein's condition for bounded losses ). We note that if the loss is bounded, @math and @math reduces to the convergence rate obtained in @cite_10 .
@cite_10
2132046078
Empirical risk minimization (ERM) is a fundamental learning rule for statistical learning problems where the data is generated according to some unknown distribution P and returns a hypothesis f chosen from a fixed class ℱ with small loss l. In the parametric setting, depending upon (l, ℱ, P) ERM can have slow (1 √n) or fast (1 n) rates of convergence of the excess risk as a function of the sample size n. There exist several results that give sufficient conditions for fast rates in terms of joint properties of l, ℱ, and P, such as the margin condition and the Bernstein condition. In the non-statistical prediction with expert advice setting, there is an analogous slow and fast rate phenomenon, and it is entirely characterized in terms of the mixability of the loss l (there being no role there for ℱ or P). The notion of stochastic mixability builds a bridge between these two models of learning, reducing to classical mixability in a special case. The present paper presents a direct proof of fast rates for ERM in terms of stochastic mixability of (l, ℱ, P), and in so doing provides new insight into the fast-rates phenomenon. The proof exploits an old result of Kemperman on the solution to the general moment problem. We also show a partial converse that suggests a characterization of fast rates for ERM in terms of stochastic mixability is possible.