Rates of convergence for random forests via generalized U-statistics

DOI10.1214/21-EJS1958zbMATH Open1493.62071OpenAlexW4206811903MaRDI 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

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

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)