Certified Interpolation Oversampling: Per-Instance Safety Guarantees for Imbalanced Learning

arXiv:2501.15790 · cs.LG, stat.ML · Submitted 2026-08-06 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Certified Interpolation Oversampling: Per-Instance Safety Guarantees for Imbalanced Learning".

Jane: The paper was written by Pankaj Yadav and Vivek Vijay from Indian Institute of Technology Jodhpur.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the arXiv channel, everyone. I'm Tom, and as always, I've got Jane here with me. Jane, we've got a paper today that's got quite a mouthful of a title: "Certified Interpolation Oversampling: Per-Instance Safety Guarantees for Imbalanced Learning."

Jane: Tom, that title is dense, but it's actually hiding something really cool. Let me unpack it. "Imbalanced learning" is when you're trying to teach a computer to spot something rare — like fraud in a sea of normal transactions, or a disease in a pile of healthy scans. The rare thing is the minority class, and most algorithms just ignore it because it's so outnumbered.

Tom: Right, and "oversampling" is the classic fix. You don't just train on what you have — you generate fake examples of the rare thing to balance the scales. SMOTE is the old standby there, and this paper is building on that whole family of tricks.

Jane: Exactly. But here's the twist — the word "certified" in the title. That's what got me excited. This paper isn't just saying "we made better fake data." It's saying "we can prove that our fake data stays safely away from the majority class." Every single generated point comes with a mathematical guarantee, not just a hope.

Tom: And that's a huge deal, because in something like medical diagnosis, if you generate a fake patient that actually looks like a healthy person, you're polluting your training data. You're teaching the model to miss the disease. This paper says "no, we've got a receipt for every fake patient we make."

Jane: The authors are Pankaj Yadav and Vivek Vijay from IIT Jodhpur in India. And they've done something pretty rare — they've preregistered their entire experiment. That means they wrote down exactly what they were going to test before they ran it, so they couldn't cherry-pick results afterward.

Tom: That's the kind of scientific honesty that makes me trust a paper more. They're not just showing you their best numbers — they're showing you everything, including the stuff that didn't work out for them.

Jane: And there's plenty of that, which we'll get into. But the headline is this: they've built a three-phase system that generates synthetic minority data, and it comes with a per-instance guarantee that it won't land in majority territory. That's the "certified" part, and it's genuinely new.

Tom: So when we say "per-instance safety guarantee," we mean for each fake data point, you can point at it and say "this one is provably at least this far from any real majority point." That's a strong promise.

Jane: It is. And it's the kind of thing that matters when synthetic data gets used in regulated industries — healthcare, finance, anywhere auditors are going to ask hard questions about where your data came from.

Tom: Let's dig into how they actually built this thing, because the engineering is clever. Stay with us.

Summary: Tom: So Jane, we've got the title unpacked. Let's talk about what this paper actually does. The full title is "Certified Interpolation Oversampling: Per-Instance Safety Guarantees for Imbalanced Learning," and the core idea is a three-phase pipeline.

Jane: Right. And each phase handles one decision. Phase one is "where do we generate?" — which minority anchor point gets to seed a new synthetic sample. Phase two is "with whom do we interpolate?" — which neighbors does that anchor pair up with. And phase three is "how far along the segment do we place the new point?"

Tom: And the key insight, which I thought was really elegant, is that they prove where safety information can actually act. They have this lemma that says if you put anchor-level safety into the neighbor selection weights, it cancels out when you normalize. It just vanishes. So the safety score has to live in the anchor selection phase instead.

Jane: That's the kind of mathematical rigor you don't usually see in oversampling papers. They're not just tweaking weights and hoping — they're proving that their design choice is the only one that can work for that information.

Tom: And the results? They ran this across forty-five datasets, four classifiers, and eleven competing methods. That's a massive evaluation. And here's the honest part — they did not find that their method crushes SMOTE on predictive accuracy. They're statistically equivalent on the main metric.

Jane: Which sounds like a letdown, but it's actually the most interesting finding in the paper. Because they're saying "look, we're not promising better accuracy — we're promising a safety guarantee that no other method provides, and we get it for free, without hurting accuracy."

Tom: Right. And they even go further — they say no sophisticated oversampler, including theirs, consistently beats simple class weighting or random oversampling on threshold-free metrics. That's a big deal because it confirms what a lot of recent research has been circling around.

Jane: It's like they're saying "the predictive headroom for geometric refinement is basically exhausted." SMOTE already sits at the ceiling. So the only axis left to improve on is the geometry of what you generate — and whether that geometry comes with a proof.

Tom: And they have that proof. Every synthetic instance seeded by a "sufficiently safe" anchor is provably at least a computable distance from every majority point. That's Lemma five in the paper, and it's unconditional — it doesn't depend on which random draws happen later.

Jane: Plus they've got a single temperature parameter, alpha, that provably shifts synthesis between boundary-seeking and interior-seeking regimes. And it's monotone — crank it up, and the safety clearance rises. Crank it down, and you head toward the boundary.

Tom: So you've got one knob that controls the entire safety-fidelity trade-off. That's a beautiful thing for practitioners.

Jane: And the reliability story is wild. They ran over eleven thousand fold-level evaluations without a single failure. Meanwhile, KMeans-SMOTE — an established baseline — failed on half of the datasets, and its failure rate got worse as imbalance got more severe.

Tom: So the method that's supposed to handle imbalance just collapses when the imbalance gets bad. That's a real problem in the field, and this paper exposes it.

Jane: Exactly. So the summary is: certified safety, provable monotonicity, zero predictive cost, and rock-solid reliability. That's the package.

Tom: Now let's talk about what they actually improved over existing methods. That's the next segment.

Improvements: Tom: So Jane, we've covered what the paper does. Let's talk about what it improves over the existing toolkit. The full title again is "Certified Interpolation Oversampling: Per-Instance Safety Guarantees for Imbalanced Learning."

Jane: Right. And the biggest improvement is obvious — nobody else in the interpolation family provides a per-instance certified guarantee. You've got methods like ADASYN that weight toward hard examples, Borderline-SMOTE that filters to the boundary, Safe-Level-SMOTE that biases placement — but none of them can point at a generated point and say "this one is provably safe."

Tom: And that's not just a marketing difference. The paper actually proves that some existing methods can place synthetic points inside the majority region. GDO — Gaussian Distribution based Oversampling — can do that when its radius is set too wide. So the guarantee isn't just nice-to-have; it's closing a real failure mode.

Jane: The second improvement is the monotone control. They've got this alpha parameter that sweeps continuously from boundary-seeking to interior-seeking behavior. Existing methods each pick one philosophy and lock you into it. ADASYN is boundary-hungry. Safe-Level-SMOTE is interior-biased. But CISO gives you both ends of the spectrum with one knob.

Tom: And they prove it's monotone. Not just "we observed it trends upward" — they prove that as alpha increases, the expected certified clearance of generated instances is nondecreasing. That's a mathematical guarantee, and they verify it empirically too.

Jane: The third improvement is well-posedness. Every selection weight is strictly positive by construction. No degenerate cases. No fallback branches. That sounds dry, but it's why they completed all eleven thousand four hundred sixty fold-level evaluations without a single failure.

Tom: And that reliability is a genuine improvement over the field. KMeans-SMOTE failed on half the datasets. ADASYN failed on a few folds. The paper argues this isn't an implementation bug — it's structural. When the minority class gets too thin, cluster-based methods just can't find reliable clusters.

Jane: There's also a subtle theoretical improvement I want to highlight. They prove a lemma about where safety information can act in the pipeline. If you put anchor-level information into neighbor weights, it cancels under normalization. That's a "you can't do that" result — and it tells the whole field where their design space actually is.

Tom: So future method designers won't waste time putting safety scores in the wrong place. That's a contribution that outlives this specific method.

Jane: And the ablation study shows each component does something measurable. Removing any phase changes the geometry of synthesis significantly — the distances between synthetic and original minority points shift. But here's the kicker — none of those geometric changes translate into predictive gains.

Tom: Which loops back to what we said earlier — the predictive ceiling is already hit. So the improvements here are about safety, control, and reliability, not about squeezing out another fraction of a percent of AUC.

Jane: And that's a legitimate contribution. The paper is saying "we're not going to pretend we beat SMOTE on accuracy. We're offering something SMOTE structurally cannot provide — a proof."

Tom: Let's bring in our senior researcher Lu to push on this. Lu, what do you make of the theoretical framing?

Lu: Thanks Tom. I think the deepest move here is the "where can safety act" lemma. It's a no-go theorem for a whole class of designs. That's the kind of result that makes me take the paper seriously beyond its own method.

Jane: And it's rare in this subfield. Most oversampling papers are "we tried a new weighting scheme and got +zero point three percent." This one says "here's a structural constraint on the entire family."

Tom: Let's dig into the actual first page of the paper next — the abstract and the setup.

First Page: Tom: So Jane, let's actually read the opening of "Certified Interpolation Oversampling: Per-Instance Safety Guarantees for Imbalanced Learning." The abstract lays out the whole mission.

Jane: And the first sentence is key — it says synthetic minority oversampling is "typically designed and evaluated against a predictive objective." That's the status quo. Everyone optimizes for downstream classification accuracy. But this paper says "we're pursuing a second objective" — generating samples that carry a stated safety property.

Tom: And that property is "established for each instance by construction rather than assumed." That's the core philosophy. You don't audit after generation — you build the guarantee into the generator itself.

Jane: The abstract then lists three guarantees. First, every synthetic instance seeded by a sufficiently safe anchor carries a certified distance from the majority class. Second, a signed temperature parameter provably and monotonically shifts synthesis between boundary-seeking and interior-seeking regimes. Third, selection weights are strictly positive, so no degenerate case exists.

Tom: And then they say something that I think is really important — "Certification is obtained alongside competitive predictive performance rather than in place of it." They're not asking you to trade accuracy for safety. They're saying you get both.

Jane: And the numbers back that up. Across forty-five datasets, four classifiers, eleven competing methods — CISO is statistically equivalent to SMOTE on precision-recall AUC. It ranks second of eleven under gradient boosting. And it completed every one of eleven thousand four hundred sixty fold-level evaluations without failure.

Tom: That last number is staggering when you think about it. Eleven thousand four hundred sixty separate evaluations. Not one crash. Meanwhile, some established baselines failed on most datasets under the same protocol.

Jane: And there's a line in the abstract that I love — "A parameter sweep further reveals a continuous fidelity-safety trade-off that competing methods occupy only as isolated points." That's the money quote. Existing methods are dots on a graph. CISO is a line.

Tom: So the first page sets up the entire story — the dual objective, the three guarantees, the massive preregistered evaluation, and the honest reporting of what did and didn't work.

Jane: And the honesty is baked into the abstract itself. They say "We report every preregistered outcome in full, including those that did not favor our initial hypotheses." That's rare. That's real science.

Tom: Let me bring in Meng, our engineer, because I want to know — does this actually run in practice?

Meng: Thanks Tom. The numbers I care about are the runtime. On the small KEEL datasets, CISO is the most expensive sampler — forty-seven milliseconds per fold versus one point two for SMOTE. That's a thirty-nine times slowdown. But in absolute terms, forty-seven milliseconds is nothing compared to training a classifier.

Jane: And on the large datasets?

Meng: That's where the tree-based search kicks in. At twenty thousand samples and one hundred sixty-six dimensions, it's one point two three seconds. Near-linear scaling. The quadratic path never triggers. So for a one-time preprocessing step, this is totally operational.

Tom: So the cost is real but manageable. And you get the guarantee for that price.

Meng: Exactly. And the reliability is the engineering story. No failures across eleven thousand runs. That's the kind of thing that makes me trust it in production.

Jane: Let's bring in Lalam to give us the big-picture cultural impact.

Lalam: Thank you, Jane. When I consider the broader implications, I see this as a step toward trustworthy synthetic data. In regulated domains — healthcare, finance, public policy — the question is no longer "does this model work?" but "can we prove what this data does?" This paper provides a template for that proof.

Tom: So it's not just an algorithm. It's a template for how to build certified data generation.

Lalam: Precisely. And the preregistration is part of that cultural shift. The authors are modeling a standard of transparency that the field needs more of.

Jane: Let's wrap this up in the conclusion.

Conclusion: Tom: So Jane, we've spent this whole episode on "Certified Interpolation Oversampling: Per-Instance Safety Guarantees for Imbalanced Learning." Let's pull it together.

Jane: The core message is that you can build an oversampler that provides per-instance safety guarantees — mathematical proofs, not hopes — while staying statistically equivalent to SMOTE on predictive performance. That's the headline.

Tom: And they did it with a three-phase design: safety-guided anchor selection, locality-and-clearance-weighted neighbor selection, and q-Gaussian placement. Each phase does one job, and each job is backed by a lemma.

Jane: The three guarantees are the certified clearance distance, the monotone temperature control, and the well-posedness that eliminates degenerate cases. And they verified all three empirically across forty-five datasets and four classifiers.

Tom: The honest part is that they didn't beat SMOTE on accuracy. But they didn't need to. They're offering something SMOTE can't — a proof that each generated point stays clear of the majority class.

Jane: And they exposed a real problem in the field — KMeans-SMOTE failing on half the datasets, with failures worsening as imbalance grows. That's a reliability gap that this paper documents and its own method avoids.

Tom: The fidelity-safety trade-off is the lasting image for me. One parameter sweeps a continuous curve through that space, while every competing method sits at a single fixed point. That's a genuine contribution to how we think about oversampling design.

Jane: And the preregistration — writing down the protocol before running the experiment — sets a standard for the field. They reported every outcome, including the ones that didn't support their hypotheses.

Tom: So we say goodbye to this paper. It's not going to change the world by squeezing out another decimal of AUC. It's going to change the world by showing that synthetic data can come with receipts.

Jane: And that's the future we want — data you can trust, with proofs you can point to. Thanks for listening, everyone. We'll see you on the next paper.

Tom: Take care, folks.

Pankaj Yadav, Vivek Vijay

Indian Institute of Technology Jodhpur

cs.LG, stat.ML

Submitted: 2026-08-06

Updated: 2026-08-10

Comments: 39 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 72/100

The gist: generating samples with a stated, verifiable safety property ensuring a synthetic minority instance does not land inside the majority region, with the guarantee certified for each instance rather

Key concepts

Imbalanced Learning
This occurs when training a computer on data where one class (the minority) is much rarer than the other. Algorithms often ignore this rare class because it is outnumbered, making it difficult to train models to spot things like fraud or diseases.
Oversampling
A technique used to address imbalanced learning. It involves generating synthetic examples of the rare or minority class data points, balancing the dataset so that the model can learn from both common and rare occurrences.
Certified Safety Guarantee
This is a mathematical proof provided by a new oversampling method. For every single generated data point, there is a guarantee that it stays safely away from any real majority class data points, ensuring the synthetic data does not pollute the training set.
Per-Instance Safety Guarantee
A strong promise where for each individual fake data point created, one can prove its distance from any actual majority point. This is a significant improvement over methods that simply claim safety.

Terminology

Summary

Summary

The paper introduces Certified Interpolation Safe Oversampling (CISO), a three-phase interpolation framework for imbalanced learning that generates synthetic minority instances carrying a per-instance certified safety property established by construction rather than assumed. The framework pursues a second objective beyond predictive performance: generating samples with a stated, verifiable safety property ensuring a synthetic minority instance does not land inside the majority region, with the guarantee certified for each instance rather than assumed, while remaining competitive on the predictive goal rather than trading it away.

The framework proceeds through three distinct phases, each governing a single decision and incorporating a precise piece of geometric information. First, a safety-guided anchor-selection distribution determines where synthesis occurs. Next, a locality- and clearance-weighted neighbor distribution decides with whom each anchor interpolates. Finally, a stochastic interpolation step, driven by a q-Gaussian placement density, determines how far along the resulting segment each synthetic instance is placed.

The framework provides three guarantees. Every synthetic instance seeded by an anchor with positive certified clearance provably lies at least a computable distance from every majority instance. A single signed temperature parameter provably and monotonically shifts synthesis between boundary-seeking and interior-seeking regimes. Furthermore, because selection weights are strictly positive by construction, no degenerate case exists.

The anchor safety score is defined as s i = i (1 - rho Reg(i)) in [0,1], where i is the min–max normalized clearance (distance to nearest majority instance) and rho Reg(i) is the regional majority density. The anchor-selection distribution is P alpha(i) =(epsilon 0 + s i) alpha over sum r=1 N 1 (epsilon 0 + s r) alpha, with epsilon 0 > 0 and alpha in R. The parameter alpha is a signed temperature: alpha > 0 concentrates synthesis on safe, interior anchors, while alpha < 0 concentrates it near the boundary. Neighbor weighting combines candidate clearance and locality through a q-Gaussian kernel, with weights w ij = (epsilon 0 + (n ij)) G q(ij). Interpolation draws a coefficient from a truncated q-Gaussian density centered at an anchor-guided ratio, producing x syn = (1-lambda) n i,a + lambda n i,b.

The certified clearance guarantee is formalized in Lemma 5: every synthetic instance seeded by anchor x i satisfies (x syn, x maj) at least c i - r i =: gamma i for all majority instances, where c i is the anchor's clearance and r i is its neighborhood radius. The certificate gamma i is computable at fit time before any classifier is trained. Proposition 1 establishes that the expected certified clearance is nondecreasing in alpha, providing a provably monotone control parameter.

The evaluation follows a protocol preregistered before execution, spanning 45 datasets (37 KEEL benchmark datasets plus 8 larger UCI datasets), four classifiers (logistic regression, RBF-kernel SVM, random forest, histogram-based gradient boosting), and eleven competing methods. The primary metric is precision-recall AUC (PR-AUC), with ROC-AUC and G-mean as secondary metrics.

Results show CISO is statistically equivalent to SMOTE on PR-AUC across all four classifiers, with Holm-corrected p-values of 1.000 (LR), 0.866 (SVC), 0.416 (RF), and 1.000 (HGB). CISO ranks second of eleven methods under gradient boosting (mean rank 5.11) behind random oversampling (5.05). CISO significantly outperforms Safe-Level-SMOTE across three classifiers (p = 0.006 for LR, 0.001 for SVC, 0.009 for HGB) and SMOTE-ENN under RF (p = 0.002). No sampling method in the comparison consistently outperforms class weighting or random oversampling on the primary threshold-free metric, extending conclusions from recent literature.

Component ablation shows no individual phase is detectable in predictive performance, with median per-dataset PR-AUC differences below 0.0016 in magnitude. However, every component is statistically significant on the geometric novelty diagnostic, with Holm-corrected p-values from 0.007 down to below 10-7, demonstrating that components govern placement and safety rather than predictive performance.

The certificate-as-predictor hypothesis (Q3) is not supported: no Spearman correlation between certified fraction and PR-AUC advantage over SMOTE reaches significance on any classifier, with the largest being rho = +0.249 under SVC at p = 0.137, and all four correlations are weakly positive rather than negative.

Distributional fidelity analysis shows CISO's held-out MMD2 is significantly higher than ROS and SMOTE (p = 2.3 times 10-10 and 1.8 times 10-10), and statistically indistinguishable from ADASYN (p = 0.091) and Borderline-SMOTE (p = 0.704). The parameter sweep reveals a continuous fidelity-safety trade-off: clearance rises monotonically with alpha from 1.675 at alpha = -1 to 2.446 at alpha = +2, while held-out MMD2 is U-shaped with minimum exactly at alpha = 0 (0.0296), rising to 0.0391 at alpha = -1 and 0.0971 at alpha = +2. Competing methods occupy only isolated points in this fidelity-safety plane.

On the scale suite of eight larger UCI datasets (up to N = 20,000 and d = 166), the predictive performance pattern replicates, with CISO's median per-dataset PR-AUC difference against SMOTE within ±0.0016 and no significant comparisons. Computational cost scales near-linearly with tree-based neighbor queries, reaching 1.23 seconds at N = 20,000, though CISO is 39× slower than SMOTE at the median on the evaluation suite (47 ms versus 1.2 ms per fold).

Reliability analysis shows CISO completed all 11,460 fold-level evaluations without a single failure, while KMeans-SMOTE failed on 50.3% of folds spanning 23 datasets, with failure rate correlating strongly with imbalance ratio (rho = +0.61, p = 0.0001), reaching complete failure on all five datasets with IR exceeding 25. ADASYN failed on 0.9% of folds across two datasets.

The paper concludes that certification is obtained alongside competitive predictive performance rather than in place of it, and that the fidelity-safety trade-off is a continuous choice rather than a static algorithm design feature, with the temperature parameter traversing this spectrum continuously where competing methods occupy only fixed points.

Improvements for AI systems

Based on the paper, here are specific improvements I can implement in AI systems:

Implementation: Add a certification layer to any oversampling or synthetic data generation pipeline that computes, for each generated instance, a provable minimum distance to the majority class before generation occurs.

What the improved system can do:

  • Guarantee that every synthetic minority instance seeded by a certified anchor (where clearance > neighborhood radius) lies at least a computable distance γi from every majority instance

  • Report the certified fraction (proportion of minority anchors with positive certificates) as a fit-time diagnostic before any classifier training

  • Fail gracefully with a clear warning when certification is vacuous (γi ≤ 0) rather than silently producing unsafe instances

Implementation: Replace fixed oversampling strategies with a single signed temperature parameter α that provably and monotonically shifts synthesis between boundary-seeking (α 0) regimes, using the anchor selection distribution Pα(i) ∝ (ε0 + si) α.

Implementation: Enforce strict positivity in all selection weights and placement densities, using the q-Gaussian kernel with q > 1 and a positive floor ε0 in every weight computation.

Implementation: Structure synthesis as: (Phase I) safety-guided anchor selection, (Phase II) locality-and-clearance-weighted neighbor selection, (Phase III) q-Gaussian placement along the interpolation segment.

Implementation: Compute a majority density field via k-NN mean distances, and place all safety information at the anchor-selection stage rather than neighbor-weighting stage (where Lemma 1 shows it cancels identically).

Implementation: Adopt the preregistered evaluation framework: disjoint tuning/evaluation suites, Holm-corrected statistical tests, explicit failure logging, and reporting of all outcomes including null results.


For regulated domains (healthcare, finance):

  • Generate synthetic minority instances with documented, per-instance distance guarantees from the majority class

  • Provide audit-ready certification metadata alongside each synthetic instance

  • Maintain predictive parity with SMOTE while offering provable safety properties

For practitioners with varying imbalance severity:

  • Deploy a single method that works across imbalance ratios from 1.8 to 129 without failure

  • Scale to datasets with N = 20,000 and d = 166 with near-linear time complexity (1.23 seconds at maximum tested scale)

For researchers studying oversampling:

  • Use the fidelity-safety plane (Figure 4) to locate any oversampling method as a point, and CISO's α-sweep as a continuous curve, enabling principled comparisons

  • Understand that geometric refinement has limited predictive headroom beyond SMOTE; the meaningful axis of differentiation is certified geometry, not accuracy

Sources

Related papers