How quickly can functions in a given class be learned from data? It is common to measure the performance of a supervised machine learning algorithm by plotting its "learning curve", that is, the decay of the classification risk (or "error rate") as a function of the number of training samples. However, the classical theoretical framework for understanding optimal rates of convergence of the risk...