The authors present K-ABENA, a selective gradient computation framework that reduces per-iteration training cost by excluding low-loss observations from the backward pass. Its canonical form combines defensive-mixture sampling with Horvitz-Thompson inverse-probability reweighting to yield a design-unbiased gradient estimator.
- The method provides an O(1/sqrt(T)) non-convex convergence guarantee for SGD under the estimator.
- Uncompensated loss-based selection fails to reach stationary points at minimizers where selection bias is bounded away from zero.
- On real datasets, the compensated estimator saves 28-54% of per-epoch gradient computation while remaining statistically indistinguishable from full-batch SGD.
- The earlier biased "regularized mode" collapses under label noise and extreme imbalance, whereas the compensated variant maintains high accuracy.
The authors consider this important because it quantifies the failure of uncompensated variants like OHEM and SBP, offering a theoretically grounded alternative that achieves significant compute savings without sacrificing convergence properties.