Minimax Rates and Spectral Distillation for Tree Ensembles
Binh Duc Vu, David S. Watson · 2026
Read Minimax Rates and Spectral Distillation for Tree Ensembles by Binh Duc Vu, David S. Watson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11841.txt.
Introduction
Binh Duc Vu and David Watson take a spectral view of tree ensembles such as random forests and gradient boosting systems. They derive minimax-optimal rates for random forest regression, showing the eigenvalue decay of the induced kernel governs the learning rate. They then compress these groups by learning curved maps of leading eigenfunctions or leading vectors, yielding shrunk models far smaller that keep strong forecast quality.
Catalog record
| CREATOR | Binh Duc Vu, David S. Watson |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99563 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11841
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Minimax Rates and Spectral Distillation for Tree Ensembles Binh Duc Vu, David S. Watson Abstract Tree ensembles such as random forests (RFs) and gradient boosting machines (GBMs) are among the most widely used supervised learners, yet their theoretical properties remain incompletely understood. We adopt a spectral perspective on these algorithms, with two main contributions. First, we derive minimax-optimal convergence for RF regression, showing that, under mild regularity conditions on tree growth, the eigenvalue decay of the induced kernel operator governs the statistical rate. Second, we exploit this spectral viewpoint to develop compression schemes for tree ensembles. For RFs, leading eigenfunctions of the kernel operator capture the dominant predictive directions; for GBMs, leading singular vectors of the smoother matrix play an analogous role. Learning nonlinear maps for these spectral representations yields distilled models that are orders of magnitude smaller than the originals while maintaining competitive predictive performance. Our methods compare favorably to state of the art algorithms for forest pruning and rule extraction, with applications to resource constrained computing. 1 Introduction Tree ensembles such as random forests (RFs) and gradient boosting machines (GBMs) are among the most popular and versatile supervised learning algorithms. Fast and easy to use, trees regularly attain state of the art results in tabular data tasks [ 35 , 69 ] , often beating out deep learning models that have proven more effective for image and language processing. Trees are especially good at adapting to sparse signals, making them a common choice in high-dimensional domains where parametric methods may struggle, such as bioinformatics [ 48 ] , econometrics [ 2 ] , and engineering [ 68 ] . Despite their prevalence, tree ensembles remain poorly understood at a theoretical level. For RFs, most authors focus on idealized variants such as purely random forests [ 15 , 34 , 10 , 46 ] , which make analysis more tractable but sacrifice the adaptive splitting that drives empirical performance. Finite sample generalization guarantees remain rare, and existing results do little to explain the effectiveness of standard greedy splits. For GBMs, the situation is arguably worse: while boosting theory is well developed in the classification setting [ 63 , 18 , 3 ] , the specific inductive bias of tree-based gradient boosting—and in particular, how ensemble size interacts with tree complexity—lacks a comparably sharp characterization. We adopt a spectral perspective that addresses both algorithms. For RFs, we work in the kernel tradition [ 15 , 23 , 67 ] , showing that the eigenvalue decay of the integral operator induced by the RF kernel governs the statistical rate. Our main theoretical result is minimax optimality for an algorithm that closely approximates the original method of 16 , affirmatively resolving a long open question in the literature. The proof sheds light on how greedy splits inherently adapt to sparse signals, connecting algorithmic hyperparameters to the spectral geometry of the induced kernel. Taking this spectral viewpoint, we observe that the principal eigenvectors of the RF kernel operator capture the most informative dimensions of the model. GBMs, by contrast, do not admit a kernel representation, but an analogous compression scheme is achievable via the singular value decomposition of its implicit smoother matrix [ 22 ] . In both cases, models can be distilled by learning the nonlinear mapping from the input space to an appropriate spectral representation. Since a few leading modes capture most of the problem’s variance, the resulting models maintain competitive performance while being significantly smaller and faster than the originals, thus enabling deployment on resource-constrained devices where full ensembles are infeasible. Crucially, while previous methods require users to set an accuracy tolerance—leaving the final model size unpredictable—our method allows the size to be set explicitly. This provides a practical solution for deployment with strict memory budgets while remaining competitive on the empirical rate-distortion Pareto frontier. The remainder of this paper is structured as follows. We review related work in Sect. 2 . Following a brief summary of our setup and assumptions in Sect. 3 , we state our main theoretical result in Sect. 4 . This motivates a distillation scheme for tree ensembles, which we describe in Sect. 5 . Empirical results are presented in Sect. 6 , including extensive benchmarks against state of the art methods. A brief discussion follows in Sect. 7 . Sect. 8 concludes. 2 Related Work RF Theory For good overviews of RF theory, see [ 9 , 65 ] . Early work in this area tended to prioritize asymptotic consistency results [ 17 , 54 , 7 , 8 , 34 , 64 ] , often under simplifying assumptions. Convergence rates are generally harder to come by, though some authors have established PAC-Bayes bounds for RFs [ 53 ] and finite sample results for classification [ 33 , 32 ] . Minimax convergence, a common optimality target in nonparametric regression, has so far proven elusive. Suboptimal rates have been derived for non-adaptive [ 46 ] and adaptive RFs [ 45 ] . An online variant of the RF algorithm known as Mondrian forests [ 47 ] are known to be minimax optimal [ 56 , 57 ] , as are so-called tessellation forests [ 58 ] , which use oblique splits. However, the split mechanism in both cases is non-adaptive, and so these results do little to explain the performance of standard RFs, which clearly benefit from their greedy optimization objective. Our theoretical approach differs markedly from previous work in this area. Classical minimax results assume that the sampling distribution is dominated by some reference measure over the input space \mathbb{R}^{d} , giving rates that scale poorly with data dimensionality [ 72 ] . However, in high-dimensional settings, data are often concentrated on a low-dimensional manifold [ 6 ] . Algorithms that can adapt to such sparse structures often converge far faster than theory would suggest. Building on this insight, several authors have taken a spectral approach to kernel regression, deriving novel minimax rates under a source condition and assumptions on eigenvalue decay [ 20 , 11 , 60 , 79 ] . We adapt these results to the RF context, establishing the minimax optimality of an adaptive RF algorithm. Ensemble compression Pruning methods for tree ensembles selectively remove splits or entire trees from the forest. This tradition goes back to the original CART algorithm, where truncating depth was proposed as a form of tree regularization [ 14 ] . Numerous ensemble variants have been developed since [ 71 ] , notably including Leaf Refinement with L_{1} pruning (LRL1) [ 19 ] , which aims to drop redundant trees; and ForestPrune (FP) [ 52 ] , which optimizes tree depth on a per-tree basis. Though FP generally compresses better than LRL1, it produces symmetric trees by default, which may be suboptimal in some settings. Building on these methods, 25 propose Level-wise Optimization and Pruning (LOP), which traverses the ensemble by tree depth, optimizing a global L_{1} -regularized objective to simultaneously prune subtrees and update leaf predictions. These methods generally fix an error tolerance upfront and minimize model size subject to this budget. Distillation approaches, by contrast, typically fix a target size upfront and minimize error subject to a budget on the compression rate. The