Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence

Ibne Farabi Shihab; Sanjeda Akter; Anuj Sharma

cs.LGApr 15, 2026

Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence

Authors: Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma

Organizations: Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University

Abstract

Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners. When training data exhibits Markov dependence, as in time-series forecasting, reinforcement learning (RL) replay buffers, and spatial grids, this classical guarantee degrades in ways that existing theory does not fully quantify. We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting, together with an adaptive algorithm that matches the rate on a graph-regular subclass. We first establish an information-theoretic lower bound for stationary, reversible, geometrically ergodic chains in fixed ambient dimension, showing that no measurable estimator can achieve excess classification risk better than $Ω(\sqrt{\Tmix/n})$ . We then prove that, on the AR(1) witness subclass underlying the lower-bound construction, dependence-agnostic uniform bagging is provably suboptimal with excess risk bounded below by $Ω(\Tmix/\sqrt{n})$ , exhibiting a $\sqrt{\Tmix}$ algorithmic gap. Finally, we propose adaptive spectral routing, which partitions the training data via the empirical Fiedler eigenvector of a dependency graph and achieves the minimax rate $\mathcal{O}(\sqrt{\Tmix/n})$ up to a lower-order geometric cut term on a graph-regular subclass, without knowledge of $\Tmix$ . Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions. Consequences for deep RL target variance, scalability via Nyström approximation, and bounded non-stationarity are developed as supporting material in the appendix.

Figures & tables

$T_{\mathrm{mix}}$	Uniform	Lag Thin.	$\hat{T}_{\text{mix}}$ -Thin	Stat. Boot	Circ. BB	Burn-in	Oracle BB	Spec. Rte.
1	$.030_{\pm.001}$	$.031_{\pm.002}$	$.031_{\pm.001}$	$.031_{\pm.001}$	$.030_{\pm.001}$	$.030_{\pm.001}$	$.030_{\pm.001}$	$\mathbf{.030_{\pm.001}}$
10	$.104_{\pm.004}$	$.086_{\pm.003}$	$.054_{\pm.003}$	$.066_{\pm.003}$	$.063_{\pm.002}$	$.041_{\pm.002}$	$.038_{\pm.001}$	$\mathbf{.039_{\pm.002}}$
50	$.228_{\pm.008}$	$.189_{\pm.006}$	$.062_{\pm.004}$	$.071_{\pm.004}$	$.067_{\pm.003}$	$.052_{\pm.003}$	$.045_{\pm.002}$	$\mathbf{.046_{\pm.003}}$
200	$.457_{\pm.013}$	$.355_{\pm.010}$	$.090_{\pm.005}$	$.126_{\pm.008}$	$.119_{\pm.007}$	$.069_{\pm.004}$	$.052_{\pm.003}$	$\mathbf{.053_{\pm.003}}$

Table 1: Excess risk on AR(1) chains, mean

\pm

standard deviation over 50 seeds.

Topology	Uniform	Lag Thin. †	Stat. Boot. †	Circ. BB †	$\hat{T}_{\text{mix}}$ -Thin †	Spec. Rte.
Sentinel-2	$.216_{\pm.008}$	$.213_{\pm.007}$	$.208_{\pm.006}$	$.205_{\pm.006}$	$.201_{\pm.005}$	$\mathbf{.087_{\pm.004}}$
BigEarthNet	$.242_{\pm.010}$	$.238_{\pm.009}$	$.233_{\pm.007}$	$.228_{\pm.008}$	$.225_{\pm.007}$	$\mathbf{.106_{\pm.005}}$
NOAA SST	$.320_{\pm.013}$	$.316_{\pm.011}$	$.310_{\pm.009}$	$.305_{\pm.010}$	$.301_{\pm.009}$	$\mathbf{.188_{\pm.008}}$

Table 2: Excess risk on real-world 2D spatial grids.

Panel of Figure 3 — Figure 3: Relationship between dataset autocorrelation and the accuracy gain of Spectral Routing over standard bagging across the 128-dataset UCR archive. Dashed red line is the linear trend.

Table 5

	Uniform Replay	Replay Baselines		Spectral Routing		Target Var.
Environment	(Compute-Match)	PER	REM	IQM (95% CI)	Time (hr)	Drop (%)
Breakout	$328\,[301,355]$	$340\,[314,362]$	$346\,[318,368]$	$\mathbf{364\,[340,386]}$	5.1	$\mathbf{-23\%}$
SpaceInvaders	$918\,[851,978]$	$931\,[865,988]$	$958\,[892,1010]$	$\mathbf{1028\,[975,1082]}$	5.6	$\mathbf{-38\%}$
Seaquest	$1489\,[1365,1598]$	$1525\,[1415,1625]$	$1550\,[1435,1655]$	$\mathbf{1642\,[1548,1726]}$	5.7	$\mathbf{-42\%}$
Q*bert	$7595\,[7250,7925]$	$7750\,[7440,8000]$	$7870\,[7590,8105]$	$\mathbf{8160\,[7905,8400]}$	5.4	$\mathbf{-35\%}$
Pong ⋆	$19.3\,[18.6,20.0]$	$19.5\,[18.9,20.1]$	$19.6\,[19.0,20.2]$	$19.8\,[19.3,20.3]$	4.8	$-2\%$

Table 5: Ensemble DQN IQM returns (with

95\%

CIs) over 10 seeds. Final column reports the empirical drop in Bellman target variance, isolating the mechanism suggested by Lemma 5 together with the replay-buffer variance discussion of Appendix E .

Table 7

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Standard RF	RF + Spec. Rte.	XGBoost	XGBoost + Spec. Rte.
Covtype	$86.4\pm 0.3$	$\mathbf{88.1\pm 0.2}$	$89.1\pm 0.2$	$\mathbf{90.4\pm 0.2}$
Higgs Boson	$71.5\pm 0.4$	$\mathbf{73.3\pm 0.3}$	$74.4\pm 0.3$	$\mathbf{75.7\pm 0.2}$

Appendix

Table 9: Tabular classification accuracy (%) with feature-similarity graphs.

	Time-Series Transformer						Mamba (State-Space Model)
	Uniform Ensemble			+ Spectral Routing			Uniform Ensemble			+ Spectral Routing
Dataset	Acc (%)	$\mathrm{Var}(\rho)\downarrow$	ECE $\downarrow$	Acc (%)	$\mathrm{Var}(\rho)\downarrow$	ECE $\downarrow$	Acc (%)	$\mathrm{Var}(\rho)\downarrow$	ECE $\downarrow$	Acc (%)	$\mathrm{Var}(\rho)\downarrow$	ECE $\downarrow$
FordA	$88.6\pm.6$	$0.142$	$0.118$	$\mathbf{91.5\pm.4}$	$\mathbf{0.081}$	$\mathbf{0.065}$	$89.3\pm.5$	$0.138$	$0.112$	$\mathbf{91.3\pm.4}$	$\mathbf{0.078}$	$\mathbf{0.061}$
StarLightCurve	$91.8\pm.4$	$0.128$	$0.105$	$\mathbf{93.4\pm.3}$	$\mathbf{0.075}$	$\mathbf{0.059}$	$92.6\pm.4$	$0.122$	$0.101$	$\mathbf{94.2\pm.3}$	$\mathbf{0.070}$	$\mathbf{0.053}$
Wafer	$93.9\pm.3$	$0.115$	$0.092$	$\mathbf{94.8\pm.2}$	$\mathbf{0.066}$	$\mathbf{0.048}$	$94.5\pm.2$	$0.110$	$0.088$	$\mathbf{95.5\pm.2}$	$\mathbf{0.062}$	$\mathbf{0.045}$
TwoPatterns	$88.2\pm.7$	$0.155$	$0.126$	$\mathbf{91.1\pm.5}$	$\mathbf{0.088}$	$\mathbf{0.072}$	$88.8\pm.6$	$0.148$	$0.120$	$\mathbf{91.7\pm.4}$	$\mathbf{0.083}$	$\mathbf{0.067}$

Appendix

Table 10: Sequence-native ablations: accuracy, margin variance, and expected calibration error. Results over 10 seeds; ensemble size

m=10

Panel of Figure 5 — Figure 5: Critical difference diagram over the full 128 UCR datasets. Methods connected by a horizontal bar are not significantly different ( $p>0.05$ , Nemenyi).

High correlation ( $\rho>0.85$ )					Low correlation ( $\rho\leq 0.85$ )
Dataset	RF	RF+SR	ROCKET	ROCKET+SR	Dataset	RF	RF+SR	ROCKET	ROCKET+SR
ECG200	$76.8\pm 1.1$	$79.7\pm 1.4$	$80.7\pm 0.9$	$82.1\pm 0.8$	SyntheticControl	$97.1\pm 0.7$	$97.2\pm 0.6$	$98.6\pm 0.4$	$98.7\pm 0.3$
GunPoint	$86.0\pm 0.9$	$89.1\pm 1.1$	$89.7\pm 0.8$	$91.2\pm 0.7$	CBF	$93.9\pm 1.0$	$94.0\pm 1.1$	$97.1\pm 0.7$	$97.2\pm 0.7$
MiddlePhalanx	$69.3\pm 2.0$	$70.8\pm 1.9$	$72.1\pm 1.4$	$72.7\pm 1.3$	FaceAll	$80.8\pm 2.1$	$80.5\pm 2.3$	$84.1\pm 1.7$	$84.0\pm 1.6$
PowerCons	$83.0\pm 1.4$	$88.9\pm 1.1$	$90.1\pm 0.9$	$92.4\pm 0.8$	FacesUCR	$86.4\pm 1.7$	$86.6\pm 1.6$	$89.7\pm 1.3$	$89.8\pm 1.2$
TwoLeadECG	$80.4\pm 1.3$	$86.3\pm 0.8$	$87.6\pm 0.6$	$89.7\pm 0.5$	Fish	$93.4\pm 1.4$	$94.7\pm 1.5$	$96.6\pm 0.9$	$97.1\pm 0.8$

Appendix

Table 11: Per-dataset accuracy (%) on a representative 40-dataset slice of the full UCR archive, grouped by autocorrelation.

Ensemble Learning

Ensemble learning combines multiple predictors to improve accuracy, robustness, calibration, or uncertainty estimates.

See all 266 papers

Minimax Rates and Spectral Distillation for Tree Ensembles
May 12, 2026Binh Duc Vu, David S. WatsonModel Compression Gradient-Boosted Decision Trees
King’s College London
Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds
Oct 14, 2026Vahe Karagulyan, Mikołaj Kasprzak, Pierre AlquierMinimax Estimation Markov Models
ESSEC Business School
Margin Certificates for Voting Classifiers under Mixing Dependence
Oct 16, 2026Adria Binte Habib, Ibne Farabi ShihabStatistical Learning Theory Generalization Bounds
Department of Computer Science and Engineering, BRAC University, Bangladesh · Department of Computer Science, Iowa State University, USA

May 12, 2026J/K move · Enter open · S save

Minimax Rates and Spectral Distillation for Tree Ensembles

Binh Duc Vu, David S. Watson

King’s College London

Model Compression Gradient-Boosted Decision Trees Decision Tree Learning Spectral Methods Statistical Learning Theory Knowledge Distillation+1

Open paper AskPDF arXiv

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.

Abstract

Ensemble Learning

Explore similar work

Minimax Rates and Spectral Distillation for Tree Ensembles

Minimax estimation of the pseudo-spectral gap of continuous Markov chains, with applications to empirical concentration bounds

Margin Certificates for Voting Classifiers under Mixing Dependence