From Stochastic Mixability to Fast Rates
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 F with small loss . In the parametric setting, depending upon ( , F, 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 , F, 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 (there being no role there for F 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 ( , F, 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.
This paper shows how to obtain fast rates for ERM from a very general assumption known as "stochastic mixability".The paper is clear, well-written, well-motivated, well-referenced, and presents a solid technical contribution.Specific comments:- in Sec. 2.1: the loss is assumed to be Lipschitz, so presumably this would not apply to classification problems with 0-1 loss.It should be made more clear that only "regression"-type learning problems are being considered.Also, F is stipulated as being compact, yet no metric/norm/topology is specified. An expert will infer that the norm in questionis L_1(P) --- which is vindicated by the covering numbers defined in Sec. 4. But the topology should be specified before compactnessis mentioned.- in Sec. 2.4, there is some inconsistency of notation between E Z_f and P Z_f. Either is fine, but please be consistent (or pointout the difference if the two are distinct). Finally, on the issue of bounded losses, which the authors bring up as an assumption to relax in the future, please take a look atA. Kontorovich: Concentration in unbounded metric spaces and algorithmic stability, ICML 2014and the numerous references therein.