Calibration for the (Computationally-Identifiable) Masses

Introduction

Fueled by rapidly growing data sets and by breakthroughs in machine learning, algorithms are informing decisions that affect all aspects of life. From news article recommendations to criminal sentencing decisions to healthcare diagnostics, increasingly algorithms are used to make predictions about individuals. Often, the predictions of an algorithm form the basis for deciding how to treat these individuals (suggesting a conservative Op-Ed, approving early parole, or initiating chemotherapy). A potential risk is that these algorithms – even given access to unbiased ground truth data – might discriminate against groups of individuals that are protected by law or by ethics. This paper aims to mitigate such risks of algorithmic discrimination.

We consider algorithms that predict the probabilities of events occurring for individuals. For example, a financial institution may be interested in predicting the probability that an individual will repay a mortgage. The institution may have at its disposal a large array of information for each individual (as well as historic data and global information such as financial and political trends). But as thorough as the company may be, a significant level of uncertainty will remain. Just as we wouldn’t expect to be able to predict with absolute certainty whether it will rain on a particular day a year from now, the financial institution wouldn’t expect to predict with absolute certainty whether an individual will repay a loan. Thus, we consider algorithms that output, for every individual $i$, a prediction $x_{i}$ of the probability that the event will occur for $i$; we call the mapping from individuals to probabilities a predictor.A predictor can be used for regression or, when paired with randomized rounding, for binary classification.

Our focus in this paper is mitigating biases that may arise as an algorithm analyzes given data – specifically, as the algorithm learns a predictor from data. Continuing the above example, suppose that in a particular protected community $S$, on average, individuals are financially disadvantaged and are unlikely to repay a loan. A machine-learning algorithm that aims to optimize the institution’s returns might devote resources to learning outside of $S$ – where there is more opportunity for gains in utility – and assign a fixed, low probability to all $i\in S$. Such an algorithm would discriminate against the qualified members of $S$. If $S$ is an underrepresented subpopulation, this form of discrimination has the potential to amplify $S$’s underrepresentation by refusing to approve members that are capable of repaying the loan.

Focusing on such concerns, we investigate a notion we call multicalibration. Multicalibration aims to mitigate discrimination that arises in the process of learning a predictor from given data. In a nutshell, multicalibration guarantees highly-accurate predictions for every subpopulation of individuals identified by a specified collection ${\cal C}$ of subsets of individuals. While our results hold for any set system ${\cal C}$, one natural way to think about ${\cal C}$ is as a collection of subsets defined by a family of boolean functions. That is, for each $S\in{\cal C}$, we consider a function $c_{S}:{\cal X}\to\left\{0,1\right\}$, where $c_{S}(i)=1$ if and only if $i\in S$. In particular, we will be most interested in considering families of boolean functions that can be represented by some bounded computational circuit class – for instance, conjunctions of a small number of boolean features or small decision trees. In the mortgage repayment example above, if the class of qualified members of $S$ can be identified by a circuit $c\in\cal C$, then the predictions made on qualified members of $S$ must be accurate, and the prediction algorithm cannot ignore / discriminate against these individuals. We emphasize that the class $\cal C$ can be quite rich and, in particular, can contain many overlapping subgroups of a protected group $S$. In this sense, multicalibration captures the notion of calibration for all computationally-identifiable subsets, where the notion of computational-identifiability is parameterized by the expressiveness of ${\cal C}$.

We present a simple, general-purpose algorithm for learning a predictor from a small set of labeled examples that is multicalibrated with respect to any given class $\cal C$. The algorithm is an iterative method, similar to gradient descent, and can be viewed as a form of no-regret online optimization. While the powerful online learning framework is exceptional in its broad applicability, a number of subtleties arise when learning a multicalibrated predictor that we must deal with. In particular, the definition of calibration refers to sets of individuals defined by the values output by the predictor. This leads to two key challenges. First, we must deal with an appropriate notion of discretization of the range of real-valued outputs; this challenge is mostly technical. Secondly, the fact that we want to update sets of predictions defined by the current predictions means that any reduction to the online learning framework is inherently an adaptive analysis procedure; as such we need to bring in machinery from the literature on differential privacy and adpative data analysis in order to guarantee good generalization from a small number of examples.

While we place no restrictions on the model class of the learned predictor, we show that implicitly the algorithm learns a model that provably generalizes well to unseen data, which may be of independent interest. We demonstrate this implicit generalization by viewing the learning algorithm as an adaptive data analysis algorithm and showing that the predictions we learn are highly compressible. In the language of circuit complexity, we show that we can build a circuit, only slightly larger than the circuits from ${\cal C}$, that implements the learned predictor. As a corollary, the learned predictor is efficient in both space to represent and time to evaluate.

We also study the computational complexity of learning multicalibrated predictors for more structured classes ${\cal C}$. We show a strong connection between the complexity of learning a multicalibrated predictor and agnostic learning [Hau92, KSS94]. In the positive direction, if there is an efficient (weak) agnostic learner [KMV08, Fel10] for a class $\cal C$, then we can achieve similarly efficient multicalibration with respect to sets defined by $\cal C$. In the other direction, we show that learning a multicalibrated predictor on sets defined by ${\cal C}$ is as hard as weak agnostic learning on ${\cal C}$. In this sense, the complexity of learning a multicalibrated predictor with respect to a class ${\cal C}$ is equivalent to the complexity of weak agnostic learning on ${\cal C}$.

We begin by elaborating on our setting. The remainder of the introduction is structured as follows. In Section 1.2 we elaborate on the notion of multicalibration and on its relationship to other notions in the larger context of fairness. We outline our main results on learning multicalibrated predictors in Section 1.3. We further elaborate on related work and on future directions in Section 1.4. Finally, we provide a brief overview of techniques in Section 1.5.

2 Fairness, calibration, and multicalibration

For an individual $i$ from the population ${\cal X}$, we denote $i$’s outcome by $o_{i}\in\{0,1\}$. We take $p^{*}_{i}\in$ to be the probability of outcome $o_{i}=1$, conditioned on all the information which is available to the algorithm. We denote by $p^{*}$ the vector of these probabilities for all individuals in ${\cal X}$. Our goal is to make a prediction $x_{i}$ for the value of $p^{*}_{i}$ for every individual $i$. As discussed above, we would like to avoid additional malicious or inadvertent discrimination (beyond the biases contained in the data). Thus, we refer to $p^{*}$ as the benchmark predictor for measuring discrimination.

Calibration

Balance

Other notions of fairness have been studied, looking at the rate of false positives and false negatives of predictions. Several variants of such properties have been recently studied on their own and in connection to calibration [KMR17, Cho17, PRW+17, HPS16, CDPF+17]. Let us briefly consider the notions referred to as balance in [KMR17]: balance for the positive class — the expected prediction $x_{i}$ for yes instances ($o_{i}=1$) in group $S$ equals the expected prediction for yes instances outside of $S$; and balance for the negative class — the expected prediction for no instances ($o_{i}=0$) in group $S$ equals the expected prediction for no instances outside of $S$. In [HPS16] it is shown how to obtain equalized odds, a definition related to error-rate balance, as a post-processing step of “correcting” any other predictor.

While both calibration and balance (as well as other related variants) intuitively seem like good properties to expect in a fair predictor (even if they are a bit weak), it has been shown that calibration and balance are impossible to obtain together (in non-degenerate cases) [KMR17, Cho17, PRW+17]. This inherent conflict between balance and calibration, combined with our observation that calibration is always aligned with the goal of accurate high-utility predictions, implies that at times, balance must be at odds with obtaining predictive utility. Our approach in this paper towards mitigating the conflict between calibration and balance is to strengthen the protections implied by calibration, rather than enforcing balance. While there are certainly contexts in which “equalizing the odds” across groups is a good idea, there are also contexts where calibration is a more appropriate notion of fairness. In particular, the benchmark predictor $p^{*}$ itself is unlikely to be balanced. Indeed, in our setting, the fact that balance is not satisfied might simply be an artifact of the inherent randomness in the process of sampling the outcome $o_{i}$, and this motivates our definition of multicalibration.

To illustrate this point, consider the following (intentionally-artificial) example: an algorithm is tasked with predicting the probability of rain during 10 days of winter, in two cities, a year from now. In city $A$ the algorithm predicts rain on each day with probability $0.8$; in city $B$ it predicts rain with probability $0.2$ (note that the certainty of the predictions is identical for both cities). A year passes and indeed in city $A$ it rains on 8 of the days, whereas in city $B$ it rains on only 2 days. What surprising accuracy! Nevertheless, the predictions violate balance; that is, after observing which days rained, the predictions treat the positive (respectively, negative) examples in city $A$ and $B$ differently. Indeed, the mayor of city $A$ may complain that the predictor hurt tourism to her city: “our sunny days are just as sunny as the sunny days of city $B$, so why were you so much more pessimistic about ours?” The point is that a priori the sunny and rainy days in $A$ (respectively, $B$) were indistinguishable from one another; further, there was a noticeable difference in the likelihood of rain between $A$ and $B$. Given the inherent uncertainty, it is unreasonable to expect accuracy on a subgroup that is only identifiable a posteriori. While this example is overly-simplified, it points to the fact that in any prediction context where there is inherent unpredictability, different false negative (or false positive) rates between groups are not necessarily a sign of discrimination.

Multicalibration

As illustrated, a principle weakness of calibration as a notion of fairness is that the guarantees are too coarse. As far as we are aware, in the existing literature, calibration has been applied to large, often disjoint, sets of protected groups; that is, the guarantees are only required to hold on average over a population defined by a small number of sensitive attributes, like race or gender. A stronger definition of fairness would ensure that the predictions on every subpopulation would be protected, including, for instance, the qualified members of $S$ from the example above. The problem with such a notion is that it is information-theoretically unattainable from a small sample of labeled examples, as it would essentially require perfect predictions. As such, we need an intermediary definition that balances the desire to protect important subgroups and the information bottleneck that arises when learning from a small sample.

To motivate our notion, consider an algorithm that produces a predictor $x$. The outcomes $o_{i}$ are determined, and then an auditor comes up with a set $S^{\prime}$ that over-performed compared with the predictions of $x$. Perhaps the learning algorithm was lazy and neglected to identify the higher potential in $S^{\prime}$? Perhaps the individuals of $S^{\prime}$ were simply lucky? How can we tell? To answer these questions, we take the following perspective: on the one hand, we can only expect a learner to produce a predictor that is calibrated on sets that could have been identified efficiently from the data at hand; on the other hand, we expect the learner to produce a predictor that is calibrated on every efficiently-identifiable subset. This motivates our definition of multicalibration, which loosely says: “A predictor $x$ is $\alpha$-multicalibrated with respect to a family of sets $\cal C$ if it is $\alpha$-calibrated with respect to every $S\in\cal C$.”

In the spirit of the discussion above, we take ${\cal C}$ to be a family of (sufficiently large) sets of individuals, such that for every $S\in{\cal C}$, the predicate $i\in S$ can be evaluated from the individual’s data within a particular family of computations (conjunctions of four attributes, bounded-depth decision trees, or any other bounded complexity class). The more powerful the family, the stronger the guarantee becomes; no subpopulation that can be identified by the family will be overlooked. At the extreme, consider multicalibration with respect to the family of polynomial-size circuits; in this case, every efficiently-identifiable subpopulation is protected! Note that the subpopulations in ${\cal C}$ can be overlapping, with complex relationships. In particular, they may well have no explicit dependence on sensitive attributes. In this sense, multicalibration goes far beyond calibration for several sensitive groups.

3 Our Results

Our study of multicalibration follows two major themes:

We investigate the feasibility of obtaining multicalibration; specifically, we study the learnability of multicalibrated predictors, showing both positive and negative results.

We investigate the properties of multicalibrated predictors. While multicalibration provides strong guarantees against forms of discrimination, we show that this protection can come at little cost in terms of complexity and utility.

We begin with a high-level overview of our setup. For a formal description of our model and assumptions, see Section 2. Suppose that for some universe of individuals ${\cal X}$, we wish to predict whether some event (ad click, loan repayment, cancer diagnosis, etc.) will occur for each individual $i\in{\cal X}$. We assume that for each individual, there is some true underlying probability $p_{i}^{*}$ that the event will occur. We call any mapping from the universe to probabilities a predictor; formally, a predictor is a function We will interchange between function and vector notation; generally we will denote the prediction that $x$ assigns to an individual $i\in{\cal X}$ as $x_{i}$. $x:{\cal X}\to$ that maps individuals from the universe to estimates of their true probabilities. We denote by $p^{*}$ the benchmark predictor that gives the true probabilities.

The first question to address is whether multicalibration is feasible. For instance, it could be the case that the requirements of multicalibration are so strong that they would require learning and representing an arbitrarily complex function $p^{*}$ exactly, which we’ve established can be infeasible. Our first result characterizes the complexity of representing a multicalbrated predictor. We demonstrate that multicalibration, indeed, can be achieved efficiently: for any $p^{*}$ and any collection of large subsets ${\cal C}$, there exists a predictor that is $\alpha$-multicalibrated on ${\cal C}$, whose complexity is only slightly larger than the complexity required to describe the sets of ${\cal C}$. For concreteness, we use circuit size as our measure of complexity in the following theorem.

Suppose ${\cal C}\subseteq 2^{{\cal X}}$ is collection of sets where for $S\in{\cal C}$, there is a circuit of size $s$ that computes membership in $S$ and $\left|S\right|\geq\gamma\left|{\cal X}\right|$. For any $p^{*}:{\cal X}\to$, there is a predictor that is $\alpha$-multicalibrated with respect to ${\cal C}$ implemented by a circuit of size $O(s/\alpha^{4}\gamma)$.

As stated, this result claims the existence of multicalibrated predictors whose predictions are efficient to evaluate. The existence of such predictors, while interesting from a complexity-theoretic perspective, begs the more practical question of whether we can get our hands on such a predictor.

In fact, we prove Theorem 1 algorithmically by learning an $\alpha$-multicalibrated predictor from labeled samples. While our model assumes the existence of some underlying true probabilities $p^{*}$, in most applications, these probabilities will not be directly observable. As such, we design algorithms that learn predictors from samples of individuals labeled with their outcomes; specifically, we assume access to labeled samples $(i,o_{i})$ of individual-outcome pairs, where $i$ is sampled according to some distribution ${\cal D}$ on the universe and $o_{i}$ is the realized value of a Bernoulli trial with probability $p_{i}^{*}$. Naturally, in this model, our goal is to give algorithms that are efficient in terms of running time and sample complexity.

In Section 3, we give an algorithm for learning a multicalibrated predictor from labeled samples, whose running time scales linearly with $\left|{\cal C}\right|$ and polynomially with $\alpha$ and $\gamma$. A consequence of our analysis is that naively, the sample complexity can be upper-bounded by $\log(\left|{\cal C}\right|)/\alpha^{6}\gamma^{6}$. We show how to improve the sample complexity over the naive approach by polynomial factors in both $\alpha$ and $\gamma$.

Suppose ${\cal C}\subseteq 2^{{\cal X}}$ is collection of sets such that for all $S\in{\cal C}$, $\left|S\right|\geq\gamma\left|X\right|$, and suppose set membership can be evaluated in time $t$. Then there is an algorithm that learns a predictor of $p^{*}:{\cal X}\to$ that is $\alpha$-multicalibrated on ${\cal C}$ from $O(\log({\left|{\cal C}\right|})/\alpha^{11/2}\gamma^{3/2})$ samples in time $O(\left|{\cal C}\right|\cdot t\cdot{\rm poly}(1/\alpha,1/\gamma))$.

Observing the linear dependence in the running time on $\left|{\cal C}\right|$, it is natural to try and develop a learning procedure with subpolynomial, or even polylogarithmic, dependence on $\left|{\cal C}\right|$. Our next results aim to characterize when this optimistic goal is possible – and when it is not. We emphasize that the algorithm of Theorem 2 learns a multicalibrated predictor for arbitrary $p^{*}:{\cal X}\to$ and ${\cal C}$. In the setting where we cannot exploit structure in $p^{*}$ to learn efficiently, we might hope to exploit structure, if it exists, in the collection of subsets ${\cal C}$. Indeed, we demonstrate a connection between our goal of learning a multicalibrated predictor and weak agnostic learning, introduced in the literature on agnostic boosting [BDLM01, KMV08, KK09, Fel10]. Our next result shows that efficient weak agnostic learning over ${\cal C}$ implies efficient learning of $\alpha$-multicalibrated predictors on ${\cal C}$.

If there is a weak agnostic learner for ${\cal C}$ that runs in time $T$, then there is an algorithm for learning an $\alpha$-multicalibrated predictor on ${\cal C}^{\prime}=\left\{S\in{\cal C}:\left|S\right|\gamma\left|X\right|\right\}$ that runs in time $O(T\cdot{\rm poly}(1/\alpha,1/\gamma))$.

Slightly more formally, we require a $(\rho,\tau)$-weak agnostic learner in the sense first introduced by [KMV08] and generalized by [Fel10]. For the specifics of the requirements and parameters, see the formal statement in Section 4.

These results show that under the right structural assumptions on $p^{*}$ or on ${\cal C}$, a multicalibrated predictor may be learned more efficiently than our upper bound for the general case. Returning to the general case, we may wonder if these structural assumptions are necessary; we answer this question in the positive. We show that for worst-case $p^{*}$ learning a multicalibrated predictor on ${\cal C}$ is as hard as weak agnostic learning for the class ${\cal C}$.

If there is an algorithm for learning an $\alpha$-multicalibrated predictor on a collection of sets ${\cal C}^{\prime}=\left\{S\in{\cal C}:\left|S\right|\geq\gamma N\right\}$ that runs in time $T$, then there is an algorithm that implements a $(\rho,\tau)$-weak agnostic learner in time $O(T\cdot{\rm poly}(1/\tau))$ for any $\rho>0$ where $\tau={\rm poly}(\rho,\gamma,\alpha)$.

In general, agnostic learning is considered a notoriously hard computational problem. In particular, under cryptographic assumptions [Val84, GGM84, BR17], this result implies that there is some constant $t>0$, such that any algorithm that learns an $\alpha$-multicalibrated predictor requires $\Omega(\left|{\cal C}\right|^{t})$ time.

Finally, we return our attention to investigating the utility of multicalibrated predictors. Above, we have argued that multicalibration provides a strong protection of groups against discrimination. We show that this protection comes at (next to) no cost in the utility of the predictor. This result adds to the growing literature on fairness-accuracy trade-offs [FKL16, BHJ+17, CG17].

Suppose ${\cal C}\subseteq 2^{{\cal X}}$ is a collection of subsets of ${\cal X}$ and ${\cal H}$ is a set of predictors. There is a predictor $x$ that is $\alpha$-multicalibrated on ${\cal C}$ such that

We can interpret Theorem 5 in different ways based on the choice of ${\cal H}$. Suppose there is some sophisticated learning algorithm (say, a neural network) that produces some predictor $h$ that obtains exceptional performance, but may violate calibration arbitrarily. If we take ${\cal H}=\left\{h\right\}$, then this result says: enforcing calibration on $h$ after learning does not hurt the accuracy by much. Further, our proof will demonstrate that if calibration changes the predictions of $h$ significantly, then this change amounts to an improvement in accuracy. See Lemma 5.2 for the exact statement. Taking a different perspective, we can also think of ${\cal H}$ as a set of predictors that, say, are implemented by a circuit class of bounded complexity (e.g. conjunctions of $k$ variables, halfspaces, circuits of size $s$). This theorem shows that for any such class of predictors ${\cal H}$ of bounded complexity, there exists a multicalibrated predictor with similar complexity that performs as well as the best $h^{*}\in{\cal H}$. In this sense, with just a slight overhead in complexity, multicalibrated predictors can achieve “best-in-class” predictions.

4 Related work

As mentioned earlier, calibration is a well-studied concept in the literature on statistics and econometrics, particularly forecasting. For a background on calibration in this context, see [SSV03, FH15] and the references therein. Calibration has also been studied in the context of structured predictions where the supported set of predictions is large [KL15]. Our algorithmic result for multicalibration bears similarity to works from the online learning literature [BM07, KP08, TTV09]. In Section 3.1, we describe a procedure for achieving a weaker notion than multicalibration, which we refer to as multi-“accurate in expectation” (multi-AE); our result can be viewed as a restatement of the boosting-based proof due to [TTV09] that every high-entropy distribution is indistinguishable by small circuits from an efficiently-samplable distribution of the same entropy. While the algorithms for learning a multi-AE and multicalibrated predictor bear similarity, when we turn to achieving multicalibration, we have to deal with a number of nontrivial challenges due to learning from a small sample (while guaranteeing generalization) and using an apprropriate notion of discretization that are not necessary in [TTV09]. We are also not aware of any prior works connecting the literature on calibration with the literature on differential privacy and adaptive data analysis.

Between populations and individuals

In [DHP+12], an individual notion of fairness was defined, referred to as “fairness through awareness.” This notion relied on a task-specific metric of similarity between individuals and formalized the idea that similar individuals (under this metric) are treated similarly. It is natural, in an array of applications, to view $p^{*}$ as defining a metric – two individuals $i$ and $j$ will be assigned the distance $|p^{*}_{i}-p^{*}_{j}|.$ In this work we consider cases in which figuring out $p^{*}$ in its entirety is difficult. Thus, one can view our approach as a meaningful compromise between group fairness (satisfying calibration) and individual-calibration (closely matching $p^{*}_{i}$). The multicalibration framework presented in this work served as the inspiration for subsequent work of a subset of the authors [KRR18] investigating how to interpolate between statistical and individual notions of “metric fairness” for general similarity metrics.

Subgroup Fairness

Contemporary independent work of [KNRW17] also investigates strengthening the guarantees of notions of group fairness by requiring that these properties hold for a much richer collection of sets. Unlike our work, their definitions require balance or statistical parity on these collection of sets. Their motivation is similar to ours, namely to bridge the gap between notions of individual fairness (powerful but hard to obtain) and population-level fairness (easy to work with but weak).

Despite similar motivations, the two approaches to subgroup fairness differ in substantial ways. As a concrete example, Theorem 5 demonstrates that achieving multicalibration is aligned with the incentives of achieving high-utility predictors; this is not necessarily the case with balance-based notions of fairness. Indeed, in the setting considered in this work, one of the motivations for multicalibration is a critique of balance that may only be heightened when considering “multi-balance”. Consider the example in [DHP+12] where in a population $S$ the strongest students apply to Engineering whereas in the general population $T$ they apply to Business. Even if predictor $p^{*}$ (for the probability of success in school) is balanced between $S$ and $T$, forcing balance between the two populations within Business applicants and within Engineering applicants would be unfair to qualified applicants in both groups. (For more discussion, see the section below on “Corrective discrimination”.)

On a technical level, both works draw connections between agnostic learning and the task of finding a group on which the fairness condition is violated ( [KNRW17] refer to this as auditing). Leveraging this connection, we show how to use an agnostic learner to learn a multicalibrated predictor efficiently. In a similar vein, [KNRW17] show how to use an agnostic learner to efficiently learn a classifier that satisfies balance or parity on a collection of sets, while achieving competitive accuracy within a given class. They also implement a more-practical variant of their algorithm and use it to conduct empirical experiments.

Preventing discrimination by algorithms is subtle; different scenarios will call for different notions of protection. As such, it is hard to imagine a universal definition of fairness. Nevertheless, these two independent works validate the need to investigate attainable approaches to mitigating discrimination beyond large protected groups. It will be interesting to further understand how these notions of subgroup fairness relate to one another, and when each approach is most appropriate.

Calibration for multiple protected sets vs. multicalibration

The literature on fairness commonly considers more than a single protected set (cf. [CSV17] which studies fairness in ranking algorithms, with protected groups being defined by each attribute of interest). The major difference in our work is that we think of protected groups as any group that can be efficiently identified, rather than those defined by sensitive properties. One side benefit of the generality of our approach is that it does not single out groups based on sensitive values for special treatment (which can be illegal in some contexts).

Calibration, Bandits, and Regret

There is a growing literature on designing fair selection policies in the multi-arm bandits setting [JKMR16, JKM+17, LRD+17]. Recently [LRD+17] initiated the study of calibration in this context. Motivated by the aforementioned work of [DHP+12], their notion of calibrated fairness aims to “treat similar individuals similarly” by designing sampling policies that have low fairness regret.

Causality and discrimination in the data

Discrimination can occur at any stage throughout the algorithmic pipeline and in many forms. The most important aspect of developing a theory of algorithmic fairness that multicalibration does not address is “unfair” data (see more below). Kilbertus et al. [KRCP+17] voice an important criticism of any notion of fairness based solely on observational criteria, as discrimination can occur through unresolved causal relationships. This criticism applies to the notions of balance, calibration, and multicalibration, which all depend only on the joint distribution of predictions, outcomes, and features.

Rather than attempting to provide a general-purpose definition of fairness, our work tackles a particular concern about discrimination that can occur as part of the process of learning a predictor from given data. In this context, we believe that multicalibration provides an important anti-discrimination guarantee.

Corrective discrimination

Let us look deeper into the biases that may be present in the gathered data, by considering the mortgage example again: perhaps the number of members of $S$ that received loans in the past is small (and thus there are too few examples for fine-grained learning within $S$); perhaps the attributes are too limited to identify the qualified members of $S$ (taking this point to the extreme, perhaps the only available attribute is membership in $S$). In these cases, the data may be insufficient for multicalibration to provide meaningful guarantees. Further, even if the algorithm was given access to unlimited rich data such that refined values of $p^{*}$ could be recovered, there are situations where preferential treatment may be in order: after all, the salaries of members of $S$ may be lower due to historical discrimination.

For these reasons, our concern that balance is inconsistent with $p^{*}$ could be answered with: “yes, and purposely so!” Indeed, [HPS16] promotes enforcing a balance-related property, called equalized odds, as a form of “corrective discrimination.” While this type of advocacy is important in many settings, multicalibration represents a different addition to the quiver of anti-discrimination measures, which we also believe is natural and desirable in many settings.

Consider a concrete example where multicalibration is appropriate, but equalizing error rates might not be: Suppose a genomics company offers individuals a prediction of their likelihood of developing certain genetic disorders. These disorders have different rates across different populations; for instance, Tay-Sachs disease is rare in the general population, but occurs much more frequently in the Ashkenazi Jewish population. We certainly do not want to enforce corrective discrimination on the Ashkenazi population by down-weighting the prediction that individuals would have Tay-Sachs (as they are endogenously more likely to have the disease). However, we also don’t want the company to base its prediction solely on the Ashkenazi feature (either positively or negatively). Instead, enforcing multicalibration would require that the learning algorithm investigate both the Ashkenazi and non-Ashkenazi population to predict accurately in each group (even if this means a higher false positive rate in the Ashkenazi population). In this case, relying on $p^{*}$ seems to be well-aligned with promoting fairness.

Finally, we consider the interplay between multicalibration and “corrective discrimination” to be an important direction for further research. For example, one can imagine applying corrective measures, such as the transformation of [HPS16], to a multi-calibrated predictor.

5 Our Techniques

Here, we give a high-level technical overview of our results. Our techniques draw from the literature on computational learning theory, online optimization, differential privacy, and adaptive data analysis.

To avoid this blow-up in sample complexity, we appeal to recently-uncovered connections between differential privacy and adaptive data analysis developed in [DFH+15c, DFH+15c, BNS+16, DFH+15b]. In Section 3.3, we show how to answer the statistical queries in a way that guarantees the learning algorithm is differentially private. This, in turn, allows us to argue that the predictor our algorithm learns from a small sample will be multicalibrated, not just for the observed individuals but also the unseen individuals. In particular, using a privacy-based approach with an analysis tailored to the goal of calibration, we obtain sample complexity that depends on $1/\alpha^{11/2}\gamma^{3/2}$ as opposed to the naive approach which results in $1/\alpha^{6}\gamma^{6}$.

As stated earlier, Theorem 1 can be seen as a corollary of Theorem 2. Bounding the number of iterations needed by the algorithm to converge not only upper-bounds the algorithm’s running time and sample complexity, but also implies that the circuit complexity of the learned predictor is not much larger than the complexity of evaluating membership for $S\in{\cal C}$. We explain this implication in Section 3.5.

The complexity of multicalibration

In Section 3.4, we discuss the complexity of learning a multicalibrated predictor and draw connections to agnostic learning [Hau92, KSS94]. We show that the algorithm learns a multicalibrated predictor in a bounded number of iterations; however, without additional assumptions about $p^{*}$ or ${\cal C}$, each iteration could take $\Omega(\left|{\cal C}\right|)$ time. In the cases where $\left|{\cal C}\right|$ is large, we might hope to improve the dependence on $\left|{\cal C}\right|$ to polylogarithmic or perhaps subpolynomial. If $p^{*}$ can be learned directly, then we can eliminate the dependence on $\left|{\cal C}\right|$ and instead, only depend on the minimum $\gamma$ such that for all $S\in{\cal C}$, $\left|S\right|\leq\gamma N$.

In the case where $p^{*}$ is arbitrary, we show that improving the dependence on $\left|{\cal C}\right|$ is possible if ${\cal C}$ is structured in a certain way, drawing a connection to the literature on agnostic learning [Hau92, KSS94, KMV08, Fel10]. Recall, in our algorithm for learning multicalibrated predictors, we maintain a candidate predictor $x$, and iteratively search for some set $S\in{\cal C}$ on which $x$ is not calibrated. To solve this search problem more quickly, we frame the search as weak agnostic learning over a concept class derived from ${\cal C}$ and over the hypothesis class of ${\cal H}=\left\{h:{\cal X}\to\right\}$.

Additionally, we show that our reduction to weak agnostic learning is unavoidable. In particular, we show that if it is possible to learn a multicalibrated predictor with respect to ${\cal C}$, then it is possible to weak agnostic learn on ${\cal C}$ (if we view ${\cal C}$ as a concept class). Specifically, we will show how to implement a weak agnostic learner for ${\cal C}$, given an algorithm to learn an $\alpha$-multicalibrated predictor $x$ with respect to ${\cal C}$ (in fact, we only need the predictor to be multicalibrated on ${\cal C}^{\prime}=\left\{S\in{\cal C}:\left|S\right|\geq\gamma\left|X\right|\right\}$). The key lemma for this reduction says that if there is some $c\in{\cal C}$ that is nontrivially correlated with the labels, then $x$ is also nontrivially correlated with $c$. As there are many natural classes ${\cal C}$ for which agnostic learning is conjectured to be hard, this gives a strong negative result to the question of whether we can obtain speedups in the general case.

In combination, these results show that the complexity of learning a multicalibrated predictor with respect to a class ${\cal C}$ is equivalent to the complexity of weak agnostic learning ${\cal C}$. Section 4 contains the formal statements and proofs that imply this equivalence.

“Best-in-class” prediction

In Section 5, we turn to understanding how requiring a predictor to be multicalibrated affects the accuracy of the predictor. We show – in contrast to many other notions of fairness – multicalibration does not limit the utility of a predictor. In particular, given any collection of predictors ${\cal H}$, and any collection of subsets ${\cal C}$, we design a procedure for obtaining a predictor $x$ that is $\alpha$-multicalibrated on ${\cal C}$ and achieves expected squared prediction error less than or equal to the the best predictor in ${\cal H}$ (plus a small additive error on $\alpha$). Further, leveraging Theorem 1 and Theorem 2, we show that the predictor $x$ can be learned from samples and implemented by a circuit of comparable size to the predictors $h\in{\cal H}$. To prove that multicalibration does not negatively impact the utility, we in fact, show a much stronger statement: if applying multicalibration to some $h\in{\cal H}$ changes the predictions of $h$ significantly (i.e. if $\left\|x-h\right\|$ is large), then this change represents an improvement in accuracy (i.e. $\left\|x-p^{*}\right\|<\left\|h-p^{*}\right\|$). In this sense, requiring multicalibration is aligned with the goals of learning a high-utility predictor.

Organization of the paper

In Section 2, we provide a description of our model and the formal definitions related to multicalibration. In Section 3, we describe and analyze our algorithm for learning multicalibrated predictors. In Section 4, we investigate the complexity of obtaining multicalibration, showing a tight connection to the complexity of weak agnostic learning. Finally, in Section 5, we demonstrate how multicalibration achieves “best-in-class” prediction.

Preliminaries

Let ${\cal X}$ denote the universe of $N$ individuals over which we wish to make predictions about some outcome $o\in\left\{0,1\right\}^{N}$. We assume that outcomes are the result of some underlying random process, where for each $i$, $o_{i}$ is sampled independentlyIn many cases, complete independence may not hold; individuals’ outcomes may be correlated in nontrivial ways. The only place we will use independence is to argue that the reliable statistics can be estimated from the observable data; our arguments can be applied to any model for which one can prove the appropriate tail inequalities. For further consideration, continue to our discussion on “observable” calibration after Claim 2.3. as a Bernoulli random variable with success probability $p_{i}^{*}$. We aim to predict the underlying parameters of the process, rather than the realized outcome of the process. A predictor $x:{\cal X}\to$ of outcome $o$ is some mapping from individuals $i\in{\cal X}$ to $$, where$x_{i}$is the prediction of$p_{i}^{*}$. We refer to$p^{*}$as the baseline predictor. When it is notationally convenient, we will sometimes treat predictors as vectors$x\in^{N}$rather than as functions$x:{\cal X}\to$, where we assume a bijection from${\cal X}$to$[N]$.

Often in learning theory, we think of learning functions $h:{\cal F}\to$ over the space of possible features ${\cal F}$. We find it preferable to reason about predictions about individuals; nevertheless, in our model, we can think of $x_{i}$ as given by the composition of two separate functions, where $x_{i}=x^{\prime}(\phi(i))$ for $x^{\prime}:{\cal F}\to$ and $\phi:{\cal X}\to{\cal F}$. As $\phi$ will be fixed and assumed to be some simple function (say, mapping individuals to their $\langle$ age, height, ZIP code, $\ldots\rangle$) we drop the explicit reference to ${\cal F}$ and $\phi$.

Sampling from 𝒳𝒳{\cal X}

Throughout, we will assume that our learning algorithms have the ability to efficiently obtain randomly sampled individuals from ${\cal X}$ (and by rejection sampling, large subsets of ${\cal X}$). Specifically, we will use $i\sim S$ to denote sampling $i$ uniformly at random from $S\subseteq{\cal X}$.

Our focus on the uniform distribution is mostly syntactic; as per our distinction between the identities of individuals $i\in{\cal X}$ and their features $\phi(i)$, the uniform distribution over individuals gives rise to a rich class of distributions over the features of individuals.

We will further assume that sampling $i\sim{\cal X}$ is inexpensive compared to obtaining a corresponding outcome $o_{i}\in\left\{0,1\right\}$ for $i\sim{\cal X}$ that is Bernoulli distributed with parameter $p_{i}^{*}$. As such, when measuring the sample complexity, we will only count the latter type of labeled samples. The learner has a good sense of the distribution over features, but not of the outcomes that arise from these features.

1 Calibration

Next, we give formal definitions of the criteria we use to measure algorithmic discrimination. The first notion captures the idea that, on average, we would like an algorithm’s predictions to be unbiased.

For any $\alpha>0$ and $S\subseteq{\cal X}$, a predictor $x$ is $\alpha$-accurate in expectation ($\alpha$-AE) with respect to $S$ if

That is, the predictions, averaged over the set $S$, are accurate up to some additive $\alpha$ slack. This basic condition is necessary to ensure unbiased predictions, but it is too weak to guarantee discrimination hasn’t occurred. In particular, suppose the underlying probabilities are such that $p_{i}^{*}=1/2$ for all $i\in S$. A predictor that predicts $1$ on half of the individuals in $S$ and on the other half is accurate in expectation, but it is arguably discriminatory; there is no difference between the individuals in $S$, but the predictor has artificially created two categories within this population. This example motivates the definition of calibration. Calibration mitigates this form of discrimination by considering the expected values over categories $S_{v}=\left\{i:x_{i}=v\right\}$ defined by the predictor $x$. Specifically, $\alpha$-calibration with respect to $S$ requires that for all but an $\alpha$-fraction of a set $S$, the average of the true probabilities of the individuals receiving prediction $v$ is $\alpha$-close to $v$.

For any $v\in$, $S\subseteq{\cal X}$, and predictor $x$, let $S_{v}=\left\{i:x_{i}=v\right\}$. For $\alpha\in$, $x$ is $\alpha$-calibrated with respect to $S$ if there exists some $S^{\prime}\subseteq S$ with $\left|S^{\prime}\right|\geq(1-\alpha)\left|S\right|$ such that for all $v\in$,

Note that $\alpha$-calibration with respect to $S$ implies $2\alpha$-AE with respect to $S$. To see this, observe that calibration implies that on a $(1-\alpha)$-fraction of $S$, the average of the values are $\alpha$-close to the expectation on this fraction; even if the other $\alpha$-fraction is arbitrary, it can only introduce another additive $\alpha$ error. This definition only requires the notion of calibration to hold on a $(1-\alpha)$-fraction of each $S$; this is for technical reasons. See Definition 2.9 to understand better the motivations for this choice.

This notion of calibration departs from prior definitions in a few ways. Earlier definitions required exact calibration with respect to ${\cal X}$; we find it meaningful to consider approximate calibration. Introducing approximation into the definition of calibration has practical motivation. In particular, we don’t expect to know the exact probabilities, nor can we observe the entire population. Given a desired accuracy and access to samples from the population, we can quantify how many samples are needed to guarantee calibration with good probability.

Note that in our definition of $\alpha$-calibration, we require relative additive error that scales with the size of $S_{v}$. That is, for some $S$ and category $S_{v}=\left\{i:x_{i}=v\right\}\cap S$, the magnitude of the sum of errors on $S_{v}$, $\left|\sum_{i\in S_{v}}(v-p_{i}^{*})\right|$, scales with $\left|S_{v}\right|$, not $N$. This relative approximation model prevents certain “attacks” against approximate calibration. Specifically, one natural way a predictor might attempt to sidestep the anti-discrimination properties of approximate calibration would be to support many distinct values of $v\in$, each with a very small number of individuals. If our notion of approximation allowed for absolute errors (i.e. errors whose sum over $S_{v}$ scale with $N$ instead of $\left|S_{v}\right|$), then this attack would be viable, leading to essentially no guarantees

Another subtle distinction is that we evaluate calibration with respect to the underlying probabilities $p^{*}\in^{N}$, as opposed to the realized outcomes $o\in\left\{0,1\right\}^{N}$. We refer to the earlier notion as observable calibration. Formally, a predictor is observably $\alpha$-calibrated with respect to $S\subseteq{\cal X}$ and outcome $o\in\left\{0,1\right\}^{N}$ if for all $v\in$,

where $S_{v}$ and $S^{\prime}$ are as in Definition 2.2. In our terminology, earlier references to calibration require that a predictor be observably -calibrated with respect to each protected group $S$. Our introduction of a non-zero $\alpha$ in these definitions allows us to relate our notion of calibration and the previous notion of observable calibration.

Let $S\subseteq{\cal X}$, $\xi>0$, and $\alpha>\sqrt{\frac{\log(1/\xi)}{2\left|S\right|}}$. Suppose the outcome $o\in\left\{0,1\right\}^{N}$ is drawn according to the true probabilities $p^{*}$. Then, with probability at least $1-\xi$ over the draw of $o$, any predictor that is $\alpha$-calibrated with respect to $S$ will be observably $2\alpha$-calibrated with respect to $S$.

Claim 2.3 follows directly from an application of Hoeffding’s inequality over the random outcome $o$. The claim implies that for sufficiently large $\alpha$, to guarantee observable $2\alpha$-calibration with high probability, it suffices to consider our notion of $\alpha$-calibration.

Independence and observability

We note that to prove Claim 2.3, we use the independence of $o_{i}$’s in our application of Hoeffding’s inequality. Throughout, the only times we invoke the independence of the realization of the $o_{i}$’s are to prove that the empirical statistics over a sufficiently large sample of observations will be concentrated around the corresponding statistics of the true parameters. Thus, the independence assumption isn’t strictly necessary; our results should hold for any model where the outcomes admit similar tail inequalities. We note, however, that if strong dependencies exist in the realization of the outcomes, our techniques will still achieve observable calibration from samples. Recall that in observable calibration, we compare the value $v$ output by the predictor on a category $S_{v}$ to the empirical average of outcomes over the category $\sum_{i\in S_{v}}o_{i}$. If we only need to guarantee closeness with respect to these observable outcomes, we do not need to ensure that sums over outcomes will be concentrated around their expectation (i.e. sums of the underlying true probabilities).

2 Learning model

In Section 3, we present algorithms to learn predictors satisfying accuracy-in-expectation and calibration. The algorithms can be viewed as statistical query algorithms [Kea98]. Specifically, the algorithms only require access to approximate statistical queries of the following form.

Note that this query model guarantees absolute additive error $\tau N$. As discussed above, our notion of calibration with respect to $S$ asks for relative additive error; however, if we know a lower bound on $\left|S\right|\geq\gamma N$, then, asking a statistical query with tolerance $\tau=\alpha\gamma$ will guarantee relative error $\alpha$ on $S$.

In addition to giving algorithms that work in this statistical learning framework, we also address the question of learning a calibrated predictor from a set of samples of outcomes. Formally, we define the access to sampled outcomes as follows.

For $p^{*}\in^{N}$, a random sample returns an individual-outcome pair $(i,o_{i})\in{\cal X}\times\left\{0,1\right\}$, where $i\sim{\cal X}$ is drawn uniformly at random and $o_{i}$ is sampled according to the Bernoulli distribution with parameter $p_{i}^{*}$.

We say an algorithm learns a predictor from samples if its only access to the true parameters $p^{*}$ is through random samples of this form. It’s easy to see that we can always implement a statistical query algorithm with access to enough random samples – for every query, we could sample a fresh set of outcomes to estimate the statistic accurately. Our goal will be to avoid resampling in order to prevent a blow-up in the sample complexity.

3 Multicalibration

We introduce the notion of multicalibration, which requires calibration to hold simultaneously on subsets of the population. We will show that multicalibration not only guarantees fairness across protected populations, but also helps us uncover more accurate predictions. To motivate multicalibration further, consider the following toy example: suppose $p^{*}$ is such that there is some population $S$ (possibly, a traditionally protected group) and a subpopulation $S^{\prime}\subseteq S$ with $\left|S^{\prime}\right|=\left|S\right|/2$, where for every $i\in S^{\prime}$, $p_{i}^{*}=1$, and for every $i\in S\setminus S^{\prime}$, $p_{i}^{*}=0$. The predictor $x$ that predicts $x_{i}=1/2$ for all $i\in S$ is calibrated on the population $S$, but clearly is suboptimal. Further, if $S^{\prime}$ was identifiable in advance, then this predictor is arguably discriminatory – there are two clearly identifiable groups within $S$, but we are treating them the same way. If, however, we insist on calibration with respect to $S^{\prime}$ in addition to $S$, then the predictor will be required to output accurate predictions for each group. Earlier approaches to using calibration to achieve fairness, as introduced in [KMR17], would prevent this form of discrimination for subsets $S$ that are identified as a protected group (defined, for example, by race), but not for subpopulations of these groups – even if the subpopulations could be easily distinguished as outstanding.

For a collection of subsets ${\cal C}$, we say that a predictor is $\alpha$-multicalibrated on ${\cal C}$ if it is $\alpha$-calibrated simultaneously on all $S\in{\cal C}$.

Let ${\cal C}\subseteq 2^{{\cal X}}$ be a collection of subsets of ${\cal X}$ and $\alpha\in$. A predictor $x$ is $\alpha$-multicalibrated on ${\cal C}$ if for all $S\in{\cal C}$, $x$ is $\alpha$-calibrated with respect to $S$.

We also define the corresponding definition for the weaker notion of $\alpha$-AE.

Let ${\cal C}\subseteq 2^{{\cal X}}$ be a collection of subsets of ${\cal X}$ and $\alpha\in$. A predictor $x$ is $\alpha$-multi-AE on ${\cal C}$ if for all $S\in{\cal C}$, $x$ is $\alpha$-AE with respect to $S$.

Even though $\alpha$-calibration is a meaningful definition if we allow for arbitrary predictions $x_{i}\in$, when designing algorithms to learn calibrated predictors, it will be useful to maintain some discretization on the values $v\in$. Formally, we will use the following definition.

Let $\lambda>0$. The $\lambda$-discretization of $$, denoted by$\Lambda=\left\{\frac{\lambda}{2},\frac{3\lambda}{2},\ldots,1-\frac{\lambda}{2}\right\}$, is the set of$1/\lambda$evenly spaced real values over$$. For$v\in\Lambda$, let

be the $\lambda$-interval centered around $v$ (except for the final interval, which will be $[1-\lambda,1]$).

At times, it will be convenient to work with a more technical variant of multicalibration, which implies $\alpha$-multicalibration. In particular, this definition will allow us to work with an explicit discretization of the values $v\in$. Throughout, for a predictor $x$, we refer to the “categories” $S_{v}(x)=\left\{i:x_{i}\in\lambda(v)\right\}\cap S$ for all $S\in{\cal C}$ and $v\in\Lambda$.

Let ${\cal C}\subseteq 2^{{\cal X}}$ be a collection of subsets of ${\cal X}$. For any $\alpha,\lambda>0$, a predictor $x$ is $(\alpha,\lambda)$-multicalibrated on ${\cal C}$ if for all $S\in{\cal C}$, $v\in\Lambda$, and all categories $S_{v}(x)$ such that $\left|S_{v}(x)\right|\geq\alpha\lambda\left|S\right|$, we have

For $\alpha,\lambda>0$, suppose ${\cal C}\subseteq 2^{{\cal X}}$ is a collection of subsets of ${\cal X}$. If $x$ is $(\alpha,\lambda)$-multicalibrated on ${\cal C}$, then $x^{\lambda}$ is $(\alpha+\lambda)$-multicalibrated on ${\cal C}$.

Consider the categories $S_{v}(x)$ where $\left|S_{v}(x)\right|<\alpha\lambda\left|S\right|$. By the $\lambda$-discretization, there are at most $1/\lambda$ such categories, so the cardinality of their union is at most $(1/\lambda)\alpha\lambda\left|S\right|=\alpha\left|S\right|$. Thus, for each $S\in{\cal C}$, there is a subset $S^{\prime}\subseteq S$ with $\left|S^{\prime}\right|\geq(1-\alpha)\left|S\right|$ where for all $v\in\Lambda$,

Further, $\lambda$-discretization will “move” the values of $x_{i}$ by at most $\lambda$, so overall, $x^{\lambda}$ will be $(\alpha+\lambda)$-calibrated. ∎

Typically, we will imagine $\lambda=\Theta(\alpha)$, but our results hold for any $\lambda\in(0,1]$. Choosing a smaller $\lambda$ will allow the predictor to be more expressive, but will also increase the running time and sample complexity. Choosing a larger $\lambda$ leads to a decay in the calibration guarantees.

Representing subsets of individuals

When representing collections of subsets, we will assume that the subsets are represented implicitly. In particular, we will assume that $S\in{\cal C}$ is given as a circuit $c_{S}:{\cal X}\to\left\{0,1\right\}$, where $S=c_{S}^{-1}(1)$; that is, for $i\in{\cal X}$, $c_{S}(i)=1$ if and only if $i\in S$. Using this implicit representation serves two purposes. First, in many cases, we may want to calibrate on a collection of subsets over a large universe; in these cases, assuming an explicit representation of each set is unreasonable. Second, associating a set $S$ with a circuit that computes membership in $S$ allows us to quantify the complexity of the sets in ${\cal C}$. In particular, it seems natural to apply multicalibration to guarantee calibration with respect to a collection of efficiently-identifiable subsets (say, subsets defined by conjunctions of four attributes, or any other simple circuit class). It seems comparatively unreasonable to require calibration on, say, a random subsets, each of which would require $\Omega(\left|{\cal X}\right|)$ bits to describe.

Learning α𝛼\alpha-multicalibrated predictors

In this section, we prove Theorem 2; that is, we provide an algorithm for efficiently learning $\alpha$-multicalibrated predictors. The algorithms we describe are iterative and fit into the powerful online optimization framework [SS12, Haz16] as well as the statistical query framework [Kea98]. For completeness, in Section 3.1, we describe an algorithm that solves the simpler task of learning an $\alpha$-multi-AE predictor, as a warm-up to introduce the main ideas; this algorithm was originally discovered by [TTV09]. In Section 3.2, we describe the algorithm for learning $\alpha$-multicalibrated predictors in full. Then, in Section 3.3, we will give a nontrivial implementation of the statistical query oracle that will imply nontrivial upper bounds on the running time and sample complexity of the learning algorithm. This implementation borrows ideas from the literature on differentially private query release and optimization [HR10, Ull15, HRRU14]. We conclude in Section 3.5 with the observation that our algorithm also has implications for the circuit complexity of calibrated predictors: for any collection of sets ${\cal C}$, there is an $\alpha$-calibrated predictor whose circuit complexity is a small factor larger than the circuit complexity required to describe the sets in ${\cal C}$. This establishes Theorem 1.

We begin our discussion with a simpler statistical query algorithm for learning an $\alpha$-multi-AE predictor. This algorithm serves as a warm-up for the subsequent algorithm for learning an $\alpha$-multicalibrated predictor.

Algorithm 3.1 describes an iterative statistical query procedure for learning a $\alpha$-multi-AE predictor on ${\cal C}$. Note that the problem of finding an $\alpha$-multi-AE predictor for some collection of sets ${\cal C}$ can be written as a linear program; the algorithm presented can be viewed as an instance of projected subgradient descent (see [Haz16]). The algorithm iteratively updates a predictor $x$ until it cannot find a set $S\in{\cal C}$ where the current estimate deviates significantly from the value reported by the statistical query. We claim that if no set violates this condition, then $x$ is $\alpha$-multi-AE on ${\cal C}$.

If Algorithm 3.1 outputs a predictor $x$, then $x$ is $\alpha$-multi-AE on ${\cal C}$.

Thus, to show the correctness of the algorithm, it remains to show that the algorithm will, in fact, terminate; we show the algorithm can make at most $O(1/\alpha^{2}\gamma)$ updates.

Suppose $\alpha,\gamma>0$ and ${\cal C}\subseteq 2^{{\cal X}}$ such that for all $S\in{\cal C}$, $\left|S\right|\geq\gamma N$. Let $\tau=\alpha\gamma/4$. Then Algorithm 3.1 makes $O(1/\alpha^{2}\gamma)$ updates to $x$ before terminating.

By setting $\tau=\alpha\gamma/4$ and by the bound $\left|\Delta_{S}\right|\geq\alpha\left|S\right|-\tau N\geq 3\alpha\left|S\right|/4$, the final quantity is at least $\Omega(\alpha^{2}\left|S\right|)$. We also have

In combination, these statements show the correctness of Algorithm 3.1 and imply an upper bound on the number of statistical queries necessary.

For $\alpha,\gamma>0$ and for any ${\cal C}\subseteq 2^{{\cal X}}$ satisfying $\left|S\right|\geq\gamma N$ for all $S\in{\cal C}$, there is a statistical query algorithm with tolerance $\tau=\alpha\gamma/4$ that learns a $\alpha$-multi-AE predictor on ${\cal C}$ in $O(\left|{\cal C}\right|/\alpha^{2}\gamma)$ queries.

Recall that, trivially, we could implement this statistical query algorithm from random samples by resampling for every query; however, in this case, we can easily improve the sample complexity exponentially over the trivial solution. Specifically, the queries we make are non-adaptive because, up front, we know a fixed collection of subsets whose expectation we might query. To guarantee accurate expectations on this fixed collection, we only need enough samples to guarantee that the sample is inaccurate on a fixed subset with very small probability, and then union bound over all $\left|{\cal C}\right|$ subsets. Appealing to a standard generalization argument [KV94], we can show the following theorem.

Note that the $\gamma$ dependence in the sample complexity is only $1/\gamma$. Naively, applying the guarantees of the statistical query oracle, we would obtain a $1/\gamma^{2}$ dependence. To achieve this bound, we note that because calibration requires relative error, we can be more judicious with our use of samples. We will exploit this observation subsequently to obtain improvements to the sample complexity for learning $\alpha$-multicalibrated predictors.

To obtain the claimed sample complexity bound, we observe that in Algorithm 3.1, we only use the statistical query oracle to guarantee bounds on the relative error of each query – not absolute error. In particular, for $S\subseteq{\cal X}$ with $\left|S\right|\geq\gamma N$, let $\bar{p}_{S}=\frac{1}{\left|S\right|}\sum_{i\in S}p_{i}^{*}$. To run Algorithm 3.1, we need only implement an oracle $\hat{p}(S)$ satisfying

2 α𝛼\alpha-Multicalibrated predictors

Next, we present the full algorithm for learning $\alpha$-multicalibrated predictors on ${\cal C}$. The algorithm is based on Algorithm 3.1 but differs in a few key ways. First, instead of updating the predictions on entire sets $S\in{\cal C}$ whose overall expectation is wrong, we update the predictions on uncalibrated categories $S_{v}=S\cap\left\{i:x_{i}=v\right\}$. This is a simple change to the algorithm in the statistical query model; however, when we wish to implement this statistical query oracle from a finite sample, we need to be more careful.

In particular, the categories of the predictor we learn are not fixed a priori, so our queries will be selected adaptively based on the results of earlier statistical queries. Stated another way, we cannot simply union bound against the collection of sets on which we wish to be calibrated. The most naive approach to bounding the sampling complexity would be as follows: at each iteration take a fresh sample large enough to guarantee $\omega N$ absolute error, for $\omega=\alpha\gamma$. Following our analysis below for this naive strategy, it’s easy to see that this approach would result in $\Omega(1/\alpha^{4}\gamma^{4})$ iterations and sample complexity $n\geq\Omega(1/\alpha^{6}\gamma^{6})$. We will improve on this approach by polynomial factors achieving a bound of at most $O(1/\alpha^{4}\gamma)$ iterations with $O(1/\alpha^{5/2}\gamma^{3/2})$ samples.

To achieve these improvements, we combine two ideas. As before, we will leverage the observation that calibration only requires relative error (as in Corollary 3.4), and thus, in principle should require fewer samples. Additionally, to avoid naively resampling but still guarantee good generalization from a small sample, we interact with the sample through a mechanism which we call a guess-and-check statistical query (similar in spirit to mechanisms proposed in [HR10, BH15, GRU12]). We show how to implement this mechanism in a manner that guarantees generalization on the unseen data even after asking many adaptively chosen statistical queries. We defer our discussion of privacy to Section 3.3.

Next, we give an iterative procedure to learn a $(\alpha,\lambda)$-multicalibrated predictor on ${\cal C}$ as described in Algorithm 3.2. The procedure is similar to Algorithm 3.1, but deliberately interacts with its statistical queries through a so-called guess-and-check oracle. In particular, each time the algorithm needs to know the value of a statistical query on a set $S$, rather than asking the query directly, we require that the algorithm submit its current guess $x_{S}=\frac{1}{\left|S\right|}\sum_{i\in S}x_{i}$ to the oracle, as well as an acceptable “window” $\omega\in$. Intuitively, if the algorithm’s guess is far from the window centered around the true expectation, then the oracle will respond with the answer to a statistical query with tolerance $\omega$. If, however, the guess is sufficiently close to the true value, then the oracle responds with $\checkmark$ to indicate that the current guess is close to the expectation, without revealing another answer.

Note that if the guess is such that \big{|}p_{S}-\left|S\right|v\big{|}\in[2\omega N,4\omega N], the the oracle may respond with some $\omega$-accurate $r\in$ or with $\checkmark$. Of course, if we have a lower bound $\omega_{0}$ on the window over a sequence of guess-and-check queries, we can implement the queries given access to a statistical query oracle with tolerance $\tau\leq\omega_{0}$; it is also clear that a statistical oracle with tolerance $\tau$ can be implemented with access to a guess-and-check oracle with window $\tau/4$. The advantage of using this guess-and-check framework is that it can be implemented in a differentially private manner. This will in turn allow us to give an algorithm for learning $\alpha$-multicalibrated predictors from a small number of samples that generalizes well.

Algorithm 3.2 runs through each possible category $S_{v}$ and if $S_{v}$ is large enough, queries the oracle. The algorithm continues searching for uncalibrated categoires until $x$’s guesses on all sufficiently large categories receive $\checkmark$. By the definition of the guess-and-check oracle, if for some category $S_{v}$ where $\left|S_{v}\right|=\beta N$ the query returns $\checkmark$, then $\bar{v}$ is at most $4\cdot(\alpha\beta N/4)=\alpha\left|S_{v}\right|$ far from the true value $\frac{1}{S_{v}}\sum_{i\in S_{v}}p_{i}^{*}$. Thus, by the stopping condition of the loop, the predictor where all $i\in\lambda(v)$ receive $x_{i}=\bar{v}$ will be $\alpha$-calibrated on every large category. Finally, the algorithm updates $x$ to be $\lambda$-discretized, so by Claim 2.10, $x$ will be $(\alpha+\lambda)$-calibrated. Further, the number of updates necessary to terminate is bounded.

Suppose $\alpha,\lambda>0$ and ${\cal C}\subseteq 2^{{\cal X}}$ where for all $S\in{\cal C}$, $\left|S\right|\geq\gamma N$. Algorithm 3.2 returns $x$ after receiving at most $O(1/\alpha^{3}\lambda\gamma)$ guess-and-check responses where $r\in$ and at most $O(\left|C\right|/\alpha^{4}\lambda\gamma)$ responses $r=\checkmark$.

For some non-$\checkmark$ response on $S_{v}=\left\{i:x_{i}\in\lambda(v)\right\}\cap S$, by the properties of the guess-and-check oracle, we can lower bound the update step size. Recall, we only query on sets wherer $\left|S_{v}\right|=\beta N\geq\alpha\left|S\right|$ with a window of $\omega=\alpha\beta/4$.

Letting $\delta_{v}=r-\bar{v}$. We can measure progress in the same way as in Lemma 3.2.

Let $\nu=\frac{1}{\left|S_{v}\right|}\sum_{i\in S_{v}}(p_{i}^{*}-x_{i})$. By the properties of the guess-and-check oracle, we can rewrite $\delta_{v}$ as $\nu-\eta$ for some $\eta\in[-\omega/\beta,\omega/\beta]$. This gives us a lower bound on the progress as follows.

This concave function in $\eta$ is minimized at an extreme value for $\eta$ (depending on the sign of $\nu$). Noting that $\left|\nu\right|\geq\alpha/2$ and $\left|\eta\right|\leq\omega/\beta=\alpha/4$, we can lower bound our progress by $(\alpha/4)^{2}\left|S_{v}\right|=\alpha^{2}\beta N/16=\alpha^{3}\lambda\gamma N/16$. As $\left\|p^{*}\right\|^{2}\leq N$, we make at most $O(1/\alpha^{3}\lambda\gamma)$ updates upper bounding the number of non-$\checkmark$ responses. By working with a $\lambda$-discretization, there are at most $\left|C\right|/\lambda$ categories to consider in every phase, so we receive at most $O(\left|C\right|/\alpha^{3}\lambda^{2}\gamma)$ $\checkmark$ responses. ∎

For $\alpha,\lambda>0$ and ${\cal C}\subseteq 2^{{\cal X}}$ where for all $S\in{\cal C}$, $\left|S\right|\geq\gamma N$, there is a statistical query algorithm that learns a $(\alpha,\lambda)$-multicalibrated predictor with respect to ${\cal C}$ in $O(\left|{\cal C}\right|/\alpha^{3}\lambda^{2}\gamma)$ queries.

Again, note that our output is, in fact, $(\alpha+\lambda)$-multicalibrated, so taking $\lambda=\alpha$, we obtain a $(2\alpha)$-multicalibrated predictor in $O(\left|{\cal C}\right|/\alpha^{5}\gamma)$ queries.

3 Answering guess-and-check queries from a random sample

Algorithm 3.2 only interacts with the sample through the guess-and-check oracle. Thus, to give a differentially private implementation of the algorithm, it suffices to give a differentially private implementation of the guess-and-check oracle [DR14].

Consider the sequence of queries that Algorithm 3.2 makes to the guess-and-check oracle. We say the sequence $\langle(S_{1},v_{1},\omega_{1}),\ldots,(S_{k},v_{k},\omega_{k})\rangle$ is a $(k,m)$-sequence of guess-and-check queries if, over the course of the $k$ queries, the response to at most $m$ of the queries is some $r\in$, and the responses to the remaining queries are all $\checkmark$. We will assume that we know a lower bound on the minimum window $\omega=\min_{j\in[k]}\omega_{j}$ over all of the queries. We say that some algorithm ${\cal A}$ responds to a guess-and-check query $(S,v,\omega)$ according to a random sample $X$ if its response satisfies the guess-and-check properties with $\sum_{i\in S}p_{i}^{*}$ replaced by its empirical estimate on $X$,

Responding to such a sequence in a differentially private manner can be achieved using techniques from the private multiplicative weights mechanism.

Suppose $\varepsilon,\delta,\omega,\xi>0$ and suppose $X\sim({\cal X}\times\left\{0,1\right\})^{n}$ is a set of $n$ random samples. Then there exists an $(\varepsilon,\delta)$-differentially private algorithm ${\cal A}$ that responds to any $(k,m)$-sequence of guess-and-check queries with minimum window $\omega$ according to $X$ provided

with probability at least $1-\xi$ over the randomness of ${\cal A}$.

Using this differentially private algorithm, we can apply generalization bounds based on privacy developed in [DFH+15c, BNS+16, DFH+15a, DFH+15b] to show that, with a modest increase in sample complexity, we can respond to all $k$ guess-and-check queries.

Let $s_{k}=\langle(S_{1},v_{1},\hat{\omega}_{1}),\ldots,(S_{k},v_{k},\hat{\omega}_{k})\rangle$ be a $(k,m)$-sequence of guess-and-check queries such that for all $j\in[k]$, $\left|S_{j}\right|=\beta_{j}N\geq\beta N$ and $\hat{\omega}_{j}=\Omega(\alpha\beta_{j})$. Then there is an algorithm ${\cal A}$ that, given $n$ random samples $X\sim({\cal X}\times\left\{0,1\right\})^{n}$, responds to $s_{k}$ such that for all $j\in[k]$, the response ${\cal A}(S_{j},v_{j},\hat{\omega}_{j};X)$ satisfies the guess-and-check properties with window $\omega_{j}=\alpha\beta_{j}$ provided

with probability at least $1-\xi$ over the randomness of ${\cal A}$ and the draw of $X$.

This theorem implies that, asymptotically, we can answer the $k$ adaptively chosen guess-and-check queries with only a $\sqrt{1/\alpha\beta}$ factor increase in the sample complexity compared to if we knew the queries in advance. Theorem 3.9 follows from tailoring the proof of the main “transfer” theorem of [BNS+16] (Theorem 3.4) specifically to the requirements of our guess-and-check oracle and applying the differentially private mechanism described in Theorem 3.8. Combining these theorems and Algorithm 3.2 and the fact that $\beta=\alpha\lambda\gamma$, we obtain an algorithm for learning $\alpha$-multicalibrated predictors from random samples.

Suppose $\alpha,\lambda,\gamma,\xi>0$, and ${\cal C}\subseteq 2^{{\cal X}}$ where for all $S\in{\cal C}$, $\left|S\right|\geq\gamma N$. Then there is an algorithm that learns an $(\alpha,\lambda)$-multicalibrated predictor with respect to ${\cal C}$ with probability at least $1-\xi$ from $n=O\left(\dfrac{\log(\left|{\cal C}\right|/\alpha\lambda\gamma\xi)}{\alpha^{4}\cdot\lambda^{3/2}\cdot\gamma^{3/2}}\right)$ samples.

4 Runtime analysis of Algorithm 3.2

Here, we present a high-level runtime analysis of Algorithm 3.2 for learning an $(\alpha,\lambda)$-calibrated predictor on ${\cal C}$. In Lemma 3.6, we claim an upper bound of $O(\left|{\cal C}\right|/\alpha^{3}\lambda^{2}\gamma)$ on the number of guess-and-check queries needed before Algorithm 3.2 converges. Here, we formally argue that each of these queries can be implemented in the random sample model without much overhead, which upper-bounds the running time of the algorithm overall. This upper bound is not immediate from our earlier analysis, as the sets and our predictor are represented implicitly as circuits.

Algorithm 3.2 runs in time $O(\left|{\cal C}\right|\cdot t\cdot{\rm poly}(1/\alpha,1/\lambda,1/\gamma))$, where $t$ is an upper bound on the time it takes to evaluate set membership for $S\in{\cal C}$.

5 The circuit complexity of multicalibrated predictors

As discussed in Section 1.3, an interesting corollary of our algorithm is a theorem about the complexity of representing a multicalibrated predictor. Indeed, from the definition of multicalibration alone, it is not immediately clear that there should be succinct descriptions of multicalibrated predictors; after all, ${\cal C}$ could contain many sets. We argue that the cardinality of ${\cal C}$ is not the operative parameter in determining the circuit complexity of a predictor $x$ that is multicalibrated on ${\cal C}$; instead it is the circuit complexity necessary to describe sets $S\in{\cal C}$, as well as the cardinality of the subsets in ${\cal C}$, and the degree of approximation.

Leveraging Lemma 3.6, we can see that Algorithm 3.2 actually gives us a way to build up a circuit that computes the mapping from individuals to the probabilities of our learned multicalibrated predictor $x$. Suppose that for all sets $S\in{\cal C}$, set membership can be determined by a circuit family of bounded complexity; that is, for all $S\in{\cal C}$, there is some $c_{S}$ with size at most $s$, such that $c_{S}(i)=1$ if and only if $i\in S$. Then we can use this family of circuits to build a circuit that implements $x$. We assume that we maintain real-valued numbers up to $b\geq\log(1/\alpha)$ bits of precision.

Suppose ${\cal C}\subseteq 2^{{\cal X}}$ is a collection of sets where each $S\in{\cal C}$ can be implemented by a boolean circuit $c_{S}$ and for all $S\in{\cal C}$, the size of $c_{S}$ is $O(s)$. Then there is a predictor that is $\alpha$-multicalibrated on ${\cal C}$ implemented by a circuit of size $O((s+b)/\alpha^{4}\gamma)$. Further, Algorithm 3.2 can be used to learn such a circuit.

We describe how to construct a circuit $f_{x}$ that, on input $i$, will output the prediction $x_{i}$ according to the predictor learned by our algorithm. We initialize $f_{x}$ to be the constant function $f_{x}(i)=1/2$ for all $i\in{\cal X}$. Throughout, we will update $f_{x}$ based on the current outputs of $f_{x}$.

We achieve this update by testing membership $i\in S$ and separately testing if the current value $f_{x}(i)=v$; if both tests pass, then we update the value output by $f_{x}(i)$ to be $r$. Specifically, we include a copy of $c_{S}$ and hard-code $v$ and $\delta_{v}=r-\bar{v}$ into the circuit; if $c_{S}(i)=1$ and the current value of $f_{x}(i)$ is in $\lambda(v)$, then we update $f_{x}(i)$ to add the hardcoded $\delta_{v}$ to its current estimate of $x_{i}$; if either test fails, then $f_{x}(i)$ remains unchanged. This logic can be implemented with addition and subtraction circuits to a precision of $\lambda$ with boolean circuits of size $O(b)$. We string these update circuits together, one for each iteration. Learning an $(\alpha/2,\alpha/2)$-multicalibrated predictor with Algoirthm 3.2 only requires $O(\alpha^{4}\gamma)$ updates. By this upper bound, we obtain an $O(\alpha^{4}\gamma)$ upper bound on the resulting circuit size. ∎

Multicalibration and weak agnostic learning

Note that in the algorithm and analysis in Section 3, we’ve assumed nothing about the structure of the underlying $p^{*}$ or ${\cal C}$; the true probabilities could be adversarially chosen and yet, our algorithm guarantees $\alpha$-multicalibration on ${\cal C}$. That said, the running time of the algorithm depends linearly on $\left|{\cal C}\right|$. As we imagine ${\cal C}$ to be a large, rich class of subsets of ${\cal X}$, in many cases linear depedence on $\left|{\cal C}\right|$ will be expensive. Thus, we turn our attention to when we can exploit structure within the collection of subsets ${\cal C}$ to speed up the learning process.

The main running time bottleneck in the algorithms arises from searching for some $S\in{\cal C}$ where calibration is violated. Without any assumptions about ${\cal C}$, we need to loop over the collection; however, if we can find such a set without looping over the entire collection of sets, then we would improve the running time of the algorithm. At a high level, we will show a connection between the agnostic learnability of ${\cal C}$ and the ability to speed up learning a multicalibrated predictor on ${\cal C}$. Imagining the sets $S\in{\cal C}$ as boolean concepts, we show that if it is possible to perform weak agnostic learning over a class ${\cal C}$ efficiently (in the sense of [KMV08, Fel10]), then there is an efficient search algorithm to find an update to the current predictor that will make progress towards multicalibration.

While there are some classes for which we have weak agnostic learners, in general, agnostic learning is considered a notoriously challenging problem. A natural question to ask is whether there is a way to speed up learning a multicalibrated predictor that does not involve agnostic learning. We answer this question in the negative. Roughly, we show that for a concept class ${\cal C}$, we can use any predictor that is multicalibrated on the large sets of ${\cal C}$ to a query for distribution-specific weak agnostic learning on ${\cal C}$. In this sense, the reduction to weak agnostic learning is inherent; any efficient algorithm for multicalibration gives rise to an algorithm for weak agnostic learning.

In all, these results show that weak agnostic learning on a class ${\cal C}$ is equivalent to learning an $\alpha$-multicalibrated predictor with respect to ${\cal C}=\left\{S\in{\cal C}:\left|S\right|\geq\gamma N\right\}$, the large sets defined by ${\cal C}$, up to polynomial factors in $1/\alpha,1/\gamma$ where $\rho$ and $\tau$ will be a function of $\alpha$ and $\gamma$.

For this discussion, we think of boolean concepts $c\in{\cal C}$ as $c:{\cal X}\to\left\{-1,1\right\}$. We will overload the notions of a concept class ${\cal C}$ of boolean functions $c:{\cal X}\to\left\{-1,1\right\}$ and our collection of subsets ${\cal C}\subseteq 2^{\cal X}$; in particular, there is a natural bijection between concepts and sets: a concept $c:{\cal X}\to\left\{-1,1\right\}$ defines a set $S\subseteq 2^{\cal X}$ where $i\in S$ if $c(i)=1$ and $i\not\in S$ if $c(i)=-1$. We will connect the problem of finding a set $S\in{\cal C}$ on which a predictor $x$ violates calibration to the problem of learning over the concept class ${\cal C}$ on a distribution ${\cal D}$.

For some distribution ${\cal D}$ supported on ${\cal X}$ and $x,y\in^{N}$, let $\langle x,y\rangle_{\cal D}=\sum_{i\in{\cal X}}{\cal D}_{i}x_{i}y_{i}$. This inner product measures the correlation between $x$ and $y$ in $^{N}$ over the discrete distribution ${\cal D}$. Throughout our discussion, we will focus on learning over the uniform distribution on ${\cal X}$ and drop explicit reference to ${\cal D}$. As per Remark Remark, this may be a rich distribution over the features of individuals.