On Imbalanced Regression with Hoeffding Trees

Pantia-Marina Alchirch; Dimitrios I. Diochnos

cs.LGFeb 25, 2026

On Imbalanced Regression with Hoeffding Trees

Authors: Pantia-Marina Alchirch, Dimitrios I. Diochnos

Organizations: University of Oklahoma

Abstract

Many real-world applications generate continuous data streams for regression. Hoeffding trees and their variants have a long-standing tradition due to their effectiveness, either alone or as base models in broader ensembles. Recent batch-learning work shows that kernel density estimation (KDE) improves smoothed predictions in imbalanced regression [Yang et al., 2021], while hierarchical shrinkage (HS) provides post-hoc regularization for decision trees without modifying their structure [Agarwal et al., 2022]. We extend KDE to streaming settings via a telescoping formulation and integrate HS into incremental decision trees. Empirical evaluation on standard online regression benchmarks shows that KDE consistently improves early-stream performance, whereas HS provides limited gains. Our implementation is publicly available at: https://github.com/marinaAlchirch/DSFA_2026.

Figures & tables

			Predict-then-train
			set size used in	Outlier	Constructed
Dataset	#Features	#Examples	Algorithm 2	removal	feature
Abalone	8	4177	2089	✗	✗
Semi	229	19452	-	✓	✗
California	8	20635	10319	✓	✗
NY Taxi	10	19997	10001	✓	✓

Table 1: Datasets and potential preprocessing for the experiments. Online tuning was tried in all datasets except for Semi due to time constraints.

Panel of Figure 1 — Figure 1: Frequency of labels in predict-then-train data using bins’ range $r=0.2$ .

		Model (potentially including HS, KDE, or both)
								HT	HAT
				HT	HAT	HT	HAT	+HS	+HS
Dataset	Metric	HT	HAT	+HS	+HS	+KDE	+KDE	+KDE	+KDE
Abalone	MAE	1.979	1.979	1.979	1.979	1.643	1.648	1.644	1.560
	RMSE	2.634	2.634	2.634	2.634	2.350	2.350	2.347	2.233
	WRMSE	7.037	7.037	6.916	6.916	7.255	7.508	7.210	7.471

Table 2: Performance comparison across datasets on the scikit-multiflow library using Algorithm 2 for tuning. Bold blue indicates best metric value per dataset, whereas plain bold indicates the second best. For comparison purposes on plain HT and HAT we bypass the tuning portions of the stream.

Panel of Figure 2 — Figure 2: RMSE plots of HT-based models for the California dataset. The KDE and KDE+HS variants perform overall better than the original HT model. Experiments performed on scikit-multiflow library.

Panel of Figure 3 — Figure 3: MAE plots of HAT-based models for the Abalone dataset. Similar to Figure 2 the KDE-enhanced model performs better than the original model. However, here HS helps even further. Experiments performed on scikit-multiflow library.

Panel of Figure 4 — Figure 4: $R^{2}$ score during the last 1K examples for HAT-based models on the NY Taxi (Fig. 4(a) ) and E-Power (Fig. 4(b) ) datasets. In both cases, the KDE variants achieve the best performance throughout the streaming process. Furthermore, in both cases plotting starts after 100 examples have first been processed since the early $R^{2}$ values are very small and dominate the y-axis in the graph. Experiments performed on scikit-multiflow library.

		Model (potentially including KDE)
						HT	HAT	iSOUP	SGT
Dataset	Metric	HT	HAT	iSOUP	SGT	+KDE	+KDE	+KDE	+KDE
Abalone	MAE	2.351	2.357	10.802	2.622	2.052	1.863	10.864	2.166
	RMSE	3.175	3.186	11.249	4.051	2.776	2.633	11.318	3.138
	WRMSE	43.815	42.957	215.832	64.202	50.971	46.795	218.941	57.864
	INVWRMSE	16.944	17.018	58.676	21.451	14.539	13.826	58.988	16.430

Table 3: Performance comparison across datasets using the River Python library. Bold values indicate the better performance between each base model and its KDE-enhanced counterpart. Bold blue indicates the best performing model for a given dataset and metric. As mentioned in the text, due to time constraints we did not perform tuning to identify the best hyper-parameters in these experiments involving the River library. For the results shown for Semi-L3 and Semi-L4 we are using only one decimal digit for better clarity. When necessary we may take into account additional decimal digits to break seeming ties regarding the best performing model (e.g., in the case of Semi-L4, plain

R^{2}

for HT and SGT+KDE appear to be both

0.0

, but HT is actually higher).

Panel of Figure 5 — Figure 5: RMSE, cumulative and during the last 1K examples, for HT-based models on the Semi-L3 (Fig. 5(a) ) and Semi-L4 (Fig. 5(b) ) datasets. Note that these results were obtained using the River library.

Decision Tree Learning

Decision tree learning builds hierarchical, rule-based models for prediction, balancing accuracy, computational cost, and interpretability.

See all 69 papers

Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models
May 22, 2026Hongyi Li, Jun Xu, Hong YanGradient-Boosted Decision Trees Decision Tree Learning
School of Intelligence Science and Engineering, Harbin Institute of Technology, Shenzhen, 518055, China and with the Shenzhen Key Lab for Advanced Motion Control and Modern Automation Equipments, Shenzhen, 518055, China · Department of Electrical Engineering, City University of Hong Kong, Kowloon, Hong Kong
Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference
May 29, 2026Salim I. Amoukou, Saumitra Mishra, Manuela VelosoAnytime-Valid Inference Decision Tree Learning
J.P. Morgan AI Research.
MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound
May 12, 2026Phu-Hoa Pham, Chi-Nguyen Tran, Nguyen Lam Phu Quy +3Class-Incremental Learning Continual Learning
Faculty of Information and Technology University of Science Vietnam National University Ho Chi Minh City, Vietnam · Department of Computer Science University of Warwick Coventry, United Kingdom

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

Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models

Hongyi Li, Jun Xu, Hong Yan

School of Intelligence Science and Engineering, Harbin Institute of Technology, Shenzhen, 518055, China and with the Shenzhen Key Lab for Advanced Motion Control and Modern Automation Equipments, Shenzhen, 518055, China · Department of Electrical Engineering, City University of Hong Kong, Kowloon, Hong Kong

Gradient-Boosted Decision Trees Decision Tree Learning Tabular Regression

Open paper AskPDF arXiv

Learning high-quality oblique decision trees remains a significant challenge due to the discrete and non-convex nature of split optimization. We present the Hinge Regression Tree (HRT) framework, which reframes each oblique split as a nonlinear least-squares problem over two linear predictors whose max/min envelope induces ReLU-like representation capacity. We show that the resulting node-level optimization can be interpreted as a damped Newton method, and we establish the monotonic decrease of the node objective for its backtracking line-search variant. We establish, theoretically, that HRT is a universal approximator with an explicit

O(δ^2)

approximation rate. Building upon this base learner, we propose HRT-Boost, a mathematically synergistic ensemble extension that couples node-level Newton updates with stage-wise functional gradient descent. We show that this ensemble construction admits a stage-wise empirical risk reduction guarantee under the squared loss. Empirical evaluations on synthetic and real-world benchmarks show that HRT is highly competitive with established single-tree baselines, and HRT-Boost compares favorably with strong ensemble baselines and often yields substantially more compact models. The code is publicly available at https://github.com/Hongyi-Li-sz/HRT-Boost.

Abstract

Decision Tree Learning

Explore similar work

Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models

Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound