Rates of convergence for random forests via generalized U-statistics

DOI10.1214/21-EJS1958zbMATH Open1493.62071arXiv1905.10651OpenAlexW4206811903MaRDI QIDQ2136608FDOQ2136608

Authors: Wei Peng, Tim Coleman, Lucas Mentch 

Publication date: 11 May 2022

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: Random forests remain among the most popular off-the-shelf supervised learning algorithms. Despite their well-documented empirical success, however, until recently, few theoretical results were available to describe their performance and behavior. In this work we push beyond recent work on consistency and asymptotic normality by establishing rates of convergence for random forests and other supervised learning ensembles. We develop the notion of generalized U-statistics and show that within this framework, random forest predictions can potentially remain asymptotically normal for larger subsample sizes than previously established. We also provide Berry-Esseen bounds in order to quantify the rate at which this convergence occurs, making explicit the roles of the subsample size and the number of trees in determining the distribution of random forest predictions.

Full work available at URL: https://arxiv.org/abs/1905.10651

Recommendations

• Towards convergence rate analysis of random forests for classification
• On the asymptotics of random forests
• Strong laws of large numbers for random forests
• Generalized random forests
• On PAC-Bayesian bounds for random forests
• Asymptotic properties of high-dimensional random forests
• On the limiting distribution of the metric dimension for random forests
• Rates of convergence for U-statistic processes and their bootstrapped versions
• Quantifying uncertainty in random forests via confidence intervals and hypothesis tests
• Random forest estimation of conditional distribution functions and conditional quantiles

zbMATH Keywords

random forestsCARTU-statisticsbaggingBerry-Esseen

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Central limit and other weak theorems (60F05) Approximations to statistical distributions (nonasymptotic) (62E17)

Cites Work

• Random survival forests
• Consistency of random forests
• Consistency of random forests and other averaging classifiers
• Title not available (Why is that?)
• Reinforcement learning trees
• Random forests
• Bagging predictors
• Central limit theorems and bootstrap in high dimensions
• Estimation and Inference of Heterogeneous Treatment Effects using Random Forests
• Random Forests and Adaptive Nearest Neighbors
• The jackknife estimate of variance
• Quantifying uncertainty in random forests via confidence intervals and hypothesis tests
• Asymptotic Statistics
• A Class of Statistics with Asymptotically Normal Distribution
• Title not available (Why is that?)
• Quantile regression forests
• Estimation and accuracy after model selection
• Do we need hundreds of classifiers to solve real world classification problems?
• Normal Approximation by Stein’s Method
• Title not available (Why is that?)
• The Accuracy of the Gaussian Approximation to the Sum of Independent Variates
• Title not available (Why is that?)
• Analysis of a random forests model
• Consistency of random survival forests
• Confidence sets for split points in decision trees
• Normal approximation under local dependence.
• Convergence rates for U-statistics and related statistics
• The Theory of Unbiased Estimation
• On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification
• A non-uniform Berry-Esseen bound via Stein's method
• Lectures on the nearest neighbor method
• On the Berry-Esseen theorem for U-statistics
• The Berry-Esseen theorem for U-statistics
• The collected works of Wassily Hoeffding. Ed. by N. I. Fisher and P. K. Sen
• Estimating a sharp convergence bound for randomized ensembles
• A random forest guided tour
• Random Forests and Kernel Methods
• CLT For U-statistics With Growing Dimension
• Title not available (Why is that?)
• The effect of splitting on random forests
• Approximating high-dimensional infinite-order \(U\)-statistics: statistical and computational guarantees
• Randomized incomplete \(U\)-statistics in high dimensions
• Title not available (Why is that?)

Cited In (10)

• Uniform consistency and uniform in number of neighbors consistency for nonparametric regression estimates and conditional \(U\)-statistics involving functional data
• Minimax optimal rates for Mondrian trees and forests
• On the asymptotics of random forests
• On the variable bandwidth kernel estimation of conditional \(U\)-statistics at optimal rates in sup-norm
• Estimating a sharp convergence bound for randomized ensembles
• Weak convergence of the conditional U-statistics for locally stationary functional time series
• Quantifying uncertainty of subsampling-based ensemble methods under a U-statistic framework
• Renewal type bootstrap for increasing degree \(U\)-process of a Markov chain
• On variance estimation of random forests with Infinite-order U-statistics
• Limit theorems for a class of processes generalizing the U -empirical process

This page was built for publication: Rates of convergence for random forests via generalized U-statistics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136608)