Multiaccuracy and Multicalibration via Proxy Groups
Authors: Beepul Bharti
Mary Versa Clemens-Sewall
Paul Yi
Jeremias Sulam
Venue: ICML 2025 poster (2025)
Keywords: multicalibration
multiaccuracy
fairness
Primary area: social_aspects->fairness
TL;DR: This work demonstrates how to evaluate and control for multiaccuracy and multicalibration when sensitive group data is missing by using proxies.

Abstract: As the use of predictive machine learning algorithms increases in high-stakes decision-making, it is imperative that these algorithms are fair across sensitive groups. However, measuring and enforcing fairness in real-world applications can be challenging due to missing or incomplete sensitive group information. Proxy-sensitive attributes have been proposed as a practical and effective solution in these settings, but only for parity-based fairness notions. Knowing how to evaluate and control for fairness with missing sensitive group data for newer, different, and more flexible frameworks, such as multiaccuracy and multicalibration, remains unexplored. In this work, we address this gap by demonstrating that in the absence of sensitive group data, proxy-sensitive attributes can provably be used to derive actionable upper bounds on the true multiaccuracy and multicalibration violations, providing insights into a predictive model’s potential worst-case fairness violations. Additionally, we show that adjusting models to satisfy multiaccuracy and multicalibration across proxy-sensitive attributes can significantly mitigate these violations for the true, but unknown, sensitive groups. Through several experiments on real-world datasets, we illustrate that approximate multiaccuracy and multicalibration can be achieved even when sensitive group data is incomplete or unavailable.

Multiaccuracy and Multicalibration via Proxy Groups
Beepul Bharti 12
Mary Versa Clemens-Sewall Paul Yi Jeremias Sulam 125
Abstract
1. Introduction
Predictive machine learning algorithms are increasingly being used in high-stakes decision-makiin contexts such healthcare (Shailaja et al., 2018), employment (Freire & de Castro, 2021), credit scoring (Thomas et al., 2017), and criminal justice (Rudin et al., 2020). Although these predictive models demonstrate impressive overall perfor- mance, growing evidence indicates that they can often ex- hibit biases and discriminate against certain sensitive groups (Obermeyer Mullainathan, 2019; Dastin, 2022; et al., 2023). For instance, ProPublica's 's investigation (Angwin et al., 2022) revealed significant racial disparities in recidi- vism risk assessment algorithms, which disproportionately classified African Americans as high-risk for re-offending, As the deployment of these algorithms increases, regulatory bodies worldwide, including the US Office of Science and Technology Policy (OSTP) (of Science & Policy, 2022), European Union (Commission, 2021), and United Nations (United Nations Educational & UNESCO), have empha- sized the importance of ensuring that predictive algorithms avoid discrimination and uphold fairness.
As the use of predictive machine learning algo- rithms increases in high-stakes decision-making, it is imperative that these algorithms are fair across sensitive groups. However, measuring and enforeing fairness in real-world applications can be challenging due missing or incomplete sensi- tive group information. Proxyvsensitive attributes have been proposed as practical and effective so- lution in these settings, but only for parity-based fairness notions. Knowing how to evaluate and control for fairness with missing sensitive group data for newer, different, and more flexible frame- works, such multiaccuracy and multicalibra- tion, remains unexplored. In this work, we ad- dress this gap by demonstrating that in the ab- sence of sensitive group data, proxy-sensitive at- tributes can provably be used to derive actionable upper bounds on the true multiaccuracy and mul- ticalibration violations, providing insights into a predictive model's potential worst-case fairness violations. Additionally, show that adjusting models to satisfy multiaccuracy and multicalibra- tion across proxy-sensitive attributes can signifi- cantly mitigate these violations for the true, but unknown, sensitive groups. Through several ex- periments on real-world datasets, we illustrate that approximate multiaccuracy and multicalibration can be achieved even when sensitive group data is incomplete or unavailable.
These concerns have led to the emergence of algorithmic fairness, a field dedicated to ensuring that predictive models do not inadvertently discriminate against sensitive groups defined by sensitive attributes such as race, age, biologi- cal sex. Unfortunately, measuring and controlling model's fairness can be challenging in many real-world settings, as sensitive group information is often incomplete or unavail- able (Holstein et al., 2019; Garin et al.; Yi et al., 2025). In certain contexts, like healthcare, privacy and legal reg- ulations such as the HIPAA Privacy Rule restrict access to sensitive data. In other cases, the information was not collected because it was considered unnecessary (Weiss- man & Hasnain-Wynia, 2011; I; Fremont et al., 2016; Zhang, 2018). Despite these obstacles, it remains crucial to eval- uate a model's fairness before and during its deployment. This raises the question: how can we evaluate and promote fairness when sensitive group information is imperfect or missing altogether?
'Deparmmnnt of Biomedical Engineering, Johns Hopkins Uni- versity, Baltimore, USA Mathematical Institute of Data Science, Johns Hopkins University, Baltimore, USA 'Department of Ap- plied Mathematics & Statistics, Johns Hopkins University, Bal- timore, USA SSt. Jude Children's 's Research Hospital, Arlington, USA DDeparmeett of Computer Science, Johns Hopkins Univer- sity, Baltimore, USA. Correspondence to: Beepul Bharti <bb- hartil @ jhu.edu>, Jeremias Sulam <jsulaml I @ jhu.edu>.
One popular approach, widely applied in healthcare (Brown et al., 2016), finance (Zhang, 2018), and politics (Imai & Khanna, 2016) is to utilize proxy attributes in place of true attributes. Proxy methods have been immensely effective
Proceedings of the 4rnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Multiaccuracy and Multicalibration via Proxy Groups
in evaluating and controlling for traditional parity-based notions of fairnsss (Diana al., 2022; Bharti et al., 2024;
1.1. Related Work
Using proxy-sensitive attributes to measure and enforce model faimess has been extensively studied for various parity-based fairness notions.
Awasthi et al., 2021; Prost et al., 2021; Zhao et al., 2022:
Awasthi et al., 2020; Gupta et al., 2018; Kallus et al., 2022), such as demographic parity (Calders et al., 2009), equalized odds (Hardt et al., 2016), and disparate mistreatment (Zafar et al., 2017), which all aim to equalize model statistics across protected groups.
Measuring fairness. Measuring a model's true fairness through proxies has become an important area of research. Chen et al. (2019) were among the first to tackle this chal- lenge by studying the error in measuring demographic parity using proxies derived from thresholding the Bayes optimal predictor for the sensitive attribute. Awasthi et al. (2021) focus on equalized odds, identifying key properties that proxies must satisfy to accurately estimate true equalized odds disparities. Kallus et al. (2022) further examine the ability to identify traditional parity- -baed fairness violations. They demonstrate that, under general assumptions about the distribution and classifiers, it is usually impossible to pinpoint fairness violations accurately using proxies. Addi- tionally, by assuming access to the Bayes optimal predictor for the sensitive attribute, they provide tight upper and lower bounds on various fairness criteria, thereby characterizing the feasible regions for these violations. More generally, considering any proxy model instead of the Bayes optimal, Zhu al. (2023) shows that estimating true parity-based fairness disparities using proxies results in errors propor- tional to the proxy error and the true fairness disparity. Most recently, Bharti et al. (2024) address setting with more lim- ited information compared to Zhu et al. (2023), providing computable and actionable upper bounds on true equalized odds disparities based on the proxy's 's misclassification error and proxy group-wise predictor statistics.
While enforcing parity is desirable in some settings, it can also lead to undesirable trade-offs. For instance, in breast cancer screening, incidence rates vary by age. with older women generally at higher risk than younger women (Kim et al., 2025). Thus, equalizing a model's false positive rates across age groups might reduce the sensitivity of cancer detection in older women, who are more likely to have the disease. Conversely, equalizing false negative rates might lead to unnecessary biopsies by increasing false positive rates in certain groups. Instead, a more appropriate fairness criterion would be to ask that the model's risk predictions ap- proximately reflect true probabilities within each age group.
These types of domain-speciff challenges have led to the development of two newer fairness notions: multiaccuracy and multicalibration (Kim et al., 2019; Gopalan et al., 2022; Hébert-Johnson et al., 201 8). Instead of enforcing parity, these methods ensure that model predictions are unbiased and well-calibrated across groups They can be applied to complex, overlapping sensitive groups as those defined by race and conder-whild maintaining high pre- dictive accuracy and ensuring the model remains useful in practice, offering significant advantages over traditional parity-based metrics. As a result, enforcing multiaccuracy or multicalibration is powerful and often preferable in many contexts (Kim et al., 2019; Hébert-Johnson et al., 2018). However, a key challenge remains: when sensitive group data is missing, how can we build provably multiaccurate and multicalibrated models leveraging proxies?
Enforcing fairness. An equally important question is how to ensure fairness using proxies. Awasthi et al. (2020) exam- ine the post-processing method for equalized odds (Hardt et al., 2016) when noisy proxies are used instead of true sensitive attributes. They show that, under conditional inde- pendence assumptions, using proxies in the post-pros post-processing method results in a predictor with reduced equalized odds disparity. Wang et al. (2020), working with a slightly dif- ferent noise model, propose robust optimization approaches to train fair models using noisy sensitive features. Hav- ing proven that fairesss violations are often unidentifiable, Kallus et al. (2022) take a different approach and focus on reducing the worst-case violations. Under additional smoothness assumptions they derive tighter feasible regions for fairness disparities, offering improved worst-case guar- antees for faimess violations. More recently, Bharti et al. (2024) characterize the predictor that has optimal worst-case violations and provide generalized version of Hardt et al. (2016)'s method that returns such a predictor. Taking a different perspective, Lahoti et al. (2020) avoid relying on proxies altogether. Instead, they propose solving a minimax optimization problem over vast set of subgroups, reasoning
Tackling this issue is essential for developing models that are fair across multiple complex groups without sacrificing accuracy or utility. In this work, we address this gap. We study how to estimate multiaccuracy and multicalibration fairness violations without access to true sensitive attributes. We show that proxy-sensitive attributes can be used to de- rive computable upper bounds on these violations, capturing the model's 's worst-case fairness. Additionally, we demon- strate that post-processing model to satisfy multiaccuracy or multicalibration across proxies effectively reduces the worst-case fairness violations, offering practical insights. In conclusion, we demonstrate that even when sensitive infor- mation is incomplete or inaccessible, proxies can greatly help in providing approximate multiaccuracy and multicali- bration protections in useful and meaningful way.
2

---

Multiaccuracy and Multicalibration via Proxy Groups
that any good proxy for sensitive feature would naturally be included in this set. Diana et al. (2022) address the problem of learning proxies that enable downstream model developers to train models that satisfy common parity-based fairness notions. They demonstrate that this entails con- structing a multiaccurate proxy and introduce a general oracle-efficient algorithm to learn such proxies.
of functions that define complex, potentially intersecting
groups in X' x Z. For any g E 9, gX,, Z) = 1 indicates that the individual (X, Z) belongs group g. For example, let X1 be an individual's 's credit score and let Z1 and Zz represent the individual's age and memhership in the African American group. Then, gXX, 2) = 1{X, > 700 A 11 > 40 A Z2 = }} specifies the group of all African Americans over the age of 40 with a credit score over 700. In this way, it is easy define arbitrary overlapping groups defined by the intersection of basic attributes and other features. Finally, in our setting, model is a function ʃ f: X - R that maps from the feature space to some discrete domain R S [0, 1]. We denote its image as Im(f) = [f(X) : X E X} and assume that [m([]] < 00.
1.2. Our Contributions
There exists a rich line of work that studies how to evaluate and enforce parity-based notions of fairness when sensitive attribute data is missing via proxies. These, however, do not extend to settings where multiaccuracy and multicalibration are more appropriate, limiting their applicability in data- scare regimes. In this work, we address this issue. Our main contributions are the following:
Problem Setting. In this work, the primary objective is to assess whether model f is fair with respect to set of sensitive groups 9 without having access to the functions in G to determine group membership. Formally, and similar to previous work (Awasthi et al., 2021; Kallus et al., 2022), we consider a setting where we do not have access to samples (X, Z, Y) from the complete distribution D - and thus we are unable to use the true set of grouping functions 9 since their domain is supported X' Z. Instead, we assume access to sufficient number of samples (X, (X) from Dxy, the marginal distribution over X' x )r which allow us to reliably evaluate the overall performance of the predictor f via its mean- aucan-suuared error
1. We study the problem of estimating multiaceuracy and multicalibration violations of a predictive model with- out access to sensitive group information.
2. We derive computable upper bounds for multiaccuracy and multicalibration violations using proxy-sensitive attributes.
3. We show that post-processing a model to satisfy multi- accuracy and multicalibration across proxies reduces the worst-case violations, allowing us to provide mean- ingful fairness guarantees without access to sensitive group data.
MSE( E (X- (X,Y)DXY
(I)
The remainder of the paper is structured as follows. In Section 2, we introduce the necessary notation and formalize the setting. Section 3 provides background on multiaccuracy and multicalibration. Our main theoretical results are presented in Section 4 and Section 5, where we establish computable upper bounds on the multiaccuracy and multicalibration violations and demonstrate how to min- imize them. Experimental results are detailed in Section 6. Finally, in Section 7 we discus the implications of our work and provide closing remarks.
Organization.
Additionally, we assume a proxy developer that has access to samples (X, Z) from Dxz, the marginal distribution over X x Z. They provide a set of learned proxy functions & = {0 X + {0, 1}} for G that only use features X, allowing to determine proxy group membership. More- over, via the proxy developer, we know how well any proxy 9 E 9 approximates its associated true و E G through its misclassification ertor,
err(g)
[X(X) + 9(X, Z)). (X.Z)=Dx2
I
(2)
2. Preliminaires
Through this setup, we are modeling real-world situations where we lack information about individuals' basic sensi- tive attributes, such as sex and race, preventing us from accurately identifying individuals' membership in complex intersecting groups (for example, white women over the age of 40). Instead, we we rely on proxies to (approximately) represent all groups. Importantly, we do not make stringent, unverifiable assumptions about these proxy functions, un- like other studies (Prost et al., 2021; Awasthi et al., 2020; 202 I); we only consider knowing their error rates, err(ğ).
Notation. We consider binary classification setting I with a data distribution D supported on X' x 2 x V, where X' C Rd and 2 C " represent a d-dimensional feature space and K -ddimensional sensitive group space, respectively, and y' = (0. 1} denotes the binary label space. For an individual represented by the pair (X, X is a vector of features and Z is vector of sensitive features (c.g., race, biological, age). We denote G = {g X' x 2 + })] as the set
'One can also extend this K-class problem using a one-vs- all approach.
With our setting fully described, we now turn to our main objective: assessing the faimess of the model f with re-
3

---

Multiaccuracy and Multicalibration via Proxy Groups
spect to G. In this work we focus on two fairness con- cepss-mlliaccurran and mulricalibrrtionn we now formally define.
can guarantee-let alone, correct-that predictor is (G, o)- MA/MC in the absence of ground truth groups G. Fortu- nately, in the following sections, we demonstrate that with proxies, one can successfully circumvent these limitations and still provide meaningful guarantees.
3. Multiaccuracy and Multicalibration
Multiaccuracy. Multiaccuracy (MA) is notion of fairness originally introduced by (Kim et al., 2019; Hébert-Johnson et al., 2018). For any sensitive group 9 G, MA evaluates the bias of model f. conditional on membership in g via
4. Bounds on Multigroup Fairness Violations
We will now demonstrate that is still possible to derive computable and useful upper bounds for the MA and MC violations of a model f across the true groups 9, even in the absence of true group information.
AE g) Eolo(XX Y)]
(3)
Our first result provides computable upper bounds on AED(J,g) g) and ECEp(J .)) for any group g.
and requires that (E)(J,g) be small for all groups g E G.
Lemma 4.1. Fix a distribution D and model f. For any group g and its corresponding proxy 9.
Definition 3.1 (Multiaceuracy (Kim et al., 2019)). Fix distribution DD and let 9 be set of groups. A model f is (G, m)-multiaccurate if
(E S F(S.)) (E)( ECEp(f.9) I F(f.9) ECED(f,0)
(6)
AE max
(1,9) max (ED(J,g) a 9Eg
(4)
(7)
where
(G, a-)-AA requires that the predictions of f be approxi- mately unbiased overall and on every group. Building on
F(f.9) min (err()) v MSE(F) err
(8)
this, (Hébert-Johnson et al., 2018) introduced stronger notion of group fairness known as multicalibration (MC),
Furthermore the upper bounds are tight.
which demands unbiased and calibrated predictions. Cen- tral to evaluating MC is the expected calibration error (FCE)
A proof of this result is provided in Appendix B.I. We now make a few remarks. First, the upper bounds on the true MA/MC violations are tight: there exist non-trivial joint dis- tributions over (f(X), 9XX) ((X), "ppssciiillllll. those for which (r) > O and MSE(J) 0 0-such that the bounds are attained with equality. Please see Appendix B.1 for a comprehensive discussion regarding these statements. Second, in our setting, both bounds can be directly evaluated because (1) we know err(ğ) for all y E G via the proxy de- veloper, who has access G and sufficient number of sam- ples (X, Z) from Dxz to compute (rr(ğ); and (2) we can reliably compute MSE(J), AED ()). and ECE 9) be- cause we have access to sufficient number of samples (X, Y) from Dxy.
for a group g E E
ECEp(f.g) = E D-D;
-x)_(())))))((())==))))))))))))) x)(f(x) vl
where Dy is the distribution of the predictions made by f under D. MC requires that ECEp(f.g) g) be small for all groups g E.
Definition 3.2 (Multicalibration (Hébert-Johnson et al., 2018)). Fix a distribution D and let g be a set of groups. A model f is (G, m)-multicallbbrtee if
ECE max (f,g) == max ECEp(f.9) S a. gEG
(5)
This result aligns with intuition, showing how the relation- ship between proxy Å and the model f constrains the maximum possible values of AED(f,g) and ECEp (f. g). If the proxy 9 is highly accurate in that it predicts the true group g better than I predicts the true label Y, i.e. if
This is an 4 notion of MC as studied in (Gopalan et al., 2022). There also exist 12 (Globus-Harris et al., 2023b) and loc (Hébert-Johnson et al., 2018) variants. aM requires that I's predictions be approximately calibrated on all groups defined by G. Note, MC is stronger than MA because intuitively MC requires MA on every level set of f-
err(O) < MSE(f).
(9)
then F(f = err(ğ), and the true violations AEp(f.0) .)) and ECEp 9) are approximately bounded by their proxy estimates. Conversely, if is highly accurate in predicting the label Y but the proxy is weaker, so that
Having presented these definitions, the problem we face is now clear: Ideally, we would like to evaluate AEmax and ECE However, this requires access to samples (X, Z,Y, ~ D and the functions G, neither of which we assume to have. As alluded to before, no method exists that
MSE(F) < err(g),
(10)

---

Multiaccuracy and Multicalibration via Proxy Groups
Algorithm I Multiaccuracy Regression
Algorithm 2 Multicalibration Boosting
1: Input: Initial model / and set of groups 9
I: Input: Initial model f. set of groups 9, and or 0
2: Solve
2: Let m = 112 t = 0, fo := f
3: while
f E arg min MSE(f)
AERIE
max Pla(X, Z) 11 E (l 1| geg
s.t. f(x f(X)
Σ (x(,
DEG
4: Set
3: Return /
P3." = P(g(X, 2) = 1, f(() =
(Ue, (() = arg max Pg.0 A 2 a
then F(S.9) = V (f) err(ū), and one can attain a better bound by considering a factor of /MSE(/) err(ğ) instead of err(ğ). Naturally, as MSE(f) decreases, the maximum possible values of AE ()) and ECED(f.
Su,g. = {X E X f((X) = U. 9x = 1}
0r = E( = ut, 9 (X, 2) =1]
0/ = arg min jōt-ul vl
decreases as well.
Most importantly, with this result, bound for the true MA and MC violations of f across G.
provide upper
fx+ = 1/4 fx()
if E Son.
otherwise
Theorem 4.2. Fix a distribution D and model f. Let G be set of true groups and G be its associated set of proxies. Then, J is (9, ((,,))))MA and (J, where
1=6+1
5: end while
6: Let T := t, = fr
B(f 9) max F(f. (E)(J.))
(11)
7: Return ƒ
GEG
((.
max F(f + E DEG
(12)
Within the bounds B(f, 9) and >(f. 9). there are only two quantities we can modify by adjusting f: the mean squared error MSE(f) and either AED 9) or (f, g). Since we lack access to the true grouping functions G and samples (X, 2) ~ Dxz, we cannot reduce the proxy errors @rr(ğ). Thus, the question is, what modifications
This result directly follows from Lemma 4.1, with a com- plete proof provided in Appendix B.2. It is particularly valu- able because, even without directly evaluating the quantities of interest, AE (f.9) and ECE (f, G), we can still evaluate these worst-case violations, which offers practical utility. For instance, if we need to ensure that is (G, a)- MC before deployment, we can proceed confidently even without direct access to G, provided that ( 9) < a. Con- versely, if the worst-case violations are large, this suggests that f may potentially be significantly biased or uncalibrated for certain groups g-
be made / such that the updated f has smaller bounds? We answer this question for the bound on MC in the following theorem.
Theorem 5.1. Fix a distribution DD initial model f. and set of proxy groups G. If a model f satisfies
ECE (f,9) < min ECED(f,
(13)
GE9
MSE( < MSE(J)
(14)
In scenario where the worst-case violations are large, model developers, we should pause deployment and ask: if it is the case that @(f. ②) or y(f. are large, can we reduce them such that we can provide better guarantees on the worst-case MA and MC violations of f? We show that is possible in the following section.
then, it will have a smaller worst-case MC violation, i.e.
>(..) S ((..)).
(15)
An identical result for MA is given Appendix A and proofs for both results are provided in Appendix B.3. This results simply states that if we can obtain new model f that 1) is (G. .MC at level
5. Reducing Worst-Case Violations
mingeg ECE and 2) has smaller MSE, then it is guaranteed to have smaller worst-case violation. Fortunately, both objectives can be nearly achieved using Algorithm 1, proposed by Gopalan et al. (2022), and Algorithm 2, introduced by Roth (2022), which produce MC and MC predictors, respectively.
The results from the previous section allow us to upper bound the MA and MC violations using proxies. Now, we show that these violations can be provably reduced, yielding stronger worst-case guarantees. Recall that we have a fixed set of proxies G. a model f, and access to samples (X, Y).
5

---

Multiaccuracy and Multicalibration via Proxy Groups
Group
err(ğ)
Group
err(g)
Group
err(ğ)
Black Women
0.027
Black Women
0.005
Women
0.027
White Women
0.122
White Women
0.046
White
0.092
Asian
0.060
Asian
0.000
Asian
0.068
Seniors
0.000
Multiracial
0,000
Black
0,039
Women
0.000
Black Adults
0.000
Asian Men
0,039
Multiracial
0.047
Women
0.079
Black Women
0.020
Table 1. Proxy errors for ACSIncome
Table 2. Proxy errors for ACSPubCov
Table Proxy errors for CheXpert
Algorithm I outlines a simple algorithm for MA. The follow- ing theorem establishes that the algorithm produces a model that satisfies MA while also guaranteeing an improvement or deterioration in MSE.
can systematically reduce worst-case violations on the true groups G. This simple yet effective approach ensures al- lows us still provide meaningful fairness guarantees and reliable predictions across sensitive subpopulations.
Theorem 5.2. Fix distribution D. predictor f. and set of groups G. Algorithm returns a model J that is (0, G-MM Moreover,
6. Experimental Results
We illustrate various aspects of our theoretical results on two tabular datasets, ACSIncome and ACSPublicCoverage (Ding et al., 2021), as well as on the CheXpert medical imaging dataset (Irvin et al., 2019). For the ACS datasets, use fixed 10% of the samples the evaluation set. The remaining 90% of the data is split into training and validation sets, with 60% used for training the model f and proxies & and 30% for adjusting f. All reported results are averages over five train/validation splits on the evaluation set. For CheXpert, we use the splits provided by (Glocker et al., 2023) for training, calibration, and evaluation. The results and metrics are computed on the evaluation set. We report results for MC in the main body of the paper and defer those for MA to Appendices C and E because MC is a stronger notion that implies MA. The code necessary to reproduce these experiments is available at ht https:// /// g hithuu. com/ SSulam-Groul httppp/p/ooyaaaaapap ma-me.
MSE(f) = MSE(f).
(16)
A proof of this result can be found in (Detommaso al., 2024), with finite-sample guarantees discussed in (Roth, 2022). Algorithm 1 updates the model f by solving a stan- dard linear regression problem, where the features are the predictions of the initial model f and grouping functions g.
While Algorithm 1 solves a optimization problem to gener- MA model in a single step, Algorithm is iterative method to ensure MC. Algorithm starts by checking if is Q-MC via the group average squared calibration error
E 19 X, 7) =]
(17)
where A.gg = Ry (()) = u. v. 2)= = 1]. If this exceeds o, it identifies the conditioning event where the calibration error is the largest and refines f's predictions. It iterates like this until convergence and this process returns new model f that is a-MC and has an MSE that is close, potentially even lower, than the MSE of the initial model f. Theorem 5.3. Fix a distribution D, predictor f and set of groups G. Algorithm 2 stops after T < a rounds and returns model, ff that is (Vo,9) 9)-M. Moreover,
6.1. ACS Experiments
For the two following tabular data experiments we use the ACS dataset, larger version of the UCI Adult dataset. In partieular,
the 2018 California data, which contains approximately 200,000 samples. We follow Hansen et al. (2024) and define multiple sensitive groups G using basic sensitive attributes Z (c.g., sex and race, which model developers aim not to discriminate towards), along with certain features X (e.g., age). Examples of groups E G include white women and black adults. For both experiments, we simulate missing sensitive attributes by excluding some Z; from the data tive model f. Instead, with an auxiliary dataset of samples (X, 2) and the true set of grouping functions G, we obtain a set of proxy functions ς to approximate G.
a²
MSE()) < MSE(f) (1-T)
4 +
(18)
proof, along with with finite-sample guarantees can found in (Globus-Hane HaoobssHHarrisse al., 2023a; Roth, 2022).
train our predic-
Having introduced these algorithms for obtaining multiac- curate and multicalibrated models f. we now have a direct path to reducing worst-case violations. By applying Algo- rithm or Algorithm (at an appropriate level o:) to our initial model ff using the proxies ς-that is, enforcing multi- accuracy or multicalibration with respect the proxies-wo we
For our initial model f, we report the worst-case violations, which we can evaluate our setting, To demonstrate that
6

---

Multiaccuracy and Multicalibration via Proxy Groups
vioiation and Bounds (Before Adustment)
Molations Bounds
Melstions and Bounds (Belore Acjustment)
MC Vistadions and Bounds
(Atter Adjustment
|Atter Adjustmmnt)
3.200
Thu Violstion Upper Bound
0.200
Tue Vioiation
0.25
0:25
True Viclation
Upper Bound
Bound
0.20
0.20
0.150
0.150
0.125
EcEl
0.125
0.15
Thee Viniation Upper Bound
0.35
0:100:
0.100
0.075
0.075
0.30-
0.050
0.050
0.05
0.05
0.025
0.025
0.000
4 6
4
5'
Groups
Groups
Groups
Groups
(a) ECE, ECE (dotted red line), and worst case violations (dotted blue line) of the original model f and adjusted model fui) on ACS Income. Here, f is decision tree.
(b) ECE, ECE (dotted red line). and worst case violations (dotted blue line) of the original model f and updated model fug on ACSPubcov. Here, f is decision tree.
enforcing MA and MC with respect to & provably reduces our upper bounds, we apply Algorithm 1 and Algorithm 2 to obtain an adjusted predictor faj and report its worst- case violations as well. Additionally, for both the initial model f and adjusted model fadj we report the AE and ECE, with respect to the true groups 9 E G. along with their maximums, AEmax and ECE Recall that in our setting, we cannot actually evaluate these quantities but we report them showcase that they lie under our bounds, illustrating the validity of our theoretical results. For these tabular experiments, we model f with a logistic regression model, a decision tree, and Random Forest. We report the results for the decision tree in the following sections and defer the remainder to Appendices C and E.
highlights the benefit of applying Algorithm and multical- ibrating the initial model f with respect to the proxy groups G. After adjusting f, the upper bound decreases, allowing us to certify that the resulting model sutj is approximately O. 3--uuliiallbrrate--a substantial improvement of 38%.
1.2. ACSPUBLICCOVERACE (ACSPUBCOV)
In this experiment, we consider the task of predicting whether low-income individuals (< $30,000) not eligi- ble for Medicare, have coverage from public health insur- ance. Examples of features X include age, educat i ion, i income, and more. To simulate missing sensitive attributes, we exclude the sex attribute.
In Table 2, we report the errors of the learned proxies 9 for specific groups. Notably, for groups independent of sex, such as asian and multiraciall the proxies 9 are per- fectly accurate, exhibiting zero misclassification error. How- ever, for groups like black women and white women, the proxies exhibit some error, though they are small. This arises because, although the proxies functions 9 are not explicit functions of sex attribute, there exists a feature, fert l lity, that indicates whether an individual has given birth within the past 12 months and serves as good predic- tor of sex. This is prime example of real-world setting where, even though sensitive attributes may be missing, strong proxies can still enable us to determine true sensitive group membership with high accuracy.
6.1.1. ACSINCOME
For this experiment, we consider the task of predicting whether working adults living in California have a yearly in- come that exceeds $50,000. Examples of features X include occupati i on and educat i on. To simulate missing sen- sitive attributes, we exclude the race attribute.
In Table 1, we report the errors of the learned proxies & for specific groups. For groups that do not depend on race, such as seniors and women, their respective proxies 9 are perfectly accurate, exhibiting zero misclas- sification error. However, for groups like mu 1 t raci a and white women, the proxies exhibit some error, albeit small. This proves to be useful in providing meaningful guarantees on how multiaccurate and multicalibrated the model f may potentially be with respect to the true (but unobserved) groups G.
In Figure Ib, we show the results of applying Algorithm to multicalibrate the initial model f with respect to the proxies g. Notably, our approach allows us to certify that the initial model is approximately 0.25-MC with respect to the true groups & despite not having access to them. This result high- lights the utility of our method, as it enables practitioners to obtain performance guarantees without needing the true group information. Furthermore, after applying Algorithm 2 to f. the resulting model fadj is certified to be approximately 0.09-MC, thereby providing a stronger guarantee.
Figure Ia showcases the utility of our bounds. Notably, the worst-case violation (dotted red line) allows us to certify that the initial model is approximately 0.21 -muuticcalibrated with respect to the true groups g. This is indeed practically useful as it enables practitioners to obtain a certificate on the MC violation without having access to the true sensitive group information. Additionally, the right-hand graph in Figure la
7

---

Multiaccuracy and Multicalibration via Proxy Groups
Volations (Bedbre adjustment)
MC viclatiors
MC Violatiors and Bounds [Beefore Adjustment)
MC MCVisation and Bounds
[Atter merl))
(Belare Adpalmentt mene!
True Vislation
True Violation
0.12
0.12
0.35
Upper Bound
0.35
Upper Bound
0.30
0.30-
0.30
0.30
0.25
0.00
True Volltion Upper Bound
ECERt.
0.08
Tuu Vistaton
0.20
0.20
0.06
Upper Bound
0.15
0.15
0.04
0.04
0.10
0.10
0.05
0.05
0.02
0.02
9
Groups
Groups
Groups
Groups
(a) ECE. ECE (dotted red line), and worst case violations (dotted blue line) of the original model f and adjusted model fatj on CheXpert. Here f is decision tree trained on embeddings of DenseNet-121 121 model pretrained on ImageNet.
(b) ECE. ECE max (dotted red line), and worst case violations (dotted blue line) of the original. unadjusted, logistic regression model (left) and end-to-end trained DenseNet- 121 model (right).
6.2. CheXpert
brate the initial model f with respect to our highly accurate proxies G. After a straightforward adjustment, the upper bound on the worst-case violation decreases significantly, certifying that the adjusted model Sadj is approximately 0.13- MC with respect to the true groups.
CheXpert is a large public dataset for chest radiograph inter- pretation, with labeled annotations for 14 observations (pos- itive, negative, or unlabeled) including cardiomegaly atelectasis, and several others. The dataset contains self-reported sensitive attributes including race, sex, and age. Following the set up of Glocker et al. (2023), we work with a sample containing a total of 127,118 chest X-ray scans and consider the task of predicting the presence of pleural effusion in the X-rays.
Figure 2b presents the results for the logistic regression and fully-trained DenseNet models. In these cases, the worst- case violations for both models indicate that they are guar- anteed to be approximately 0.11 and 0. 1.12mmulicaliibrated with respect to the true groups Notably, both models are ap- proximately 2.0--multicalibrated with respect to the proxies. Thus, further adjustments provide negligible improvements.
We consider all 14 groups that can be made from conjunc- tions of sex and race. Examples of groups g E G include black men, asian women, white women, etc. In this example, we assume that we do not have direct knowl- edge of patient's self-reported sex or race when train- ing or evaluating our model (as is common for privacy reasons). Instead, with an auxiliary dataset with samples (X, we use the X-rays to learn proxy functions for sex and race. We then use them to construct proxies for all conjunctions as well. In Table 3, we report the proxy errors for specific groups.
7. Conclusion
In this work, we address the challenge of measuring multiac- curacy and multicalibration with respect to sensitive groups when sensitive group data is missing or unobserved. By leveraging proxy- sroxy-sensitive attributes, we derive actionable upper bounds on true the multiaccuracy and multicalibration violations, offering a principled approach assessing worst- case fairness violations. Furthermore, demonstrate that adjusting models to be multiaccurate or multicalibrated with respect to proxy- sexx-ssenitive attributes can significantly reduce these upper bounds, thereby providing useful guarantees on multiaccuracy and multicalibration violations for the true, but unknown, sensitive groups
We consider three different models for f. The first is decision tree classifier trained on features extracted from 1enseNet-121 model (Huang et al., 2017) pretrained on ImageNet (Deng et al., 2009). The second is linear model (Breiman, 2001) trained on the same features. The third is a DenseNet- 121 trained end-to-end on the X-rays.
Through empirical validation real-world datasets, we show that multiaccuracy and multicalibration can be approx- imated even in the absence of complete sensitive group data. These findings highlight the practicality of using proxies to assess and enforce faimess in high-stakes decision-making contexts, where access to demographic information is often restricted. In particular, we illustrate the practical benefit of enforeing multiaccuracy and multicalibration with respect to proxies, providing practitioners with simple and effective tool to improve fairness in their models.
Figure 2a illustrates the results for the decision tree model. Before any adjustments, worst-case violation serves as early warning that the model f may be significantly uncalibrated on certain groups, with violation as large as a RJ 0.42. In a medical setting like this, such a finding is cru- cial, as it indicates that our predictions could be either overly confident or underconfident on sensitive groups. On the other hand, the right-hand graph of Figure 2a demonstrates the practical benefit of applying Algorithm 2 to multicali-
8

---

Multiaccuracy and Multicalibration via Proxy Groups
Naturally, multiaccuracy and multicalibration may not be the most appropriate fairness metrics across all settings. Nonetheless, whenever these notions are relevant, our meth- ods offer, for the first time, the possibility to provide cer- tificates and strengthen them without requiring access to ground truth group data. Lastly, note that without our rec- ommendations of correcting for worst-case fairness with proxies, models trained on this data can inadvertently learn these sensitive attributes indirectly and base decisions them, leading potential negative outcomes. Our results and methodology prevent this by providing a principled approach to adjust models and reduce worst-case multiaccu- racy and multicalibration violations.
Breiman, L. Random forests. Machine learning, 45(1):
5-32, 2001.
Brown, D. P., Knapp, C., Baker, K., and Kaufmann, M. Using bayesian imputation to assess racial and ethnic disparities in pediatric performance measures. Health services research, 51(3):1055-1188, 2016.
Calders, T., Kamiran, F., and Pechenizkiy, M. Building classifiers with independency constraints. In 2009 IEEE international conference data mining workshops, pp. 13-18. IEEF, 2009.
Chen, J., Kallus, N., Mao, X., Svacha, G., and Udell, M. Faimess under unawareness: Assessing disparity when protected class unobserved. Proceedings of the conference on fairness, accountability, and transparency, pp. 339-348 2019.
Impact Statement
In this work, we propose effective solution to techni- cal problem: estimating and controlling for multiaccuracy and multicalibration using proxies. While proxies can be controversial and pose risks-such as reinforcing discrimi- nation or compromising privacy-predictee learn sensitive attributes indirectly, leading to unintended harm. When used carefully, proxies can help mitigate these risks, demonstrate in this work. However, deploying proxies in weal-world scenarios requires a careful evalua- tion of trade-offs through discussions with policymakers, domain experts, and other stakeholders. Ultimately, proxies should be employed responsibly and solely for assessing and promoting fairness.
Commission, E. Proposal for a regulation laying down harmonised rules on artificial intelligence (artificial intelligence act), 2021. URL https:
models often
/ deiigital-stratee ec. wwwpppp.....uru..eee.e.... aeaiccee/regulltoory-faaaeeee
Dastin, J. Amazon scraps secret ai recruiting tool that showed bias against women. In Ethics of data and ana- Auerbach Publications, 2022.
lytics, pp. 296-299.
Deng, J., Dong, W., Socher, R., Li, L.-J.,, Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. 2009 IEEE conference on computer vision and pattern recognition (CVPR), pp. 248-255. IEEE, 2009.
Acknowledgements
This work was supported by NIH award R01
Detommaso, G., Bertran, M., Fogliato, R., and Roth, A. Multicalibration for confidence scoring in llms. In Pro- ceedings of the 41st International Conference on Machine Learning, ICML'24, 2024.
References
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Ma- chine bias. In Ethics of data and analytics, pp. 254-264. Auerbach Publications, 2022.
Diana, E., Gill, W., Kearns, M., Kenthapadi, K., Roth, A., and Sharifi-Malvan Mallajiri,,, S. Multiaccurate proxies for downstream faimess. 2022 ACM Conference on Fairness, Accountability, and Transparency, 2022.
Awasthi, P., Kleindessner, M., and Morgenstern, J. Equal- ized odds postprocessing under imperfect group infor- mation. In International Conference on Artificial Intelli- gence and Statistics, pp. 1770-1780. PMLR, 2020.
Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478-6499 2021.
Awasthi, P., Beutel, A., Kleindessner, M.. Morgenstem, J., and Wang, X. Evaluating fairness of machine learning models under uncertain and incomplete information. In Proceedings of the 2021 ACM Conference on Fairness, Accoumability, and Transparency, pp. 206-214, 2021.
Freire, M. N. and de Castro, L. N. e-recruitment recom- mender systems: systematic review. Knowledge and Information Systems, 63:1-20 2021.
Bharti, B., Yi, P., and Sulam, J. Estimating and control- ling for equalized odds via sensitive attribute predictors. Advances in neural information processing systems, 36, 2024.
Fremont, A., Weissman, J. S., Hoch, E., and Elliott, M. N.
When race/ethnicity data are lacking: using advanced indirect estimation methods to measure disparities. Rand health quarterly, 6(1), 2016.

---

Multiaccuracy and Multicalibration via Proxy Groups
Garin, S., Parekh, V., Sulam, J., al. Medical imaging data science competitions should report dataset demographics and evaluate for bias [published online ahead of print april 3, 2023]. Nat Med.
Irvin, J., Rajpurkar, P., Ko, M., Yu, Y., Ciurea-lleus, S., Chute, C.,, Marklund, H., Haghgoo, B., Ball, R., Shpan- skaya, K., et al. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison. In Proceedings of the AAAI conference on artificial intelli- gence, volume 33, pp. 590-597, 2019.
Globus-Harriss I., Gupta, V., Jung, C., Kearns, M., Mor- genstern, J., and Roth, A. Multicalibrated regression for downstream fairness. In Proceedings of the 2023 AAAI/ACM Conference on Al, Ethics, and Sociery, pp- 236, 2023a.
Kallus, N., Mao, X., and Zhou, A. Assessing algorithmic fairness with unobserved protected class using data com- bination, Management Science, 68(3):1959 (8(3):1959-198) 2022.
Mlobus-Harriss I., Harrison, D., Kearns, M., Roth, A., and Sorrell, Multicalibration as boosting for regression. arXiv preprint arXiv:230111376; 2023b.
Kim, J., Harper, A., McCormack, V., Sung, H., Houssami, N., Morgan, E., Mutebi, M., Garvey, G., Soerjomataram, I., and Fidler-Benaoudia, M. M. Global patterns and trends in breast cancer incidence and mortality across 185 countries. Nature Medicine, pp. 2025.
Glocker, B., Jones, C., Bernhardt, M., and Winzeck, S. Algorithmic encoding of protected characteristics in chest X-ray disease detection models. EiBioMedicine, 89, 2023.
Kim, M. P., Ghorbani, A., and Zou, J. Multiaccuracy: Black- box post-processing for fairesss in classification. In Pro- ceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 247-254-244 2019.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. Omnipredictors. In Braverman, M. (ed.), 13th Innovations in Theoretical Computer Science Con- ference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPles). Schloss Dagstubl- Leibaiz-ZZentrum für Informatik, 2022.
Lahoti, P., Beutel, A., Chen, J., Lee, K., Prost, F,, Thain, N., Wang. X., and Chi, E. Fairness without demograph- ics through adversarially reweighted learning. Advances in neural information processing systems, 33:728-740. 2020.
Gupta, M., Cotter, A.. Fard, M. M., and Wang, S. Proxy fairness. arXiv preprint arXiv: 1806. 1212, 2018.
Li, D., Bharti, B., Wei, J., Sulam, J., and Yi, H. Sex im- balance produces biased deep learning models for knee osteoarthritis detection. Canadian Association of Radiol- ogists Journal, 74(1):219-22) 221, 2023.
Hansen, D., Devic, S., Nakkiran, P., and Sharan, V. When is multicalibration post-processing necessary? In Advances in Neural Information Processing Systems, 2024.
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Obermeyer, Z. and Mullainathan, S. Dissecting racial bias in an algorithm that guides health decisions for 70 million people. In Proceedings of the conference on fairness, accountabilityy and transparency, pp. 89-89, 2019.
Hébert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. Multicalibration: Calibration for the (computationally- identifiable) masses. In International Conference on Ma- chine Learning, pp. 9939-1948. PMLR, 2018
of Science, W. H. and Policy, T. blueprint for an ai bill of rights, 2022. https: //wp:://wwww.. whitehouse, wtwpehusuu..oo/sttppp... gov/ostp/
The URL
ai-bill-of-rigg
Holstein, K., Wortman Vaughan, J.. Daumé III, H., Dudik, M., and Wallach, H. Improving faimess in machine learn ing systems: What do industry practitioners need? In Proceedings of the 2019 CHI conference on human fac- tors in computing systems, pp. 1-16, 2019.
Prost, F., Awasthi, P., Blumm, N., Kumthekar, A., Potter, T., Wei, L., Wang, X., Chi, E. H., Chen, J., and Beutel, A. Measuring model faimess under noisy covariates: A theoretical perspective. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pp. 873-883, 2021.
Huang, G., Liu, Z., Van Der Maaten, L.,, and Weinberger, K. Q. Densely connected convolutional networks. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Roth, A. Uncertain: Modern Topics in Uncertainty Estima- tion. 2022.
Imai, K. and Khanna, K. Improving ecological inference by predicting individual ethnicity from voter registration records. Political Analysis, 24(2):263-272, 2016.
Rudin, C., Wang, C., and Coker, B. The age of secrecy and unfairness in recidivism prediction. Harvard Data Science Review, 2(1):1, 2020.
10

---

Multiaccuracy and Multicalibration via Proxy Groups
Shailaja, K., Seetharamulu, B., and Jabbar, M. Machine learning in healthcare: A review. In 2018 Second in- ternational conference electronics, communication and aerospace technology (ICECA), pp. 910-914. IEEE, 2018.
Thomas, L.,, Crook, J., and Edelman, D. Credit scoring and its applications. SIAM, 2017.
United Nations Educational, and (UNESCO), C. O. Rec- ommendation on the ethics of artificial intelligence, 2021.
Wang, S., Guo, W., Narasimhan, H., Cotter, A., Gupta, M., and Jordan, M. Robust optimization for fairness with noisy protected groups. Advances neural information processing systems, 33:5190-5203, 2020.
Weissman, J. S. and Hasnain- Hasnain-Wynia, R. Advancing health care equity through improved data collection. New Eng- land Journal of Medicine, 364(24):2276-2277, 2011.
Yi, P. H., Bachina, P., Bharti, B., Garin, S. P., Kanhere, A., Kulkarmi, P., Li, D., Parekh, V. S., Santomartino, S. M., Moy, I.,, et al. Pitfalls and best practices in evaluation of ai algorithmic biases in radiology. Radiology, 315(2):
e241674, 2025.
Zafar, M. B., Valera, I., Gomez Rodriguez, M., and Gum- madi, K. P. Fairness beyond disparate treatment dis- parate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th international conference on world wide web. pp. 1171-1180, 2017.
Zhang, Y. Assessing fair lending risks using race/ethnicity proxies. Management Science, 64(1):178-197) 2018.
Zhao, T., Dai, E., Shu, K., and Wang, S. Towards fair classifiers without sensitive attributes: Exploring biases in related features. 2022.
Zhu, Z., Yao, Y., Sun, J., Li, H., and Liu, Y. Weak proxies are sufficient and preferable for fairness with missing sen- sitive attributes. In International Conference on Machine Learning, pp. 43258-43288 PMLR, 2023.

---

Multiaccuracy and Multicalibration via Proxy Groups
A. Additional Theoretical Results
Here we present a version of Theorem 5.1 for multiaccuracy.
Theorem A.I. Fix distribution D, initial model J, and set of proxy groups S. If a model satisfies
AE max
(f, 9) min (E)
(19)
MSE(f) S MSE(f)
(20)
then, will have smaller worst-case MA violation, i.e. {(f. & B(f.))
A proof of this result is provided in Appendix B.3.
B. Proofs
B.1. Proof Lemma 4.1
Proof. Throughout these proofs, denote
p Plx(X, Z) i,ğ(X) = j] and 12)(0) Pla(X,, = =i, = = u].
(21)
We begin with proving the result for multiaccuracy.
Step 1: Establishing the Multiaccuracy Bound
Fix distribution D and predictor f. Consider any group g E 9 and its corresponding proxy G. Then,
AED(f.g)
EXg(X, (X(( - Yi
(22)
Zlg(X, Z)((( Y) - -X( -
-Y)
(23)
Y3u (FXX - XX]
(24)
2)x(X, - Y) -(())(((())))) rリu + AED(f.9)
(25)
[[(((X, 2)- - -(x)) (f(X) - r3! + AEE
(26)
$ (X,, 2) 0(x) (xx) Y)I + AED(J.9)
(27)
< min (VElls(X,, Z) ((X) |1 [X) - 213,. Blla(X, - 8(X11) + (ED(f.9)
(28)
min
(VMSE(J) err(r)) err(ğ) + AED(J.))
(29)
Here applied the triangle inequality in line 24, Jensen's 's inequality in line 27, and Holder's inequality in line 28.
Step 2: Tightness of the Multiaccuracy Bound
We now show these bounds are tight. To be precise, we will prove that there exists joint distribution over the random variables (f(X), Y, gXx, Z), ((X) for which these bounds hold with equality.
Consider group g E 9 and corresponding proxy G. First, consider the scenario where MSE(f) S err(ğ) so that by the first result of Lemma 4.1 we have
AED(f.9) S AED(f.ğ) / err MSE(F).
(30)
Consider the following data generating process:
Conditioned on the event (g(X, Z) ). one has f(X) = Y.
12

---

Multiaccuracy and Multicalibration via Proxy Groups
Conditioned on the event (g(X,, 2) 1, 1x) 0}, one has that f(X) /MSE(/) Verr(t)
and Y 0,
10,1 so that err(ğ) = 19,00
Then,
- - Y)J - B(((X) - 21) + +(((X) - -Y (1(x 1,0(X) 0j0î,
(31)
ver(())
MSE(f).
(32)
Further,
- Y -
Y 9(X, Z) 1,)(X) 11 + E[f(X) - Y 19(X, 2) 0x,(
1]
(33)
0.
(34)
As result,
2)((X)))((() Y)] ( Y) + /er(gg) V VMSE(f)
(35)
( YY + Ver( /MSE(f).
(36)
Now, consider the scenario where MSE(f) err(g) so that by the first result Lemma 4.1 we have
AEp(f.g) AED(f.9) err
(37)
Consider the following data generating process:
Conditional on the event {,(X, Z) = ((X),, f(X) 2 Y
Conditional the event {g(X, Z) 1,9(X) 0), f(X) and Y 0.
/8,1 = so that err(î) = 14,00
Then,
2) -Y] = Y - 1,9()) 11H4, E[f(X) - Y 1)(X,2) 1.0(X) 0|p9,
(38)
= =]f((X) - Y -
1444, + err(g)
(39)
Further,
((((X)(((X) - = - 1 1)(x 1,0() = 14 E(((X) - ((x,2) =0,((X)
= =,
1]m8,1
(40)
=[((() - Y 1 1,0(X) 1/ 0.
(41)
In passing, note that requiring S(X) > Y above is much more than needed, but take this for simplicity. Moving on, and result,
(oo(X,2((((X) y(c
B((())((X)) - Y)] + err(g) (((X)(((X) - reI + +err(a).
(42)
13

---

Multiaccuracy and Multicalibration via Proxy Groups
We now prove the result for multicalibration.
Step 1: Establishing the Multicallibratinn Bound
Fix a distribution D and predictor f. Consider any group E 9 and its corresponding proxy 9 E G. Then,
ECEp(f.9) = E
- = v]
(43)
- oa
E
(X, (X) V)I m)
(44)
B((()(((X)) - ()I(() =
(45)
E
X)I(()- v)
( o1
+ ECEE
(46)
V)I = =0] B((X)((())) - ()I(X)= =01
< T
+ D.ECED(J.))
(47)
- -Y) - -x(x)(( - f)I(X) = = + +ECED(f.0)
E
(48)
9(X, ()(() -Y) -(X)0(( y) 1|1CKK= -r] =0]]
< E
B
+ -CCED(J,0)
(49)
8(x, (x(( rY -(x) - 83 + (F.E
E
(50)
E
- (0(X,2)- ((X)) (1(X) m/ (J.
(o(X,
(51)
< min (VBlle(X, - Y| Bl|o(X, 2) ((xx))) - ECED
(52)
min
(v MSE(f)) err(g.g). e EC
(53)
Here applied the reverse triangle inequality in (47), Jensen's 's inequality in line (49), and Holder's inequality in line (52).
Step 2: Tightness of the Multicalibration Bound
We now show these bounds are tight. To be precise, we will prove that there exists a joint distribution over the random variables (f Y, g(X, 2), ((X) for which these bounds hold with equality.
Consider group g E and its corresponding proxy S. First, consider the scenario where MSE(f) S err that by the first result of Lemma 4.1 we have
ECEp(f.g) < ECE + Verr(0) /MSE(f).
(54)
Consider the same data generating process used to establish the MA bound, AED(S, S AED /MSE(()) Then,
Elo(X, -
u|
E Dー
Elf(X) - - 11(() = v. = 1,0(X) = 1] 17,1
(55)
+ +Ef((X) - -Y = =e v. = L. = 0] pi. (()((v))
(56)
MSS(E)
E
11 (1))(w))
(57)
wm D1
err( (
())
u (1)0(1))
(58)
Verr(
/MSE())
1i.0 = (er(()))eer(()))
(59)
Verr(
14

---

Multiaccuracy and Multicalibration via Proxy Groups
Further,
- = = ,
-xxxx -- = 11.11111111 (1,1(0)
-
(60)
- -x1()) -, - 11,1116,11
(61)
=0
(62)
As result,
R Dn
Blg(XX - = o) = (X - -X))XX)))))) = m) (S) err
(63)
unDD
Now, consider the scenario where MSE > err(i) so that by the first result of Lemma 4.1 we have
ECEp(f.9) & ECE + err(g)
(64)
Consider the same data generating process used to establish the MA bound, (E)(J.g) (E)( err(ğ). Then,
E
= E aNDD
B[f(x) - Y f(x) = v, = 1.9(X) = 1] (v)
(65)
+ +[)((X) Y (f(x) u. v, = 1,0( = = 0] v1,0(t)
(66)
= E e-D,
B(x(x) - Y ff(x) = c. 9x, =) 1] (7, + n
(67)
E B(S(X) Y f(x) 2) -1 (v)
(68)
+
E
[x))
(69)
E
B[f(X) Y f(x) = v. 11 (f,1
+ Hî.0-
(70)
Further,
E
Elg(X) - -] = E D>
B[f(x) - Y f(x) = v,9(X,2) = -1)(()))))())))))))) = 1] 11,41,,100 (w)
(71)
+ +Eff(X) - Y f(x) -v,0(x,))= = 0,0(()) = 1] 16, (v)
(72)
= E wnDy
Bif(x) - Y f(x)= xx))= = 1,0(X) = 1] 1 (v)
(73)
As result,
Blg(X, -))() X)I((X= w| D
E onDD
- = =] + +er(())
(74)
The following bounds are tight in that we show there exists a distribution for which the bound is attained. The bounds can nonetheless be improved by assuming complete access to the marginal distributions over (f(X).Y.gXX)) and (x(X, 2), (()). In this case, one could derive tight bounds that agree with this observed information with techniques used in(Kallus al., 2022; Bharti et al., 2024) that rely on the Fréchet inequalities.
15

---

Multiaccuracy and Multicalibration via Proxy Groups
B.2. Proof of Theorem 4.2
Proof. We prove the result for multiaceuracy, Recall Lemma 4.1, which states that for any group g and its proxy g
AEp(f.9) S F(f.)) AED(f.g)
(75)
Thus, Vg E 9.
AEp(f.g) S ((f = max F(f.9) + AED(f.9)
(76)
This proves that f is (9, ( The proof for multicalibration follows an identical argument.
B.3. Proof of Theorem 5.1
Proof. Fix a distribution D, model ʃ. set of groups G and its corresponding proxies S. Recall by Theorem 4.2 that f is (G, mmulicciila where
((. = max min (err()), ffSE(f) err(ğ) + ECEp(f..))
(77)
DEG
First, note that for MSE(/) > err(g), the term
min
(rr((), v (J) err(ū)
(78)
constant with respect to MSE(/) and for MSE(S) S err(ğ) increases as MSE(ʃ) increases.
Now, suppose another model satisfies the following
ECE max (f, min ECE ECE (f,g) AE
(79)
MSE(f) & MSE(f).
(80)
Then,
(f.9) max min
err(ğ), V MSE(J) err(ğ)
ECE (f.9)
(81)
9E9
max
min
err(g)) (MSE(f) err
+ ECE (f.
(82)
gEg
min
(er(()) /MS( err(ğ)
ECE max (f,G)
(83)
GE9
max
min (err()), VMSE(f) err(g)
+ min ECE ÓEğ
(84)
gEg
max 9eg
min (er(()) / MS) err(i)
+ ECEE (J,9)
(85)
= ((.ğ).
(86)
The proof of the multiaccuracy result in Theorem A. follows an identical argument.
16

---

Multiaccuracy and Multicalibration via Proxy Groups
C. Additional Experiment Details
ACS Experiments
Models. the ACSIncome and PubCov experiments, we use Random Forests as the proxy models g. and train three types of models f: logistic regression, decision tree, and Random Forest.
along with their proxy errors reported in Tables 4 and All MA related results for the different models are presented in Appendices E.1 and E.2. Note, all of the models are MA with respect to G and G. As result, adjusting with respect to the proxies provides no benefit. All MC related results for the different models f are presented in Appendices E,4 and E.5. Note, the logistic regression and Random Forest models are highly multicalibrated with respect to 9 and g. As a result, adjusting provides no benefit. On the other hand, the decision tree is grossly uncalibrated with respect to some proxies, As a result, we see benefit in multicalibrating with respect to the proxies.
Results. The sensitive groups
C.2. CheXpert
Models. In the CheXpert experiment, we follow Glocker et al. (2023) and train DenseNet-12 121 model for the to predict race and sex. For the models f. we use three types. The first is decision tree classifier trained on features extracted from a DenseNet-121 model (Huang et al., 2017) pretrained on ImageNet (Deng et al., 2009). The second is a linear model (Breiman, 2001) trained the same features. The third DenseNet-12) model trained end-to-end the raw X-ray images.
The groups used along with proxy errors are reported in Table 6. All multiaccuracy related results for the different types of models f are presented in Appendix E.3. Note, all of the models are multiaccurate with respect to & and g. As result, adjusting provides no benefit. All multicalibration related results for the different types models are presented in Appendix E.6. Note, the logistic regression and fully trained DenseNet-121 models are highly multicalibrated with respect G and 9. As a result, adjusting provides no benefit. On the other hand, the decision tree is grossly uncalibrated with respect some proxies. As result,
Results.
benefit in multicalibrating with respect the proxies.
D. Additional Tables
Group
err(ğ)
Group
err(g)
Group
err
Men
0.027
Black Adults
0.044
Black Adults
0.044
Women
0.027
Black Women
0.027
Black Women
0.027
White
0.920
Women
0.000
Women
0.000
Asian
0.068
Never Married
0.000
Never Married
0.000
Black
0.039
American Indian
0,007
American Indian
0.007
Asian Men
0.039
Seniors
0,000
White Women
0.123
Asian Women
0.034
White Women
0.123
Multiracial
0.047
Black Men
0.021
Multiracial
0.047
White Children
0.002
Black Women
0.020
White Children
0.002
Asian
0.060
White Men
0.067
Asian
0.060
White Women
0.062
Table S. Sensitive groups and the proxy er- rors used in the ACSPubCov experiment
Table Sensitive groups and proxy er- rors used in the ACSIncome experiment
Table Sensitive groups and the proxy er- rors used in the CheXpert experiment
17

---

Multiaccuracy and Multicalibration via Proxy Groups
E. Additional Figures
E.I. Multiaccuracy results for ACSIncome
Vislations
Violations and
0.12
0.12
0.10
0.10
0.08
0.08
0.06
0.06
0.04
0.02
True Violation
Thee Violation
Upper Bound
Upper Bound
Groups
Groups
Figure B.I. AE(J 9). AE (S.g) g) (dotted red line), and worst violations (dotted blue line) of the original model f and adjusted model fut on ACSIncome. Here, is logistic regression.
MA Viclations and Bounds (Before Agjustmennt ent)
MA Vialations and Bounds (After Adjustmeett
0.32
0.12
0.10
0.08
0.08
ABlen.
0.06
0.06
0.04
0.04
0.02
True Violation
0.02
Tue Violation
Upper Bound
Upper
0.00
0.00
5 o
6
5
Figure B.2. AE( g). AE (f. g) (dotted red line), and worst case violations (dotted blue line) of the original model and adjusted model fut on ACSIncome. Here, f is decision tree.
(Beffore Adjustmentt
(After Adjustmentt)
0.12
0.12
0.20
0.10
0.08
ME 97
0.08
M015-0
0.06
Tue Violation
Upper Bound
Upper Bound
Groups
Groups
Figure B.3. AE(F, g). AE (f.g) (dotted red line), and worst case violations (dotted blue line) of the original model f and adjusted model far ACSIncome. Here, f is Random Forest.
18

---

Multiaccuracy and Multicalibration via Proxy Groups
E.2. Multiaccuracy results for ACSPubCov
Viclations Bounds (Bofore Adjustm ond)
(Atter Adjustmment)
0.07
0.07
0.08
0.00
0.05
0.04
0.04
0.03
0.03
0.02
0.02
True Violation
Upper Bound
Upper Bound
8 S
or
o"
4 Groups
Groups
Figure B.4. AE(S.g) 9). AE (J.g) (dotted line). and worst case violations (dotted blue line) of the original model f and adjusted model fat on ACSPubCov. Here, f is a logistic regression.
MA Viclations and Bounds (Beffore Adjustm eni)
MA Violetions and Bounds (Afteer Adjustmentt
0.08
0.07
0.07
0.08
0.06
AElfes
0.04
0.04
0.03
0.03
0.02
0.02
Violation
Violation
Upper Bound
Upper Bound
6.
4
Groups
Groups
Figure B.5. AE(f. g). AE (f.g) g) (dotted red line), and worst violations (dotted blue line) of the original model f and adjusted model fag on ACSPubCov. Here, f decision tree.
MA Viclations and Bounds (Beffrre Adjustmentt enntt
MA Violations and Bounds (After Asjustrrend)
0.08
0.07
0.07
0.06
0.06
0.04
0.04
0.03
0.03
0.01
The Violation
Upper Bound
Upper Bound
5
Groups
Groups
g) (dotted red line), and worst violations (dotted blue line) of the original model f and adjusted model fat ACSPubCov. Here, is Random Forest.
Figure B.6. AE(f.)) g). AE (f.g)
19

---

Multiaccuracy and Multicalibration via Proxy Groups
E.3. Multiaccuracy results for CheXpert
Viclations Bounds (Bofore Adjustmentt ond!
Violations and (Atter Adjustmment
0.08
0.00
0.06
NEffx. 07
0.06
4817 01
0.02
0.02
True Violation Upper Bound
Upper Bound
ot 4 6 g
3 S
OF Groups
Groups
Figure B.7. AE(J.)) g). AE (f.g) (dotted red line), and worst case violations (dotted blue line) of the original model f and adjusted model fut CheXpert. Here, f is logistic regression.
Violations and Bounds (Before Adjustment enti
Violations and Bounds Adjustmentt
0.08
0.08
ABfee. gl
Arttg)
0.06
0.04
0.02
0.02
True Viclation
True Violation Upper Bound
Bound
0"
g2>
Groups
Groups
Figure B.8. AE(f. g). AE (f. g) (dotted red line), and worst case violations (dotted blue line) of the original model f and adjusted model fag on Xpert Here, / decision tree.
MA Viclations and Bounds (Before Adjustm entt
MA Violations and Bounds (After Adjustmrert)
0.06
0.06
0.04
0.04
0.02
0.02
Viclation
True Violation Upper Bound
Upper Bound
0 o 6' 6
3
Groups
Groups
Pigure B.9. AE(F g). AET* (f-g) g) (dotted red line), and worst case violations (dotted blue line) of the original model and adjusted model fat on CheXpert. Here, f is DenseNet- 121 model.
20

---

Multiaccuracy and Multicalibration via Proxy Groups
E.4. Multicalibration results for ACSIncome
MC Viclations and Bounds Adjustment
Viclations and Bounds Adjustmmnt:
0.24
0.14
0.12
0.12
0.10
0.10
0.08
True Violation Upper Bound
ECEifen
0.08
True Violation
Upper Bourd
0.06
0.06
Groups
Groups
Figure B. ECE, ECE (dotted red line), and viola- tions (dotted blue line) of the original model f and adjusted model fag on ACSIncome, Here, f logistic regression.
MC Vislatiens and Bounds (Befbre Acuustment)
MC Violations and Bounds (Aiter Adjutmment
0.200
True Violation
0.200
True Violation
Bound
Upper Bound
0.150
0.150
80
0.125
ECEIT
0.125
0.100
0.100
0.075
0.075
0.025
0.025
Groups
Groups
Figure B. ECE. EcE (dotted red line). and worst viola- tions (dotted blue line) of the original model f and adjusted model fai ACSoncome. Here, f decision tree.
MC Vielations and Bounds (Before Agjustiennt ent)
MC Violetions and Bounds (Atter Adjustmeett)
0.14
0.14
0.32
0.08
Truc Violation
ECEifee
0.08
Tue Viclation Bound
0.06
0.06
0.02
0.02
3 6
6"
39
6" 4'
Figure 1. ECE, EaE (dotted red line), and worst case viola- tions (dotted blue line) of the original model and adjusted model fai on ACSIncome. Here, f is a Random Forest.
21

---

Multiaccuracy and Multicalibration via Proxy Groups
E.5. Multicalibration results for ACSPubCov
MC Viclations and Bounds (Before Adjustment
Viclations and Bounds Adjustmmnt:
0.08
0.08
ECEIfen g)
F2n0. 88
0.06
True Violation
0.06
True Violation
Upper Bound
Upper Bourd
0.04
0.04
6" Groups
Groups
Pigure B.13. ECE, ECE (dotted red line), and worst case viola- tions (dotted blue line) the original model and adjusted model Sag on ACSPubCov. Here, f is a logistic regression.
Vislations and Bourds
(After and
.... Upper Bound
0.15
True Violation Upper Bound
EcElGa:
0.30
0.10
0.05
0.05
Grmups
Figure B.14. ECE, ECE (dotted red line), and worst case viola- tions (dotted blue line) the original model and adjusted model faaj on ACSPubCov. Here, f is a decision tree.
(Before Adjustmense
(Atter Adjustmentt
0.32
0.12
0.20
0.10
0.08
0.08
ECEIfe:
0.06
Upper Bound
0.06
Upper Bound
0.04
0.04
0.02
0.02
Groups
Figure B.15. ECE, MaE (dotted red line), and worst case viola- tions (dotted blue line) of the original model f and adjusted model Say on ACSPubCov. Here, f is a Random Forest.
22

---

Multiaccuracy and Multicalibration via Proxy Groups
E.6. Multicalibration results for CheXpert
Viclations Bounds (Bofore Adjustmentt ond!
Viclations (Atter Adjustmentt
0.10
0.10
ECBfc. 0)
0.06
Upper Bound
0.06
Upper Bound
0.02
0.02
4 6
Groups
Groups
Figure B.16. ECE, ECE (dotted red line), and worst case viola- tions (dotted blue line) the original model f and adjusted model fwū on CheXpert. Here, f is logistic regression.
Violations
Viclations and Adjustment:
(Before adjustmentt enti
0.40
Violation
0.40
0.35
Upper Bound
0.35
Upper Bound
0.25
0.25
0.20
0.20
0.15
0.15
0.10
0.10
6"
9
Groups
Groups
Figure B.17. ECE, EcE (dotted red line), and worst case viola- tions (dotted blue line) of the original model f and adjusted model Say on Che Here, f a decision tree.
MC Viclations and Bounds (Before Adjustm entt
MC Violations and Bounds (After Acjustrreet)
0.08
0.08
Violation Bound
ECEEha
True Vielation
0.06
0.06
0.04
0.02
0.02
Groups
Pigure B.18. ECE, ECE (dotted red line), and worst case viola- tions (dotted blue line) of the original model and adjusted model fal on CheXpert. Here, f is DenseNet- 121 model.
23


Reviews:
[{"review_id": "UD4HksGbip", "reviewer": "Reviewer_LB2V", "summary": "This paper explores the problem of evaluating and achieving multiaccuracy (MA) and multicalibration (MC) when sensitive group information is missing. The authors address this challenge by learning proxy functions to predict group membership without direct access to sensitive attributes.\n1. Theoretical results: The paper establishes an upper bound on the evaluation error of MA and MC for the original groups in terms of the corresponding error on the proxy groups. Additionally, the authors propose an algorithm that post-processes a predictor to ensure multiaccuracy and multicalibration with respect to the proxy groups, which in turn guarantees these properties for the original groups.\n2. Empirical results: Experimental results demonstrate that post-processing based on proxy groups effectively reduces worst-case MA and MC violations for the original groups.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review! Our responses to your questions and concerns are below.\n\n**Concern 1: General Concerns around Worst-Case Violations**\n\nAs you correctly state, we establish upper bounds on the MA/MC violations across the true groups in terms of the violations on the proxies, the proxy errors, and the $MSE$ of $f$. We would like to add that \n\n1) We have established lower bounds using identical techniques for MA (and we believe the same hold for MC); we will include them in the revised version.\n2) The bounds are **tight**, i.e. there exists a distribution over $(f, Y, g, \\hat{g})$ such that the bounds hold with **equality**:\n\nW.l.o.g., consider the AE violation for a group $g$. Consider first $MSE(f) \\leq P(\\hat{g} \\neq g)$, so the upper bound is \n\n$$\n|AE(f, g)| \\leq |AE(f, \\hat{g})| + \\sqrt{MSE(f)}\\cdot\\sqrt{P(\\hat{g} \\neq g)}.\n$$\n\nAssume also that $MSE(f) > 0$ and $P(\\hat{g} \\neq g) > 0$ (i.e. not perfect predictors). The bound holds with equality if the data-generating process satisfies:\n\n1) $P(\\hat{g} \\neq g) = P(\\hat{g} = 0, g=1)$\n2) $f-Y  = \\lambda\\cdot(g - \\hat{g})$ where $\\lambda = \\sqrt{\\frac{MSE(f)}{P(\\hat{g} \\neq g)}}$\n\nOn the other hand, when $MSE(f) > P(\\hat{g} \\neq g)$, the bound is\n\n$$\n|AE(f, g)| \\leq |AE(f, \\hat{g})| + P(\\hat{g} \\neq g),\n$$\n\nWith analogous (but slightly more involved) steps, one can construct a distribution where this upper bound holds with equality. \n\nWe will include all these points in the revised version. Given these two facts, we believe that our claim —“If the worst-case violations are large, this suggests that $f$ may potentially be significantly biased or uncalibrated for certain groups”—is reasonable and hope the reviewer agrees.\n\nAdditionally, we agree that it is important to emphasize that Theorem 5.1 applies to the worst-case violation, and not the true violation. In our setting, the true violation cannot be evaluated; thus, one cannot provably reduce it. Yet, we can minimize the upper bound. The reviewer is correct that this will not reduce the actual violation, but we argue this is still an effective way to provide meaningful guarantees — as demonstrated in the experiments. We can modify $f$ such that the upper bound is less than $\\alpha$,  concluding that the *true violation* is also less than $\\alpha$. We will make sure to clarify this distinction in the revised manuscript.\n\n**Concern 2: Figures/Finite Sample Analysis**\n\nRecall the upper bound is a function of $MSE(f)$, $err(\\hat{g})$, and $ECE(f, \\hat{g})$. Here $f$ is the output of a learning algorithm that takes a training sample $S_{train}$, and the modified $f$ is the output of running the algorithm on a calibration set $S_{cal}$. To compute the upper bound, we simply compute sample estimates of all 3 quantities on a fixed held-out set and report the average over five train/calibration splits. Note that stating the theoretical results in terms of the distributional quantities is standard practice in this area of work [1,2,3].\n\nWe do not include a finite sample analysis in the manuscript but refer the readers to [2] where a complete finite sample analysis is done. The analysis repeatedly uses Chernoff bounds to show that, as long as the algorithms run on a finite sample of $n$ i.i.d samples from $\\mathcal{D}$, then the guarantees carry over to the true distribution with high probability when $n$ is sufficiently large. We will happily include the main results from [2] and explain their application to our setting in our revised appendix.\n\n**Concern 3: Lack of Algorithmic Innovation**\n\nWhile we do not introduce a new algorithm, we do not think this is a weakness. When trying to extend various fairness guarantees via proxies, other works have needed to provide new algorithms to control either the true violation or upper bounds [4,5] because the theory demanded it. Our theory clearly shows that a new algorithm is **not** needed, which we believe to be an elegant contribution.\n\n**Additional comments**\n\n1) Thank you for pointing out the typo in Theorem 5.3! It should be $T < \\frac{4}{\\alpha^2}$ rounds. We will correct this.\n2) Line 436 is correct. Since the models are already highly multicalibrated across the proxies, correcting more provides a minimal reduction in our bounds.\n\nThank you for your questions and comments! We hope we have addressed them in a clear and satisfactory manner.\n\n[1] \"Multicalibration for Confidence Scoring in LLMs\", Detomasso et al. ICML 2024.\n[2] \"Uncertain: Modern Topics in Uncertainty Estimation\", Roth 2022.\n[3] \"Multicalibration as Boosting for Regression\", Globus-Harris et al. ICML 2023\n[4] \"Estimating and Controlling for EOD via Sensitive Attribute Predictors\", Bharti et al. NeurIPS 2023.\n[5] \"Multiaccurate Proxies for Downstream Fairness\", Diana et al. FaccT 2022.", "claims_and_evidence": "1. Line 234 \"Conversely, if the worst-case violations are large, this suggests that f may potentially be significantly biased or uncalibrated for certain groups g\". Although the authors emphasizes the word \"potentially\", I still don't think it is a right claim to make in the theoretical section as they do not have a theorem that lower bound error on the original groups by the error of the proxy groups.\n2. For the claim made by authors after theorem 5.1, they should also emphasize that they guarantee they get is for the so-called \"worst-case\" violation in their bound analysis, but does not necessarily mean that the violation gets smaller. \nIn general, the authors should be careful to make it clear that the worst-case violations does not mean the actually violation, and also this worst-case violations might not be tight upper bound for certain cases.", "methods_and_evaluation_criteria": "Learning proxy functions is a natural and intuitive approach for this problem, and the chosen benchmark/dataset is appropriate. However, I am uncertain about how the upper bound bar in the figure is determined, whether it takes finite sample analysis into consideration.", "theoretical_claims": "I have checked all the proofs, and they appear to be correct. However, some theorems lack clear interpretations. As I previously pointed out, their theorems suggest that the \"worst-case\" error decreases, but the worst-case analysis may not be tight. Additionally, reducing worst-case violations does not necessarily imply a reduction in the true violation.\n\nFor instance, the bound in Theorem 5.3 might not be tight. The authors seem to suggest that achieving an \nepsilon error would require 1/epsilon^8 iterations, which appears overly pessimistic. I recommend that the authors carefully verify the result in Globus-Harris et al. (2023).\n\nMoreover, it would be beneficial if the authors included a finite-sample analysis.", "experimental_designs_or_analyses": "I have checked the soundness of the experiments, and the results appear solid. However, I have a few clarifications and suggestions:\n1. In line 436, the statement \"Notably, both models are approximately 0.03-multicalibrated with respect to the proxies\" might be incorrect. Should this refer to the original groups instead of the proxies?\n2. It would be helpful if the authors discussed how the predictor could be further calibrated with respect to the original groups in cases where it already exhibits small violations for the proxies. This could provide deeper insights into the limitations and effectiveness of the approach.\n3. Additionally, I would like clarification on how the upper bound in the figure is determined. Does it take finite-sample analysis into account, or is it simply computed using the evaluation error? Providing details on this would improve the interpretability of the results.", "relation_to_broader_scientific_literature": "The algorithm used to achieve multiaccuracy (MA) and multicalibration (MC) in this paper is based on the work of Roth (2022) and Globus-Harris et al. (2023), meaning the authors do not introduce a new algorithm. Their primary contribution lies in addressing the scenario where the sensitive attributes that define the groups are missing. While fairness under incomplete sensitive data has been studied in the context of other fairness metrics, this paper is the first to explore the problem specifically for MA and MC. Their approach leverages proxy functions to address this challenge.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The writing is clear and well-structured, making the paper easy to follow.\n2. This is the first work to study the use of proxy functions for achieving multiaccuracy (MA) and multicalibration (MC) in the setting where sensitive groups information is missing.\nWeaknesses:\n1. The paper lacks algorithmic innovation. Rather than introducing a new algorithm, the authors primarily adapt existing methods by applying them to proxy groups instead of the original groups. While this is a meaningful extension, it limits the novelty of their technical contributions.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. I would like clarification on how the upper bound in the figure is determined. Does it take finite-sample analysis into account, or is it simply computed using the evaluation error?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "He0bVjKq8R", "reviewer": "Reviewer_HMNE", "summary": "In this paper, the authors study the problem of fairness in ML. To be specific, they focus on a scenario where different groups are evaluated independently with respect to their accuracies and calibration errors (coined as Multiaccuracy and Multicalibration fairness in the literature). The literature has studied Multiaccuracy and Multicalibration in scenarios where sensitive attributes are available. The authors address this limitation by (i) providing theoretical bounds for Multiaccuracy and Multicalibration fairness if proxy attributes/groups are used and (ii) proposing/adapting algorithms to improve Multiaccuracy and Multicalibration fairness of ML algorithms without sensitive attribute information.\n\n## update after rebuttal\n\nI've read the comments by other reviewers and the rebuttal provided the authors. Therefore, I keep my original acceptance recommendation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review! We are glad you enjoyed the paper. Our responses to your questions and concerns are below.\n\n**Concern 1: Use of proxies**\n\nWe agree with the reviewer: proxy-sensitive attributes can be problematic as they introduce another source of error into an already sensitive issue. Nonetheless, note that there are settings where (i) this is inevitable (when ground-truth attributes aren't available/recorded), or (ii) when subjects wish to withhold their ground-truth sensitive data (e.g. for privacy reasons). In both these cases, we show that one can nonetheless provide precise guarantees on maximum fairness violations; thus, these proxies can be helpful. We will make sure to discuss these concerns in depth, the pros and cons of using proxies, in our revised version.\n\n**Concern 2: Figures**\n\nRegarding the comment that “the proxies exhibit some error, albeit small.”, we note that we are referring to the misclassification error of proxies, which are precisely reported in Tables 1-3 in the main text, along with Tables 4-6 in the Appendix. We could turn these tables into figures, if necessary, but we thought the tabular format to be sufficient.\n\nWe apologize for the lack of clarity in Figures 1-4. The x-axis refers to the group memberships, and the y-axis is the expected calibration error of each of the groups, $ECE(f,g)$. To make the figures more readable, we refer to the groups as $g_1, \\dots, g_k$, but we realize that it may be unclear which group each $g_i$ is referring to. We will certainly clarify in this revised version! \n\nAdditionally, the 2 lines refer to the actual violation (red) and upper bound (blue). We understand that the legend may be confusing. In the revised version, we will place “True Violation” directly above the dotted red line and “Upper Bound” directly above the blue line, making it clearer.\n\n**Additional comments**\n\nWhat is $v$ in the ECE definition?\n\nThe value $v$ refers to every value in $[0,1]$ that the predictor can take. For example, let $v = 0.3$. Then, the inner term in the ECE is just $|E[g(X,Z)(0.3 - Y)|f(X)=0.3]|$. That is, the group-wise error for all points $X$ where $f(X)=0.3$. The expected calibration error takes the average of this quantity over all $v$, where $v$ is sampled from the distribution of predictions made by $f$.\n\nTo be more clear, we will edit the manuscript with the following:\n\n\"Central to evaluating MC is the expected calibration error (ECE) for a group $g \\in \\mathcal{G}$\n\n$$ECE(f,g) = E_{v \\sim \\mathcal{D}_f}[|E[g(X,Z)(f(X)−Y)|f(X) = v]|]$$\n\nwhere the outer expectation is over $v \\sim \\mathcal{D}_f$, the distribution of predictions made by the model $f$ under $\\mathcal{D}$\"\n\nWe also thank you for catching the other typos! We will make sure to fix them in the revised manuscript.\n\nFinally, thank you for your questions and comments! We hope we have addressed them in a clear and satisfactory manner.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Partially.", "experimental_designs_or_analyses": "Yes, all of them.", "relation_to_broader_scientific_literature": "The literature has studied Multiaccuracy and Multicalibration in scenarios where sensitive attributes are available. The authors address this limitation by (i) providing theoretical bounds for Multiaccuracy and Multicalibration fairness if proxy attributes/groups are used and (ii) proposing/adapting algorithms to improve Multiaccuracy and Multicalibration fairness of ML algorithms without sensitive attribute information.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n+ Addressing bias and fairness in scenarios where sensitive attributes are unavailable is an important challenge in ML fairness.\n+ Multiaccuracy and Multicalibration are important fairness definitions.\n+ The paper provides theoretical supports as well as experimental results on several datasets.\n+ Overall, the paper is very well written and easy to follow.\n\nWeaknesses:\n\nI am generally happy with the paper but I would like to state a few things:\n\n1. I am generally unhappy with the proxy attribute approach relying on a separate model trained to estimate the sensitive attributes/groups. We are introducing a source of error into a very sensitive issue. If there turns out to be low fairness, it is not clear what the source of the problem is. \n\n2. \"the proxies exhibit some error, albeit small.\" => For completeness, please provide these figures.\n\n3. Figs 1-4 do not have the labels for the axes and the lines. This makes it difficult to compare the subplots and evaluate the results.", "other_comments_or_suggestions": "Minor comments:\n\n- What is v in the ECE definition on Line 186?\n- \"data-scare regimes\" => \"data-scarce regimes\".\n- \"notefirst that\" => \"note first that\".", "questions_for_authors": "Please see Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a9NnX07rd8", "reviewer": "Reviewer_VC5A", "summary": "The paper \"Multiaccuracy and Multicalibration via Proxy Groups\" addresses the challenge of ensuring fairness in predictive machine learning models when sensitive group data is missing or incomplete. The authors focus on two fairness notions—multiaccuracy and multicalibration—which aim to ensure that model predictions are unbiased and well-calibrated across groups.\nThe paper demonstrates that proxy-sensitive attributes (features correlated with true sensitive attributes) can be used to derive actionable upper bounds on the true multiaccuracy and multicalibration violations. This allows practitioners to assess worst-case fairness violations even when true sensitive group data is unavailable.\nThe authors show that enforcing multiaccuracy and multicalibration using proxy-sensitive attributes can significantly mitigate fairness violations for the true (but unknown) demographic groups. They introduce computational methods to adjust models to satisfy these fairness criteria.\nFinally, the study evaluates the proposed methods on multiple datasets, including ACSIncome, ACSPublicCoverage, and CheXpert (a medical imaging dataset). The results demonstrate that enforcing fairness across proxies leads to substantial reductions in worst-case fairness violations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! We are glad you enjoyed the paper. Our responses to your questions and concerns are below.\n\n**Concern 1: Validity of some claims**\n\nWe apologize if some claims seem unsupported; let us clarify: \n\n*Claim 1: \"even when sensitive information is incomplete or inaccessible, proxies can extend approximate multiaccuracy and multicalibration protections in a meaningful way\"*\n\nWith proxies, we can establish non-trivial upper bounds on true MA/MC violations. Denote this bound as $B$. Then, while one cannot determine the exact violations, one can still provably assert that the model is $B$-multiaccurate/multicalibrated, providing a meaningful guarantee on the MA/MC violations of $f$. We will reword the statement to accurately reflect this point.\n\n*Claim 2: \"our methods offer, for the first time, the possibility to certify and correct multiaccuracy and multicalibration without requiring access to ground truth group data\"*\n\nYou are correct that other works have also explored fairness by bounding fairness violations using proxies - as we cite in our manuscript. However, all of these works were concerned with parity- or group-based notions of fairness, such as demographic parity, equalized odds, equal opportunity, etc. Our work is the first to use proxies to bound MA/MC violations, which are quite different notions of fairness that are not parity-based [1].\n\n*Claim 3: \"Applying our methods ensures stronger fairness guarantees\"*\n\nWe apologize that this claim suggests our methods allow us to control the true MA/MC violations. What we meant to convey is that our methods allow us to get stronger guarantees on the worst-case violations, which we believe (and demonstrated) can be practically useful. This is because, in our setting, the true violation cannot be evaluated. However, if one can modify $f$ such that our upper bound is less than $\\alpha$, we can conclude that the true violation is also less than $\\alpha$. Thus, our theory and methods are useful. We will make sure to clarify this point in the revised manuscript.\n\n**Concern 2: Potential failure of proxies**\n\nWe believe there might be a slight misunderstanding here. In this work, we make no assumptions on how good or bad the proxies are. Additionally, our goal is not to assess how the true MA/MC guarantee changes as the proxies change. In the demographically scarce setting that we study, the true MA/MC violations cannot be identified/determined. Thus, we focus on providing bounds on these violations, which can be interpreted as worst-case violations. When analyzing the bounds (see e.g. Lemma 4.1), it's clear that if the proxies are bad, then our bounds will be naturally large, indicating the MA/MC violations could be large as well. Likewise, as the proxies become more accurate, our bound collapses to the true violation. \n\nRegardless of the quality of the proxies, our bounds always hold (i.e. we don't require any assumptions on them), and our methodology will always reduce the worst-case violation. Finally, the reason we do not benchmark against other methods is that our focus was not on studying *how* to build proxies for accurate fairness estimation. Instead, our focus is to study how to obtain practical MA/MC guarantees with *any set of proxies* that might be available via a general worst-case analysis.\n\n**Concern 3: questions about experiments**\n\nWe agree that a synthetic experiment would be good! It would allow us to showcase when our bounds are tight (see rebuttal to reviewer LB2V) and analyze how the true fairness violations and proxy-fairness violations differ as a function of the proxy error. We plan to include a synthetic example in the revised manuscript. Thank you for the great suggestion!\n\nAdditionally, you observe that some proxy groups (e.g., “Women” in Table 1 with zero error) may be too accurate, suggesting that another feature (e.g., pregnancy status ?) strongly correlates with the sensitive attribute. This is correct! This point comes to illustrate that in many real-world scenarios, even without observing $Z$, we can learn highly accurate proxies and use them to provide meaningful fairness estimates via worst-case analysis.\n\n**Additional comments**\n\n*Definition of Multicalibration*\n\nThank you for pointing this out! You are correct in saying that the definition of multicalibration is different from the one proposed in [1]. The one we use is also referred to as \"multicalibration\" in other works [2,3] but, to be more precise, it should be referred to as approximate-multicalibration, or multicalibration in expectation. We will make this distinction very clear in the revised manuscript.\n\n[1] \"Calibration for the (Computationally-Identifiable) Masses\", Úrsula Hébert-Johnson et al. ICML 2018.\n[2] \"Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration\", Gopalan et al.. NeurIPS 2023.\n[3] \"Multicalibrated Regression for Downstream Fairness\", Globus-Harris et al. AIES 2023.", "claims_and_evidence": "Some claims are well supported.\n1) The authors derive provable upper bounds on multiaccuracy and multicalibration violations using proxy-sensitive attributes. These bounds are mathematically justified and clearly stated in Theorem 4.2 and Lemma 4.1. The theoretical results align with known fairness literature, and the derivations appear sound.\n2) The authors present two algorithms (Multiaccuracy Regression and Multicalibration Boosting) that adjust models based on proxy attributes to reduce fairness violations. Theoretical results (Theorem 5.1 and Theorem 5.3) prove that these algorithms reduce worst-case violations while maintaining or improving predictive performance.\n3) Empirical results on ACSIncome, ACSPublicCoverage, and CheXpert datasets demonstrate that the proposed methods successfully reduce fairness violations. Figures 1–4 illustrate reductions in worst-case multicalibration errors, showing that fairness guarantees improve after post-processing.\nNevertheless, some claims are still non-supported. For instance, the very last sentence of the introduction is \"Even when sensitive information is incomplete or inaccessible, proxies can extend approximate multiaccuracy and multicalibration protections in a meaningful way.\" I did not see an explicit discussion on that point Also (see discussion below), \"our methods offer, for the first time, the possibility to certify and correct multiaccuracy and multicalibration without requiring access to ground truth group data\". I think that some related research on fairness with partially observed sensitive attributes suggests that bounding fairness violations using proxies has been explored before, such as\nAwasthi, P., Kleindessner, M., and Morgenstern, J. Equalized odds postprocessing under imperfect group information. In International Conference on Artificial Intelligence and Statistics, pp. 1770–1780. PMLR, 2020.\nor \nBharti, B., Yi, P., and Sulam, J. Estimating and controlling for equalized odds via sensitive attribute predictors. Advances in neural information processing systems, 36, 2024.\nAnd finally, at the end of section 5, it is claimed that \"Applying our methods ensures stronger fairness guarantees,\" but while post-processing reduces fairness violations with respect to proxies, it does not guarantee fairness with respect to the true sensitive attributes (which remain unobserved).", "methods_and_evaluation_criteria": "The methods assume that proxy attributes are sufficiently good approximations of true sensitive attributes. However, the paper does not systematically test when proxies fail or lead to misleading fairness estimates. A stronger evaluation would vary proxy errors to test robustness.\nThe paper does not benchmark against other fairness estimation techniques that work with missing sensitive data (e.g., Bayesian imputation, adversarial debiasing). Adding comparisons would help assess whether proxy-based methods are superior, complementary, or limited in certain contexts.\nFurther, since fairness bounds depend on proxy quality and sample size, reporting confidence intervals or uncertainty estimates would make the results more robust.", "theoretical_claims": "Yes, all of them. The mathematics are rather straightforward", "experimental_designs_or_analyses": "I noticed the lack of a controlled synthetic dataset. There is no dataset where ground truth fairness violations are explicitly known. This makes it impossible to verify whether proxy-based fairness estimates accurately reflect reality. A synthetic dataset (where fairness violations are designed and known) could have served as a check.\nSome proxy groups (e.g., “Women” in Table 1 with zero error) may be too accurate, suggesting that another feature (e.g., pregnancy status ?) strongly correlates with the sensitive attribute.", "relation_to_broader_scientific_literature": "When sensitive attributes are missing or incomplete, fairness evaluation becomes difficult, and several approaches have been proposed. Important references are given.", "essential_references_not_discussed": "The definition of multicalibration used here seems to be weaker than that of the original work \nHebert-Johnson, U., Kim, M., Reingold, O., &amp; Rothblum, G. (2018). Multicalibration: Calibration for the (computationally-identifiable) masses. In J. Dy &amp; A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning (Vol. 80, pp. 1939–1948).\nIt is important to explicitly clarify this distinction and its implications early in the paper, particularly the relationship between the definition based on the ECE and the definition (3.2) of multicalibration in Hebert-Johnson et al. (2018).\nAdditionally, the derived upper bounds should be explicitly linked to this weaker definition of multicalibration.", "other_strengths_and_weaknesses": "The paper is very interesting.\nThe fairness bounds are derived under the assumption that proxy attributes adequately approximate true sensitive attributes, but this assumption is never explicitly validated. Furthermore, it does not explore how fairness guarantees degrade when proxies are inaccurate.\nIt does not benchmark against other methods for fairness estimation without sensitive attributes, such as Bayesian imputation for fairness estimation (as in Chen et al., 2019) or worst-case fairness estimation (as in Kallus et al., 2022)", "other_comments_or_suggestions": "see previous box", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZTYNuwL11K", "reviewer": "Reviewer_hLPe", "summary": "The authors propose way to measure multicalibration/multiaccuracy by leveraging proxies (that way is to necessary to have access to the data) in order to compute worst case scenarios (formalized as an upper bound on their proposed metrics). They show that postprocessing model to satisfy multicalibration and multi-accuracy across proxies ends up in a reduction of the worst case (the computed upper bounds) violations.\n\nThey prove in theorem 4.2 how the multi-calibration/multi-accuracy of a model with respect to G is upper bounded with the multi-calibration/multi-accuracy with respect to the proxy. \n\nThe experimental results back up the developed theory .\n\nWeaknesses:\n- The last result, how the standard post-processing for multicalibration on proxy groups reduces the worst case could be a corollary from the main result (theorem 4.2). Is not clear to me why to devote a whole section to introduce standard procedures.\n- For me there is a mismatch on the motivation the authors used for using proxy-groups and their methods. They claim using population level values allows for better privacy (which I agree) but then they present a method which still needs individual level data about the proxy groups. Moreover, given that the final algorithm is the standard postprocessig to achieve multicalibration, the only real information that is being omitted are which ones were the original groups of interests.\n\nStrengths:\n- The main result is interesting and timely. The experiments are well thought for backing their claims and usefulness of their approach of using proxy groups.\n- The method is dependent both on the soundness of the proxies and the quality of the model.\n\nOverall I think the idea is good but the paper has very superficial analysis, again section five is superfluous. Perhaps will be better to study further the relationship between the quality of the model vs the quality of the groups, obtaining thus a result akin to the optimal bound that the practitioner can use as a reference for when to improve their proxies or when to improve their model.\n\nFinally, although the experiments are sound, is not clear to me how they improve fairness. I would like to see frorm a decision making point of view, how the proposed method would be used in real life.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! \n\n**Concern 1: Motivation and Method Mismatch**\n\nWe believe there might be a misunderstanding of the motivation behind our work - we apologize if it was not sufficiently clear.\n\nOur goal is to develop a predictor $f$: $\\mathcal{X} \\rightarrow [0,1]$ that is multiaccurate/multicalibrated across a set of sensitive groups $\\mathcal{G} = \\set{g: \\mathcal{X} \\times \\mathcal{Z}: \\rightarrow \\set{0,1}}$. However, we do not observe sensitive information $Z$ and instead have access to the marginal distribution over features $X$ and labels $Y$, denoted as $\\mathcal{D}_{\\mathcal{X}\\mathcal{Y}}$. Thus, note that once cannot evaluate the true MA/MC violations with respect to the true grouping functions $g \\in \\mathcal{G}$ since they are functions of unobserved $Z$. This is a common and important problem often seen in healthcare and government applications [1,2].\n\nThus, we employ the popular approach of using proxies [3,4], denoted as $\\hat{g}: \\mathcal{X} \\rightarrow \\set{0,1}$, of the true groups $g$. We show that with proxies (and their misclassification rates), while we can’t measure the MA/MC violations over the true groups, we can provide upper bounds that certify that their worst-case violations are below a given level. Moreover, we show that the worst-case bound is actionable; i.e. it can be reduced by making $f$ multiaccurate/multicalibrated with respect to the groups defined by the proxies. This is useful because:\n\n 1) If we can ensure that the worst-case violation  $< \\alpha$, then the true violation (across the true, unobserved group) is $< \\alpha$ as well! \n\n2) We do not need to develop a new algorithm, and instead can leverage existing ones that generate models that are multiaccurate/multicalibrated for any arbitrary set of groups.\n\nIn conclusion, one can get *approximate* MA/MC guarantees via reducing worst-case violations.\n\nWe are not trying to “claim that using population values allows for better privacy”, and apologize if this was not clear. \n\nAdditionally, the reviewer asks, “They present a method which still needs individual-level data about the proxy groups?”. Note that the algorithms take as input any set of groups and, as currently presented, there are multiple instances of $g(X, Z)$ written. We see how this could be confusing, as it implies that we need access to $Z$. However, we want to clarify that when using the proxies, all instances of $g(X, Z)$ are replaced by $\\hat{g}(X)$. As a result, with the proxies as inputs to the algorithms, all sensitive information $Z$ is naturally omitted. \n\n**Concern 2: Need for section 5**\n\nWe kindly disagree that section 5 is superficial.  For many readers not familiar with the literature, it may not be immediately clear from Theorem 4.2 how post-processing for multicalibration on proxy groups would reduce the worst-case violation, and to what level $\\alpha$ one needs to multicalibrate. Our theorem makes this clear. Importantly, Section 5 shows that enforcing MA/MC does not degrade the MSE, which we need to ensure that our bounds get smaller when enforcing MA/MC across the proxies.\n\n**Additional Questions/Concerns**\n\n*Although the experiments are sound, is not clear to me how they improve fairness. I would like to see from a decision-making point of view, how the proposed method would be used in real life*\n\nThe notions of fairness we are focused on are multiaccuracy/multicalibration [5]. Our theory and experiments clearly show that these notions of fairness (their worst-case violations) can be provably reduced. We believe this is very useful: Suppose one needs to build a model that is $\\alpha$-MC across the true groups. With our results, we can reduce the worst-case violation and, if it is less than $\\alpha$, then we know the true violation is less than $\\alpha$ as well - without requiring knowledge of the true groups! \n\n*Is there a way to know when to refine the proxies versus when it is more beneficial to instead improve the accuracy of the model?*\n\nBy \"beneficial\", does the Rev. mean reducing the worst-case bounds? Based on our results, neither is more beneficial than the other since improving the proxies or improving the accuracy of $f$ will always reduce the bound. Additionally, multicalibrating with respect to the proxies **will** reduce the bound.\n\nThank you for your questions and comments. We hope we have addressed them in a clear and satisfactory manner, and we'll be happy to address any outstanding questions!\n\n[1] \"Advancing healthcare equity through improved data collection\", J.S. Weissman et al. New England Journal of Medicine, 2011.\n[2] \"Improving fairness in machine learning systems: What do industry practitioners need?\", K. Holstein et al. CHI 2019.\n[3] \"Using Bayesian imputation to assess racial and ethnic disparities in pediatric performance measures\", D. Brown et al. Health services research 2016.\n[5] \"Calibration for the (Computationally-Identifiable) Masses\", Úrsula Hébert-Johnson et al. ICML 2018.", "claims_and_evidence": "The theory results are well presented, correctly proved and backed by relevant experiments.", "methods_and_evaluation_criteria": "They do.", "theoretical_claims": "Th proofs are correct.", "experimental_designs_or_analyses": "The experiments are well thought and are relevant for the paper.", "relation_to_broader_scientific_literature": "See weakness in the summary section", "essential_references_not_discussed": "Not to my knowledge", "other_strengths_and_weaknesses": "See weakness in the summary section", "other_comments_or_suggestions": "...See weakness in the summary section", "questions_for_authors": "- Is there a way to know when to refined the proxies versus when is more beneficial to instead improve the accuracy of the model?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of ensuring multiaccuracy and multicalibration using "proxy" groups, i.e., when access to exact group-denoting labels are not available, but a function that "predicts" group measurement is available. Overall, the results are a relatively direct extension of existing work in multiaccuracy and multicalibration, with the additional 'twist' of lack of access to group-denoting information.

The reviewers were split on the merits of the paper. Reviewer LB2V found the novelty somewhat limited, with the proposed algorithms being straightforward extensions of, e.g., boosting algorithms existing in the literature. Reviewer hLPe also noted that the results could be improved to have greater relevance for practitioners (e.g., when to improve the model vs. the proxy scorer).

The other two reviewers were more positive, though reviewer VC5A noted that the paper misses comparison with basic data imputation techniques.

Overall, I found the messaging of this paper confusing. One of the main points frequently made in the multiaccuracy and multicalibration literature is that pre-defined population groups are not required -- even if only defined via proxy variables. The goal in this line of work is to automatically outline "computationally identifiable groups" where the model errs, instead of relying on pre-defined group attributes (variable Z in the paper). I understand that the authors still optimize over a group of functions over X and Z, though they also assume a 'proxy developer' with explicit access to (X,Z) samples. This seems to go against the spirit of the multiaccuracy and multicalibration literature.

Though the paper is a relatively direct extension of existing work on multiaccuracy and multicalibration, it still presents a solid theoretical development and experiments, as recognized by the reviewers. However, the limited novelty limits the potential impact of the contribution. I encourage the authors to take the reviewers comments into account.
Decision: Accept (poster)