Loss Minimization Yields Multicalibration for Large Neural Networks
Multicalibration is a notion of fairness for predictors that requires them to
provide calibrated predictions across a large set of protected groups.
Multicalibration is known to be a distinct goal than loss minimization, even
for simple predictors such as linear functions.
  In this work, we consider the setting where the protected groups can be
represented by neural networks of size $k$, and the predictors are neural
networks of size $n > k$. We show that minimizing the squared loss over all
neural nets of size $n$ implies multicalibration for all but a bounded number
of unlucky values of $n$. We also give evidence that our bound on the number of
unlucky values is tight, given our proof technique. Previously, results of the
flavor that loss minimization yields multicalibration were known only for
predictors that were near the ground truth, hence were rather limited in
applicability. Unlike these, our results rely on the expressivity of neural
nets and utilize the representation of the predictor.
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, Preetum Nakkiran
# Loss minimization yields multicalibration

###### Abstract

Multicalibration is a notion of fairness that aims to provide accurate predictions across a large set of groups. Multicalibration is known to be a different goal than loss minimization, even for simple predictors such as linear functions. In this note, we show that for (almost all) large neural network sizes, optimally minimizing squared error leads to multicalibration. Our results are about representational aspects of neural networks, and not about algorithmic or sample complexity considerations. Previous such results were known only for predictors that were nearly Bayes-optimal and were therefore representation independent. We emphasize that our results do not apply to specific algorithms for optimizing neural networks, such as SGD, and thus they should not be interpreted as "fairness comes for free from optimizing neural networks".

## 1 Introduction

Accuracy and multicalibration (MC) are different notions. Accuracy is typically framed as loss minimization. For simplicity, consider the squared loss of a predictor \(\ell(f):=\mathbb{E}[(f(x)-y)^{2}]\), with bounded labels \(y\in\{0,1\}\) and examples \((x,y)\in\mathcal{X}\times\mathcal{Y}\) that are drawn from an arbitrary joint distribution \(\mathcal{D}\). A predictor is a function \(f:\mathcal{X}\to[0,1]\) which assigns to each point \(x\) a probability \(f(x)\) which is the estimated probability that the label is \(1\). The notions of multicalibration, introduced in the work of Hebert-Johnson et al. (2018) is a notion of fairness that applies to every subgroup in a family \(\mathcal{C}\). Informally, it asks that the predictions be calibrated even conditioned on membership in \(\mathcal{C}\).

**Definition 1.1** (Multicalibration (Kim et al., 2022; Hebert-Johnson et al., 2018)).: _Let \(\alpha>0\) and \(\mathcal{C}\) be a class of auditor functions \(c:\mathcal{X}\times[0,1]\to[0,1]\). The predictor \(f:\mathcal{X}\to[0,1]\) is \((\mathcal{C},\alpha)\)-multicalibrated or \((\mathcal{C},\alpha)\)-MC if for all \(c\in\mathcal{C}\),_

\[\Big{|}\,\mathbb{E}_{x,y}\left[c\big{(}x,f(x)\big{)}\cdot\big{(}y-f(x)\big{)} \right]\Big{|}\leq\alpha.\]

_When \(\mathcal{C}\) is clear from context, we say that \(f\) is \(\alpha\)-MC for brevity. 1_

Footnote 1: The MC definition above is version due to Kim et al. (2022, Appendix 1), which was also used by Deng et al. (2023); Dwork et al. (2022). The original definition (Hebert-Johnson et al., 2018; Gopalan et al., 2022) considers only those \(c\) that can be factored as \(c(x,f(x))=g(x)w(f(x))\) where \(g:\mathcal{X}\to[0,1]\) and \(w:[0,1]\to[0,1]\). For the setting where \(\mathcal{C}\) is a family of neural nets, the general definition is more natural, since it amounts to both \(x\) and \(f(x)\) being inputs to an auditor neural net.

When \(c\) maps to \(\{0,1\}\) values, it can be viewed as defining a _group_ which is a subset of the domain \(\mathcal{X}\) and MC means that \(\mathbb{E}[y]\approx\mathbb{E}[f(x)]\) conditioned on membership in this group, where the degree of closeness depends on the size of the group. Good calibration is guaranteed for any group of sufficient likelihood that can be computed by the classifier family.
We also consider the weaker notion of multiaccuracy in expectation, where the auditor \(\mathcal{C}\) does not have access to the predictions.

**Definition 1.2** (Multiaccuracy in expectation (Hebert-Johnson et al., 2018)).: _Let \(\alpha>0\) and \(\mathcal{C}\) be a class of auditor functions \(c:\mathcal{X}\to[0,1]\). The predictor \(f:\mathcal{X}\to[0,1]\) is \((\mathcal{C},\alpha)\)-multiaccurate or \((\mathcal{C},\alpha)\)-MA if for all \(c\in\mathcal{C}\),_

\[\Big{|}\,\mathbb{E}_{x,y}\big{[}c(x)\cdot\big{(}y-f(x)\big{)}\big{]}\,\Big{|} \leq\alpha.\]

Multiaccuracy implies the weaker guarantee of accuracy in expectation for any group of sufficient likelihood that can be computed by the classifier family \(\mathcal{C}\).

In this work, we consider the class \(\mathcal{C}\) computed by bounded-size Neural Networks (NNs), say of at most \(k\) nodes. This is a flexible representation due to the universality of NNs. For large enough \(k\), \(\mathcal{C}\) can express predicates like \(x\in S\) and \(f(x)\in I\) for simple subsets \(S\subseteq\mathcal{X}\) and \(I\subseteq[0,1]\). Our definition allows the generalization to \(c\) that may output real values in \([0,1]\), which we can think of conditioning on a distribution. The size restriction \(k\) is of interest and will play a fundamental role in our analysis. It captures the complexity of the auditor class \(\mathcal{C}\), which may be smaller than the predictor \(f\) learned in many cases of interest, if we require that \(f\) be \((\mathcal{C},\alpha)\)-multicalibrated.

It is easy to show that the Bayes optimal predictor \(f(x)=\mathbb{E}[y\mid x]\) both perfectly minimizes squared loss and is also perfectly multicalibrated with respect to any class \(\mathcal{C}\)(see Barocas et al., 2019, Chapter 3). Liu et al. (2019) bound the MC error in terms of closeness to Bayes optimality. While interesting, these statements are representation independent-they do not shed light on different representations used in practice, such as linear predictors or NNs. In general, it is unclear whether the optimal predictor from a restricted family, which is chosen to minimize a certain loss should satisfy multicalibration (or even just calibration). It is easy to see that a loss-optimal linear function will not in general be multicalibrated. Our core question is: _are loss-optimal NNs multicalibrated_?

The relation between loss minimization and multicalibration has been investigated extensively in the literature over the last few years (Kim et al., 2019, Gopalan et al., 2022, 2023a). It is known that minimizing any proper loss for linear models over a base hypothesis class \(\mathcal{C}\) yields multiaccuracy for \(\mathcal{C}\)(Gopalan et al., 2023a), but not multicalibration (Gopalan et al., 2022c). Indeed, it is known from the work of Gopalan et al. (2022a) that achieving multicalibration is as hard as minimizing arbitrary convex losses over \(\mathcal{C}\). However, little was known about the relation between these notions and models for which loss-minimization is non-convex, most importantly for deep neural nets. Kim et al. (2019) showed that retraining the last layer of a DNN with cross-entropy guarantees multiaccuracy with respect the features in the penultimate layer; this can be seen as a consequence of the result of Gopalan et al. (2023a) for linear models. To summarize the state of our understanding before this work, the convex setting was well understood, but there was little evidence one way or the other for how loss minimization and multicalibration relate in the non-convex case in setting, and for DNNs in particular.

### Our results

We present the following answer to this question: _(most) loss-optimal large NNs are in fact multicalibrated_. Thus unlike simple classifiers, such as linear threshold functions, which face a trade-off between optimizing loss and MC, we show that for large NNs, the goals of MC and accuracy are closely aligned. Simpler representations may have other redeeming qualities, such as interpretability, but our analysis shows that NNs do not face the same inherent tension.

This is important because it would otherwise be natural to combine NNs with existing MC algorithms. These MC algorithms are boosting-like algorithms that can achieve MC using any loss-minimizing algorithm-they repeatedly run the learning algorithm and produce a classifier that is an ensemble of the
base classifiers (in this case NNs). Of course, one cannot efficiently solve the NP-hard problem of minimizing loss over all NNs of a given size, and in practice heuristics such as gradient descent are used. In this paradigm common in computational learning theory, an analysis of perfect loss minimization sheds light on a heuristic optimizer-if the property fails to hold for the heuristic then we understand it is due to poor loss minimization (and sometimes can be used to further reduce loss). Our results suggest that, rather than using an MC algorithm which would train multiple NNs and output a complex ensemble, one may prefer to simply train a larger NN. However, like the analysis of these MC algorithms, our analysis only holds assuming one can minimize loss over NNs (and a MC failure, once detected, can be directly converted into a NN with lower loss).

Making this precise is somewhat subtle. Our results do not address algorithmic or sample complexity of NNs, which is left for future work. We disregard training time, compute and data resources. The results may be of interest purely for understanding NNs as a representation, similar to the universal representation theorems (e.g., Hornik et al., 1989). They also may be relevant to settings where inference is the bottleneck, e.g., the case where one is concerned with accuracy and model size. Using massive training resources is also consistent with recent large-scale pre-training efforts used to create models that can be then re-used across numerous applications, such as GPT-3 (Brown et al., 2020), PaLM (Chowdhery et al., 2022) and DALL-E-2 (Ramesh et al., 2022). Model-size and accuracy are often of greater importance as the pre-training costs can be amortized over numerous applications of inference.

For neural nets, there may be no single optimal NN but instead a sequence of successively larger NNs that achieve decreasing losses, only approaching Bayes optimality for impractically large networks. One must therefore select a finite-size NN. If we are simply outputting the NN with lowest generalization loss, this essentially amounts to selecting the size. The first theorem states that for all but a bounded number of NN sizes, the loss-optimal NN is nearly MC with respect to smaller NNs, say of size \(k\) nodes.

**Theorem 1.3** (Informal version of Theorem 3.2).: _Let \(k\in\mathbb{N}\) be an integer and \(\alpha\in(0,1]\). Then there are only \(O(k/\alpha^{2})\) different neural network sizes \(n\) for which the loss-optimal \(n\)-node NN is not \(\alpha\)-MC with respect to NNs of size \(k\)._

While this does not indicate which NN sizes will lead to MC, it suggests that the vast majority of loss-optimal large NNs (size \(\gg k/\alpha^{2}\)) are MC. The intuition behind why a large NN is MC is simple: if a NN \(f\) is not MC, then its loss can be improved using the classifier \(c\) which is a witness to its MC failure. Unfortunately, this improved NN is larger, so \(f\) may be optimal for its size. Nonetheless, we are able to bound the number of sizes for which MC fails. In other words, failure of the loss-optimizer to be multicalibrated at size \(n\) indicates a significant drop in loss happens at size \(n+k\), and such significant drops cannot happen too often.

We also give a second approach based on regularization, which can also be motivated economically. Deploying large classifiers is expensive. To deploy a finite classifier, one may consider a cost, say, a linear cost of for deploying a NN of \(n\) nodes. Once amortized over queries, this is equivalent to using regularization and choosing a classifier that minimizes loss plus a constant, say \(1/N\), times size. Since loss \(\ell(f)\in[0,1]\), the optimal solution is always an NN with at most \(N\) nodes. Our second theorem shows that large NNs optimized for loss, with sufficiently small regularization, achieve MC. These networks may be similarly large.

**Theorem 1.4** (Informal version of Theorem 3.3).: _Let \(k\in\mathbb{N}\) be an integer and \(\alpha\in(0,1]\). Then, for \(N=O(k/\alpha^{2})\), selecting a NN with size regularization term \(1/N\) will lead to a NN of size \(\leq N\) that is \(\alpha\)-MC with respect to NNs of size \(k\)._

While we cannot give tight lower bounds for analysis, Section 4 presents lower bounds suggesting that our current analysis cannot be significantly improved. To do this, we observe that the same exact
analysis proves that loss minimization for Juntas (functions depending on a bounded number of features) yields multiaccuracy for juntas of bounded size \(k\). Here we show a lower bound, proving tightness up to constant factors of our bounds: there are indeed \(\Omega(k/\alpha^{2})\) integers \(n\) for which the loss-optimal junta is not multiaccurate. The right quantitative bound uses the noise stability of the majority function (see O'Donnell, 2014). Thus, a stronger result, if it exists, would use properties of DNNs and calibration beyond what our proof currently uses.

**Theorem 1.5** (Informal statement of Theorem 4.2).: _Let \(\mathcal{J}_{k}(\mathcal{X})\) denote functions that depend on \(k\) input variables from the domain \(\mathcal{X}=\{\pm 1\}^{m}\). For every \(k\) and small enough \(\alpha\), there exist \(m\in\mathbb{Z}_{>0}\), a distribution \(\mathcal{D}\) over \(\mathcal{X}\times\{0,1\}=\{\pm 1\}^{m}\times\{0,1\}\), and at least \(\Omega(k/\alpha^{2})\) distinct non-negative integers \(n\) such that any model \(f_{n}\in\mathcal{J}_{n}(\mathcal{X})\) is not \((\mathcal{C},\alpha)\)-MA with respect to \(\mathcal{C}=\mathcal{J}_{k}(\mathcal{X})\)._

Contributions.Our main contribution is proving that for "most" large NNs, loss-optimal NNs are multicibrated. We provide two ways of formalizing the notion of most, which both lead to similar bounds. This can be viewed as an additional potential benefit of the NN representation, which is not satisfied by all other representations. However, as discussed in Section 6, this should not be viewed as a statement that "fairness comes for free if you just optimize NNs," because of the blowup we face in the NN size, because MC is not itself adequate for fairness in some applications, and because it is not known if we can efficiently find perfectly optimal NNs.

The work of Hebert-Johnson et al. (2018) reduces the problem of learning such a predictor to weak agnostic learning for the class \(\mathcal{C}\). Their algorithm starts an arbitrary predictor \(f\) and a weak agnostic learner for the class \(\mathcal{C}\), and post-process \(f\) to a predictor \(g\) which is \((\mathcal{C},\alpha)\)-multicalibrated. One can view \(g\) as being a circuit composed of \(f\) together with some number of hypothesis from the class \(\mathcal{C}\). Subsequently, Gopalan et al. (2022) showed that MC can be achieved using the boosting via branching programs algorithm of Mansour and McAllester (2002). Given that NNs are essentially circuits, hence more general than branching programs, it is perhaps not surprising that one can achieve MC using a neural net architecture.

But in this view, we only think of neural nets as a circuit class, without paying attention to how they are learned. The dominant approach to learning a neural net is to fix an architecture and then perform loss minimization. Previous results did not shed much light on whether neural nets learned using this paradigm can be reasonably multicibrated for an expressive class \(\mathcal{C}\). Our work takes a step in this direction by showing that the goal of loss minimization is aligned with multicalibration. The next step towards would be to specialize the loss minimization algorithm to stochastic gradient descent, which is popularly used, and ask if the resulting neural nets offer any multicalibration guarantees.

Organization.Section 2 defines the setting and mathematical preliminaries. Section 3 gives our main results, with the regularization analysis covered in Section 3.1. Releated work is presented in Section 5. Finally, Section 6 discusses risks and limitations of the present work.

## 2 Preliminaries

We assume \(\mathcal{X}\subseteq\mathbb{R}^{d}\) is a Euclidean space in some dimension \(d\), and focus on binary classification where \(\mathcal{Y}=\{0,1\}\). We can also allow for \(\mathcal{Y}=[0,1]\), in which case the multicalibration guarantee we achieve is called mean multicalibration (Jung et al., 2020), or the multiclass setting with \(l>2\) distinct labels, we focus on the binary classification setting for simplicity. We assume an arbitrary, unknown joint distribution \(\mathcal{D}\) on \(\mathcal{X}\times\mathcal{Y}\). For simplicity we focus on the \(l_{2}\) loss,

\[\ell(f):=\operatorname*{\mathbb{E}}_{\mathcal{D}}\left[\left(y-f(x)\right)^{2} \right].\]
Since only one distribution \(\mathcal{D}\) is used throughout the analysis, we assume it is fixed and omit it from our notation, e.g., writing \(\ell(f)\) rather than \(\ell_{\mathcal{D}}(f)\) and omitting it from the expectation when clear from context, as above.

For a Euclidean subset \(S\), let \(\mathsf{NN}_{n}(S)\) denote the family of fully-connected Neural Networks with the standard ReLU activations and exactly \(n\) nodes, which map inputs from \(S\) to output values in \([0,1]\). The ReLU activation computes \(\mathsf{ReLU}(z):=\max(0,z)\) on input \(z\). Thus \(\mathsf{NN}_{n}\) is defined by a Directed Acyclic Graph (DAG) with \(n\) nodes, where the activation of a node with \(d_{\text{in}}\) inputs is \(a=\mathsf{ReLU}(w\cdot a_{\text{in}}+b)\) where \(a_{\text{in}}\in\mathbb{R}^{d_{\text{in}}}\) is the vector of activations of its inputs, \(w\in\mathbb{R}^{d_{\text{in}}}\) is a vector of equal dimension, and \(b\in\mathbb{R}\) is a bias term. We also define \(\mathsf{NN}_{0}=\{0\}\), i.e., the constant \(0\) function is defined to be computed by a 0-node NN. The set of functions computed by \(\mathsf{NN}_{n}(S)\) is monotonically increasing with \(n\) since we can trivially add identity nodes to compute the same function.

Enforcing an output in \([0,1]\) is added to the definition for convenience and can easily be achieved by wrapping the output \(z\) in two ReLUs:

\[\forall z\in\mathbb{R}\ \operatorname{clip}_{[0,1]}(z):=\mathsf{ReLU}(z- \mathsf{ReLU}(z-1))=\max(0,\min(1,z))\in[0,1]. \tag{1}\]

The results in this paper can be extended by enforcing various architectures, such as a NN with a given number of hidden layers, but we present the results for a general feed-forward architecture for simplicity.

## 3 Multicalibration and NNs

A standard fact from statistics is that if one has a function that is correlated with the residual \(y-f(x)\), one can scale and add it to the predictor to reduce loss, and clipping it to the interval \(\mathcal{Y}=[0,1]\) can only further reduce loss. This combination can easily be computed using ReLU functions. The Lemma below shows that if a \(k\)-node witness \(c\) to the fact that \(f\) is not \(\alpha\)-MC, can be used to augment \(f\) with \(k+3\) additional nodes and reduce its loss by at least \(\alpha^{2}\).

**Lemma 3.1** (Loss reduction from MC).: _Let \(f\in\mathsf{NN}_{n}(\mathcal{X})\), \(c\in\mathsf{NN}_{k}(\mathcal{X}\times\mathcal{Y})\) and suppose,_

\[\mathbb{E}\left[c\big{(}x,f(x)\big{)}\cdot\big{(}y-f(x)\big{)}\right]=\beta.\]

_Then \(h(x):=\operatorname{clip}_{[0,1]}\bigl{(}f(x)+\beta c(x,f(x))\bigr{)}\) belongs to \(\mathsf{NN}_{n+k+3}(\mathcal{X})\) and has loss \(\ell(h)\leq\ell(f)-\beta^{2}\)._

Proof.: Observe that \(h(x)=\operatorname{clip}_{\mathcal{Y}}\bigl{(}f(x)+\beta c(x,f(x))\bigr{)}\) is computed by

\[h(x)=\mathsf{ReLU}\bigl{(}\mathsf{ReLU}(f(x)+\beta c(x,f(x)))-\mathsf{ReLU}(f( x)+\beta c(x,f(x))-1)\bigr{)}. \tag{2}\]

as can be seen through Eq. (1). Then observe that Eq. (2) is indeed a representation of a \((n+k+3)\)-node NN: \(n\) nodes to compute \(f(x)\), \(k\) nodes to compute \(c(x,f(x))\) and then the 3 additional ReLU nodes as described (note that \(f(x)\) and \(c(x,f(x))\) are both re-used without recomputing them). Thus \(h\in\mathsf{NN}_{n+k+3}(\mathcal{X})\) as claimed.

Next, define \(g(x):=f(x)+\beta c(x,f(x))\), so \(h(x)=\operatorname{clip}_{[0,1]}(g(x))\). Then,

\[\ell(g) =\mathbb{E}\left[(y-f(x)-\beta c(x,f(x)))^{2}\right]\] \[=\mathbb{E}\left[(y-f(x))^{2}-2\beta c(x,f(x))(y-f(x))+\beta^{2}c ^{2}(x,f(x))\right]\] \[=\ell(f)-2\beta\,\mathbb{E}\left[c(x,f(x))(y-f(x))\right]+\beta^{ 2}\,\mathbb{E}\left[c^{2}(x,f(x))\right]\] \[=\ell(f)-2\beta^{2}+\beta^{2}\,\mathbb{E}\left[c^{2}(x,f(x)) \right].\]

Since \(c^{2}(x,f(x))\leq 1\), this implies that \(\ell(g)\leq\ell(f)-\beta^{2}\). Finally, note that for any \((x,y)\), \((y-h(x))^{2}\leq(y-g(x))^{2}\) since \(y\in\{0,1\}\) and \(h(x)\) is the projection of \(g(x)\) onto the closest point in \([0,1]\), thus \(\ell(h)\leq\ell(g)\)
Using this lemma, we can now prove our main result. The first states that the set of NN sizes \(n\) for which there is a loss-optimal, \(n\)-node NN that is _not_\((\mathcal{C},\alpha)\)-MC is at most \((k+3)/\alpha^{2}\).

**Theorem 3.2**.: _Let \(\mathcal{D}\) be a distribution over \(\mathcal{X}\times\mathcal{Y}\), and let \(k\in\mathbb{N}\) and \(\alpha\in(0,1]\). Then for all but at most \((k+3)/\alpha^{2}\) integers \(n\in\mathbb{N}\), for every minimizer \(\hat{f}_{n}\):_

\[\hat{f}_{n}\in\operatorname*{arg\,min}_{f\in\mathsf{NN}_{n}(\mathcal{X})}\ell (f),\]

\(\hat{f}_{n}\) _is \((\mathcal{C},\alpha)\)-MC with respect to \(\mathcal{C}=\mathsf{NN}_{k}(\mathcal{X}\times\mathcal{Y})\)._

Proof.: Say an \(n\)-node NN is "bad" if it minimizes loss among \(\mathsf{NN}_{n}(\mathcal{X})\) but is _not_\((\mathcal{C},\alpha)\)-MC. Say size \(n\) is "bad" if there is any bad \(n\)-node NN. For each \(n\), fix \(f_{n}\in\mathsf{NN}_{n}(\mathcal{X})\) that minimizes \(\ell(f)\). If there is more than one such minimizer, select a bad one if there is one. The losses for \(f_{n}\) are non-increasing and between 0 and 1, because the set of functions computable by \(\mathsf{NN}_{n}\) is monotonically increasing with \(n\):

\[1\geq\ell(f_{1})\geq\ell(f_{2})\geq\ell(f_{3})\ldots\geq 0.\]

For any \(n\), we claim that if there is an \(n\)-node NN \(f_{n}\in\mathsf{NN}_{n}(\mathcal{X})\) which minimizes \(\ell(f)\) that is not \((\mathcal{C},\alpha)\)-MC, then it must be the case that,

\[\ell(f_{n+k+3})<\ell(f_{n})-\alpha^{2}. \tag{3}\]

This is because: (1) by definition of \((\mathcal{C},\alpha)\)-MC, there must be a auditor \(c\in\mathcal{C}\) with

\[|\mathbb{E}[c(x,f_{n}(x))(y-f_{n}(x))]|=\beta>\alpha\]

and (2) by Lemma 3.1 we can combine \(f_{n},c\) to form a NN with \((n+k+3)\) nodes where the loss drops by \(\beta^{2}>\alpha^{2}\), implying Equation (3).

To complete the proof, partition the integers based on their residues mod \(b=k+3\). In each partition, there will be \(<1/\alpha^{2}\) drops in \(\ell(f_{n})\) of magnitude \(\alpha\) since \(\ell(f_{n})\in[0,1]\), and each bad size corresponds to a drop of magnitude at least \(\alpha^{2}\) by Equation (3). 

### Regularization

If one is worried about avoiding a "bad" size, then one can pick the size randomly from a large range, since there are relatively few bad sizes. Alternatively, one can use the natural regularization approach discussed in the introduction. Note that if one applies a regularization of \(1/N\) times the number of nodes, the optimum will never have more than \(N\) nodes because the loss of a NN with 0 nodes is at most 1. In this case, one guarantees \((\mathcal{C},\alpha)\)-MC with certainty.

**Theorem 3.3** (Size-regularized NNs.).: _Let \(\mathcal{D}\) be a distribution over \(\mathcal{X}\times[0,1]\), and let \(k\in\mathbb{N},\alpha\in(0,1]\) and \(N=(k+3)/\alpha^{2}\). Let \(\hat{f}\) be any minimizer of:_

\[\hat{f}\in\operatorname*{arg\,min}_{n\leq N;\,\hat{f}\in\mathsf{NN}_{n}( \mathcal{X})}\ell(f)+\frac{n}{N}. \tag{4}\]

_Then \(\hat{f}\) is \((\mathcal{C},\alpha)\)-MC for \(\mathcal{C}=\mathsf{NN}_{k}(\mathcal{X}\times[0,1])\)._

Proof.: The size-0 NN that computes the constant 0 function has loss at most 1 (since the labels are in \(\{0,1\}\)). So we may assume that the optimization was carried out over all \(n\), as any solution to the full optimization will have \(n\leq N\).
Say the minimum occurs at \(\hat{n},\hat{f}\), so \(\hat{f}\) consists of \(\hat{n}\) nodes. Suppose the theorem were false, i.e., there exists some \(c\in\mathsf{NN}_{k}(\mathcal{X}\times[0,1])\) with at most \(k\) nodes such that

\[\beta:=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[c\big{(}x,\hat{f }(x)\big{)}\cdot\big{(}y-\hat{f}(x)\big{)}\right]\]

satisfies \(|\beta|>\alpha\). By Lemma 3.1, for

\[h(x):=\operatorname{clip}_{[0,1]}\left(\hat{f}(x)+\beta c\big{(}x,\hat{f}(x) \big{)}\right),\]

we have,

\[\ell(h)\leq\ell(\hat{f})-\beta^{2}<\ell(\hat{f})-\alpha^{2}=\ell(\hat{f})- \frac{k+3}{N},\]

where the last equality is by the choice of \(N\). Again \(h\in\mathsf{NN}_{\hat{n}+k+3}\). This contradicts the optimality of \(\hat{f}\) for Eq. (4), since

\[\ell(h)+\frac{1}{N}(\hat{n}+k+3)<\ell(\hat{f})+\frac{1}{N}\hat{n}.\]

This gives a way of finding a \(n\leq(k+3)/\alpha^{2}\)-node NN that is \(\alpha\)-MC with respect to \(k\)-node NNs, since \(N=(k+3)/\alpha^{2}\).

Finite training sets.If one has a training set consisting of \(m\) examples iid from \(\mathcal{D}\), a natural approach is to minimize training loss. If \(m\) is sufficiently large compared to the number of NN parameters, which is polynomial in \(n\), generalization bounds guarantee every \(f\in\mathsf{NN}_{n}(\mathcal{X})\) will have training loss close to its true loss \(\ell(f)\), and thus any \(\hat{f}_{n}\) which minimizes training error (still ignoring computation time) will have, say, \(\ell(\hat{f}_{n})\leq\min_{\mathsf{NN}_{n}(\mathcal{X})}\ell(f)+\epsilon\) for \(\epsilon=O(\alpha^{2})\). This can, in turn, be used with the above theorems to show that, outside a set of \(O(k/\alpha^{2})\) NN sizes, all NNs that are optimal on the training set will be \(O(\alpha)\)-MC with respect to \(k\)-node NNs. While such an analysis would be straightforward, we find it unsatisfactory given the fact that current generalization bounds, though correct, seem to be too loose to capture the performance of many NN learning algorithms in practice (e.g. (Zhang et al., 2021; Nagarajan and Kolter, 2019)). However, our results above may be relevant in settings where generalization is guaranteed -- for example, when models are trained using Stochastic Gradient Descent (SGD) for only one-epoch (one pass through the training data). In this case, the learning algorithm can be thought of as optimizing via SGD directly on the population loss, without considering a finite train set. If we heuristically believe that, when run for long enough, the optimization reaches close to a population loss minima within the architecture family, then our results imply most resulting minima will also be multicalibrated. Moreover, the one-epoch setting may not be far from reality, since most modern large language models are indeed trained for only one epoch (Brown et al., 2020; Biderman et al., 2023), and there is evidence that generalization in the multi-epoch setting can be understood via the one-epoch setting (Nakkiran et al., 2021).

## 4 A lower bound

We would like to understand the tightness of the analysis we have presented. Unfortunately, this is challenging due to the complex structure of NNs. Instead, this section provides some evidence of the tightness of our analysis at least _using our current methods_. To do this, we consider another natural class of functions namely \(k\)_-juntas_ and a weaker notion of multigroup fairness called multiaccuracy, to which our analysis applies. In this setting, we show a sharp result, proving that our bounds are tight up to constant factors.
The class of _Juntas_, functions that depend on a small subset of inputs, has been well studied in computational learning theory (Mossel et al., 2004; Fischer et al., 2004). In this section, we show that Juntas satisfy a similar property to NNs in that, for most sizes, minimizing loss for Juntas also implies MA with respect to smaller Juntas. We also prove a _lower bound_ for showing that our bounds are tight up to constant factors.

For our results in this section, we choose the domain \(\mathcal{X}\) to be the Boolean cube \(\{-1,1\}^{m}\) for a dimension \(m\in\mathbb{Z}_{>0}\). That is, every \(x\in\mathcal{X}\) can be written as \(x=(x_{1},\ldots,x_{m})\) where \(x_{i}\in\{-1,1\}\) for every \(i=1,\ldots,m\). For a positive integer \(k\) and a function \(f:\mathcal{X}\to[0,1]\), we say \(f\) is a _\(k\)-junta_ if there exist \(i_{1},\ldots,i_{k}\in\{1,\ldots,m\}\) and \(g:\{-1,1\}^{k}\to[0,1]\) such that \(f(x)=g(x_{i_{1}},\ldots,x_{i_{k}})\) for every \(x\in\mathcal{X}\). We say a function \(f:\mathcal{X}\to[0,1]\) is a \(0\)-junta if \(f\) is a constant function. We use \(\mathcal{J}_{k}(\mathcal{X})\) to denote the family of \(k\)-juntas over domain \(\mathcal{X}\).

The following theorem is analogous to Theorem 3.2:

**Theorem 4.1**.: _Let \(\mathcal{D}\) be a distribution over \(\mathcal{X}\times\mathcal{Y}\), where \(\mathcal{X}=\{-1,1\}^{m}\) for a positive integer \(m\) and \(\mathcal{Y}=\{0,1\}\). Let \(k\in\mathbb{Z}_{>0}\) and \(\alpha\in(0,1]\) be parameters. Then for all but at most \(k/\alpha^{2}\) nonnegative integers \(n\in\mathbb{Z}_{\geq 0}\), for every minimizer \(\hat{f}_{n}\):_

\[\hat{f}_{n}\in\operatorname*{arg\,min}_{f\in\mathcal{J}_{n}(\mathcal{X})}\ell (f),\]

\(\hat{f}_{n}\) _is \((\mathcal{C},\alpha)\)-MA with respect to \(\mathcal{C}=\mathcal{J}_{k}(\mathcal{X})\)._

The proof works exactly like the proof of Theorem 3.2 using the following observation. For \(f\in\mathcal{J}_{n}(\mathcal{X}),c\in\mathcal{J}_{k}(\mathcal{X})\), and \(\beta\in\mathbb{R}\), define function \(h:\mathcal{X}\to[0,1]\) as

\[h(x)=\operatorname{clip}_{[0,1]}(f(x)+\beta c(x)),\]

then \(h\in\mathcal{J}_{n+k}(\mathcal{X})\). The following theorem gives a lower bound that matches Theorem 4.1 up to a constant factor.

**Theorem 4.2**.: _For every \(k\in\mathbb{Z}_{>0}\) and every \(\alpha\in(0,1/(6\pi)]\), there exist \(m\in\mathbb{Z}_{>0}\), a distribution \(\mathcal{D}\) over \(\mathcal{X}\times\mathcal{Y}\) with \(\mathcal{X}=\{-1,1\}^{m}\) and \(\mathcal{Y}=\{0,1\}\), and at least \(k/(54\pi^{2}\alpha^{2})\) distinct nonnegative integers \(n\) such that any model \(f_{n}\in\mathcal{J}_{n}(\mathcal{X})\) is not \((\mathcal{C},\alpha)\)-MA with respect to \(\mathcal{C}=\mathcal{J}_{k}(\mathcal{X})\)._

Key to our proof of Theorem 4.2 is the _majority_ function. For an odd positive integer \(k\), we define the majority function \(\mathsf{MAJ}:\{-1,1\}^{k}\to\{-1,1\}\) such that for every \((x_{1},\ldots,x_{k})\in\{-1,1\}^{k}\), \(\mathsf{MAJ}(x_{1},\ldots,x_{k})=1\) if \(x_{1}+\cdots+x_{k}>0\), and \(\mathsf{MAJ}(x_{1},\ldots,x_{k})=-1\) otherwise. The following lemma about majority functions follows from standard noise sensitivity bounds (see O'Donnell, 2014). We provide a proof for completeness.

**Lemma 4.3**.: _For any odd positive integers \(m\) and \(k\) satisfying \(k\leq m\),_

\[\mathbb{E}[\mathsf{MAJ}(x_{1},\ldots,x_{k})\mathsf{MAJ}(x_{1},\ldots,x_{m})]> \frac{2}{\pi}\cdot\sqrt{\frac{k}{m}},\]

_where the expectation is over \((x_{1},\ldots,x_{m})\) drawn uniformly at random from \(\{-1,1\}^{m}\).2_

Footnote 2: The constant \(2/\pi\) cannot be improved because in the limit where \(k,m\to\infty,\sqrt{k/m}\to\rho\in(0,1)\), using the central limit theorem one can show that \(\mathbb{E}[\mathsf{MAJ}(x_{1},\ldots,x_{k})\mathsf{MAJ}(x_{1},\ldots,x_{m})] \to(2/\pi)\arcsin\rho\). Also, it is easy to show that \(\mathbb{E}[f(x_{1},\ldots,x_{k})\mathsf{MAJ}(x_{1},\ldots,x_{m})]\) is maximized when \(f=\mathsf{MAJ}\) among all \(f:\{-1,1\}^{k}\to[-1,1]\) (see e.g. Gopalan et al., 2008, Lemma 13).
Using the majority function, we define a distribution \(\mathcal{D}\) over \(\{-1,1\}^{m}\times\{0,1\}\) for any odd positive integer \(m\) as follows. We first draw \(x\in\{-1,1\}^{m}\) uniformly at random and then set

\[y=\frac{1}{2}(1+\mathsf{MAJ}(x))\in\{0,1\}.\]

We define \(\mathcal{D}\) to be the distribution of \((x,y)\). Lemma 4.3 allows us to prove the following lemma about the distribution \(\mathcal{D}\), which we then use to prove Theorem 4.2.

**Lemma 4.4**.: _Let \(k,m\) be odd positive integers satisfying \(k\leq m\). Define \(\mathcal{X}:=\{-1,1\}^{m}\) and define distribution \(\mathcal{D}\) as above. Let \(\alpha>0\) be a parameter satisfying_

\[\alpha\leq\frac{1}{3\pi}\cdot\sqrt{\frac{k}{m}}. \tag{5}\]

_Then any function \(f\in\mathcal{J}_{m-k}(\{-1,1\}^{m})\) is not \((\mathcal{C},\alpha)\)-MA with respect to \(\mathcal{C}=\mathcal{J}_{k}(\mathcal{X})\)._

Proof.: We first show that for any function \(f\in\mathcal{J}_{m-k}(\{-1,1\}^{m})\), there exist \(i_{1},\ldots,i_{k}\in\{1,\ldots,m\}\) such that

\[\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))\mathsf{MAJ}(x_{i_{1}},\ldots,x_{i_ {k}})]>\frac{1}{\pi}\cdot\sqrt{\frac{k}{m}}. \tag{6}\]

By the definition of \(f\in\mathcal{J}_{m-k}(\mathcal{X})\), there exist \(j_{1},\ldots,j_{m-k}\in\{1,\ldots,m\}\) and \(g:\{-1,1\}^{m-k}\) such that

\[f(x)=g(x_{j_{1}},\ldots,g_{j_{m-k}})\quad\text{for every $x\in\mathcal{X}$}.\]

Now we choose distinct \(i_{1},\ldots,i_{k}\in\{1,\ldots,m\}\setminus\{j_{1},\ldots,j_{m-k}\}\). We have

\[\mathbb{E}_{(x,y)\sim\mathcal{D}}[f(x)\mathsf{MAJ}(x_{i_{1}},\ldots,x_{i_{k}}) ]=\mathbb{E}[g(x_{j_{1}},\ldots,g_{j_{m-k}})\mathsf{MAJ}(x_{i_{1}},\ldots,x_{i _{k}})]=0, \tag{7}\]

where the last equation holds because \((x_{i_{1}},\ldots,x_{i_{k}})\) is independent from \((x_{j_{1}},\ldots,x_{j_{m-k}})\). By Lemma 4.3 and our choice of distribution \(\mathcal{D}\),

\[\mathbb{E}_{(x,y)\sim\mathcal{D}}[y\,\mathsf{MAJ}(x_{i_{1}},\ldots,x_{i_{k}}) ]>\frac{1}{\pi}\cdot\sqrt{\frac{k}{m}}. \tag{8}\]

Combining (7) and (8) proves (6). Now we show that \(f\) is _not_\((\mathcal{C},\alpha)\)-MA with respect to \(\mathcal{C}=\mathcal{J}_{k}(\mathcal{X})\). Assume for the sake of contradiction that \(f\) is \((\mathcal{C},\alpha)\)-MA. Then for the function \(c:\mathcal{X}\to[0,1]\) such that \(c(x)=\frac{1}{2}(1+\mathsf{MAJ}(x_{i_{1}},\ldots,x_{i_{k}}))\), it holds that

\[\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))c(x)]\leq\alpha.\]

Also,

\[\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))]\geq-\alpha.\]

Therefore,

\[\mathbb{E}_{(x,y)\sim\mathcal{D}}[(y-f(x))\mathsf{MAJ}(x_{i_{1}},\ldots,x_{i _{k}})]=\mathbb{E}[(y-f(x))(2c(x)-1)]\leq 3\alpha.\]

This is a contradiction with (6) due to our assumption (5). 

We are now ready to prove our lower bound Theorem 4.2.
Proof of Theorem 4.2.: For any positive integer \(k\), define \(k_{1}\) to be the largest odd integer that does not exceed \(k\). It is easy to verify that \(k_{1}\geq k/2>0\). For any \(\alpha\in(0,1/(6\pi)]\), choose \(m\) to be the largest odd integer smaller than \(k_{1}/(9\pi^{2}\alpha^{2})\). Our assumption that \(\alpha\leq 1/(6\pi)\) ensures that \(k_{1}/(9\pi^{2}\alpha^{2})\geq 4k_{1}\), and thus \(m\geq 3k_{1}\) and \(m\geq k_{1}/(18\pi^{2}\alpha^{2})\). Moreover, our choice of \(m\) ensures that

\[\alpha\leq\frac{1}{3\pi}\sqrt{\frac{k_{1}}{m}}.\]

By Lemma 4.4, for \(\mathcal{X}=\{-1,1\}^{m}\) and \(\mathcal{Y}=\{0,1\}\) there exists a distribution \(\mathcal{D}\) over \(\mathcal{X}\times\mathcal{Y}\) such that for every nonnegative integer \(n=0,\ldots,m-k_{1}\), any model \(f_{n}\in\mathcal{J}_{n}(\mathcal{X})\) is _not_\((\mathcal{C},\alpha)\)-MA with respect to \(\mathcal{C}=\mathcal{J}_{k_{1}}(\mathcal{X})\). Since \(\mathcal{J}_{k_{1}}(\mathcal{X})\subseteq\mathcal{J}_{k}(\mathcal{X})\), any \(f_{n}\in\mathcal{J}_{n}(\mathcal{X})\) is also _not_\((\mathcal{C},\alpha)\)-MA with respect to \(\mathcal{C}=\mathcal{J}_{k}(\mathcal{X})\). The number of such integers \(n\) is

\[m-k_{1}+1\geq 2m/3\geq(2/3)(k_{1}/(18\pi^{2}\alpha^{2}))=k_{1}/(27\pi^{2} \alpha^{2})\geq k/(54\pi^{2}\alpha^{2}).\qed\]

## 5 Related Work

The notion of multicalibration for multigroup fairness was introduced in Hebert-Johnson et al. (2018), see also Kearns et al. (2017), Kleinberg et al. (2017). This notion has proved to be unexpectedly rich, with connections to several other areas. The work of Dwork et al. (2021) relates it to indistinguishability, while Kim et al. (2022) connects it to domain adaptation. A line of work on omniprediction Gopalan et al. (2022); Gu et al. (2023); Hu et al. (2022) has shown that multicalibration for a class \(\mathcal{C}\) implies strong loss minimization guarantees when compared against benchmarks from \(\mathcal{C}\). This is the opposite direction to the one we study here: it shows settings where loss minimization results from multicalibration. A more recent work Gopalan et al. (2023) in fact shows an equivalence between multicalibration and certain swap loss minimization problems. Without getting into details, the model of loss minimization is inspired by internal regret in online learning, and is different from the standard notion that we study here.

Perhaps the most related work to ours is that of Liu et al. (2019) and Barocas et al. (2019, Chapter 3), who provide MC guarantees for classifiers whose loss is near the absolute minimum possible loss of Bayes-optimal predictors, in the case of squared error \(f(x)=\mathbb{E}[y\mid x]\).

Finally, there is a long history studying calibration (not MC) which can be viewed as a special case of MC where the groups are defined by \(f(x)\) only, i.e., \(c(f(x))\), ignoring the features \(x\) itself. In particular, a set of practical studies that have found that large NNs are often calibrated out "of the box" despite being optimized solely for loss Minderer et al. (2021); Hendrycks et al. (2020); Karandikar et al. (2021); Desai and Durrett (2020); Carrell et al. (2022). A concurrent work of Blasiok et al. (2022) attempts to explain this phenomenon by proving that: functions whose loss cannot be improved much by (a simpler) post-processing are exactly those that are close to calibrated. They then speculate that well-trained neural networks are likely to be loss-optimal in this sense, and thus calibrated. The present work can be seen as pursuing a similar line of reasoning, but in the more general setting of multicalibration.

The work of Kim et al. (2019) showed that the performance of image classifiers on demographic subgroups can be improved by ensuring multiaccuracy. We are not aware of experimental work measuring the degree of multicalibration for large neural networks on massive training sets. There are numerous works on the representation ability of NNs Hornik et al. (1989) and about their accuracy and generalization (e.g., Zhang et al., 2021; Nagarajan and Kolter, 2019), too large to survey here.

## 6 Discussion

We start by discussing some limitations of our work. We do not provide any guidance on selecting \(k\), which is an important theoretical and practical issue. Second, there is a blowup in the NN size \(n\) required
to achieve MC with respect to NNs of size \(k\). Also, the model we study is highly unrealistic in that we assume that we have unbounded training data and computational resources at training time. Even though current pre-training efforts do involve massive amounts of data and compute, it is not clear that they are or will ever approach what could be done in this limit.

Nonetheless, we feel that it still may be useful to understand the nature of different classifier representations and the tensions that they face. First of all, one conclusion of this work is that one can achieve MC with NNs-as a representation they are not limited in the same way as some other classifiers. In particular, simpler classifiers (which may enjoy other benefits such as interpretability) may face an inherent tension between accuracy and calibration overall and among different groups.

If one leads a group of practitioners training NNs and one is concerned about multicalibration, our work suggests that incentivizing them to simply minimize loss may, to some extent, be aligned with MC. This is formal in the sense of Lemma 3.1: if one can identify a classifier for which the current predictor is miscalibrated, then one can further reduce the loss, escaping a local minimum if the classifier was trained with a local optimization algorithm. But this may naturally happen if they were incentivized to minimize loss. If it is not happening naturally, such a "check" could be suggested and it would be entirely compatible with the group's loss incentives.

Future work.It would be interesting to empirically measure whether NNs used in practice are multicalibrated. If so, this might be viewed as one additional benefit of their use over simpler models. If not, it would be interesting to understand the reasons- the gaps between theory and practice.

Another direction would be to prove a similar result for other classes of hypotheses. The key property of neural nets that we use is that the post-processing required to update the predictor can be incorporated into a predictor of larger size. It is not hard to see that other classes such as decision trees and branching programs (parametrized by size) do have this property. But they are not known to have provable algorithms for squared loss minimization. In contrast linear models do admit efficient loss minimization. But they are not powerful enough to be closed under the kinds of post-processing that multicalibration requires. Moreover, they cannot express the kind of predicates that are interesting for multicalibration, such as \(x\in S\) and \(f(x)=0.1\).

An intriguing question is whether there is a hypothesis class that is indeed powerful enough to give interesting multicalibration guarantees and is closed under post-processing, but which admits efficient loss minimization. It is also possible that there exists a no-free-lunch flavor of result which rules out such a possibility. We leave formalizing and proving such results to future work.

Risks.We conclude on a cautionary note. There is a risk that this and other similar work will be misinterpreted as "fairness/multicalibration comes for free if you just optimize loss in DNNs" but that is not a valid conclusion for multiple reasons. First of all, multicalibration is only one notion of fairness. It is particularly applicable in settings where and the groups of interest are identifiable from \(x\). Multicalibration cannot protect groups of concern that are not identifiable from \(x\), e.g., race is a complex feature that may not be explicitly coded or perfectly computable from existing features, and the protection gets weaker for smaller groups.

If a practitioner was given an _explicit_ set of protected groups whose accuracy is to be prioritized, they ought to consider all steps in the machine learning pipeline and not just optimization: they might adjust their architectures, collect additional data, or expand the feature set so as to increase the family of protected subgroups and performance on those groups. For instance, explicitly investigating multicalibration may lead to discovering certain groups on which it is hard to achieve good calibration, which requires a different type of learning architecture, better datasets or more informative features.
## Acknowledgments

We thank Ryan O'Donnell and Rocco Servedio for suggesting the current proof of Lemma 4.3. We also thank Barry-John Theobald for comments on an early draft. Part of this work was performed while LH was interning at Apple. LH is also supported by Moses Charikar's and Omer Reingold's Simons Investigators awards, Omer Reingold's NSF Award IIS-1908774, and the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.

JB is supported by a Junior Fellowship from the Simons Society of Fellows.
