Concentration and excess risk bounds for imbalanced classification with synthetic oversampling
Touqeer Ahmad, Mohammadreza M. Kalan, François Portier, Gilles Stupfler · 2025
Read Concentration and excess risk bounds for imbalanced classification with synthetic oversampling by Touqeer Ahmad, Mohammadreza M. Kalan, François Portier, Gilles Stupfler (2025) 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-2510-20472.txt.
Introduction
Touqeer Ahmad and three co-authors build the math base for SMOTE, a top cure for skewed class sets in training. SMOTE makes fake new cases of the rare class to bulk it up. Though it works well in use, its math base was thin. Their frame asks what goes on when a model trains on such a bulked set.
A shared bound first caps the gap from risk on fake rare cases to true risk on the real rare spread. A non-parametric excess risk proof then comes for kernel-based models trained that way. The pair of results give hands-on rules to tune SMOTE and the next model step. Count tests back the math marks.
Catalog record
| CREATOR | Touqeer Ahmad, Mohammadreza M. Kalan, François Portier, Gilles Stupfler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-20472
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Concentration and excess risk bounds for imbalanced classification with synthetic oversampling Touqeer Ahmad, Mohammadreza M. Kalan, François Portier, Gilles Stupfler Abstract Synthetic oversampling of minority examples using Smote and its variants is a leading strategy for addressing imbalanced classification problems. Despite the success of this approach in practice, its theoretical foundations remain underexplored. We develop a theoretical framework to analyze the behavior of Smote and related methods when classifiers are trained on synthetic data. We first derive a uniform concentration bound on the discrepancy between the empirical risk over synthetic minority samples and the population risk on the true minority distribution. We then provide a nonparametric excess risk guarantee for kernel-based classifiers trained using such synthetic data. These results lead to practical guidelines for better parameter tuning of both Smote and the downstream learning algorithm. Numerical experiments are provided to illustrate and support the theoretical findings. 1 Introduction The problem of imbalanced classification arises when one of the classes of interest, often referred to as the minority class , is significantly underrepresented relative to the other classes. In such settings, standard classification algorithms tend to produce trivial decision rules that favor the majority class, often ignoring the minority class altogether. Designing algorithms that perform well under class imbalance has become a key challenge in modern machine learning ( Chawla et al. 2004 ; He and Garcia 2009 ; Lemaitre et al. 2017 ; Spelmen and Porkodi 2018 ; Feng et al. 2021 ) . There are two main families of methods to tackle this problem. Model-level approaches modify the training objective, often by reweighting the loss function to penalize misclassification of the minority class more heavily. Several theoretical developments support this direction, including work on cost-sensitive learning ( Menon et al. 2013 ; Xu et al. 2020 ; Aghbalou et al. 2024 ) , Neyman-Pearson classification ( Rigollet and Tong 2011 ; Tong 2013 ; Kalan and Kpotufe 2024 ) and applications to deep learning models ( Cao et al. 2019 ; Byrd and Lipton 2019 ) . By contrast, data-level approaches modify the training data by applying resampling techniques ( Kubat and Matwin 1997 ; Chawla et al. 2002 ; Mani and Zhang 2003 ; Barandela et al. 2004 ; Lemaitre et al. 2017 ) , either by reducing the size of the majority class (undersampling) or by augmenting the minority class with synthetic data (oversampling). Their key advantage is compatibility with off-the-shelf machine learning algorithms and standard validation strategies, such as cross-validation. While undersampling can reduce computational complexity in training well-specified parametric models ( Wang 2020 ; Chen et al. 2025 ) , it risks discarding valuable information. Oversampling, however, seeks to mitigate imbalance by generating new synthetic examples for the minority class. The seminal oversampling algorithm, known as Smote (Synthetic Minority Oversampling Technique) ( Chawla et al. 2002 ) , generates new samples by interpolating between a minority instance and its nearest minority class neighbors. A different proposal called Kernel Density Estimation-based Oversampling ( Kdeo ) was further introduced in Gao et al. 2012 ; Kamalov 2020 . The present paper studies, from a theoretical perspective, the use of Smote and Kdeo for imbalanced binary classification problems. Both methods are nonparametric and iteratively generate synthetic data points from the minority class to achieve a more balanced dataset. Similar methods such as Gsmote ( Sakho et al. 2024 ) can be handled using our approach, but significantly different extensions of Smote such as Borderline-Smote ( Han et al. 2005 ) and Adasyn ( He et al. 2008 ) cannot be. We adopt a transfer learning viewpoint, interpreting oversampling as a means to generate synthetic samples for the estimation of a modified, weighted probability measure that gives more weight to the minority class. This perspective transforms the original imbalanced learning task into a balanced one and allows us to unify reweighting and resampling approaches under a common objective: approximating the same reweighted distribution. By contrast with previous studies on Smote -based algorithms relying on the ROC curve ( Chawla et al. 2002 ) , AUC ( Sakho et al. 2024 ) or F1-score ( Bej et al. 2021 ) , the metric of interest here is associated with the AM-risk to account for the fact that oversampling facilitates a shift toward a more balanced risk. Our main contributions are threefold: • Uniform concentration inequalities for Smote and Kdeo . We derive uniform concentration bounds for the discrepancy between the empirical risk on synthetic data and the population risk on the minority class, over a class of uniformly bounded functions. For Smote , we obtain a bound of order n_{1}^{-1/2}+(k/n_{1})^{1/d} , where n_{1} is the number of minority class samples and k is the number of neighbors used in Smote . For Kdeo , a similar bound of the form n_{1}^{-1/2}+h is established, where h is the kernel bandwidth. From these inequalities, we then derive, for each oversampling method, excess risk bounds for classifiers trained on synthetically generated data, implying consistency results for the balanced risk, provided the oversampling parameters ( k and h ) are sufficiently small and the hypothesis class has controlled Rademacher complexity. This supports the commonly recommended choice of k=5 when using Smote ( Chawla et al. 2002 ) . For Kdeo , this choice of k=5 corresponds to choosing h of order n_{1}^{-1/d} . • Excess risk bounds for nonparametric classifiers with Kdeo . We analyze the performance of a kernel smoothing plug-in classifier ( Audibert and Tsybakov 2007 ; Devroye et al. 2013 ) with Kdeo . We establish an upper bound on the excess risk of this classifier, revealing a variance term of order (n_{1}h^{d})^{-1/2} and a bias term of order h or h^{2} , depending on the regularity of the class-specific distributions. This highlights a trade-off involved in choosing the kernel bandwidth h , whose optimal choice is different from the Smote -default analogous choice n_{1}^{-1/d} and depends on the regularity of the distribution. This analysis provides novel theoretical guidance for bandwidth selection in Kdeo , an issue that has remained largely heuristic in practice. • Empirical validation. Numerical experiments illustrate and support the theory. They demonstrate that following the well-known Scott’s rule h\propto n_{1}^{-1/(d+4)} might be highly beneficial when using nonparametric classification rules such as kernel smoothing or nearest neighbors . This improvement is less significant when using a parametric classification rule such as logistic regression . Related Work. While the empirical effectiveness of Smote is widely acknowledged, its theoretical justification remains limited. The density, mean, and variance of the sampling distribution have recently been derived ( Elreedy and Atiya 2019 ; Elreedy et al. 2024 ; Sakho et al. 2024 ) . As far as we are aware, our work provides the first concentration inequalities for Smote , thereby offering a principled explanation for its success. We rely on advanced tools from nearest neighbors theory, notably Vapnik-style inequalities ( Xue and Kpotufe 2018 ; Jiang 2019 ; Portier 2025 ) . Regarding Kdeo , we go beyond earlier studies by deriving not only concentration results but also excess risk bounds for the kernel smoothing plug-in algorithm of Audibert and Tsybakov 2007 ; Devroye et al. 2013 . Our theory builds