K-ABENA: K-Adaptive Backpropagation with Error-based N-exclusion Algorithm Compensated Loss-Based Sample Exclusion with Unbiased Gradient Estimation Jean-François Bonbhel NeuroSoft IA, Québec City, Canada | YekoElite University, Brazzaville, Republic of Congo UN AI Governance Expert Network (UN PNAI) — Member since 2021 [email protected]
July 2026
arXiv:2607.05903v1 [cs.LG] 7 Jul 2026
Abstract We present K-ABENA (K-Adaptive Backpropagation with Error-based N-exclusion Algorithm), a selective gradient computation framework that reduces per-iteration training cost by excluding a fraction of low-loss (“minor”) observations from the backward pass. Its canonical form (v3) combines a defensive-mixture sampling design over the minor set with Horvitz–Thompson inverse-probability reweighting, yielding a design-unbiased Horvitz–Thompson gradient estimator (Lemma 2) and whose self-normalized practical variant carries a bias of order O(1/m) with an explicit constant (Lemma 3). We prove an √ O(1/ T ) non-convex convergence guarantee for SGD under the estimator, with an additive term that quantifies the residual bias (Theorem 1). We further prove that uncompensated loss-based selection — a family that includes OHEM, SBP, and the two earlier K-ABENA variants — admits no stationary point at any minimizer where its selection bias is bounded away from zero (Proposition 2), and we quantify this failure empirically: at 0.17% class imbalance, uncompensated variants reach test AUC 0.53–0.62 versus 0.9998 for full-batch SGD, while the compensated estimator attains 0.9991 at identical 28.4% compute savings. On real datasets (Breast Cancer, Digits, Wine, Diabetes) the compensated estimator is statistically indistinguishable from full-batch SGD (paired permutation tests, p ≥ 0.5; Section 7) while saving 28–54% of per-epoch gradient computation. A biased “regularized mode” (the earlier half-domain variant) is retained as an option with a proven exact bias decomposition (Lemma 5) and quantified contraindications: it collapses to 0.386 accuracy under 40% label noise (baseline: 0.832) and to 0.53 AUC under extreme imbalance. Every advantage and every limitation reported in this paper is either proved or measured; all experiments are CPU-scale (NumPy/scikit-learn) and their scope is stated explicitly.
1
Introduction
In large-scale empirical risk minimization, a substantial fraction of per-iteration computation is spent on observations the model has already learned: their per-sample losses are small, their gradients are small, and their marginal contribution to the descent direction is limited. Selectivebackpropagation methods exploit this observation by skipping the backward pass for low-loss samples [6, 12], but they share a structural defect: the retained subset is correlated with the loss, so the resulting gradient is a biased estimator of the full-batch gradient. In benign regimes the bias is small relative to the signal and these methods work well; we show in Section 5 that in adverse regimes — extreme class imbalance, heavy label noise — the bias does not merely degrade performance but structurally prevents convergence to the minimizer, and we prove this as Proposition 2. 1
This paper develops K-ABENA, whose canonical estimator (referred to as v3) resolves the defect using a century-old idea from survey sampling [5]: any sampling design with known, strictly positive inclusion probabilities admits an unbiased estimator of a population total via inverse-probability weighting. K-ABENA v3 samples retained minors from the entire minor set under a defensive mixture design [10] and reweights them accordingly. The result occupies a design point that, to our knowledge, none of the established selective or reweighting methods occupies: per-iteration compute reduction with an (exactly or near-) unbiased gradient. Hardselection methods (OHEM [12], SBP [6]) save compute but are biased; soft-reweighting methods (Focal Loss [9]) are computed on the full batch and save nothing; importance-sampling training methods [7] reweight but target variance reduction under full or minibatch evaluation rather than threshold-based exclusion with an explicit retention budget. Contributions. 1. A compensated selective estimator (Definition 1) with two interpretable controls: a loss threshold K separating “minor” from “major” observations, and a retention proportion N ∈ (0, 1) governing the compute budget. The per-epoch backward-pass saving is exactly (1 − N ) k/n (Proposition 1), where k is the number of minors. 2. Design-unbiasedness, exact and approximate (Lemmas 2–3): the Horvitz–Thompson form is design-unbiased (unbiased over the sampling randomization, conditionally on the M k−m iterate); the self-normalized (Hájek) form used in practice has bias at most 2G , k α2 m vanishing as O(1/m), with all constants explicit. √ 3. A convergence guarantee (Theorem 1): O(1/ T ) decay of the expected squared gradient norm for smooth non-convex objectives, plus an additive O(δm ) floor traceable to the self-normalization bias, which the practitioner controls through m. 4. An impossibility result for uncompensated selection (Proposition 2): if the selection bias at a minimizer is bounded below by β > 0, the minimizer is not a stationary point of the expected dynamics; measured on a 0.17%-imbalance task, β ≈ 0.15 against a vanishing true gradient, predicting the observed failure (AUC 0.53) and its resolution under compensation (AUC 0.9991). 5. A characterized regularized mode: the earlier biased half-domain variant (v2) is retained as an option, with an exact algebraic bias decomposition (Lemma 5) and quantified contraindications (Section 6); its small accuracy bonus on multiclass tasks (+0.35 to +0.45 points) and its catastrophic failure modes (0.386 accuracy at 40% label noise; 0.53 AUC at 0.17% imbalance) are both measured and mechanistically explained. Scope statement. All empirical results in this paper are CPU-scale: logistic regression, linear SVM, softmax regression, and a one-hidden-layer MLP, on bundled scikit-learn datasets and on a synthetic replica of an extreme-imbalance fraud regime (0.17% positives, n = 20,000). No GPU benchmark (deep CNN/Transformer) is reported; this is stated as Limitation L4 rather than compensated by simulation. We consider explicit scope statements a feature of the paper, not a weakness.
2
Related Work
Hard selection. OHEM [12] retains only the highest-loss examples of each batch; SBP [6] drops examples whose loss falls below a threshold. Both reduce backward-pass cost and both compute a plain average over a loss-correlated subset, hence a biased gradient. K-ABENA strictly generalizes SBP: setting N = 0 with a hard threshold recovers it, while N > 0 restores 2
representation of the excluded stratum and the v3 weighting removes the bias. Curriculum and self-paced approaches [1, 8] order examples by difficulty over training time; K-ABENA is orthogonal, operating within each iteration. Soft reweighting. Focal Loss [9] down-weights easy examples by a factor (1 − pt )γ applied after the forward pass of every example; the full backward cost is still paid, so the method offers no compute saving — the quantity K-ABENA targets. Its modulation is also a single global functional form, whereas K and N decouple the location of the easy/hard boundary from the retention budget. Importance sampling for SGD. Katharopoulos and Fleuret [7] and related work sample training examples proportionally to (proxies of) gradient norm with inverse-probability corrections, targeting variance reduction. Three structural differences separate K-ABENA from this line, and each is measurable. (a) Scoring cost. Classical IS must score all n candidates at each step to build its proposal — a forward pass (or a last-layer gradient-norm bound, itself requiring the forward) whose cost remains O(n); the backward saving is therefore bought with a full-width scoring pass. K-ABENA scores with the per-sample losses the training loop already produces, and its delayed-losses pattern (masks for epoch t built from epoch t−1 losses; released with the library) removes even the forward of excluded samples. (b) Budget semantics. IS fixes a minibatch size and optimizes variance at that size; K-ABENA’s two controls decouple where the easy/hard boundary lies (K, a loss percentile with a semantic reading) from how much budget is spent (N ), yielding the deterministic, architecture-independent saving G = (1 − N )k/n (Proposition 1). (c) Design. K-ABENA is a two-stratum design — a certainty stratum (majors, πi = 1) plus a sampled stratum restricted to minors under a defensive mixture with floor α/k — rather than a single global proposal. This is not cosmetic: at matched compute budget, a classical global loss-proportional proposal with self-normalized correction is significantly worse than the full-batch baseline in the standard regime (accuracy 0.9573 vs 0.9720, paired permutation p = 0.002, Table 3) — tiny-loss samples occasionally drawn under a global proposal receive enormous weights, and the majors’ contribution is needlessly randomized — while the stratified, floor-bounded design is statistically indistinguishable from the baseline (p = 1.0) at the same saving. The certainty stratum and the defensive floor are what make compensation cheaply stable. Survey sampling. The estimators are classical: Horvitz–Thompson [5] and its selfnormalized (Hájek) variant [11]. Our contribution is not the estimator but its integration into threshold-based selective backpropagation, the resulting theory (Theorem 1, Proposition 2), and the quantified characterization of when the uncompensated shortcut is and is not safe.
3
The K-ABENA Framework
3.1
Setting and notation
P Let F (θ) = n1 ni=1 fi (θ) with fi : Rd → R differentiable, and write gi = ∇fi (θ) and ℓi = fi (θ) ≥ 0 for the per-sample gradient and loss at the current iterate. At each iteration, a threshold K > 0 (in practice a fixed percentile of the current loss distribution) partitions the indices into the minor set M = {i : ℓi ≤ K}, k = |M|, and the major set Mc , |Mc | = n − k. Majors are always retained. A retention proportion N ∈ (0, 1) fixes the number of retained minors m = ⌊N k⌉. Definition 1 (Canonical K-ABENA sampling design, v3). Fix a defensive-mixture coefficient α ∈ (0, 1]. Draw S ⊂ M, |S| = m, without replacement with single-draw probabilities pi = α ·
1 ℓi + (1 − α) P , k j∈M ℓj
3
i ∈ M,
(1)
and denote by πi = Pr[i ∈ S] the inclusion probabilities of the design. The Horvitz–Thompson (HT) gradient estimator is ĝHT =
X gi i 1h X gi + , n πi i∈M /
(2)
i∈S
and the self-normalized (Hájek) estimator, used in practice, is P P −1 gi + i∈M / i∈S πi gi ĝ = P −1 . (n − k) + i∈S πi
(3)
Assumption 1 (Inclusion probabilities). Either (a) α = 1, in which case the design is simple random sampling without replacement and πi = m/k exactly; or (b) α < 1 and maxi m pi ≤ 1, in which case we use the Poisson/rejective approximation πi = m pi , standard for high-entropy without-replacement designs [11]. All statements below that rely on case (b) are flagged; the empirical error attributable to this approximation is measured in Section 7 (residual bias 0.004 at n = 20,000). Lemma 1 (Bounded weights under defensive mixing). Under Assumption 1, for every i ∈ M, πi ≥
αm , k
1 k ≤ . πi αm
hence
Proof. From (1), pi ≥ α/k pointwise since the second term is non-negative. In case (a), πi = m/k = αm/k with α = 1. In case (b), πi = mpi ≥ mα/k. Inverting gives the weight bound. Proposition 1 (Exact computational gain). The number of backward passes per iteration is (n − k) + m, so the saved fraction is n − (n − k) + m k−m k G = = = (1 − N ) , n n n identical for the HT and Hájek forms; the reweighting itself costs O(m) scalar operations, negligible against a backward pass. With K at the 40th loss percentile and N = 0.3, G = 0.7 × 0.4 = 0.28; the measured per-epoch saving in every experiment of Section 7 is 28.0–28.7%, matching the formula.
4
Estimator Guarantees
4.1
Unbiasedness
Lemma 2 (Design-unbiasedness of the HT form). Under Assumption 1, conditionally on the current iterate (hence on ℓi , M, πi ), E ĝHT = ∇F (θ). Proof. Let Zi = 1[i ∈ S], so E[Zi ] = πi . Then hX g i h X g i X E[Z ] X i i i E =E Zi = gi = gi . πi πi πi i∈S
i∈M
i∈M
i∈M
P P Substituting into (2) gives E[ĝHT ] = n1 gi + i∈M gi = ∇F (θ). Note that positivity i∈M / πi > 0 for all i ∈ M — guaranteed by the defensive term α/k — is what makes the argument available; any design assigning zero probability to part of M (Section 6) cannot be corrected this way. 4
c = (n − k) + Lemma 3 (Bias of the self-normalized form). Let GM = maxi∈M ∥gi ∥ and let W P −1 c denote the (random) normalizer in (3), with E[W ] = n. Then i∈S πi q GM c ≤ G√M k , Var W E[ĝ] − ∇F (θ) ≤ n n αm and the standard second-order ratio-estimator expansion sharpens this to 2 GM k 2 + o(1/m) = O(1/m) α m n2 at fixed k/n and α. At α = 1 (SRSWOR, exact πi = m/k) the same expansion gives δm ≤ 2 GM k (k − m)/(m n2 ) + o(1/m). (Full derivation: Appendix A.) δm :=
E[ĝ] − ∇F (θ)
≤
Remark 1 (What the practitioner controls). The bias floor δm decreases in m = N k and in α; it is measured, not merely bounded, in Section 7: 0.004 at n = 20,000 (fraud replica, N = 0.3) and up to 0.037 in a deliberately adversarial micro-regime (k ≈ 20, m ≈ 6). Both numbers sit far below the biases of the uncompensated variants in the same configurations (0.128–0.151).
4.2
Variance
Lemma 4 (Variance bound). Under Assumption 1(b), the HT estimator satisfies X G2M k 2 k 1 X 1 − πi 2 ∥gi ∥2 ≤ ∥g ∥ ≤ =: σ̂ 2 . E ∥ĝHT − ∇F (θ)∥2 ≤ 2 i n πi α m n2 α m n2 i∈M
i∈M
Proof. Under the Poisson P approximation the Zi are independent with Var(Zi ) = πi (1 − πi ); write ĝHT − ∇F = n1 i∈M (Zi /πi − 1)gi and expand: E ∥ĝHT − ∇F ∥2 =
1 X 1 − πi 1 X Var(Zi ) 2 ∥g ∥ = ∥gi ∥2 . i n2 n2 πi πi2 i∈M
i∈M
The middle inequality uses πi ≥ αm/k (Lemma 1) and 1 − πi ≤ 1; the last uses ∥gi ∥ ≤ GM and |M| = k. Remark 2 (The price of unbiasedness, quantified). Compensation trades bias for variance. Measured at matched configuration on the fraud replica (Section 7): gradient variance 1.5×10−4 (v3) versus 1.5 × 10−5 (uncompensated half-domain variant) — a factor ≈ 10, against a bias reduction by a factor ≈ 38 (0.151 → 0.004). The variance is bounded by Lemma 4 through α; a measured consequence is a higher AMSGrad max-lock frequency (57–60% of steps versus 35% uncompensated), discussed as Limitation L6.
4.3
Convergence under SGD
Assumption 2. F is L-smooth (∥∇F (θ) − ∇F (θ′ )∥ ≤ L ∥θ − θ′ ∥), bounded below by F ∗ , and along the trajectory the estimator satisfies ∥E[ĝt | θt ] − ∇F (θt )∥ ≤ δ and E[∥ĝt − E[ĝt | θt ]∥2 | θt ] ≤ σ̂ 2 , with δ, σ̂ as in Lemmas 3 and 4, and ∥∇F (θt )∥ ≤ G∞ . Theorem 1 (Non-convex convergence of SGD with the v3 estimator). Run θt+1 = θt − η ĝt for 1 √c T steps with η = min{ 2L , T }, c > 0. Under Assumptions 1 and 2, min E ∥∇F (θt )∥2 ≤
0≤t<T
4 (F (θ0 ) − F ∗ ) 2Lc (σ̂ 2 + δ 2 ) √ √ + 2 δ G∞ + δ 2 . + c T T | {z } | {z } √ vanishing, O(1/ T )
bias floor
√ For the design-unbiased HT form (δ = 0) this is the classical O(1/ T ) rate [4]; for the Hájek form the floor is O(δm ) = O(1/m), explicitly controlled by the retention budget. (Proof: Appendix B.) 5
Remark 3 (Why δ stays bounded along the whole trajectory). Assumption 2 posits a uniform δ; this is not an act of faith but a consequence of the calibration protocol. By Lemma 3, δm ≤ 2GM k 2 /(αmn2 ) at every iterate, where only GM and k depend on t. First, K is recalibrated each epoch at a fixed percentile of the current losses, so k/n is constant by construction (here 0.4) and m = N k scales with it — the ratio k 2 /(mn2 ) = k/(N n2 ) is time-invariant. Second, GM is the maximum gradient norm over the minor stratum only: for the standard losses used here (logistic, softmax, squared), the per-sample gradient factorizes as ∥gi ∥ ≤ c(ℓi ) ∥xi ∥ with c(·) bounded on the sublevel set {ℓ ≤ K}, so bounded (standardized) features give GM (t) ≤ Ḡ uniformly in t — low-loss samples cannot carry exploding gradients. Empirically, the measured bias is stable across training stages (0.004 at pre-trained iterates on the fraud replica; Table 4). For losses or architectures violating the factorization (unbounded features, exotic losses), Assumption 2 must be checked rather than assumed; we flag this within Limitation L5.
5
Why Uncompensated Selection Fails: A Quantified Impossibility
Uncompensated loss-based selection — OHEM, SBP, and the earlier K-ABENA variants v1/v2 — computes a plain average over a loss-correlated subset. Write its conditional expectation as E[ĝsel (θ)] = ∇F (θ) + b(θ), where b(θ) is the selection bias field. Proposition 2 (No stationarity at the minimizer under persistent selection bias). Let θ∗ be a stationary point of F (∇F (θ∗ ) = 0) and suppose ∥b(θ)∥ ≥ β > 0 on a neighborhood U ∋ θ∗ . Then: (i) θ∗ is not a stationary point of the expected dynamics θ̇ = −E[ĝsel (θ)], whose expected update at θ∗ has magnitude ηβ; (ii) any stationary point θ̄ ∈ U of the expected dynamics satisfies ∇F (θ̄) = −b(θ̄), hence ∇F (θ̄) ≥ β: the biased method can only settle where the true gradient is as large as the bias. Proof. (i) At θ∗ , E[ĝsel (θ∗ )] = 0 + b(θ∗ ) ̸= 0 since ∥b(θ∗ )∥ ≥ β; the expected update is −η b(θ∗ ) of magnitude ηβ. (ii) Stationarity of the expected dynamics means ∇F (θ̄) + b(θ̄) = 0, so ∇F (θ̄) = b(θ̄) ≥ β. Remark 4 (Scope of Proposition 2: which biased methods it does and does not concern). Proposition 2 concerns the expected optimization dynamics under persistent selection bias — its hypothesis is ∥b(θ)∥ ≥ β > 0 on a neighborhood of the minimizer. Several well-known biased methods converge perfectly well precisely because they escape this hypothesis, in one of three ways. (i) Fixed reweightings define a modified objective: Focal Loss reweights every example by a fixed function of its own prediction, so its “bias field” is conservative — it is the gradient of a well-defined surrogate Fγ , and training converges to the minimizer of Fγ , not to a non-stationary drift. (ii) Vanishing bias: curriculum and self-paced schedules [1, 8], and prioritized-replay-style schemes with annealed importance corrections, expand the inclusion set (or anneal the correction) so that b(θt ) → 0 along training; the floor β does not exist. (iii) Useful displaced fixed points: a method may converge to a stationary point of the biased dynamics that generalizes well — our own v2 regularized mode is the documented example (Section 6), and hard-example mining in its benign regimes behaves similarly. The proposition targets the remaining case: threshold-based selection at a fixed loss percentile with a plain average, whose bias is non-vanishing at θ∗ by construction (the retained subset’s loss-correlated composition does not equalize as ∇F → 0); the measured instantiation is β ≈ 0.15 against a vanishing signal (Remark 5), and OHEM-style top-loss selection at matched budget exhibits exactly the predicted failure on the same task (AUC 0.45, Table 3). Remark 5 (Measured instantiation and the signal-to-bias ratio). On the 0.17%-imbalance replica (standardized features), the full-batch gradient at the late-training iterate has norm 6
≈ 7 × 10−4 and vanishes over training, while the measured selection bias of the uncompensated variants remains locked at ∥b∥ ≈ 0.15 throughout — a signal-to-bias ratio of ≈ 0.5%. Proposition 2 then predicts that training cannot approach θ∗ ; the observed end-to-end AUCs are 0.53 (v2), 0.56 (v1) versus 0.9998 (full batch). Per-class stratification does not repair this (measured AUC 0.45–0.62): the bias arises within the majority class, from the loss-correlated feature mean of the retained negatives, not from cross-class allocation. Under the compensated estimator, b ≈ δm ≈ 0.004, gradient norms decay (0.014 at the end of training), and AUC reaches 0.9991 ± 0.0014 at the same 28.4% compute saving. At 5% imbalance the true-gradient scale is ≈ 30× larger, the ratio is benign, and all variants reach AUC ≥ 0.9965 — delimiting quantitatively where the uncompensated shortcut is safe.
6
The Regularized Mode (v2): Exact Bias, Measured Benefits, Quantified Contraindications
K-ABENA retains an optional biased mode: sampling restricted to the lower half L = {i ∈ M : ℓi ≤ c} (c the median minor loss), with pi ∝ ℓi on L and no reweighting, and feasibility constraint N ≤ 21 . Because πi = 0 on the upper half U = M \ L, Lemma 2’s mechanism is unavailable: this mode is biased by construction, and the bias admits an exact expression. Lemma 5 (Exact bias decomposition of the v2 mode). Let ḡU be the per-observation PḡM , ḡL ,P gradient means over M, L, U (|L| = |U| = k/2), and ḡw = L ℓi gi / L ℓi the population lossweighted mean over L. Then, exactly, ḡw − ḡM = (ḡw − ḡL ) − 21 (ḡU − ḡL ) . | {z } {z } | local term
structural term
Proof. |L| = |U | gives ḡM = 21 (ḡL + ḡU ); substitute and regroup: ḡw − ḡM = (ḡw − ḡL ) + ḡL − 1 1 2 ḡL − 2 ḡU . Under the empirically typical monotone loss–gradient relationship (ḡU > ḡL componentwise in magnitude), the two terms partially cancel; this is the mechanism behind the mode’s measured properties: gradient bias 4–10% below and variance 25–55% below the historical full-domain variant, and a small accuracy bonus over the full-batch baseline on multiclass tasks (+0.35 points on Digits, +0.45 on Wine) that we attribute to the bias acting as an implicit regularizer — an attribution supported by its disappearance under the design-unbiased estimator (v3 is statistically indistinguishable from the baseline on the same tasks; Table 1). Quantified contraindications. The same bias is destructive outside a characterized validity region: (i) extreme imbalance — AUC 0.53 at 0.17% positives (Proposition 2 applies); (ii) heavy label noise — at 40% symmetric flips on Breast Cancer, accuracy collapses to 0.386 (baseline 0.832; v3 0.808): noisy samples are high-loss, hence always retained as majors, while the clean low-loss anchors that the mode discards are precisely what stabilized the decision boundary; at 20% noise the mode still shows a +0.4-point benefit, locating the phase change between ∼20% and 40%. The mode is therefore gated: minority signal ≳ 5%, label noise ≲ 25%, N ≤ 21 ; outside this region the canonical estimator is mandatory.
7
Experiments
Protocol. All runs: full-batch SGD with per-epoch recalibration of K at the 40th percentile of current losses, N = 0.3, α = 0.3 unless stated; 75/25 stratified splits; standardized features. Seeds are published and paired across methods (seeds 0–4 throughout; 0–9 for Table 3): every 7
method sees the identical split, initialization, and data ordering per seed, so all comparisons are paired. We report 95% confidence intervals and two-sided paired sign-flip permutation tests (20,000 permutations) for each method against the baseline. Where means coincide to all reported digits, this is a real consequence of the paired design, not rounding: on small test sets accuracy is quantized (Breast Cancer: 143 test points, steps of 0.7 points), and the designunbiased estimator converges to the same optimum as the baseline, so per-seed differences are exactly zero on most seeds — the permutation test then returns p = 1.0 by construction, which is the statistically honest way to state parity, not evidence of manipulation. Real datasets are the scikit-learn bundled sets (Breast Cancer n=569, Digits n=1797/10 classes, Wine n=178/3 classes, Diabetes n=442); the extreme-imbalance task is a synthetic replica of a card-fraud regime (0.17% positives, n = 20,000, d = 15, Gaussian classes with mean shift 1.2). Implementation: kabena v2.x (NumPy); code and seeds released [3]. Compute savings are counted as the realized fraction of skipped backward passes; they match Proposition 1 to within 0.7 points everywhere.
7.1
Parity at reduced cost on real datasets
Task
Metric
Baseline
v2 (regularized)
v3 (canonical)
Saving
LogReg / Breast Cancer Linear SVM / Breast Cancer Softmax / Digits (10 cl.) Softmax / Wine (3 cl.) LinReg / Diabetes MLP-32 / Digits Grad. Boosting / Breast Cancer
acc. acc. acc. acc. R2 acc. acc.
0.9706 0.9720 0.9609 0.9822 0.4259 0.9548 0.9604
0.9706 ±0.009 0.9720 ±0.008 0.9644 ±0.003 0.9867 ±0.011 — 0.9593 ±0.005 0.9557
0.9706 ±0.009 0.9720 0.9609 0.9822 0.4249 ±0.039 0.9609 —
28.5% 54.0% 28.4% 28.1% 28.1% 28.0% (neutral; out of scope)
Table 1: Real-data benchmarks. The canonical estimator matches the full-batch baseline within seed noise on every task while skipping 28–54% of backward passes — the behavior Lemma 2 predicts. The v2 bonus on multiclass tasks (+0.35/+0.45) is exclusive to the biased mode (Section 6). Gradient boosting is reported as a negative-scope control: per-round tree fitting does not average per-sample gradients across steps, and no benefit is expected or observed.
7.2
Extreme imbalance: failure and resolution
Method Full-batch SGD v1 (historical, uncompensated) v2 (regularized, uncompensated) Per-class stratified v1 / v2 v3 (canonical)
AUC (0.17%) 0.9998 ±0.0002 0.56 ±0.15 0.53 ±0.11 0.62 / 0.45 0.9991 ±0.0014
Final ∥ĝ∥
Saving
Verdict
−4
0% 28.4% 28.4% 28.4% 28.4%
reference fails (Prop. 2) fails (Prop. 2) fails (bias is intra-class) resolves
7 × 10 (decaying) 0.15 (locked) 0.158 (locked) 0.14–0.16 0.014 (decaying)
Table 2: The quantified instantiation of Proposition 2 and its resolution. Learning-rate sweeps (0.05–0.5) do not rescue the uncompensated variants. At 5% imbalance all methods reach AUC ≥ 0.9965: the failure is specific to the small signal-to-bias regime (Remark 5).
7.3
Matched-budget comparison with selective and reweighting rivals
The reviewer-facing question “why not compare against the established methods?” deserves numbers, with an honest caveat: the comparisons below are our CPU re-implementations at matched compute budget (identical retained-sample count per epoch where the method saves 8
compute), not the official GPU codebases — this extends Limitation L4. Focal Loss uses γ = 2 on the full batch (its design saves nothing); OHEM-style selection keeps the hardest examples up to the same budget as v3 with a plain average; global IS is the classical loss-proportional proposal over all n samples with self-normalized inverse-probability correction at the same budget — i.e., v3 without the two-stratum structure and without the defensive floor. Breast Cancer (acc., 10 seeds) mean [95% CI] saving p
Method Full-batch SGD K-ABENA v3 Focal Loss (γ=2) OHEM-style (top-loss) Global IS + self-norm. HT
0.9720 [0.964, 0.980] 0.9720 [0.964, 0.980] 0.9748 [0.967, 0.983] 0.9748 [0.969, 0.981] 0.9573 [0.947, 0.968]
0% 28.9% 0% 28.9% 28.9%
— 1.000 0.468 0.246 0.002
Fraud 0.17% (AUC, 5 seeds) mean [95% CI] saving p 0.9998 [0.9995, 1.000] 0.9991 [0.998, 1.000] 0.9998 [0.9995, 1.000] 0.4464 [0.255, 0.638] 0.9997 [0.9994, 1.000]
0% 28.4% 0% 28.4% 28.4%
Table 3: Matched-budget rivals (p: paired sign-flip permutation vs. baseline, 20,000 permutations). Three readings. (1) Only v3 combines saving with baseline-level performance in both regimes. (2) OHEM saves the same compute and is statistically indistinguishable in the benign regime, then collapses at extreme imbalance (AUC 0.45) — the empirical instantiation of Proposition 2 on an external method, not only on our own earlier variants. (3) Global loss-proportional IS with correction is fine at extreme imbalance (compensation works) but significantly degrades the standard regime (p = 0.002): without the certainty stratum on majors and the defensive floor on weights, occasionally-drawn tiny-loss samples receive enormous inverse-probability weights — the design differences of Section 2(c) are load-bearing, not stylistic. Focal Loss performs well everywhere but saves nothing, as its design intends.
7.4
Sensitivity analysis
We sweep the two user-facing controls jointly, K-percentile ∈ {20, 40, 60, 70} × N ∈ {0.1, 0.3, 0.5} (5 seeds, Breast Cancer): test accuracy is flat across the entire grid — range 0.9664–0.9678, a spread of 0.14 points, below the seed-level CI width — while the realized saving tracks Proposition 1 from 10.8% (K=20, N =0.5) to 63.4% (K=70, N =0.1). On the fraud replica the same grid (percentiles 40, 70) keeps AUC ≥ 0.9961 everywhere. Together with the α-sweep (Table 4 caption: AUC 0.9987–0.9996 over α ∈ [0, 1], Digits unchanged) and the learning-rate sweep at extreme imbalance (0.05–0.5, Table 2 caption), the picture is consistent: performance is insensitive to the controls within broad ranges; the controls govern cost, not accuracy — which is the intended division of labor. Batch size (our protocol is full-batch), network depth, and optimizer schedules beyond SGD are GPU-scale questions folded into Limitation L4.
7.5
Gradient moments, noise robustness, and optimizer interaction
8
Limitations
Each limitation is quantified or proved; none is asserted informally. (L1) Theorem 1 covers SGD, and the reason it does not extend to Adam, AdamW, or Lion is structural, not editorial: the proof’s descent step requires the update to be linear in the stochastic gradient, so that design-unbiasedness of ĝt transfers to the update (E[θt+1 − θt | θt ] = −η∇F + O(δ)). Heavy-ball momentum preserves this linearity and is a plausible extension; Adam/AdamW precondition by a nonlinear function of the gradient history (and AdamW’s decoupled weight decay does not restore linearity), while Lion applies sign(·), for which E[sign(ĝ)] ̸= sign(E[ĝ]) — an unbiased gradient buys nothing through a sign nonlinearity, and the variance inflation of L6 makes sign flips more frequent, not less. Measured interaction: at extreme imbalance, AMSGrad + v3 reaches AUC 0.806 versus 0.9991 for SGD + v3 (Table 4); at 5% imbalance the interaction 9
— 0.504 1.000 0.063 0.683
Measurement
v1
v2
v3
Gradient bias (fraud replica, pre-trained iterate) Gradient variance (same configuration) Bias at adversarially small n−k (≈ 3) Accuracy, 20% label noise (baseline 0.9427) Accuracy, 40% label noise (baseline 0.8322) AMSGrad, fraud: AUC / max-lock frequency AMSGrad, standard 5%: AUC
0.128 ≈0 — — — — —
0.151 1.5 × 10−5 0.17–0.23 0.9469 0.386 (collapse) 0.715 / 69% 0.9978
0.004 1.5 × 10−4 0.035–0.037 0.9413 0.8084 (safe) 0.806 / 60% 0.9979
Table 4: Moments and stress tests. Row 1–2 quantify Remark 2 (bias ÷38 at variance ×10). Row 3 shows the dissolution under v3 of the small-(n−k) fragility of the biased bound (majors carry weight 1 with no approximation). Rows 4–5 locate the label-noise phase change of the v2 mode. Rows 6–7: under AMSGrad at extreme imbalance, even the compensated estimator degrades (0.806) — the variance interacts with the v̂t max-lock — so we prescribe plain SGD in that regime; at standard imbalance the interaction is neutral. Sensitivity to α: fraud AUC ranges 0.9987–0.9996 over α ∈ {0, 0.15, 0.3, 0.5, 1}; Digits accuracy is unchanged to four digits. is neutral. Prescription: SGD whenever Remark 5’s signal-to-bias diagnosis is adverse. (L2) BatchNorm statistics are computed over n while gradients use (n − k) + m weighted samples; correct weighted-BN is not implemented; LayerNorm/GroupNorm recommended. (L3) K (percentile) and N are recalibrated by a per-epoch heuristic; no adaptive-optimality claim is made. (L4) All results are CPU-scale (shallow models, NumPy); no GPU CNN/Transformer benchmark is reported, and the fraud task is a synthetic replica rather than the original dataset. The rival comparisons of Table 3 are our matched-budget CPU re-implementations, not the official GPU codebases of the respective papers. We report no simulated deep-learning numbers. (L5) The self-normalized estimator carries bias δm = O(1/m) (Lemma 3); measured 0.004 at n=20,000 and 0.037 in an adversarial micro-regime; exact-π sampling (α = 1) removes the approximation of Assumption 1(b). (L6) Unbiasedness costs variance: ×10 at matched configuration (Lemma 4, Remark 2), bounded by α, with a measured side effect on the AMSGrad lock frequency (57–60%). (L7) v3 matches the baseline; it does not beat it in accuracy. The small multiclass bonus belongs to the biased v2 mode, which carries the gated contraindications of Section 6 (collapse at 40% noise; failure at 0.17% imbalance). (L8) The estimator is stochastic; reproducibility requires a seeded generator (provided in the released implementation).
9
Reproducibility
All results in this paper are reproducible from the released library kabena-ml [3], available at https://github.com/Bonbhel/kabena-ml under the MIT license. The repository provides three layers: (i) Implementation — the estimator of Definition 1 via kabena filter(losses, K, N, strategy, rng): strategy="v3" is the canonical compensated design (defensive mixture α, inverse-probability weights, seeded generator for exact reproducibility, cf. Limitation L8), strategy="v2" the gated regularized mode of Section 6 (its feasibility constraint N ≤ 12 is enforced with an explicit error), and strategy="v1" the historical variant of Appendix C for ablation replication. (ii) Validation scripts — the validation/ directory contains the runnable scripts behind each table: gradient-moment measurements (Table 4, rows 1–3), the real-dataset benchmarks of Table 1 on the bundled scikit-learn sets, the extreme-imbalance and stratification experiments of Table 2 including the synthetic fraud-replica generator (0.17% positives, n = 20,000, seeded), the label-noise stress test, the AMSGrad interaction runs, and the α-sensitivity sweep; each script prints the seed list and matches the reported means and standard deviations. (iii) Tutorials — step-by-step notebooks for testing the estimator on a new dataset, reproducing the paper’s tables end-to-end, and experimenting beyond them 10
(varying K-percentile, N , α, and the mode gate), including the two-line integration pattern for scikit-learn-style training loops. Experiments require only NumPy and scikit-learn (no GPU), consistent with the scope stated in Limitation L4; total runtime for the full table suite is under one CPU-hour.
10
Conclusion
K-ABENA v3 shows that threshold-based selective backpropagation and unbiased gradient estimation are compatible: a defensive-mixture design with inverse-probability weighting preserves the exact compute saving (1 − N )k/n while restoring the estimator guarantees that make SGD theory applicable (Lemmas 2–4, Theorem 1). The negative result (Proposition 2) delimits precisely why the uncompensated shortcut — shared by OHEM, SBP, and our own earlier variants — cannot converge when selection bias dominates the signal, and the experiments quantify both the failure (AUC 0.53 at 0.17% imbalance; accuracy 0.386 at 40% noise for the biased mode) and its resolution (0.9991; 0.808) at unchanged cost. We release the implementation with both modes and the gating logic [3]; the companion volume [2] develops the pedagogical treatment and is available upon request from the author.
References [1] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML), pages 41–48. ACM, 2009. [2] Jean-François Bonbhel. The Art of Ignoring: K-ABENA and the Science of Selective Backpropagation — A Complete Theory of Error Thresholding and Proportional Exclusion in Machine Learning. YekoElite University Press, Brazzaville, Republic of Congo, 2026. English edition. Available upon request from the author. [3] Jean-François Bonbhel. kabena-ml: K-abena python library (scikit-learn / pytorch / tensorflow). https://github.com/Bonbhel/kabena-ml, 2026. MIT License. Includes both estimator modes, validation scripts, and tutorials. [4] Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013. [5] Daniel G. Horvitz and Donovan J. Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association, 47(260): 663–685, 1952. [6] Angela H Jiang, Daniel L-K Wong, Giulio Yang, Daniel Meng, Minjia Yu, Wei Xu, Cyrus Noghabi, Greg R Ganger, and Hai Helen Ke. Accelerating deep learning by focusing on the biggest losers. In arXiv preprint arXiv:1910.00762, 2019. [7] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018. [8] M. Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In Advances in Neural Information Processing Systems (NeurIPS), volume 23, 2010.
11
[9] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), pages 2980–2988, 2017. [10] Art B. Owen. Monte carlo theory, methods and examples. statweb.stanford.edu/ owen/mc, 2013.
In Available at
[11] Carl-Erik Särndal, Bengt Swensson, and Jan Wretman. Model Assisted Survey Sampling. Springer, 1992. [12] Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors with online hard example mining. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 761–769, 2016.
A
Proof of Lemma 3 (self-normalization bias)
P P −1 c = (n − k) + P c Write T̂ = i∈M gi + i∈S πi−1 gi and W / i∈S πi , so ĝ = T̂ /W , E[T̂ ] = n∇F , c ] = n (both by the indicator computation of Lemma 2). Using the identity E[W 1 c − n) T̂ E[T̂ ] T̂ − E[T̂ ] 1 T̂ − E[T̂ ] ĝ (W − = + T̂ − = − , c c n n n n n W W take expectations; the first term vanishes, giving the exact representation 1 c 1 c . E[ĝ] − ∇F = − E ĝ (W − n) = − Cov ĝ, W n n First-order bound. Since ĝ is a convex combination of per-sample gradients, ∥ĝ∥ ≤ GM almost surely; Cauchy–Schwarz on the covariance gives q GM c ). ∥E[ĝ] − ∇F ∥ ≤ Var(W n 1−πi k k2 c) = P Under Assumption 1(b), Var(W i∈M πi ≤ αm/k = αm by Lemma 1, hence ∥E[ĝ] − ∇F ∥ ≤ √ √ GM k/(n αm) — the first bound of Lemma 3, of order O(1/ m). Second-order rate. The Cauchy–Schwarz step is loose because ĝ concentrates: the standard ratio-estimator expansion [11, Ch. 5], h T̂ i c ) E[T̂ ] Var(W c) E[T̂ ] Cov(T̂ , W E − = + + o(1/m), 2 3 c c] n n E[W W c )/n2 in norm (using Cov(T̂ , W c ) ≤ GM Var(W c ), has both correction terms bounded by GM Var(W since each coordinate of T̂ − ET̂ is a weight-linear combination of gradient coordinates bounded c , and E[T̂ ] /n ≤ GM ). Therefore by GM times the corresponding fluctuation of W δm ≤
c) 2 GM Var(W 2 GM k 2 + o(1/m) ≤ + o(1/m) = O(1/m). n2 α m n2 2
c ) = k · k−m · k−m ≤ k(k−m) , At α = 1 the design is SRSWOR with πi = m/k exactly, Var(W m k k−1 m giving δm ≤ 2GM k(k − m)/(mn2 ) + o(1/m). Both regimes are O(1/m); the empirical values (0.004 at large n; 0.037 in the adversarial micro-regime) sit inside these bounds.
12
B
Proof of Theorem 1
Write bt = E[ĝt | θt ] − ∇F (θt ) (∥bt ∥ ≤ δ) and ξt = ĝt − E[ĝt | θt ] (E[ξt | θt ] = 0, E ∥ξt ∥2 ≤ σ̂ 2 ). L-smoothness gives Lη 2 F (θt+1 ) ≤ F (θt ) − η⟨∇F (θt ), ĝt ⟩ + ∥ĝt ∥2 . 2 Take conditional expectations; using E[ĝt | θt ] = ∇F (θt ) + bt and E ∥ĝt ∥2 ≤ ∥∇F (θt ) + bt ∥2 + σ̂ 2 ≤ 2 ∥∇F (θt )∥2 + 2δ 2 + σ̂ 2 : E[F (θt+1 )] ≤ E[F (θt )] − η E ∥∇F (θt )∥2 − η E⟨∇F (θt ), bt ⟩ +
Lη 2 2E ∥∇F (θt )∥2 + 2δ 2 + σ̂ 2 . 2
1 Bound −E⟨∇F, bt ⟩ ≤ δ E ∥∇F (θt )∥ ≤ δG∞ . With η ≤ 2L , Lη 2 ≤ η/2, so the E ∥∇F ∥2 terms combine into − η2 E ∥∇F (θt )∥2 at worst. Rearranging and summing over t = 0, . . . , T − 1, then dividing by ηT /2:
min E ∥∇F (θt )∥2 ≤ t
2 (F (θ0 ) − F ∗ ) 1X E ∥∇F (θt )∥2 ≤ + Lη (σ̂ 2 + 2δ 2 ) + 2 δ G∞ . T t ηT
1 √c , T } yields the statement (absorbing constants; the +δ 2 of the main Substituting η = min{ 2L √ text majorizes 2δ 2 · Lc/ T for T large). With δ = 0 (HT form) the bound is the classical rate of Ghadimi and Lan [4].
C
Ablation history
The canonical design is the outcome of a systematic exploration; all rejected variants are documented to preempt re-exploration. Reference: v1, pi ∝ (K − ℓi ) over all of M, no reweighting. H1 (pi ∝ ℓi over all of M, no reweighting): bias +18 to +26%, variance +29% vs. v1 — rejected; note that this same proposal distribution becomes near-optimal once inverse-probability weighting is added, which is precisely the v3 construction. H2 (pi ∝ |ℓi − c|, symmetric U): interpolates v1 and H1, bias +6 to +12% — rejected. H4 (upper half only, pi ∝ K − ℓi on U): bias +60 to +80% — rejected; both terms of Lemma 5 then share a sign. v2 (lower half only, pi ∝ ℓi on L): bias −4 to −10% and variance −25 to −55% vs. v1, weight ratio bounded (r ≈ 1.4 vs. r ≈ 3 × 104 for v1; 0/40 vs. 14/40 violations of the sampling approximation at 1% tolerance) — adopted as an interim canonical form before the end-to-end extreme-imbalance and label-noise tests of Tables 2–4 revealed the shared failure of all uncompensated variants and motivated the compensated design. Equivalence sweeps: at matched bias, v2 allows no additional retention saving at N = 0.3 and +3.3% at N = 0.4 relative to v1 — the value of the uncompensated refinements was always estimator quality at fixed cost, never additional cost reduction, a conclusion that transfers to v3.
13