# Rate of convergence - comparison of supervised ML methods

I am working on a project with sparse labelled datasets, and am looking for references regarding the rate of convergence of different supervised ML techniques with respect to dataset size.

I know that in general boosting algorithms, and other models that can be found in Scikit-learn like SVM's, converge faster than neural networks. However, I cannot find any academic papers that explore, empirically or theoretically, the difference in how much data different methods need before they reach n% accuracy. I only know this from experience and various blog posts.

For this question I am ignoring semi-supervised and weakly supervised methods. I am also ignoring transfer learning.

This is a pretty involved question since this is an active area of research. The first statement is that often, the architecture is important (or number of parameters) before we can say something to the effect of we require $$O(n^{k} log(\frac{1}{\delta^i}))$$ for $$i, k \ge 1$$ samples to converge to a local optima. Guaranteeing accuracy is also depending on the data, so it is likely specific to what the data is itself. So you can break your question down into the analysis of stochastic gradient descent and the analysis of it in the context of neural networks. Unfortunately, neither of these deal with specific datasets, so your question about wanting accuracy $$\ge n$$ is still not possible with such a claim. To the best of my knowledge I am not familiar with claims made along that direction, however, with the former (analysis of SGD/specific neural architectures), there are some claims and papers that I can link below.
2. On the rate of convergence of fully connected very deep neural network regression estimates -- This paper deals with a specific loss function not often found in classification ($$\ell_2$$ norm between the predictions and targets) but might serve as a useful reference. (https://arxiv.org/abs/1908.11133)