Research map / Learning theory and algorithms / Prediction and decision losses

Discretization-free Multicalibration through Loss Minimization over Tree Ensembles

NeurIPS 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Tree ensemble optimization · 0 citations (OpenAlex)

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.

Proposes a discretization-free multicalibration method that post-processes a base predictor by square-loss ERM over depth-two tree ensembles (LightGBM), with a theorem guaranteeing multicalibration under a loss-saturation assumption.

Problem

Existing multicalibration algorithms discretize the predictor's output space and iteratively remap values within level sets, which departs from standard ERM, adds rounding error and a sensitive granularity hyperparameter, and can distort predictions.

Approach

Replace iterative level-set correction with a single square-loss ERM step over depth-two decision trees whose split features are thresholds on the base predictor's continuous output and group indicators; under a loss-saturation assumption this yields multicalibration error at most sqrt(epsilon_loss + epsilon_round).

Key results

• Empirical loss improvement from a second post-processing pass is tiny across all six tasks (e.g., 1e-4 for income classification, 6e-7 for income regression), supporting the loss-saturation assumption.
• The discretization-free method matches or beats LSBoost and MCBoost multicalibration error across discretization granularities m in {10,...,100}, even though baselines are tuned per discretization.
• Worst-group smECE for the proposed method is lowest on 5 of 6 tasks, e.g., 89.26 vs 146.68 (LSBoost best) on skin lesion and 24.57 vs 39.39 on comment toxicity.

Measured effects reported in the paper

Surprising findings

• Depth-two tree ensembles cannot represent XOR-style group interactions, so the method can fail to multicalibrate when the base predictor is constant (constructed counterexample).
• On travel time regression, the uncalibrated baseline already has low multicalibration error, leaving little room for post-processing gains.

Limitations

• Multicalibration guarantee relies on a loss-saturation assumption that is heuristic and lacks a general proof; counterexamples exist when the base predictor is uninformative.
• Finite-sample guarantees are only sketched via Rademacher complexity analysis in the appendix.
• Experiments are limited to a few tabular, image, and text tasks with around 50 or fewer groups.

Experimental setup

Datasets: ACS (Folktables) 2018 California UTKFace ISIC Challenge 2019 CivilComments (WILDS)

Benchmarks: ACS income regression ACS income classification ACS travel time regression UTKFace age regression ISIC 2019 skin lesion classification CivilComments toxicity classification

Metrics: multicalibration error (l1, grid-discretized) worst-group smooth ECE squared loss

Baselines: Uncalibrated baseline Multiaccurate baseline LSBoost MCBoost

Builds on: LightGBM MCBoost LSBoost multiaccuracy

Closest papers by meaning

• Bridging Multicalibration and Out-of-distribution Generalization Beyond Covariate Shift (NeurIPS 2024 · similarity 0.86)
• Improved Bounds for Swap Multicalibration and Swap Omniprediction (NeurIPS 2025 · similarity 0.86)
• Minimax Rates and Spectral Distillation for Tree Ensembles (NeurIPS 2026 · similarity 0.86)
• Instance-Adaptive Online Multicalibration (NeurIPS 2026 · similarity 0.85)
• Improved and Oracle-Efficient Online $\ell_1$-Multicalibration (ICML 2025 · similarity 0.85)
• Testing Calibration in Nearly-Linear Time (NeurIPS 2024 · similarity 0.84)