Discretization-free Multicalibration through Loss Minimization over Tree Ensembles
Authors: Hongyi Henry Jin
Zijun Ding
Dung Daniel Ngo
Steven Wu
Venue: NeurIPS 2025 poster ()
Keywords: Algorithmic Fairness
Multicalibration
Primary area: social_and_economic_aspects_of_machine_learning

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 an 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. Code to replicate the results in this work is available at https://github.com/hjenryin/Discretization-free-MC.

Discretization-free Multicalibration through Loss Minimization over Tree Ensembles
Hongyi Henry Jin
Zijun Ding
University of California, Los Angeles Los Angeles, CA, USA
Carnegie Mellon University Pittsburgh, PA, USA
Dung Daniel Ngo"
Zhiwei Steven Wu Carnegie Mellon University Pittsburgh, PA, USA
J.P. Morgan Chase AI Research New York, NY, USA
Abstract
In recent years, multicalibration has emerged as desirable learning objective for ensuring that predictor is calibrated across rich collection of overlapping subpopulations. Existing approaches typically achieve multicalibration by dis- cretizing 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 sensi- tive hyperparameter, and may distort the predictor's 's outputs in ways that hinder downstream peciiiio-mmainn
In this work, propose discretization-fiet multicalibration method that di- rectly optimizes an empirical risk objective over an ensemble of depth-two deci- sion trees. Our ERM approach can be implemented using off-the-shelff tree en- semble learning methods such LightGB.M. Our algorithm provably achieves multicalibration, provided that the data distribution satisfies technical condition we term as loss saturation. Across multiple datasets, our empirical evaluation shows that this condition always met in practice. Our discretization-fiet algo- rithm consistently matches outperforms existing multicalibration approaches- even when evaluated using a discretization-bant based multicalibration metric that shares its discretization granularity with the baselines. Code to replicate the results this work available at [https: /ttp://ggtth/////// com/ hoom//jeerriin Discretization free MC
Introduction
In many applications, machine learning predictors are at the heart of the decision-making process, from finance (Fuster et al. (2022) 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 faimesss literature learning objective to mitigate the risk of algorithmic discrim- ination. Informally, multicalibration requires predictor to be calibrated on average over a family of groups G: for all groups G and for all v in the range of
E[(y f()) fzz) v|
where g: X + (0, 1} a group indicator function.
Part the work was done CMU.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

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,j 2018 Clobus-Harris et al. 2023; Haghtalab et al.) (023) 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-thal must be carefully tuned. As noted by Nixon et al. (2019), this induces varsinarannce tradeoff: finer diseretization improves resolution but requires more data per bin, while coarser discretization sacrifices precision. BBlasiok & 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 make optimal decisions. (Zhao al. 2021
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 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 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-procesiigg Empirically, we observe that this saturation condition consistently holds across multiple real-world datasets.
We evaluate discretization-fiet approach across diverse set of tabular, image, and text datasets. Compared to existing multicalibration methods, our algorithm delivers competi- tive and often lower multicalibration error- even discretization scheme used for evaluation.
even when baselines tuned using the same
2 Related works
Multicalibratiin
Multicalibration was first introduced by Hebert-Johnson et al. (2018) as no- tion of multi-group fairness. This growing line of research is then extended in several directions. including generalizing relaxing the notion of multicalibration (Gopalan al. 2022: Zhang al.
2024
Wu et al., 2024. Deng et al. 2023). applying multicalibration to conformal prediction (Jung al. 2022). as well as exploring mathematical implications of multicalibration (Jung et al. 2022
Gopalan et al. 2021 Globus Blobus-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); HarrissHarris cet 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 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- directly via single loss minimization step? [lasiok 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 con-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. (024) ask whether ERM alone suffices. Our experiments show that it often does not but our post- processneessing reliably recovers multicalibration.
multicalibration be achieved

---

3 Preliminaries
We consider prediction tasks over domain Z x y. where represents the feature domain and y represents the label domain. We require the labels to be real values in [0, 1] that is, the label can either be binary outcome for classification with y {0, } real value for regression with ) [0, 1]. For domain 2, we write D E (( to denote the true distribution over the labeled samples.
A predictor f is map f: : X' - [0, 1]. We write R(f)) to denote the range of a predictor f. We are interested in the squared error of predictor f with respect the underlying distribution D.
Definition 3.1 (Squared loss). The squared loss of a predictor I on distribution D is
((f.D) (( (ff(z) y)²
(1)
We omit the distributions from the notation when is clear from context.
Note that when y = [o, 1), the squared loss is the familiar MSE loss function, whose application in multicalibration has been discussed in Globus-Harris al. (2023). When y =00,1) the squared
loss is the Brier score, which is commonly used for multicalibration algorithms (Hansen et al. 2024 Blasiok et al., 2023).
We formally specify the multicalibration notion used in this work. Given the underlying distribution D and a set of groups 9 C 2* we write g + {0, 1 1JI0I as the high-dimensional group indicator function, where (xr) indicates that the datapoint multicalibration error, we use the following & definition (Hansen et al., (024). Note that the l version of multicalibration is more interpretable than the 12 version, and different versions of multicalibration can be bounded by each other (Globus- Harris et al. 2023).
X' belongs to the i-th group. To measure
Definition 3.2 (Multicalibration Error). Fix a distribution D (2 and predictor X [0, 1]. We define the mullicalibration error of f with respect to D and 9 as:
Σ DER())
Pr (a.)) (fx)
P v. (x) 1] [ (fx)) f(x) U. (x) 1]1
(2)
We say that a predictor f a-multicalibrated if its multicalibration error most a. Note that our definitions here and analysis in the next section are population- basedd and we leave the finite-sample analysis to Appendix
4 DFMC: A Discretization-Free Algorithm for Multicalibration
In this section, we describe our proposed algorithm for multicalibration. At high level, we train decision tree ensemble of depth 2, using the output base predictor fo and the group membership as input features, to minimize the squared loss on the true distribution D.
More formally, consider the following subsets of X' used the splitting criterion for the decision trees:
(fo) = {(x E X fo(x) 2 o} E u
S2( {(x ex (x()) = 1) [[G]]]
Each decision tree of depth 2 in the ensemble assigns real value es qiii [4] to each of its 4 leaves. Formally, the set of decision trees written as T( 9), where:
T(oo 9) c H( ESI + I(r E Ax 82) c Tfx & A E
+ c4 1x A $2 C1, C2, C3, c4 E s1 (1b), 82 S
To find the optimal of decision trees T C C(ff9), 9), we use solver to minimizes the squared loss and obtain our post-processed predictor:
Pa (o(f)
arg min
fo (6++ +,DD
(5)
Tg ()
LET
3

---

In practice, the implementation of most solvers does not enforce this exact structure of choosing splitting criterion. For simplicity, we present our algorithm as in Equation ( and we explain in Appendix C why our analysis still holds for them despite such slight differences.
Tree 1
Algorithm 1 Discretization-fre Multicalibration
(DFMC)
folx) 0.37
Require: Calibration set D
(X,J),
+
No
Tree
Group indicator function g X - {0, 10.1]
Uncalibrated base model fu : X 7 R,
92
62 (2)?
Ensemble solver SOLVEENSEMBLE
Yes
1: Set the (lg) + d)-dimensional input features
-0.3
+0133
-0:2
+0.12
X' (
2: Set the output features y = =
Figure Illustration of the tree ensemble.
3: return SOLVEENSSOV""NNEERBE"""""
An illustration of Equation (5) can be found in Figure Being discretization- free enables our algorithm to avoid the complexity with discretization, makes it simpler and provides more flexibil- ity than existing ones. Algorithm outlines how we can optimize for Equation (5) using on-the- shelf solvers like LightGBM (Ke et al.] 2017) XGBoost (Chen & Guestrin, 2016) with simple features. Also, although the evaluation of Definition 33.2 still requires discretized predictions, our discretizationn-ree predictor be evaluated under flexible discretization scheme with consistently strong performance. We formalize this flexibility in Definition 4.1
Definition 4.1 (Discretization Operation), A function fm is an m-discretized version of a predictor if it maps the continuous output of to finte set of m values, with the property that fm Z (12) whenever (xx1 2 (xx22 for any Iı, 322 E X. We write the discretization error Ground as Ground = =(ffral
Foal D) fffaal D).
(6)
Note that we do not restrict ourselves to specific discretization function for this evaluation. Round- ing to the nearest value on predefined grid, which commonly used existing multicalibration algorithms, is among the possible discretization methods we allow. As we will show shortly, unlike algorithms that incorporate discretization as intrinsic component, our discretization-fret predictor performs well under various discretization schemes used solely for evaluation purposes.
Through the following lemmas, we associate the continuous optimization for the squared loss with the discretized metric of multicalibration.
Lemma 4.2. Consider the post-processing step Pg in Equation 5). For all f E [0, 1] and m E N, and for any m-discretized version fm of f. we have
U(p(ff) S ((po(fm))))
The proof follows by constructing set of trees T E T(f.9) such that f + Exer approximates Pg (f()) well.
Lemma 4.3. Given a predictor f whose range is of size m, training an ensemble of decision trees on f as in the post-procest pos-pprcessiing step Equation encompasses adding linear function of the groups on each output level set of f. That is,
m Σ I[f(x)= = (2)
df GER
S
++
f Σ TET
17)
where Um R())2u 1/2 Um.
The proof follows by rewriting [xf(x) f as thresholding functions.

---

Lemma 4,4. If a predictor f with R(f) {U1, ... .um y has a multicalibration enror w.r.t G larger than then there exists linear functions h1 Ei C, such that
((1,)) l ft I[ u,},3, D + a²
(8)
The prrof follows by picking the worst group 9k from the definition of multicalibration for each by and constructing the linear functions h, = G2Kk-
Before the main theorem, we introduce the following necessary assumption.
Assumption 4.5 (Loss Saturation of Algorithm D. Given an uncalibrated predictor fo. let fral pa(fo) be our proposed predictor calibrated with Algorithm [
We assume that the squared loss of fool is e-saturated w.r. Pg with small marginal improvement Closs < 1:
E(foal D) ((pa() Eloss
(
that is, running Algorithm on foot again gives a small marginal improvement of at most Closs-
This is reasonable assumption because our formulation is essentially supervised learning problem with simple features, where the objective is to minimize the squared loss. Decision tree ensembles a well-established and widely used method in general for this setting, with mature solvers and have stood the test of time. Consequently, the loss achieved by our method should already low, leaving little room for further improvement. We also provide numerical simulation in Table T on the datasets to empirically support this assumption.
Theorem 4.6 (Algorithm I Yields Small Multicalibration Error Given Assumption 4.5 Let foul be the predictor obtained by Algorithm 1 and feal be m-discretized version. If the discretization error of feal is Eround, and the loss of foul is -sturraatd with respect to Pg as in Assumption 4.5 then the mullicalibration error of feal with respect to G is at most / VEloss + 6yound-
Proof. If Fool has a multicalibration error larger than a, then post post-processing it with pg can reduce Jm
the loss:
Ficll D) - (po(Fmat), =[(fral Feal D) -
min TST(eee
fm
+ Σt.D
(Equation (5)
LET
Foal D) -min&
jeul +
Σ
11 11 = 14,,
hj
1=1
(Lemma 4.3
>
(Lemma 4.4
On the other hand, the reduction of loss should be small:
feall D) 1000p(pp(fi) (po(feal), D) <e(foal, D) + Eround l (ppal)))),
(Equation (
<((f D) + Ground l (poa))
(Lemma 4.2)
Sftoss Ground
(Assumption 4.5
This implics that the multicalibration error feal is at most / Eloss + Eround-
Remark 4.7. To wrap up the analysis, we provide high level comparison of our algorithm with relevant prior works. The theoretical algorithm proposed in Blasiok et al. (2023) is the most similar one to ours in that both theoretically achieve discretization- mization. While they theoretically proved loss saturation for an intractable class of neural networks by adding more nodes without practical implementation, we empirically verify this assumption for tree ensembles and provide an efficient algorithm.
multccaiiratton through loss mini-
5

---

On the other hand. the construction of a tree ensemble is highly relevant to the algorithm presented in Globus- Harris et al. (2023). Unlike their approach, ours uses the continuous output as a feature in the ensemble, thereby avoiding discretization. Apart from that, our algorithm is quite similar to the first iteration of theirs via the relationship shown Lemma 4.3 with Assumption 4.5 indicating convergence after this single iteration.
5 Experiments
5.1 Dataset Setup
In this section, we describe the dataset we use and the experiment pipeline.
A common dataset to consider in fairness and multicalibration literature is the ACS dataset, obtained through the Folktables (Ding et al.) 2021) package. The Folktables package defines a rich set of tasks, and consider three tasks derived from the dataset: income regression and travel time regression predicts the person's income and commute time, and income classification predicts whether person's income is higher than $50,000. On each of these tasks, we define around 50 groups based on the data attributes.
The prior work of Hansen et al.] (2024) has pointed out that multicalibration post-processing has limited effect on tabular data, so we also evaluate our algorithm on various text and image datasets. Zhang et al. (2017) introduced the UTKFace dataset, with person's face image associated with their age, gender and race. We consider the task of predicting the age of the person given the face, and use individual's 's attribute as the group. ISIC challenge dataset is image dataset related to skin lesion, and we considered the task introduced in the ISIC Challenge 2019 (Tschandl et al.) 2018 Codella al. 2017 Combalia al. 2019) predict whether the skin lesion is melanocytic nevus or not. The dataset provide metadata including the age, gender or anatomic site of the patient, and we use these as the group. Finally, we consider the Comment Toxicity Classification dataset (Borkan et al. (2019) from the WILDS dataset (Koh et al. (202]). which is a text classification task to predict whether comment is toxie not. The WILDS dataset already defines eight groups based on the identities mentioned in the comment, and we use them as the group.
Detailed description of the dataset, including dataset partitioning and the specific groups, is left to Appendix D
5.2 Our algorithms and the baselines
In this section we describe the algorithms evaluated these experiments, which includes two discretization-free baselines with no multicalibration guarantee, two existing multicalibration algo- rithms, and our algorithm. The uncalibrated baseline depends largely on the task: We used linear models for tabular data, ResNet for image data, and DistilBERT for text data. Due to its dependency on the specific dataset, further details are left to Appendix D Another baseline algorithm that we might be interested in is the multiaccurate predictor (Hebert-Johnson et al. 2018 Roth 2022), which guarantees that the predicted mean on each subgroup is close to the true mean on that group. Although it's a far weaker notion than multicalibration, it's s an extremely simple method promoting fairness across subgroups that can be implemented with a single linear model.
The multicalibration algorithms that we compare with are MCBoost and LSBoost. Both require discretizing the output space in advance and work in an iterative manner by correcting the prediction on each level set until convergence. MCBoost (Roth 2022) enumerates over {a : ge(x)) = 1, f(x) t} for all E [[[]] and v E R(f) in every single iteration and fixes the subset with the largest deviation from the true mean by setting the predicted value on that subset to the true mean. LSBoost Hlobus-Harris et al. 2023), on the other hand, considers the groups as a whole. In each iteration, the whole calibration set is partitioned into multiple level sets based on the current predicted value, and a weak learner is fit with the group information for each level set using data points in that set. The predicted value of the weak learner will assign the data points new level set for the next iteration. Finally, we implement our algorithm described in Algorithm I with the LightGBM (Ke) et al. 2017) solver.
MCBoost and LSBoost require discretization before calibration, so for each selection of discretiza- tion, we find the hyperparameters that minimize the multicalibration error on the validation set. As

---

Table 1: The empirical marginal improvement of running Algorithm provement is minimal, validating Assumption
the second time. The im-
4.5
Task
E(fo)
{(fra)
((po(f
closs ((foal)
{(po (feal)
Skin Lesion Classification
0.2262
0.1475
0.1492
-2 x 10
Income Classification
0.1831
0.1432
0.1431
x 10-1
Comment Toxicity Classification
0.0589
0.0516
0.0517
-2 x 10-5
Age Regression
0.0051
0.0011
0.0011
x 10-6
Income Regression
0.0414
0.0361
0.0361
x 10-7
Travel Time Regression
0.0302
0.0298
0.0298
2 x 10-6
for the other three algorithms, we just directly minimize the squared error. Further details, includ- ing training specifications and hyperparameters, are left Appendix E For all experiments, we fix the training set for the uncalibrated baseline and the test set for evaluation. The calibration and validation set are partitioned 10 times, with the standard deviation indicated in the plots and the tables.
5.3
Experiment Results
5.3.1 Empirical validation of Assumption 4.5
We first validate Assumption 4.5 empirically: Running Algorithm ! second time gives small marginal improvement. Note that due to the imperfection of optimization, we would not be able to obtain the true minimizer of the test set. Instead, we run the optimization set with early stopping and present the empirical loss improvement ČLees {p (f) - E(f) on the test set. The true Closs would contain
the calibration
additional optimization error term Copt. satisfying éloss Élass + Copt. We present Éloss in Table I and summarize our first observation:
Observation 1. Across all different datasets and tasks evaluated, the marginal improvement of rumning Equation 5 a second time is small, validating the loss saturation assumption in Assump- tion
5.3.2 Threshold-robut evaluation of multicalibration error
In this section, we empirically validate Theorem and compared our discretization-fii algorithm with other multicalibration algorithms. Recall that for the evaluation of multicalibration error, the predictor needs have a finite range, so we would need derive discretized version of a con- tinuous predictor for evaluation. We ensure fair comparison across different algorithms by using the same discretization regime.
particular, we use the grid discretization regime and restrict the 2m-1), ), where m is the number of element in the level set. We vary m E {10, 20, 30, 50, 75, 100). While a separate predictor is trained for each y for MCBoost and LSBoost, we only train single predictor for our algorithm and then evaluate the multicalibra- tion error of its m-discretized version with varying m.
codomain to LS = { 2m. 2m
We present the multicalibration error versus the number of non-empty level sets in Figure 2
Observation 2. Although empirical buseline algorithms can obtain low multicalibration error in certain cases, post-processing can further decrease the error in general.
A direct observation is that Travel Time Regression is an outlier among the six subplots in Figure 2 Although all other datasets evaluated, the uncalibrated baseline has a higher multicalibration error, compared to other algorithms, such a difference in the error is not observed in this dataset. The uncalibrated baseline algorithm already obtained low multicalibration error, leaving little room for improvement for other post-processing methods. This partially echoes the observations in Hansen et al. (2024) that ERM on certain function classes can already achieve low multicalibration error on tabular data; yet it also highlights that post-processing is indeed necessary in general to obtain multicalibrated predictor.
Observation 3. Our algorithm achieves multicalibration error that matches and often improves upon existing methods. This performance advantage persists even when competing algorithms are specifically tuned using the same discretization scheme used in evaluation.
7

---

Multicalibration error
Skin Lesion Classification
Income Classification
Comment Toxicity Classification
0.08
0.08
0.006
0.06
0.06
Multicalibration Error
0.001
0.04
0.04
0.02
0.02
0.002
50
100
50
100
Age Regression
Income Regression
Travel Time Regression
0.02
0.01
0.015
0,015
0.01
0.005
0.005
0.005
20
40
60
80
50
100
10
20
Size Predictor Range
Different discretized version of uncalibrated buseline predictor
Different discretized version of multinceurate baseline predictor
Sooostt predictors trained with different discretization
MCBoost predictor trained with different discretization
Different discretized version of our predictor
Figure 2: Multicalbbration error on different datasets. The y-axis is the multicalibration error, and the x-axis is the size of range, which may not equal m, the size of the codomain, and the error band displays the standard deviation. The graph shows that, a predictor trained using our algorithm can be discretized arbitrarily, and its m-discretized version has matching lower multicalibration error than the predictor calibrated with other multicalibration algorithm using that specific discretization.
We compare the algorithms at the same range size to minimize the effect of discretization error Our discretization-fret algorithm was only calibrated once minimize the squared loss, and in most cases its m-discretized version has matching or better multicalibration етгог than the other multicalibration algorithms, even though these algorithms go through separate hyperparameter tuning and calibration process for each discretization m. This observation validates our theoretical analysis in Theorem 4.6 and demonstrates the benefit of our discretization-fret algorithm of being flexible to down-stream discretization.
5.3.3 Discretization-free fairness through worst-group Smooth ECE
We would also like to evaluate our algorithm with another metric, worst-group smooth expected calibration error (worst-group smECE), which has also been used heuristic metric in Hansen et al. (2024). smECE was introduced by Blasiok & Nakkiran (2023) as a continuous metric cali- bration, and thus feel it can be suitable for our evaluation. In the context of multi-group faimess,
we could evaluate smECE on all groups that we' re interested in and take the worst group as the final metric, although it is not directly related multicalibration. This would also serve comple- ment to the metric of multicalibration, which can be viewed as the group-size-weightee worst-group binned ECE. The result presented in Table can be summarized by the following observation.
Observation Our discretization-fre algorithm achieves better calibration on the worst groups than other multicalibration algorithms.

---

Table The worst group smECE of the evaluated algorithms, along with their standard deviation. The values have been multiplied by 1000 for readability. Results show that our discretization- -ree algorithm is more calibrated among the worst groups than other multicalibration algorithms.
Skin
Comment
Travel Time
Income Class.
Age Reg.
Income Reg.
Method
Discretization
Lesion Class.
Toxicity Class.
Reg.
Uncalibrated Baseline
290.77
281.81
119.28
111.04
155.13
72.38
Multiaccurate Bascline
169.28
94.05
71.38
47.54
56.61
34.94
#6.24
#5.71
#6.89
#0.71
+0.29
#5.72
10
146.68
102.06
41.04
41.51
72.29
58.73
#27.44
#11.17
110.34
29.73
113.41
#3.59
159.31
102.57
39.39
23.29
73.82
54.96
20
#29.24
+17.25
+12.74
+7.00
+9.76
#14.69
30
160 80 #36.54
90.17
36.61
20.25
80.03
60.88
26.59
19.77
113.36
113.63
LSBoost
147.87
102.08
38.42
25.49
82,78
55,20
50
+12.13
75
144.05
108.26
45.66
34.16
81.47
59.07
#22.57
#14.05
#6.55
#7.26
13.62
100
149.77
124.94
44.28
51.13
76.83
66.59
#26.00
+20.48
#7.77
#11.13
+3.39
+5.34
278.75
259.83
78,30
106.73
154,28
59.42
217.81
25.00
115.59
20.00
15.12
20.00
263.71
212.19
65.17
108.20
138.96
72.01
#18.93
+33.65
#20.58
20.00
26.81
40,00
261.02
186.57
90.66
106.34
125.01
73.96
30
#26.77
#41.96
117.87
20.00
#16.07
20.00
MCBoost
50
252.76
182.07
86.74
112.37
141.07
69.69
217.20
145.79
121.29
20.00
15.60
16.83
75
239.26 26
193.78
81.74
111.00
130.15
68.79
#22.52
+6.30
#3.72
#16.26
+2.25
100
259.49
198.78
85.24
109,82
131.43
67.30
221.55
Ours
89.26
87.30
24.57
20.87
44.41
31.85
+25.94
+4.76
5.3.4 Evaluation of loss and accuracy
Apart from multicalibration, some standard metrics might be of interest when evaluating an algo- rithm. We present accuracy for classification tasks and MSE error for regression tasks. The results presented in Table yields the following observation:
Observation 5. Our algorithm does not sacrifice standard evaluation metrics like MSE error or accuracy.
Such results are anticipated, as our algorithm is simply minimizing the loss (namely the MSE error for regression tasks or the Brier score for classification tasks) based on a set of selected features.
Conclusion
In this work, we provide discretization- algorithm for multicalibration by solving ERM problem with simple features using decision tree ensembles, thereby avoiding the nuisance of dis- cretization. We prove theoretically that algorithm outputs multicalibrated predictor, given the assumption of loss saturation in tree ensembles, which is consistently validated across multiple real-world datasets. Our experiments also confirm our algorithm's 's strong performance compared to existing ones.
We believe our work has impact societal aspects of machine learning. Our algorithm can be ap- plied to high-stakes decision-making systems domains such as finance, healthcare, and employ- ment. The discretization-fin nature allows our predictor to serve as a drop-in replacement for an un- calibrated regressor or binary classifier suitable for different downstream applications; and by fram- ing multicalibration into typical loss minimization problem, provide simple library-calling

---

Table The accuracy (%) of the evaluated algorithms, along with their standard deviation. Results show that our discretization-fee algorithm does not interfere with the standard MSE error of regres- sion problems.
Class. Accuracy (%)
Reg. MSE Error (x10-3)
Skin Lesion Class.
Comment Toxicity Class.
Travel Time Reg.
Method
Discretization
Income Class.
Age Reg.
Income Reg.
Uncalibrated Baseline
70.21
76.71
92.88
5.11
41.39
30.19
Multiaccurate Baseline
73.
92.89
3.51
37.92
29.76
20.31
20.06
40.00
#0.02
a0.02
20.02
77.22
77.96
92.81
2.01
39.66
31.00
#1.00
+0.25
+0.08
#0.24
#0.35
#0.07
20
76.55
78 09
92.78
1.42
38.98
30.29
20.95
10.33
10.06
20.16
40.31
20.09
30
76.86
78. 16
92.78
1.36
39.03
30.25
20.46
#0.21
40.06
#0.13
40.23
#0.04
LSBoost
50
77.06
78. 11
92.71
1.52
39.51
30.16
20.17
40.22
20.03
75
76.52
77.81
92.65
1.53
38.83
30.13
#0.19
+0.19
#0.03
100
76. 12.12
77.60
92.81
1.72
38.80
30.17
+0.30
#0.20
#0.20
=0.03
71.00
76.71
92.88
5.08
42.18
31.23
#1.01
+0.00
+0.00
#0.25
40.01
#0.00
72.15
77.10
92.88
4.69
41.10
30,42
#1.63
+0.34
+0.00
+0.30
#0.23
=0.00
73.54
77.23
92.88
4.92
40.70
30.31
#1.24
+0.20
+0.00
#0.17
#0.26
=0.00
MCBoost
72.07
77.20
92.88 .8.8
4,40
40.93
30.22
+1.01
+0.40
+0.00
+0.38
#0.27
=0.00
75
73.12
76.89
92.88
3.81
40.72
30.22
21.00
10.17
40.00
20.36
40.32
20.01
72.29
76.70
92.87
3.88
40.95
30.18
100
#1.08
+0.22
#0.41
+0.29
20.03
Ours
78.90
79.27
92.93
1.08
36.11
29.80
20.02
20.04
implementation that lowers the technical barrier for practitioners to incorporate fairness- aware tech- niques into their workflows. We believe this work can enhance the adoption of multicalibration techniques within the machine learning community.
A limitation of this work is that Assumption i. is heuristic assumption that holds under realistic settings, but has unrealistic counterexamples described Appendix where So contains no infor- mation. From this construction, it seems that the additional improvement éloss may depend on the uncalibrated predictor we start with, namely fo- For future work, would interesting to formalize such dependency and bound the error.
Additionally, the scope of this work primarily focuses on group fairness, requiring binary group indicators to be explicitly provided as the input to the proposed algorithm, which is a common setting in group fairness research. (Caton & Haas, 2024) The algorithm does have the potential to extend to implicit groups, such as groups defined from continuous features, or intersections of the explicitly provided ones. Continuous features like age could be directly handled by tree-ensemble solvers. Besides, intersections of the input features could be captured by deeper tree structures. We designate the empirical performance and theoretical claims of these extensions for future research.
Acknowledgment
7.SW was supported in part by the NSF award #2232692.
10

---

References
Borkan, D., Dixon, L., Sorensen, J., Thain, N., and Vasserman, L. Nuanced metrics for measuring unintended bias with real data for text classification. In Companion Proceedings of The 2019 World Wide Web Conference, 2019.
Blasiok, J. and Nakkiran, P. Smooth exe: Principled reiabbii diagrams via kernel smoothing, 2023. URL https: http://aaxvvvv.. org/ abs/2309/ 12236
Blasiok, J., Gopalan, P., Hu, L., Kalai, A. T., and Nakkiran, P. Loss minimization yields multicali-
bration for large neural networks, 2023. (tRthttps: /taas///axxiii http//awwwv....aaaaaa//o// wttp://ggggbbb/.ooeeese www.//3cee.. 09424
Caton, S. and Haas, C. Fairness in machine learning: A survey. ACM Comput. Surv., 56(7),
April 2024. ISSN 0360-0300. doi: 10.1145/3616855. URL httpp:://cc..org//eee/op// 66655
Chen, T. and Guestrin, C. Xghoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785- 794. ACM, 2016.
Codella. N. C. F., Gutman, D. A., Celebi, M. E., Helba, B., Marchetti, M. A.. Dusza, S. W. Kalloo, A., Liopyris, K., Mishra, N. K., Kittler, H., and Halpern, A. Skin lesion analysis toward melanoma detection: A challenge at the 2017 international symposium on biomedical imaging (isbi), hosted by the international skin imaging collaboration (ISIC). CoRR, abs/1710.05006, 2017. URL http: / arxiv. org/ abs /1710. 05006
Combalia, M., Codella, N. C. F., Rotemberg, V., Helba, B., Vilaplana, V., Reiter, O., Carrera, C., Barreiro, A., Halpern, A. C., Puig, S., and Malvehy, Ben20000: Dermoscopic lesions in the wild, 2019. htttttt/t///aiiiii wrg. 9088 02288
Deng. Z., Dwork, C., and Zhang, L. Happymap A generalized multicalibration method.
In Information Technology Convergence and Services, 2023. URL https://api.
semant romanticscholas org/ httg://orpusDDDD 256504829
Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 34, 2021.
Duffy, N. and Helmbold, D. P. Boosting methods for regression. Machine Learning, 47(2-3))153- 200, May 2002. doi: 10.1023/A:1013365666444 URL httpp:://oi..rr 10.13///1.1110// 1013685603443
Fuster, A., effects of machine learning on credit markets. The Journal Finance, 77(1):5-41 2022.
P., Ramadorai, T., and Walther, B. Z. Predictably unequal? the
Clobus-Harris, I., Harrison, D., Kearns, M., Roth, A., and Sorrell, J. Multicalibration as boosting for regression. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 1445--11492. PMLR, 23-29 Jul 2023. URL https: https::/pproceeinngs. mlr wtt.::s..w..........mmmm wwwpsseeeeuo.. globus harris23a................ html
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. Omnipredictors, 2021. URL
https: aawiiiiii........ wwggabs.ss....ooo.....o...e./.ee 25390
Gopalan, P., Kim, M. P., Singhal, M. A., and Zhao, S. Low-degree multicalibration. In Loh, P.- L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 3193 3234. PMLR, 02 05 Jul 2022. URL mlr prwss v1 / gww.lan22..aaaaaooooooo
Haghtalab, N., Jordan, M., and Zhao, E. A unifying perspective on multi-calibration In Oh, A., Naumann, T., Glober-
Game dynamics for multi-objective learning. son, A., Saenko, K., Hardt, M., and Levine, (eds.), Advances Neurul formation Processing Systems, volume 36, pp. 72464-72506. Curran Associates, Inc., 2023. URL
hctpp//ppprrr.iilee//pp/////22. fi Ei1/99aaccaaaee33333002200200222

---

Hansen, D., Devic, S., Nakkiran, P., and Sharan, V. When is multicalibration post- processoces nec- essary?, 2024.
wwtp:ii..rrr//aaao aaaaaaas//244 06487
Hebert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. Multicalibration Calibration for the cnapputtttionlll-ddnniifii masses. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1939-1948. PMLR, 10-15 Jul 2018. URL #ress/v80/hebre johnson 1 8a .html
mlr.
Jung, C., Noarov, G., Ramalingam, R., and Roth, A. Batch multivalid conformal prediction, 2022.
URL htttttttp///xiiii owg. 2209. 15145
Ke, G., Meng, Q. Finley, T., Wang. T., Chen, Ma, W., Ye, Q. and Liu, T.-Y. Lightgbm: A highly efficient gradient boosting decision tree. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.,
Files/paper/2017/ 2017. URL httpps://proceeddnnng/ www.:ne....ccccoo.......eoo pdf File/ 34494444400020888666666666665553
Kim, M. P., Kern, C., Goldwasser, S., Kreuter, F., and Reingold, O. Universal adaptability: caree--ndeeenndent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119(4))e10809711) 2022. doi: 10.1073/pmas.21089971999
Koh, P. W., Sagawa, S., Marklund, H., Xie, S. M.,, Zhang, M., Balsubramani, A., Hu, W., Yasunaga, M., Phillips, R. L.., Gao, I., Lee, T., David, E.,, Stavness, I., Guo, W., Earnshaw, B. A., Haque, I. S., Beery, S., Leskovec, J., Kundaje, A., Pierson, E., Levine, S., Finn, C., and Liang, P. WILDS: A benchmark of wn-the-wild distribution shifts. In International Conference Machine Learning (ICML), 2021.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Foundations of Machine Learning, second edition. Adaptive Computation and Machine Learning series. MIT Press, 2018. ISBN 9780262351362. URL https:
google..ooooooooooooooooooo..o.. www haana//ooksiico www.:iiddd.BWWAAABB....
Nixon, J., Dusenberry, M. W., Zhang, L., Jerfel, G., and Tran, D. Measuring calibration in deep
learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recogni- tion (CVPR) Workshops, June 2019.
Rajkomar, A., Hardt, M., Howell, M. D., Corrado, G., and Chin, M. H. Ensuring fairness in machine learning to advance health equity. Annals of internal medicine, 169(12):866-87) 2018.
Roth, A. Uncertain: Modern topics in uncertainty quantification, 2022. URL https::/www/ wwww.
cis. www.n. http://.ww..aaatctt//ttaanannoop pdf
Sanh, V., Debut, L., Chaumond. J., and Wolf, T. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter, 2020. URL https: //trx/aavvvvv//////////aa/aaaavl org/ abs/1910, 01108
Tschandl, P., Rosendahl, C., and Kittler, H. The HAM10000 dataset, a large collection of multi- source dermatoscopic images of common pigmented skin lesions. Sci. Data, 511:180011, August 2018.
Wu, J., Liu, J., Cui, P., and Wu, Bridging multicalibration and beyond covariate shift. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024. URL httpt::///// http::::////peeeveeeee www.eewwwwwwweeeneeeeeeeeeeeeeee
generalization
Zhang, L., Roth, A., and Zhang, L. Fair risk control: A generalized framework for calibrating multi-group fairness risks, 2024. Uttpstts:://axxi
02225
Zhang, 7., Song, Y., and Qi, H. Age progresssion/regressionn by conditional adversarial autoencoder, 2017. pottitttss///axxitt http:://awxxxw..ooa///////////// 08423
Zhao, S., Kim, M. P., Sahoo, R. Ma, T., and Ermon, S. Calibrating predictions to decisions: a novel approach to multi-class calibration. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845397
12

---

A Omitted Proofs in Section
We would first provide formal definition of the discretization operation.
Definition A.1 (Discretization Operation). function fm an m-discretized version of a predictor
f if
there exists a monotonic non-decreasing function d on [0, 1] such that d(f(x)) = fm(
d right-continuous on [0, 11, that lim d(x) = d(c), (0,
[R(fm)] = m. i.e. the range of fm is of size m.
The additional requirement on fight-continiig has minimal effect on the algorithm, but is only helpful for the proof of the following lemma.
Lemma 4.2. Consider the post-processing step Pg in Equation 5 For all f E [0, 1] and e and for any m-discretized version fm of f. we have
E(pe(f), e(pe(fmm)))
Proof of Lemma 4.2
Since
& (1+I
())(D))
min
TCT(S LET
we show that Vc > 0, there exists T S C(f,9) such that
s+ E 1D s (ps (fm) .D) +
RET
f Σ 1D - (po (fm) .D))
l
IET
+ Σ 1 - /1 - ED (Ps (Imo) - 11) =)
=Ep
1ET
ED
/ + Σ - pa(sm))
(++Z Σ 1 + pe (Fr)) 2y
IET
NET
ED (1++
27
Ep
Σ po(fm)
Σ
+ (F + 2|/9
IET
FET
<4
En
Σ
pr(mm)
1ET
Thus, it suffices to show that
Vc 0, CT(.
+ Et-po(fm)
S 5//4
(10)
tET
Since pe (fm) Jm Eiero where T' E T(fm: 9), we write
f + Σ t po(Fma) $ f Σ t fm
Σ
+
IET
tET
tET,
13

---

and try to construct Ti, T- g to bound the two terms.
We first show the second term can be zero by showing that T(fm, 9) CT(,9). By Equations and 4). it suffices show that
3
(fm(x)) S((),
Si
(11)
that is,
Ve E [0. 3u E [0.1] s.t. for E X: : 2 2 = fx E f(()) 2 um}
assuming E X fm(()= 2 0) 0
Let
== == min fm( 2 e [0.1
It follows directly that Væ s.t. fm (x) 2 u, f(x) 2 u.
On the other hand, since J' = d(f) for some monotonically non-decreasing d, we have Va s.t. f(x) 2 (x) = d(f(x)) 2 d(u). Since E (f(x) fm()) 2 o} = {v d(v) 2 v}. we have d(u) 2 c. Then {z X: fm (2) 20) fx X: f(x) 2 2) follows directly. This indicates we can construct T-2 TV.
remains to show that
Ve 3, C C(f.9) such that f+ Et- fm
S e/4
(12)
Let ui = min( (x) 2 J where up < ... Um is the range of fi. We partition [0, 1]
into intervals
[0, e0,) (e/2, 2c) .................... [[ e/2,
For each us, we denote n(u)) as the largest integer such that euu))_e/2 S u, We further split the in- terval containing u4 into two intervals (n(u:)+< cc/2, uz) and [u,, (n(u,) ++ ((l))++)-(/))) +1)-c/2). In this way, we par- tition [o, 1] into + -1 intervals such that each interval has size and that U1, ... um can only be the boundaries of some intervals. We write the intervals as (1, /12//4mm- 1 72/e+m-1l
where 1 = 0, 22/e+m-1 1.
We then construct the following trees
G d(l.)
4
4(x) ((0)=I(0 (1)))
0
Σ cj
Ti (1/)//tm 2/e+m-1
2
Then Va, assume f(x) E (R) for some k. Then
f(x) + Σ1(x))
f(x) fm(())
1ET
14 r
f(x) + d(lx))
d(1x)
2
4. + rk
< Fk
lx
((x)
<
2
2
4"
Therefore, we show that Ve 0. 37, S ((f,9) such that +++EEEn t- fm S
'The minimum exists because the infimum belongs the set: in(( (n) 2 v) E (f(z) (m)
v). Recall that there exists monotonic non-decreasing d that's right- on [0, 1]. s.t. (z)
(x)( It suffices to show that yo A inf(y : d(y) 2 o) E {y d(y) 2 v} 2 S. By definition of infimum, An E N", By. E S s.t. yo yn, < + Then lim.. = yo- Since d is right limn-ro d(yn) d(yo). Since d(yn) 2 v. have d(vo) Thus, go S.
14

---

Lemma 4.3. Given a predictor f whose range is size m, training an ensemble of decision trees on f as in the post-pree post-processing step Equation encompasses adding linear function of the groups on each output level set of f. That is,
f+ E [(f(z)=
- (4-
(d (
c GER
}
f+ E 1ET
TETUE
} (7)
where Um E ER()), U1 < 1/2 < < Um
Proof of Lemma 4.3] wh E { E t/} (e' + E. c/a1) | | Je d +
Σ; G.9. Then we can write h as
m Σ
- f
[((x)) = U3 رر
JEL
m
j-1 hy ( h4
f+ Σ
Hf(x) 2 uز}
JEI
m
f+
[f(x)) 2 V/J4i.
JEL
where R2 is still a linear function of gs. Let R/g = d² + E.cig. By Equation 4
vi,j, 2 U3 Jci 9 E T(f.g)
because we can set
=1 = = x: f(x) u--1) fo E x:
c1 =,
And also,
Vj, T 2 ) ET(19))
because we can set
fx (()
= 1)) ===
Thus, vh E { f I[f(z) = 17) (d E, 2.: &&ER.
R }. we have
he f Σ TCT().9) }
IET
Lemma 4,4. If a predictor f with R(f) = {U1, un has a multicalibration error w.r.. G larger than a, then there exists linear functions h, E, dg such that
e(f,)) > f ft uf
+ aa
(8)
Proof of Lemma 4.4
Assume f has the largest calibration error on the k-th group, namely
ls arg max
Σ
Pr [f(x) v, (x) 1] [Baay)> [f(z) y f(x) v. (z = 1] (Ha1)~
+E[|G]]
ve R(F)
Then we let
{- B [f(x) y f(x) = Uy (x() = 1]. if = k;
d
(13)
0
i +
15

---

Let ok =a. Then h2 = ajgh. Then,
((f.) - ff Σ
If uf==, D
SE(|R(SI
Pr [f(x) = RD (f(x) - -)²² [fx) = =ny]
(m.y)/>
+ hy(x) Pr [f()) uIED (f(x)+
8)² f(x) = us] v) +13(0) f(xx) u,]
Pr [f(z) v, LE (2:
Pr [fx) Ug DD (5agnn((()) y) + azyn 1sx)) vy]
m
Pr 99k (z) Σ
Pr
[f(z) = 03 BD (az(f(x) - y) ag f(x) uy (x()) = 1|
(x.y)D
(x,n)~=
j=1
= Pr (ox(z) = 1] Σ (20/D
Pr
[f()) = 52
(a.a)-DD
The final equation is due to aj = -E a.y) [f(x) y f(z)= of multicalibration error, Equation 13 indicates that
)). = 1]. By the definition
Pr [f(x) = = (a.N)~
a
plg (z) ((()))) 1]
By Cauchy-Schwarz inequality we have
((JD)) - s+ Σ užbحeز D
jE((R())
Pr [9x(x)) 11
Pr [f(x)= = =ogla (2.0)D
(ay)D
クラ=1 Pr Pr ((x) =1yla]]
Pr [9x(x)= =1]
a² Σ/1 Pr(z.)) (f()) = 8y]
2 a
(())))))D(9(2)) =1]
B Discussion on the applicability of the algorithm
Our algorithm consistently achieved low multicalibration error across all the datasets we exper- imented with, demonstrating its effectiveness in realistic datasets. However, to the best our knowledge, we could not find guarantee that our algorithm will always return model with low multicalibration error. The main difficulty is to obtain a guarantee that Assumption holds.
On the other hand, it's possible to construct example where our algorithm fails to achieve low multicalibration error. Unlike the above experiments where we post process upon a predictor, the construction uses unrealistic setting where the base predictor outputs constant value. Assume
16

---

the goal is to obtain multicalibration w.r.t. three binary groups, namely g(x) E {0, with 9:(z) wap. 0.5, and gi being independent. The ground truth y(z) is given by
-1 7) ( (20(1) 1 )22(2) + gos(x))
y(œ) =(1 -(1->)
+ (x) + g2(x) @ ga(x)),
where y E (0, 1) a constant and @ denotes the XOR operation. Note that the base predictor is constant, loss minimizer given by algorithm is
f(x) - (1->) (0)) (foo))))
1 f02(s) + { 2'
?
as ensemble of decision trees of depth 2 will never be able capture the XOR operation. The
first term makes sure that f(x;) # f(x;) whenever g(x;) + g(x;), leaving multicalibration error
Σ
Pr [f(x) - (,);(z) = (2.0)/
vER(S)
[( (f(x) - [(x) = = = 1]]
Σ
Pr
-10)= = =1]
(2.0)~D
VE R(f)
In this example, E(J = /4, and since (ax outputs a different value for different value of ( running algorithm second time gives zero-error pc) y(x), making closs 72/ /4. This large improvement is a violation of Assumption 4.5 which explains why the algorithm is not able achieve low multicalibration error in this case. This is mainly due the lack information in the base predictor, rendering the ensemble less useful. Again, we emphasize that this is construction often unrealistic we usually have non non-trivial base predictor that gives meaningful prediction before we seek to calibrate it for fairness or robustness across distributions.
C Implementation of the trees in established tree-ensemble solvers
In Equation we defined the set of trees T of our algorithm, where we require that each tree splits on single threshold and single group. However, this might not be what solvers like Ke et al. (2077) and Chen & Guestrin (2016) implement. In fact, with fo(r) and given as the input, depth-2 trees in those solvers are given by
T' 9) = far Txx A 02 Hi E Ax & 82) + es T(x & 81 Ax E 8s)
(14)
+ c4 11x 81 Az 8e)
cn, 02, c3, c4 R, 82, E (1))
where S₁ and S2 are the same as Equation still hold for such implementation.
We want to show that our arguments in Section
From Equation 14 we see that C T'. If is substituted by T', Lemma 4.2 would still be valid, as guaranteed by Equation (1) and Equation (12). which still hold for the expanded set T'. Lemma would still be valid as well, as
{ |
GET (ET(T))))))
+ }
TCT(F
TCT((9))
IET
Lemma 4.4 does not involve the definition T. Therefore, the analysis in Section applies to these established solvers.
D Description of Datasets
In this section describe the datasets we use for evaluation the proposed method.
17

---

Table 4: The number of groups defined for the ACS dataset.
Number of groups defined on the attribute
Attribute
Income Regression
Income Classification
Travel Time Regression
Race
5
Gender
2
2
Age
5
5
Education
6
6
6
Occupation
30
30
33
Total
48
48
51
D.1
ACS Dataset
The American Community Survey (ACS) dataset a public dataset that contains demographic in- formation about the US population, and can be accessed through the folktable package (Ding al. 2021). In this work we consider three tasks using data retrieved from this dataset, namely Income Regression, Income Classification, and Travel Time Regression. We used the subset of the 2018 census data California.
Data preprocess Folktable already defines the features associated with each task and pro- vides a preprocessing filter that extracts set of reasonably clean records. We used the provided filter to preprocess the data. Additionally, for income regression task, since the income has a long tail, scaling the income value to [0, would lead to a large mass of data points around 0. As imple- mented in Globus-Harris et (2023), we filter out the data points with income higher than 100,000 and scale the income to [0, 1.. Travel time regression does not have similar long tail, so we directly scale the travel time [0, 1].
Dataset partition and the uncalibrated base predictors Given the features provided in Folktables that does not contain nan features, we fit a linear regressor for regression tasks and linear SVM model for classification tasks using randomly sampled 50,000 data entries, Apart from that, we set aside 12,000 data entries for the test set and 18,000 entries for the calibration and validation set.
Groups In order to create rich set of groups, construct the binary groups using the five at- tributes in the dataset: race, gender, age, education and occupation. We transformed the categorized features into one-hot encoding. Specifically, we used age groups instead of the numerical age, and we categorized the occupation by the first two digits of the occupation codes. For each category, as long contains more than 1% of the data, we accept 50 groups for each of the three tasks. (See Table 4
group. In this way, defined around
D.2 CivilComments Dataset
This dataset came from the WILDS Kataset(Koh et al.) 2021: Borkan et al. 2019) which collected 447,998 comments labeled by crowd workers. The task is predict whether comment is consid- ered toxic or not.
Dataset partition and the uncalibrated base predictor Koh al. 22021) partitioned the dataset into train set (60%), validation set (10%) and test set (30%), and provided baseline predictor. We set aside one-sixth of the training set and combine it withe validation set for calibration and validation. As for the base predictor, also followed the training of the baseline algorithm in the original paper and trained a DistilBERT (Sanh et al.) 2020) model using the same specified hyperparameters and settings.
Groups Koh et al. 202 provides eight predefined groups based on the identity terms mentioned in the comments, namely male, female, LGBTQ, Christian, Muslim, other religions, black, and white. We use these groups for the multicalibration evaluation.
18

---

D.3 UTKFaae Dataset
The UTKFaae dataset (Zhag et al. 2017) consists of 23,707 face images with annotations of age, gender and race, ranging from I to 120 years old. We use the dataset for the age regression task.
Dataset partition and the uncalibrated hase predictor We used 40% of the data for training, 40% for calibration and validation, and 20% for testing. The base predictor was trained on the training set with a ResNet-18 model for 30 epochs with early stopping enabled.
Groups
We defined 16 groups (2 for gender, 5 for race, and for age) on this dataset.
D.4
ISIC Dataset
The International Skin Imaging Collaboration (ISIC) dataset is public dataset that contains images of skin lesions together with patient metadata and diagnosis label. We use the data provided in the ISIC 2019 challenge Tschandl
challenge[Tschanl et al. 2018 Codella et al. 2017 Combalia et al. 2019). The original
task classify the skin lesion images into one of the seven categories, and we consider the derived binary classification task for predicting the category NV, which accounts for 50.8% of the dataset.
Dataset partition and the uncalibrated base predictor Since the test labels not made public, we only use the 25,331 training images. The images in the dataset come from three sources: 49.0% al. 2019), 59.5% from HAM (Tschandl Codella et al. (2017) or other sources. We use the 12413 BCN images as the training set for the base predictor, three-fourths of the HAM images (7511 images) as the calibration and validation set, and the remaining 5407 images as the test set. The base predictor was trained on the training set with a ResNet-18 18 custiiclassification model for 20 epochs with early stopping enabled. The predicted probability of the category NV was used as the base predictor output.
from BCN (Combalia
al., 2018), and 11.5% from
Groups The ISIC challenge provides metadata, which includes approximate age and gender of the patients as well as the anatomy site. Just like in the ACS dataset, we consider a category as a group if it has at least 1% of the data. In total 14 binary groups (2 for gender, for anatomy site, and 7 for age) were defined.
E Details of calibration algorithms
In our experiments, we fix the uncalibrated base predictor and the test set and introduce randomness by partitioning the remaining part into an equal-sized calibration and validation set 10 times. After finding the best hyperparameters choice of hyperparameters and report the performance on the test set. For LSBoost and MCBoost, since the number of level sets m needs to be determined calibration time, we sweep over the hyperparameters on the ten folds for all 6 level sets we evaluated, namely {10, 20, 30, 50, 75, 100), and choose the best hyperparameters for each level set.
the 10 folds, calibrate the base predictor using this specific
We now introduce the algorithms' implementation detail and the hyperparameters involved:
Multiaccurate Baseline
It's been shown in Roth (022) that a linear model with & regularization guarantees multiaccuracy. We use the binary groups as the feature and sweep over the regularization strength À in (0, 10-6, 10-5,..... 10-2)-
Our algorithm works pretty much out-of-the-box by passing the uncalibrated prediction, the groups and the ground truth to the Light GBM et al. (017) solver. To avoid the complexity of determining the optimal number of trees, we use early stopping with patience of 50 iterations and set high maximum limit of 5000 trees. 30% of the calibration set is set aside during calibration to monitor the loss continues to decrease, and this is different from the validation set, which is solely used to tune the hyperparameters. In other words, given set of hyperparameters, the calibration set the only data that is used, though internally, only 70% of the calibration set is used for learning the parameters. The depth of each tree is two, indicated in the main body. We vary the learning rate across five exponentially spaced points from 0.01 to I and adjust the feature subsampling ratio linearly across 10 points from 0.1 to 1.
Ours
19

---

LSBoost LSBoost is introduced in Globus- Harris et al. (2023), and we used the implementation provided by the authors, with minor modifications in the multiprocessing implementation and round- ing the output to the 1/m grids. Unlike the algorithm described in the original paper, the authors also implemented early stopping in their code base, and for better performance, this also enabled in our experiment with 30% of the calibration set as described in the previous paragraph. Considering that our algorithm uses decision trees depth as the weak learners, we experimented with trees of depth both I and 2 during hyperparameter sweep. Other hyperparameters include the learning rate, which can 0.1, 0.3, or 1, and the subsampling ratio for the weak learner, which adjusted linearly across 10 points from 0.1 to 1. In total, 2 x 3 10 60 hyperparameter combinations evaluated on all ten folds and all six calibration level sets.
MCBoost We implement the algorithm described in Roth (2022). which is variant of the prim- itive multicalibration algorithm proposed by [Hebrtt-Jhhnon et al. (2018). This algorithm doesn' t involve any hyperparameters, but it's known that it can be prone overfit, proportion of the calibration set for early stopping. We consider this proportion as a hyperparameter, and swept over the values {0.1, 0.2, 0.3, 0.4, 0.5}. Like LSBoost, the hyperparameters evaluated on all ten folds and all six calibration level sets.
also set aside
The uncalibrated predictors for the image text task were trained on an A A100 GPU or an RTX 4090 GPU. Other predictors, as well as the calibrators, were trained on an AMD 64-core CPU. Running all the experiments takes approximately 6 hours.
F Statistical Learning Guarantees for Tree Ensemble Optimization
In Section 4 we established a theoretical framework that connects multicalibration error with loss, demonstrating that when decision tree ensembles achieve effective loss minimization, the multical- ibration error can be bounded. However, in the finite sample regime, there would be an additional excess risk term due to the empirical (instead of distributional) loss minimization. This section extends our analysis, examining how finite sample affects these theoretical guarantees.
Recall that we constructed the trees in the ensemble using the splitting criteria defined in Equa- tion
E fo(x) 2 20) )
(1h)) =
U
(VER(fO)U(O)
S2(9)
U f g((x) = =1} 11
11
Each tree in T(fo. 9) can be formally written as
C1 1fx E 51 Axr E }2} + 02 11(x E 81 A x & 82) + c3 12 $ 81 A E 82) + + -xx $ s1 A $2)
where $1 E S (fo). and 82 E S2(G). Here we can require c2 C3, c1 E [-1, 1), because the ground truth label is in [].
As shown in equation [ the post-processed predictor obtained by solving
(fx fu+t) Σ t,
arg min po
TST TCT(
1ET
With only a finite number of samples, the excess risk measures the discrepancy between the loss of the empirical predictor Po (ffu and the optimal one on the distribution pa (fo)
Eaacess (po(fo), D) (po(fo),
With this term, the multicalibration error a in Theorem 4.6 would change to be
v VEose Eround Ceacess
20

---

Closs only depends on the distribution, and is assumed to be small according to Assumption 4.5 We also do focus on the case where the rounding error Ground dominates neither. In this section we try to derive bound on the excess risk fercess by analyzing the convergence and the generalization of loss minimization on our ensemble. We then try provide an asymptotic analysis of how many samples are required to achieve target multicalibration error by considering a (f
F11 Loss minimization in practice
Loss minimization is typically done through adding trees to the ensemble
Po (fo) arg min e TCT(So.)) 1 I
LET
In practice, typically limit the number of trees added, namely the size of subset T, by setting maximum limit or through early stopping. This keeps the running time of the algorithm reasonable, and balance optimization error reduction against model complexity. This motivates the intro- duction of a parameter Nr to represent the maximum number of trees in our ensemble. We define the function class FNy that empirically optimize
T1
FNz
So
Σ
4 n NT, 4 (T)..))
F.2 Rademacher Complexity of FNT
The generalization error increases as Ny increases and as the model becomes more complex. We use the Rademacher complexity to quantify the complexity so as to bound the generalization error using the number of samples, the number of trees, and the number of groups We first recall the definition of the Rademacher complexity a class of functions
Definition F.1. For hypothesis class and sample size n, the Rademacher complexity R., (H)) is defined as
RA (H) = Bo,s(ssi sup hEH
Σ o,h(1,)]
where = {01, 22,1,22-00 22,,.., In. is a sample of n points drawn i.i.d. from distribution D, and 00..02...,, ) are independent Rademacher random variables (taking values +1 or -1 with equal probability).
We now state several key lemmas that will be used in our analysis. These lemmas are standard results in statistical learning theory and can found Mohri al. (2018).
Lemma F2 (Massart's Lemma), Let A Rm be a finite set, with maxxE [|||, then the following holds
m
rV 2og A
Eg
sup Σ 0.00 m
m
where a,s are independent uniform random variables taking values (-1,+1) and T Z1.... Fe the components of vector
Lemma F.3 (Talagrand's Contraction Lemma), Let H be a class of real-valued functions. If 6 RR is Lipschitz function with Lipschitz constant L, then
n
E
sup NEH
Σ
(,0(((2)))
L.
sup heet
Σ o,
Lemma E.4 (Sum Rule). For any two hypothesis sets and H'' of functions mapping from X
Rm (H H²) Rm (H) + Rom (H')
where H. + H' (h + N/ he H, h' E H'} } is the class.
21

---

To analyze the Rademacher complexity of our tree ensemble function class FNy, we begin by ana- lyzing the components that make up our trees. We introduce the following auxiliary function classes
Fi [I(x E Har & si 81 E (:u))):: the set of threshold indicator functions
1fz E s1} [[f((a) 2 of for R(fo) U {0} and their complements 1{ & $1
1(f(z)) <z}
J/ - [1{2 E 82) 1r & 82)
82 {2 the set of group indicator functions 1f
82) = (x) = 1 for i E [ and their complements [1 & 82) = (()((a)) = 0}
We proceed through the following steps
Lemma F.5. For the threshold indicator function class Fi = {1f E s11,1 $ $1 s1 E Si(fo)}, the Rademacher complexity is
Ra (Fi) = =(n -1/2)
Proof. Let S = f.i..... Fnd be sample, and let oi...., nn be Rademacher random variables. Consider the values ...S ffo(
(..) and rearrange them in non-decreasing order as fo( S
For any threshold R(b) U (0), there exists a k {0, 1.....,n} nf such that (()o(()())) 2 v} for i >> l and (())(z()) 2 v} for i S k. Thus,
Co.Ifo(E.) 20
Σ
(
i=k+1
where (() is the Rademacher variable corresponding to z(()-
Similarly, for the complement indicator
Σ (Tl())) < Σ 1
Therefore
sup EEA
fxi) = max
max OSSSn
(
max osksn
Since the Rademacher variables symmetrie, both terms have the same distribution, and we have
E
sup fEFi
-
1
E.
Σ
T
n
OSASn
We now need to bound E, Imaxogkgn inequality, for any À
Σ Till. Let S = Ek or. Using Doob's martingale
S X2
S
osksn
X2
Using the formula for the expectation of non-negative random variable
E
max
|S&||
P
max Oskkm
Syl 2 t
dt
OSkŠR
n
min
L,
dt
0
(2
Vn
n1
1dl. +
dl
12
10
Vn
(-7)
= Vπ+ + Vπ= 2
22

---

Therefore
Er
max USASn
0i
S
2nn
i=1
And
1 R2 (Fi) B,
2 2/n
2
Σ 03
max OSksn
n
Vn
Lemma F.6. For the group indicator function class F2 {Ifx E s2),1{r $2) |s E (2))),, the Rademacher complexity is
(2) =0 10g(19)) (G))
(V
72
Proof. We prove by applying Lemma F.2 (Massart's Lemma). We first identify the set A and com- pute the parameter in the lemma.
Let S = (21 .. be a sample. For each function f F2, we can represent it as vector
X (f(x1) f f*x)) [0, C R". Let A= = {xy : f E F22 be the set of all such vectors.
Note that |A| |F22 S 2| since F2 consists of at most [ group indicator functions and their complements.
Fo A. since f(x;) (0, 1} for all i, we have
||xs||2
Σ [xx)}²
Σ f(x;) S vn
1
Therefore, r = maxxed
|xx|2 S Vn.
By Massart's Lemma
1
< I'V 2og A
Eg
sup n xE.A i=1
0g
vn. v (2
lo (2
Vn
log((g))
n
By definition, this expectation precisely the Rademacher complexity (F),,), thus completing proof.
Lemma F.7. For the product class consisting of all possible products of indicators from F1 and Fg. denoted as Fi @ F2 {fi fa fi F1, F2). the Rademacher complexity is
(V
[og(((())
(T(FFF))=
n
Proof. For any f1 E Fi and f2 E F2, we have the identity
fi f2 2 ((i
f2)² 8 121
23

---

Therefore, the product class Fi @ F2 is a subset of
(F F2) (-1) F2). where F² = (f if and (Fi F2) + f2) : F1, F2). Using the properties of Rademacher complexity. we can obtain
R₂ (Fi 0 F2) S - Rn
By Talagrand's Contraction Lemma, for the squaring operation (which is Lipschitz with constant when the norms of the function output are bounded by 1)
F2)²) 2 (F - F2) = (R) - (F)(
Similarly,
R- Rn(FF) 2 (F2
Substituting these bounds give
1 (2)n R, (Fa)) + (R)( + 2R, (F2) (R) + 2R, (F2)
(R. 2 F2) S
Given that Rg (Fi) 1/2) and R, (F22 O (lvlog((9))/m) when [ > 1, the dominant term is R2 (F2). Therefore.
(v log(1g])
RA & F2)
12
Proposition F.8. The Rademacher complexity of the tree ensemble function class FNy bounded by
log(19))
RA (N(x))= =0 NNV
Proof. First, consider the Rademacher complexity for the class of trees with 4 leaves, denoted as (). Each tree in T(fo. 9) can be expressed as a linear combination of indicator products, corresponding to the leaves
C1 1|x E 81 AIE 52) + 02 1(x E s1 A & 22) cs 1a s1 Ax 82) + 1xx & s1 A2 82)
Let Hi (c 11 E si A 82) S1 E Si(o), s2 E S2( ei E []], and similarly define Ho. H3. and H4 for the other terms. The indicator products like I(r E si Ax E 82) are elements of Fi @ F2. By Talagrand's Contraction Lemma (Lemma F33 since the coefficients e; [-1, 1]. they are bounded by Cmaz = 1. The function 6(h) = c h for a fixed c [-1, 1] is Lipschitz with constant |c| < Therefore, for each term j {1,2, 3,4]
R, $ Rs (J (F F = (oog(199)
(
Since we can write
Nr
FN, = (f6) Σ
(Hi + Ho + Hg H4).
and the Rademacher complexity of singleton set is O, we can repeatedly apply Lemma F4 to obtain
Rr, Nr (1 (1OoR((9)
log (())
o (NT
n
72
This completes the proof.

---

F.3 Optimizing over FN, and its Convergence Rate
As Nr grows larger, more trees are added, which enables more accurate optimization of the loss. We calculate the convergence of the tree ensemble as Nr increases by analyzing the convergence rate the optimization algorithm used to construct the tree ensemble.
Although LightGBM is often a practical choice for minimizing the loss and is used for our experi- ments, do not restrict ourselves to any solver in Algorithm i Section 4 For the purpose of this convergence analysis, we will analyze an alternative algorithm, SquareLev.R, introduced by Duffy and Helmbold Duffy & Helmbold (2002). All results and algorithm details in this subsection are derived from their work.
Like LightGBM, the SquareLev.R algorithm is a boosting algorithm designed to iteratively reduce the squared loss. It achieves this by minimizing the variance of the residuals at each step. The residual for sample æ; at the beginning of step is defined
(k-1) yi F
where (x; is the prediction of the ensemble after k 1 base learners have been added. The minimization of the variance of the residuals aligns with the purpose of loss minimization, as they equivalent up constant shift of the predictor.
Algorithm 2 SquareLev.R Algorithm Duffy & Helmbold (0002)
1: Input: A sample S ((11,31) (12, v2)...., (m vm)] base learning algorithm, and pa-
rameters p. Tmaz
2: Set (xx)) < 1/m and L
3: Initialize master function F1 to the zero function
4: for i 1 to do
5: Ti <- P1 (x:))
D Initial residuals, effectively r()))
6: end for
7: while ||r F 2 mp and < T Tmaz do
8:
1+1
9:
for i = to m do
0 < r; m Σ,
end for
12:
S" + {(11, Ø1),... (mm. }m
Call base learner with distribution D over S", obtaining hypothesis
((-r) f) frlllallf-
14:
E
-1lr-112 02 Ff-1112
15:
16:
Fl < Fi-1 + arf
for
i 1 m do
18:
F3 f yi (x2))
19:
end for
20:
end while
Output:
The pseudocode for the SquareLev.k algorithm is presented in Algorithm 2 Based Theorem 4.1 and 4.2 from Duffy & Helmbold (2002), we can characterize the convergence of the SquareLev.R algorithm using the Pearson correlation (also referred to the "edge" in weak learning) between the residuals and the base learner output, specifically the e term
Proposition F.9. The variance of the residuals is reduced by factor (1 (1 during step k. in the Squarelev.R algorithm. the edges of the weak hypotheses used by SquareLev.K are bounded below by Emin O, then the variance of residuals after NT steps, then the variance of residuals is bounded by
Var(x!Nr)) & Var(r )1 2 Nr.
Since the squared error shifted ensemble equivalent to this variance of residuals, this implies similar exponential reduction in the empirical loss.
25

---

F.4 Combined Analysis and Sample Complexity
We now combine the Rademacher complexity analysis with the convergence rate results to establish the sample complexity for achieving a target multi-calibration error.
Theorem F.10. With a samples taken i...d. from the distribution D, the excess risk of minimizing the loss on the ensemble SNr by running the Lev. algorithm for Ny iterations is bounded with probability 8 by
N (og((G))
log(1/5)
O ((1 mm))) O
+0
This result follows from combining the optimization error (governed by the convergence rate of the empirical loss) and the generalization error (governed by the Rademacher complexity).
Given that the multi-calibration error is bounded by the square root of the true expected loss closs (as stated in Theorem (.6)) to achieve multi-calibration error bounded by we require that this true expected loss be bounded by a². This leads to the following corollary Corollary F.11. If the number of trees NT and the sample size should satisfy
Nr = O (Emin log(1/a))
and
n= Ω2 (a (a Eyin log( (G) (1/o(1))) +a log(1/)))
(1/ai)
minimizing the loss on ensembles defined Equation (5) by running the SquareLev.R algorithm for NY iterations using n. samples taken i..d. from the distribution '' gives a multi-calibratonn error less than with probability 6 when the discretization error is small and Assumption ho5ds.
Proof. For the multi-calibration error to be less than a, we need the empirical risk, as bounded by Theorem F.10 to be S a². We aim for each of the three terms in the bound to be O(a²). For simplicity in balancing, let's set each term to be S Ka² // for some constant K.
For the first term (empirical optimization error)
Ka²
2 Nr
3
taking logarithms and using the approximation log(1 x) S - for gives
2 log(L/a) log log(K/3) 0 (emin log log(1/a))
Nr
e
For the second term
log(19)
Ka²
Nrv
substituting Nr = O log(1/a)) gives
n Ω (a 4 emn log 2ogg (1/a) log(19)))
And for the third term
log(1/8) Ka²
<
3
solving for gives
n = S (a (og(1/5))
Combining these constraints on n, the overall sample size is determined by the sum of these require- ments
== Ω (ax - -m (og(()) log" (1/x) + (log(16)))
This completes the proof.
L
Corollary F.11 provides clear guidance on the relationship between the desired multi-calibrattin emor a. the number of trees Nr, and the required sample size to ensure the true expected loss is sufficiently small. This indicates that, even when we only have finite samples, the main conclusion still holds.
26

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not re- move the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes]. , [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiiatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evalu- perfectly acceptable answer "[No]
ation. While "[Yes] " generally preferable "[No] provided a proper justification is given (c.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NearIPS Paper Check- list".
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have clearly outlined the contributions and the scope the end of the introduction and in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Ys]]
27

---

Justification:
See Appendix B for a discussion of Assumption 4.5 sumption empirically across wide range of datasets, and provided an unrealistic coun- terexample.
We validated the as-
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
See Section 4 for the assumption, and Appendix A for the complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
28

---

Justification: We provided the experimental setup in Section 5 and detailed specifications in Appendices D and
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. Releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We made public the code, the results and the instructions reproduce them at https: // com http:/cco.chhhhheeeeeeeee hww.eeenniiiiiieereteeeeee liztiionn f All packages and dataset we use are publicly available, and the download link provided in the link as well.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nt /tte:://ipsscooo
pub public//an guides/ gwwids///oeeeuieeeeeeeeee
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: 7/n 7/nips.on cc/ppbl c/ wtw.:/giessseeee wtw.ddeeee//ooSSuoobomo as ionPol 1 icy) for more details.
29

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provided the detailed experiment specification in Appendices D and
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We repeated our experiments 10 folds and reported the mean and standard deviation either using error bands (in figures) or the values (in tables).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
30

---

Answer: [Yes]
Justification:
We specified the compute resources at the end of Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://s////eueupsssccoo httpu//pp...coo...c//aaaooo.eee.
Answer: [Yes]
Justification: We not identify any harm in the research process and does not anticipate harmful impact.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
We discussed broader impacts in our conclusion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
31

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not provide novel datasets nor pretrained models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited all the datasets we use in Appendix D and the algorithms we use in Appendix E
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, [paperswit wwwwthhood thoode com/ datasets] has curated licenses for some datasets. Their licensing guide help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
We have released any assets this moment.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the datasettcooe/mmodll part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
32

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non standarad components.
Please refer to our LLM policy httttp:///neurisscc///como
2025/LLX for what should or should not be described.
33


Reviews:
[{"review_id": "sSLVvjJ6dP", "reviewer": "Reviewer_3K17", "summary": "This paper tackles multicalibration without the discretization step required by prior methods. The authors proposed a simple one short learning algorithm that fits a LightGBM with depth 2, which effectively models the interaction of base predictor and the grouping indicators. They also proved that, if the learned ensemble is ”loss-saturated”,  then the multicalibration error is bounded. Empirically, across 6 datasets, the method has the lowest worst group smECE in general compared to baselines.", "questions": "Questions:\n\n1. Could you comment on how the algorithm behaves when relevant sub-groups are not explicitly encoded? How sensitive is it to “hidden” groups that fall outside of the provided indicators?\n2. Have you experimented with tree depth greater than 2? Could deeper trees help capture interactions among explicit groups and extend to a broader group family? \n3. Are there any empirical details on the number of boosting rounds you used, as well as that used by LSBoost, at the same tree depth? I think comparing the number of round convergence of “one-shot” and “recursive” algorithms is quite interesting.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper developed a novel technique that got rid of the discretization step widely used by previous methods.\n2. This paper used a single Ensemble tree fit to capture the interactions between the base prediction and group indicators, which is concise and easy to implement.\n3. The empirical evaluation showed improved performance across 6 datasets over existing approaches on multicalibration error and worst group smECE.\n4. The paper is well-written with theoretical justifications.\n\nWeaknesses:\n\n1. Unlike LSBoost that calibrates with respect to a function class, the method this paper introduced only guarantees the application to pre-specified groups. The method could suffer from unspecified important subgroups or high-dimension grouping structure.\n2. Section 5.3.2 reports the discretized version of the proposed predictor, however, the author doesn’t show the undiscretized version, but only showed the worst group smECE in Section 5.3.3 instead. I understand that comparison in 5.3.2 is already fair, but adding the undiscretized version would give readers a more complete picture of practical performance.", "was_revised": true, "final_justification": "All the main concerns are solved. W1 is partially addressed and could be an interesting further direction.", "rebuttal": "We thank the reviewer for the careful review, and we’re happy to answer the questions raised by the reviewer.\n\n1. On the binary group features\n\n    As pointed out by the reviewers, LSBoost extends the binary groups to a function class that is closed under affine transformations, while currently, we do not fully support such a function class. This extends the scope of our algorithm beyond group fairness, and we intend to leave this for future investigation. We’ll also discuss more about this in point 3.\n\n2. On the evaluation in section 5.3.2\n\n    We’d like to point out that the metric we use in 5.3.2 is the Multicalibration Error in Definition 3.2, which only works with discretized predictors. Therefore, it’s not possible to directly calculate this metric using the undiscretized version of the predictor. Indeed in practice, there may be other metrics that practitioners might be interested in, and we provided a smooth indicator of multicalibration in Section 5.3.3. For other practical metrics beyond multicalibration that works on continuous outputs, we reported the accuracy and loss in our response to Reviewer zBZu, and we kindly refer you to our answer there.\n\n3. On the behaviors of hidden groups, and extensions to deeper trees\n\n    This is a great question! While we cannot guarantee performance on general unspecified \"hidden\" groups, it might be possible to extend our approach if these groups are assumed to have certain structures, which include:\n\n    - Intervals on continuous features. Trees can learn to take thresholds on continuous features, and two trees of depth one on some feature can represent an interval on this feature. If we assume that there are some unknown sensitive groups that can be represented by intervals on some continuous feature, ensembles of trees of depth 2 could still learn to be multicalibrated wrt to that group. \n    - Intersections on identifiable groups. If hidden groups are intersections of existing binary indicators or continuous feature intervals, then using trees of depth three instead (one level for $f_0$, two for group intersections) could enable multicalibration for these composite groups.\n\n    Note that the tree ensemble will try to be multicalibrated w.r.t. all possible groups in this manner. For instance, the continuous age feature can be passed if we want the model to be multicalibrated to all age intervals. It's important to note that explicit group definition is generally preferable when possible, because extending to these complex structures increases model complexity, potentially leading to decreased performance due to bias-variance trade-offs. For instance, using depth-3 trees requires multicalibration with respect to all sets described by intersections of groups, which is a much more challenging task.\n\n4. On the empirical details of the number of trees\n\n   We evaluate the number of trees of our best performing model on each task, averaged over 10 folds, and present the result in the column “Ours”.\n\n   As for LSBoost, in most of the cases, trees of depth 1 performs better than trees of depth 2 as a weak learner, and these cases are removed from the evaluation. We record the number of refinement rounds of LSBoost as well as the total number of trees used in the remaining cases, and present the results in the column \"LSBoost\".\n\n   Table: Number of trees used for each task.\n\n   |                                   | Ours           | LSBoost                                              |\n   |:----------------------------------|:---------------|:-----------------------------------------------------|\n   | Skin Lesion Classification        | 423.9 ± 97.5   |                                                      |\n   | Income Classification             | 830.8 ± 133.4  | #Grid = 10: 64.2 ± 13.5 trees in 17.6 ± 4.5 rounds   |\n   |                                   |                | #Grid = 30: 441.9 ± 83.1 trees in 58.5 ± 16.0 rounds |\n   | Comments Toxicity Classification  | 558.0 ± 103.3  |                                                      |\n   | Age Regression                    | 2496.1 ± 677.5 | #Grid = 20: 94.9 ± 14.0 trees in 8.9 ± 1.4 rounds    |\n   |                                   |                | #Grid = 30: 90.3 ± 30.6 trees in 7.0 ± 1.9 rounds    |\n   | Income Regression                 | 1201.3 ± 171.4 |                                                      |\n   | Travel Time Regression            | 108.2 ± 48.7   | #Grid = 10: 36.0 ± 32.2 trees in 15.0 ± 12.6 rounds  |\n   |                                   |                | #Grid = 30: 11.6 ± 6.0 trees in 6.2 ± 3.0 rounds     |\n   |                                   |                | #Grid = 100: 8.0 ± 3.8 trees in 4.6 ± 2.8 rounds     |\n\n   The number of trees actually varies a lot across datasets, but in general, our models consist of more trees."}, {"review_id": "JphTSOuSv3", "reviewer": "Reviewer_sZFF", "summary": "The paper proposes a novel multicalibration algorithm that relaxes the discretization preprocessing typically required in existing multicalibration methods. The theoretical results hold for any Discretization Operation as defined by the authors. The core idea is to use depth-two decision trees trained via empirical risk minimization (ERM). Under the loss saturation assumption, the algorithm achieves multicalibration guarantees.\n\nTo demonstrate its practicality, the authors conduct empirical evaluations on multiple datasets, showing improved performance over existing multicalibration algorithms.", "questions": "In Figure 2, what exactly is meant by “different discretization”?  What is the significance of using different discretizations in this plot?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The method generalizes previous approaches by relaxing the discretization requirement, enabling application to a broader class of discretization strategies.\n2. The use of simple depth-two decision trees enhances both practical usability and interpretability.\n3. The paper is clearly written and easy to follow.\n\nWeaknesses\nThe loss saturation assumption is essential to the theoretical guarantee. While it often holds in practice, the authors provide a specific counterexample where it fails.", "was_revised": true, "final_justification": "The authors have fully answered to my questions.", "rebuttal": "We thank the reviewer for the careful review. We are happy to respond to the question raised by the reviewer.\n\nBy discretization we mean restricting the codomain of the predictor to a discrete set, and a different discretization means a different codomain. For uncalibrated baseline, multiaccurate baseline and our algorithm, it's done by rounding the real-valued output to the nearest value in the codomain; and for LSBoost and MCBoost, it's done by setting the hyperparameter of the algorithm before running it.\n\nWe vary the discretization for these two reasons:\n\n1. Evaluation requirement: Multicalibration error, as defined in Definition 3.2, can only be computed for predictors with finite output ranges, so even our continuous predictor must be discretized for evaluation purposes. This metric can be sensitive to discretization, so we vary it for a more robust evaluation.\n\n2. Practical significance: Different downstream applications may require different precision levels or thresholds for decision-making. Varying the discretization strengthens the point that a single trained predictor maintains low multicalibration error across various discretization schemes, making it more flexible for diverse applications without retraining."}, {"review_id": "zIQjXJzttV", "reviewer": "Reviewer_Wact", "summary": "The paper proposes a new multicalibration algorithm which does not require specifying the granularity of the level sets at training time. This is because the algorithm works by finding a subset of decision trees (on particular features such as group membership / prediction thresholds) which minimize the squared loss. This stands in contrast to most previous iterative-patching style algorithms.\n\nThe main theoretical result is a statement on the multicalibration error achieved by the post-processing algorithm. In particular, assuming that the post-processing algorithm does not improve the loss by much, and also that the discretization error is low, then the multicalibration error is also low.\n\nFinally, experiments are conducted in comparing the proposed post-processing algorithm to LSBoost and MCBoost, two previous multicalibration algorithms.", "questions": "I had some questions on the evaluations run in the paper.\n1. When reporting the results of the uncalibrated baseline, is the baseline predictor trained on the entire train + calib set, or just the train set? The reason I ask is because Hansen et al. argue that we should evaluate mcb post-processing algorithms w.r.t. the baseline which uses all available training data (since that is what a practitioner would probably try first).\n2. Similarly, it seems that the baseline DistillBert model for CivilComments used in the submitted paper seems quite weak. In particular, Hansen et al. seem to use the same groups and model architecture, and achieve a much better baseline worst-group smECE of around 0.06 (compared to the 0.119 reported in this paper). Therefore, all multicalibration post-processing algorithms “appear” less useful, since the baseline is already so good. Improving the baseline model may decrease the gap / improvement between standard mcb post-processing methods and the proposed decision tree ensemble approach. (If you are struggling to improve the worst-group smECE of the Distilbert model, one tip is to leave it training for longer!)\n\nI think that these are minor quibbles given that the proposed post-processing method seems to clearly improve on the tested baselines. In particular, the fact that one could get better baselines in certain regimes --- say, for the experiments with NNs --- does not detract from the overall results or message, which holds for all model families, including simple models on tabular baselines.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I previously served as an emergency reviewer for this paper (and hence, re-used the summary above). \n\nIn my opinion, the most important strength of the paper is that the multicalibration post-processing algorithm it proposes seems to be extremely effective (conditioned on the evaluations run by the paper).\n\nAt the time of my previous review, my main concerns / weaknesses were the following:\n\n1. Motivation for focusing on the “discretization-free” approach of the paper.\n2. Not evaluating worst-group calibration error within the experiments, which is a natural metric that practitioners may be interested in.\n\nThe first point (1) seems to be better addressed in this version of the paper. In particular, the second paragraph of the introduction motivates why one would want to get rid of the multicalibration discretization parameter with five concrete reasons:\n- Introduces rounding error which leads to prediction distortion\n- Adds a (sensitive) additional hyperparameter to model tuning\n- The parameter introduces a bias / variance tradeoff\n- Instability under different parameter choices\n- Downstream decision makers with different utility functions may not get predictions with enough granularity in order to make a correct decision.\n\nI think all of these are reasonable and effective motivations to get rid of the discretization parameter, and hence, I feel point (1) is no longer a major weakness of the paper. I would appreciate additional citations for the first and fifth bullets if possible!\n\nThe second weakness I had, point (2), also seems to have been addressed. In particular, the paper evaluates on the worst group smECE in Table 2, where they show that their proposed post-processing method outperforms all other baselines. In the prior version, the paper evaluated on the multicalibration error of a rounded predictor, which was a bit of an odd metric to evaluate on.\n\nSince both of the major weaknesses were addressed, I am happy to advocate for accepting the paper.", "was_revised": true, "final_justification": "The authors answered the few questions I had. The work remains a strong contribution to the empirical multicalibration literature, and may eventually become the de-facto multicalibration algorithm for practitioners.", "rebuttal": "We thank the reviewer for the careful review. We are happy to respond to the questions raised by the reviewer.\n\n- On the dataset partitioning for the training of the baseline:\n\n  Indeed, our uncalibrated baseline models were trained only on the training set, not on the combined training + calibration data. While training a separate model with the combined dataset may decrease the performance gap between the uncalibrated models and the multicalibration ones, this won’t affect the gap among the multicalibration models, as they all post-processed the uncalibrated model (trained on only the training set) using a held-out calibration dataset. \n\n  The difference in this setting stems from the purpose of the experiments: Hansen et al. focused on whether multicalibration algorithms are necessary or not, i.e., if setting aside some data for different multicalibration algorithms will be beneficial compared to the baseline algorithms; while we focused on, given the same baseline algorithm and a calibration set, how well our algorithm perform compared to others. If considered this way, our setting should make sense as well. \n\n- On the discrepancy of the performance of the uncalibrated model on CivilComments dataset:\n\n  Thank you for pointing this out! Due to the aforementioned difference in data partitioning, we used 225,000 samples for baseline training, while Hansen et al. used 270,000 for the baseline algorithm. We also followed the suggested setting of finetuning for 5 epochs suggested by Koh et al. Indeed, it seems that training for additional 5 epochs might increase the performance of the uncalibrated predictor, as indicated by the results of Hansen et al., and we thank the reviewer for the kind tip.\n\n- Additional citations\n\n    As for the bibliographyic reference of the motivation, we find this work [1] relevant. Our motivation is quite similar to the motivating example of this paper, namely, down-stream decision-makers hope that the same model's predictions \"lead to beneficial decisions according to their own loss functions\".\n\n    Another work [2] might be relevant as well, as it discussed how information loss \"caused by rounding can influence the predictive power of the machine learning models\".\n\n[1] Zhao et al. (2021). Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration. NeurIPS 2021.\n\n[2] Senavirathne, N., Torra, V. Rounding based continuous data discretization for statistical disclosure control. J Ambient Intell Human Comput 14, 15139–15157 (2023)"}, {"review_id": "XQXPQ9SvqT", "reviewer": "Reviewer_zBZu", "summary": "This paper studies the problem of multicalibration, where a predictor is calibrated for a large family of groups. It proposes a one-shot, discretization-free method, which treats the uncalibrated score as another feature, fits an L2-boosted forest so that once it cannot lower the loss further, the model is multicalibrated across all groups without choosing bins by hand. The paper provides theoretical support and experiments across six datasets, achieving the lowest worst-group Smooth-ECE on each dataset.", "questions": "See weaknesses.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper seems to provide a nice theoretical link between loss and multicalibration. \n- The results show that the method improves worst-group calibration.\n\nWeaknesses:\n- Does the algorithm affect accuracy of the predictors? I may have missed this but it looks like only calibration error is reported. \n- How scalable is this method to many groups? Can this approach extend to implicit groups defined by unlabeled features?\n- Does the method rely on square loss? Would it work to minimize cross-entropy instead?\n- Can you include a baseline that is not multicalibration-aware just to see how much calibration error remains? \n-  The method requires explicit group features, which may be difficult to obtain.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful review, and we’re happy to answer the questions raised. \n\n1. On the accuracy of the predictors\n\n    This is a major aspect that practitioners might wonder about, and we thank the reviewer for pointing this out. Apart from calibration, other metrics might be of interest when evaluating an algorithm. Here we present the accuracy (for classification tasks) and MSE error (for regression tasks)\n\n    Table 1: The accuracy (%) of the predictors on classification tasks. The higher, the better.\n\n    | Method                 | Discr.   | Skin Lesion Class.   | Income Class.   | Comment Toxicity Class.   |\n    |:-----------------------|:---------|:---------------------|:----------------|:--------------------------|\n    | Uncalibrated Baseline  | /        | 70.21                | 76.71           | 92.88                     |\n    | Multiaccurate Baseline | /        | 73.19 ± 0.31         | 78.97 ± 0.06    | 92.89 ± 0.00              |\n    | LSBoost                | 10       | 77.22 ± 1.00         | 77.96 ± 0.25    | 92.81 ± 0.08              |\n    |                 | 20       | 76.55 ± 0.95         | 78.09 ± 0.33    | 92.78 ± 0.06              |\n    |                 | 30       | 76.86 ± 0.46         | 78.16 ± 0.21    | 92.78 ± 0.06              |\n    |                 | 50       | 77.06 ± 0.52         | 78.11 ± 0.20    | 92.71 ± 0.07              |\n    |                 | 75       | 76.52 ± 0.72         | 77.81 ± 0.27    | 92.65 ± 0.04              |\n    |                 | 100      | 76.12 ± 0.50         | 77.60 ± 0.30    | 92.81 ± 0.05              |\n    | MCBoost                | 10       | 71.00 ± 1.01         | 76.71 ± 0.00    | 92.88 ± 0.00              |\n    |                 | 20       | 72.15 ± 1.63         | 77.10 ± 0.34    | 92.88 ± 0.00              |\n    |                 | 30       | 73.54 ± 1.24         | 77.23 ± 0.20    | 92.88 ± 0.00              |\n    |                 | 50       | 72.07 ± 1.01         | 77.20 ± 0.40    | 92.88 ± 0.00              |\n    |                 | 75       | 73.12 ± 1.00         | 76.89 ± 0.17    | 92.88 ± 0.00              |\n    |                 | 100      | 72.29 ± 1.08         | 76.70 ± 0.22    | 92.87 ± 0.01              |\n    | Ours                   | /        | **78.90** ± 0.17         | **79.27** ± 0.07    | **92.93** ± 0.01              |\n\n    Table 2: The MSE loss ($\\times 10^{-3}$) of the predictors on regression tasks. The lower, the better.\n\n    | Method                 | Discr.   | Age Reg.    | Income Reg.   | Travel Time Reg.   |\n    |:-----------------------|:---------|:------------|:--------------|:-------------------|\n    | Uncalibrated Baseline  | /        | 5.11        | 41.39         | 30.19              |\n    | Multiaccurate Baseline | /        | 3.51 ± 0.02 | 37.92 ± 0.02  | 29.76 ± 0.02       |\n    | LSBoost                | 10       | 2.01 ± 0.24 | 39.66 ± 0.35  | 31.06 ± 0.07       |\n    |                 | 20       | 1.42 ± 0.16 | 38.98 ± 0.31  | 30.29 ± 0.09       |\n    |                 | 30       | 1.36 ± 0.13 | 39.03 ± 0.23  | 30.25 ± 0.04       |\n    |                 | 50       | 1.52 ± 0.17 | 39.51 ± 0.22  | 30.16 ± 0.03       |\n    |                 | 75       | 1.53 ± 0.19 | 38.83 ± 0.19  | 30.13 ± 0.03       |\n    |                 | 100      | 1.72 ± 0.20 | 38.80 ± 0.20  | 30.17 ± 0.03       |\n    | MCBoost                | 10       | 5.08 ± 0.25 | 42.18 ± 0.01  | 31.23 ± 0.00       |\n    |                 | 20       | 4.69 ± 0.30 | 41.10 ± 0.23  | 30.42 ± 0.00       |\n    |                 | 30       | 4.92 ± 0.17 | 40.70 ± 0.26  | 30.31 ± 0.00       |\n    |                 | 50       | 4.40 ± 0.38 | 40.93 ± 0.27  | 30.22 ± 0.00       |\n    |                 | 75       | 3.81 ± 0.36 | 40.72 ± 0.32  | 30.22 ± 0.01       |\n    |                 | 100      | 3.88 ± 0.41 | 40.95 ± 0.29  | 30.18 ± 0.03       |\n    | Ours                   | /        | **1.08** ± 0.02 | **36.11** ± 0.11  | **29.80** ± 0.04       |\n\n    By optimizing for the loss directly, our algorithm performs slightly better on standard metrics (MSE error / accuracy) on all the tasks evaluated.\n\n2. On the scalability w.r.t. number of groups.\n\n    Our approach scales well, which has been supported by both theoretical and empirical analysis. In theory, we selected a specific boosting algorithm that can be used in our framework and conducted finite-sample analysis in Appendix E. We showed that the sample complexity scales logarithmically with the number of groups. Empirically, we evaluated on approximately 50 groups for tabular data, substantially exceeding prior empirical multicalibration studies (e.g., Hansen et al. utilized at most 20 groups). \n\n3. On the selection of loss function.\n\n    Unfortunately we didn’t support other loss functions for now. We acknowledge that cross entropy is more prevalent than Brier score loss for classification tasks, and this could be left for future investigations.\n\n4. On baselines that are not multicalibration aware.\n\n    We did include non-multicalibration-aware baselines in our evaluation. The Multiaccurate Baseline achieves multiaccuracy (a weaker condition than multicalibration) and consistently exhibits higher calibration error than other algorithms. \n\n5. On the requirement of explicit group features\n\n    Indeed, we require the group features to be explicitly given, and the model's performance on unseen groups is not guaranteed. This represents a limitation of our current approach. However, as established in the algorithmic fairness literature, many works in algorithmic fairness require that “variables are explicitly defined as ‘sensitive’ by specific legal frameworks”. [1] While extending to implicit group discovery constitutes important future work, explicit group definition remains the predominant paradigm in fairness-aware machine learning applications.\n\n    We would also like to add that our response point 3 to Reviewer 3k17 might be related, in which we discussed how certain group structures can be implicitly defined.\n\n[1] Simon Caton and Christian Haas. 2024. Fairness in Machine Learning: A Survey. ACM Comput. Surv. 56, 7, Article 166 (July 2024), 38 pages. https://doi.org/10.1145/3616865"}, {"review_id": "84OE2sU9RI", "reviewer": "Reviewer_kSyY", "summary": "The paper presents a novel multi-calibration method: given a base predictor $f_0$, the paper proposed to optimize the MSE by adding a series of depth-2 trees. A single depth-2 tree would partition the dataset into four subgroups, based on 1) whether $f_0(x) >= v$ and 2) whether the instances belong to a certain pre-defined group $i$. \n\nTheoretical results show that such a algorithm \"automatically\" guarantees bounded multi-calibration error. Thus, the method does not depend on how we discretize the range of $Y$; although this is still needed to evaluate the multi-calibration error afterwards. Emprical experiments also domenstrate that the multi-calibration errors are lower than competitor methods.", "questions": "Besides my comments above, I have the following questions:\n\n1) why using linear models for the tabular data in the experiment? This is related to my last point above: what would happen if you use, e.g., lightGBM, or another tree-boosting method like XGboost here?\n\n2) Why some of the points are missing in Figure 2? Is it because of the too long runtime or something else? \n\n3) I would appreciate an empirical verification of Thm 4.6, to further justify the assumptions used for proof. That is, to empirically compare the multi-calibration error with the $sqrt(\\epsilon_{round} + \\epsilon_{loss})$.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "I like the proposed direction in the paper; however I don't think the paper is mature enough to be published at a venue like NeurIPS. \n\nStrenghs: \n- The paper is well-structured. The story line is in general clear. \n- The report empirical experiment results look quite strong. \n- The paper takes a quite novel approach to tackle this problem (to the best of my knowledge). \n\nHowever, I do have the following concerns: \n1. In the descriptions of the technical part in Section 4, some parts are contradictory to each other. \n- In eq.3, it does not make sense for $S_1(f_0)$ and $S_2(\\mathcal{G})$ to take the union among all possible $v$ and $i$ respectively. I assume you want to use them to denote the collection of the subsets, not the union of the subsets?\n- Eq.4 is contradictory to the illustration in Fig.1: in eq.4, $s_2$ is any FIXED element from $S_2(G)$, yet in Fig.1, it seems that $s_2$ can be different (you can take g_1(.) and g_2(.) for different leaves. )\n\n2. The source code is not shared making the reproducibility of the results quite low. Any specific reason why the code is not shared to the reviewers?\n\n3. It seems in the paper that the method can work with any model $f_0$; however, I am a bit skeptical in whether the proposed method would encounter a pitfall: e.g., when $f_0$ is trained with a tree boosting method (which is quite common for tabular data), and e.q.(5) is optimized with a tree boosting as well, then will the proposed method still learn to multi-calibrate? I would appreciate if this is at least discussed.", "was_revised": true, "final_justification": "All my major concerns are addressed. The only minor issues left are about\n\n1) the \"overshooting\" in the empirical validation of the theorem. \n2) the presentation of the method in the figure, but this is minor (though it might cause some big confusions so please revise it).", "rebuttal": "We thank the reviewer for the careful review. We’re happy to respond to the questions raised by the reviewer.\n\n1. Notation error in eq 3.\n\n    Indeed, according to eq 4, $s_1$ and $s_2$ should be sets, so $\\mathcal{S}$ should be a collection of sets. The correct version of Eq. 3 should be $\\mathcal{S}_1(f_0) = \\\\{ \\\\{ x \\in \\mathcal{X} : f_0(x) \\geq v \\\\} : v \\in R(f_0) \\cup \\\\{0\\\\} \\\\} $ and $\\mathcal{S}_2(G) = \\\\{ \\\\{ x \\in \\mathcal{X} : g_i(x) = 1 \\\\} : i \\in [|G|] \\\\} .$ Thank you for noting this technical inaccuracy, and we’ll correct it in our manuscript.\n\n2. Difference between Fig. 1 and Eq. 4\n\n    The two representations are different but theoretically equivalent. On one hand, the formulation in Eq. 4 can be represented by the one in Fig. 1 simply by setting the groups to be the same in a tree. On the other hand, a tree that has two different groups as features can be written as the sum of two trees in Eq. 4, one with $c_1=c_2=0$ and the other with $c_3=c_4=0$. In the illustration, we used different groups in the first place, as that’s what is implemented by the solver. We intend to change this to avoid confusion. \n\n3. Source code availability\n\n    We have already made the codebase available online. Thank you for your interest in our implementation.\n\n4. On the model architecture of the baseline algorithm for tabular data\n     Linear models are commonly used for tabular data in fairness literature, as evidenced by [1,2,3]. However, we recognize tree-boosting methods are also prevalent. In our derivation, we didn’t restrict the architecture of the uncalibrated baseline. Also, our method operates on different input features, and therefore does not contradict the baseline architecture. \n    \n    We further conducted an experiment here in which tree-boosting architecture is used for the uncalibrated baseline: \n\n    - Experiment setting: instead of linear models, we use `LGBMClassifier(num_leaves=8)` and `LGBMRegressor(num_leaves=8)` for the classification and regression tasks respectively. The other hyperparameters are chosen by default.\n\n    - Results: We present the loss in Table 3 (complementing Table 1 in the paper) and worst-group smECE in Table 4 (complementing Table 2 in the paper). \n\n        Table 3: The empirical marginal improvement of running Algorithm 1 the second time.\n\n        | Task | $\\ell(f_0)$ | $\\ell(f^{cal})$ | $\\ell(p_G(f^{cal}))$ | $\\hat{\\epsilon}_{loss} = \\ell(f^{cal}) - \\ell(p_G(f^{cal}))$ |\n        |------|-------------|-----------------|---------------------|---------------------------------------------------|\n        | Income Classification | 0.1285 | 0.1277 | 0.1276 | $2 \\times 10^{-5}$ |\n        | Income Regression  | 0.0325 | 0.0322 | 0.0322 | $9 \\times 10^{-7}$ |\n        | Travel Time Regression  | 0.0276 | 0.0276 | 0.0276 | $-3 \\times 10^{-6}$ |\n\n        Table 4: The worst-group smECE of the evaluated algorithms. The values have been multiplied by 1000 for readability. \n\n        | Method                 | Discr.   | Income Class.   | Income Reg.   | Travel Time   |\n        |:-----------------------|:---------|:----------------|:--------------|:--------------|\n        | Uncalibrated Baseline  | /        | 93.20           | 63.27         | 24.93         |\n        | Multiaccurate Baseline | /        | 67.50 ± 12.76   | 41.13 ± 1.92  | 24.88 ± 2.23  |\n        | LSBoost                | 10       | 91.06 ± 3.29    | 50.56 ± 7.27  | 42.86 ± 0.07  |\n        |                 | 20       | 93.48 ± 1.22    | 51.16 ± 7.76  | 26.56 ± 0.22  |\n        |                 | 30       | 86.89 ± 6.18    | 50.78 ± 5.05  | 28.04 ± 0.75  |\n        |                 | 50       | 78.52 ± 8.01    | 56.51 ± 4.21  | 27.26 ± 2.65  |\n        |                 | 75       | 84.49 ± 7.46    | 56.99 ± 3.53  | 26.36 ± 1.50  |\n        |                 | 100      | 87.58 ± 4.21    | 57.69 ± 3.19  | 28.97 ± 3.17  |\n        | MCBoost                | 10       | 94.57 ± 0.00    | 62.99 ± 0.00  | 42.84 ± 0.00  |\n        |                 | 20       | 90.41 ± 3.21    | 64.95 ± 0.45  | 26.48 ± 0.00  |\n        |                 | 30       | 89.62 ± 2.49    | 63.78 ± 0.51  | 27.82 ± 0.71  |\n        |                 | 50       | 91.54 ± 2.02    | 62.26 ± 0.49  | 28.62 ± 1.89  |\n        |                 | 75       | 92.33 ± 1.82    | 63.06 ± 0.50  | 25.67 ± 1.39  |\n        |                 | 100      | 93.64 ± 1.62    | 62.70 ± 1.01  | 27.13 ± 0.36  |\n        | Ours                   | /        | **64.08** ± 13.65   | **38.34** ± 2.33  | **24.75** ± 2.20  |\n\n\n    Table 3 shows that Assumption 1 is still empirically valid in the new setting. Table 4 shows that using a tree-boosting baseline also produces remarkable multicalibration, even surpassing what we originally reported with linear base models. Therefore, our algorithm still works when the uncalibrated model is a tree ensemble.\n\n5. Clarification of Fig. 2:\n\n    During discretization, we set the size of the codomain to be 10, 20, 30, 50, 75, 100, and there are always six points on each line in Fig. 2. From this perspective, no point is missing. We think what the reviewer meant by missing is that some lines don’t extend to 100. This is because the x axis in Fig. 2 is the size of the range, which can be smaller than the size of the codomain. \n\n6. Empirical evaluation of the theorem\n\n    First, we would like to point out that it is not possible to directly evaluate $\\epsilon_{loss}$, as discussed in 5.3.1. We use $\\hat \\epsilon_{loss}$, the empirical loss improvement instead as a proxy, with $\\epsilon_{loss}=\\hat \\epsilon_{loss} + \\epsilon_{opt} \\geq \\hat \\epsilon_{loss}$, where $\\epsilon_{opt}$ is the optimization error. \n\n\n    Denoting the multicalibration error as $\\alpha$, we show that, empirically, $\\alpha < \\sqrt{\\hat \\epsilon_{loss} + \\epsilon_{round}} \\le \\sqrt{\\epsilon_{loss} + \\epsilon_{round}}$ in most cases. We calculate $\\alpha - \\sqrt{\\hat \\epsilon_{loss} + \\epsilon_{round}}$ and present it in the following table. \n\n    Table: $\\alpha - \\sqrt{\\hat \\epsilon_{loss} + \\epsilon_{round}}$ of our algorithm on different tasks and different discretization, multiplied by 1000 for readability. \n    | Discretization | Income Class.   | Comment Toxicity Class.   | Age Reg.      | Income Reg.   | Travel Time Reg.   |\n    |--------------:|:----------------|:--------------------------|:--------------|:--------------|:-------------------|\n    |            10 | -19.69 ± 1.14   | -35.78 ± 0.76             | -19.15 ± 0.37 | -25.30 ± 0.87 | -17.55 ± 0.72      |\n    |            20 | -6.63 ± 0.98    | -16.86 ± 0.69             | -7.00 ± 0.70  | -11.93 ± 0.83 | -11.41 ± 0.62      |\n    |            30 | -2.22 ± 1.71    | -10.74 ± 1.07             | -4.84 ± 0.75  | -6.33 ± 0.90  | -7.86 ± 0.89       |\n    |            50 | 1.62 ± 1.58     | -5.75 ± 1.66              | -2.66 ± 0.54  | -1.39 ± 1.33  | -2.49 ± 1.01       |\n    |            75 | 2.68 ± 1.70     | -3.75 ± 1.98              | -1.31 ± 0.81  | 0.72 ± 1.62   | -0.63 ± 0.62       |\n    |           100 | 5.34 ± 2.02     | -2.03 ± 2.27              | -0.39 ± 0.75  | 2.11 ± 1.29   | 0.80 ± 0.61        |\n\n    Note that the task the task Skin Lesion Classification is not included here. This is because the empirical evaluation of $\\hat \\epsilon_{loss} + \\epsilon_{round}$ is negative for this task.\n\n    As is shown here, we have $\\alpha < \\sqrt{\\hat \\epsilon_{loss} + \\epsilon_{round}}$ in 80% of the different settings. Given $\\epsilon_{loss}\\geq \\hat \\epsilon_{loss}$, we can assert that $\\sqrt{\\epsilon_{loss} + \\epsilon_{round}}$ is empirically larger than the multicalibration error in most cases, thus validating the theorem empirically. \n\nWe hope this helps answer your questions.\n\n[1] Jung, Christopher et al. “Batch Multivalid Conformal Prediction.” International Conference on Learning Representations(2023).\n\n[2] Xian, Ruicheng et al. “Fair and Optimal Classification via Post-Processing.” International Conference on Machine Learning (2022).\n\n[3] Chen, Yatong et al. “Fairness Transferability Subject to Bounded Distribution Shift.” Advances in Neural Information Processing Systems (2022)"}]

Author rebuttal:

Meta-review: This paper proposes a discretization-free approach to multicalibration based on optimizing a loss objective over ensembles of depth-two decision trees. The work is motivated by the limitations of prior discretization-based methods, which introduce rounding errors, additional hyperparameters, and potential distortions in downstream use. The authors provide theoretical guarantees under a "loss saturation" condition, and present empirical evaluations across multiple datasets showing improvements over existing baselines.

The reviewers found the paper to be technically solid, novel, and relevant to the community. They noted that the method elegantly eliminates the discretization bottleneck, while retaining multicalibration guarantees. The approach is simple to implement (using standard tree ensemble solvers) and empirically performs competitively or better than previous multicalibration methods, especially on worst-group calibration metrics. The theoretical contribution was found to be well-motivated and rigorous. Reviewers also appreciated the clear presentation of the results.
Decision: Accept (poster)