# Omnipredictors

Parikshit Gopalan111Email<EMAIL_ADDRESS>
VMware Research  Adam Tauman Kalai222Email<EMAIL_ADDRESS>
Microsoft Research  Omer Reingold333Most of the work performed while visiting
VMware Research. Research supported in part by NSF Award IIS-1908774, The
Simons Foundation collaboration on the theory of algorithmic fairness and The
Sloan Foundation grant G-2020-13941. Email<EMAIL_ADDRESS>
Stanford University  Vatsal Sharan444Most of the work performed while at MIT.
Email<EMAIL_ADDRESS>
USC  Udi Wieder555Email<EMAIL_ADDRESS>
VMware Research

###### Abstract

Loss minimization is a dominant paradigm in machine learning, where a
predictor is trained to minimize some loss function that depends on an
uncertain event (e.g., “will it rain tomorrow?”). Different loss functions
imply different learning algorithms and, at times, very different predictors.
While widespread and appealing, a clear drawback of this approach is that the
loss function may not be known at the time of learning, requiring the
algorithm to use a best-guess loss function. Alternatively, the same
classifier may be used to inform multiple decisions, which correspond to
multiple loss functions, requiring multiple learning algorithms to be run on
the same data. We suggest a rigorous new paradigm for loss minimization in
machine learning where the loss function can be ignored at the time of
learning and only be taken into account when deciding an action.

We introduce the notion of an (${\cal L},\mathcal{C}$)-omnipredictor, which
could be used to optimize any loss in a family ${\cal L}$. Once the loss
function is set, the outputs of the predictor can be post-processed (a simple
univariate data-independent transformation of individual predictions) to do
well compared with any hypothesis from the class $\cal C$. The post processing
is essentially what one would perform if the outputs of the predictor were
true probabilities of the uncertain events. In a sense, omnipredictors extract
all the predictive power from the class $\mathcal{C}$, irrespective of the
loss function in $\cal L$.

We show that such “loss-oblivious” learning is feasible through a connection
to multicalibration, a notion introduced in the context of algorithmic
fairness. A multicalibrated predictor doesn’t aim to minimize some loss
function, but rather to make calibrated predictions, even when conditioned on
inputs lying in certain sets $c$ belonging to a family $\mathcal{C}$ which is
weakly learnable. We show that a $\mathcal{C}$-multicalibrated predictor is
also an (${\cal L},\mathcal{C}$)-omnipredictor, where $\cal L$ contains all
convex loss functions with some mild Lipschitz conditions. The predictors are
even omnipredictors with respect to sparse linear combinations of functions in
$\mathcal{C}$. As a corollary, we deduce that distribution-specific weak
agnostic learning is complete for a large class of loss minimization tasks.

In addition, we show how multicalibration can be viewed as a solution concept
for agnostic boosting, shedding new light on past results. Finally, we
transfer our insights back to the context of algorithmic fairness by providing
omnipredictors for multi-group loss minimization.

###### Contents

  1. 1 Introduction
    1. 1.1 Omnipredictors: one predictor to rule them all
    2. 1.2 Omnipredictors for convex loss minimization
    3. 1.3 Multicalibration and agnostic boosting
    4. 1.4 Technical overview: Omnipredictors from multicalibration
    5. 1.5 Organization of this paper
  2. 2 Related work
  3. 3 Notation and Preliminaries
    1. 3.1 Nice loss functions
  4. 4 Omnipredictors
  5. 5 Multicalibration
    1. 5.1 Multicalibration via covariance
    2. 5.2 Some closure properties of multicalibration
  6. 6 Omnipredictors for convex loss minimization
    1. 6.1 Post-processing for nice loss functions
    2. 6.2 Loss minimization through Multicalibration
    3. 6.3 Limits for omnipredictors from multicalibration
  7. 7 Agnostic boosting via multicalibration
    1. 7.1 Multicalibration can be better than $\mathrm{OPT}$
  8. 8 Omnipredictors in the real valued setting
    1. 8.1 Improved bounds for squared loss
  9. 9 Computing approximately multicalibrated partitions
  10. A Relation to prior definitions of multicalibration
  11. B Algorithm for the multi-class setting
  12. C More Proofs
    1. C.1 Proofs from Section 5
    2. C.2 Proof of Theorem 5.10
    3. C.3 Proof of Lemma 8.4: Stronger bounds for the $\ell_{2}$ loss

##  1 Introduction

In machine learning, it is well-known that the best classifier may depend
heavily on the choice of a loss function, and therefore correctly modeling the
loss function is crucial for success in many applications. Modern machine
learning libraries such as PyTorch, Tensorflow, and scikit-learn each offer a
choice of over a dozen loss functions. However, this poses a challenge in
applications where the loss is not known in advance or multiple losses may be
used. For motivation, suppose you are training a binary classifier to predict
whether a person has a certain medical condition ($y=1$), such as COVID-19 or
some heart condition, given their attributes $x$. The cost for
misclassification may vary dramatically, depending on the application. For an
infectious disease, the question of whether an individual should be allowed to
go out for a stroll is different than whether a person should be allowed to go
to work in a nursing home. Similarly, deciding on whether to advise a daily
dose of aspirin carries very different risks than recommending cardiac
catheterization. Furthermore, medical interventions that may be developed in
the future may carry yet other, unforeseen, risks and benefits that may
require retraining with a different loss function.

We adopt the following problem setup: we are given a distribution
$\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$ where $\mathcal{X}$ is the
domain and $\mathcal{Y}$ is the set of labels (for example $\mathcal{Y}$ can
be $\\{0,1\\}$ or $[0,1]$). On each $x$, we take an action
$t(x)\in\mathbb{R}$, and suffer loss $\ell(y,t(x))$ which depends on the label
$y$ and the action $t(x)$. We will refer to the function
$t:\mathcal{X}\rightarrow\mathbb{R}$ which maps points in the domain to
actions as the hypothesis. Our goal is to find a hypothesis that minimizes
$\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},t(\mathbf{x}))]$ in
comparison to some reference class of hypotheses.666Such a loss function that
is the expectation of a loss for individual examples is called a decomposable
loss in the literature. We will refer to a function $f$ which maps
$\mathcal{X}$ to probability distributions over $\mathcal{Y}$ as a predictor.
The goal of a predictor is to model the conditional distribution of labels
$\mathbf{y}|\mathbf{x}=x$ for every point in the domain.

A classic example of different optimal hypotheses for different loss functions
is the $\ell_{2}$ vs. $\ell_{1}$ losses which are minimized by the mean and
median respectively. Consider a joint distribution $\mathcal{D}$ on
$\mathcal{X}\times[0,1]$, where $\mathbf{x}\in\mathcal{X}$ is a set of
attributes (given) and $\mathbf{y}\in[0,1]$ is an outcome. Consider an $x$
such that the corresponding $y$ is uniform in $[0.8,1]$ with probability $0.6$
and 0 with probability $0.4$. In this case, to minimize the expected
$\ell_{2}$ loss $\ell(y,t)=(y-t)^{2}$ you would set $t(x)=0.45$, whereas to
minimize the expected $\ell_{1}$ loss $\ell(y,t)=|y-t|$ you would set
$t(x)=0.83$. Not only is $t$ different for the two losses, you cannot learn
one from the other. In other words, learning to minimize the $\ell_{2}$ loss
looses information that is necessary to minimize the $\ell_{1}$ loss and vice
versa.

The phenomenon that there is no simple way to get one loss-minimizing
predictor from another is not unique to $\ell_{2}$ vs. $\ell_{1}$ losses.
Consider the distribution illustrated in Figure 1, which is known as a nested
halfspace [18]. Consider a common and simple family of loss functions where
$\ell(y,t)=c_{y}|y-t|$ where $y\in\\{0,1\\}$ and $c_{0},c_{1}\geq 0$ are the
costs of false positives and false negatives respectively. Even for linear
classification, as the ratio $c_{0}/c_{1}$ varies, a different direction is
optimal. The standard ML approach of minimizing a given loss would require
separate classifiers for each loss. There is no clear way to infer the optimal
classifier for one set of costs from the classifier for another; applying
standard post-processing techniques, such as Platt Calibration [31] or
Isotonic Regression [39], to the predictions so that $\Pr[y=1|t=z]\approx z$
will not fix the issue since the optimal direction is different.

###  1.1 Omnipredictors: one predictor to rule them all

This paper advocates a new paradigm for loss minimization: train a single
predictor that could later be used for minimizing a wide range of loss
functions, without having to further look at the data. Why should such
predictors exist, and are they computationally tractable? One source of
optimism is that the ground-truth predictor $f^{*}$ does allow exactly that.

First consider the case of Boolean labels, and let $\mathcal{D}$ denote a
distribution on $\mathcal{X}\times\\{0,1\\}$ (our results also apply to real-
valued outcomes). We define
$f^{*}(x)=\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}}[\mathbf{y}|x]\in[0,1]$
to be the conditional expectation of the label for $\mathbf{x}$. The value
$t(x)$ which minimizes the loss
$\operatorname*{\mathbf{E}}_{\mathbf{y}|x}[\ell(\mathbf{y},t(x))]$ depends
only on $f^{*}(x)$. Furthermore, as long as $\ell$ is smooth and easy to
compute, $t$ can easily be computed from $f^{*}$. We denote the univariate
post-processing function that optimizes loss $\ell$ given true probabilities
by $k_{\ell}^{*}:[0,1]\rightarrow\mathbb{R}$. So for example for
$\ell_{2}(y,t)=(y-t)^{2}$, we have $k_{\ell_{2}}^{*}(p)=p$ and for
$\ell_{1}(y,t)=|y-t|$, $k_{\ell_{1}}^{*}(p)=\mathbbm{1}(p\geq 1/2)$.

Figure 1: Binary classification with target function
$\Pr[y=1|x]=\frac{x_{1}}{x_{1}+x_{2}}$ for $x\in[0.1,1]^{2}$. As can be seen
from the level sets, the direction of the optimal linear classifier varies
depending on the cost of false positives and negatives. This example is
learned to near optimal loss for any loss with fixed costs of false-positives
and false-negatives by an omnipredictor for the class ${\cal
C}=\\{x_{1},x_{2}\\}$.

For every loss function $\ell$, the composition of $f^{*}$ and $k_{\ell}^{*}$
minimizes the loss $\ell$, even conditioned on complete knowledge of
$\mathcal{D}$. The connection between perfect predictors and choosing the
optimal action is well understood and plays an important role in the
Statistics literature on proper scoring rules and forecasting (cf. [33]). But
learning $f^{*}$ from samples from $D$ is information-theoretically and
computationally impossible in general. The natural approach is to learn a
model $f$ for $f^{*}$ and then compose $k_{\ell}^{*}$ with $f$. Common
instantiations of this approach (such as using logistic regression to model
$f$) do not yield particularly strong guarantees in the realistic non-
realizable setting where $f^{*}$ does not come from the class of model
distributions (see the further discussion in Section 2). Our main conceptual
contribution is to introduce the notion of Omnipredictors, which provide a
framework to derive strong rigorous guarantees using this composition approach
even in the non-realizable setting.

The goal of an omnipredictor is to learn a predictor $f$ that could replace
$f^{*}$ for the purpose of minimizing any loss from a class $\mathcal{L}$
compared to some hypothesis class $\mathcal{C}$. For a family $\mathcal{L}$ of
loss functions, and a family $\mathcal{C}$ of hypotheses
$c:\mathcal{X}\rightarrow\mathbb{R}$, we introduce the notion of an (${\cal
L},\mathcal{C}$)-omnipredictor, which is a predictor
$f:\mathcal{X}\rightarrow[0,1]$ with the property that for every loss function
$\ell\in{\cal L}$, there is a post-processing function $k_{\ell}$ such that
the expected loss of the composition $k_{\ell}\circ f$ measured using $\ell$
is almost as small as that of the best hypothesis $c\in\mathcal{C}$.

###  1.2 Omnipredictors for convex loss minimization

Omnipredictors can replace perfect predictors for the sake of minimizing loss
in $\cal L$ compared with the class $\mathcal{C}$. In this sense they extract
all the predictive power of $\mathcal{C}$ for such tasks. The key questions
are of efficiency and simplicity: how strong a learning primitive do we need
to assume to get an omnipredictor for $\mathcal{L},\mathcal{C}$, and how
complex is the predictor. The main result of this paper is that one can
efficiently learn simple omnipredictors for broad classes of loss functions
and hypotheses, from weak learning primitives.

#### Our main result.

We show that for any hypothesis class $\mathcal{C}$, a weak agnostic learner
for $\mathcal{C}$ is sufficient to efficiently compute an
$(\mathcal{L},\mathcal{C})$-omnipredictor where $\mathcal{L}$ consists of all
decomposable convex loss functions obeying mild Lipshcitz conditions; it
includes popular loss functions such as the $\ell_{p}$ losses for all $p$, the
exponential loss and the logistic loss. Weak agnostic learnability captures a
common modeling assumption in practice, and is a well-studied notion in the
computational learning literature [3, 25, 21, 10]. The weak agnostic learning
assumption says that if there is a hypothesis in $\mathcal{C}$ that labels the
data reasonably well (say with $0$-$1$ loss of $0.7$), then we can efficiently
find one that has a non-trivial advantage over random guessing (say with
$0$-$1$ loss of $0.51$). In essence, our main result derives strong optimality
bounds for a broad and powerful class of loss functions starting from a weak
optimality condition for the $0$-$1$ loss.

Perhaps surprisingly, our results are obtained not via the machinery of convex
optimization, but by drawing a connection to work on fairness in machine
learning, specifically the notion of multicalibration [15]. Multicalibration
is a notion motivated by the goal of preventing unfair treatment of protected
sub-populations in prediction; it does not explicitly consider loss
minimization. We draw a connection to omnipredictors using a covariance-based
recasting of the notion of multicalibration, that clarifies the connection of
multicalibration to the literature on boosting [27, 17, 21]. A multicalibrated
predictor satisfying this definition can be computed by a branching program,
building on existing work in the literature on boosting [29, 27, 17] and
multicalibration [13]. This new connection shows that the well-known boosting
by branching programs algorithms [23, 29] yield multicalibrated predictors and
can in fact be used to derive strong guarantees for a broad family of convex
loss functions.

The post-processing function $k_{\ell}$ used in our positive results is
essentially $k^{*}_{\ell}$ with small modifications. As the example in Figure
1 demonstrates, even in natural cases, an (${\cal
L},\mathcal{C}$)-omnipredictor cannot be a function in $\mathcal{C}$; in other
words, the learning task we solve is inherently not proper.

#### Omnipredictors for larger classes.

An advantage of our covariance-based notion of multicalibration is that it is
closed under linear combinations. We use this to show that any multicalibrated
predictor for $\mathcal{C}$ is in fact an
$(\mathcal{L},\mathrm{Lin}_{\mathcal{C}})$-omnipredictor where
$\mathrm{Lin}_{\mathcal{C}}$ consists of linear combinations of functions in
$\mathcal{C}$. We give negative results for slightly larger classes, showing
that a multicalibrated predictor for $\mathcal{C}$ is not necessarily an
omnipredictor for the class $\mathrm{Thr_{\mathcal{C}}}$ which consist of
thresholds of functions in $\mathcal{C}$. Similarly, it is need not be an
omnipredictor for the class $\mathcal{C}$ but with non-convex loss functions.
This shows that the connection between multicalibration and omnipredictors
that we present is fairly tight.

#### Omnipredictors for multi-group loss minimization

A very recent line of research defines multi-group notions of loss
minimization [2, 32].777The notion of loss in [32] is more general than in
this paper and includes global functions of loss rather than the expectation
of loss on individual elements. See further comparison in Section 2. Multi-
group loss minimization is well motivated from the point of view of fairness
as it guarantees that no sub-population’s loss is sacrificed for the sake of
global loss minimization. Say we have a collection of sub-populations $\cal T$
and hypotheses $\cal P$ and seek to take actions such that for every set
$T\in\cal T$, our actions can compare with the best hypothesis in $P\in\cal P$
for that sub-population $T$. Indeed, one may wish to vary the loss function
for various subgroups: say in a medical scenario where different age-groups
are known to react differently to the same treatment.

We derive strong multi-group loss minimization guarantees using the closure of
multicalibration under conditioning on subsets in $\mathcal{C}$. We show that
in the scenario above, a multicalibrated predictor for
$\mathcal{T}\times\mathcal{P}=\\{T\cdot P,T\in\mathcal{T},P\in\mathcal{P}\\}$
gives an $(\mathcal{L},\mathcal{P})$-omnipredictor for every sub-population
$T\in\cal T$. Hence given a sub-population $T\in\cal T$ and a loss
$\ell\in\mathcal{L}$, the predictions of the omnipredictor can be post-
processed to be competitive with the best hypothesis from $\cal P$ for that
loss function $\ell$ and sub-population $T$.

#### Omnipredictors for real-valued labels.

We extend the notion of omnipredictors to the setting where the labels come
from an arbitrary subset $\mathcal{Y}\subseteq\mathbb{R}$. Our primary
interest is in multi-class prediction where $\mathcal{Y}=[k]$ and the bounded
real-valued setting where $\mathcal{Y}=[0,1]$. We show that omnipredictors can
be learned in this setting, for similar families of loss functions, again
assuming weak learnability of $\mathcal{C}$. We also show a stronger bound for
the $\ell_{2}$ loss than what the general theorem implies.

###  1.3 Multicalibration and agnostic boosting

One of our contributions in this work is to formalize and leverage the
connections between multicalibration and the literature on agnostic boosting.
We propose a covariance-based recasting of the notion of multicalibration,
inspired by the literature on boosting [17, 21]. We show that this definition
has several advantages, for instance it implies some general closure
properties for multicalibration. In the other direction, our work suggests
multicalibration as a solution concept for agnostic boosting. By specializing
our main result on omnipredictors to the $\ell_{1}$ loss, we derive a new
proof of the classic result of [22] on agnostic learning. We elaborate on
these connections in this subsection.

#### A covariance-based formulation of multicalibration.

Calibration has been well-studied in the statistics literature in the context
of forecasting [7]. It was introduced to the algorithmic fairness literature
by [24]. In the setting of Boolean labels, we are given a distribution
$\mathcal{D}$ on $\mathcal{X}\times\\{0,1\\}$ of labelled examples, and wish
to learn a predictor $f:\mathcal{X}\rightarrow[0,1]$, where $f(x)$ is our
model for $\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{y}|x]$. The
predictor $f$ is (approximately) calibrated if for every value $v$ in its
range we have that $\Pr[y=1|f(x)=v]\approx v$. This means that the prediction
$f(x)$ can be interpreted as a probability that is correct in expectation over
individuals in the same level set of $f$. By itself, calibration is a very
weak property, both in terms of fairness as well as in terms of accuracy. This
motivated [15] to introduce the notion of multicalibration that asks for $f$
to be calibrated on a rich collection of subgroups $\mathcal{C}$ rather than
just a few protected sets.

We draw a connection to omnipredictors by introducing a covariance-based
recasting of the notion of multicalibration, that clarifies the connection to
the literature on boosting [17, 27, 21]. Prior definitions consider
multicalibration for a family $\mathcal{C}$ of sets or equivalently Boolean
functions $c:\mathcal{X}\rightarrow\\{0,1\\}$, whereas we allow arbitrary
real-valued functions. Rather than work with predictors, we define
multicalibration for partitions, inspired by the recent work of [13] in the
unsupervised setting. A partition $\mathcal{S}=\\{S_{1},\ldots,S_{m}\\}$ of
the domain is a collection of disjoint subsets whose union is $\mathcal{X}$.
Intuitively, we want these sets to be (approximate) level sets for $f^{*}$. We
let $\mathcal{D}_{i}$ denote the distribution $\mathcal{D}$ conditioned on
$\mathbf{x}\in S_{i}$. The partition $\mathcal{S}$ gives a canonical predictor
$f^{\mathcal{S}}$ where for each $x\in S_{i}$, we predict
$f^{\mathcal{S}}(x)=\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[\mathbf{y}]$.
In analogy to boosting (see, e.g., [17, 27, 21]), we phrase multicalibration
in terms of the covariance888Recall that
$\operatorname*{{\bf{Cov}}}[\mathbf{z}_{1}\mathbf{z}_{2}]=\operatorname*{\mathbf{E}}[\mathbf{z}_{1}\mathbf{z}_{2}]-\operatorname*{\mathbf{E}}[\mathbf{z}_{1}]\operatorname*{\mathbf{E}}[\mathbf{z}_{2}]$
between $c(\mathbf{x})$ and $\mathbf{y}$ conditioned on each state $S_{i}$ of
the partition. We say that $\mathcal{S}$ is $\alpha$-multicalibrated for
$\mathcal{C}$ if for every $i\in[m]$ and $c\in\mathcal{C}$,

$\displaystyle\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbf{y}]\Bigr{\rvert}\leq\alpha.$
(1)

In reality, we will weaken the definition to only hold in expectation under
$\mathcal{D}$ rather than require it for every state of the partition, but we
ignore this distinction for now. While our definition is formulated
differently, we show that it matches the original definition when
$\mathcal{C}$ consists of Boolean functions (see Lemma A.3 and the discussion
in Appendix A). This lets us adapt existing algorithms in the literature [29,
17, 13] to give an efficient procedure to compute multicalibrated partitions,
assuming a weak agnostic learner for the class $\mathcal{C}$. Working with
covariance which is bilinear lets us derive powerful closure properties for
multicalibration. For instance, if $f$ is multicalibrated with respect to
$\mathcal{C}$ it is also multicalibrated (with some deterioration in
parameters) with respect to the class $\mathrm{Lin}_{\mathcal{C}}$ of (sparse)
linear combinations of $\mathcal{C}$. We also show that conditioning on sets
in $\mathcal{C}$ preserves multicalibration.

#### Agnostic boosting from multicalibration.

The problem of agnostically learning a class $\mathcal{C}$ is, given samples
from a distribution $\mathcal{D}$ on $\mathcal{X}\times\\{0,1\\}$, find a
binary classifier $f:\mathcal{X}\rightarrow\\{0,1\\}$ whose classification
error aka $0$-$1$ loss defined as
$\mathrm{err}(f)=\Pr_{\mathcal{D}}[f(\mathbf{x})\neq\mathbf{y}]$ is not much
larger than that of the best classifier from $\mathcal{C}$. The boosting
approach to agnostic learning is to start from a weak agnostic learner, which
only guarantees some non-trivial correlation with the labels, and boost it to
obtain a classifier that agnostically learns $\mathcal{C}$ [3, 25, 10].

Our work suggests multicalibration as a solution concept for agnostic
boosting. Indeed, our definition of multicalibration based on covariance
parallels that of [17, 27], who use covariance as a splitting criterion. Hence
when the algorithms of [29, 17, 27] terminate, they have found a
multicalibrated partition. Viewed in this light, our results show that these
algorithms give a broad and powerful guarantee beyond just $0$-$1$ loss: they
are competitive with sparse linear combinations over $\mathcal{C}$ in
optimizing a large family of convex, Lipschitz loss functions (with a simple
post-processing step). While AdaBoost or Logistic regression are known to
minimize the exponential and logistic loss respectively over sparse linear
combinations of $\mathcal{C}$ [36], no similar result was known for algorithms
based on branching programs [29, 17, 27].

Let us now focus on $0$-$1$ loss. Since $0$-$1$ loss for Boolean functions
equals $\ell_{1}$ loss, our results apply to it. We show that for any
multicalibrated partiton $\mathcal{S}$, the predictor $k_{\ell_{1}}\circ
f^{\mathcal{S}}$ is competitive not just with the best classifier in
$\mathcal{C}$, but with the best classifier in the larger class $\mathcal{H}$
of functions that are approximated (in $\ell_{1}$) by linear combinations of
$\mathcal{C}$. This lets us re-derive the classic result of [22] on agnostic
learning. While not a new result, we feel that our treatment clarifies and
unifies existing results (see Theorem 7.3 and the comments following it). It
strengthens known results on the noise-tolerant boosting abilities of such
programs [27, 25]. Further, we show examples where
$\mathrm{err}(k_{\ell_{1}}\circ f^{\mathcal{S}})$ is markedly better than any
linear combination of $\mathcal{C}$, showing that multicalibration is a
stronger solution concept than those considered previously.

###  1.4 Technical overview: Omnipredictors from multicalibration

Let $\ell:\\{0,1\\}\times\mathbb{R}\rightarrow\mathbb{R}$ be a loss function
that takes a label $y\in\mathcal{Y}$ and an action $t\in\mathbb{R}$ as
arguments. A hypothesis $t:\mathcal{X}\rightarrow\mathbb{R}$ which prescribes
an action for every point in the domain suffers a loss of
$E_{\mathcal{D}}[\ell(\mathbf{y},t(\mathbf{x})]$. Our main technical result
states that if $\mathcal{S}$ is multicalibrated, then $f^{\mathcal{S}}$ is an
$(\mathcal{L},\mathcal{C})$-omnipredictor where $\mathcal{L}$ consists of all
convex losses satisfying some mild Lipschitz conditions. Here for simplicity,
we make the stronger assumption that the loss $\ell(y,t)$ is convex and
Lipschitz everywhere as a function of $t$. We do not assume anything about the
relation between $\ell(0,t)$ and $\ell(1,t)$.

We sketch how multicalibration leads $f^{\mathcal{S}}$ to be an omnipredictor,
emphasizing intuition over rigor. We will argue that the loss
$\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},k^{*}_{\ell}(f^{\mathcal{S}}(\mathbf{x}))]$
is not much more than
$\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},c(\mathbf{x}))]$ for
any $c\in\mathcal{C}$. We fix a state $S_{i}\in\mathcal{S}$ and analyze the
loss suffered by $c(x)$ under $\mathcal{D}_{i}$ as follows.

  1. 1.

Reduction to predicting two values: In general, $c(x)$ could take on many
values under $\mathcal{D}_{i}$. However, since the goal is to minimize
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[\ell(\mathbf{y},c(\mathbf{x}))]$,
we can pretend that $c$ takes only two values,
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|\mathbf{y}=0}[c(\mathbf{x})]$
whenever $\mathbf{y}=0$ and
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|\mathbf{y}=1}[c(\mathbf{x})]$
whenever $\mathbf{y}=1$ (we say pretend since the actions taken can only
depend on $x$ and not on $y$). By the convexity of the loss functions, this
can only reduce the expected loss.

  2. 2.

Reduction to predicting one value:  A consequence of multicalibration, which
follows from the definition of covariance, is that conditioning on the label
$\mathbf{y}=b$ does not change the expectation of $c(\mathbf{x})$ much.
Formally for $b\in\\{0,1\\}$,

$\displaystyle\Pr_{\mathcal{D}_{i}}[\mathbf{y}=b]\left|\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|\mathbf{y}=b}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]\right|\leq\alpha.$
(2)

Since the loss functions $\ell(b,t)$ are Lipschitz in $t$ for $b\in\\{0,1\\}$,
we can replace
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|\mathbf{y}=b}[c(\mathbf{x})]$
with $\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]$ with only a
small increase in the loss. At this point, we have reduced to the case where
$c$ predicts the constant value
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]$ under
$\mathcal{D}_{i}$.

  3. 3.

The best value:  Let
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[\mathbf{y}]=p_{i}$, thus
$\mathbf{y}$ is distributed as a Bernoulli random variable with parameter
$p_{i}$. Thus, the best single value to predict is $k^{*}_{\ell}(p_{i})$,
which is the minimizer of the expected loss
$p_{i}\ell(0,t)+(1-p_{i})\ell(1,t)$. But we defined $f^{\mathcal{S}}(x)=p_{i}$
for all $x\in S_{i}$, so
$k^{*}_{\ell}(p_{i})=k^{*}_{\ell}(f^{\mathcal{S}}(x)$).

We conclude that post-processing the predictions $f^{\mathcal{S}}$ by the
function $k^{*}_{\ell}$ is nearly as good as any $c\in\mathcal{C}$ for
minimizing expected loss under $\mathcal{D}$ for any convex, Lipschitz loss
function $\ell$ (up to an additive error that goes to $0$ with $\alpha$).
Hence $f^{\mathcal{S}}$ is an $(\mathcal{L},\mathcal{C})$-omnipredictor. As a
consequence, having a weak agnostic learner for $\mathcal{C}$ suffices to
learn a predictor that can minimize any such loss function competitively to
predictors in $\mathcal{C}$, even without knowing the loss function in
advance.

###  1.5 Organization of this paper

We survey related work in Section 2, and set up notation in Section 3. We
define the notion of omnipredictors in Section 4. We introduce our notion of
multicalibration in Section 5 and derive closure properties for it in Section
5.2. A detailed discussion of how our definition compares to previous
definitions can be found in Appendix A. We prove our main result on
$(\mathcal{L},\mathcal{C})$-omnipredictors for binary labels (Theorem 6.3) in
Section 6, along with the extensions to $\mathrm{Lin}_{\mathcal{C}}$
(Corollary 6.5), and its application to multi-group loss minimization
(Corollary 6.6). Section 6.3 shows that multicalibration for $\mathcal{C}$
does not yield omnipredictors for thresholds of $\mathcal{C}$ or for non-
convex losses. Section 7 presents applications of our results to agnostic
learning, and an example showing that multicalibration can give stronger
guarantee than $\mathrm{OPT}(\mathrm{Lin}_{\mathcal{C}})$. We present the
extension to the real valued setting in Section 8, and derive a stronger bound
for $\ell_{2}$ loss in Theorem 8.3. We present an algorithm for computing
multicalibrated partitions in Section 9.

##  2 Related work

While the notion of an omnipredictor is introduced in this work, our
definitions draw on two previous lines of work. The first is the notion of
multicalibration for predictors that was defined in the work of Herbert-
Johnson et al. [15].999See also [26], who in parallel with [15] introduced
notions of multi-group fairness. A detailed discussion of how our definitions
of multicalibration compare to previous definitions appears in Appendix A. The
other is work on boosting by branching programs of Mansour-McAllester [29],
which built on Kearns-Mansour [23] and the notion of correlation boosting [17,
27].

#### Group fairness and multicalibration.

While multicalibration was introduced with the motivation of algorithmic
fairness, it has been shown to be quite useful from the context of accuracy
when learning in an heterogeneous environment. This was done both
experimentally [19, 6] and in real-life implementations [4]. From a
theoretical perspective, it has been shown in [15] that post-processing a
predictor to make it multicalibrated cannot increase the $\ell_{2}$ loss. This
was extended to showing some optimality results of multicalibrated predictors
with respect to $\ell_{2}$ and even log-loss [12, 20]. Multicalibrated
predictors are also connected to loss minimization through the notion of
outcome-indistinguishability [9] in the work of [32]. Outcome
indistinguishability shows that a multicalibrated predictor is
indistinguishable from the true probabilities predictor in a particular
technical sense. In [32] this is used to create a predictor that can be used
to minimize a rather general and potentially global notion of loss even when
restricted to sub-groups. The proof constructs a family of distinguishers, for
a fixed loss function, such that if there exists a subset on which the a
predictor doesn’t minimize the loss function then one of the predictors can
distinguish the predictor from the true-probabilities predictor in the sense
of outcome indistinguishability. The main way in which all of these results
are different from what we show is that they do not seek to simultaneously
allow for the minimization of such a rich family of loss functions. In the
case of [32], since the result goes through outcome indistinguishability, to
minimize a loss with respect to a class $\mathcal{C}$, a predictor needs to be
multicalibrated with respect to a different class that relies on the loss
function and incorporates the reduction from multicalibration and outcome
indistinguishability. In contrast, our result addresses minimization of a
family of losses that may not be known at the time of learning, and we assume
the learnability of $\mathcal{C}$ alone. Convexity of the losses plays a key
role in our upper bounds.

#### Agnostic boosting.

Our work is closely related to work on boosting via branching programs [23,
29, 27, 17]. Indeed, the splitting criterion used in the work of Kalai [17] is
precisely that
$\operatorname*{{\bf{Cov}}}[c(\mathbf{x}),\mathbf{y}]\geq\alpha$ for some
$c\in\mathcal{C}$, for the task of learning generalized linear models. The
okay learners in the work of [27] are also based on having non-trivial
Covariance with the target. Our results show that upon termination, these
algorithms yields an approximately multicalibrated partition; hence we can
view multicalibration as a solution concept for the output of Boosting by
Branching Program family of algorithms. It was known that these algorithms
have stronger noise tolerance properties than potential based algorithms such
as AdaBoost, see [27, 25]. Our results significantly strengthen our
understanding of the power of these algorithms, showing that they give
guarantees for a broad family of convex loss functions, and not just $0$-$1$
loss.

#### Naive instantiations of the composition approach.

The obvious attempt to building omnipredictors would be to learn a model $f$
for $f^{*}$ using a model family $\mathcal{F}$ such as logistic regression,
and then compose it with the right post-processing function $k_{\ell}^{*}$ for
a given loss $\ell$. In the context of binary classification, for certain
families of non-decomposable accuracy metrics (including $F$-scores and AUC),
it is shown in [30, 8] that this approach gives the best predictor for the
hypothesis class $\mathcal{C}$ of binary classifiers derived by thresholding
models from $\mathcal{F}$.

These results can be seen as a form of omnipredictors, but with strong
restrictions on $\mathcal{L}$ and $\mathcal{C}$. Their results do not apply to
the decomposable convex losses we consider; indeed it seems unlikely that the
output of logistic regression can give reasonable guarantees for say the
exponential loss or squared loss, even with post-processing. More importantly,
our results hold for arbitrary classes $\mathcal{C}$ that are weakly
agnostically learnable. For any such class, we show how to construct a model
$f$ which is an omnipredictor. In contrast, their results prove optimality for
a rather limited hypothesis class $\mathcal{C}$ derived from the model family
$\mathcal{F}$.

#### Condtional density estimation

For real-valued $y\in\mathbb{R}$, an omnipredictor solves the problem of
Conditional Density Estimation (CDE) [14]. While CDE is recognized as an
important problem in practice and a number of CDE algorithms have been
proposed, it has received little attention in the computational learning
theory literature. The notion of omnipredictor is related to the statistical
notion of a sufficient statistic, which is a statistic that captures all
relevant information about a distribution.

#### Surrogate loss functions for classification

There is a large literature in statistics which shows that a convex surrogate
loss function (with certain properties) can be used instead of the hard to
optimize 0-1 loss, and any hypothesis $c\in\mathcal{C}$ which minimizes the
surrogate loss will also minimize the original 0-1 loss with respect to
$\mathcal{C}$ [28, 37, 1]. There are also similar results for the multi-class
0-1 loss [38], and in the asymmetric setting when the false positive and false
negative costs are known [34]. However, this line of work is quite different
from ours, crucially an $(\mathcal{L},\mathcal{C})$-omnipredictor optimizes
not just for a single loss but for any loss in the family $\mathcal{L}$ (such
as different false positive and false negative costs, we recall that as Fig. 1
shows this cannot be achieved with a single hypothesis from $\mathcal{C}$).

##  3 Notation and Preliminaries

Let $\mathcal{D}$ denote a distribution on $\mathcal{X}\times\mathcal{Y}$. The
set $\mathcal{X}$ represents points in our space, it could be continuous or
discrete. The set $\mathcal{Y}$ represents the labels, we will typically
consider $\mathcal{Y}=\\{0,1\\}$, $\mathcal{Y}=[k]$ or $\mathcal{Y}=[0,1]$. We
use $(\mathbf{x},\mathbf{y})\sim\mathcal{D}$ where
$\mathbf{x}\in\mathcal{X},\mathbf{y}\in\mathcal{Y}$ to denote a sample from
$\mathcal{D}$. We use boldface for random variables. For any
$S\subset\mathcal{X}$, let
$\mathcal{D}(S)=\Pr_{\mathbf{x}\sim\mathcal{D}}[\mathbf{x}\in S]$. We will use
$\mathbf{y}\sim\mathrm{Ber(p)}$ to denote sampling from the Bernoulli
distribution with parameter $p$.

Let $\mathcal{C}=\\{c:\mathcal{X}\rightarrow\mathbb{R}\\}$ be a collection of
real-valued hypotheses on a domain $\mathcal{X}$, which could be continuous or
discrete. The hypotheses in $\mathcal{C}$ should be efficiently computable,
and the reader can think of them as monomials, decision trees or neural nets.
We will denote

$\left\lVert\mathcal{C}\right\rVert_{\infty}=\max_{c\in\mathcal{C},x\in\mathcal{X}}|c(x)|.$

A loss function $\ell$ takes a label $y\in\mathcal{Y}$, an action
$t\in\mathbb{R}$ and returns a loss value $\ell(y,t)$. Common examples are the
$\ell_{p}$ losses $\ell_{p}(y,t)=|y-t|^{p}$ and logistic loss
$\ell(y,t)=\log(1+\exp(-yt))$. The problem of minimizing a loss function
$\ell$ is to learn a hypotheses $h:\mathcal{X}\rightarrow\mathbb{R}$ such that
the expected loss
$\ell_{\mathcal{D}}(h){:=}\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},h(\mathbf{x}))]$
is small. Let
$\mathcal{L}=\\{\ell:\mathcal{Y}\times\mathbb{R}\rightarrow\mathbb{R}\\}$
denote a collection of loss functions.

A partition $\mathcal{S}=\\{S_{1},\ldots,S_{m}\\}$ of the domain
$\mathcal{X}$, is a collection of disjoint subsets whose union equals
$\mathcal{X}$, we refer to $m$ as its size. We refer to each $S_{i}$ as a
state in the partition. Given a partition
$\mathcal{S}=\\{S_{1},\ldots,S_{m}\\}$ of the domain $\mathcal{X}$, define the
conditional distribution $\mathcal{D}_{i}$ over $S_{i}\times\mathcal{Y}$ as
$\mathcal{D}_{i}=\mathcal{D}|\mathbf{x}\in S_{i}$.

A (binary) predictor is a function $f:\mathcal{X}\rightarrow[0,1]$, where
$f(x)$ is interpreted as the probability conditioned on $x$ that
$\mathbf{y}=1$. We define the ground truth predictor as
$f^{*}(x):={\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{y}|\mathbf{x}=x]}$.
For general label sets $\mathcal{Y}$, let $\mathcal{P}(\mathcal{Y})$ denote
the space of probability distributions on $\mathcal{Y}$. Define the ground
truth predictor $f^{*}:\mathcal{X}\rightarrow\mathcal{P}(\mathcal{Y})$ where
$f^{*}(x)$ is the distribution of $\mathbf{y}|x$. A predictor is a function
$f:\mathcal{X}\rightarrow\mathcal{P}(\mathcal{Y})$ which is intended to be an
approximation of $f^{*}$.

We denote by $g\circ h$ the composition of functions.

###  3.1 Nice loss functions

We say $\ell:\mathcal{Y}\times\mathbb{R}\rightarrow\mathbb{R}$ is a convex
loss function, if $\ell(y,t)$ is a convex function of $t$ for every
$y\in\mathcal{Y}$. Note that in the binary setting, our formulation allows for
binary classification with different false-positive/negative costs, e.g.,
$\ell(y,t)=c_{y}|t-y|$ where $c_{0}$ and $c_{1}$ are the different costs. A
function $f:\mathbb{R}\rightarrow\mathbb{R}$ is said to be $B$-Lipschitz over
interval $I$ if $|f(t)-f(t^{\prime})|\leq B|t-t^{\prime}|$ for all
$t,t^{\prime}\in I$. We say the function is $B$-Lipschitz if the condition
holds for $I=\mathbb{R}$. While assuming the loss is $B$-Lipschitz is
sufficient for us, we can work with a weaker notion that only requires the
Lipschitz property on a sufficiently large interval. This weaker notion covers
most commonly used loss functions such as the exponential loss that are not
Lipschitz everywhere. Also, we will define loss functions in the setting of
labels that come from $\mathcal{Y}$. In this section though, we will focus on
the case $\mathcal{Y}=\\{0,1\\}$.

######  Definition 3.1.

For $B,\epsilon>0$, a convex loss function
$\ell:\mathcal{Y}\times\mathbb{R}\rightarrow\mathbb{R}$ is $(B,\epsilon)$-nice
if there is a closed interval $I=I_{\ell}\subseteq\mathbb{R}$ satisfying:

  1. 1.

($B$-Lipschitzness) For all $y$, $\ell(y,t)$ is $B$-Lipschitz in $t$ over
$I_{\ell}$:

$\forall y\in\mathcal{Y},\ t,t^{\prime}\in
I_{\ell},|\ell(y,t)-\ell(y,t^{\prime})|\leq B|t-t^{\prime}|.$

  2. 2.

($\epsilon$-optimality) For $y\in\mathcal{Y}$, $I_{\ell}$ contains an
$\epsilon$-optimal minimizer of $\ell(y,t)$:

$\inf_{t\in I_{\ell}}\ell(y,t)\leq\inf_{t\in\mathbb{R}}\ell(y,t)+\epsilon.$

Let $\mathcal{L}(B,\epsilon)$ be the set of all $(B,\epsilon)$-nice functions.

Observe that if a function is $B$-Lipschitz on $\mathbb{R}$, then it is
$(B,0)$-nice with $I_{\ell}=\mathbb{R}$.

For a closed interval $I=[c,d]$ define the function

$\displaystyle\operatorname{clip}(t,I)=\begin{cases}c\ \text{if}\ t\leq c\\\
t\ \text{if}\ c\leq t\leq d\\\ d\ \text{if}\ d\leq t.\end{cases}$

We use some simple facts about this function without proof, the first is a
simple consequence of $\epsilon$-optimality and convexity.

######  Lemma 3.2.

If $\ell$ is $(B,\epsilon)$-nice, then
$\ell(y,\operatorname{clip}(t,I_{\ell}))\leq\ell(y,t)+\epsilon$. The function
$\operatorname{clip}(t,I_{\ell})$ is $1$-Lipschitz as a function of $t$.

Here are a few examples of nice loss functions:

  * •

Binary classification with different false-positive/negative costs, e.g.,
$\ell(y,t)=\kappa_{y}|y-t|$ where $\kappa_{0}\neq\kappa_{1}$ are the different
costs. Here $I_{\ell}=[0,1],B=\max(\kappa_{0},\kappa_{1}),\epsilon=0$.

  * •

The $\ell_{p}$ losses for $p\geq 1$:

$\ell_{p}(y,t){:=}|y-t|^{p}$

take $I_{\ell}=[0,1],B=p,\epsilon=0$.

  * •

The exponential loss $\ell(y,t)=e^{(1-2y)t}$. Here, for any $\epsilon>0$, we
can take $I_{\ell}=[-\ln(1/\epsilon),\ln(1/\epsilon)]$ and $B=1/\epsilon$.

  * •

The logistic loss $\ell(y,t)=\log(1+\exp((1-2y)t))$. Here we take
$I_{\ell}=\mathbb{R}$, $B=1$ and $\epsilon=0$.

  * •

The hinge loss $\ell(y,t)=\max(0,1+(1-2y)t)$. Here we take
$I_{\ell}=\mathbb{R}$, $B=1$ and $\epsilon=0$.

It is worth noting that only for exponential loss did we need $\epsilon>0$.

##  4 Omnipredictors

In this section, we define our notion of Omnipredictors. Our definitions are
simpler for the case of binary labels where $\mathcal{Y}=\\{0,1\\}$, hence we
present that case first. Recall that for a predictor $h$,
$\ell_{\mathcal{D}}(h)$ is the expected loss of $h$ under $\mathcal{D}$.

######  Definition 4.1 (Omnipredictor).

Let $\mathcal{C}$ be family of functions on $\mathcal{X}$, and let
$\mathcal{L}$ be a family of loss functions. The predictor
$f:\mathcal{X}\rightarrow[0,1]$ is an
$(\mathcal{L},\mathcal{C},\delta)$-omnipredictor if for every
$\ell\in\mathcal{L}$ there exists a function $k:[0,1]\rightarrow\mathbb{R}$ so
that

$\ell_{\mathcal{D}}(k\circ
f)\leq\min_{c\in\mathcal{C}}\ell_{\mathcal{D}}(c)+\delta.$

The definition states that for every loss $\ell$, there is a simple
(univariate) transformation $k$ of the predictions $f$, such that the
composition $k\circ f$ has loss comparable to the best hypothesis
$c\in\mathcal{C}$, which is chosen tailored to the loss $\ell$.

Setting aside efficiency considerations, it is easy to show that $f^{*}$ is an
omnipredictor for every $\mathcal{C},\mathcal{L}$.

######  Lemma 4.2.

For every $\mathcal{C},\mathcal{L}$, the ground-truth predictor $f^{*}$ is an
$(\mathcal{L},\mathcal{C},0)$-omnipredictor.

###### Proof.

By the definition of omnipredictors, given an arbitrary loss function
$\ell:\\{0,1\\}\times\mathbb{R}\rightarrow\mathbb{R}$, our goal is to find
$k^{*}_{\ell}:\\{0,1\\}\rightarrow\mathbb{R}$ so that

$\displaystyle\ell_{\mathcal{D}}(k^{*}_{\ell}\circ
f)\leq\min_{c:\mathcal{X}\rightarrow\mathbb{R}}\ell_{\mathcal{D}}(c).$ (3)

Define the function $k^{*}_{\ell}:[0,1]\rightarrow\mathbb{R}$ which minimizes
expected loss under the Bernoulli distribution:

$\displaystyle
k_{\ell}^{*}(p)=\operatorname*{arg\,min}_{t\in\mathbb{R}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathrm{Ber(p)}}[\ell(\mathbf{y},t)]=\operatorname*{arg\,min}_{t\in\mathbb{R}}p\ell(1,t)+(1-p)\ell(0,t).$
(4)

If there are multiple minima we break ties arbitrarily. Conditioned on
$\mathbf{x}=x$, $\mathbf{y}\sim\mathrm{Ber(f^{*}(x))}$, so
$k_{\ell}^{*}(f^{*}(x))\in\mathbb{R}$ is the value that minimizes the expected
loss. Hence for every $x\in\mathcal{X}$,

$\operatorname*{\mathbf{E}}_{\mathcal{D}|\mathbf{x}=x}[\ell(\mathbf{y},k_{\ell}^{*}(f^{*}(x))]\leq\operatorname*{\mathbf{E}}_{\mathcal{D}|\mathbf{x}=x}[\ell(\mathbf{y},c(x))].$

Equation (3) follows by averaging over all values of $x$. ∎

Note that the function $k^{*}_{\ell}$ depends on $\ell$ but is independent of
the distribution $\mathcal{D}$. For instance, for the $\ell_{1}$ loss,
$\ell_{1}(y,t)=|y-t|$, we have $k_{\ell_{1}}^{*}(p)=\mathbbm{1}(p\geq 1/2)$.
For the $\ell_{2}$ loss $\ell_{2}(y,t)=(y-t)^{2}$, we have
$k_{\ell_{2}}^{*}(p)=p$. While Definition 4.1 does not place any restrictions
on the post-processing function $k$, in our upper bounds, we will choose $k$
which is very close to the function $k^{*}$ above. Our upper bounds will be
efficient for (convex) functions $\ell$ such that a good approximation to
$k^{*}$ can be be approximated efficiently. Our lower bounds will hold for
arbitrary $k$.

Finally, a natural family of predictors arising from partitions plays a key
role in our results.

######  Definition 4.3.

Given a partition $\mathcal{S}$ of $\mathcal{X}$ of size $m$, let
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[\mathbf{y}]=p_{i}\in[0,1]$ for
$i\in[m]$. The canonical predictor for $\mathcal{S}$ is
$f^{\mathcal{S}}(x)=p_{i}$ for all $x\in S_{i}$.

The canonical predictor simply predicts the expected label in each state of
the partition. Since $f^{\mathcal{S}}$ is constant within each state of the
partition, it can be viewed as a function
$f^{\mathcal{S}}:\mathcal{S}\rightarrow\mathbb{R}$. This view will be useful
in our results.

#### Omnipredictors for general $\mathcal{Y}$.

Consider the setting where we are given a distribution $\mathcal{D}$ on
$\mathcal{X}\times\mathcal{Y}$ for $\mathcal{Y}\subseteq\mathbb{R}$, hence the
labels can take on real values. We are primarily interested in the real-valued
setting of $\mathcal{Y}=[0,1]$, and the multi-class setting where
$\mathcal{Y}=[l]$.

Given a state $S_{i}$ in a partition $\mathcal{S}$, let
$P_{i}\in\mathcal{P}(\mathcal{Y})$ denote the distribution of $\mathbf{y}$
under $\mathcal{D}_{i}$. The canonical predictor
$f^{\mathcal{S}}:\mathcal{X}\rightarrow\mathcal{P}(\mathcal{Y})$ is given by
$f^{\mathcal{S}}(x)=P_{i}$ for all $x\in S_{i}$.

We now define the notion of an omnipredictor. The main difference from the
binary case is that the predictor now predicts a distribution in
$\mathcal{P}(\mathcal{Y})$, so the post-processing function $k$ maps
distributions to real values.

######  Definition 4.4.

Let $\mathcal{C}$ be family of functions on $\mathcal{X}$, and let
$\mathcal{L}$ be a family of loss functions
$\ell:\mathcal{Y}\times\mathbb{R}\rightarrow\mathbb{R}$. The predictor
$f:\mathcal{X}\rightarrow\mathcal{P}(\mathcal{Y})$ is an
$(\mathcal{L},\mathcal{C},\delta)$-omnipredictor if for every
$\ell\in\mathcal{L}$ there exists a function
$k:\mathcal{P}(\mathcal{Y})\rightarrow\mathbb{R}$ so that

$\ell_{\mathcal{D}}(k\circ
f)\leq\min_{c\in\mathcal{C}}\ell_{\mathcal{D}}(c)+\delta.$

##  5 Multicalibration

In this section, we present our definitions of multicalibration. We first
consider the case of binary labels, and then extend it to the multi-class and
real-valued settings. To streamline the presentation, routine proofs are
deferred to Appendix C.1. Given real-valued random variables
$\mathbf{z}_{1},\mathbf{z}_{2}$ from a joint distribution $\mathcal{D}$, we
define

$\displaystyle\operatorname*{{\bf{Cov}}}_{\mathcal{D}}[\mathbf{z}_{1},\mathbf{z}_{2}]$
$\displaystyle=\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}_{1}\mathbf{z}_{2}]-\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}_{1}]\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}_{2}]=\operatorname*{\mathbf{E}}_{\mathcal{D}}\left[\mathbf{z}_{1}(\mathbf{z}_{2}-\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}_{2}])\right].$

We will use the fact that covariance is bilinear. The following identity will
be useful for Boolean $\mathbf{y}$.

######  Corollary 5.1.

For random variables $(\mathbf{z},\mathbf{y})\sim\mathcal{D}$ where
$\mathbf{y}\in\\{0,1\\}$,

$\displaystyle\operatorname*{{\bf{Cov}}}_{\mathcal{D}}[\mathbf{z},\mathbf{y}]=\Pr_{\mathcal{D}}[\mathbf{y}=1]\left(\operatorname*{\mathbf{E}}_{\mathcal{D}|\mathbf{y}=1}[\mathbf{z}]-\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}]\right)=\Pr_{\mathcal{D}}[\mathbf{y}=0]\left(\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}]-\operatorname*{\mathbf{E}}_{\mathcal{D}|\mathbf{y}=0}[\mathbf{z}]\right).$
(5)

###  5.1 Multicalibration via covariance

In this section, we define multicalibration for the binary labels setting
where $\mathcal{Y}=\\{0,1\\}$. We build on a recent line of work [15, 16, 19,
13]. A detailed discussion of how our definitions compare to previous
definitions is presented in Appendix A. The following definition is a
generalization of the notion of $\alpha$-multicalibration to real-valued $c$,
and in the setting of partitions.

######  Definition 5.2.

Let $\mathcal{D}$ be a distribution on $\mathcal{X}\times\\{0,1\\}$. The
partition $\mathcal{S}$ of $\mathcal{X}$ is $\alpha$-multicalibrated for
$\mathcal{C},\mathcal{D}$ if for every $i\in[m]$ and $c\in\mathcal{C}$, the
conditional distribution $\mathcal{D}_{i}=\mathcal{D}|\mathbf{x}\in S_{i}$
satisfies

$\displaystyle\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbf{y}]\Bigr{\rvert}\leq\alpha.$
(6)

A consequence of this definition is that for each $\mathcal{D}_{i}$,
conditioning on $\mathbf{y}$ does not change the expectation of
$c(\mathbf{x})$ by much. Formally, by Equation (5), for $i\in[m]$ and
$b\in\\{0,1\\}$,

$\displaystyle\Pr_{\mathcal{D}_{i}}[\mathbf{y}=b]\left|\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|\mathbf{y}=b}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]\right|\leq\alpha.$
(7)

Definition 5.2 requires a bound on the covariance for every distribution
$\mathcal{D}_{i}$. This might be hard to achieve if $\mathcal{D}(S_{i})$ is
tiny, and hence we hardly see samples from $\mathcal{D}_{i}$ when sampling
from $\mathcal{D}$. This motivated a relaxed definition called
$(\alpha,\beta)$-multicalibration in [15, 13]. We propose a different
definition for which it is also easy to achieve sample efficiency. Rather than
requiring the covariance be small for every $i$, we only require it to be
small on average. Let $\mathbf{i}\sim\mathcal{D}$ denote sampling (the index
of) a set from the partition $\mathcal{S}$ according to $\mathcal{D}$ so that
$\Pr[\mathbf{i}=i]=\mathcal{D}(S_{i})$.

######  Definition 5.3.

The partition $\mathcal{S}$ of $\mathcal{X}$ is $\alpha$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$ if for every $c\in\mathcal{C}$,

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{\mathbf{i}}}[c(\mathbf{x}),\mathbf{y}]\Bigr{\rvert}\leq\alpha.$
(8)

The next lemma shows that approximate multicalibration implies closeness to
(strict) multicalibration under the distribution $\mathcal{D}$. The proof is
by applying Markov’s inequality to Definition 5.3.

######  Lemma 5.4.

If $\mathcal{S}$ is $\alpha$-approximately multicalibrated for
$\mathcal{C},\mathcal{D}$, then for every $c\in\mathcal{C}$ and
$\beta\in[0,1]$

$\displaystyle\Pr_{\mathbf{i}\sim\mathcal{D}}\left[\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{\mathbf{i}}}[c(\mathbf{x}),\mathbf{y}\Bigr{\rvert}\geq\frac{\alpha}{\beta}\right]\leq\beta.$
(9)

This lemma shows that being $\alpha\beta$-approximately multicalibrated is
closely related to the notion of $(\alpha,\beta)$-multicalibration in [15,
13], which roughly says that the $\alpha$-multicalibration condition holds for
all but a $\beta$ fraction of the space $\mathcal{X}$. Conversely, one can
show that $(\alpha,\beta)$-multicalibration gives
$(\alpha+\beta\left\lVert\mathcal{C}\right\rVert_{\infty})$-approximate
multicalibration. We find the single parameter notion of $\alpha$-approximate
multicalibration more elegant. It is also easy to achieve sample efficiency,
since as the next lemma shows, it only requires strong conditional guarantees
for large states.

######  Lemma 5.5.

Let the partition $\mathcal{S}$ be such that for all $i\in[m]$ where

$\displaystyle\mathcal{D}(S_{i})\geq\frac{\alpha}{2m\left\lVert\mathcal{C}\right\rVert_{\infty}}$
(10)

it holds that for every $c\in\mathcal{C}$,

$\displaystyle\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbf{y}]\Bigr{\rvert}\leq\frac{\alpha}{2}.$
(11)

Then $\mathcal{S}$ is $\alpha$-approximately multicalibrated for
$\mathcal{C},\mathcal{D}$.

Approximate multicalibration implies that for an average state in the
partition, conditioning on the label does not change the expectation of $c(x)$
much. The proof follows by plugging Equation (5) in the definition of
approximate multicalibration.

######  Corollary 5.6.

If $\mathcal{S}$ is $\alpha$-approximately multicalibrated for
$\mathcal{C},\mathcal{D}$, then for $c\in\mathcal{C}$ and $b\in\\{0,1\\}$,

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Pr_{\mathcal{D}_{i}}[\mathbf{y}=b]\left|\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|\mathbf{y}=b}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]\right|\right]\leq\alpha.$
(12)

#### Extension to the multi-class setting

In the multi-class setting $\mathcal{Y}=[l]$, so that $l=2$ is exactly the
Boolean case considered above. We use $\mathbbm{1}(\mathbf{y}=j)$ to denote
the indicator of the event that the label is $j$. The following definition
generalizes Definition 5.3:

######  Definition 5.7.

Let $\mathcal{D}$ be a distribution on $\mathcal{X}\times[l]$ where $l\geq 2$.
The partition $\mathcal{S}$ of $\mathcal{X}$ is $\alpha$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$ if for every $c\in\mathcal{C}$
and $j\in[l]$, it holds that

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbbm{1}(\mathbf{y}=j)]\Bigr{\rvert}\right]\leq\alpha.$
(13)

#### Extension to the bounded real-valued case.

We now consider the setting where $\mathcal{Y}$ is a bounded interval, by
scaling we may consider $\mathcal{Y}=[0,1]$. For interval
$J=[v,w]\subset\mathcal{Y}$, let $\mathbbm{1}(\mathbf{y}\in J)$ be the
indicator of the event that $\mathbf{y}\in J$.

######  Definition 5.8.

Let $\mathcal{D}$ be a distribution on $\mathcal{X}\times[0,1]$. The partition
$\mathcal{S}$ of $\mathcal{X}$ is $\alpha$-approximately multicalibrated for
$\mathcal{C},\mathcal{D}$ if for every $c\in\mathcal{C}$ and interval
$J\subseteq[0,1]$, it holds that

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbbm{1}(\mathbf{y}\in
J)]\Bigr{\rvert}\right]\leq\alpha.$ (14)

#### Computational efficiency

Given these new definitions, a natural question is about the computational
complexity of computing multicalibrated partitions. Following [15], this task
can be accomplished efficiently given a weak agnostic learner for the class
$\mathcal{C}$. We present a formal statement of this result for the multi-
class setting in Theorem 9.2. The multi-class setting includes the Boolean
labels setting as a special case. For the purposes of omniprediction, we show
in Section 8 that the bounded real-valued setting reduces to the multi-class
setting. We defer these results to Section 9 since we do not consider them to
be the main contribution of this work, several of the ideas used in the
algorithm and its analysis are present in previous work, they are presented
here for completeness.

###  5.2 Some closure properties of multicalibration

In this section, we prove that approximate multicalibration is closed under
two natural operations on the class $\mathcal{C}$ and the distribution
$\mathcal{D}$:

  1. 1.

Linear combinations of $\mathcal{C}$:  We take sparse linear combinations of
the functions $c\in\mathcal{C}$.

  2. 2.

Conditioning $\mathcal{D}$ on a subset:  We condition the distribution
$\mathcal{D}$ on a subset $\mathcal{X}^{\prime}\subseteq\mathcal{X}$ whose
indicator lies in the set $\mathcal{C}$.

Again we prove these for the case $\mathcal{Y}=\\{0,1\\}$, but the extension
to arbitrary $\mathcal{Y}$ is routine.

#### Multi-calibration under linear combinations.

We will typically start with an approximately multicalibrated partition for a
base class of bounded or even Boolean functions, such as decision trees or
coordinate functions. Since our definition allows the functions $c$ to be
real-valued and possibly unbounded, we can consider functions arising from
linear combinations over this base class. The motivation for this comes from
boosting algorithms like AdaBoost or Logistic Regression, where we take a base
class of weak learners, and then construct a strong learner which is a linear
combination of the weak learners [11, 35].

We will denote by $\mathrm{Lin}_{\mathcal{C}}$ the set of all linear functions
over $\mathcal{C}$. We associate the vector $w=(w_{0},w_{1},\ldots)$ with the
function $g_{w}\in\mathrm{Lin}_{\mathcal{C}}$ defined by
$g_{w}(x)=w_{0}+\sum_{j}w_{j}c_{j}(x)$ where $c_{j}\in\mathcal{C}$ and denote
$\|w\|_{1}=\sum_{j\geq 1}w_{j}$ (note we have excluded $w_{0}$). Let

$\mathrm{Lin}_{\mathcal{C}}(W)=\\{g_{w}\in\mathrm{Lin}_{\mathcal{C}}:\|w\|_{1}\leq
W\\}$ (15)

be the set of all $W$-sparse linear combinations. The following simple claim
shows that multicalibration is closed under taking sparse linear combinations.
The parameter $\alpha$ degrades with the sparsity. The proof follows from
linearity of covariance, and is given in Appendix C.1.

######  Lemma 5.9.

For any $W>0$, if $\mathcal{S}$ is $\alpha$-approximately multicalibrated for
$\mathcal{C},\mathcal{D}$, then it is $\alpha W$-approximately multicalibrated
for $\mathrm{Lin}_{\mathcal{C}}(W),\mathcal{D}$.

#### Multi-calibration for sub-populations.

Let $T\subseteq\mathcal{X}$ be a sub-population such that its indicator
function belongs to $\mathcal{C}$. Let $\mathcal{D}^{\prime}$ denote the
distribution $\mathcal{D}|\mathbf{x}\in T$, where
$\mathcal{D}^{\prime}(x)=\mathcal{D}(x)/\mathcal{D}(T)\;\forall x\in T$. Let
$\mathcal{S}^{\prime}=\\{S_{i}\cap T\\}$ be the partition of $T$ induced by
$\mathcal{S}$. We will use $\mathcal{D}^{\prime}_{i}$ for the distribution
$\mathcal{D}^{\prime}|\mathbf{x}\in S^{\prime}_{i}$ (which is the same as
$\mathcal{D}|\mathbf{x}\in S^{\prime}_{i}$ since $S^{\prime}_{i}\subseteq T$),
and will denote
$p^{\prime}_{i}=\operatorname*{\mathbf{E}}_{\mathcal{D}^{\prime}_{i}}[\mathbf{y}]$.
Let $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ denote the subset of functions
from $\mathcal{C}$ that are supported on $T$ (functions that are 0 outside of
$T$). Note that $\mathcal{C}^{\prime}$ is nonempty, since the indicator of $T$
lies in it. The proof of the following result for the sub-population $T$ in
Appendix C.2.

######  Theorem 5.10.

If $\mathcal{S}$ is $\alpha$-approximately multicalibrated for
$\mathcal{C},\mathcal{D}$, then $\mathcal{S}^{\prime}$ is
$\alpha(1+\left\lVert\mathcal{C}^{\prime}\right\rVert_{\infty})/\mathcal{D}(\mathcal{X}^{\prime})$-approximately
multicalibrated for $\mathcal{C}^{\prime},\mathcal{D}^{\prime}$.

##  6 Omnipredictors for convex loss minimization

In this section we consider the setting of binary labels where
$\mathcal{Y}=\\{0,1\\}$.

###  6.1 Post-processing for nice loss functions

Given an $(B,\epsilon)$-nice loss function, there is a natural post-processing
of the canonical predictor $f^{\mathcal{S}}$ that we will analyze. Rather than
choose the value $k^{*}(p)\in\mathbb{R}$ which minimizes expected loss under
$\mathrm{Ber(p)}$, we restrict ourselves to the best value from $I_{\ell}$.
This restriction only costs us $\epsilon$ by the $\epsilon$-optimality
property.

######  Definition 6.1.

Given a nice loss function $\ell$, define the function
$k_{\ell}:[0,1]\rightarrow I_{\ell}$ by

$\displaystyle k_{\ell}(p)=\operatorname*{arg\,min}_{t\in
I_{\ell}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathrm{Ber(p)}}\ell(\mathbf{y},t).$
(16)

Given a partition $\mathcal{S}$ of $\mathcal{X}$, define the $\ell$-optimized
hypothesis $h^{\mathcal{S}}_{\ell}:\mathcal{X}\rightarrow I_{\ell}$ as

$h^{\mathcal{S}}_{\ell}(x)=k_{\ell}\circ f^{\mathcal{S}}(x).$

Since $\ell$ is convex as a function of $t$, so is

$\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathrm{Ber(p)}}\ell(\mathbf{y},t)=p\ell(0,t)+(1-p)\ell(1,t).$

Hence computing $k_{\ell}$ is a one-dimensional convex minimization problem, a
classical problem with several known algorithms [5]. Being able to compute an
$\epsilon^{\prime}$-approximate solution suffices for us, we can absorb the
$\epsilon^{\prime}$ term into the error $\epsilon$, and pretend that $\ell$ is
$(B,\epsilon+\epsilon^{\prime})$-nice instead.

We can view the hypothesis $h^{\mathcal{S}}_{\ell}$ as a function mapping
$\mathcal{S}$ to $I_{\ell}$, since it is constant on each
$S_{i}\in\mathcal{S}$, and its range is $I_{\ell}$. A simple consequence of
the definition is that it is the best function in this class for minimizing
expected loss.

######  Corollary 6.2.

For all functions $h:\mathcal{S}\rightarrow I_{\ell}$,
$\ell_{\mathcal{D}}(h^{\mathcal{S}}_{\ell})\leq\ell_{\mathcal{D}}(h)$.

###### Proof.

We sample $\mathbf{i}\sim\mathcal{D}$ and then
$\mathbf{x},\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}$ and show that the
inequality holds conditioned on every choice of $\mathbf{i}=i$. Since
$\mathbf{y}\sim D_{i}$ is distributed as $\mathrm{Ber(p_{i})}$,

$\ell_{\mathcal{D}_{i}}(h^{\mathcal{S}}_{\ell})=\operatorname*{\mathbf{E}}_{\mathrm{Ber(p_{i})}}[\ell(\mathbf{y},k_{\ell}(p_{i}))]\leq\operatorname*{\mathbf{E}}_{\mathrm{Ber(p_{i})}}[\ell(\mathbf{y},h(S_{i}))]=\ell_{\mathcal{D}_{i}}(h)$

where the inequality is by Definition 6.1. ∎

###  6.2 Loss minimization through Multicalibration

Our main result in this section is the following theorem.

######  Theorem 6.3.

Let $\mathcal{D}$ be a distribution on $\mathcal{X}\times\\{0,1\\}$,
$\mathcal{C}$ be a family of real-valued functions on $\mathcal{X}$ and
$\mathcal{L}(B,\epsilon)$ be the family of all $(B,\epsilon)$-nice loss
functions. If the partition $\mathcal{S}$ is $\alpha$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$, then the canonical predictor
$f^{\mathcal{S}}$ is an $(\mathcal{L},\mathcal{C},2\alpha
B+\epsilon)$-omnipredictor.

The following lemma is the key ingredient in our result. Informally it says
that $c$ has limited distinguishing power within each state of the partition.
Specifically, that $c(x)$ is not much better at minimizing a loss than the
function obtained by taking its conditional expectation within each state of
the partition $\mathcal{S}$.

######  Lemma 6.4.

Given $\ell\in\mathcal{L}$ and $c\in\mathcal{C}$, define the predictor
$\widehat{c}:\mathcal{S}\rightarrow I_{\ell}$ by

$\widehat{c}(x)=\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(x)],I_{\ell}\right)\
\text{for}\ x\in S_{i}.$

We have

$\displaystyle\ell_{\mathcal{D}}(\widehat{c})\leq\ell_{\mathcal{D}}(c)+2\alpha
B+\epsilon.$ (17)

###### Proof.

By the convexity of $\ell$ we have

$\displaystyle\ell_{\mathcal{D}}(c)=\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},c(\mathbf{x}))]=\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{\mathbf{i}}|\mathbf{y}}[\ell(\mathbf{y},c(\mathbf{x})]\geq\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\left[\ell\left(\mathbf{y},\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{\mathbf{i}}|\mathbf{y}}[c(\mathbf{x})]\right)\right].$
(18)

By Lemma 3.2,

$\ell\left(\mathbf{y},\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})]\right)\geq\ell\left(\mathbf{y},\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})],I_{\ell}\right)\right)-\epsilon.$

Plugging this into Equation (18), we get

$\displaystyle\ell_{\mathcal{D}}(c)\geq\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\left[\ell\left(\mathbf{y},\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})],I_{\ell}\right)\right)\right]-\epsilon.$
(19)

From the definition of $\widehat{c}$,

$\displaystyle\ell_{\mathcal{D}}(\widehat{c})=\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},\widehat{c}(\mathbf{x}))]=\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\left[\ell\left(\mathbf{y},\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})],I_{\ell}\right)\right)\right].$
(20)

Subtracting Equation (19) from Equation (20) we get

$\displaystyle\ell_{\mathcal{D}}(\widehat{c})-\ell_{\mathcal{D}}(c)\leq$
$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\left[\ell\left(\mathbf{y},\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})],I_{\ell}\right)\right)-\ell\left(\mathbf{y},\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})],I_{\ell}\right)\right)\right]+\epsilon.$
(21)

Since $\ell$ is $B$-Lipschitz on $I_{\ell}$ and
$\operatorname{clip}(t,I_{\ell})$ is $1$-Lipschitz as a function of $t$,

$\displaystyle\ell\left(\mathbf{y},\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})],I_{\ell}\right)\right)$
$\displaystyle-\ell\left(\mathbf{y},\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})],I_{\ell}\right)\right)$
$\displaystyle\leq
B\Bigl{\lvert}\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})],I_{\ell}\right)-\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})],I_{\ell}\right)\Bigr{\rvert}$
$\displaystyle\leq
B\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})]\Bigr{\rvert}.$
(22)

Plugging this into Equation (21) gives

$\displaystyle\ell_{\mathcal{D}}(\widehat{c})-\ell_{\mathcal{D}}(c)-\epsilon$
$\displaystyle\leq
B\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\left|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})]\right|$
(23)
$\displaystyle=B\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\sum_{b\in\\{0,1\\}}\Pr_{\mathcal{D}_{\mathbf{i}}}[\mathbf{y}=b]\left|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})]\right|\right]$
$\displaystyle=B\sum_{b\in\\{0,1\\}}\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Pr_{\mathcal{D}_{\mathbf{i}}}[\mathbf{y}=b]\left|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})]\right|\right]$
$\displaystyle\leq B\sum_{b\in\\{0,1\\}}\alpha=2\alpha B,$

where the last inequality follows by the multicalibration condition (Equation
(7)). ∎

As a consequence we can now prove Theorem 6.3.

###### Proof of Theorem 6.3.

Let $h^{\mathcal{S}}_{\ell}=k_{\ell}\circ f^{\mathcal{S}}$ be the
$\ell$-optimized hypothesis. It suffices to show that for any
$c\in\mathcal{C}$

$\displaystyle\ell_{\mathcal{D}}(h^{\mathcal{S}}_{\ell})\leq\ell_{\mathcal{D}}(c)+2\alpha
B+\epsilon.$ (24)

For any $c\in\mathcal{C}$, we have

$\ell_{\mathcal{D}}(h^{\mathcal{S}}_{\ell})\leq\ell_{\mathcal{D}}(\widehat{c})\leq\ell_{\mathcal{D}}(c)+2\alpha
B+\epsilon$

where the first inequality is by Corollary 6.2, which applies since
$\widehat{c}$ is a function mapping $\mathcal{S}$ to $I_{\ell}$. The second is
by Lemma 6.4. ∎

Consider the family $\mathrm{Lin}_{\mathcal{C}}(W)$ of linear combinations
over $\mathcal{C}$ of weight at most $W$. By Lemma 5.9, $\mathcal{S}$ is
$\alpha W$-approximately multicalibrated for $\mathrm{Lin}_{\mathcal{C}}(W)$.
Applying Theorem 6.3, we derive the following corollary.

######  Corollary 6.5.

Let $\mathcal{D}$ be a distribution on $\mathcal{X}\times\\{0,1\\}$,
$\mathrm{Lin}_{\mathcal{C}}(W)$ be linear functions in $\mathcal{C}$ of with
$\left\lVert w\right\rVert_{1}\leq W$ (see eq. 15) and
$\mathcal{L}=\mathcal{L}(B,\epsilon)$ be the family of all $(B,\epsilon)$-nice
loss functions. If the partition $\mathcal{S}$ is $\alpha$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$, then $f^{\mathcal{S}}$ is an
$(\mathcal{L},\mathrm{Lin}_{\mathcal{C}}(W),2\alpha
BW+\epsilon)$-omnipredictor.

To interpret this, assume we have an $(B,\epsilon)$-nice loss function and we
wish to have a predictor that is within $2\epsilon$ of any function in
$\mathrm{Lin}_{\mathcal{C}}(W)$. Corollary 6.5 says that it suffices to have
an $\alpha$-approximately multicalibrated partition where
$\alpha=\epsilon/2BW$. Note that algorithms for computing such partitions have
running time which is polynomial in $1/\alpha$, which translates to running
time polynomial in $BW/\epsilon$.

We derive a corollary for sub-populations follows from Theorem 6.3 and 5.10.
For two families of functions
$\mathcal{T},\mathcal{P}:\mathcal{X}\rightarrow\mathbb{R}$, we define their
product as

$\mathcal{T}\times\mathcal{P}=\\{c:c(x)=T(x)P(x),T\in\mathcal{T},P\in\mathcal{P}\\}.$

Note that in the case when $T\in\mathcal{T}$ is binary-valued,
$\mathcal{T}\times\mathcal{P}$ contains the restriction of every
$P\in\mathcal{P}$ to the support of $T$.

######  Corollary 6.6.

Let $\mathcal{D}$ be a distribution on $\mathcal{X}\times\\{0,1\\}$,
$\mathcal{T}$ be a family of binary-valued functions on $\mathcal{X}$,
$\mathcal{P}$ be a family of real-valued functions and
$\mathcal{L}(B,\epsilon)$ be the family of all $(B,\epsilon)$-nice loss
functions. Let the partition $\mathcal{S}$ be $\alpha$-approximately
multicalibrated for $\mathcal{T}\times\mathcal{P},\mathcal{D}$. For
$T\in\mathcal{T}$, let
$\alpha^{\prime}=\alpha(1+\left\lVert\mathcal{P}\right\rVert_{\infty})/\mathcal{D}(T)$.
Then the canonical predictor $f^{\mathcal{S}}$ is an
$(\mathcal{L},\mathcal{P},2\alpha^{\prime}B+\epsilon)$-omnipredictor for the
sub-population $T$.

To informally instantiate this for a simple case, let
$\mathcal{T},\mathcal{P}$ be the class of decision trees of depth $d_{1}$ and
$d_{2}$ respectively. Let the partition $\mathcal{S}$ be multicalibrated with
respect to decision trees of depth $d_{1}+d_{2}$. If we now consider any sub-
population $T$ identified by decision trees of depth $d_{1}$, then the above
result implies that the canonical predictor $f^{\mathcal{S}}$ is an
omnipredictor for $T$, when compared against the class of decision trees of
depth $d_{2}$ evaluated on $T$.

###  6.3 Limits for omnipredictors from multicalibration

Corollary 6.5 shows that multicalibration for $\mathcal{C}$ gives
omnipredictors for $\mathrm{Lin}_{\mathcal{C}}$. It is natural to ask whether
we can get omnipredictors for a richer class of functions using
multicalibration for $\mathcal{C}$. A natural candidate would be thresholds of
functions in $\mathcal{C}$:

$\mathrm{Thr_{\mathcal{C}}}=\\{\mathbbm{1}(c(x)\geq
v):c\in\mathcal{C},v\in\mathbb{R}\\}.$

Another natural extension would be to relax the convexity condition for loss
functions in $\mathcal{L}$. We present a simple counterexample which shows
that multicalibration for $\mathcal{C}$ is insufficient to give omnipredictors
for both these classes. This shows that a significant strengthening of the
bound from Corollary 6.5 might not be possible.

######  Lemma 6.7.

There exists a distribution $\mathcal{D}$, a set
$\mathcal{C}:\mathcal{X}\rightarrow\mathbb{R}$ of functions, and a
$0$-multicalibrated partition $\mathcal{S}$ for $\mathcal{C},\mathcal{D}$ such
that for any $\delta<1/4$,

  * •

$f^{\mathcal{S}}$ is not an
$(\mathcal{L},\mathrm{Thr_{\mathcal{C}}},\delta)$-omnipredictor for any
$\mathcal{L}$ containing the $\ell_{1}$ loss function.

  * •

$f^{\mathcal{S}}$ is not an $(\mathcal{L},\mathcal{C},\delta)$-omnipredictor
for any $\mathcal{L}$ containing the (non-convex) loss function
$\ell(y,t)=|y-\mathbbm{1}(t\geq 0)|$.

###### Proof.

Let $\mathcal{D}$ be the distribution on $\\{0,1\\}^{3}\times\\{0,1\\}$ where
$\mathbf{x}\sim\\{0,1\\}^{3}$ is sampled uniformly and
$\mathbf{y}=\mathbbm{1}(\sum_{i=1}^{3}\mathbf{x}_{i}\equiv 0\bmod 2)$ is the
negated Parity function. Let $\mathcal{C}=\\{\sum_{i}w_{i}x_{i}-w_{0}\\}$ be
all affine functions. We claim the trivial partition
$\mathcal{S}=\\{\\{0,1\\}^{3}\\}$ is $0$-multicalibrated for
$\mathcal{C},\mathcal{D}$. This is because every $x_{i}$ is independent of
$\mathbf{y}$, so their covariance is $0$. By linearity of expectation, the
same is true for all functions in $\mathcal{C}$. Thus $f^{\mathcal{S}}(x)=1/2$
for every $x\in\\{0,1\\}^{3}$.

Now consider the $\ell_{1}$ loss. A simple calculation shows that for every
$k:\\{0,1\\}\rightarrow\mathbb{R}$, $\bar{\ell}_{1}(k\circ
f^{\mathcal{S}},\mathcal{D})\geq 1/2$. In contrast
$h(x)=\mathbbm{1}(x_{1}+x_{2}+x_{3}\geq 1.5)\in\mathrm{Thr_{\mathcal{C}}}$
gives $\bar{\ell}_{1}(h,\mathcal{D})=1/4$, since it gets the two middle layers
correct. This proves part (1).

To deduce part (2), let $\ell(y,t)=|y-\mathbbm{1}(t\geq 0)|$ and
$g(x)=x_{1}+x_{2}+x_{3}-1.5\in\mathcal{C}$. Note that

$1/4=\bar{\ell}_{1}(h,\mathcal{D})=\operatorname*{\mathbf{E}}_{\mathcal{D}}[|h(\mathbf{x})-\mathbf{y}|]=\operatorname*{\mathbf{E}}_{\mathcal{D}}[|\mathbbm{1}(g(\mathbf{x})\geq
0)-\mathbf{y}|]=\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},g(\mathbf{x}))]=\bar{\ell}(g,\mathcal{D}).$

In contrast, for any $k:[0,1]\rightarrow\mathbb{R}$, it follows that
$\bar{\ell}(k\circ f^{\mathcal{S}},\mathcal{D})\geq 1/2$. ∎

In part (2), the loss function $|y-\mathbbm{1}(t\geq 0)|$ is not Lipshcitz or
differentiable in $t$. We can ensure both these conditions by replacing it
with the sigmoid function, which still preserves the correlation with parity,
at the cost of some reduction in $\delta$ for which the bound holds [17].

##  7 Agnostic boosting via multicalibration

In this section we apply our results to the setting of agnostic learning,
where the labels are Boolean, and the relevant loss is the classification
error aka $0$-$1$ loss.

######  Definition 7.1.

Let $\mathcal{H}:\mathcal{X}\rightarrow\\{0,1\\}$ be a family of classifiers.
Given a distribution $\mathcal{D}$ on $\mathcal{X}\times\\{0,1\\}$, for
$h\in\mathcal{H}$ let its classification error be
$\mathrm{err}(h)=\Pr_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[h(\mathbf{x})\neq\mathbf{y}]$
and $\mathrm{OPT}(\mathcal{H})=\min_{h\in\mathcal{H}}\mathrm{err}(h)$. An
algorithm is an agnostic learner for a class $\mathcal{H}$ if it produces a
hypothesis $f$ such that
$\mathrm{err}(f)\leq\mathrm{OPT}(\mathcal{H})+\epsilon$.

The $\ell_{1}$ loss defined by $\ell_{1}(y,t)=|y-t|$ becomes the
classification error for Boolean functions, since for any
$h:\mathcal{X}\rightarrow\\{0,1\\}$,

$\mathrm{err}(h)=\Pr_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[y\neq
h(\mathbf{x})]=\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[|\mathbf{y}-h(\mathbf{x})|]=\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[\ell_{1}(y,h(\mathbf{x}))].$

######  Definition 7.2.

A class $\mathcal{H}$ is $(\epsilon,W)$-approximated by the class
$\mathcal{C}$ if for every $h\in\mathcal{H}$ and $\epsilon>0$, there exists
$g_{w}\in\mathrm{Lin}_{\mathcal{C}}(W)$ such that

$\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}\left[|g_{w}(x)-h(\mathbf{x})|\right]\leq\epsilon.$

For $p\in[0,1]$ the function

$\\\ E_{\mathbf{y}\sim\mathrm{Ber(p)}}\ell_{1}(\mathbf{y},t)=p|1-t|+(1-p)|t|$

is minimized in $t$ by the function $k_{\ell_{1}}(p)=\mathbbm{1}(p\geq 1/2)$.
Hence the $\ell_{1}$-optimized hypothesis $h^{\mathcal{S}}_{\ell_{1}}$ outputs
$1$ for $x\in S_{i}$ where $p_{i}\geq 1/2$ and $0$ elsewhere.

We are now ready to state our main result about agnostic learning via multi-
calibration. We show that multicalibration gives a predictor that is
competitive with the best predictor in a possibly much more powerful class
$\mathcal{H}$. Since multicalibration can be achieved using a weak learner for
$\mathcal{C}$, this implies a form of agnostic boosting.

######  Theorem 7.3.

Let $\mathcal{H}$ be a class that is $(\epsilon/2,W)$-approximated by
$\mathcal{C}$. If the partition $\mathcal{S}$ is $\epsilon/2W$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$, then
$\mathrm{err}(h^{\mathcal{S}}_{\ell_{1}})\leq\mathrm{OPT}(\mathcal{H})+\epsilon$.
Hence an algorithm that outputs such a partition gives an agnostic learner for
$\mathcal{H}$.

###### Proof.

Let $h=\arg\min_{h\in\mathcal{H}}\mathrm{err}(h)$ so that
$\mathrm{err}(h)=\mathrm{OPT}(\mathcal{H})$. There exists
$g_{w}\in\mathrm{Lin}_{\mathcal{C}}(W)$ such that

$\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[|g_{w}(x)-h(\mathbf{x})|]\leq\epsilon/2.$

Hence by the triangle inequality,

$\displaystyle\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[\ell_{1}(\mathbf{y},g_{w}(\mathbf{x})]$
$\displaystyle\leq\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[|\mathbf{y}-h(\mathbf{x})|]+\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[|g_{w}(\mathbf{x})-h(\mathbf{x})|]\leq\mathrm{err}(h)+\epsilon/2.$

The $\ell_{1}$ loss function is $1$-Lipschitz, and $(\mathbb{R},1,0)$-nice. By
Corollary 6.5 we conclude that since $\mathcal{S}$ is $\epsilon/2W$
approximately multicalibrated for $\mathcal{C},\mathcal{D}$,

$\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[\ell(\mathbf{y},h^{\mathcal{S}}_{\ell_{1}}(\mathbf{x}))]\leq\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}\left[\ell(\mathbf{y},g_{w}(\mathbf{x}))\right]+\epsilon/2\leq\mathrm{err}(h)+\epsilon.$

But since $h^{\mathcal{S}}_{\ell_{1}}$ is a Boolean function, we have

$\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[\ell(\mathbf{y},h^{\mathcal{S}}_{\ell_{1}}(\mathbf{x}))]=\mathrm{err}(h^{\mathcal{S}}_{\ell_{1}}).$

Hence $\mathrm{err}(h^{\mathcal{S}}_{\ell_{1}})\leq\mathrm{err}(h)+\epsilon$,
which proves our claim. ∎

Some comments on the connection of Theorem 7.3 to other work:

  * •

The agnostic learnability of a class $\mathcal{H}$ that is $\ell_{1}$
approximated by $\mathcal{C}$ was first proved by [22] using linear
programming; see [10, 21] for a boosting based approach. Our result reproves
this through multicalibration and the algorithm of [29].

  * •

Agnostic boosting was introduced in the work of [3]. The agnostic boosting
abilities of the [29] algorithm are analyzed in [25], however they bound the
error by $\mathrm{OPT}(\mathcal{C})$. Our work shows that this algorithm is
even more powerful; one can compare it to $\mathrm{OPT}(\mathcal{H})$.

  * •

Theorem 7.3 gives an upper bound, but it is not a tight characterization of
the error of the hypothesis $h^{\mathcal{S}}_{\ell_{1}}$. Indeed, in
subsection 7.1, we give an example showing that the error of the hypothesis
can be much smaller than $\mathrm{OPT}(\mathrm{Lin}_{\mathcal{C}})$.

  * •

For the purposes of agnostic boosting, it is often desirable to keep the same
marginal distribution over $\mathcal{X}$. Following Kalai-Kanade [21] and
Feldman [10], one can reduce multicalibration to weak agnostic learning over a
distribution with the same marginal on $\mathcal{X}$, by adding noise to the
labels.

###  7.1 Multicalibration can be better than $\mathrm{OPT}$

In the literature of agnostic boosting (specifically [21]), a $\gamma$-weak
agnostic learner [21] for ${\cal H}$ is defined as an algorithm that outputs
$c\in{\cal C}$ such that,

$\displaystyle\operatorname*{{\bf{cor}}}_{\mathcal{D}}(c)\geq\gamma\sup_{h\in{\cal
H}}\operatorname*{{\bf{cor}}}_{\mathcal{D}}(h),$ (25)

for $\gamma>0$ in terms of correlation
$\operatorname*{{\bf{cor}}}_{\mathcal{D}}(h)\in[-1,1]$ defined as,

$\operatorname*{{\bf{cor}}}_{\mathcal{D}}(h):=\Pr_{\mathcal{D}}[h(x)=y]-\Pr_{\mathcal{D}}[h(x)\neq
y].$

It is shown that a $\gamma$ weak agnostic learner can be used to achieve error
within $\epsilon$ of $\mathrm{OPT}(\mathcal{H})$ using time and samples
$\operatorname{poly}(1/\gamma,1/\epsilon)$. [21] do not explicitly limit what
class $\mathcal{H}$ can be relative to $\mathcal{C}$, beyond saying that it
should satisfy condition Equation (25). However it is not difficult to see
that this definition limits agnostic boosting to ${\cal
H}\subseteq\mathrm{Lin}_{\mathcal{C}}$, i.e., linear combinations as defined
in Equation (15). Therefore, agnostic boosting (as in [25, 21]) essentially
learns linear combinations of ${\cal C}$, while we have shown that multi-
calibrated predictors also satisfy this goal. Indeed, our proof shows that the
marginal distribution on $\mathcal{X}$ can be considered fixed, we just
require Equation (25) to hold for all $h\in\mathcal{H}$ and marginal
distributions on the label $\mathbf{y}$.

######  Lemma 7.4.

For Equation (25) to hold for every $h\in\mathcal{H}$, we must have ${\cal
H}\subseteq\mathrm{Lin}_{\mathcal{C}}$.

###### Proof.

For the purpose of contradiction consider any
$h\notin\mathrm{Lin}_{\mathcal{C}}$. Let $g:\mathcal{X}\rightarrow\mathbb{R}$
be the projection of $h$ onto $\mathrm{Lin}_{\mathcal{C}}$, i.e., that
minimizes $\operatorname*{\mathbf{E}}_{\mathcal{D}}[(g(x)-h(x))^{2}]$. Since
$\mathcal{X}$ and ${\cal C}$ are finite, $g$ is bounded. Thus consider

$f^{*}(x):=\frac{1}{2}+\frac{h(x)-g(x)}{\max_{\mathcal{X}}|h(x)-g(x)|}\in[0,1].$

In particular, for the distribution $\mathcal{D}^{\prime}$ which has the same
marginal over $\mathcal{X}$ but so that
$f^{*}(x)=\operatorname*{\mathbf{E}}_{\mathcal{D}^{\prime}}\mathbf{y}|x]$, it
is not difficult to see that
$\operatorname*{{\bf{cor}}}_{\mathcal{D}^{\prime}}(c)=0$ for all $c\in{\cal
C}$ and yet $\operatorname*{{\bf{cor}}}_{\mathcal{D}^{\prime}}(h)>0$ violating
the definition of a weak learner. ∎

We now show that being approximately multicalibrated is a stronger notion than
$\mathrm{OPT}(\mathrm{Lin}_{\mathcal{C}})$ in that being multi-calibrated with
respect to ${\cal C}$ implies a loss that may be even lower than the best
classifier in $\mathrm{Lin}_{\mathcal{C}}$. This says that the upper bound on
the classification error in terms of
$\mathrm{OPT}(\mathrm{Lin}_{\mathcal{C}})$ given by Theorem 7.3 may not always
be tight.

######  Theorem 7.5.

For any $\epsilon>0$, there exists a distribution $\mathcal{D}$ on
$\\{0,1\\}^{2}\times\\{0,1\\}$ and a set of functions
$\mathcal{C}:\mathcal{X}\rightarrow\\{0,1\\}$ such that for any approximately
multicalibrated partition $\mathcal{S}$, we have
$\mathrm{OPT}(\mathrm{Lin}_{\mathcal{C}})-\mathrm{err}(h^{\mathcal{S}}_{\ell_{1}},\mathcal{D})\geq
1/4-\epsilon/2$.

###### Proof.

Let $\mathcal{X}=\\{0,1\\}^{2},\mathcal{Y}=\\{0,1\\}$, the marginal
distribution over $x\in\mathcal{X}$ uniform, and the conditional distribution
over $\mathcal{Y}$ given by

$\operatorname*{\mathbf{E}}[\mathbf{y}|x]=\begin{cases}0&\text{if }x=(0,0)\\\
\epsilon&\text{if }x=(1,0)\\\ \epsilon&\text{if }x=(1,1)\\\ 1&\text{if
}x=(0,1).\end{cases}$

Let $\mathcal{C}=\\{x_{1},x_{2}\\}$ be the family of two classifiers based on
the two coordinates. It is not hard to see that, for this ${\cal C}$ and for
${\cal H}:=\mathrm{Lin}_{\mathcal{C}}$, which is the most agnostic boosting
can cover, $\mathrm{OPT}(\mathcal{H})=1/4$ is the error of the best classifier
$c(x)=x_{2}$. On the other hand, it is not difficult to see that any multi-
calibrated partition must have separate sets for $\\{(0,1)\\}$ and
$\\{(0,0)\\}$. This implies a smaller 0-1 loss of $\epsilon/2$. ∎

Clearly, by reducing the constant $\epsilon$, the multi-calibrated loss can
approach 0, but we chose not to set it to exactly 0 because standard boosting
could be applied in the noiseless case.

##  8 Omnipredictors in the real valued setting

In this section we will consider two settings:

  1. 1.

The multi-class setting. Here the labels take values in $[l]$. For each
$j\in[l]$, the label $j$ is associated with the loss function $\ell(j,t)$
which is $(B,\epsilon)$-nice. This means that there is an interval $I_{\ell}$
for which the $B$-Lipshcitz and $\epsilon$-optimality property hold for the
functions $\ell(j,t)$ for every $j\in[k]$. The loss functions for different
labels could be very different, in analogy to different false positive and
negative scores for the Boolean case.

  2. 2.

The real-valued setting. Here the labels take values in $[0,1]$. We will
assume that the loss function $\ell(y,t)$ is $B$-Lipschitz in $y$ for all $t$,
and that $\ell(y,t)$ is $(B,\epsilon)$-nice as a function of $t$.101010One can
relax the Lipschitz requirement in the first argument and only require it for
$t\in I$ rather than all $t$. We work with the stronger assumption for
simplicity

We show that for nice loss functions, omniprediction in the real-valued
setting reduces to the multi-class setting. We take $l=\lceil
B/\epsilon\rceil$ and partition $[0,1]$ into $l$ disjoint buckets
$\\{b_{j}\\}_{j=1}^{l}$ of width $\epsilon/B$ each. For $y\in b_{j}$, we use
the loss function $\ell(j/l,t)$ in place of $\ell(y,t)$. This amounts to
discretizing $y$ to $\widehat{y}$ where $|y-\widehat{y}|\leq\epsilon/B$. By
the $B$-Lipschitz property, it follows that for any predictor
$f:\mathcal{X}\rightarrow\mathbb{R}$,

$\displaystyle\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\mathbf{y},f(\mathbf{x}))]-\operatorname*{\mathbf{E}}_{\mathcal{D}}[\ell(\widehat{\mathbf{y}},f(\mathbf{x}))]\Bigr{\rvert}\leq\operatorname*{\mathbf{E}}_{\mathcal{D}}\left[\Bigl{\lvert}\ell(\mathbf{y},f(\mathbf{x})-\ell(\widehat{\mathbf{y}},f(\mathbf{x})\Bigr{\rvert}\right]\leq\epsilon.$
(26)

Since $\widehat{y}$ takes on $l$ discrete values, we have reduced to the
multi-class setting.

Hence we now focus on generalizing our results to the multi-class setting
where $\mathcal{Y}=[l]$ for $l\geq 2$. Recall that the definition of
multicalibration in the multi-class requires that for all $c\in\mathcal{C}$
and $j\in[l]$, we have

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{\mathbf{i}}}[c(x)\mathbbm{1}(\mathbf{y}=j)]\Bigr{\rvert}\right]\leq\alpha.$
(27)

Let $\mathcal{P}(l)$ denote the space of probability distributions on $l$.
Given a partition $\mathcal{S}$, we associate to each state $S_{i}$ a
probability distribution over labels $P_{i}\in\mathcal{P}(l)$. The canonical
predictor $f^{\mathcal{S}}:\mathcal{X}\rightarrow\mathcal{P}(l)$ predicts a in
$\mathcal{P}$ for every $x\in\mathcal{X}$ and is given by

$f^{\mathcal{S}}(x)=P_{i}\ \forall x\in S_{i}.$

In analogy with the corresponding definitions for the binary classification
setting, for every $P\in\mathcal{P}(l)$ we define $k_{\ell}(P)\in I$ to be the
action that minimizes expected loss under $P$:

$\displaystyle k_{\ell}(P)=\arg\min_{t\in
I}\operatorname*{\mathbf{E}}_{\mathbf{j}\sim P}[\ell(\mathbf{j},t)]$

and the $\ell$-optimized hypothesis
$h^{\mathcal{S}}_{\ell}:\mathcal{X}\rightarrow I$ by

$\displaystyle f^{\mathcal{S}}_{\ell}(x)=k_{\ell}(P_{i})\ \forall x\in S_{i}.$

Our main theorem is a direct generalization of Theorem 6.3.

######  Theorem 8.1.

Let $\mathcal{D}$ be a distribution on $\mathcal{X}\times[l]$ and
$\ell:[l]\times\mathbb{R}\rightarrow\mathbb{R}$ be a $(B,\epsilon)$-nice loss
function. If the partition $\mathcal{S}$ is $\alpha$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$, then the canonical predictor
$f^{\mathcal{S}}$ is an $(\mathcal{L},\mathcal{C},k\alpha
B+\epsilon)$-omnipredictor.

The theorem follows from the next Lemma which generalizes Lemma 6.4 to $l\geq
2$. Since the proof follows along similar lines till the last step, we only
describe the difference.

######  Lemma 8.2.

Let $\ell:[l]\times\mathbb{R}\rightarrow\mathbb{R}$ be an $(B,\epsilon)$ nice
function. Given $c\in\mathcal{C}$, if we define the predictor
$\widehat{c}:\mathcal{S}\rightarrow I_{\ell}$ by

$\widehat{c}(x)=\operatorname{clip}\left(\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(x)],I_{\ell}\right)\
\text{for}\ x\in S_{i}.$

then

$\displaystyle\ell_{\mathcal{D}}(\widehat{c})\leq\ell_{\mathcal{D}}(c)+l\alpha
B+\epsilon.$ (28)

###### Proof.

We follow the proof of Lemma 6.4 till Equation (23), this portion does not
assume $\mathbf{y}\in\\{0,1\\}$. At this point we have established that

$\displaystyle\ell_{\mathcal{D}}(\widehat{c})-\ell_{\mathcal{D}}(c)-\epsilon$
$\displaystyle\leq
B\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\left|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})]\right|$
(29)

The following analog of Corollary 5.6 follows from Equation (5) about
covariance with binary random variables. For every $j\in[l]$

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Pr_{\mathcal{D}_{i}}[\mathbf{y}=j]\left|\operatorname*{\mathbf{E}}_{\mathcal{D}_{\mathbf{i}}|\mathbf{y}=j}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathcal{D}_{\mathbf{i}}}[c(\mathbf{x})]\right|\right]=\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\left|\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{\mathbf{i}}}[c(\mathbf{x}),\mathbbm{1}(\mathbf{y}=j)\right|\right]\leq\alpha.$

We use this to bound the RHS of Equation (29) as

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{\mathbf{i}}}\left|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{i}|\mathbf{y}}[c(\mathbf{x})]\right|$
$\displaystyle=\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\sum_{j\in[l]}\Pr_{\mathcal{D}_{\mathbf{i}}}[\mathbf{y}=j]\left|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{\mathbf{i}}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{\mathbf{i}}|\mathbf{y}=j}[c(\mathbf{x})]\right|$
$\displaystyle=\sum_{j\in[l]}\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Pr_{\mathcal{D}_{\mathbf{i}}}[\mathbf{y}=j]\left|\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{\mathbf{i}}}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}_{\mathbf{i}}|\mathbf{y}=j}[c(\mathbf{x})]\right|\right]$
$\displaystyle\leq\sum_{j\in[l]}\alpha=l\alpha.$

Plugging this into the RHS of Equation (29) gives the desired bound. ∎

We now derive the proof of Theorem 8.1. From the definition of
$h^{\mathcal{S}}_{\ell}$ it follows that

$h^{\mathcal{S}}_{\ell}=\operatorname*{arg\,min}_{h:\mathcal{S}\rightarrow
I_{\ell}}\ell_{\mathcal{D}}(h).$

Since $\widehat{c}:\mathcal{S}\rightarrow I_{\ell}$ this implies
$\ell_{\mathcal{D}}(h^{\mathcal{S}}_{\ell})\leq\ell_{\mathcal{D}}(\widehat{c})$.
The claim now follows from Lemma 8.2.

###  8.1 Improved bounds for squared loss

One of the most commonly used losses for the real-valued case is the squared
loss $\ell_{2}(y,t)=(t-y)^{2}$. For this loss, we can show a stronger bound.
Since $\ell_{2}$ is a proper scoring rule, the post-processing function
$k^{*}_{\ell_{2}}$ is just the identity function, hence
$h^{\mathcal{S}}_{\ell_{2}}(x)=f^{\mathcal{S}}(x)=\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}_{i}}[\mathbf{y}]=p_{i}$.

We will show the following guarantee comparing it to any linear function.

######  Theorem 8.3.

Consider the real-valued prediction problem with $y\in[0,1]$, let
$\widehat{y}$ be a discretization of $y$ into $\lceil 1/\epsilon\rceil$
buckets (as in Equation 26). Let $\mathcal{S}$ be $\alpha$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$, and $f^{\mathcal{S}}(x)$ be the
predictor defined above. Let $\ell(\mathbf{y},t)=(t-y)^{2}$ denoted the
$\ell_{2}$ loss. For any function $g_{w}\in\mathrm{Lin}_{\mathcal{C}}$ and
$y\in[0,1]$, we have

$\displaystyle\ell_{\mathcal{D}}(f^{\mathcal{S}})+\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[(g_{w}(\mathbf{x})-f^{\mathcal{S}}(\mathbf{x}))^{2}]\leq\ell_{\mathcal{D}}(g_{w})+\lceil
1/\epsilon\rceil\alpha\|w\|_{1}+\epsilon.$ (30)

Let us compare this bound with the one implied by Corollary 6.5, which applies
since $\ell_{2}$ loss is $([0,1],1,0)$-nice. The main difference is the
addition of the term
$\operatorname*{\mathbf{E}}[(g_{w}(\mathbf{x})-f^{\mathcal{S}}(\mathbf{x}))^{2}]$
to the LHS. This tells us that when $\lceil 1/\epsilon\rceil\alpha\|w\|_{1}$
is small (say $O(\epsilon)$), any linear function that is far (in squared
distance) from $f^{\mathcal{S}}$ incurs large $\ell_{2}$ loss. This theorem
follows from the following Pythagorean bound which holds for the squared
error, proved in Appendix C.3.

######  Lemma 8.4.

In the setting of Theorem 8.3,

$\displaystyle\Bigl{\lvert}\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[\ell_{2}(\mathbf{y},g_{w}(\mathbf{x}))]-\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[\ell_{2}(\mathbf{y},f_{\mathcal{S}}(\mathbf{x}))]-\operatorname*{\mathbf{E}}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}}[(g_{w}(\mathbf{x})-f_{\mathcal{S}}(\mathbf{x}))^{2}]\Bigr{\rvert}\leq\lceil
1/\epsilon\rceil\alpha\|w\|_{1}+\epsilon.$

##  9 Computing approximately multicalibrated partitions

In this section, we show how one can use a weak agnostic learner to compute a
multi-calibrated partition for the multi-class setting, where we are given a
distribution $\mathcal{D}$ on $\mathcal{X}\times[l]$ and our goal is to
compute a partition of $\mathcal{X}$ satisfying definition 5.7. We start with
the definition of a weak agnostic leaner in the setting where the class of
hypotheses $\mathcal{C}$ can be real-valued. Similar definitions appear in the
literature in [17, 25, 21]. We restrict the class of output hypotheses
$\mathcal{C}^{\prime}$ found by the weak learner to be Boolean for simplicity,
but this requirement is easy to relax.

######  Definition 9.1.

Let $\mathcal{C}=\\{c:\mathcal{X}\rightarrow\mathbb{R}\\}$ be a family of
real-valued hypotheses. Let $w:(0,1]\rightarrow(0,1]$ be such that
$w(\alpha)\leq\alpha$. Let
$\mathcal{C}^{\prime}=\\{c^{\prime}:\mathcal{X}\rightarrow\\{0,1\\}\\}$ be a
family of Boolean hypotheses. An $(w,\mathcal{C}^{\prime})$ weak learner for
$\mathcal{C}$ is given sample access to a distribution $\mathcal{D}$ on
$\mathcal{X}\times\\{0,1\\}$. If there exists $c\in\mathcal{C}$ such that
$\operatorname*{{\bf{Cov}}}_{\mathcal{D}}[c(\mathbf{x}),\mathbf{y}]\geq\alpha$,
then with probability $1-\delta$ the weak learner returns a hypothesis
$c^{\prime}\in\mathcal{C}^{\prime}$ such that
$\operatorname*{{\bf{Cov}}}_{\mathcal{D}}[c^{\prime}(\mathbf{x}),\mathbf{y}]\geq
w(\alpha)$.

A few comments on our definition:

  * •

We have defined the weak agnostic learner to work for every distribution
$\mathcal{D}$ on $\mathcal{X}\times\\{0,1\\}$. One can work with a weaker
notion called distribution-specific agnostic learning [21, 10], where we only
have guarantees for a fixed marginal distribution on $\mathcal{X}$.

  * •

Ideally, we would like $w(\alpha)$ to be lower bounded by a polynomial in
$\alpha$, and the sample complexity and running time to depend polynomially on
$1/w(\alpha),\log(1/\delta)$ and the dimensionality of $\mathcal{X}$. Since
$w(\alpha)\leq\alpha$, this allows a polynomial dependence in $1/\alpha$. For
simplicity, we will ignore the failure probability $\delta$ since it can be
made arbitrarily small by repetition. We will state our results in terms of
the number of calls made to the weak learner, through which the running time
and sample complexity of our algorithm will depend on those for the weak
learner.

  * •

We can relax the assumption that $\mathcal{C}^{\prime}$ is Boolean to allow
for bounded real-valued functions: if
$c^{\prime}:\mathcal{X}\rightarrow\mathbb{R}$ satisfies
$\operatorname*{{\bf{Cov}}}[c^{\prime}(\mathbf{x}),\mathbf{y}]\geq w(\alpha)$,
then it is well-known [17] that there exists $\theta$ such that the
$\operatorname*{{\bf{Cov}}}[\mathbbm{1}(c^{\prime}(x)\geq\theta),\mathbf{y}]\geq
w(\alpha)/\max_{x\in\mathcal{X}}|c^{\prime}(x)|$. Such a $\theta$ can be found
by a simple line search.

######  Theorem 9.2.

Given a $(w,\mathcal{C}^{\prime})$ weak learner for $\mathcal{C}$, for any
$\alpha>0$ and any distribution $\mathcal{D}$ on $\mathcal{X}\times[l]$, there
is an efficient algorithm to compute an $\alpha$-approximately multicalibrated
partition for $\mathcal{C},\mathcal{D}$ of size

$m\leq 2l\left(\frac{12}{\alpha w(\alpha/2)^{2}}\right)^{l-1}.$

The partition can be computed by a layered branching program with nodes
labelled by hypotheses from $\mathcal{C}^{\prime}$, of width $m$ and length
$T$ where

$T\leq 2l\left(\frac{12}{\alpha w(\alpha/2)^{2}}\right)^{l}.$

The algorithm makes $O((l/w(\alpha/2))^{O(l)})$ queries to the weak agnostic
learner.

Our algorithm uses ideas and analyses that appear previously in the literature
[29, 17, 13], yet since it differs each of these works along one or more axes,
we present the algorithm and sketch its analysis in Appendix B for
completeness. We highlight the similarities and differences from previous work
below.

  * •

The notion of boosting using branching programs was introduced by [29],
building on the work of [23] on boosting via decision trees. The work of [17]
shows that the [29] algorithm can be used to achieve correlation boosting in
real-valued setting where the labels come form $[0,1]$. Under the assumption
that for any distribution $\mathcal{D}$ on $\mathcal{X}\times[0,1]$, the weak
learner can produce a real-valued hypothesis that has non-trivial correlation
with the labels; Kalai [17] shows that the [29] algorithm produces a
hypothesis whose correlation with the labels is close to $1$. In contrast, we
work with binary labels, and only assume that the weak learner can produce a
correlated hypothesis for a specific marginal distribution $\mathcal{D}_{X}$.
The outcome of our algorithm is a multicalibrated partition. Our definition of
multicalibration is influenced by the correlation-based notion of weak
learning form this work.

  * •

The notion of multicalibrated partitions was introduced in [13] in the context
of computing importance weights. Their work may be thought of defining
approximate multicalibration in the unsupervised setting, which involves some
subtle technical issues. Similarly, our algorithm and analysis follows the
same high level outline, but there are technical differences.

## References

  * BJM [06] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe.  Convexity, classification, and risk bounds.  Journal of the American Statistical Association, 101(473):138–156, 2006.
  * BL [20] Avrim Blum and Thodoris Lykouris.  Advancing Subgroup Fairness via Sleeping Experts.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, pages 55:1–55:24, 2020.
  * BLM [01] Shai Ben-David, Philip M. Long, and Yishay Mansour.  Agnostic boosting.  In 14th Annual Conference on Computational Learning Theory, COLT, 2001.
  * BRA+ [20] Noam Barda, Dan Riesel, Amichay Akriv, Joseph Levy, Uriah Finkel, Gal Yona, Daniel Greenfeld, Shimon Sheiba, Jonathan Somer, Eitan Bachmat, Guy N. Rothblum, Uri Shalit, Doron Netzer, Ran Balicer, and Noa Dagan.  Developing a COVID-19 mortality risk prediction model when individual-level data are not available.  Nat Commun, 11, 2020.
  * BV [04] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, 2004.
  * BYR+ [21] N Barda, G Yona, GN Rothblum, P Greenland, M Leibowitz, R Balicer, E Bachmat, and N. Dagan.  Addressing bias in prediction models by improving subpopulation calibration.  J Am Med Inform Assoc., 28(3):549–558, 2021.
  * Daw [82] A. P. Dawid.  Objective probability forecasts.  University College London, Dept. of Statistical Science. Research Report 14, 1982.
  * DKKN [17] Krzysztof Dembczyński, Wojciech Kotłowski, Oluwasanmi Koyejo, and Nagarajan Natarajan.  Consistency analysis for binary classification revisited.  In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 961–969. PMLR, 06–11 Aug 2017\.
  * DKR+ [21] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona.  Outcome indistinguishability.  In ACM Symposium on Theory of Computing (STOC’21), 2021.
  * Fel [09] Vitaly Feldman.  Distribution-specific agnostic boosting.  arXiv preprint arXiv:0909.2927, 2009.
  * FS [97] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * GKR [19] Sumegha Garg, Michael P. Kim, and Omer Reingold.  Tracking and improving information in the service of fairness.  In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 809–824, 2019\.
  * GRSW [21] Parikshit Gopalan, Omer Reingold, Vatsal Sharan, and Udi Wieder.  Multicalibrated partitions for importance weights.  arXiv preprint arXiv:2103.05853, 2021.
  * Han [94] Bruce E Hansen.  Autoregressive conditional density estimation.  International Economic Review, pages 705–730, 1994.
  * HKRR [18] Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum.  Multicalibration: Calibration for the (computationally-identifiable) masses.  In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018.
  * JLP+ [20] Christopher Jung, Changhwa Lee, Mallesh M. Pai, Aaron Roth, and Rakesh Vohra.  Moment multicalibration for uncertainty estimation.  CoRR, abs/2008.08037, 2020.
  * Kal [04] Adam Kalai.  Learning monotonic linear functions.  In John Shawe-Taylor and Yoram Singer, editors, Learning Theory, 17th Annual Conference on Learning Theory, COLT 2004, volume 3120 of Lecture Notes in Computer Science, pages 487–501. Springer, 2004.
  * Kal [07] Adam Tauman Kalai.  Learning nested halfspaces and uphill decision trees.  In Learning Theory, 20th Annual Conference on Learning Theory, COLT 2007, volume 4539 of Lecture Notes in Computer Science, pages 378–392. Springer, 2007.
  * KGZ [19] Michael P. Kim, Amirata Ghorbani, and James Zou.  Multiaccuracy: Black-box post-processing for fairness in classification.  In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247–254, 2019.
  * Kim [20] Michael P. Kim.  A complexity-theoretic perspective on fairness.  PhD thesis, Stanford University, 2020.
  * KK [09] Adam Kalai and Varun Kanade.  Potential-based agnostic boosting.  In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
  * KKMS [08] Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio.  Agnostically learning halfspaces.  SIAM J. Comput., 37(6):1777–1805, 2008.
  * KM [99] Michael J. Kearns and Yishay Mansour.  On the boosting ability of top-down decision tree learning algorithms.  J. Comput. Syst. Sci., 58(1):109–128, 1999.
  * KMR [17] Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan.  Inherent trade-offs in the fair determination of risk scores.  In 8th Innovations in Theoretical Computer Science Conference, ITCS, 2017.
  * KMV [08] Adam Tauman Kalai, Yishay Mansour, and Elad Verbin.  On agnostic boosting and parity learning.  In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 629–638. ACM, 2008.
  * KNRW [18] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu.  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.  In International Conference on Machine Learning, pages 2564–2572, 2018.
  * KS [05] Adam Tauman Kalai and Rocco A Servedio.  Boosting in the presence of noise.  Journal of Computer and System Sciences, 71(3):266–290, 2005.
  * LV+ [04] Gábor Lugosi, Nicolas Vayatis, et al.  On the bayes-risk consistency of regularized boosting methods.  The Annals of statistics, 32(1):30–55, 2004.
  * MM [02] Yishay Mansour and David McAllester.  Boosting using branching programs.  Journal of Computer and System Sciences, 64(1):103–112, 2002.
  * NKRD [15] Nagarajan Natarajan, Oluwasanmi Koyejo, Pradeep Ravikumar, and Inderjit S. Dhillon.  Optimal decision-theoretic classification using non-decomposable performance metrics.  CoRR, abs/1505.01802, 2015.
  * Pla [99] John C. Platt.  Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods.  In ADVANCES IN LARGE MARGIN CLASSIFIERS, pages 61–74. MIT Press, 1999.
  * RY [21] Guy N. Rothblum and Gal Yona.  Multi-group agnostic PAC learnability.  CoRR, abs/2105.09989, 2021.
  * Sch [89] Mark J. Schervish.  A general method for comparing probability assessors.  The Annals of Statistics, 17(4):1856–1879, 1989.
  * Sco [12] Clayton Scott.  Calibrated asymmetric surrogate losses.  Electronic Journal of Statistics, 6:958–992, 2012.
  * SF [12] Robert E. Schapire and Yoav Freund.  Boosting: Foundations and Algorithms.  MIT Press, 2012.
  * SSBD [14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014.
  * Ste [05] Ingo Steinwart.  Consistency of support vector machines and other regularized kernel classifiers.  IEEE transactions on information theory, 51(1):128–142, 2005.
  * TB [07] Ambuj Tewari and Peter L Bartlett.  On the consistency of multiclass classification methods.  Journal of Machine Learning Research, 8(5), 2007.
  * ZE [01] Bianca Zadrozny and Charles Elkan.  Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers.  In Proceedings of the Eighteenth International Conference on Machine Learning (ICML 2001), pages 609–616. Morgan Kaufmann, 2001.

##  Appendix A Relation to prior definitions of multicalibration

The work of [15, 16] and follow-up papers considers the setting of predictors
$f:\mathcal{X}\rightarrow[0,1]$ and where $\mathcal{C}$ is a collection of
subsets or equivalently of Boolean functions. Our work departs from this along
some axes:

  1. 1.

We consider partitions and not predictors. While this is a seemingly minor
change, it lets us work with the covariance under the conditional
distribution, which proves to be the right notion for numerous technical
reasons. This is inspired by the works of [13] who introduced partitions for
multicalibration in the unsupervised setting, for the problem of computing
importance weights, and [17] who uses covariance as a splitting criterion for
boosting.

  2. 2.

We allow $\mathcal{C}$ to consist of arbitrary real-valued functions, not just
Boolean functions. Real-valued functions have been considered for
multiaccuracy [19] but to our knowledge, not for multicalibration. In the
Boolean setting, our definition is essentially equivalent to that of [15, 16],
under a suitable setting of parameters.

#### Partitions versus Predictors

A predictor is a function $f:\mathcal{X}\rightarrow[0,1]$. The goal of our
algorithm is to produce a predictor that approximates the ground truth values
$f^{*}:\mathcal{X}\rightarrow[0,1]$. We say that $f$ is $\alpha$-calibrated
for a set $S$ if

$\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}|S}[f(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathbf{y}\sim\mathcal{D}}[\mathbf{y}]\Bigr{\rvert}\leq\alpha.$

One can switch between the notions of predictors and partitions with only a
small loss in parameters. We first show how to derive a predictor from a
partition and vice versa.

######  Definition A.1.

For $\lambda>0$, let $m=\lceil 1/\lambda\rceil$ and let
$J(\lambda)=\\{J_{i}\\}_{i=1}^{m}$ denote the partition of $[0,1]$ into
disjoint intervals of width $\lambda$. Given a predictor
$f:\mathcal{X}\rightarrow[0,1]$, the $\lambda$-canonical partition of
$\mathcal{X}$ if given by $\mathcal{S}^{f}=\\{S_{i}\\}_{i=1}^{m}$ where
$S_{i}=f^{-1}(J_{i})$.

Our notion of canonical partition is inspired by the notion of
$\lambda$-discretization in [15], however they discretize the range of $f$,
rather than partition the domain $\mathcal{X}$. Suppose we start from a
partition $\mathcal{S}$ and let $f=f^{\mathcal{S}}$ be its canonical
predictor. The canonical $\lambda$-partion $\mathcal{S}^{f}$ for $f$ will
merge together those states in $\mathcal{S}$ for which
$\operatorname*{\mathbf{E}}[\mathbf{y}]$ lies in $J_{i}$, hence these
expectations are all within $\lambda$ of each other. Hence the canonical
predictor for $\mathcal{S}$ and $\mathcal{S}^{f}$ only differs from the
canonical predictor for $\mathcal{S}$ by $\lambda$. In the other direction, if
we start from $f$ and let $\mathcal{S}=\mathcal{S}^{f}$ be the
$\lambda$-canonical partition, and $f^{\mathcal{S}}$ to be the corresponding
canonical predictor, then
$f^{\mathcal{S}}(x)=\operatorname*{\mathbf{E}}_{S_{i}}[\mathbf{y}]$ is simply
the average of $f$ over all $x$ where $f(x)\in J_{i}$. If the predictor $f$ is
$\alpha$-calibrated for the set $S_{i}$, then this average
$\operatorname*{\mathbf{E}}_{S_{i}}[\mathbf{y}]$ is $\alpha$-close to
$\operatorname*{\mathbf{E}}_{\mathbf{x}\in S_{i}}[f(\mathbf{x})]\in J_{i}$,
hence $|f(x)-f^{\mathcal{S}}(x)|\leq(\alpha+\lambda)$ for any $x\in S_{i}$.

#### Comparing the definitions for Boolean functions

Let us consider the family $\mathcal{C}$ to consist of Boolean functions
$c:\mathcal{X}\rightarrow\\{0,1\\}$. We can associate each $c\in\mathcal{C}$
with the subset $c^{-1}(1)\subseteq\mathcal{X}$. The two relevant definitions
for us are the notion of multicalibration from [15] and mean-multicalibration
from [16]. Both definitions apply to families of sets and predictors, so we
restate them specialized to the setting of a canonical predictor for a
partition. [16] were interested in the case when $y\in[0,1]$, since their goal
was to define multicalibration for higher moments. In our setting, we consider
the Boolean case.

######  Definition A.2.

[16] Let $\mathcal{C}$ be a collection of Boolean functions and let
$\mathcal{S}$ be a partition. The canonical predictor associated with
$\mathcal{S}$ is $\alpha$-mean multicalibrated if for every $c\in\mathcal{C}$

$\displaystyle\Pr_{\mathcal{D}_{i}}[c(\mathbf{x})=1]\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|c(\mathbf{x})=1}[\mathbf{y}]-\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[\mathbf{y}]\Bigr{\rvert}\leq\alpha.$
(31)

This is a slight variation of the original definition of multicalibration from
[15], who required the RHS be bounded by $\alpha$, but then only consider
those $i,c$ where
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})\geq\gamma]$. The
two definitions are equivalent up to a reparametrization, the above
formulation handles the case of small sets by allowing the guarantee to
degrade. See Remark 2.1 of [16].

In Equation (7) we condition on $\mathbf{y}$ and consider the expectation of
$c(\mathbf{x})$, whereas (31) conditions on $c(\mathbf{x})$ and takes the
expectation of $\mathbf{y}$. Conditioning on $\mathbf{y}$ extends naturally
even to real-valued functions $c$ and Boolean labels $\mathbf{y}$, where the
notion of conditioning on $c$ may not make sense. We also extend it to real-
valued $\mathbf{y}$ by considering the event $\mathbbm{1}(\mathbf{y}\in J)$
for some interval $J$. But in fact the two definitions are equivalent when $c$
and $\mathbf{y}$ are both Boolean.

######  Lemma A.3.

For Boolean functions $c$, Equation (31) is equivalent to Equation (6).

###### Proof.

Since $c$ is Boolean we have

$\displaystyle\Pr_{\mathcal{D}_{i}}[c(\mathbf{x})=1]$
$\displaystyle=\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]$
$\displaystyle\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}|c(\mathbf{x})=1}[\mathbf{y}]$
$\displaystyle=\frac{\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})y]}{\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]}.$

We may assume $\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]\neq
0$, else the condition holds trivially. Multiplying both sides by
$\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]$, we can rewrite
Equation (31) as

$\displaystyle\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})y]-\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[y]\Bigr{\rvert}\leq\alpha.$

The quantity on the left is
$|\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),y]|$, hence this
is identical to Equation (6). ∎

##  Appendix B Algorithm for the multi-class setting

In this Section, we sketch the proof of Theorem 9.2.

A distribution in $\mathcal{P}(l)$ in a vector $v\in[0,1]^{l}$ such that
$\sum_{i}v_{i}=1$. We can partition this space into subcubes, where each
subcube is the product of $l$ intervals of length $\delta$. We refer to this
collection of subcubes as $\mathcal{I}_{\delta}$. Naively
$|\mathcal{I}_{\delta}|=O(1/\delta^{l})$, we can also bound it by
$lO(1/\delta^{l-1})$ by observing that since the co-ordinates need to sum to
$1$, fixing the first $l-1$ co-ordinates leaves at most $l$ possible intervals
of the length $\delta$ for the last coordinate.

Our algorithm maintains a partition $\mathcal{S}$ of the space $\mathcal{X}$.
We have a target bound on the number of states $m=|\mathcal{I}_{\delta}|$ for
$\delta$ to be specified later. We will ensure that the number of states never
exceeds $2m$. We iteratively modify the partition until we reach a
multicalibrated partition, using one of two operations $\mathrm{Split}$ and
$\mathrm{Merge}$. $\mathrm{Split}$ increases the number of states in the
partition by $1$. $\mathrm{Merge}$ is applied whenever the number of states
exceeds $2m$ and brings the number down to at most $m$. The algorithm
terminates when neither operation is applicable. This results a sequence
$\\{\mathcal{S}_{t}\\}_{t=0}^{T}$ starting from the trivial partition
$\mathcal{S}_{0}=\\{\mathcal{X}\\}$ until the algorithm terminates with
$\mathcal{S}_{T}$, which we will show is multicalibrated. For very partition
$\mathcal{S}_{t}$, we define a corresponding distribution function
$f_{t}:\mathcal{S}_{t}\rightarrow\mathcal{P}(l)$, where
$f_{t}(S_{i})\in\mathcal{P}(l)$ is the distribution over labels $[l]$
conditioned on $S_{i}$.

####  $\mathrm{Split}$:

The $\mathrm{Split}$ operation takes a two arguments

  1. 1.

A state $S_{i}\in\mathcal{S}_{t}$ such that $\mathcal{D}(S_{i})\geq\alpha/4m$.

  2. 2.

A hypothesis $c^{\prime}\in\mathcal{C}^{\prime}$ such that there exists a
label $j\in[l]$ so that

$\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c^{\prime}(\mathbf{x}),\mathbbm{1}(\mathbf{y}=j)]\geq
w(\alpha/2).$

It splits $S_{i}$ into two states $T_{0}=S_{i}\cap c^{\prime-1}(0)$ and
$T_{1}=S_{i}\cap c^{\prime-1}(1)$ to create the next partition
$\mathcal{S}_{t+1}$. To see if the $\mathrm{Split}$ operation can be applied,
we iterate over all states $S_{i}$ which are sufficiently large
($\mathcal{D}(S_{i})\geq\alpha/4m$). For every $j\in[l]$, we create a
distribution $\mathcal{D}_{i,j}$ on $\mathcal{X}\times\\{0,1\\}$ by sampling a
pair $\mathbf{x},\mathbf{y}$ according to $\mathcal{D}_{i}$ and outputting the
pair $(\mathbf{x},\mathbbm{1}(\mathbf{y}=j))$. We run the weak learner on each
such distribution $\mathcal{D}_{i,j}$. If for some $j$, it find a hypothesis
$c^{\prime}\in\mathcal{C}^{\prime}$, we run $\mathrm{Split}$ on the apir
$(S_{i},c^{\prime})$.

####  $\mathrm{Merge}$:

The $\mathrm{Merge}$ operation is applied whenever the number of states
exceeds $2m$, and brings it down to at most $m$. For every subcube
$I\in\mathcal{I}_{\delta}$, we merge all states $S_{i}$ so that
$f_{t}(S_{i})\in I$ into a single state.

#### Correctness.

Suppose the algorithm terminates at time $T$, and let $m_{T}$ denote the
number of states. For every $i\in m_{T}$ such that
$\mathcal{D}(S_{i})\geq\alpha/4m$, for every $c\in\mathcal{C}$ and $j\in[l]$

$\displaystyle\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbbm{1}(\mathbf{y}=j)]\leq\alpha/2$
(32)

If this condition were violated, then running the weak learner on
$\mathcal{D}_{i}$ is guaranteed to find $c^{\prime}$, such that we can run
$\mathrm{Split}$ on the pair $S_{i},c^{\prime}$, violating the termination
condition. We can use these conditions to show that for any $c\in\mathcal{C}$
and $j\in[l]$,

$\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\left|\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbbm{1}(\mathbf{y}=j)\right|\right]\leq\alpha$

hence the partition is indeed multicalibrated. The total contribution from
small states $S_{i}$ such that $\mathcal{D}(S_{i})\leq\alpha/4m$ is at most
$\alpha/2$ since there are at most $2m$ states. By Equation (32), the
contribution to it from large states is bounded by $\alpha/2$.

#### Running time.

We bound the number of iterations using
$\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[\|f_{t}(\mathbf{x})\|^{2}]$
as our potential function, as in [17]. If $\mathcal{S}_{t+1}$ is created from
$\mathcal{S}_{t}$ by splitting the state $S_{i}$ using
$c^{\prime}\in\mathcal{C}^{\prime}$, then one can show that

$\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[\|f_{t+1}(\mathbf{x})\|^{2}]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[\|f_{t}(\mathbf{x})\|^{2}]\geq\mathcal{D}(S_{i})\sum_{j\in[l]}\left(\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c^{\prime}(x),\mathbbm{1}(\mathbf{y}=j)]\right)^{2}\geq\frac{\alpha}{4m}w(\alpha/2)^{2}.$

On the other hand, one can show that a $\mathrm{Merge}$ operation only causes
a small reduction in the potential. If $\mathcal{S}_{t+1}$ is created from
$\mathcal{S}_{t}$ by a $\mathrm{Merge}$ operation, then

$\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[\|f_{t+1}(\mathbf{x})\|^{2}]-\operatorname*{\mathbf{E}}_{\mathbf{x}\sim\mathcal{D}}[\|f_{t}(\mathbf{x})\|^{2}]\geq-2\delta.$

Since the $\mathrm{Merge}$ operation reduces the number of states from $2m$ to
$m$, there are at least $m$ $\mathrm{Split}$ operations before the next
$\mathrm{Merge}$ happens. If we partition time into epochs, each ending with a
$\mathrm{Merge}$, then in each epoch, the potential increases by at least

$m\frac{\alpha}{4m}w(\alpha/2)^{2}-2\delta=\frac{\alpha}{4}w(\alpha/2)^{2}-2\delta\geq\delta$

if we choose

$\delta=\frac{\alpha}{12}w(\alpha/2)^{2}.$

Since the potential can be at most $1$, this implies a bound of $1/\delta$ on
the number of epochs. We have

$m_{T}\leq 2m\leq 2l/\delta^{l-1}\leq 2l\left(\frac{12}{\alpha
w(\alpha/2)^{2}}\right)^{l-1}$

Since the number of epochs is at most $1/\delta$ and a single epoch involves
at most $2m$ $\mathrm{Split}$ operations, we have

$T\leq 2m/\delta\leq 2l/\delta^{l}\leq 2l\left(\frac{12}{\alpha
w(\alpha/2)^{2}}\right)^{l}.$

#### Sample Complexity.

At each time step, the weak agnostic learner might be invoked at most $l\cdot
m$ times. Since we only consider those states $S_{i}$ where
$\mathcal{D}(S_{i})\geq\alpha/4m$, the number of samples from $\mathcal{D}$
needed for each call is roughly $4m/\alpha$ times the sample complexity of the
weak agnostic learner. Overall, the multiplicative overhead in sample
complexity over the weak agnostic learner is

$lm\cdot 4m/\alpha\cdot T=O\left(l^{2}\left(\frac{12}{\alpha
w(\alpha/2)^{2}}\right)^{3l}\right).$

##  Appendix C More Proofs

###  C.1 Proofs from Section 5

###### Proof of Corollary 5.1.

Since $\mathbf{y}\in\\{0,1\\}$,
$\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{y}]=\Pr_{\mathcal{D}}[\mathbf{y}=1]$,
while
$\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}\mathbf{y}]=\Pr[\mathbf{y}=1]\operatorname*{\mathbf{E}}_{\mathcal{D}}[\mathbf{z}|\mathbf{y}=1]$.
Substituting in the definition of covariance gives the first equality in
Equation (5). To derive the second equality, we let
$\mathbf{y}^{\prime}=1-\mathbf{y}$ so that

$\operatorname*{{\bf{Cov}}}_{\mathcal{D}}[\mathbf{z},\mathbf{y}^{\prime}]=\operatorname*{{\bf{Cov}}}_{\mathcal{D}}[\mathbf{z},1-\mathbf{y}]=-\operatorname*{{\bf{Cov}}}_{\mathcal{D}}[\mathbf{z},\mathbf{y}]$

and then apply the same reasoning to $\mathbf{y}^{\prime}$. ∎

###### Proof of Lemma 5.5.

Let $L\subseteq[m]$ denote the set of states for which Equation (10) does not
hold. For such states we use the bound

$\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbf{y}]\leq\max_{x\in\mathcal{X},y\in\\{0,1\\}}|c(x)||y|\leq\left\lVert
C\right\rVert_{\infty}.$

Hence

$\sum_{i\in
L}D(S_{i})\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbf{y}]\leq
m\frac{\alpha}{2m\left\lVert C\right\rVert_{\infty}}\left\lVert
C\right\rVert_{\infty}\leq\frac{\alpha}{2}.$

By Equation (11) we have the bound

$\sum_{i\not\in
L}D(S_{i})\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbf{y}]\leq\frac{\alpha}{2}.$

Summing the two bounds, we conclude that $\mathcal{S}$ is
$\alpha$-approximately multicalibrated. ∎

###### Proof of Corollary 5.6.

By Equation (5),

$\displaystyle\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\Pr_{\mathcal{D}_{i}}[\mathbf{y}=b]\left|E_{\mathcal{D}_{i}|\mathbf{y}=b}[c(\mathbf{x})]-\operatorname*{\mathbf{E}}_{\mathcal{D}_{i}}[c(\mathbf{x})]\right|\right]=\operatorname*{\mathbf{E}}_{\mathbf{i}\sim\mathcal{D}}\left[\left|\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{\mathbf{i}}}[(c\mathbf{x}),\mathbf{y}]\right|\right]\leq\alpha.$

∎

###### Proof of Lemma 5.9.

Let $g_{w}\in\mathrm{Lin}_{\mathcal{C}}(W)$. Then for each $i\in[m]$, using
the linearity of covariance

$\displaystyle\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[g_{w}(\mathbf{x}),\mathbf{y}]=w_{0}\operatorname*{{\bf{Cov}}}[1,\mathbf{y}]+\sum_{j\geq
1}w_{j}\operatorname*{{\bf{Cov}}}_{D_{i}}[c_{j}(\mathbf{x}),\mathbf{y})]=\sum_{j\geq
1}w_{j}\operatorname*{{\bf{Cov}}}_{D_{i}}[c_{j}(\mathbf{x}),\mathbf{y})]$

Averaging over states, using the triangle inequality and using approximate
multicalibration,

$\displaystyle\sum_{i\in[m]}\mathcal{D}(S_{i})\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[g_{w}(\mathbf{x}),\mathbf{y}]\Bigr{\rvert}$
$\displaystyle=\sum_{i\in[m]}\mathcal{D}(S_{i})\Bigl{\lvert}\sum_{j\geq
1}w_{j}\operatorname*{{\bf{Cov}}}_{D_{i}}[c_{j}(\mathbf{x}),\mathbf{y})]\Bigr{\rvert}$
$\displaystyle\leq\sum_{i\in[m]}\mathcal{D}(S_{i})\sum_{j\geq
1}|w_{j}|\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{D_{i}}[c_{j}(\mathbf{x}),\mathbf{y})]\Bigr{\rvert}$
$\displaystyle=\sum_{j\geq
1}|w_{j}|\sum_{i\in[m]}\mathcal{D}(S_{i})\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{D_{i}}[c_{j}(\mathbf{x}),\mathbf{y})]\Bigr{\rvert}$
$\displaystyle\leq\alpha\sum_{j\geq 1}|w_{j}|\leq\alpha W.$

∎

###  C.2 Proof of Theorem 5.10

In order to prove Theorem 5.10, we will first restate the definition of
multicalibration as follows. For a set $S\subseteq\mathcal{X}$, let $S(x)=1$
if $x\in S$ and $0$ otherwise.

######  Lemma C.1.

The partition $\mathcal{S}$ of $\mathcal{X}$ is $\alpha$-approximately
multicalibrated for $\mathcal{C},\mathcal{D}$ iff for every $c\in\mathcal{C}$,

$\displaystyle\sum_{i\in[m]}\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[S_{i}(x)c(\mathbf{x})(\mathbf{y}-p_{i})]\Bigr{\rvert}\leq\alpha.$
(33)

###### Proof.

We can rewrite the LHS of Equation (8) as

$\displaystyle\sum_{i\in[m]}\mathcal{D}(S_{i})\Bigl{\lvert}\operatorname*{{\bf{Cov}}}_{\mathcal{D}_{i}}[c(\mathbf{x}),\mathbf{y}]\Bigr{\rvert}=\sum_{i\in[m]}\mathcal{D}(S_{i})\frac{\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[S_{i}(x)c(\mathbf{x})(y-p_{i})]\Bigr{\rvert}}{\mathcal{D}(S_{i})}=\sum_{i\in[m]}\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[S_{i}(x)c(\mathbf{x})(y-p_{i})]\Bigr{\rvert}$
(34)

∎

###### Proof of Lemma 5.10.

By Lemma C.1, our goal is to show that for any
$c^{\prime}\in\mathcal{C}^{\prime}$,

$\displaystyle\sum_{i\in[m]}\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}^{\prime}}[S^{\prime}_{i}(x)c^{\prime}(\mathbf{x})(\mathbf{y}-p^{\prime}_{i})]\Bigr{\rvert}\leq\frac{(1+\left\lVert\mathcal{C}^{\prime}\right\rVert_{\infty})\alpha}{\mathcal{D}(\mathcal{X}^{\prime})}.$
(35)

Observe that the expectations are of quantities supported on
$\mathcal{X}^{\prime}$, and for every $x\in X^{\prime}$,
$\mathcal{D}^{\prime}_{i}(x)=\mathcal{D}_{i}(x)/\mathcal{D}(\mathcal{X}^{\prime})$,
so this is equivalent to showing that

$\displaystyle\sum_{i\in[m]}\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[S^{\prime}_{i}(x)c^{\prime}(\mathbf{x})(\mathbf{y}-p^{\prime}_{i})]\Bigr{\rvert}\leq(1+\left\lVert\mathcal{C}^{\prime}\right\rVert_{\infty})\alpha.$

We will bound the LHS using the triangle inequality as

$\displaystyle\sum_{i\in[m]}\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[S^{\prime}_{i}(x)c^{\prime}(\mathbf{x})(\mathbf{y}-p^{\prime}_{i})]\Bigr{\rvert}\leq\sum_{i\in[m]}\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[S^{\prime}_{i}(x)c^{\prime}(\mathbf{x})(\mathbf{y}-p_{i})]\Bigr{\rvert}+\sum_{i\in[m]}\Bigl{\lvert}\operatorname*{\mathbf{E}}_{\mathcal{D}}[S^{\prime}_{i}(x)c^{\prime}(\mathbf{x})(p^{\prime}_{i}-p_{i})]\Bigr{\rvert}.$
(36)

We claim that for every $x\in\mathcal{X}$,
$S(x)c^{\prime}(x)=S_{i}^{\prime}(x)c^{\prime}(x)$. This follows since
$S_{i}(x)-S_{i}^{\prime}(x)=0$ for $x\in\mathcal{X}^{\prime}$ and
$c^{\prime}(x)=0$ for $x\not\in\mathcal{X}^{\prime}$ since
$c^{\prime}\in\mathcal{C}^{\prime}$ is supported on $\mathcal{X}^{\prime}$.
Hence we can bound the first term by