Multiclass learning with margin: exponential rates with no bias-variance trade-off

It was recently remarked that the learning curves observed in practice can be quite different from those predicted in theory [21]. In particular, while one might expect performance to degrade as models get larger or less constrained [7], this is in fact not the case. By the no free lunch theorem [19], theoretical results critically depend on the set of assumptions made on the problem. Such assumptions can be hard to verify in practice, hence a possible way to tackle the seeming contradictions in learning theory vs. practice is to consider a wider range of assumptions, and check whether the corresponding results can explain empirical observations. In the context of classification, it is interesting to consider assumptions describing the difficulty of the problem in terms of margin [9, 18]. It is well known that very different learning curves can be obtained depending on the considered margin conditions [2].