Concentration and excess risk bounds for imbalanced classification with synthetic oversampling
Authors: Touqeer Ahmad
Mohammadreza Mousavi Kalan
François Portier
Gilles Stupfler
Venue: NeurIPS 2025 poster ()
Keywords: Synthetic oversampling; Imbalanced classification; Concentration inequality; Excess risk bound; AM-risk
Primary area: theory
TL;DR: The paper investigates some concentration inequalities and excess risk bounds for imbalanced classification problems when using some synthetic oversampling techniques as SMOTE.

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.

Concentration and excess risk bounds for imbalanced classification with synthetic oversampling
Touqeer Ahmad', Mohammadreza M. Kalan', François Portier', Gilles Stupfler
Univ Rennes, Ensai, CNRS, CREST- -UMR 9194, F-35000 Rennes, France Univ Angers, CNRS, LAREMA, SFR MATHSTIC, F-49000 Angers, France
Abstract
Synthetic oversampling of minority examples using SMOTE and its variants a leading strategy for addressing imbalanced classification problems. Despite the suc- cess this approach in practice, its theoretical foundations remain underexplored. We develop 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 nonparametric excess risk guarantee for beanel-based classifiers trained using such synthetic data. These results lead to practical guidelines for better pa- rameter tuning of both SMOTE and the downstream learning algorithm. Numerical experiments are provided to illustrate and support the theoretical findings.
Introduction
The problem of imbalanced classification arises when one of the classes 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 Lemaiire 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 AAghbalou et al. [2024]. Neyman classification [Rigollet and Tong 201 Tong 2013 Kalan and Kpotufe 20244 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.) 20044 Lemaitre 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 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 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-baan based
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

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-
[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 modified, weighted probability measure that gives more weight to the minority class. This perspective transforms the original imbalanced learning task into balanced one and allows us to unify reweighting and resampling approaches under common objective: approximating the same reweighted distribution. By contrast with previous studies on SMOTE- algorithms relying on the ROC curve [Chawla et al.) 2002], AUC (Sakho et al.) 2024] or F1 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 " 1/2 + (k/m)) )1/d where n1 is the number of minority class samples and k is the number of 1/2
neighbors used in SMOTE. For KDEO, a similar bound of the form " -1/2 + h is established, where h is the kernel bandwidth. From these inequalities, 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 f) are sufficiently small and the hypothesis class has controlled Rademacher complexity. This supports the commonly recommended choice of l = when using SMOTE [Chawla al., 2002]. For KDEO, this choice of k =
1/2 corresponds to choosing / of order "1
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, -m1// and bias term of order / or 12, depending distributions. This highlights trade-off involved in choosing the kernel bandwidth h. whose optimal choice is different from the SMOTE-
the regularity of the class-specific
analogous choice n, 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 x n, -111((+))) might be highly beneficial when using nonparametric classification rules such as kernel smoothing 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| [aako et al. 2024). As far as we are aware, our work provides the first concentration inequalities for SMOTE, thereby offering principled explanation for its success. We rely on advanced tools from nearest neighbors theory,
notably Vapnik-style inequalities [uue and Kpotufe, 2018 Diang 2019 Portier 2025].
Regarding KDEO, we go beyond earlier studies by deriving not only concentration results but also excess risk bounds for the kemnel smoothing plug-in in algorithm Afuuibbe and Tsybakov [007]]
Devroye et al. [2013]. Our theory builds upon concentration bounds for the L' Lerorr [evrryee 1991
and bias-variance decompositions from Devroye and Györr [1985). (Holmstrmm and Klemelä 1992]
We note that Tong [2013] deals with the different problem of Neyman-Pearson classification by controlling the
-error, rather than the I,- eerrrr of KDE. We extend these results to the case of
Lipschitz densities that may exhibit discontinuities at domain boundaries common scenario in real-world applications.
Outline. Section 2 introduces the mathematical background and formal characterization of the problem. Section 3 presents the main theoretical results and Section provides supporting numerical experiments. The Appendix contains all mathematical proofs and additional numerical results.
4
2

---

2 Problem setting
2.1 Background
Let IP be a probability distribution on Rd x {0, 1}. and let D, independent and identically distributed (i.i.d.) random variables with common distribution P.. Denote by п1 = Di=1 -r, and no = >>=1 [y, the number of samples from the conditional distributions F1 == Y = and Pp == P 0), respectively. Under class imbalance, we assume 1 < no. or equivalently, P1 P(Y 1)
1s be
p1 PP(Y = 0). Denote by (Xu)isism and I the features corresponding respectively to the minority and majority classes.
Let be loss function, e.g. the 0-1 loss {(a) 1 {a<0) or a convex surrogate such as f(a)) e used to evaluate discriminant function g Rd + R. For each pair (X,Y), ((g(X)(2 1)) quantifies the quality of the prediction and can be used to define the (imbalanced) risk
R(g)= ((((g(X)((2 1))] pı E [((g()))
(1 p1) Bo(((-g(X))]-
key challenge here is that trivial classifiers that always predict the majority class (Y = 0) will achieve a low such risk when Pr is small, even though they perform poorly the minority class (Y = 1). A common approach to mitigate this issue is to consider the 3-reweighted (balanced) risk
Rg( = BE, [(((()))) (1 3) E, [x(()-
where a commonly used choice is 3 = 1/2. corresponding to the so-called AM-risk as studied in Menon et al. (2013), J. Xu et al. 2.200]. Aghhalou al. [2024). While Rę(g) can in principle be minimized by reweighting the original samples, a widely used and successful alternative is synthetic oversampling. We focus on SMOTE and KDEO, that expand the minority class until the empirical class prior of the augmented sample matches the evaluation weight 3.
2.2 Oversampling techniques
SMOTE. This method generates synthetic minority samples by interpolating between randomly selected minority examples and their nearest neighbors (NN), thereby filling in sparse regions of the minority class in the feature space. At each iteration i, a minority class (Y = 1) sample X1s is drawn uniformly at random from the minority class points {Xi] and then another point 1; is generated uniformly at random among the kNN of X1s in the minority class deprived of X1s, that is, Kishessm {X1s} (if n1 = 1, we set X, 1 = X1e). A synthetic sample is generated as
=i= = - (1 AX
where \ ~~ 200 1] is independently drawn. The distribution of synthetic SMOTE points is then the mixture (1/m)) E Uu (Xi:), where U4 (Xi:) denotes the (conditional) uniform distribution over the union of segments _ (X1,, x with (x(1) (x {() being the set of le nearest neighbors of X1s within the minority class deprived of X1s-
KDEO. This method generates synthetic minority samples by perturbing randomly selected minority points using sernel-based noise. There are again two steps. First, a point X,, is drawn uniformly at random from the minority class (X1)) signy then, a synthetic sample is generated
X X1, + hW,,
(2)
where W; ~ K is independently drawn from fixed kernel distribution (e.g., standard Gaussian), and h 0 is a bandwidth parameter controlling the magnitude of the perturbation. This procedure can be interpreted as, given a kernel function K and bandwidth h > 0, drawing synthetic samples Xi; from the KDE (x) (1/nz) 1 K2 X1:) (with K2 (z) h (x////) in the minority class. The key difference between SMOTE and KDEO lies in the support and shape of the component distributions: SMOTE uses uniform distributions over segments joining neighbors, while KDEO
employs symmetric kernels that may perturb points in any direction.
The number of synthetic replications is chosen so that the proportion between the synthetic minority samples and the majority samples is such that m/(m + no) R B3. By considering m no. we focus on the minimization of the AM-risk R1,2, but our results also hold for arbitrary B E (0, 1).
3

---

3 Main results
3.1 Concentration inequalities and excess risk bound for empirical risk minimization with oversampling
We show first that the empirical mean based on SMOTE or KDEO-generated samples concentrates uniformly around the population mean over a class of uniformly bounded functions. For SMOTE, we put a mild condition on the minority class distribution P1 to ensure that it puts enough mass everywhere on its support. Let (ax, r) be the Euclidean ball with center z and radius r > 0 in Rd.
Assumption 1. There exists a constant Ca > such that for all x E supp((11) and all r > 0, we have Pi (B(z, r)) 2 min(Car" 1}. [In particular, supp((1)) ) is bounded.]
The above assumption is standard to obtain error bounds for nearest neighbors estimators [Gadat et al. 2016 Jiang 2019 Portier 2025] or other local averaging methods such as local polynomial estimators Audibert and Tsybakov| (007). The next assumption, not actually specific to SMOTE, introduces the class of functions over which the uniform convergence bound derived.
Assumption 2. Let be a separable class of functions G R + R which is uniformly bounded, i.e. there is B > O such that supGer |G]| S B, and each G F is L--Lipschitz
One last assumption is needed to control the complexity of the class F. This assumption relies on the well-known notion of Rademacher complexity [Bartlett and Mendelson, 2002] recalled below.
Definition 1 (Rademacher complexity). Let Xi,..., Xn be i.i.d. from a distribution P on X, and let : on be ii.d. Rademacher random variables (i.e. PP(o; =1] Fla, =-1] = 1/2) that are independent of the X,, The empirical Rademacher complexity of F on Xim = (X1..... Xn) is
RT XI:: == E.g sup Σ o, aXX GEF t=1
Assumption 3 (Rademacher Bound). There exists a sequence Rr(F) such that, for every distribution P on X' with supp( P) C supp((Pi) i) U supp((Po) and n 2 the following common upper bound holds:
E Ex -P
pm (
(F..F..
Note that the SMOTE algorithm only applies when > O. Define
m
Msmote (G) =
G(Xi))
1mi10) + 0 x [()=0))
m
While this specification necessary to make our statement mathematically correct, we note that, in the case n1 = 0. the corresponding behavior could have been specified in an arbitrary manner. We further introduce of (F) supGer Var (Gr(G(()) Y = 1), where X denotes the original data, and, likewise, D.) given that 71 > O, where X11 is drawn uniformly at random from the minority class (X1s (Xiiisssn ig We make below the convention (J( 1/0- too and we set hū = max(k, (d + 11) log(2ng + 1og(8/8)) on the event {nr > 1} and 0 otherwise.
we let (FF = supGeF Var(G(X
Theorem 1. Suppose that Assumptions 7 2 aandBhold Let 8 E (0. 1/5) and m 2 1. If > 1, let A E [l,..., 1} and let {X issss be t.i.d. samples generated by the SMOTE algorithm Then, with probability at least 58.
6
1/8
Kg
1/8
sup GEF
|mooe (G) -Ei [G()(]]] 4Rm(F) 4Rn, (F)
R,
Ca
m1
where
FF(
oi(F m
1
8
1
1 5
R
+
2 log
+
B
log
m
We apply this to the proof of excess risk bound for empirical risk minimization algorithms under synthetic SMOTE-based oversampling. Let G be class of real-valued discriminative functions

---

3.1 Concentration inequalities and excess risk bound for empirical risk minimization with oversampling
defined on Rd and let f: R + [0, oo)
be the loss function. Consider the following classifier:
g argminges ((1220) Σ ((g(X))) + (ma20) Σ e(- (
(3)
This is standard classifier, using SMOTE-generated data. By convention, and similarly what was done with Mommtte (G) above, the first term (resp. second term) in the above minimization is set as 0 when 74 (resp. fgg 0). Let ((G) {e 9, 9 E 9] and oā( suPGer Var[G(X)]| 0].
Corollary 2. Let m = no Imi > 0} and 6 E (0, 1/7). Under the assumptions of Theorem with F ((g) U)( we have, with probability least 78.
6 Ca
1/d
k5
1/d
R1 inf B1/2(9) S 4Rm, (F) + 8Roo (F) + gEB
+
R.
n1
where
oF(F)
()
(F Y1o
8
2
1
R
+
2 log
+
B
+
log
n1
71
3
n10
nh
We turn to KDEO. For q > 0 and any measurable f : IRd - [0, oo), let =- [|=]]] Define PEDRO (G) as Pismote (G), only with synthetic data generated by KDEO rather than SMOTE Theorem Suppose that Assumptions andd hold. Let K be a density function with M (K)= co.
=
Let ô E (0, 1/5) and m 2 1. Moreover, whenever nı > O, let {Xi, {Xi:hsisg be m i.dd samples generated by the KDEO algorithm (2). Then, with probability least 1 55,
sup (uRDBO E, [G()(] S 4Rn, (F) + 4Rm + 5LhM; (K) + R. GEF
where
oi(F)
(f( m
1
8 B
27 8m
R =
2 log
+
log
n1
For the classifier defined in 3 with KDEO and not SMOTE, we obtain the excess risk bound below.
Corollary 4. Let nol [m > 0} and 8 E (0, 1/7). Under the assumptions of Theorem 3 with F ((G) ( we have, with probability at least - 78.
R1 R1)2(08)= inf R1/2(9)= I 4Rn, (F) + 8R, (F) + 5LhM + R,
gEG
where
(F(F) 710
(F
(FF n1o
1
8
35
1 m1
R
2 log
+
B
log
5
8no
Remark 1. The Lipschitz property required in Corollaries standard loss functions such as hinge and logistic, and for classifiers like neural networks under mild conditions such as bounded spectral norms of the weight matrices.
2 Band as part of Assumption holld for
Remark 2. Many practical function classes satisfy the Rademacher complexxity bound in Assumption 3 under natural constraints, with (F) - B////n, where By > 0 is constant. For example, F. has finite VC-subgraph dimension v, Ihen the previous bound is valid with B, depending on B and (F) Giné and Guillow
2001 Proposition 2: for linear predictors based F
<. R, one has that B depends on R and W and the ambiens {i + w x |wlll2 < WW with x
dimension [Bartltt and Mendelson
2002 Lemma 19]; and for fully-connected ReLU networks of depth L whose inputs satisfy | S R and whose weight matrices A obey the Frobenius-nomm
bounds | S 85, By scales as RVT Se Golooich et al. 2018 Theorem 1).
Remark 3. The bounds of Corollaries [ aand B depend on the sample sizes ng and which, in our framework, are random variables. Considering n,, a multiplicative Chernoff bound gives that with probability at least 1 5, n4 2 rp - t), where e² = 2 log( 2log(1/8)/ (npp). Doing so reveals frontier which is, in the asymptotic regime, rip - cc. When pr below this frontier, it is not clear that consistent estimation is possible as the bound does not vanish asymptotically.
5

---

3.2 Nonparametric excess risk bound for the KDEO-based kernel smoothing plug-in classifier
3.2 Nonparametric excess risk bound for the KDEO-based kernel smoothing plug-in classifier
The balanced Bayes classifier minimizing the AM-risk g(x) (n(z)>p1) where r7(x;) = P(Y l|x = r). Besides, if P,, has a density function fy with respect to the Lebesgue measure then, by the law of total probability, the distribution of X has density f = pı + (1 p1 Po with respect to this same measure. It follows from the Bayes formula that the balanced Bayes classifier is then given by
Va E R. g(x) ((f())>((0)) (=)()))/((=)))
Our ultimate goal study the counterpart of g using a KDEO-based kernel smoothing classifier. Before that, we give a general result. with respect to the AM-risk, on the performance of any discrimination rule of the form ((x) 1 fo())))) where each fy is an estimator of fy.
Theorem 5. For each y E {0, 1}, suppose that Py has a density fg with respect to the Lebesgue measure. Let Sy denote the support of I, and S = So U Sr. We have
1 -f(=))-(())ee R1yz(0) R1)2( - 2 [f(()) fi()) + 2 -o(x))
1
This is reminiscent of known results in [Devroye et al. 2013 Chapter 6] or (Devroye and Györt 1985 Chapter 10], showing that the excess classification risk is bounded by the L'reroor of the conditional probability estimators or the density estimators in the different classes. Theorem [5] though, is concerned with the AM-risk while the above references deal with the standard risk measure.
Let us now focus the kernel smoothing classifier of Audibert and Tsybakov [2077] Devroye et al.)
(2033) when using KDE-generated data. Consider, as in (2). independent samples { lgiggm with common density SIn (given the initial sample), i.e. the KDE of the minority class covariates. Define
n" (z) EE EisKK,t K,(x xi.)
mfia (z)
Ee Kz(1 Xos) (ff + (x)
with the convention 0/0 0 and where (x) = 1 (m1 (1/m) Σ K2(x Xi.) is the kernel density estimate based on synthetic data from class and foe is the kernel density estimate based on initial data from class (with for = 0 when no = 0). One could, of course, choose a different kernel for fue. ft. and fux: we take the same kernel K in each estimate for the sake of simplicity.
By setting m ny (m1>0), the discrimination rule g" (x) = 1 (1)())11/2) = [ (o))) is tailored to minimizing the A.M-risk. Next we obtain an upper bound on the excess risk of g in this setting. Regularity assumptions are required; let, for any open subset U of Rd, (U) be the Sobolev space of functions G U + E whose (weak) partial derivatives of order s are integrable.
Assumption 4. K IRd + R is square-integrable symmetric density function such that Ma+e (K- K2) < 0o for some E >> 0 and M2(K) < oc.
Assumption 5. For each y E {0, 1}. Pp has a density fo E W2.1 (TR') with respect to the Lebesgue measure and (f))(fy) < co for some e >> O.
To deal with situations violating Assumption 5 where the densities may, for example, have compact supports and be smooth and bounded away from zero on the interior of their supports, we introduce alternative assumptions. For two sets S1 and S2, S₁ + S2 is the set {sı + 82, ($1,82) E S1 x 52). The Lebesgue measure is denoted by X and the topological boundary of a set E is denoted by OE.
Assumption 6. K 12d + IR is a square- -interriitteeabee symmetric density function supported on B 1). Assumption 7. For each y (0, ), the support Sy of Py is smooth, in the sense that there are K. To > O such that X(as, + B(0,r)) I er for O < r < To- Moreover, Ty has a density fy E (U) with respect to the Lebesgue measure, where U is the interior of S, which is bounded on as (0,, 2ro), and (fy)(Sy) < do for some : > O.
Assumption 7 on S,, is, for example, satisfied if as, is a finite union of compact, closed and smooth submanifolds of dimension
1 in Rd whose pairwise distances to one another are nonzero. This is a consequence of Weyl's 'ss tube formula in the Euclidean space, see Equation (14) in Weyl [1939] applied to manifolds of codimension mn with the notation therein; a self-contained statement of this result is Theorem 9.3. in Nicolacscu 2007]]
6

---

3.2 Nonparametric excess risk bound for the KDEO-based kernel smoothing plug-in classifier
These assumptions make it possible to prove L' bounds on the KDEs of the fy. The proofs rest upon the McDiarmid inequality (McDiarmid 1989 and bias- decomposition, where is shown and used that, if Jy (x)z)= = Ka( 2) (z)dz denotes the convolution of fy and Ki.
Mo(K2) nyhd (1 + h/(++)/22)
Blfun()) - fo * (n(x) I Gydey
and I |150x - S
oyh under Assumptions and v/y if S ro under Assumptions
6 and
The constant Gydde (resp. dy. byy, defined right below Lemma 5 (resp. Lemma 6). depends on Jy and K (resp. Jy and K) only, see the Appendix. Let us introduce Zy obtained from Cy,d,s by plugging in fyh instead of fy- One may likewise obtain (conditional) L'-bbund on the KDE fi. based upon the oversampled covariates {Xi, hisismm in the minority class. Combining these bounds with Theorem | results in the following bound on the excess risk of the classification rule 9"
Theorem 6. Lel m no (m120) [
and ē E 1/3). Then, with probability at least 1 - 36,
R1/2(0") R1/2(0)
M)3
I
Co.d.e nosd
+ tLdeV niha + &ldde nosa
(1 + max(h, s)d(+))/2)
2
1
1
2 log
+
Vno
2//11
f dos + d1 (h2 + s²) under Assumptions and 5
+ 2 vos + (h + +s hf S Tn under Assumptions and
In Theorem 6 the leading term (in case of second order regularity) scaling as (nus")-11/2 + s² (n1h")-1/2 + n2. The optimal value of the second bandwidth s, involved the error for and fi, (based no observations), is then Ro -1/(4+4) while the optimal value for the first bandwidth h, involved in the data generation step (based on n1 observations) is h = n, -1((444)) In highly imbalanced scenarios where / - 0, the two bandwidths should thus be set differently to optimize the upper bound and reach the optimal convergence rate no
-2/(d+4) + n2
-2/(d+4)
Remark 4 (Comparison with SMOTE). The default value in SMOTE is k = 5 |Chawla et al. 2002 which, viewing kNN as a kernel estimator with data-driven bandwidth (see e.g. Portier et al. [2024), Lemma 3), would correspond to choice of h ~ (1/n1)*/ (omitting constants). This is different from the optimal choice above, and it would not (based on our upper bound) guarantee consistency, as the upper bound in Theorem 6 would not converge to O.
Remark (Comparison with the kernel smoothing plug-in rule). Our method of proof allows to establish an excess AM-risk bound for the kernel smoothing rule 9n = ((un(a)> based on the initial data only (see Proposition 9 in the Appendix). The bound scales as (rzhh) -1/2 + h²2 (nghh) 1/2 + h the optimal value for h being h = (1/n1 + 1/rz)) 1/dx))/(d42)) The bound obtained in Theorem 6 is similar but different, as the two bandwidth parameters, h and s. might be set differently.
These remarks suggest that the synthetic oversampling rule g" (i) performs no worse than the rule 9n based on the initial data only, (ii) should be expected to perform better than rule using SMOTE synthetic generation with default parameters, and (iii) improvements may be observed in practice by choosing carefully In the numerical experiments, by considering the K-NN classifier, which can be seen as a practical modification of the kernel smoothing classifier, we investigate a cross-validation procedure choose K (having similar role s), while h is chosen following Scott's rule.
Investigating the KNN plug-in rule (instead of kernel smoothing) in Theorem 6 as well as fast convergence rates under the noise condition of Audibert and Tsybakov (2007). Tong (2013) remain open problems. Finally, Theorem (6is only valid for KDE-bbaeed sampling and might be extended to SMOTE. None of these problems direct consequences of this work.

---

4 Numerical experiments
4.1 Methods in competition
Oversampling techniques. The SMOTE and KDEO methods are applied to imbalanced data with
R < no. After oversampling, the synthetic data will contain m no observations with label 1 and vi observations with label 0. For SMOTE, we consider the default choice k 5 neighbors. For KDEO, we consider the matrix-valued bandwidth H1 such that H? = n 2/(44) 1) C1 following from Scott's rule, where C1 is the covariance matrix computed from the minority class samples.
Classification methods. We consider the kernel smoothing (KS) discrimination rule studied in Section 3.2 and the KNN classification rule as follows. First, apply the concerned oversampling technique, either SMOTE or KDEO, and then employ the KNN (resp. KS) algorithm with parameter
K = vn (resp. = S obtained from Scott's rule $ 0g 2/(d++1 j 0, 1, where C is the covariance matrix of class j). This choice of Sj (as well as H1 for KDFO) corresponds to the optimal scaling recommended by Theorem [ Note that both KNN and KS are based on the local averaging principle. This is compared to the logistic regression (LR) method, employed to incorporate a parametric classification approach and to illustrate the theory developed in Section 3.1 Finally, we also consider the K -NN balanced Bayes classifier (BBC), which does not involve oversampling but rather reweighting. It is defined as the classifier (1xx(=))))) where fiN N (z) is the KNN estimator of (7(x) with hyperparameter K = v and 6 = n1 Under class imbalance, the threshold adjustment allows to minimize the AM-risk [Aghbalou et al., 2024]. Similar results with Random Forest. classifier applied after SMOTE and KDEO are given in the Appendix.
4.2 Simulated data
Four models are considered. In all cases, ((x, Yi) are n = 1000 i.i.d. training samples from the distribution of (X,Y). Let e, be the ith vector in the canonical basis of Rd.
Let X ~ (0, Ta) and Y ~ Bernoull((expit(X* el + +a), with a tuning class imbalance and expit (u) (xp(u)/(1 + exp(u)).
Example 1:
GPD( 0.5) have a Generalized Pareto distribution, where a (X) = exp(X e1). Define Y 1(2>1) with f tuning class imbalance.
Example 2: Let ~ (0, Ta) and
Example 3: Let Z Bsin (T e 22 + (1 B) sin( X xTe, /2//2) with B Bernoulli (0.5).
X ~ ~N, Ta). Y1 ~ GPD(1, 0. Y/2 ~ Exp(10) Set Y = (2>x) with / tuning class imbalance.
Example 4: Let d = 2 and μ] = (0. (0.0) T. F2 = (10, T, M3 (10. 0)_ #4 = (0. 10) T. Let Z be (1.2,3,4)-v)) 4aaluue with PZZ- = c) = We. then X ~ Σe=1 Nue: 61,) ( (z==c and Y = L(223).
Take = 4 in Examples 1, 2 and 3. In each case, the validation sample is created by generating 10000 observations and then undersampling the majority class so to obtain balanced data set.
Results when varying k in SMOTE and H in KDEO. Figure I different values of and H are considered when dealing with Examples 2 and 3 for which the binary response Y was constructed by thresholding at the probability consider SMOTE(K) with varying & E (7, 65). and KDEO(H) with varying H = cHt, for e ranging (1/20, 3), where H, follows from Scott's rule. The KS, KNN and LR classification methods are considered. Figure [iaullaysss the average (over 50 replications) AM-risk over the validation set.
P1 = 0.90 (for Examples 1 and 4, see the Appendix). We
In Figure I we see that varying in SMOTE(K) or the bandwidth H in KDEO(H) leads to noticeable changes in the AM-rrisk values. In contrast, when using LR, changing H or k has almost no effect. This indicates that LR is considerably less sensitive the choice of oversampling parameters or H compared to nonparametric classifiers. This was already suggested by Corollaries and 4 while the impact of a real-valued bandwidth was formally analyzed in Theorem/6 when using KS. Observe also that, in Figure (left panel), the optimal value of i for SMOTE(K) when using KNN lies between 45 and 60. This differs substantially from the default k = 5. Figure (right panel) shows that varying the bandwidth H does not yield improvements over KDFO, which relies on Scott's 's rule of thumb, that in fact turns out to be optimal. Finally, note that KDFO (F) with small H produces results that closely resemble those of SMOTE, which is consistent with the intuition that & and H play a similar role.
8

---

4.3 Real data analysis: Abalone, California, MagicTel, Phoneme, and House_ 16H datasets
Results under different degrees of class imbalance. The methods are evaluated on Examples 2 and 3 (for Examples 1 and 4, see the Appendix), where the parameters t, a and w are adjusted to achieve different probability levels (1 - p = 0.60, 0.80, 0.85, 0.90, 0.92, 0.95). The AM-risk of the KNN and KS classifiers for Examples and is reported in Figure 2
under KDFO and SMOTE.
Across all examples, both classifiers exhibit similar patterns. A clear performance gain is observed for KDEO and BBC compared with SMOTE. In partieular, the AM risk of the KS classifier under KDEO sampling is consistently smaller than that of KNN when trained under SMOTE. These results suggest that fine-tuning the bandwidth H1 in KDEO, together with the use of the KS classifier based on well-chosen matrices S,, provides clear benefits. This, in turn, opens the perspective of tuning KNN using cross- cross-validation, as investigated below. By contrast, the LR classifier performs uniformly across all resampling methods (see the Appendix). This is in line with the results given in Theorems [] and as they suggest that estimating the risk with SMOTE or KDFO gives better results when K and H are small, underlining that oversampling may not be critical for such a parametric classifier.
Cross validation (CV) selection of K in KNN: SMOTE- -VOTEECV, KDEO-CV, BBC-CV. To improve the KNN classifier's s performance, we consider selecting K via cross-validation. Specifically, we use 5-fold cross-validation, where in each fold, the data is first balanced using the chosen oversampling method (SMOTE/KDEO) and then K is selected (from grid) to minimize the validation error. For the BBC, the procedure differs: we apply the BBC classifier obtained from training folds and choose the value of K that minimizes an AM-risk estimate obtained via under-sampliee ande--sampling of the testing fold.
The AM-risk across BBC, SMOTE, and KDFO, and the CV choice of K are reported for Examples 2 and 3 in Figure (resp. Examples 1 and 4 given in the Appendix). A noticeable improvement can be observed in the results for KDEO-CV and SMOTE-CV. The CV on K yields poorer performance for the BBC, suggesting that the BBC and CV may not interact effectively in this context. Moreover, KDEO and KDEO-CV consistently outperform SMOTE, SMOTE-CV, and BBC, even in scenarios where the probability pl is smaller. The intuition is that KDEO, which generates synthetic samples using kernel density estimates, may better approximate the true minority distribution than SMOTE
4.3 Real data analysis: Abalone, California, Magic Phoneme, and House 16H datasets
Each dataset is split into training and validation sets using a 70 : 30 ratio. California and MagicTTel are balanced datasets; to make the training set imbalanced, we subsample the minority class in these two datasets, adjusting the imbalance ratio to 20%, 10%, and 5%. The validation sets are balanced by undersampling the majority class to ensure fair assessment aligned with the evaluation metric.
The AM-risk results for the KNN classifier are presented in Figure I (for alternative classifiers, see the Appendix). SMOTE and KDEO generally perform similarly except for Abalone, where SMOTE consistently achieves a smaller risk. This suggests that the Abalone features might have a specific structure that is better synthesized by nearest neighbors rather than by the (more arbitrary) Gaussian kernel. One particularly relevant conclusion is that using CV for choosing K compared to the choice K- /n. (almost) continuously improves the performance across all the different cases. A similar pattern is observed for Random Forest, LR, and LR-Lasso, see the Appendix.
Methods
SMOTEO
Nothods
Esample
Esarpie
Exsmple
Example
0.45
0.73
0.27
0.34
0.75
AM rok
3.25
0.
025
30g
Eayy
Figure 1: Average AM-risk of KNN, KS, and LR classifiers on balanced data over 50 replications. Left: using SMOTE and SMOTE(K) with & (7, 65). Right: using KDEO and KDEO(H), with H = clt, and e ranging in (1/20, 3) where H₁ follows from Scott's rule.
9

---

4.3 Real data analysis: Abalone, California, MagicTel, Phoneme, and House_ 16H datasets
Example 2
Example
KNW
KNN
KS
0.393
0.32
A8 10
0.353
6.2
6a
Figure 2: Average AM-risk across different data imbalance regimes for the KS (described in Sec- tion 3.2 and KNN classification rules computed over 50 replications.
Methods
ESC
1082
SMOTE
Nethods
BEC
(0E3
SMOTE
Example 2
Example 3
0.32
Add Rtai
0.78
0.75
6250-
0.28
6226
dsp
oze
032
Figure 3: Average AM-risk across different data imbalance regimes for the KNN methods described in Section 4.1 computed over 50 replications.
Methods
Risk
0.3
0.0
Abatone
Calioomta(20%)
Calioonia(105)
55
Magic Tei(20%)
MagkcTall0%
MagicTel(55))
Phoneme
House 16H
Datasets
Figure AM-risk corresponding different rebalancing methods and datasets when using the KNN classifier.
10

---

REFERENCES
Acknowledgments
Ahmad acknowledges support from the Région Bretagne through project RAD-2021-MaEY) G. Stupfler acknowledges support from grants ANR-19-CE40-0013 (ExtremReg project), ANR-23- CE40-0009 (EXSTA project) and L-LI--LBB-0020--0 (Centre Henri Lebesgue), the TSE-HEC ACPR Chair "Regulation and systemic risks", and the Chair Stress Test, RISK Management and Financial Steering of the Foundation Ecole Polytechnique.
References
Anass Aghbalou, Anne Sabourin, and François Portier. Sharp error bounds for imbalanced classi- fication: how many examples in the minority class? In International Conference on Artificial Intelligence and Statistics, pages 838 846. PMLR, 2024.
Lean-Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2):608 633,,,,2222 2007.
Ricardo Barandela, Rosa Valdovinos, J. Salvador Sánchez, and Francesc J. Ferri. The imbalanced training sample problem: Under over sampling? In Ana Fred, Temry M. Caclli, Robert P. W. Duin, Aurélio C. Campilho, and Dick de Ridder, editors, Structural, Syntactic, and Statistical Pattern Recognition, pages 806 814, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-48) 2002.
Saptarshi Bej, Narek Davtyan, Markus Wolfien, Mariam Nassar, and Olaf Wolkenhauer. Loras: oversampling approach for imbalanced datasets. Machine Learning, 110:279-301, 2021.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. Oxford University Press, 2013.
Olivier Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathematique, 334(6):495 500, 2002.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 872-881. PMLR, 09-15 Jun 2019.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with labelldistribution-aaarr margin loss. Advances in Neural Information Processing Systems, 32, 2019.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of Artificial Intellignnce Research, 16:321-357, 2002.
Nitesh V Chawla, Nathalie Japkowicz, and Aleksander Kotcz. Special issue on learning from imbalanced data sets. ACM SIGKDD Explorations Newsletter, 6(1):1-6, 2004.
Yan Chen, Jose Blanchet, Krzysztof Dembezynski, Laura Fee Nemn and Aaron Eliasib Flores. Optimal downsampling for imbalanced classification with generalized linear models. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Benrard Delyon and François Portier. Integral approximation by kernel smoothing. Bernoulli, 22(4):
2177-2208, 2016.
Lue Devroye. Exponential Inequalities in Nonparametric Estimation, pages 31-44. Springer Netherlands, 1991.
Lue Devroye and László Györfi. Nonparametric Density Estimation: The LI View. John Wiley Sons, New York, 1985.
Lue Devroye, Lászłó Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.

---

REFERENCES
Dina Elreedy and Amir F Atiya. A comprehensive analysis of synthetic minority oversampling technique (SMOTE) for handling class imbalance. Information Sciences, 505:32-64, 2019.
Dina Elreedy, Amir Atiya, and Firuz Kamalov. A theoretical distribution analysis of synthetic minority oversampling technique (SMOTE) for imbalanced learning. Machine Learning. 113(7): 4903,4923,20 2024.
Yang Feng, Min Zhou, and Xin Tong. Imbalanced classification: A paradigm-based review. Statistical Analysis and Data Mining: The ASA Data Science Journal, 14(5):383-466, 2021.
Sébastien Gadat, Thierry Klein, and Clément Marteau, Classification in general finite dimensional spaces with the k-nearest neighbor rule. The Annals of Statistics,, 44(3):982-1099, 2016.
Ming Gao, Xia Hong. Sheng Chen, and Chris J Harris. Probability density function estimation based over-sampling for imbalanced two-class problems. In The 2012 International Joint Conference on Neural Networks (IJCNN), pages 1-8. IEEE, 2012.
Evarist Giné and Richard Nickl, Uniform central limit theorems for kernel density estimators. Probability Theory and Related Fields, 141(33333-337, 2008
Evarist Giné and Armelle Guillou. On consistency of kernel density estimators for randomly censored data: Rates holding uniformly over adaptive intervals. Annales de I' I'Institut Henri Poincaré (B)
Probability and Statistics, 37(4)5503-522, 2001.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018.
Hui Han, YuanYuan Wang, and Bing-Huan Mao. Borderline-MMOTE:: new over-sampling method in imbalanced data sets learning. In International Conference on Intelligent Computing, pages 878-887 Springer, 2005.
Haibo He and Edwardo A. Garcia. Learning from imbalanced data. JEEE Transactions on Knowledge and Data Engineering, 21(9): 1284, 2009.
Haibo He, Yang Bai, Edwardo A Garcia, and Shutao Li. Adasyn: Adaptive synthetic sampling approach for imbalanced learning. In 2008 IEEE international joint conference on neural networks (IEEE world congress on computational intelligence), pages 1322-1328, leee, 2008.
Lasse Holmström and Jussi Klemelä. Asymptotic bounds for the expected L error of multivariate kernel density estimator. Journal of Multivariate Analysis, 42(2):245-266, 1992.
Heinrich Jiang. Non-asymptotic uniform rates of consistency for k-NN regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3999-4006, 2019.
Mohammadreza M Kalan and Samory Kpotufe. Distribution-Fres Rates in Seyman-Pearson Classifi- cation. arXiv preprint arXiv:2402.09560, 2024.
Firuz Kamalov. Kernel density estimation based sampling for imbalanced class distribution. Informa- tion Sciences, 512: 112::199-1200 1201, 2020.
Miroslav Kubat and Stan Matwin. Addressing the curse of imbalanced training sets: one-sided selection. In Proceedings of the 14th International Conference on Machine Learning, pages 179-186. Morgan Kaufmann, 1997.
Guillaume Lemaitre, Fernando Nogueira, and Christos K Aridas. Imbalanced-leam:: A Python toolbox to tackle the curse of imbalanced datasets in machine learning. Journal of Machine Learning Research, 18(17):1-5, 2017.
Inderject Mani and Zhang, kNN approach unbalanced data distributions: a case study involving information extraction. In Proceedings of International Conference on Machine Learning (ICML 2003), Workshop on Learning from Imbalanced Data Sets, pages 1-7. ICML United States, 2003.
Colin MeDiarmid, On the method of bounded differences. Surveys in Combinatorics, 141(1): 148-188, 1989.
12

---

REFERENCES
Aditya Menon, Harikrishna Narasimhan, Shivani Agarwal, and Sanjay Chawla. On the statistical con- sistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pages 603-611. PMIR, 2013.
N. G. Meyers and J. Serrin. H W. Proceedings of the National Academy of Sciences, 51(6): 1053-1056, 1964.
Liviu Nicolaescu. Lectures on the Geometry of Manifolds (second edition). World Scientific, 2007.
François Portier. Nearest neighbor empirical processes. Bernoulli, (1(1)3122-332 2025.
François Portier, Lionel Truquet, and Ikko Yamane. Nearest neighbor sampling for covariate shift adaptation. Journal of Machine Learning Research, 25(410):1-42, 2024.
Philippe Rigollet and Xin Tong. Neyman-Pearson classification, convexity and stochastic constraints. Journal of Machine Learning Research, 12(86):2831-2855 2011.
Abdoulaye Sakho, Emmanuel Malherbe, and Erwan Scornet. Do we need rebalancing strategies? theoretical and empirical study around smote and its variants, 2024. URL/tttss://arxiv org/
abs/2405 03819
David W Scott. Mulfivariate density estimation: theory, practice and visualization. John Wiley & Sons, 2015.
Vimalraj Spelmen and R Porkodi. A review on handling imbalanced data. In 2018 International Conference on Current Trends towards Converging Technologies (ICCTCT), pages 1-11. IEEE, 2018.
Michel Talagrand. New concentration inequalities in product spaces. Inventiones mathematicae, 126 (3):505-563, 1996.
Xin Tong. A plug-in approach to Neyman-Pearson classification. Journal of Machine Learning Research,
2013.
Haiying Wang. Logistic regression for massive data with rare events. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learming, volume 119 of Proceedings of Machine Learning Research, pages 9829-9836. PMLR, 13-18 Jul 2020.
Hermann Weyl. On the volume of tubes. American Journal of Mathematics, 61(2):461-472, 1939.
Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. Class-weighted classification: Trade-offs and robust approaches. In International Conference on Machine Leurning, pages 10544-10554. PMLR, 2020.
Lirong Xue and Samory Kpotufe. Achieving the time of 1-NN, but the accuracy of k-NN. In Proceedings of the 21 International Conference Artificial Intelligence and Statistics, pages (628-16366 PMLR, 2018
13

---

REFERENCES
NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: As stated in the abstract, the paper establishes concentration bounds well as excess risk bounds for imbalanced classification using synthetic oversampling techniques. We have also included numerical experiments as stated in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper discusses some limitations of the work. In particular, Theorem 2 in Section highlights that the current theoretical results are limited a single test function G. Extending these results to uniform bounds over a class of functions G with controlled complexity remains an open problem. The authors explicitly note that their results represent initial step toward addressing this broader and more challenging extension.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
14

---

REFERENCES
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
The main theoretical results are discussed in the main paper, and further details of the theoretical results and the proofs of the main results are provided in the Supplement
Justification:
file. Most of the assumptions we needed are discussed in the main text, and details are provided in the Supplement.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The synthetic and real data experimental results provided in the paper are reproducible. The paper provides sufficient detail to reproduce the main experimental results. The synthetic data generation process is clearly described and algorithms for oversampling techniques are given the supplement file. Real datasets used are publicly available through the OpenML and UCI machine learning repositories. While the code is hosted on GitHub repository, link is withheld to maintain anonymity for the review process. Nonetheless, the paper includes all necessary implementation and evaluation details relevant to its main claims.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
15

---

REFERENCES
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The paper provides open access to the data and code. The authors have provided anonymous Zip file with supplement containing the necessary materials reproduce the main experimental results as per NeurlPS guidelines, Following the anonymous review process, the code will be released publicly via GitHub repository, with instructions to ensure reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips cuublic/guidee /ooeeeeeeooeeeumimacccea wwtponssssonPoo. ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: For the synthetic data experiments, the paper clearly describes how the training and validation datasets are generated. In the real-world application, the data splitting strategy is also provided. Additionally, key training details dethils-such hyperparameter choices and optimizer settings- are described sufficiently to understand and interpret the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

REFERENCES
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
The paper provides appropriate information about the statistical significance of the experimental results in terms of the AM-risk, which is the central evaluation metric. Rele- vant variability measures, lines, and bars are reported for synthetic and real-world application experiments, allowing for meaningful interpretation of performance differences.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The paper does not provide detailed information about the computational resources used for the experiments (e.g., type compute workers, memory, or execution time). However, the experiments appear in paper can be easily run on a standard personal computer.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
17

---

REFERENCES
Question: Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics http://ss.aaarr....c/aaaaaa/eeea
Answer: [Yes]
The paper complies with the NeurIPS Code of Ethics. The work does not involve human subjects, sensitive data, or applications with foreseeable harmful impact. The methods and results are reported transparently, and all claims are appropriately sup- ported by theoretical and empirical evidence. The authors have also made efforts to ensure reproducibility by providing code and data.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
18

---

REFERENCES
Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [No]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
19

---

REFERENCES
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: /ccppp//enearrrssscc/oofeeeeee/e for what should or should not be described.
20

---

Appendix to "Concentration and excess risk bounds for imbalanced classification with synthetic oversampling"
Touqeer Ahmad, Mohammadreza M. Kalan, François Portier, Gilles Stupfler
This appendix is organized as follows. We provide auxiliary theoretical results in Appendix A among which classical concentration inequalities and inequalities for convolution of density functions. We
then prove Theorem iin Appendix B and Theorem in Appendix C unified proof of Corollaries
and is given in Appendix DJ Appendix E and Appendix are dedicated to the proofs of Theorems gives the statement of Proposition 9 which is used in Remark 3
and 6, respectively. Appendix G
ol
the paper. Appendix HH gives a further set of numerical results complementing those of Section
A
Auxiliary results
A.1
Concentration inequalities
The following lemma provides a uniform bound on the distance between a point and its k-th nearest neighbor.
Lemma (uue and Kpotufe 2018). Lemma 1). Fix nı > 0 and let (Xis)sisn, be ii.dd samples from a distribution IP satisfying Assumption Define (x( as the Euclidean distance from a point E supp((P1) to its k-th nearest neighbor in [Ku]ssism Then, for all 6 1), with probability at least ô, it holds that
1/d mmax(k; (d+ log(2m1) + log(8/5)) (Ca)
Ak f1,...,m1h m1
sup (x(()) S xEsupp(E1)
n1
We next recall, without proof, the classical McDiarmid and -ouggque incqualities.
Lemma 2 (McDiarmid inequality, see McDiarmid (189)). Let Z1, Z2....... random variables taking values in some set X. Let T::T: X + be a function satisfying the bounded differences condition: for each E {1, .1,,,...,n). there exists a constant C₁ 2 O such that for all 21..... Zas 2 E.
......,2 Zn be independent
[T(z,...., 2i Ri, Aitl,..... .,)) T(= 2: 2/.
zn)l S C..
Then, for all t > 0,
2t2
P(T(ZZ,...... Zn) - ETT Zn)) 2 S exp
T
C
s=
212
and P( ,2, - E,, 2n)] [n)] -t) < exp
Σ ?
In particular, for any ô E (0, 1/2), it holds with probability at least - 25 that
log(1 10)
T(Z 2n) E Z.)Il S
Σ C7.
2 t=1
Lemma (Talagrand (996). Theorem 2.3 in Bousquet 2002]; with separability assump-
tions, Boucheron et al. [2013] p.315). Let 71...., 7m be independent and identically distributed random variables with values in a measurable space X. Let F be a separable class of measurable
functions f: X + I. that satisfy. for some U > 0.
Ef(Z,) = and [f(x)) SU for all FF xEX.
Let 0² = =supper Var (f((z)) Then for every t 0.
p Sn 1 B(S.)
2(n22 + 2UE(( + -t S r
(5)
where Sn can be either equal sup f(Zi) supjeF |E f(Z)))
21

---

A.2 Inequalities for the convolution of density functions
The next lemma simplifies the bound in the conclusion (5) of Lemma to a form that is more convenient for our purposes.
Lemma 4, Assume the setting of Lemma 3 Jand retain the notation therein. Then, for all 8 E (0, 1),
S. - (S.) + 2no2 log(116) + 1og(1/6) 2 1
where Sn, can be either equal sup fer E f(Z,) JEF EE f(Z,))
Proof. We take t (6) and bound the square-root term in 5 as follows:
v 2(nn² + 2UE(())) log(1/6) S V log(1/0) + AU B(S,) log(1/5)
S log(1/)) + (S,,) log(1/0).
Apply (5) in Lemma with log((1)) complete the proof.
A.2 Inequalities for the convolution density functions
The first lemma is the key ingredient in order to control variance terms in integrated L' ddeviations of kernel density estimators. It holds under simple conditions on the tails of f and K; in particular, it holds if f and K have compact support, and it holds under either Assumptions 5 under Assumptions 6
Recall the notation Mş(g)= == [1=1]]](=)dd.
Lemma 5. Let f. B + I be two density functions such that Ma+elf + K) for some E > O. Then it holds that
I VS* S VVa 1 11 2dd= / (Mate-((Matt())) ha+e Ma+o(K))
sc( + (d44))22
where == -Ca(11 + / Ma+e K)) and Cd.e is constant that depends on d and e only.
With this lemma
disposal and the notation of our paper, define Cy.d.r (1
MMa++(f + K)), which constant that appears in Theorem 6 and that depends on E, and K only. Extensions of this lemma may be found in Holmström and Klemelä 1992 Lemma 7 and Proposition 8), where an L' rate of convergence is established for the kernel density estimator; the above version is sufficient for our purposes.
Proof. Let g be a density function on Rd By the Cauchy-Schward inequality, it holds
J J1mppa g(())dx
V | ( / I Jhmpps ||م|| (d+c)
dx.
The second integral in the right-ham hand side can calculated using polar coordinates:
f M ||أ||
(d+=) dx = dVa / p (d+ts) p dp dp= dVa
psl
where Va is the volume of the unit ball in IR.d. Besides, by the Jensen inequality,
Jraless
Vg(z) dr - Va Vh g(x) dx 1 VVa' Va
Va
As consequence
/ Vo(x)dr=) -f / Vo(x)do +
/ Vo(z)dx s VVa
1 V d
|| g(x)dx
22

---

A.2 Inequalities for the convolution of density functions
It suffices to apply the above inequality to the density : x: f Kn(x) = I f(x - 22)Kn(2)d= and to notice that
f ||=:12² f Kn(r)dr=)
// |k|12 f(x - 2))
// ||s =1Æ (()
S 24+=-1
If (t)))tt)(()KK dz s 2dt==1 (Ma+e(J) + n M
(J
complete the proof.
We turn to two lemmas dedicated to the control of bias terms in integrated L deviations of kernel density estimators. These lemmas are in the same spirit as Lemma in Giné and Nickl (2008) as well as Lemma 6 in Delyon and Portier [2016), where similar quantities (these articles work with respect to probability measure instead of the Lebesgue measure) are analyzed using high-order kernels to benefit from the smoothness of f. Our approach is somewhat different as we rely on standard kernels under twice differentiability most. The rate of convergence obtained is therefore slower but the results have wider scope. Note also that Proposition 3 and Corollary I in Giné and Nickl 2008) provide (without rate) the convergence to 0 of similar quantities. One of the two statements below, which shall be used under Assumptions 4 and 5 Proposition 4].
is taken from Holmström and Klemelä 1992
Lemma 6 (Proposition 4 in Holmström and Klemelä 1992 ). Suppose that K is symmetric density function on Red, that M2(K) (K) < oo and J E WZ.(R (Ra). Then
J lf (f(KK(()>>> - f(x)ldx h2d
where
d Σ
/ f [2)(z)do +2
Σ /
Φ =
f(x)ddr
| (x()dx
Isicjsa'
is finite constant that depends on the L -norm of the second weak partial derivatives ff f (1 S i S d) of and only.
With this lemma at our disposal and the notation of our paper, we define o as being the constant appearing in (ii) with Sy. which is constant that appears in Theorem 6 and that depends on fy and K only.
Our next and final lemma is analogous to Lemma 6 but only requires the existence and integrability of the weak gradient of f. so that it can be applied under Assumptions 6 and 7 It should be clear that this result is not a straightforward consequence of the results of Holmström and Klemelä [992]. because it is not assumed below that f is smooth on the whole of R
Lemma 7, Suppose that
K is symmetric density function supported on B(0, 1).
f has a support S such that there are K., ro > O with A(OS + B(0,r)) S er for all (0,ro).
f WU.)(U), where U denotes the interior of S.
. f is bounded on as + B(0, 2ro).
If h < To. then it holds that
J - f
hob,
where, letting f denote the weak gradient of f.
/ [1V 22 + 2x
+ = (1)))
sup f(z).
se asas (0.2
23

---

A.2 Inequalities for the convolution of density functions
With this lemma at our disposal and the notation of our paper, we define Vy as being the constant v with f fy. which a constant that appears Theorem (lnn that depends on fy and K only.
Proof. Fix h S ro.
Write
/ [1((1 (f(x- - -(())) / (f(x + f(z))
f* - f(x))
by the symmetry assumption on K. Let as h). Since K is supported on B(0, 1), for f (x) - ((a) to be nonzero necessary that either E Sn or x E T. Moreover, the assumption S ensures that as S \ U has Lebesgue measure zero. Hence we have
J +
Kn(x) JIs*Kn(o)- -(x)dd S Soorp VENGA (S(c + -()) de
+ 1. V. B(OM)
- f(v)) dr.
(6)
We start by dealing with the first integral in the right-hand side of (6). By the Meyers-Serrin
theorem [Meyers and Serrin 1964), there exists sequence (fr) of functions that are infinitely
differentiable on and such that fn + f in W., that is, (1f((())) - f(x) + [])
V V - O. Note that when x E U O T and y E B(O,h), one has x + y U, and then obviously
JOnT UALONN
()( ( dr
= J SAICAD L' V Kr) dx.
This leads, for any n, to the inequality
dr
$ -T SBROAA [' y' Vffa + ty) (n) dy dx
I JAON - U + +v) - - dx
+ JunTs
+ J SBCOMS ('' VV -f) + 11) Kn(u) dy dx.
(7)
Clearly
S.nee JEIO ((fn
fz 8) (Un-f)(++++
- -fre ( dx S (f((x) f(x)(dr
and Soreee Venci ( vv f( Ky) dx < (K)(K) / (VV)(())-V(((l)))))
Both of these upper bounds converge to 0 as n + co. Then, letting + oo in we get
J.nn I (f(z (()))) dr < $ J "T Tv Kn) dx.
24

---

Now by a change of variables, symmetry of K, and the inequality,
Venuns L. Vf +x) (V))
-V vf(z - u) (f=+ x- ka(ttt)tt (a udu
1 IV - u)ll2
(fo 1 ( Ilullada
B(0,0))
(1l ||
where L(u) Co 1- --1-d ( Note that J [[L(()llldd [ K hM, (K).
As consequence
Momel/an (f( [(x)) de S [ (1VV/l2 * (1
UnT
- [VI(x))lad
/
[L(())ladu
(MM((K) [Vf(2))2dd..
(8)
Concerning the second integral in (6). since there x E T and y E BO0, holds that the distance of r + to OS is at most 2h and then [f + y) - f(x) < 2sup=eas-BBs B(0,2A)) f(z). Plugging this
along with ( into (6). we find, for h S ro. that
f [I - f(x))dx= & (K)(K) / [V + 21(T)
sup f(z).
=eas B(0,20)))2ro)
The assumption on yields X(T) = x(S + B(O, S sh and then
f - ((x)ddx S h (M(KK / [VI + 2
sup
f())
SEaS+BOU 200
as announced.
B Proof of Theorem 1
Let
Z (²F Z Smotte
(F)
Mmmote - -G)-E, []X]]]] GEF
sup
Given that n > 0, we decompose the supremum as (²) < ZF(F) + (FF), with
m
1
11
(i(F) = sup
G(X+)
71 Σ G(X1)
GEF
m
1=1
and ZF(F)
sup
G(X)) - E
GEF
We further bound each term on the right-hand side separately, beginning with the first one. Let us recall
aj (G(X)))2
m1 (
27
of(F)
G(Xis)
sup GEF
M1
m1
Lemma 8. Let D, = {(X,, Y be a set of i...d samples drawn from a distribution TP, and
let (XT) um be i...d. samples generated according the SMOTE algorithm (.). Suppose that
25

---

the minority class distribution P1 satisfies Assumption 7 Furthermore, let F be function class satisfying Assumptions andd Fix ò (0, 1/3). Then, on the event {n] > 03, we have
201 (F) log()
8B 3m
1/d
ks
1/d
P (F) S 4mm +
log (1/6) + L
Y
Ca
71
36.
Proof. First, recall that when > 0 then at each iteration i, Xi, is drawn uniformly at random on the line linking X1 to X1s, where X1 is drawn uniformly random from the minority class samples (Xuhisigny On the event {n1 > 0}, we then consider the following decomposition:
(FF))
sup GEF
((( - G((M))
sup GEF
1 m
m O
22
G(Xi))
m
T1
As for the first term in ( using the Lipschitz property of the function class F stated in Assumption 2 have
Σ sup GEF
-
I T||xi X1ill2
sup GEF
According to the SMOTE procedure described in Section 2.2 we have || & S x (Xir)
where (1(4) (Xis) denotes the distance the k-th nearest neighbor of X3; among the sample s (XI...... Xin }. Note that, by construction, rk (X,x)) T (&1;), with Tx+1 introduced
Lemma and representing the distance to the (k 1)-th nearest neighbor within the full sample (X11... la }. It follows, when n1 > 1, that
sup GET
m Σ m
(G(X)) G(Xx)) L max 1515m
TA
(1)
(X S L
(x)) (10) xEsupp(F1)
sup
Conditionally on Y1.. and given that nı 1, (X11, Xin, is an iid. sample of n1 elements with common distribution P1. Then applying Lemma] [
we obtain that, whenever n1 > 1,
3 Ca
1/d
max(k + 1. (d + 1) log(2m) log(8/5))
1/a
P sup (ESupp(P1))
(x) >
Y1:0
S 6.
11
Clearly max(k + 1, (d + 1) log(2n)) + log(8/8)) s max(2k, (d + 1) log(2n;) + log(8/6)) s 2kg so that, when n1
1,
6
1/d
1/d
sup (x+1 > #Esupp(P1)
Yim
S 8.
Ca
n2
Dealing with the case пı = 1 separately, for which the inequality below is trivial, and using (10), we obtain that whenever n, 0,
sup
Σ
m
-(X))))((())))))))))) ST.
(())) Ca
6
1/d
kis
1/d
Yis
2 1 8.
m
n1
For the second term in we further work conditionally on D,, while assuming that nı > 0. For any G F, define vha (z) G(x) p(G), where H(G) 1 Σn G(Xx)). Note that since Xu
drawn uniformly at random from (Xuihsssm we have ((G((n) Da) = μ(G), so the (Xx1) centered given D,,. Let
Sn = sup GEF m
1 m
Σ
vol sup
Σ
m
G(X)))
1 m1
Σ
a(x)s)
GE
m
i=1
26

---

The class of functions {go. G' FF satisfies the assumptions of Lemma 3 (with the centering assumption understood conditionally on D, and n, > 0), and
sup Var(#a((X1) (..) sup E (G(Xn) -=(G))²) GEF
GE.
1
Σ ((X))))
1 11
21 C(T))
)
21
oF(F).
sup
GeF
11
Using the symmetrization technique, we derive bound for [[Sm [Dn] in order to apply Lemma 4 Let {Xi+) / be independent copy of {Ku)) given Da. and let {e:):- be independent Rademacher random variables that are independent of the K/mmm (Xx) and of D,.. Then:
(c(Xw) G(X))) Dm
ElSm
Dn) S E
sup GET
(ghost sample)
Ei (G(X)) G(X(e)) Dn
= E
sup
(symmetrization)
GEFF
t=1
$ 2
sup
E, G(Xi+)
Dn
GEF m
2 (F),
where the last inequality follows from Assumption
Then, by Lemma appplied to Sm, we obtain
P
sup
1
G(X))
11 Σ
G(X1.)
s (F) +
20 log(1/0)
GE.F
m
m
8B
log (og(1/6 (1/8)
Da 2 1 - 5.
3m
By combining this with the same argument applied to -1'G = G. and using the symmetry of the Ey. we obtain
(F² log(1/6)
P
sup
G(X))
G(XI))
< (F) +
GEF
1=1
8B
+
log (1/8) Dn, 21 12--2 26.
3m
which implies that when n1 > have
1 n1
20 (F) log(1/8)
P
sup GEF
G(E))
G(X)) $ (F) +
n2
8B
log (0g())))
Yi:m
28
3m
by integrating out the conditional probability with respect to X1...., X,, The proof complete.
Lemma 9. Let D,, {X,,, Y:) be i.i.d. samples drawn from distribution and let F be Fix 8 (0.1/2). Then, whenever ny > O, and if
function class satisfying Assumptions 2 and 3
oFF = supGEF Var[G(XX)| = 11. we have
20 F log(1/8)
8B 3n1
P ZZ(F) < 4R,, (F) + (
l1g(1/8)
Y1m
25.
n1
Proof. Conditioning on the label sequence Yim (Y,,.., leaving the (Xii)sism i.i.d. Following the second part of the proof of Lemma 8 define vi (x:) = G(zr) E, [G()] and, when n1 > 0,
Yn) makes deterministic while
1 n1
Sa sup
va (X1:).
GC
TI
1=1
27

---

Then, on fn] > 0}, we obtain by the same argument that E[S,,, [1m] S 2R,, (F) and, by Lemma
get
(F) log(1/6)
8B
Sm S 4R (F) +
log(1/8)
Vim
2
71
3n1
Repeating the argument for -va we obtain the bound
(07 log(1/6)
P
sup GET
Σ
G(Xi))
B, [G()] S 4Rn, (F) +
71
n1
2m1
8B
log(1/0)
Yi:n
21-28
3n1
as required.
End of the proof of Theorem 7 Let > We have
IP (FZ t} Yım) P(ZZ* f3 Yim) 4mi00) ((Z* t Yim) [m==0))
However, from (F) _ (F) + (J), the union bound ensures that, if t l/ = t
P (1Z Yi:) (m:20)
IP (12) > t \m [m110)) + +P((2 t2 Yim) [mi10))
By Lemmas 8 and it follows that, whenever n1 > O,
P ((IZ(()) t} Yim) 56, where I and l2 are respectively chosen as the upper bounds in Lemmas
(11)
8 and resulting in
1/d
hi
1/d
t= 4Rm (F) + 4R (F) + L
Ca
71
+ 267 log(1/8)
20 (F)
(1/(
8B
8B
log(1/6).
m
n1
3m
3n1
When n1 0, we set / = too and thus P (((Z((F) 1 Y1
0. As a consequence, obtain
(F) > t) = E(P (1 > t} \ [mn1>0) & 58P (11 > 0) s 58, which completes the
proof.
C Proof of Theorem 3
We start exactly as in the proof of Theorem I
On the event n1 > 0, let
Z (F) ZKDBO (F)
sup GEF
|MKDEO (G) E, (XX)]
and write Z*(F) (F) + (2) with
1 Σ G(XR) G(XT)
Zi(F) = sup GET
im1
and Zi(F
sup
-(X)))E,(((()))
GeF
The second term has already been controlled in Lemma 9 The first term is the focus of the next lemma.
Lemma 10. Let D,, = {(X,, Y.)L= be a set of n i..dd. samples drawn from a distribution TP, and
let (Xi, 1m m be m i.i.d. samples generated according KDE-bbsed oversampling (2) Let F be
function class satisfying Assumptions and 3 Fix 8 E (0,1/3). Then, on the event [1 > 0}, we have
20² (F) (og((11)))
9B m
P
(iFF) S 4Rm (F) -
5LhM, (K) + (1/0) Yim
2 1 36.
m
28

---

Proof. Analogously to the proof of Lemma 8
we work on the event {nı > 0} to write, as in
(i()
sup
Σ
G(
+ sup GEF
Σ
G(X
1 Σ G(Xi))
GEF
==1
i=1
For the second term in the right-hand side, we obtained the proof Lemmal 8 that
R1
20 ( log(1/5)
sup
Σ
G(X))
G(X1s)
(F) +
GE
m
11
m
8B log(1/8
+ 3m
Yim
28
(12)
the event (ng 0}. The first term needs particular treatment because, contrast with SMOTE, the KDB-based perturbation hW; used generate Xi, from X is not bounded anymore. We further decompose this first term. Note that conditionally on the initial sample Dn and {ni 0}, the
A (G) = G(X1,) G(X1;) are i..dd and that, for any G F.
/
E B [
GG(X+ G(X)) & Lh (Illl2((w)dd = (hM)
(13)
We then have, when 71 > O,
m
m
sup GEF
(G( G(Xi:))
sup GEF
A
E[AH),.))
LhMI(K).
Since |A]
2B, have A |[ S 4B and, due the above bound on E[Aii||P,)
holds that
Var P,, < E|Ai S PF & 2BLLM
Applying Lemma
(with absolute value), we find that when m > O,
m
m
IP
sup GEFF
(A: E D.I)
2E
sup
Σ (A
E|A D..))
D
GEF
m
4BLhM (K) log
16B
log(1/8)
D,
6.
m
3m
Using 13) and the inequality ab S + for any a, b 2 0, we obtain that
sup GEF
Σ (G(X))) - -((x))
m
< (K)
+
19B
log(1/0)
D,
2 21-8.
m
3m
i=1
Then, when ni
0,
1
S 5LAM + 19B
P sup
-
log(1/8)
Yim
2 11 8
GET
3m
:-1
by integrating out the conditional probability with respect to X,...., X,, The result follows by recalling [2p.
End of the proof of Theorem 3 The proof is similar to that of Theorem Putting together the conclusion of Lemma 9 and that of Lemma 10 obtain that whenever n 0.
P (1 (F) > t} Y1m) < 56,
(14)
where
== 4Rn (F) 4mmm (F) + 5LLM,
(F)
B
27 8
2
+
log
121
m
71
The result follows because under nı = 0. it holds that IP(
+00 YY..) = 0.
29

---

D Proof of Corollaries and 4
We start by proving Corollary
2 and then we will adapt the proof obtain Corollary
Let
1 R1 == + no
(1mI20) Σ ((o(X)))) + 1 (m020) Σ al ((-o((oo)))
The proof starts with the standard decomposition
R1/2(08) inf R1/2(9)= S 2 sup [R1/2(9) Ray2(0)l-
sEG
sEG
This follows from, first, the inequalities
R1/2(08) inf (1)2(g) ges
R1/2(0b) - R1)2(0g) + R1y2(08) inf R1/2(9)
gEg
< sup 11/2((9) 1112((9)1 + inf (1)2(1) - inf R R1/2(9)
SEG
gEg
gEg
and, second, from the inequalities
inf
R1/2(0) inf R R1/2(9) R1/2(0') inf R2/2(9) 959
gEg
gEg
R R1/2(19) R1/2(00)
inf R1/2(g)
gEg
S sup (1/2(()) R2/2(1) + R1/2(1d) geg
inf (1/2(9)
valid for any g' E G. Then, by definition (g) and Rg (2()) and using m = no, we find, when no, n21 0,
B1/2(06)
inf (1)2(9)
gEg
m
no (((-g(Xoo)) Eo(e(-9(X)))))
< sup
Σ -
- [x(e((()))] Σ
,EG m + no
m
< sup 3Eg
((g(x;))) - [(((((()))
+ sup 9EG
((-g(Xox)) - Eole(-9(X)))
m
1 - - EIG(())
1 Ro
= sup GE
+ sup
G(Xus) - Eo|G(X))
m
GEE
Ø)
770 i=1
m
< sup GEF
G(X)) - E[((
+ sup GEF
G(Xoz) - - [x(]
(F) + ZoF
where (J) is introduced in the proof of Theorem and Zo(F) is the rightmost term. Regarding Zo(F), we can use Lemma 9 (with Fo instead of IP)) to get that, when no > 0, it holds that
(Zo(F)) > to Vim) S 28,
with
(F) log(1/8) + 3no
8B
to = 4R (F) +
log(1/8)
no
About the first term, Z' Z*FF), it shown in that, whenever ni
IP (Z* > Yı.) < 56,
with defined just below
II The union bound gives that, whenever no, n2 > 0,
IP R (1)2(08) - inf R1/2(9) > t + to Nim < 76.
geg
30

---

Then, setting t + to +oo in case 1o71 = 0, and considering the cases 7g > 0 and Ro7l 0 separately, we find
P R1/2(03)
- inf gEg
R1/2 > t to X1.m
=
P
[11/2 (11/2(00)
inf R1 R1/2(0) > + to 11m in S 76. gEG
Hence taking the expectation gives
R1/2(00) inf R1/2(0) 1 (1) S 76.
9Eg
We obtain the statement of Corollary b using that m no when rearranging the terms in t + to.
Concerning Corollary 4 the proof proceeds in similar fashion, up to the application of 11 At this point, we instead use to complete the argument.
E
Proof of Theorem 5
We have
2 E, (1(x))))) + ((()))()))
= = (1- (B(= (1-n + pi B( =o)))))()(()))
by taking conditional expecttiion with respect to X. Besides, (X)(X)) P1 and then
= (1 10-ppp)---
-r -L
+
= (1 -P) " +
follows that
2( - R1))(1))) = (1 -1- p1) 111i)''p1EL((LLeaaaaa
B(( [((xx==))(( - (())))
Observe that -100x)=)1-11(xx-11
[ [[)(())==) - -1((x)=11 and that, by definition
of g. (X) if and only if n(X) < pl. As such
(1(o(x)=0) - (o(x))=)) (X)) 1p1 (xx)
and then
2(R1/2(0) R1/2(1)) = (1 - (pp)p=)= "(1 - n(x))
(1 p1) s 1(00)))))))1((())) - (1
(((() - fo(z))dæ
S ( - fo(x) - (f((x) - fo(x:))der
where to obtain the last inequality, we have used that 9 and disagree if and only if fi - fo and fo have different signs. Conclude using the triangle inequality.
Proof of Theorem 6
The proof consists in applying Theorem 5 after obtaining two bounds on the I errors for and fi.- This leads to proving two preliminary results which are of interest in their own right. Recall that (z) 0 if ny 0.
31

---

Proposition (L' bound on class-specifi kernel density estimators). Ler ò E (0, and E {0, 1}. Then, on the event {ny > 0}. we have
F r (f [s(x))de S Cy,d, + 12(+))/22) >
Mo(K?)
log(1/6)
nighd
nyy
Oghh under Assumptions 4 anddd Lyg if S ro under Assumptions
Yim
2
6
and
where Cy.d,z (resp. Φy Vy) is defined below Lemma resp. below Lemma below Lemma) depends only on (K, Ju, d (resp. (K,y)))
7 and
Proof. Denote throughout by Yim the random vector (Yı...., Yn). We start by applying McDi- armid's incquality (Lemma 2). with respect to the conditional probability given Yim.
Ty Ty.. (X1, ................................ Xnn) / lfun(x) - fuu(()))(())((d)
Note that for any i (I,...,, n), whenever ny 0,
TY E5....,,,,11. X,, X,) TY.. (XI,..,,X, X...... X.))
||==v) /
KKax X;) Kn(x - Xi) <2 |[x=v) =: Ct.
ny
Remarking that Σi= Of for ny = O, we obtain by the McDiarmid inequality that with probability (conditionally on Y1..) at least 1 5,
(4/n,)) ) (ny >0). and that the assumption of Lemma 2 is trivially correct
/ ([m()))J((<(ll))) (x) s (fimtoo - ly Yim +
(lg((1/5) ng
(n,20)
Swapping integral and conditional expectation and using the triangle and (conditional) Jensen inequalities, we get
[lfaatt) - fo(x))dr S / / [(eart)) (funle)- - B((u)())) (I) (x) Yi.m dx
2
/ ((fa( -fanm))-((()) fo(z)) (c))ddd dx 22og(1 (0))
1n,207
(15)
Fly
The first two terms depend on Yim and are further investigated on the event {ny 0}. For the first term above, which the variance term, we have, by independence of the random variables (Y,, Xi)..... (Yn......Y............
E (Fmm(e) - (1(()))))(((ff((eeeeeee (2) Y1n
-X)
1=1
E(K [KKR X.))
n
[K (x: Xi-y v)
ny
Mo(K2)
ngh fy. Kr (z)
with k= = K2 K2/Mo(K22). By Lemma applied fy and K,
E (funlee) ( E(f -Euna))--EUuuu)))...)... Yim dx S (1 + A
Mk3) n2
(16)
32

---

For the bias term, noting that
= R(Ka(o 1 Σ <x
X)IV = y) = y * Kn(z),
Thy
we apply Lemma 6 to obtain that
/ [B(fu fa(x)lde S uyh
(17)
under Assumptions 45 and use Lemma to find
I sigh
(18)
under Assumptions G when h S ro- Combining 15 that the event
16
and T8
we have therefore shown
E = { [sn(()) -()h))) fo(x)ldo Cy.die(1 h1044)/22)
(o()
log (L/()
nyyh
+ oyh under Assumptions 4 viyh i S ro under Assumptions
and
6 and
has probability at least 1 8 conditionally Y1.. and when ny 0, which is the result.
Proposition "L'- -buud on kernel density estimators based on KDEO). Let E (0, 1/2). Then, on the event {ni > 0}, we have
P ( (f,((=) - (x))dxx s d,, + slaterrey
Mo (K msd
P
M)(K2) nyhd
+ (1,d,(11 + )
+ V2log(1/6)
V
Vmn
+ @1i x2) under Assumptions and
5
YIn
1hih + 8) if, s S ro under Assumptions G andd
2
where &i,d = (1 + / Mate(fun + K)) and with the notation of Proposition 7
Proof. Write the quantity of interest as
/ ffa(o))f(()l)))) s (onddddsf(iteee f1it,())
+ (E(f) -(())))))))(() (19)
We control the two terms on the right-hand side separately. Define
- - -.t...)iitfi.ttt))BBi---t-)-- E(fi (m:20)
and note that the function TD. satisfies the assumption of Lemma with C₁ = (2/m) [m) (n)>0). >a}- Since, given D, and {ni 0}. the Xi; are i.i.d. generated according to fun. we can therefore apply the McDiarmid inequality. conditionally on D,,, to obtain, with probability at least - 8 (conditionally on D.))
/ ((()))(((()))))))) $ ( B(fi DDm dr
2 llg(11/8)
1 (m1
m
33

---

Then the Jensen inequality gives that, with probability at least 8 (conditionally on Dn),
/ -((. & / (f - ((fi) (D,, dx
2log(1/0)
(m120)-
m
Now we investigate the behavior of the first term in the right-hand side on the event {n1 > 0}. We have
((it))) [Dm]
m Var(K,(I - x1)) = ECK3 (x1)
1
m Mo(K2)
Sin Kx(
mss
with K = K22")( Using Lemma
5 and the previous probability bound, we get that the event
E1 - (1fiiite) (ff,(0) (((,)))) s (1d,(( + s/d+0) /
(K2) mst
2 (l0((1))
m
satisfies ((E))Dn)) (m)200) & 8, and then, integrating out the conditional expectation with respect to X1, X
P(EilYim))(mms00 S 8.
(20)
To control the second term in 19 write
/ [B(f,,()))))-- - fi = / 1fnn * *K(x))())))))))))))))))(<)) - ff((z)ldr
< / 10fn - -fi) (o(x))dd f Ifi * -o(x)- f((x)l
/ ((a(())) - li (i())dd + / 1/1 1/1 Ko(t) (i()))dd.
was shown at the end of Proposition
7 that the event
{ [
- fi S c1,d.(1 (1+114+))1))
Mo(K2) ny hd
2 log (1/6)
h1 under Assumptions 4 and with if h < under Assumptions
6 and
has probability at least conditionally on Y1.m and when nı > 0. This statement with Lemma under Assumptions 4 Lemma 7 Assumptions 6 when I ro. allows to obtain that the event
Eg = {1 (ULT) - f1(x))dr s c..d.(11 + (d(e))/2)
Ma(K2) ny hd
(og(1/5) n1
(1b + 52) under Assumptions and 5 th1 (h + +) if h, S rn under Assumptions 6 and 7
+
satisfies
(21)
combination of 19 20 and 21 yields
PEE U E Y (m oop S (m) + ( 2m, S 26.
The result follows immediately.
34

---

End the the proof of Theorem 6 Since m = (m)0), we clearly have r)) 1/2 if and only if
fia(x) > (1)( Hence we can apply Theorem to obtain
R1/2(0") R1)2(9) S 1
- fo(s))dx
/ -
Using finally Proposition 7 to control the first term and Proposition 8 to control the second one, we conclude that
P R1/2(0") - R1/2(1)
$ C0,de
(1 11
Mo(K2) nggd
C1,de +
(1 + h
Mo(K2) ni
2
11,d (1 o(d4e)/2)
Mo(K2) ngsa
2 1lg((1/))
/ +
2 2
1 f Φns² 2 + (h² +22 under Assumptions and
Yim
I(non 30) 2 - 36.
2 1988 + wh (h + 8) if h1 S under Assumptions and
Rearrange the above upper bound (taken be infinite the event {nom1 0), and hence also valid on this event) and integrate out the conditional expectation given Yin to complete the proof. L
G Analysis of the kernel smoothing plug-in rule
Let us finally highlight that we get, as a direct byproduct of Theorem and Proposition 7 the following bound on the risk of the kernel discrimination rule
((x) ğn (x) ((fi(()))ooa=))))
based on the initial data only. This will used for comparison purposes with Theorem G Remark Proposition Let 8 (0, 1/2.. Then, with probubility at least 1 25,
R1/2(0) R1/2(0) = MM((K2)
Co.d,e (vigh
Ci,ds Vnind
(1 + (d+e)/22
2
1og(1/0)
+
+ V
2
(Øv + 01)h² under Assumptions 4 and
+
2
(wo
w/1hh if S ro under Assumptions and
with the notation of Proposition
7
where the upper bound is taken to infinite when 1on = 0.
H Additional numerical results
H.1 Algorithms for oversampling methods
Algorithm I exxplains the different steps of the SMOTE algorithm for generating synthetic samples while highlighting the different hyperparameters involved.
KDE-based oversampling (KDEO) is another option to tackle the imbalanced data in similar spirit to SMOTE. In contrast with SMOTE, the KDEO algorithm relies on kernel function K and bandwidth matrix H that governs the smoothness of the estimated density function and the tradeoff between bias and variance. Since the parameter H has a significant impact on accuracy of KDE, several methods have been developed to obtain appropriate choice of H. Algorithm exxplann the steps KDFO follows for oversampling compliance with the bandwidth selected through the multivariate version of Scott's s rule of thumb [Scott 2015).
35

---

H.2 Simulated data
Algorithm SMOTE
Input: Samples (X11.... Xin, } C R", number nearest neighbors is E {0, ...,,, A1 1}. and number of synthetic samples
1: for each i = 1..... ........ do
Generate X1, uniformly among {Xuihssssm
i > 1 and k: > O, generate X uniformly among the k nearest neighbors to X1s in the minority class deprived of X₁.- Else, do X1= = X1:-
X1 (1 - A)X + AX where À ~ 4 1]. 2: end for
3: Return (Xio Xim)
Algorithm 2 KDEO
Xin, J C gd, number of synthetic samples m Compute the (empirical) covariance matrix S of minority samples and the bandwidth matrix H1 to satisfy H? = -2/(d+4) (Scott's rule of thumb).
Input: Samples [X.,,..., ,
2: for each i 1 .....: : m do
Generate X,, uniformly among (Xuihgigm.
Generate W; ~ (0, Ip).
Generate X1, X1 + H,W,
end for 4:
Return (X%. )
H.2 Simulated data
We provide results linked the analysis of Examples I and in the main paper. Before that, also introduce a further example, where again, the {(X,, hisis are n 1000 i.i.d. samples from the distribution of (X, Y) and e; is the ith vector in the canonical basis of RRd.
B, with B ~ Bernoulli(0.5). Yi is extended generalized Pareto random variable, i.c. Y ~ EGPD( (X) o(X), (f, 0.5) and Y2 ~ (x)))),) where x(X)= = exp(X" e1), (X) = cxp(X e2) and (X) (xp es). Define Y 1(Z>() with tuning class imbalance.
Example S.1: Let Z = BY;
In Example S.1. the parameter L is tuned to achieve various probability levels (1 P1 0.60, 0.80, 0.85, 0.90, 0.92, 0.95). The considered methods are the ones introduced in Sections 3.2 and of the main document.
The AM-risk performances of the KS and KNN classifiers for Examples 1, 4, and 1 are reported in Figure 6 where both methods exhibit identical patterns and achieve superior performance with KDEO and BBC compared to SMOTE. Moreover, the KNNN classifier can further improved by tuning the hyperparameter K via CV, shown in Figure 7 A noticeable performance improvement can be observed in the KDEO-CV, SMOTE-CV results, but CV on yields poorer performance for the BBC. Moreover, SMOTE-Cr CV,, KDEO and BBC exhibit very similar performance, indicating that these methods enhance minority class representation comparably when used with KNN, which is consistent with the theoretical justifications presented in the main document.
We also consider other classifiers, i.c. Random Forest and Logistic Regression (LR), compared to the the main document. Figure shows the AM-risk results for the Random Forest classifier. The KDEO and BBC perform better than SMOTE terms of AM-risk. Further notice that KDEO still performs better than BBC even when the probability of the minority class P1 is small. In Example 4, all methods perform similarly. We did not use CV to select the number of features at each split, the low dimensionality makes CV not beneficial; without CV, BBC performs comparably to the oversampling methods across all examples.
In contrast, the LR classifier performs uniformly across all resampling methods (see Figure Notice that the I.R classifier performs worse when applied to more complex classification structures. This overall uniformity in results is in line with the results given in Theorems I and 3 as they suggest that
36

---

H.3
Real data analysis: Abalone, California, Teg Phoneme, and House 16H datasets
Methoss
SMOTE KMY
SMOTERS K38
SMOTE LR. SHOTEOI-AR
Nethods <2EO K3 KOEDIHI <S KOEO 41 KOEDINI-
Example
Exampic 4
Exemple
Example
0.0
0.34
C.5
0.45
AM
0.22
0.23
0.43
02
0.35
1000
Hi75
Eoi1
mi
Figure 5: Average AM-risk of KNN, KS, and LR classifiers on balanced data over 50 replications. Left: using SMOTE and SMOTE(K) with k E (7, 65). Right: using KDEO and KDFO with H cH1 and e ranging (1/20, 3) where H1 follows from Scott's rule.
Example 1
Example
Methods BBC
#3ED SHOTE
Methods BBC # K3FG SMOTE
KS
0.40
0.38
0.37
AM rbk
0.36
0.35
0.34
0.33
0.60
0.90
8.8
6.00
8.00
66:
0.0
P
Example 5.1
Methods
0.36
0.32
AM6 rak
0.2
626
0.00
280
8.02
0.00
0.50
2.55
Figure 6: Average AM-risk across different data imbalance regimes for the KS (described in Sec- tion 3.2) and KNN classification rules computed over 50 replications.
estimating the risk with SMOTE KDEO gives better results when K and H are small, underlining that oversampling may not be critical for such type of (parametric) classifier.
H.3 Real data analysis: Abalone, California, MagicTel, Phoneme, and House 16H datasets
We apply the Random Forest, KS, LR, and LR-Lasso classifiers to the real datasets considered in the main paper. The AM-risk results for the KS are given in Figure T0, those for Random Forest in Figure [I while results for the LR and LR-Lasso classifiers presented in Figure 12 The KS
37

---

H.3
Real data analysis: Abalone, California, Tag Phoneme, and House 16H datasets
Methods
KIED
SHOTE
Nethods
BEC
1060
SMOTE SMOTE-EV
BEC-CV
Example
Example
641-
0.41
0.38
AM Risk
0.36
0.3
033
0.80
6/0g
0.82
0
0.00
6ap
8.65
632
698
Nethods
BBC
SMOTE
BIC-CV KIE0-CY SHOTE-CY
Example S.1
0.40
0.35
AM Rbk
0.30
625
des
600
6.c
Figure 7: Average AM-risk across different data imbalance regimes for the KNN methods described in Section 4.1 computed over 50 replications.
classifier shows comparable performance to SMOTE and KDEO across all datasets. For instance, in the MagicTTll dataset, KDEO performs slightly better, while California and Abalone SMOTE stand superior. For the Random Forest classifier, SMOTE and KDEO-based oversampling exhibit comparable performance across all datasets. Similarly, both oversampling methods yield nearly identical results the LR and LR-Lasso classifiers, except for the Abalone and House 16H datasets. key finding is that using cross- validatiin select the number of features at each split in Random Forest and the regularization parameter in LR-Lasso consistently enhances performance across all scenarios, with the exception of Abalone and House 16H. The low dimensionality of the Abalone and House_ 16H datasets may explain the lack of performance improvement when CV is used for parameter tuning.
38

---

H.3 Real data analysis: Abalone, California, TagicTel, Phoneme, and House 16H datasets
Example
Example
AM
C.0
0.300
0.75
625
65
0d6
625
630
68
835
P
P1
Nethods
SMOTE
Methods XCEO
Example
A21 Ruk
es
1-Bt
Nothods 31t 1010 SM0TE
NMk
025
1-
Figure 8: Average AM-risk across different data imbalance regimes for the Random Forest classifier computed over 50 replications.
39

---

H.3 Real data analysis: Abalone, California, TagicTel, Phoneme, and House 16H datasets
Example
Example
LOGISTIC
LOG STIC
0.33
6.30
0.55
AM rdX
0.24
0.21
0300
0.22
639
68
Bar
Example
Example
Methocs
Methods
LOGISTIC
LOGISTIC
0.502
0.499
0.497
C21
0.45
600
-Pi
Example
Methocs BSC KDED SMOTE
LOGISTIC
C36
1-p
Figure 9: Average AM-risk across different data imbalance regimes for the Logistic Regression classifier computed over 50 replications.
40

---

H.3 Real data analysis: Abalone, California, TagicTel, Phoneme, and House 16H datasets
Methods
SMOTE
KDEO
0.3
AM Risk
0.2
0.1
0.0
Abalooe
Callomiar20%)
Califomiar1%%)
Californi(5%)
Magic (2120)))
MagicTell5%)
Phaneme
House 16H
MagicTel(10m)
Datasets
Figure 10: AM-risk corresponding to different rebalancing methods and datasets when using the KS classifier.
Methods
SMOTE
KDED
0.2
Abaione
Colioomit10%)
(
MagicTeiZ(0%)
HapicTe((109)
MagicTe(5%)
Phoneme
House, 1GH
Datasets
Figure 1I: AM-risk corresponding different rebalancing methods and datasets when using the Random Forest classifier.
41

---

H.3 Real data analysis: Abalone, California, TagicTel, Phoneme, and House_ 16H datasets
Methods
SMOTE SMOTE
KOEO
KDEO-CV
0.3
AM
0.1
0.0
Abalone
(20
Callomar1100)
Callforma
MagicTel110%
MagicTe85%)
Phonene
House, 16H
Dalasets
Figure 12: AM-risk corresponding to different rebalancing methods and datasets when using LR and LR-Lasso classifier. Methods containing the "CV" characters stand for the LR-Lasso classifier with regularization parameter tuned through CV.
42


Reviews:
[{"review_id": "dH7LcWfOPM", "reviewer": "Reviewer_1z62", "summary": "This paper develops a theoretical framework to analyze the behavior of SMOTE and related synthetic oversampling methods in imbalanced classification. The authors establish an exponential inequality to characterize the gap between empirical risk on synthetic samples and the true population risk on the minority class. Furthermore, they demonstrate that a kernel-based classification rule trained on synthetic data can achieve the minimax rate of convergence. The paper claims these theoretical findings lead to practical guidelines for better parameter tuning of both oversampling techniques and downstream learning algorithms, with numerical experiments provided to support the theoretical findings.", "questions": "- SMOTE is a classic algorithm with extensive research over the years, which has identified many shortcomings, such as its inability to fundamentally increase information, its failure to address issues of insufficient representation or noise in the original minority class, its sensitivity to noise and outliers, its tendency to cause boundary overlap, the curse of dimensionality, its inability to handle sub-cluster structures, and its limited performance in extreme imbalance ratios. Does the theoretical framework proposed in this paper address these known problems, or does it provide any specific insights or directions for resolving them?\n- Does Assumption 1 implicitly require that minority class samples are drawn independently and identically distributed from the overall distribution, or does the framework account for other sampling scenarios?", "limitations": "yes.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The paper tackles the significant and practical problem of imbalanced classification, which is prevalent across many real-world machine learning applications.\n- The paper develops a theoretical framework for understanding SMOTE and related oversampling methods, establishing exponential inequalities for the gap between empirical and true population risk on synthetic data, and demonstrating that a kernel-based classifier trained on synthetic data can achieve minimax optimal rates of convergence.\n\n## Weaknesses\n- The abstract claims the theoretical findings \"lead to practical guidelines for better parameter tuning of both SMOTE and the downstream learning algorithm\". However, the introduction does not elaborate on what these specific guidelines are, making this core claim feel unsubstantiated.\n- Assumption 1 imposes a strong condition on the minority class distribution requiring a minimum probability within any Euclidean ball and boundedness of its support. This assumption, particularly the minimum probability condition, is quite stringent and is unlikely to hold for many real-world minority class distributions. Relying on such a strong assumption significantly limits the generalizability and practical applicability of the subsequent theoretical proofs and results.\n- Section 3.2 provides detailed excess risk bounds for a specific kernel smoothing plug-in classifier, forming a cornerstone of the paper's theoretical contribution and leading to optimal bandwidth choices for KDE oversampling. However, in Section 4, the authors do not use the theoretically analyzed kernel smoothing classifier. Instead, they switch to a KNN classifier, justifying this only with \"it is a slight variation of kernel smoothing plug-in classifiers\" and \"for comparison purposes.\" While KNN and kernel methods share conceptual links, they are distinct algorithms with different statistical properties and convergence behaviors. Theoretical guarantees derived for one algorithm cannot be directly and unprovenly generalized to another.\n- The paper's title and abstract both claim to analyze SMOTE and related methods. While concentration inequalities are provided for both SMOTE and KDE , the more critical excess risk bound analysis only presents results based on KDE oversampling, conspicuously lacking a corresponding analysis for SMOTE. This incompleteness implies that the theoretical framework does not fully cover SMOTE, despite its prominent mention in the paper's stated scope.\n- The experimental results show that once cross-validation is used to select the classifier's parameters, the influence of the oversampling parameter becomes \"minimal\" . This finding substantially undermines the value of the paper's core claim to provide \"practical guidelines for better parameter tuning of both SMOTE and the downstream learning algorithm.\"", "was_revised": true, "final_justification": "After carefully considering the author's reply, I decided to raise my score.", "rebuttal": "First of all, we would like to thank the referee for his or her valuable comments and suggestions, which will help us to improve the quality and clarity of the manuscript. In what follows we provide answers to all of his or her comments suggesting the  changes that we would like to do in the next version of our paper.\n\n**1) The abstract claims the ... :**\n\nWe agree with the remark and will make the suggested changes in the new version where we will make sure that our choice for $k$ in SMOTE appears clearly in the introduction. Our point is that, when using SMOTE in a nonparametric framework (as in Section 3.2 where another KDE oversampling strategy is analyzed), one should take care of the bias-variance tradeoff, leading to choosing $k$ larger than the standard implementation $k=5$.\n\n**2) Assumption 1 imposes a strong condition ... :**\n\nIn practice, before generating synthetic samples, one may clip or truncate extreme outliers, or add small Gaussian jitter. These steps help ensure that the neighborhood of each data point contains sufficient mass for meaningful interpolation. The SMOGN method [Branco et al., 2017] adopts a similar approach by combining noise injection with SMOTE, and shows improved performance over standard SMOTE on certain datasets. Our theoretical guarantee therefore complements—rather than contradicts—this empirical practice.\n\nThis assumption is technical but essential for establishing our convergence rates for SMOTE. It ensures that the distance between any point $x$ and its $k$-th nearest neighbor in the sample is of order $(k/n)^{1/d}$. This, in turn, implies that the perturbation introduced by SMOTE does not deviate significantly from the original distribution. Such an assumption is well known in nonparametric estimation theory, where it is required to achieve minimax convergence rates. Many common distributions satisfy it---for example, the uniform distribution on the unit cube or any distribution with a density bounded away from zero on a domain with smooth boundary (see Jiang, 2019). As such, the assumption is both standard and necessary in what is among the first theoretical analyses of SMOTE. We also note that if the distribution is supported on a lower-dimensional subspace, such as a manifold of dimension $d_0$, the assumption can be adapted by replacing $d$ with $d_0$, resulting in improved convergence rates as in the paper \"$k$-NN regression adapts to local intrinsic dimension; Kpotufe, Samory; NeurIPS-2011\". We plan to make a remark about this after Assumption 1.\n\n**3) Section 3.2 provides detailed excess risk bounds ... :**\n\nThe reviewer is correct in pointing out that kernel smoothing classification is distinct from $k$-nearest neighbor (KNN) classification, and we agree that the transition between the two in our discussion may appear somewhat loose.\n\nTo clarify our position: the theoretical results in Section~3.2 for the kernel smoothing classifier stem from a natural synergy between KDE-based oversampling and kernel smoothing classification. Since both components rely on kernel density estimation, the resulting mathematical framework is coherent and relatively self-contained. We believe this structure has allowed our analysis and proofs to be more transparent and technically tractable. While similar results could, in principle, be developed for combinations such as KNN with KDE-based oversampling or KNN with SMOTE, we expect such extensions to be technically more involved and therefore beyond the scope of this paper.\n\nFurthermore, as detailed in our response to the next question, we have also derived a uniform convergence result for SMOTE, which directly addresses the performance of classifiers trained on SMOTE-generated synthetic data. We will include this result in the final version of the paper.\n\nRegarding the numerical experiments, we chose to focus on KNN primarily because it is more widely used and familiar within the machine learning community compared to the kernel smoothing classifier. That said, we also included results using random forests and logistic regression. We note that it is straightforward to incorporate results for the kernel smoothing classifier as well, and we are happy to include these in the supplementary material of the revised version.\n\n**4) The paper's title and abstract both claim to analyze SMOTE ... :**\n\nWe agree with the referee that the theoretical guarantees for SMOTE differ from those obtained for KDE-based oversampling. Specifically, the analysis for SMOTE establishes a concentration inequality showing that the empirical mean under SMOTE remains close to the population mean. In contrast, our results for KDE oversampling provide nonparametric excess risk bounds.\n\nRecognizing this apparent imbalance, we investigated possible extensions of the SMOTE concentration result. Encouragingly, we were able to generalize it to a uniform concentration inequality over a class of functions. The resulting bound is similar in structure to the original one, with the addition of a Rademacher complexity term to account for the function class's richness. This extension highlights the relevance of our results to neural network learning with SMOTE, and we consider it an important theoretical contribution.\n\nThis new uniform convergence bound has the same form as Theorem 1, except that it holds uniformly over a class $\\mathcal{F}$ of $L$-Lipschitz functions that are uniformly bounded, i.e., $\\sup_{G \\in \\mathcal{F}} \\|G\\|_{\\infty} \\leq B$. The bound on the supremum of the difference between the empirical mean and the population mean\n\n$\\sup_{G\\in \\mathcal{F}}\\left|\\frac{1}{m} \\sum_{i=1}^{m} G (X_{1i}^{*}) - \\mathbb{E}_{1}[G(X)]\\right|$\n\nremains structurally the same, with the addition of a Rademacher complexity term corresponding to the function class $\\mathcal{F}$. Note that it does not involves too many changes in view of the revision.\n\nThe proof is similar to that of the previous version, except that we now use the Talagrand--Bousquet inequality, which provides a concentration bound for the quantity $S_n - \\mathbb{E}[S_n]$, where\n\n$$S_n = \\sup_{f \\in \\mathcal{F}} \\sum_{i=1}^n f(Z_i),$$\n\nthe random variables $Z_i$ are i.i.d. random variables, and $\\mathcal{F}$ is a uniformly bounded class of functions.\n\n**5) The experimental results show that once cross-validation ... :**\n\nWe agree with the reviewer's observation. Our theoretical findings indicate that the choice of hyperparameters for both SMOTE and KDE-based oversampling is critical, and that standard implementations do not select them optimally especially when a nonparametric classifier is employed as in Section 3.2 of the paper. In fact, our result shows that when a nonparametric estimator is used the choice of $k$ should be made to achieve bias-variance tradeoff. For this reason we advocate in the experiments that the Scott rule, which typically optimizes bias-variance tradeoff, might be a good choice. We plan to claim this in a clear way in the next version.\n\nThis also motivated us to explore cross-validation strategies for selecting the classifiers' hyperparameters. Interestingly, we found that when model hyperparameters are properly tuned via cross-validation, the sensitivity to SMOTE’s hyperparameters is significantly reduced while not solving the problem yet (see Figure 1 for KDE-based oversampling where choosing a too large bandwidth diminishes the accuracy). This is an important insight, as it suggests a promising direction for future work: studying the interaction between SMOTE hyperparameters and cross-validation-based model selection. We agree that this perspective should be more clearly articulated, and we are happy to revise the conclusion—and possibly other parts of the paper—to highlight this point and encourage further investigation.\n\n**Questions:**\n\n**1) SMOTE is a classic algorithm with extensive ... :**\n\nThe reviewer's list of concerns is extensive and, to some extent, shared by many other approaches in the literature. We believe, however, that our work offers useful insights into several of these issues.\n\nFirst, as stated in the introduction, one key point of our paper is that SMOTE does not introduce new information: synthetic samples are generated from existing data without incorporating additional observations. From this perspective, SMOTE serves primarily as a mechanism for balancing risk, thereby enabling the derivation of new theoretical results using new information.\n\nSecond, our work sheds light on the curse of dimensionality inherent both in nonparametric methods and the newly derived theorem for the uniform convergence case, which is suitable for neural networks. As shown by the convergence rates in Section 3.2, oversampling methods such as KDE oversampling are also subject to some limitation since the term $1/(n_1h^d)$ appears in the bounds. However, the result in Section 3.1 highlights a different aspect: SMOTE can be effective in training parametric classifiers by minimizing the SMOTE empirical risk. Such approaches are known to be less vulnerable to the curse of dimensionality.\n\nThird, regarding its sensitivity to outliers, this highlights the importance of Assumption 1, which requires that there be sufficient mass around the data points. In practice, one common approach is to clip or truncate extreme outliers, which aligns with Assumption 1 used in our work.\n\nFinally, regarding extreme imbalance ratios, our analysis identifies a boundary condition for learning. For training a parametric classifier, it is necessary that $np \\to \\infty$, where $p$ is the probability of minority class, while for nonparametric rules, learning is feasible under the weaker condition $np h^d \\to \\infty$.\n\n**2) Does Assumption 1 implicitly ... :**\n\nNote that our problem setting (Section 2) implies that the base sample $D_n$ is independent and identically distributed. We will make this more clear in the final version."}, {"review_id": "0NcQf5l8zG", "reviewer": "Reviewer_pe2f", "summary": "This paper provides a theoretical analysis of synthetic oversampling methods—specifically SMOTE and KDE-based techniques—for binary classification under severe class imbalance. The authors analyze the statistical properties of oversampling from both a concentration and excess risk perspective:\n\t1.\tConcentration bounds (Theorems 1 & 2, pages 5–6) are derived to relate the empirical risk computed on synthetic minority samples to the true population risk. These are obtained for both SMOTE (via nearest neighbors) and KDE (via random samples from an estimated density).\n\t2.\tExcess AM-risk bound (Theorem 4, page 11) is established for plug-in classifiers trained on synthetic data generated via KDE. The bound decomposes the error into bias and variance components and suggests optimal bandwidths for both sample generation and classifier construction.\n\t3.\tPractical guidance is derived from the theory—e.g., justifying small k in SMOTE and the importance of tuning bandwidths in KDE—especially under extreme imbalance n_1/n_0 \\to 0.\n\t4.\tExperiments on both synthetic and real datasets (Section 5) validate these theoretical findings and examine the effect of different oversampling hyperparameters on performance across various classifiers.\n\nThe work unifies existing data-level and model-level approaches to class imbalance, offers new non-asymptotic theoretical tools, and motivates principled hyperparameter selection in oversampling pipelines.", "questions": "1.\tExtension of Theorem 4 to SMOTE:\nYou mention (line 257) that excess risk analysis for SMOTE is more difficult. Is this due to the discontinuous support of the interpolated samples? Could an approximation (e.g., under smoothness of f^*) yield a rough bound?\n\t2.\tBandwidth mismatch:\nTheorem 4 (line 237) suggests that the optimal KDE bandwidth for sample generation may differ from the optimal classifier bandwidth. Do your experiments support this? Can you comment on how sensitive the AM-risk is to this mismatch?\n\t3.\tLogistic regression stability:\nIn line 335 (page 14), you mention that logistic regression is relatively unaffected by oversampling. Given that Theorems 1–2 still apply in principle, is this due to insensitivity to data augmentation, or model robustness to density perturbation?\n\t4.\tApplicability of concentration bounds to learned classifiers:\nWould it be possible to extend Theorems 1–2 to uniform convergence over a class of Lipschitz classifiers (e.g., KNN or kernel classifiers)? If not, could empirical Rademacher complexity or covering number arguments be layered on top?\n\nSuggestions for Improvement\n\t•\tAdd a brief discussion on how Assumption 5 aligns with the geometry of P(X|Y=1). If the data lives in \\mathbb{R}^d, the measure condition should reflect dimensionality.\n\t•\tConsider including a KDE vs. SMOTE comparison in excess risk terms, even if only heuristic or simulated.\n\t•\tInclude a toy experiment showing the effect of varying h and s in accordance with Theorem 4, to highlight the practical relevance of the theory.\n\t•\tClarify whether your theoretical guidance can improve hyperparameter tuning in practice compared to cross-validation.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\t•\tNovel theoretical analysis: The concentration bounds (Theorems 1 & 2) and excess risk result (Theorem 4) represent significant theoretical contributions that go beyond standard margin-based generalization theory. The analysis draws from nonparametric statistics and covers both SMOTE-like (nearest-neighbor-based) and kernel-based oversampling.\n\t•\tPractical motivation and implications: The work sheds light on popular heuristics such as SMOTE with k=5, showing when such defaults are suboptimal. The theoretical results suggest parameter tuning strategies, particularly in severely imbalanced regimes.\n\t•\tUnifying perspective: The framing of synthetic oversampling as a reweighting scheme that alters the data distribution while maintaining the form of the classifier allows the authors to bridge the gap between model-level and data-level solutions.\n\t•\tEmpirical alignment: The experiments (Section 5, Figures 1–3) are consistent with theoretical insights. For example, small k in SMOTE and tuned bandwidths in KDE improve performance in high-imbalance settings, especially with nonparametric classifiers like KNN.\n\n⸻\n\nWeaknesses\n\nNo excess risk bound for SMOTE:\nWhile Theorem 4 provides an excess AM-risk bound for KDE-based oversampling, no analogous bound is developed for SMOTE. This creates an asymmetry in the paper’s theoretical treatment, despite positioning SMOTE and KDE as parallel methods. The authors acknowledge this in Remark 3 (line 257, page 12), stating that the analysis is difficult, but the lack of even a heuristic or qualitative bound limits the completeness of the comparison.\n\n Optimality claim is narrow in scope:\nThe authors argue in Remark 3 (lines 244–247) that the KDE bound is minimax-optimal in the regime n_1/n_0 \\to 0, but no general lower bound or tightness analysis is provided outside this limit. In more typical imbalance regimes, it is unclear whether the bound remains informative. A discussion of whether the bias–variance tradeoff changes with milder imbalance would help contextualize the theoretical result.\n\n Experiments do not test theory-guided hyperparameter choices:\nAlthough Theorem 4 and the surrounding discussion motivate specific bandwidth choices h, s for KDE sample generation and classification, the experiments (Section 5) rely on heuristic rules (e.g., Scott’s rule, line 326) or cross-validation. There is no test of whether the theory-derived bandwidths improve performance, nor whether cross-validated choices align with theoretical prescriptions.\n\nAssumption 5 may be overly strong:\nAssumption 5 (line 201, page 10) requires that\n\\inf_{x \\in \\mathcal{X}} P(B(x,r)) \\geq C_1 r,\nwhich is unrealistic in high-dimensional Euclidean spaces where measure scales as r^d, not r. Unless the support of P(X|Y=1) lies on a one-dimensional manifold, this assumption is too strong. Clarifying whether this is a typo or whether the support is indeed lower-dimensional would improve the paper’s theoretical transparency.\n\nNo uniform concentration: The concentration inequalities (Theorems 1 & 2) are stated for a fixed Lipschitz function G. As noted in line 165, these do not extend to uniform convergence over function classes. This means the results do not directly guarantee generalization for learned classifiers trained on synthetic data.", "was_revised": true, "final_justification": "I've read the responses and the comments, I've decided to keep my score.", "rebuttal": "First of all, we would like to thank the referee for his or her valuable comments and suggestions, which will help us to improve the quality and clarity of the manuscript. In what follows we provide answers to all of his or her comments suggesting the changes that we would like to do in the next version of our paper.\n\n**1) No excess risk**\n\nObtaining an analogous nonparametric bound for SMOTE-based oversampling is indeed difficult because, as we point out below as an answer to your first question, SMOTE-based oversampling is essentially 1-dimensional while KDE-based oversampling is $d$-dimensional. The techniques we use and develop are only well-suited to the analysis of synthetic samples that do not lie in a lower-dimensional subspace of $\\mathbb{R}^d$. That being said, since KDE-based oversampling can itself be viewed as an approximation of SMOTE-based oversampling (due to kernel smoothing), it is possible that Theorem 4 represents a rough version of what could be obtained for SMOTE. \n\nFurthermore, we investigated possible extensions of the SMOTE concentration result. Encouragingly, we were able to generalize it to a uniform concentration inequality over a class of functions, yielding an excess risk bound for SMOTE. The resulting bound is similar in structure to the original one, with the addition of a Rademacher complexity term to account for the function class's richness. This extension highlights the relevance of our results to neural network learning with SMOTE, and we consider it an important theoretical contribution.\n\nThis new uniform convergence bound has the same form as Theorem 1, except that it holds uniformly over a class $\\mathcal{F}$ of $L$-Lipschitz functions that are uniformly bounded, i.e., $\\sup_{G \\in \\mathcal{F}} \\|G\\|_{\\infty} \\leq B$. The bound on the supremum of the difference between the empirical mean and the population mean\n\n$\\sup_{G\\in \\mathcal{F}}\\left|\\frac{1}{m} \\sum_{i=1}^{m} G (X_{1i}^{*}) - \\mathbb{E}_{1}[G(X)]\\right|$\n\nremains structurally the same, with the addition of a Rademacher complexity term corresponding to the function class $\\mathcal{F}$. Note that it does not involves too many changes in view of the revision.\n\nThe proof is similar to that of the previous version, except that we now use the Talagrand--Bousquet inequality, which provides a concentration bound for the quantity $S_n - \\mathbb{E}[S_n]$, where\n\n$$S_n = \\sup_{f \\in \\mathcal{F}} \\sum_{i=1}^n f(Z_i),$$\n\nthe random variables $Z_i$ are i.i.d. random variables, and $\\mathcal{F}$ is a uniformly bounded class of functions.\n\n**2) Optimality claim**\n\nRemark 3 does not address minimax optimality; rather, it discusses the optimal choice of bandwidths. By \"optimal\" here, we mean the bandwidths that minimize the upper bound, and we will clarify this point in the revision.\n\nFurthermore, regarding the minimax optimality, and in the case of milder imbalance $n_1/n_0\\to \\lambda<1$, the bound from Theorem 4 takes the form of a sum of variance and bias terms, including components like $(n_1 h^d)^{-1/2}$, $(n_1 s^d)^{-1/2}$, $h^2$, $s^2$. Optimizing over bandwidths $h$ and $s$, we find $h^\\star \\asymp s^\\star \\asymp n_1^{-1/(d+4)}$, leading to an excess risk of order $n_1^{-2/(d+4)}$. This shows that, under milder imbalance, the bias–variance tradeoff behaves similarly to classical nonparametric settings, and the KDE approach retains favorable properties. \n\nOf course, the above expression is of no use in the highly imbalanced regime $n_1/n_0\\to \\lambda=0$. In this highly imbalanced regime, the optimal KDE bandwidth becomes dependent on $n_0$, as indicated in our submission. We will include this summary in the revision to better contextualize Theorem 4.\n\n**3) Experiments**\n\nAs shown in Figure 1, Section 4 of the main document, we use Scott’s rule to select the bandwidth $h=n_1^{-2/(d+4)}$ and additionally examine the effects of both larger and smaller bandwidths to assess sensitivity. We also agree to include results using the theoretically optimal bandwidth. However, we anticipate that these results will not differ significantly from those already presented. Indeed,  Scott's rule is optimizing (up to constants) the upper bound of Theorem 5 (under Assumption 2 and 3).\n\n**4) Assumption 5**\n\nAssumption 5 is about the regularity of the boundary of the supporting set $S_y$, rather than about its interior, and we will be happy to make this explicit in the revision to avoid any confusion. Note that the set $\\partial S_y  + B(0,r)$ in Assumption 5 is usually not shrinking in every direction, which is why $r$ appears rather than $r^d$ in the upper bound; for instance, if $\\partial S_y$ is a circle in the Euclidean plane $d=2$, then $\\partial S_y + B(0,r) $ is just an annulus around this circle having area proportional to $r$. As explained in the text below this assumption, it is satisfied if, for example, $\\partial S_y$ is a finite union of compact, closed and smooth submanifolds of dimension $d-1$ in $\\mathbb{R}^d$ whose pairwise distances to one another are nonzero. This is, we think, the typical case in practice. If the reviewer was actually thinking of Assumption 1, let us recall that this assumption reads as follows\n\n``There exists a constant $C_d>0$ such that for all $x\\in \\text{supp}(\\mathbb{P}_1)$ and all $r>0$, we have $\\mathbb{P}_1(B(x,r))\\geq \\min\\{C_d r^d,1\\}$.''\n\nThis is the realistic setting the referee was mentioning, with a small ball probability scaling as $r^d$.\n\n**5) No uniform concentration**\n\nIn the answer to the referee's first question, we mentioned that we have extended the results to establish uniform convergence for a class of uniformly bounded functions.\n\n**Questions**\n\n**1)Extension of Theorem 4 to SMOTE**\n\nFirst, we note—as mentioned in response to previous questions—that we were able to extend the current results for SMOTE to a uniform convergence setting, yielding an excess risk bound for a class of uniformly bounded functions. We will incorporate this result into the revised version of the paper. However, deriving nonparametric excess risk bounds analogous to Theorem 4 remains challenging in the context of SMOTE.\n\nLet us, first of all, highlight that KDE-based oversampling can itself be viewed as an approximation of SMOTE-based oversampling. Indeed, as outlined in Sections 2.1 and 2.2 of our submission, KDE oversampling can be interpreted as, given a kernel function \\( K \\) and bandwidth $h > 0$, drawing synthetic samples $X_1^*$ from the KDE $\\hat{f}_{1h}$ which is equal to\n\n$(1/n_1) \\sum_{i=1}^{n_1} K_h(\\cdot - X_{1i})$ in the minority class. \n\nThis is a regularized version of sampling from the mixture $(1/ n_1) \\sum_{i=1}^{n_1} \\hat K(\\cdot, X_{1i})$, where $\\hat K(\\cdot, z)$ denotes the uniform distribution over the union of segments \n\n$\\bigcup_{j=1}^k (z, \\hat X_{1j}(z) )$ where $\\hat X_{1j}(z) $ being the nearest neighbors to $z$ in the minority class, which is nothing but SMOTE resampling.\n\n**2) Bandwidth mismatch**\n\nAs discussed in our response to Comment 3, our experiments confirm that the AM-risk is indeed more sensitive to the KDE bandwidth (used for sample generation) than to the classifier bandwidth. This supports the theoretical insight from Theorem 4, which highlights a potential mismatch in optimal bandwidths for these two components.\n\nIn practice, we observed that careful tuning of the KDE bandwidth significantly impacts performance, while variations in classifier bandwidth have a relatively smaller effect. To mitigate the mismatch, we adopted a data-driven approach to select bandwidths, optimizing for downstream AM-risk. This strategy led to consistent improvements, as shown in Figure 2. These findings reinforce the importance of treating KDE and classifier bandwidths as separate hyperparameters during tuning.\n\n**3) Logistic regression stability**\n\nWhen comparing our new uniform concentration inequality (stated above to answer the referee's first question) to our Theorem 5 (nonparametric excess risk), we see that learning a classifier with SMOTE or KDE based oversampling from a parametric class is easier than learning a nonparametric classifier (such as the investigated kernel smoothing classifier). Indeed, for non-parametric learning, SMOTE parameter $k$ needs to achieve bias-variance tradeoff while, in contrast, $k$ can be as small as possible when training a parametric classifier. Our interpretation is that this is due to (relative) insensitivity to data augmentation because the logistic regression classifier, being parametric, converges with a faster rate than the $K$NN classifier.\n\n**4) Applicability of concentration bounds**\n\nAs mentioned in response to the previous questions, we were able to extend the current result to uniform convergence over a class of uniformly bounded functions. This leads to an excess risk bound for classifiers trained on synthetically generated data.\n\n**Suggestions**\n\nWe will be happy to do so for both Assumptions 1 and 5 in order to remove any potential source of confusion.\n\nNow that we have excess risk bounds based on uniform convergence results, we will include a comparison.\n\nWe will conduct experiments using kernel classifiers to demonstrate the impact of kernel bandwidths used for classification and those used for generating synthetic examples.\n\n**hyperparameter tuning:**\n\nThe Scott rule that is proposed to tune $k$ in SMOTE or $H$ in KDE oversampling, is inspired form our theory, especially the excess risk bound in Theorem 5. Our findings is that it provides a reasonable choice for both approaches as it consistently performs well across all the experiments we have conducted. Cross-validation was also employed to tune the\nclassifier’s hyperparameters, resulting in a significant performance improvement, as illustrated in\nFigure 2. We will investigate this further in the revised manuscript.We plan to make this clearer as this point was also suggested by the other referees."}, {"review_id": "p4WM53K7mH", "reviewer": "Reviewer_P1wd", "summary": "This paper provides a theoretical framework for analyzing SMOTE and its variants, widely used for imbalanced classification. It establishes an exponential inequality bounding the gap between empirical and population risk on synthetic data, and proves that kernel-based classifiers trained on such data can achieve minimax optimal rates. The results offer practical insights for tuning SMOTE and downstream models, supported by numerical experiments.", "questions": "1. How do the theoretical guarantees extend to or break down when using modern non-kernel classifiers, such as deep neural networks, which are commonly used in imbalanced classification tasks?\n\n2. Can the authors comment on the robustness of their bounds in high-dimensional settings, where synthetic samples generated by SMOTE may suffer from over-smoothing or introduce unrealistic interpolations?\n\n3. How does the proposed framework handle or adapt to more advanced oversampling strategies (e.g., BorderlineSMOTE, ADASYN), and can similar concentration and excess risk bounds be established for those methods?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper establishes an exponential concentration inequality quantifying the discrepancy between empirical and population risk on synthetic minority samples. It also proves minimax optimality of kernel-based classifiers trained with SMOTE-generated data, an important contribution that formalizes a widely used heuristic.\n\n2. The theoretical insights directly inform practical guidelines for tuning SMOTE parameters and the downstream classifier, enhancing the usability of the findings.\n\n3. Establishing minimax rates when learning from synthetic examples is a fresh angle in theoretical ML and adds depth to the understanding of oversampling strategies.\n\nWeaknesses: \n\n1. The theoretical results rely on smoothness assumptions and kernel-based classifiers, which may not capture the behavior of neural networks commonly used in practice.\n\n2. The framework appears focused on binary classification. An extension to multi-class imbalanced settings would broaden applicability and address a more general class of real-world problems.", "was_revised": true, "final_justification": "I find the potential extension of the SMOTE concentration result to a uniform concentration inequality over a class of functions particularly interesting, and I encourage the authors to include a discussion of this. My concerns have been largely addressed, and I will maintain my current evaluation.", "rebuttal": "First of all, we would like to thank the referee for his or her valuable comments and suggestions, which will help us to improve the quality and clarity of the manuscript. In what follows we provide answers to all of his or her comments suggesting the  changes that we would like to do in the next version of our paper.\n\n**1) The theoretical results rely on smoothness assumptions and kernel-based classifiers ... :**\n\nTheorem 1 does not rely on smoothness assumptions and only depends on Lipschitz continuity, which includes the case of neural networks. However, it does not provide an excess risk bound for a classifier trained on synthetically generated data.\n\nFurthermore, we investigated possible extensions of the SMOTE concentration result. Encouragingly, we were able to generalize it to a uniform concentration inequality over a class of functions, yielding an excess risk bound for SMOTE. The resulting bound is similar in structure to the original one, with the addition of a Rademacher complexity term to account for the function class's richness. This extension highlights the relevance of our results to neural network learning with SMOTE, and we consider it an important theoretical contribution.\n\nThis new uniform convergence bound has the same form as Theorem 1, except that it holds uniformly over a class $\\mathcal{F}$ of $L$-Lipschitz functions that are uniformly bounded, i.e., $\\sup_{G \\in \\mathcal{F}} \\|G\\|_{\\infty} \\leq B$. The bound on the supremum of the difference between the empirical mean and the population mean\n\n$\\sup_{G\\in \\mathcal{F}}\\left|\\frac{1}{m} \\sum_{i=1}^{m} G (X_{1i}^{*}) - \\mathbb{E}_{1}[G(X)]\\right|$\n\n remains structurally the same, with the addition of a Rademacher complexity term corresponding to the function class $\\mathcal{F}$. Note that it does not involves too much changes in view of the revision.\n\nThe proof is similar to that of the previous version, except that we now use the Talagrand--Bousquet inequality, which provides a concentration bound for the quantity $S_n - \\mathbb{E}[S_n]$, where\n\n$$S_n = \\sup_{f \\in \\mathcal{F}} \\sum_{i=1}^n f(Z_i),$$\n\nthe random variables $Z_i$ are i.i.d. random variables, and $\\mathcal{F}$ is a uniformly bounded class of functions.\n\n**2) The framework appears focused on binary classification.**\n\nTheorems 1 and 2 do not, in fact, assume a binary classification setting; rather, they show that the empirical mean with respect to the probability of a synthetically-generated class concentrates around the population mean. This is of course readily adapted to the multi-class classification setting by fixing one reference class from which synthetic observations are sampled and as such, our results immediately apply to multi-class classification. However, the current statements of Theorems 1 and 2 do not provide excess risk bounds for a learned classifier. With the extension of these results to the uniform convergence setting, we can obtain excess risk bounds for multi-class classification as well, as explained in the previous answer.\n\n**Questions :**\n\n**1) How do the theoretical guarantees extend to or break down when using modern non-kernel classifiers**\n\nAs mentioned in the previous question, since we have established a uniform convergence result for a class of uniformly bounded functions, it implies that we can derive excess risk bounds for classifiers such as neural networks, given their finite Rademacher complexities. This extension directly addresses the reviewer’s question and will be incorporated into the revised version.\n\n**2) Can the authors comment on the robustness of their bounds in high-dimensional settings**\n\nOur bounds remain valid in any dimension. As the dimension $d$ increases, the bias term $(k/n_{1})^{1/d}$ shrinks more slowly and can overtake the $n_{1}^{-1/2}$ variance term, so the overall upper bound becomes looser—the classic curse of dimensionality. Using a moderate neighborhood size (e.g., $k \\propto n_{1}^{4/(d+4)}$ ) or first projecting onto a lower–dimensional subspace (PCA or manifold‑SMOTE) keeps this bias under control and prevents oversmoothing from dominating.\n\n**3) How does the proposed framework handle or adapt to more advanced oversampling strategies**\n\nThe main difficulty with these approaches is that they select neighborhoods from both classes. In contrast, we rely on uniform bounds for k-NN, which are based on data from a single distribution. In the case of BorderlineSMOTE, one must handle data from two distributions simultaneously while still bounding the risk with respect to one of them."}, {"review_id": "ZXtInovyJ8", "reviewer": "Reviewer_eFiF", "summary": "This paper presents a rigorous theoretical framework for analyzing SMOTE and KDE-based oversampling techniques in imbalanced classification. The work makes significant theoretical contributions while maintaining practical relevance.", "questions": "How does performance scale with increasing dimensionality?", "limitations": "The author has established important theoretical results in the paper and should discuss how to guide the selection of hyperparameters in practical applications.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. Theoretical contributions. Fills important theoretical gaps in understanding SMOTE and its variants and provides mathematical foundation for widely-used oversampling techniques.\n2. Extends classical non-parametric risk analysis to imbalanced settings.\n3. Comprehensive numerical experiments support theoretical findings.\n\n**Weaknesses:**\n1. Enhanced readability. For readers with limited mathematical background, the paper can improve: more intuitive explanations of key concepts, intuitive interpretations of theorems, and visualizations of the theoretical relationships.\n2. Expanded experimental analysis. Evaluation on a broader range of datasets, especially extremely imbalanced cases and analysis of scalability with increasing dimensionality.\n4. Lack conclusion. The paper ends directly after the experimental part without conclusion.", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to thank the referee for his or her valuable comments and suggestions, which will help us to improve the quality and clarity of the manuscript. In what follows we provide answers to all of his or her comments suggesting the  changes that we would like to do in the next version of our paper.\n\n**1) Enhanced readability**\n\nThank you for the reviewer’s suggestion. In the revised version, we will include more intuitive explanations of the key concepts and main results, along with some illustrative examples.\n\n**2) Expanded experimental analysis**\n\nWe are happy to explore additional datasets with higher dimensions and to expand our experimental results.\n\n**3) Lack conclusion**\n\nWe will add a conclusion section and summarize the key contributions in the revised version.\n\n**Questions**\n\n**How does performance scale with increasing dimensionality?**\n\nIn our theoretical bounds, the variance term—which decreases at the rate of $\\frac{1}{\\sqrt{n_{1}}}$—is independent of the dimension, whereas the bias term slows with increasing dimension due to the presence of the factor $\\left( \\frac{k}{n_{1}} \\right)^{1/d}$. As $d $ increases, the bias decays more slowly and eventually dominates the variance. In practice, when the dimensionality is too high, one can apply PCA as a preprocessing step or use manifold-based SMOTE to mitigate the curse of dimensionality.\n\n**Limitations**\n\n**The author has established important theoretical results in the paper and should discuss how to guide the selection of hyperparameters in practical applications.**\n\nWe selected the optimal values for these hyperparameters, as shown in Figure 1, where the effects of varying $h$ and $k$ under Theorem 4 are delineated. Cross-validation was also employed to tune the classifier's hyperparameters, resulting in a significant performance improvement, as illustrated in Figure 2. We will investigate this further in the revised manuscript."}]

Author rebuttal:

Meta-review: (a) Summarize the scientific claims and findings of the paper based on your own reading and characterizations from the reviewers.
This paper develops a theoretical framework to analyze SMOTE and KDE-based synthetic oversampling methods for imbalanced binary classification. The authors establish exponential concentration inequalities that bound the gap between the empirical risk computed on synthetic minority samples and the true population risk. Furthermore, they demonstrate that a kernel-based classification rule trained on synthetic data generated via KDE oversampling can achieve the minimax rate of convergence. The paper claims these theoretical findings lead to practical guidelines for parameter tuning of both oversampling techniques and downstream learning algorithms, which are supported by numerical experiments.

(b) Strengths of the paper  
1.  Novel Theoretical Contributions: The paper provides some of the first non-asymptotic concentration and excess risk bounds for synthetic oversampling methods, representing a significant advancement in the theoretical understanding of these widely used techniques.
2.  Practical Relevance: The work successfully bridges theory and practice by deriving insights that inform parameter selection (e.g., justifying the common choice of k=5 in SMOTE, highlighting the need for bandwidth tuning in KDE) for imbalanced learning scenarios.
3.  Comprehensive Analysis: The framework systematically analyzes both SMOTE (nearest-neighbor-based) and KDE (kernel-based) oversampling, offering a unifying perspective on data-level approaches to class imbalance.
4.  Strong Rebuttal and Revisions: The authors were highly responsive to reviewer concerns. They addressed the major weakness by deriving a new uniform concentration inequality for SMOTE over a class of functions, which enables excess risk bounds and significantly expands the scope of their theoretical contributions.

(c) Weaknesses of the paper and what might be missing  
1.  Assumption Scrutiny: The strong assumptions required for the theoretical guarantees, particularly Assumption 1 (minimum probability mass within Euclidean balls), may limit the generalizability of the results to real-world high-dimensional data where such conditions are often violated.
2.  Theoretical Asymmetry: Despite the authors' improvements, the theoretical analysis remains more comprehensive for KDE-based oversampling than for SMOTE, creating an imbalance in the treatment of these two methods.
3.  Experimental-Theoretical Alignment: The experiments could be more directly tied to the theory, such as explicitly testing the theoretically derived optimal bandwidths against heuristic choices to demonstrate the practical value of the theoretical guidelines.
4.  Scope of Classifiers: The primary theoretical analysis focuses on kernel-based classifiers, while the experiments use KNN and other methods. Although the new uniform convergence bound helps generalize the theory, the initial focus might feel somewhat narrow.

(d) Most important reasons for the decision to accept  
The decision to accept is based on the paper's significant and novel theoretical contributions to an important and practical problem. The work provides foundational theoretical analysis for synthetic oversampling methods, offering the first minimax optimality results for learning from synthetically generated data. This represents a substantial advancement in the theoretical understanding of these widely used techniques.

The authors' strong rebuttal effectively addressed the most critical concerns raised during the review process. By deriving a new uniform concentration inequality for SMOTE, they substantially improved the paper's theoretical contributions and scope. Their commitments to revise the manuscript for improved clarity, add a conclusion section, and expand experimental analysis further strengthen the work.

The reviewer consensus is positive, with scores of 5 (Accept), 4 (Borderline Accept), 4 (Borderline Accept), and 4 (Borderline Accept) after the rebuttal. While the paper has limitations regarding its assumptions and scope, it makes a solid theoretical contribution that meets the standards for NeurIPS acceptance as a poster presentation.

(e) Summary of the discussion and changes during the rebuttal period  
The reviewers raised several key points:
1.  Concern regarding Assumption 1: One reviewer questioned the reasonableness of Assumption 1 for high-dimensional data, suggesting it contradicts the realities of the curse of dimensionality. The authors clarified that this is a standard assumption in non-parametric literature, is only used for the SMOTE theorem, and explicitly reflects the curse of dimensionality in the resulting bounds.
2.  Theoretical Asymmetry (Lack of SMOTE excess risk bound): Multiple reviewers noted the lack of an excess risk bound for SMOTE compared to the detailed analysis for KDE. The authors addressed this powerfully by deriving a new uniform concentration inequality for SMOTE over a class of functions, which enables excess risk bounds for classifiers trained on SMOTE-generated data.
3.  Choice of Classifier: Reviewers noted a disconnect between the kernel classifier used in the theory and the KNN classifier used in experiments. The authors explained their choice was for community familiarity and demonstrated that the theoretical insights still hold.
4.  Practical Impact: Reviewers questioned the practical utility of the tuning guidelines. The authors agreed to clarify their guidance, emphasizing that their theory justifies data-driven tuning that optimizes the bias-variance tradeoff.
5.  Clarity and Presentation: Reviewers requested improved readability, a conclusion section, and expanded experiments. The authors committed to all these changes.

The authors' rebuttal was highly effective in addressing the major concerns. They transformed the primary weakness (the lack of a SMOTE excess risk bound) into a strength by deriving a new theoretical result. Their defense of Assumption 1 was reasonable and grounded in existing literature. The clear majority positive consensus post-rebuttal supports acceptance. The paper makes a valuable theoretical contribution that will interest the NeurIPS community.
Decision: Accept (poster)