Discretization-free Multicalibration through Loss Minimization over Tree Ensembles
Hongyi Henry Jin, Zijun Ding, Dung Daniel Ngo, Zhiwei Steven Wu · 2025
Read Discretization-free Multicalibration through Loss Minimization over Tree Ensembles by Hongyi Henry Jin, Zijun Ding, Dung Daniel Ngo, Zhiwei Steven Wu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-17435.txt.
Introduction
Hongyi Henry Jin and three co-authors found in 2025 a cleaner route to fair predictions across many overlapping groups. A predictor is multicalibrated when its stated odds hold true inside every group that matters. Old methods chop the output range into bins and patch values step by step, which adds rounding error and touchy settings.
Their method skips the chopping. It fits an ensemble of shallow decision trees by plain loss minimization, using off-the-shelf boosting tools. Under a stated fairness condition on the data, the method provably reaches multicalibration. Standard training pipelines stay intact.
Catalog record
| CREATOR | Hongyi Henry Jin, Zijun Ding, Dung Daniel Ngo, Zhiwei Steven Wu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-17435
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Discretization-free Multicalibration through Loss Minimization over Tree Ensembles Hongyi Henry Jin, Zijun Ding, Dung Daniel Ngo, Zhiwei Steven Wu Abstract In recent years, multicalibration has emerged as a desirable learning objective for ensuring that a predictor is calibrated across a rich collection of overlapping subpopulations. Existing approaches typically achieve multicalibration by discretizing the predictor’s output space and iteratively adjusting its output values. However, this discretization approach departs from the standard empirical risk minimization (ERM) pipeline, introduces rounding error and additional sensitive hyperparameter, and may distort the predictor’s outputs in ways that hinder downstream decision-making. In this work, we propose a discretization-free multicalibration method that directly optimizes an empirical risk objective over an ensemble of depth-two decision trees. Our ERM approach can be implemented using off-the-shelf tree ensemble learning methods such as LightGBM. Our algorithm provably achieves multicalibration, provided that the data distribution satisfies a technical condition we term as loss saturation. Across multiple datasets, our empirical evaluation shows that this condition is always met in practice. Our discretization-free algorithm consistently matches or outperforms existing multicalibration approaches—even when evaluated using a discretization-based multicalibration metric that shares its discretization granularity with the baselines. 1 Introduction In many applications, machine learning predictors are at the heart of the decision-making process, from finance ( Fuster et al., 2022 ) to healthcare diagnostics ( Rajkomar et al., 2018 ) . Despite its ubiquity, there is growing concern that these predictors might discriminate against individuals in protected groups. In recent years, multicalibration ( Hebert-Johnson et al., 2018 ) has emerged from the algorithmic fairness literature as a learning objective to mitigate the risk of algorithmic discrimination. Informally, multicalibration requires a predictor to be calibrated on average over a family of groups {\mathcal{G}} : for all groups g\in{\mathcal{G}} and for all v in the range of f , \mathbb{E}[(y-f(x))\cdot g(x)|f(x)=v]=0 where g\colon\mathcal{X}\rightarrow\{0,1\} is a group indicator function. Typically, multicalibration algorithms discretize the output space of the predictor so that the range of f , R(f) , is a finite set. Existing work in the multicalibration literature ( Hebert-Johnson et al., 2018 ; Globus-Harris et al., 2023 ; Haghtalab et al., 2023 ) heavily relies on the discretized output space or level sets , and all existing algorithms use calibration data to iteratively remap the output of a predictor f within these level sets to reduce the multicalibration error at each iteration. However, discretization can be undesirable in practice for several reasons. First, it introduces rounding error that can distort predictions and degrade accuracy. Second, it adds a sensitive hyperparameter—the discretization granularity—that must be carefully tuned. As noted by Nixon et al. (2019) , this induces a bias-variance tradeoff: finer discretization improves resolution but requires more data per bin, while coarser discretization sacrifices precision. Błasiok & Nakkiran (2023) observe that the calibration error metric can be unstable under different discretization parameters. Finally, when there are multiple downstream decision makers with heterogeneous utility functions, fixed discretization may fail to provide the precision necessary for them to make optimal decisions. Our results and contributions. In a nutshell, we develop a simple, practical, and performant discretization-free algorithm for multicalibration. In more details: • Given a black-box predictor, our discretization-free algorithm post-processes its outputs by solving a square-loss empirical risk minimization (ERM) problem over an ensemble of depth-two decision trees. Each tree splits on features derived from the predictor’s output or group membership. This ERM step can be efficiently implemented using standard tree ensemble methods such as LightGBM ( Ke et al., 2017 ) . • We prove theoretically that our algorithm outputs a multicalibrated predictor, given the assumption that decision tree ensembles saturate in loss improvement after optimization–that is, the square loss cannot be further reduced through another round of tree-ensemble post-processing. Empirically, we observe that this saturation condition consistently holds across multiple real-world datasets. • We evaluate our discretization-free approach across a diverse set of tabular, image, and text datasets. Compared to existing multicalibration methods, our algorithm delivers competitive and often lower multicalibration error—even when baselines are tuned baselines are tuned using the same discretization scheme used for evaluation. 2 Related works Multicalibration Multicalibration was first introduced by Hebert-Johnson et al. (2018) as a notion of multi-group fairness. This growing line of research is then extended in several directions, including generalizing or relaxing the notion of multicalibration ( Gopalan et al., 2022 ; Zhang et al., 2024 ; Wu et al., 2024 ; Deng et al., 2023 ) , applying multicalibration to conformal prediction ( Jung et al., 2022 ) , as well as exploring mathematical implications of multicalibration ( Jung et al., 2022 ; Gopalan et al., 2021 ; Globus-Harris et al., 2023 ; Wu et al., 2024 ; Kim et al., 2022 ) . Algorithms for multicalibration. All existing multicalibration algorithms are discretization-based and operate across level sets of the predictor. Hebert-Johnson et al. (2018) ; Globus-Harris et al. (2023) audit multicalibration error of the predictor within the level sets in each iteration and patch identified bias until convergence. Haghtalab et al. (2023) views multicalibration as a multi-objective optimization problem solved using game dynamics, where the groups and the level sets are generalized to distributions and loss functions in general. Multicalibration and Loss Minimization. A key appeal of multicalibration is its alignment with loss minimization: existing multicalibration algorithms iteratively update the predictor with each update reducing the square loss. This naturally raises the question—can multicalibration be achieved directly via a single loss minimization step? Błasiok et al. (2023) show that minimizing population loss over a class of neural networks of certain size yields multicalibration for groups defined by smaller networks. However, their result is non-constructive and assumes optimization oracle over an intractable function class. In contrast, our approach solves a one-shot ERM over a simple class of tree ensembles, implementable via standard tools. Relatedly, Hansen et al. (2024) ask whether ERM alone suffices. Our experiments show that it often does not—but our post-processing reliably recovers multicalibration. 3 Preliminaries We consider prediction tasks over a domain \mathcal{Z}=\mathcal{X}\times\mathcal{Y} , where \mathcal{X} represents the feature domain and \mathcal{Y} represents the label domain. We require the labels to be real values in [0,1] – that is, the label can either be a binary outcome for classification with \mathcal{Y}=\{0,1\} or a real value for regression with \mathcal{Y}=[0,1] . For a domain \mathcal{Z} , we write \mathcal{D}\in\Delta(\mathcal{Z}) to denote the true distribution over the labeled samples. A predictor f is a map f:\mathcal{X}\to[0,1] . We write \mathcal{R}(f) to denote the range of a predictor f . We are interested in the squared error of a predictor f with respect to the underlying distribution \mathcal{D} . Definition 3.1 (Squared loss) . The squared loss of a predictor f on distribution \mathcal{D} is \ell(f,\mathcal{D})=\mathbb{E}_{(x,y)\sim\mathcal{D}}[(f(x)-y)^{2}] (1) We omit the distributions \mathcal{D} from the notation when it is clear from context. Note that when \mathcal{Y}=[0,1] , the squared loss is the familiar MSE loss function, whose application in multicalibration has been discussed in Globus-Harris et al. (2023) . When \mathcal{Y}=\{0,1\} , the squared loss is the Brier score, which is commonly used for multicalibration algorithms ( Hansen et al., 2024 ; Błasiok et al., 2023 ) . We formally specify the multicalibration notion used in this work. Given