ICCHA2022

8th International Conference on
Computational Harmonic Analysis

September 12-16, 2022

In the last years, Deep Learning has led to a number of breakthroughs in diverse areas of machine learning, and especially in classification problems such as in image classification. For a certain model class of classification problems, this paper analyzes the optimal decay of the generalization error depending on the number of training samples. Precisely, we consider classification problems in which the decision boundary between the different classes has a given regularity, for instance $C^k$ regularity or Barron regularity. We precisely determine (up to log factors) the minimax rates for learning an unknown function from this class based on noiseless training samples, where we allow an arbitrary learning procedure, not necessarily based on neural networks. For classifiers with Barron-regular decision boundaries, the derived rates do not deteriorate with the ambient dimension, and can be (essentially) attained by empirical Hinge-loss minimization over a suitable class of ReLU networks. In particular, these neural networks can overcome the curse of dimensionality for these functions.