Towards Convergence Rate Analysis of Random Forests for Classification

Random forests have been one of the successful ensemble algorithms in machine learning. The basic idea is to construct a large number of random trees individually and make prediction based on an average of their predictions. The great successes have attracted much attention on the consistency of random forests, mostly focusing on regression. This work takes one step towards convergence rates of random forests for classification. We present the first finite-sample rate O(n {-1/(8d 2)}) on the convergence of pure random forests for classification, which can be improved to be of O(n {-1/(3.87d