Research map / Learning theory and algorithms / Kernels and regression theory
Concentration and excess risk bounds for imbalanced classification with synthetic oversampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical analysis of SMOTE and KDE-based oversampling (KDEO): uniform concentration bounds for synthetic minority risk and excess AM-risk bounds for ERM and kernel smoothing classifiers trained on oversampled data, with simulations and real-data experiments.
Problem
Imbalanced binary classification with synthetic oversampling (SMOTE, KDEO) lacks theoretical foundations; it is unclear how oversampling affects risk and how to tune k or bandwidth h.
Approach
Treat oversampling as generating samples from a reweighted (balanced) distribution, derive uniform concentration bounds for empirical risk on synthetic minority data (via Rademacher complexity and Talagrand/Bousquet-type inequalities, nearest-neighbor distance bounds for SMOTE, and L1 KDE bounds for KDEO), and derive excess AM-risk bounds, including a nonparametric kernel smoothing plug-in classif
Key results
- Derived uniform concentration bound for SMOTE of order n_1^{-1/2} + (k/n_1)^{1/d} and for KDEO of order n_1^{-1/2} + h.
- Kernel smoothing classifier with KDEO has excess AM-risk bound with variance term (n_1 h^d)^{-1/2} and bias h or h^2; optimal h differs from SMOTE default k=5.
- Simulations: optimal SMOTE k in 45-60 for KNN rather than default k=5; KDEO with Scott's rule outperforms SMOTE and BBC across imbalance levels; LR is insensitive to oversampling parameters.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KDE-based oversampling (KDEO) instead of SMOTE | KNN and kernel smoothing classifiers · Simulated Examples 2 and 3 across imbalance levels | AM-risk | Helped |
| Use kernel smoothing with KDEO instead of KNN with SMOTE | KDEO and SMOTE classifiers · Simulated Examples 2 and 3 across imbalance levels | AM-risk | Helped |
| Select K by cross-validation instead of setting K=√n (ablation) | KNN with KDEO or SMOTE · Simulated Examples 2 and 3 | AM-risk | Helped |
| Select K by cross-validation (ablation) | KNN with KDEO-CV · Simulated Examples 2 and 3, including lower minority probabilities | AM-risk | Helped |
| Select K by cross-validation instead of setting K=√n (ablation) | KNN with balanced Bayes classifier (BBC) · Simulated Examples 2 and 3 | AM-risk | Hurt |
| Choose K by cross-validation instead of K=√n (ablation) | KNN · Abalone, California, MagicTel, Phoneme, and House_16H | AM-risk | Helped |
| Use SMOTE instead of KDEO | KNN · Abalone | AM-risk | Helped |
| Use KDEO instead of SMOTE | KNN · California, MagicTel, Phoneme, and House_16H | AM-risk | No clear effect |
| Vary SMOTE neighbor count k from the default k=5 (ablation) | KNN with SMOTE · Simulated Examples 2 and 3 | AM-risk | Mixed |
| Vary KDEO bandwidth H around Scott's-rule bandwidth H1 (ablation) | KNN and kernel smoothing with KDEO · Simulated Examples 2 and 3 | AM-risk | No clear effect |
| Vary SMOTE k or KDEO bandwidth H (ablation) | Logistic regression with oversampling · Simulated Examples 2 and 3 | AM-risk | No clear effect |
Surprising findings
- The default SMOTE choice k=5 corresponds to a bandwidth that does not guarantee consistency under the derived bound, and empirically optimal k was around 45-60.
- Logistic regression performance is largely insensitive to the choice of oversampling parameters k or H, unlike nonparametric classifiers.
Limitations
- Theory for SMOTE excess risk is not given for the kernel plug-in classifier; the KDEO excess-risk result is only for KDE-based sampling and might not extend to SMOTE.
- Consistency requires the minority sample size to be large relative to 1/p_1; the bounds do not vanish when n_1 p_1 is too small.
- Analysis of the KNN plug-in rule and fast rates under noise conditions are left open.
Experimental setup
Datasets: Abalone California MagicTel Phoneme House_16H simulated examples 1-4
Benchmarks: simulated examples 1-4 Abalone California MagicTel Phoneme House_16H
Metrics: AM-risk (balanced risk)
Baselines: SMOTE KDEO balanced Bayes classifier SMOTE-CV KDEO-CV logistic regression
Builds on: SMOTE KDEO Rademacher complexity kernel smoothing plug-in classifier
Closest papers by meaning
- Restoring balance: principled under/oversampling of data for optimal classification (ICML 2024 · similarity 0.88)
- Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data (ICML 2025 · similarity 0.87)
- Learning under Localized Minority Imbalance (NeurIPS 2026 · similarity 0.87)
- Synthetic Tabular Data Generation for Imbalanced Classification: The Surprising Effectiveness of an Overlap Class (AAAI 2025 · similarity 0.85)
- Balanced Data, Imbalanced Spectra: Unveiling Class Disparities with Spectral Imbalance (ICML 2024 · similarity 0.85)
- Learning Imbalanced Data with Beneficial Label Noise (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.