Multiaccuracy and Multicalibration via Proxy Groups

Thank you for the review!

Concern 1: Motivation and Method Mismatch

We believe there might be a misunderstanding of the motivation behind our work - we apologize if it was not sufficiently clear.

Our 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].

Thus, 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:

1. If we can ensure that the worst-case violation $< \alpha$, then the true violation (across the true, unobserved group) is $< \alpha$ as well!

2. 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.

In conclusion, one can get approximate MA/MC guarantees via reducing worst-case violations.

We are not trying to “claim that using population values allows for better privacy”, and apologize if this was not clear.

Additionally, 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.

Concern 2: Need for section 5

We 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.

Additional Questions/Concerns

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

The 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!

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?

By "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.

Thank 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!

[1] "Advancing healthcare equity through improved data collection", J.S. Weissman et al. New England Journal of Medicine, 2011. [2] "Improving fairness in machine learning systems: What do industry practitioners need?", K. Holstein et al. CHI 2019. [3] "Using Bayesian imputation to assess racial and ethnic disparities in pediatric performance measures", D. Brown et al. Health services research 2016. [5] "Calibration for the (Computationally-Identifiable) Masses", Úrsula Hébert-Johnson et al. ICML 2018.

Thank you for the review! We are glad you enjoyed the paper. Our responses to your questions and concerns are below.

Concern 1: Validity of some claims

We apologize if some claims seem unsupported; let us clarify:

Claim 1: "even when sensitive information is incomplete or inaccessible, proxies can extend approximate multiaccuracy and multicalibration protections in a meaningful way"

With 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.

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"

You 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].

Claim 3: "Applying our methods ensures stronger fairness guarantees"

We 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.

Concern 2: Potential failure of proxies

We 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.

Regardless 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.

Concern 3: questions about experiments

We 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!

Additionally, 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.

Additional comments

Definition of Multicalibration

Thank 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.

[1] "Calibration for the (Computationally-Identifiable) Masses", Úrsula Hébert-Johnson et al. ICML 2018. [2] "Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration", Gopalan et al.. NeurIPS 2023. [3] "Multicalibrated Regression for Downstream Fairness", Globus-Harris et al. AIES 2023.

Thank you for your careful review! We are glad you enjoyed the paper. Our responses to your questions and concerns are below.

Concern 1: Use of proxies

We 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.

Concern 2: Figures

Regarding 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.

We 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!

Additionally, 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.

Additional comments

What is $v$ in the ECE definition?

The 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$.

To be more clear, we will edit the manuscript with the following:

"Central to evaluating MC is the expected calibration error (ECE) for a group $g \in \mathcal{G}$

$ECE(f,g) = E_{v \sim \mathcal{D}_f}[|E[g(X,Z)(f(X)−Y)|f(X) = v]|]$

where the outer expectation is over $v \sim \mathcal{D}_f$, the distribution of predictions made by the model $f$ under $\mathcal{D}$"

We also thank you for catching the other typos! We will make sure to fix them in the revised manuscript.

Finally, thank you for your questions and comments! We hope we have addressed them in a clear and satisfactory manner.

Thank you for the thoughtful review! Our responses to your questions and concerns are below.

Concern 1: General Concerns around Worst-Case Violations

As 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

1. 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.
2. The bounds are tight, i.e. there exists a distribution over $(f, Y, g, \hat{g})$ such that the bounds hold with equality:

W.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

$$|AE(f, g)| \leq |AE(f, \hat{g})| + \sqrt{MSE(f)}\cdot\sqrt{P(\hat{g} \neq g)}.$$

Assume 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:

1. $P(\hat{g} \neq g) = P(\hat{g} = 0, g=1)$
2. $f-Y = \lambda\cdot(g - \hat{g})$ where $\lambda = \sqrt{\frac{MSE(f)}{P(\hat{g} \neq g)}}$

On the other hand, when $MSE(f) > P(\hat{g} \neq g)$, the bound is

$$|AE(f, g)| \leq |AE(f, \hat{g})| + P(\hat{g} \neq g),$$

With analogous (but slightly more involved) steps, one can construct a distribution where this upper bound holds with equality.

We 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.

Additionally, 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.

Concern 2: Figures/Finite Sample Analysis

Recall 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].

We 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.

Concern 3: Lack of Algorithmic Innovation

While 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.

Additional comments

1. Thank you for pointing out the typo in Theorem 5.3! It should be $T < \frac{4}{\alpha^2}$ rounds. We will correct this.
2. Line 436 is correct. Since the models are already highly multicalibrated across the proxies, correcting more provides a minimal reduction in our bounds.

Thank you for your questions and comments! We hope we have addressed them in a clear and satisfactory manner.

[1] "Multicalibration for Confidence Scoring in LLMs", Detomasso et al. ICML 2024. [2] "Uncertain: Modern Topics in Uncertainty Estimation", Roth 2022. [3] "Multicalibration as Boosting for Regression", Globus-Harris et al. ICML 2023 [4] "Estimating and Controlling for EOD via Sensitive Attribute Predictors", Bharti et al. NeurIPS 2023. [5] "Multiaccurate Proxies for Downstream Fairness", Diana et al. FaccT 2022.