cs.LGNov 2, 2026

CERBO: Certified Recourse at a Requested Rate for Gradient-Boosted Trees

Authors: Farhan Shahriyar Hossain, Taufikur Rahman Fuad, Md. Zarif Bin Hasnat, Md Abrar Jahin, Md Rizwan Parvez

Organizations: Islamic University of Technology · University of Southern California · Qatar Computing Research Institute (QCRI)

Abstract

Recourse-aware learning trains models so that people who receive an adverse decision can reverse it with an affordable change. For gradient-boosted decision trees (GBDTs), the existing method, RABIT, exposes a single recourse weight whose effect on the recourse rate is abrupt and data-dependent, and its training bound cannot certify recourse for any rejected individual. We present Certified Recourse Boosting (CERBO), which takes a requested recourse rate and returns a GBDT with certified actions: it tracks exact additive effort along tree paths, trains against committed boxes (a family of bounds that contains RABIT's and certifies a within-budget action for each training sample) and adjusts the weight after every tree until the certified rate meets the request. A calibration step guarantees the rate on new individuals, and the certifier runs on any tree ensemble, including XGBoost and LightGBM, in milliseconds per person without a solver. In RABIT's own experimental protocol, at equal accuracy, CERBO raises the recourse ratio from 0.90 to 0.99 on FICO and from 0.64 to 0.77 on Bail. Under additive costs on six data sets, it raises the area under the accuracy-recourse frontier in all 12 settings, and in simulated deployments it guarantees recourse to 70% of rejected individuals in 11 of 12 settings, against 2 for RABIT.

Figures & tables

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Optimal Recourse Summaries via Bi-Objective Decision Tree Learning

    May 8, 2026Ioannis Chatzis, Jason Liartis, Athanasios Voulodimos +1Algorithmic AuditingDecision Tree Learning