CS Paper Radar

CBE: A Complexity-adaptive Boundary-aware Ensemble Method for Imbalanced Data

Xun Wei

cs.LG ·submitted 2026-10-29 06:38 UTC · v1
benchmark

Abstract

In many real-world classification tasks, datasets exhibit class imbalance, which can degrade the generalization performance of conventional learning algorithms. Data complexity has recently been recognized as a more objective indicator of learning difficulty than the imbalance ratio alone, because class overlap and complex decision boundaries often impair classifiers more severely than imbalance itself. Samples near the decision boundary are inherently difficult to classify, which has motivated many researchers to focus on such instances to improve classifier performance. However, most under-sampling approaches fail to differentiate their sampling of boundary samples across datasets of varying complexity. To overcome this limitation, we propose a complexity-adaptive boundary-aware ensemble (CBE) framework that links the sampling weight distribution to data complexity and dynamically adjusts the boundary preference of under-sampling accordingly. We also introduce an overall complexity measure that combines metrics at multiple levels and use it to divide imbalanced datasets into three categories. Extensive experiments on 24 benchmark datasets from UCI and KEEL show that the proposed method outperforms many existing methods in terms of F-measure and G-mean on Easy and Median datasets, without degrading performance on hard cases.

Comment
12 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

From Imbalance to Evidence: Deep Nonparametric Testing for Complex Data under Severe Sample Imbalance

cs.LG stat.MLstat.ME ·2026-10-09 ·Guanhao Zhou, Xiufan Yu
similarity 0.63
Abstract

Comparing distributions under severe sample imbalance requires effectively using abundant majority observations while retaining sensitivity to differences involving the smaller sample. This challenge is particularly relevant for complex, non-Euclidean data, such as graphs, whose structural characteristics call for flexible testing procedures. Classifier two-sample tests (C2STs) provide such flexibility, but existing procedures are primarily designed for balanced or comparably sized samples. In this paper, we study C2STs in a highly imbalanced regime, and show that severe sample imbalance may substantially degrade testing performance. Different from conventional imbalanced learning approaches that treat sample imbalance merely as a nuisance for classifier training, we turn it into a source of repeated testing evidence. Building on this insight, we propose an Enhanced Imbalance-Aware Deep Classifier Two-Sample Test (EIAD-C2ST), a classifier-agnostic framework designed for sample imbalance that accommodates diverse data modalities by tailoring classifiers to data structure. For computationally expensive deep classifiers, we further develop a scalable representation-amortized implementation strategy. Theoretically, we establish rigorous guarantees on asymptotic size and characterize conditions for power consistency, allowing the imbalance ratio to diverge. We demonstrate the empirical gains using simulations and an application to blockchain forensics. The results reveal that the majority-sample surplus, when properly leveraged, can be organized into useful statistical evidence, rather than an obstacle, for distributional comparisons with complex data.

0.31

Weighting-Based Strategies for Classification: Analysis and Local Peak Dynamics with CART Trees

cs.LG stat.ML ·2026-10-13 ·Abdoulaye Sakho, Emmanuel Malherbe, Erwan Scornet
theory similarity 0.62
Abstract

Tabular learning tasks often suffer from class imbalance, which is often addressed via weighting-based strategies. In this work, we compare the naive approach (unweighted) with the weighting-based rebalancing strategies. Somewhat surprisingly, we demonstrate that, asymptotically, as the predictor complexity increases with sample size, weighting strategies yield predictive performance identical to unweighted approaches across all evaluation metrics, up to a shift in the final threshold. To go beyond, we theoretically study the estimation of a linear regression function through weighted and unweighted CART trees with limited depths. In this setting, we prove that the points in the PR space for both strategies are distributed along the same curve, thus illustrating the similar nonasymptotic performance of the two strategies. Then, we numerically identify more complex synthetic settings where performance gaps, evaluated via fixed classifier complexity, favor weighting strategies. Thus, to guide practitioners, we introduce an indicator that aims at signaling whether a data set may benefit from weighting.

0.27

Using Set Learning to Improve Set-Valued Classifiers on Long-tailed Data

cs.LG cs.CV ·2026-10-20 ·Kevin Kasa, Scott C. Lowe, Graham W. Taylor
similarity 0.61
Abstract

Set-valued classification (SVC) offers a practical approach to communicating uncertainty while maintaining accuracy by predicting variable-sized sets per input rather than fixed-sized sets (e.g. top-1 or top-5). However, set-valued classifiers (SVCs) exhibit significantly degraded performance on long-tailed and imbalanced datasets, a setting for which they are ostensibly well-suited. This becomes apparent under macro-average evaluation, which weighs all classes equally. SVCs are typically formed during a post-hoc calibration stage, so little is known about how training dynamics affect their behaviour. In this work, we investigate how different neural network training strategies and loss functions impact downstream SVC performance on highly imbalanced data. In addition to methods such as label smoothing and class-balancing, we investigate whether loss functions that operate over sets of examples in a batch, rather than treating all examples as independent, lead to better downstream SVCs. We adapt the recently proposed odd-K-out (OKO) loss function, which learns from sets of training samples, improving its sample efficiency whilst introducing algorithmic modifications that reduce its computational overhead from 3.2x to just 1.36x that of standard cross-entropy training. Experiments on highly long-tailed datasets demonstrate our modified OKO approach significantly improves macro-accuracy across multiple SVC methods - including top-k, average-k, and conformal prediction - while maintaining competitive micro-accuracy. This improved performance on minority classes occurs without substantially increasing prediction set sizes, suggesting that carefully constructed set-based training can produce networks better suited to imbalanced data.

0.28

Rethinking Data Selection: The Importance of Coverage over Difficulty in LLM Fine-Tuning

cs.LG ·2026-11-05 ·Lalchand Pandia, Kanishka Misra, Allyson Ettinger
similarity 0.58
Abstract

Selecting high-quality training data can reduce computation cost for LLM fine-tuning. Prior work on data selection developed a variety of difficulty-based scores, motivated by the intuition that harder examples are more informative. While effective for smaller classification models, we find that such methods often fail to outperform random selection for LLM fine-tuning. Our analysis reveals that random selection performs better because it is more representative of the underlying input space---i.e., has better coverage. To validate the importance of coverage, we implement a simple clustering-based selection method which selects data that is more representative of the underlying input distribution. On a set of diverse single-domain tasks, this method yields performance at or above that of random selection. On the diverse, multi-domain Tülu 3 mixture, where random sampling no longer guarantees a balanced subset, our method outperforms all methods. Overall, our results indicate that prioritizing coverage over difficulty leads to more effective data selection for LLM fine-tuning.

0.32

Synthetic Data Augmentation for Fairness under Data Imbalance: Theory and Adaptive Allocation

cs.LG stat.MLstat.ME ·2026-11-11 ·Zhengchi Ma, Kaifeng Zhang, Anru R. Zhang
hot direction similarity 0.57
Abstract

Data imbalance across sensitive groups and class labels is common in classification problems and can contribute to substantial fairness disparities. We study how such imbalance affects Equal Opportunity and how synthetic data augmentation can mitigate the resulting unfairness. We first identify two mechanisms, prevalence imbalance and group-size imbalance, through which changes in the training distribution shift the learned decision boundary and induce disparities in group true positive rates. Motivated by this analysis, we study exact full-balance augmentation, which equalizes all group-label cells. We establish conditions under which full balancing strictly improves Equal Opportunity together with a prediction-error comparison under the oracle balanced distribution, and show that the Equal Opportunity gap of the synthetic-data classifier converges to that of the oracle balanced classifier as the sample size grows and the generator error vanishes. The finite-sample convergence rate agrees, up to logarithmic factors and generator-approximation error, with the information-theoretic lower-bound rate under the corresponding regularity regimes. Since exact balancing need not provide the best fairness-accuracy trade-off in practice, we further propose Accuracy-Constrained Adaptive Synthetic Augmentation (ACASA), which learns both where and how much to augment by minimizing estimated fairness disparity subject to a constraint on predictive accuracy. We provide a finite-sample guarantee comparing the selected augmentation allocation with the population-optimal accuracy-feasible allocation. Simulation studies and real data application support the theoretical findings and demonstrate that synthetic augmentation can substantially reduce fairness disparities while achieving favorable empirical fairness-accuracy trade-offs.

0.32

FH-Sampling: Frequency-aware Hypergraph-driven Oversampling for Imbalanced Time-Series Classification

cs.LG ·2026-11-16 ·Yunrong Hao, Ruohao Dai, Zhen Liu, Guan Wang, Wenbin Pei +1 more
similarity 0.56
Abstract

Imbalanced time-series data appears commonly in diverse applications, such as medical diagnosis. When trained on imbalanced data, classifiers tend to exhibit a bias toward the majority class, making it difficult to identify minority-class instances accurately, despite their critical importance. Sampling techniques have proven effective in rebalancing imbalanced data. However, existing interpolation-based oversampling methods typically rely on pairwise interpolation, limiting their ability to capture high-order inter-sample relationships, and their inherent smoothing effects tend to suppress high-frequency components, compromising spectral fidelity. Therefore, we propose a Frequency-aware Hypergraph-driven Oversampling method (FH-Sampling) for imbalanced time-series classification. In FH-Sampling, a hypergraph is first constructed in the original time-series space to capture complex high-order inter-sample relationships, and sampling ratios are adaptively assigned to mitigate the impact of noisy samples. The discrete wavelet transform decomposes each sample into frequency components. Guided by the sample hypergraph, FH-Sampling combines high-frequency components from related samples while retaining the target sample's low-frequency component to help preserve important frequency characteristics. Experiments on 24 imbalanced datasets demonstrate the advantages of FH-Sampling for imbalanced time-series classification. We further apply FH-Sampling to aircraft trajectory generation. Experiments on simulated aircraft trajectories show that FH-Sampling produces trajectories that better match the real distribution, highlighting its potential for practical applications.

0.14

Mini-batch Sampling Strategies for Long-Tailed Image Classification: An Empirical Study on CIFAR-100-LT

cs.CV stat.MLcs.LG ·2026-09-14 ·Siyu Yuan
code/data similarity 0.56
Abstract · 38 pages, 12 figures, 17 tables. Code and per-run logs: https://github.com/SiyuYuan0117/longtail-sampling

Real-world datasets often exhibit long-tailed class distributions, where a few head classes contain a large number of training samples while a large number of tail classes have only a few. The composition of each mini-batch, determined by the sampling strategy, governs which classes contribute to the stochastic gradient estimate, and therefore affects convergence behaviour and generalisation across the whole class spectrum. We provide a systematic theoretical and empirical comparison of four mini-batch sampling strategies for long-tailed image classification: uniform instance sampling, class-balanced sampling, square-root sampling, and progressively balanced sampling. We place all four in a unified bias-variance framework describing their effect on gradient estimation, which exposes the tension between unbiased optimisation of the empirical loss and fair representation of rare classes. We then evaluate them under controlled conditions using ResNet-32 on CIFAR-100-LT at three imbalance ratios (rho = 10, 50, 100), with every strategy sharing the same long-tailed subsets and initialisation within a seed. Progressive sampling improves tail-class accuracy by 25% relative to the uniform baseline at rho = 100 (13.5% versus 10.8%), consistently across all three seeds, while its overall accuracy is not distinguishable from that of uniform sampling given the seed-to-seed variation (40.0% versus 39.7%); the tail-class gain, not the overall gain, is the robust effect. At rho = 100, class-balanced sampling degrades accuracy on every class group, including the tail classes it is designed to help, which we attribute to overfitting caused by extreme oversampling of scarce data; at rho = 50 this failure is confined to head and medium classes. These results indicate that when rebalancing is applied during training matters as much as how much rebalancing is applied.

0.44

Two-Level Softmax Sampling Done Right: Correcting Bias from Size Imbalance and Dispersion

cs.LG cs.IRstat.ML ·2026-10-07 ·Walid Bendada, Guillaume Salha-Galvan
publishedunusual similarity 0.56
Abstract · NeurIPS 2026

Sampling from a softmax distribution is a fundamental operation in machine learning, but its linear complexity in the number of items makes exact sampling impractical at scale. Two-level softmax (2LS) sampling is a popular alternative enabling sublinear-time sampling. Assuming items are partitioned into clusters, 2LS first samples a cluster and then an item within it. In this paper, we show that, despite its advantages, 2LS introduces systematic and undesirable sampling biases, which arise from misweighting clusters by ignoring both cluster size imbalance and intra-cluster similarity dispersion. We propose two sampling methods, Size-Corrected 2LS (S-2LS) and Size- and Dispersion-Corrected 2LS (SD-2LS), which correct these biases and provide provably better softmax approximations with negligible to non-existent computational overhead. In-depth experiments on five large-scale datasets validate the improved sampling properties of our methods. We recommend their consistent use in place of standard 2LS in future work.

0.65