Research map / Learning theory and algorithms / Matrix and tensor methods

Minimax Rates and Spectral Distillation for Tree Ensembles

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Structured low-rank learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows minimax-optimal rates for random forest regression under polynomial kernel eigendecay and distills RFs and GBMs into small spectral-embedding MLPs (SCATE) that beat pruning and rule-extraction baselines at 10KB/100KB.

Problem

Tree ensembles lack sharp theory for adaptive random forests (no minimax rates) and GBMs, and existing compression methods either fix an error tolerance (so size is unpredictable) or are dominated on rate-performance trade-offs at tight memory budgets.

Approach

Treat the RF kernel operator (and the GBM smoother matrix via SVD) as the primary object: polynomial eigendecay yields minimax RF rates, and a small MLP is trained to reproduce the leading eigenfunctions/singular vectors weighted by squared eigenvalues, giving a fixed-size distilled model.

Key results

• At 10KB, SCATE achieves the best average rank (1.77) for RF compression, versus 3.47 for LOP and 4.8 for FP.
• At 100KB, SCATE achieves the best average rank (1.93) for RF compression, with FP-SCATE second (2.47).
• For GBM compression, SCATE ties for best average rank (2.13) at both 10KB and 100KB sizes.

Surprising findings

• FP-SCATE declines markedly when applied to GBMs, attributed to FP's pruning altering the ensemble structure and violating the smoother recursion.
• The theoretical minimax result holds only under assumption (C3), which is substantive and not derived from the other assumptions for general bounded densities.

Limitations

• Minimax theorem covers only RF regression; GBM analysis is conjectural because the smoother matrix is neither symmetric nor PSD.
• Storing operators requires O(N^2) space and truncated decomposition O(N^2 P) time; only the top 20 to 50 eigenfunctions are used.
• Distilled MLP sacrifices interpretability of tree rules; GBM classification is handled by treating it as MSE regression, limiting to binary.

Experimental setup

Datasets: abalone adult auto_mpg banknote bc boston california churn concrete diabetes friedman_1 spambase

Benchmarks: abalone adult auto_mpg banknote bc boston california churn concrete diabetes friedman_1 spambase

Metrics: R^2 accuracy average rank

Baselines: ForestPrune Level-wise Optimization and Pruning FIRE TreeExtract SSF Naive Distillation Naive RF NeuralEF NeuralSVD SpIN

Builds on: random forests gradient boosting machines ForestPrune NeuralSVD NeuralEF

Closest papers by meaning

• Compressing tree ensembles through Level-wise Optimization and Pruning (ICML 2025 · similarity 0.88)
• On Computing Optimal Tree Ensembles (ICML 2023 · similarity 0.88)
• Matrix-Free Stochastic Training of Low-Rank Spectral Graph Learning via Randomized Adaptive Spectral Estimation (NeurIPS 2026 · similarity 0.88)
• Smaller, more accurate regression forests using tree alternating optimization (ICML 2020 · similarity 0.87)
• Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles (AAAI 2025 · similarity 0.87)
• Discretization-free Multicalibration through Loss Minimization over Tree Ensembles (NeurIPS 2025 · similarity 0.86)