# Loss minimization yields multicalibration
for large neural networks

Jarosław Błasiok
Columbia University  Parikshit Gopalan
Apple  Lunjia Hu
Stanford University  Adam Tauman Kalai
Microsoft Research  Preetum Nakkiran
Apple

###### 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):=\mathop{\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 Hébert-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; Hébert-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{|}\mathop{\mathbb{E}}\nolimits_{x,y}\left[c\bigl{(}x,f(x)\bigr{)}\cdot\bigl{(}y-f(x)\bigr{)}\right]\Big{|}\leq\alpha.$

When $\mathcal{C}$ is clear from context, we say that $f$ is $\alpha$-MC for
brevity. 111The 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 (Hébert-Johnson et al., 2018; Gopalan et al., 2022b)
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
$\mathop{\mathbb{E}}[y]\approx\mathop{\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 (Hébert-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{|}\mathop{\mathbb{E}}\nolimits_{x,y}\left[c(x)\cdot\bigl{(}y-f(x)\bigr{)}\right]\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 lerge 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)=\mathop{\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., 2022a, 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.

###  1.1 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 multicalibrated. 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 Hébert-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. (2022a) 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 multicalibrated 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):=\mathop{\mathbb{E}}_{\mathcal{D}}\left[\bigl{(}y-f(x)\bigr{)}^{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}~{}~{}\mathrm{clip}_{[0,1]}(z):=\mathsf{ReLU}(z-\mathsf{ReLU}(z-1))=\max(0,\min(1,z))\in[0,1].$
(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,

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

Then $h(x):=\mathrm{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)=\mathrm{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{)}.\\\ $ (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 $\mathsf{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)=\mathrm{clip}_{[0,1]}(g(x))$. Then,

$\displaystyle\ell(g)$ $\displaystyle=\mathop{\mathbb{E}}\left[(y-f(x)-\beta
c(x,f(x)))^{2}\right]$
$\displaystyle=\mathop{\mathbb{E}}\left[(y-f(x))^{2}-2\beta
c(x,f(x))(y-f(x))+\beta^{2}c^{2}(x,f(x))\right]$
$\displaystyle=\ell(f)-2\beta\mathop{\mathbb{E}}\left[c(x,f(x))(y-f(x))\right]+\beta^{2}\mathop{\mathbb{E}}\left[c^{2}(x,f(x))\right]$
$\displaystyle=\ell(f)-2\beta^{2}+\beta^{2}\mathop{\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\mathop{\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}.$ (3)

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

$\left|\mathop{\mathbb{E}}[c(x,f_{n}(x))(y-f_{n}(x))]\right|=\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).
∎

###  3.1 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\mathop{\arg\min}_{n\leq
N;f\in\mathsf{NN}_{n}(\mathcal{X})}\ell(f)+\frac{n}{N}.$ (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:=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[c\bigl{(}x,\hat{f}(x)\bigr{)}\cdot\bigl{(}y-\hat{f}(x)\bigr{)}\right]$

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

$h(x):=\mathrm{clip}_{[0,1]}\left(\hat{f}(x)+\beta
c\bigl{(}x,\hat{f}(x)\bigr{)}\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\mathop{\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)=\mathrm{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$,

$\mathop{\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}$.222The 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
$\mathop{\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
$\mathop{\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}}.$ (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

$\mathop{\mathbb{E}}\nolimits_{(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}}.$
(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

$\mathop{\mathbb{E}}\nolimits_{(x,y)\sim\mathcal{D}}[f(x){\mathsf{MAJ}}(x_{i_{1}},\ldots,x_{i_{k}})]=\mathop{\mathbb{E}}[g(x_{j_{1}},\ldots,g_{j_{m-k}}){\mathsf{MAJ}}(x_{i_{1}},\ldots,x_{i_{k}})]=0,$
(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}$,

$\mathop{\mathbb{E}}\nolimits_{(x,y)\sim\mathcal{D}}[y\,{\mathsf{MAJ}}(x_{i_{1}},\ldots,x_{i_{k}})]>\frac{1}{\pi}\cdot\sqrt{\frac{k}{m}}.$
(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

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

Also,

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

Therefore,

$\mathop{\mathbb{E}}\nolimits_{(x,y)\sim\mathcal{D}}[(y-f(x)){\mathsf{MAJ}}(x_{i_{1}},\ldots,x_{i_{k}})]=\mathop{\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
Hébert-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., 2022a, 2023a; 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., 2023b) 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)=\mathop{\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 Błasiok 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 (e.g., 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.

## References

  * Barocas et al. [2019] Solon Barocas, Moritz Hardt, and Arvind Narayanan.  _Fairness and Machine Learning: Limitations and Opportunities_.  fairmlbook.org, 2019.  http://www.fairmlbook.org.
  * Biderman et al. [2023] Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al.  Pythia: A suite for analyzing large language models across training and scaling.  _arXiv preprint arXiv:2304.01373_ , 2023.
  * Błasiok et al. [2022] Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran.  When loss minimization yields calibration for deep neural networks.  _In preparation_ , 2022.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, …, and Dario Amodei.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Carrell et al. [2022] Annabelle Carrell, Neil Mallinar, James Lucas, and Preetum Nakkiran.  The calibration generalization gap.  _arXiv preprint arXiv:2210.01964_ , 2022.
  * Chowdhery et al. [2022] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, …, and Noah Fiedel.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.  URL https://arxiv.org/abs/2204.02311.
  * Deng et al. [2023] Zhun Deng, Cynthia Dwork, and Linjun Zhang.  Happymap : A generalized multicalibration method.  In Yael Tauman Kalai, editor, _14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA_ , volume 251 of _LIPIcs_ , pages 41:1–41:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.  doi: 10.4230/LIPIcs.ITCS.2023.41.  URL https://doi.org/10.4230/LIPIcs.ITCS.2023.41.
  * Desai and Durrett [2020] Shrey Desai and Greg Durrett.  Calibration of pre-trained transformers.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 295–302, 2020.
  * Dwork et al. [2021] 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.  URL https://arxiv.org/abs/2011.13426.
  * Dwork et al. [2022] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona.  Beyond bernoulli: Generating random outcomes that cannot be distinguished from nature.  In _The 33rd International Conference on Algorithmic Learning Theory_ , 2022.
  * Fischer et al. [2004] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky.  Testing juntas.  _Journal of Computer and System Sciences_ , 68(4):753–787, 2004.  URL https://www.sciencedirect.com/science/article/pii/S0022000003001831.  Special Issue on FOCS 2002.
  * Gopalan et al. [2008] Parikshit Gopalan, Adam Tauman Kalai, and Adam R. Klivans.  Agnostically learning decision trees.  In _Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing_ , STOC ’08, page 527–536, 2008.
  * Gopalan et al. [2022a] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder.  Omnipredictors.  In _Innovations in Theoretical Computer Science (ITCS’2022)_ , 2022a.  URL https://arxiv.org/abs/2109.05389.
  * Gopalan et al. [2022b] Parikshit Gopalan, Michael P. Kim, Mihir Singhal, and Shengjia Zhao.  Low-degree multicalibration.  In _Conference on Learning Theory, 2-5 July 2022, London, UK_ , volume 178 of _Proceedings of Machine Learning Research_ , pages 3193–3234. PMLR, 2022b.
  * Gopalan et al. [2022c] Parikshit Gopalan, Omer Reingold, Vatsal Sharan, and Udi Wieder.  Multicalibrated partitions for importance weights.  In _International Conference on Algorithmic Learning Theory, 29-1 April 2022, Paris, France_ , volume 167 of _Proceedings of Machine Learning Research_ , pages 408–435. PMLR, 2022c.
  * Gopalan et al. [2023a] Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder.  Loss Minimization Through the Lens Of Outcome Indistinguishability.  In Yael Tauman Kalai, editor, _14th Innovations in Theoretical Computer Science Conference (ITCS 2023)_ , volume 251 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 60:1–60:20, Dagstuhl, Germany, 2023a. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-95977-263-1.  doi: 10.4230/LIPIcs.ITCS.2023.60.  URL https://drops.dagstuhl.de/opus/volltexte/2023/17563.
  * Gopalan et al. [2023b] Parikshit Gopalan, Michael Kim, and Omer Reingold.  Characterizing notions of omniprediction via multicalibration.  In _under submission_ , 2023b.  URL https://arxiv.org/abs/2302.06726.
  * Hébert-Johnson et al. [2018] Ú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.
  * Hendrycks* et al. [2020] Dan Hendrycks*, Norman Mu*, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan.  Augmix: A simple method to improve robustness and uncertainty under data shift.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=S1gmrxHFvB.
  * Hornik et al. [1989] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Hu et al. [2022] Lunjia Hu, Inbal Livni-Navon, Omer Reingold, and Chutong Yang.  Omnipredictors for constrained optimization.  _arXiv preprint arXiv:2209.07463_ , 2022.
  * Jung et al. [2020] Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra.  Moment multicalibration for uncertainty estimation.  _arXiv preprint arXiv:2008.08037_ , 2020.
  * Karandikar et al. [2021] Archit Karandikar, Nicholas Cain, Dustin Tran, Balaji Lakshminarayanan, Jonathon Shlens, Michael C Mozer, and Becca Roelofs.  Soft calibration objectives for neural networks.  _Advances in Neural Information Processing Systems_ , 34:29768–29779, 2021.
  * Kearns et al. [2017] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu.  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.  _arXiv preprint arXiv:1711.05144_ , 2017.
  * Kim et al. [2019] 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 et al. [2022] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold.  Universal adaptability: Target-independent inference that competes with propensity scoring.  _Proceedings of the National Academy of Sciences_ , 119(4), 2022.
  * Kleinberg et al. [2017] 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.
  * Liu et al. [2019] Lydia T Liu, Max Simchowitz, and Moritz Hardt.  The implicit fairness criterion of unconstrained learning.  In _International Conference on Machine Learning_ , pages 4051–4060. PMLR, 2019.
  * Mansour and McAllester [2002] Yishay Mansour and David McAllester.  Boosting using branching programs.  _Journal of Computer and System Sciences_ , 64(1):103–112, 2002.
  * Minderer et al. [2021] Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic.  Revisiting the calibration of modern neural networks.  _Advances in Neural Information Processing Systems_ , 34:15682–15694, 2021.
  * Mossel et al. [2004] Elchanan Mossel, Ryan O’Donnell, and Rocco A. Servedio.  Learning functions of k relevant variables.  _Journal of Computer and System Sciences_ , 69(3):421–434, 2004.  ISSN 0022-0000.  doi: https://doi.org/10.1016/j.jcss.2004.04.002.  URL https://www.sciencedirect.com/science/article/pii/S0022000004000418.  Special Issue on STOC 2003.
  * Nagarajan and Kolter [2019] Vaishnavh Nagarajan and J Zico Kolter.  Uniform convergence may be unable to explain generalization in deep learning.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Nakkiran et al. [2021] Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi.  The deep bootstrap framework: Good online learners are good offline generalizers.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=guetrIHLFGI.
  * O’Donnell [2014] Ryan O’Donnell.  _Analysis of boolean functions_.  Cambridge University Press, 2014.
  * Ramesh et al. [2022] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents, 2022\.  URL https://arxiv.org/abs/2204.06125.
  * Titsworth [1962] Robert C Titsworth.  _Correlation properties of cyclic sequences_.  PhD thesis, California Institute of Technology, 1962.
  * Zhang et al. [2021] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning (still) requires rethinking generalization.  _Communications of the ACM_ , 64(3):107–115, 2021\.

##  Appendix A Correlation between majority functions

We restate and prove Lemma 4.3. See 4.3

###### Proof.

For any $S\subseteq\\{1,\ldots,m\\}$, we define

$\displaystyle\widehat{\mathsf{MAJ}}_{k}(S):=\mathop{\mathbb{E}}[{\mathsf{MAJ}}(x_{1},\ldots,x_{k})\prod_{i\in
S}x_{i}].$

By the Plancherel theorem,

$\mathop{\mathbb{E}}[{\mathsf{MAJ}}(x_{1},\ldots,x_{k}){\mathsf{MAJ}}(x_{1},\ldots,x_{m})]=\sum_{S\subseteq\\{1,\ldots,m\\}}\widehat{\mathsf{MAJ}}_{k}(S)\widehat{\mathsf{MAJ}}_{m}(S).$

It is easy to verify that if $S$ is not a subset of $\\{1,\ldots,k\\}$, then
$\widehat{\mathsf{MAJ}}_{k}(S)=0$. Also, by calculating the Fourier
coefficients of the majority function [Titsworth, 1962] [see O’Donnell, 2014,
Section 5.3], we have
$\widehat{\mathsf{MAJ}}_{k}(S)\widehat{\mathsf{MAJ}}_{m}(S)\geq 0$ for any
$S\subseteq\\{1,\ldots,k\\}$. Therefore,

$\displaystyle\mathop{\mathbb{E}}[{\mathsf{MAJ}}(x_{1},\ldots,x_{k}){\mathsf{MAJ}}(x_{1},\ldots,x_{m})]$
$\displaystyle\geq\sum_{i=1}^{k}\widehat{\mathsf{MAJ}}_{k}(\\{i\\})\widehat{\mathsf{MAJ}}_{m}(\\{i\\})$
$\displaystyle=k\left(\genfrac{(}{)}{0.0pt}{1}{k-1}{(k-1)/2}/2^{k-1}\right)\left(\genfrac{(}{)}{0.0pt}{1}{m-1}{(m-1)/2}/2^{m-1}\right)$
$\displaystyle>k\sqrt{\frac{2}{\pi k}}\sqrt{\frac{2}{\pi m}}$
$\displaystyle=\frac{2}{\pi}\sqrt{\frac{k}{m}}.$

Here we use the fact that for any odd positive integer $k$,

$\genfrac{(}{)}{0.0pt}{1}{k-1}{(k-1)/2}/2^{k-1}=\frac{1\times
3\times\cdots\times(k-2)}{2\times
4\times\cdots\times(k-1)}=\sqrt{\frac{1}{k}\cdot\left(\frac{1}{2}\cdot\frac{3}{2}\cdot\frac{3}{4}\cdot\frac{5}{4}\cdot\cdots\cdot\frac{k-2}{k-1}\cdot\frac{k}{k-1}\right)}>\sqrt{\frac{1}{k}\cdot\frac{2}{\pi}},$

where the last inequality follows from the Wallis product formula for $\pi$. ∎


# A Frobenius integrability theorem for plane fields generated by
quasiconformal deformations

Slobodan N. Simić  Department of Mathematics and Statistics
San José State University
San Jose, CA 95192-0103<EMAIL_ADDRESS>
###### Abstract.

We generalize the classical Frobenius integrability theorem to plane fields of
class $C^{Q}$, a regularity class introduced by Reimann [Rei76] for vector
fields in Euclidean spaces. A $C^{Q}$ vector field is uniquely integrable and
its flow is a quasiconformal deformation. We show that an a.e. involutive
$C^{Q}$ plane field (defined in a suitable way) in $\mathbb{R}^{n}$ is
integrable, with integral manifolds of class $C^{1}$.

This work was partially supported by an SJSU Research, Scholarship, and
Creative Activity grant.

##  1\. Introduction

Frobenius’s integrability theorem is a fundamental result in differential
topology and gives a necessary and sufficient condition for a smooth plane
field (i.e., a distribution) to be tangent to a foliation. The result has been
generalized to Lipschitz plane fields in [Sim96] and [Ram07]. The goal of this
paper is to further extend Frobenius’s theorem to a regularity class weaker
than Lipschitz.

In [Rei76], Reimann introduced this new regularity class for vector fields and
showed that it is situated between Lipschitz and Zygmund. We will call the
vector fields in this class Q-vector fields, or of class $C^{Q}$ (see the
definition below). Reimann proved that a Q-vector field is uniquely integrable
and that each time $t$ map of its flow is quasiconformal. That is, the flow is
a quasiconformal deformation.

######  1 Definition.

A continuous vector field $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is
called a Q-vector field or of class $C^{Q}$ if

$\left\lVert f\right\rVert_{Q}=\sup\left|\frac{\langle
a,f(x+a)-f(x)\rangle}{|a|^{2}}-\frac{\langle
b,f(x+b)-f(x)\rangle}{|b|^{2}}\right|<\infty,$

where the supremum is taken over all $x\in\mathbb{R}^{n}$ and $|a|=|b|\neq 0$.

Let

$\left\lVert f\right\rVert_{Z}=\sup_{x,y\in\mathbb{R}^{n},y\neq
0}\frac{|f(x+y)+f(x-y)-2f(x)|}{|y|}$

and

$\left\lVert f\right\rVert_{L}=\sup_{x\neq y}\frac{|f(x)-f(y)|}{|x-y|}$

denote the Zygmund and Lipschitz seminorms of
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$.

The following properties were shown in [Rei76]:

  1. (1)

$\left\lVert f\right\rVert_{Z}\leq 4\left\lVert f\right\rVert_{Q}\leq
8\left\lVert f\right\rVert_{L}$. Thus every Lipschitz vector field is of class
$C^{Q}$. In dimension one, we have $\left\lVert f\right\rVert_{Z}=\left\lVert
f\right\rVert_{Q}.$

  2. (2)

If $f$ is a Q-vector field and $n\geq 2$, then $f$ is Frechét differentiable
a.e., its classical partial derivatives coincide with its weak derivatives and
are locally integrable.

  3. (3)

If $f:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is a Q-vector field and $n\geq 2$, then
the differential equation $\dot{x}=f(x)$ is uniquely integrable, and for every
$t$, the time $t$ map of its flow is $e^{c\left\lvert
t\right\rvert}$-quasiconformal, for some $c>0$.

Recall also:

######  2 Definition.

A homeomorphism $h:U\rightarrow V$ between open sets in $\mathbb{R}^{n}$ is
said to be $K$-quasiconformal ($K$-qc) if the following conditions are
satisfied:

  1. (a)

$h$ is absolutely continuous on almost every line segment in $U$ parallel to
the coordinate axes;

  2. (b)

$h$ is differentiable a.e.;

  3. (c)

$\frac{1}{K}\left\lVert Dh(x)\right\rVert^{n}\leq|\det Dh(x)|\leq
K\>m(Dh(x))^{n}$, for a.e. $x\in U$,

where, for a linear map $A$, $m(A)$ denotes the ”minimum norm” of $A$:

$m(A)=\min\\{|Av|:|v|=1\\}.$

The following characterization of Q-vector fields was proved in [Rei76] (cf.,
Theorem 3):

######  3 Theorem.

A continuous vector field $f:\mathbb{R}^{n}\to\mathbb{R}^{n}$ $(n\geq 2)$ is
of class $C^{Q}$ if and only if:

  * (a)

$f$ has distributional derivatives which are locally integrable.

  * (b)

$\left\lvert f(x)\right\rvert=O(\left\lvert x\right\rvert\log\left\lvert
x\right\rvert)$, as $\left\lvert x\right\rvert\to\infty$.

  * (c)

The anticonformal part $Sf$ of the derivative of $f$ is essentially bounded,
where

$Sf=\frac{1}{2}[Df+(Df)^{T}]-\frac{1}{n}\text{Trace}(Df)I.$

Let $X$ and $Y$ be vector fields of class $C^{Q}$. Since both are a.e.
differentiable, we can define their Lie bracket in the usual way:

$[X,Y]=DX(Y)-DY(X).$

Alternatively,

$[X,Y]u=X(Yu)-Y(Xu),$

for every $C^{\infty}$ function $u:\mathbb{R}^{n}\to\mathbb{R}$.

For a discussion of properties of the Lie bracket in the setting of rough
vector fields (i.e., Lipschitz and below), see [CT21].

### Plane fields of class $C^{Q}$

We come to the question of how to define a plane field of class $C^{Q}$. One
possibility is to use the usual route and say that $E$ is class $C^{Q}$ if it
is locally spanned by $C^{Q}$ vector fields. This leads to some technical
difficulties so instead we opt for a slightly stronger definition.

Let $E$ be a continuous $k$-dimensional plane field on $\mathbb{R}^{n}$ and
let $p\in\mathbb{R}^{n}$ be arbitrary. Let $H_{p}$ be an $(n-k)$-dimensional
coordinate plane in $\mathbb{R}^{n}$ such that $E_{p}$ is transverse to
$\\{p\\}\times H_{p}\subset T_{p}\mathbb{R}^{n}$. Continuity of $E$ implies
the existence of a neighborhood $U$ of $p$ such that for every $q\in U$,
$E_{q}$ remains transverse to $\\{q\\}\times H_{p}\subset
T_{q}\mathbb{R}^{n}$. Let $K_{p}$ be the $k$-dimensional coordinate subspace
of $\mathbb{R}^{n}$ complementary to $H_{p}$ and denote by $\pi_{p}$ the
orthogonal projection $\pi_{p}:\mathbb{R}^{n}\to K_{p}$. Observe that for
every $q\in U$, the restriction of $D_{q}\pi_{p}$ to $E_{q}$ is injective.

For an arbitrary vector field $X$ on $K_{p}$ with compact support in
$\pi_{p}(U)$, define a lift $\hat{X}$ of $X$ to $E$ by

$\hat{X}_{q}=(\left.D_{q}\pi_{p}\right|_{E_{q}})^{-1}(X_{\pi(q)}),$

for $q\in U$, and $\hat{X}_{q}=0$, otherwise. This vector field is a section
of $E$.

######  4 Definition.

A continuous $k$-dimensional plane field $E$ on $\mathbb{R}^{n}$ is a
$Q$-plane field or of class $C^{Q}$, if for every $p,U,H_{p}$, and $X$ as
above, the following holds: if $X$ is $C^{\infty}$ and has compact support,
then its lift $\hat{X}$ to $E$ (defined as above) is a Q-vector field.

Note that if $E$ is of class $C^{r}$ ($r\geq 1$) or Lipschitz, then lifts to
$E$ of $C^{\infty}$ vector fields are $C^{r}$ or Lipschitz, respectively.

######  5 Definition.

A plane field of class $C^{Q}$ is said to be involutive if for every two
$C^{Q}$ sections $X,Y$ of $E$, their Lie bracket $[X,Y]$ is an a.e. section of
$E$; i.e.,

$[X,Y]_{p}\in E_{p},$

for a.e. $p$.

Our main result is:

######  Frobenius Theorem.

Let $E$ be a $k$-dimensional plane field of class $C^{Q}$ on $\mathbb{R}^{n}$.
If $E$ is involutive, then $E$ is integrable, in the following sense. For
every $p\in\mathbb{R}^{n}$, there exists a cubic neighborhood
$U=(-\varepsilon,\varepsilon)^{n}$ of $\mathbf{0}$ in $\mathbb{R}^{n}$, a
neighborhood $V$ of $p$, and an almost everywhere differentiable homeomorphism

$\Phi:U\to V$

such that $\Phi$ maps slices
$(-\varepsilon,\varepsilon)^{k}\times\\{\text{const}\\}$ to integral manifolds
of $E$ in $V$. Writing $\Psi=\Phi^{-1}:p\mapsto x=(x_{1},\ldots,x_{n})$, we
have that the integral manifolds of $E$ in $V$ are the slices

$x_{k+1}=\text{\rm constant},\ldots,x_{n}=\text{\rm constant}.$

Every integral manifold of $E$ in $V$ lies in one of these slices and is of
class $C^{1}$.

##  2\. Preliminaries from the DiPerna-Lions-Ambrosio theory

We briefly recall some basic facts from the DiPerna-Lions-Ambrosio theory
(cf., [Amb04, dL89]) of regular Lagrangian flows, which generalize the notion
of a flow for “rough” vector fields. These will be needed in the proof of the
main result.

The basic idea of DiPerna-Lions-Ambrosio is to exploit (via the theory of
characteristics) the connection between the ODE $\dot{x}=X(x)$, where $X$ is a
vector field, and the associated transport PDE:

$\frac{\partial u}{\partial t}+X\cdot\nabla_{x}u=0,$

for a function $u=u(t,x)$.

A common definition of this generalized notion of a flow is the following.

######  6 Definition (Regular Lagrangian flows [CT21]).

We say that $\phi:\mathbb{R}\times\mathbb{R}^{n}\to\mathbb{R}^{n}$ is a
regular Lagrangian flow for a vector field $X$ on $\mathbb{R}^{n}$ if:

  1. (a)

For a.e. (with respect to the 1-dimensional Lebesgue measure) $t\in\mathbb{R}$
and every measure zero Borel set $A\subset\mathbb{R}^{n}$, the set
$\phi_{t}^{-1}(A)$ has $n$-dimensional Lebesgue measure zero, where
$\phi_{t}(x)=\phi(t,x)$.

  2. (b)

We have $\phi_{0}=\text{\rm identity}$ and for a.e. $x\in\mathbb{R}^{n}$,
$t\mapsto\phi_{t}(x)$ is an absolutely continuous integral curve of $X$, i.e.,

$\frac{d}{dt}\phi_{t}(x)=X(\phi_{t}(x)).$

DiPerna, Ambrosio, and Lions showed that if $X\in L^{\infty}\cap BV$ has
essentially bounded divergence, then the regular Lagrangian flow of $X$ exists
and is unique. Regular Lagrangian flows are _stable_ in the following sense:
if $(X_{k})$ is a sequence of smooth vector fields such that $X_{k}\to X$
strongly in $L^{1}_{\text{loc}}$, and $(\text{div}(X_{k}))$ is equibounded in
$L^{\infty}$, then the flows $\phi_{t}^{k}$ of $X_{k}$ converge strongly to
$\phi_{t}$ in $L^{1}_{\text{loc}}$, for every $t\in\mathbb{R}$.

If $X$ is of class $C^{Q}$, each time $t$-map $\phi_{t}$ of its flow (in the
usual sense) is $K$-quasiconformal for some $K$, hence preserves sets of
Lebesgue measure zero (see [Kos09]). Thus $\\{\phi_{t}\\}$ is the regular
Lagrangian flow of $X$.

######  7 Lemma.

Let $X$ is a $C^{Q}$ vector field with divergence in $L^{\infty}$ and denote
by $\\{\phi_{t}\\}$ its flow. Then $\left\lVert
D\phi_{t}\right\rVert_{L^{\infty}}<\infty$, for each $t$, i.e., $\phi_{t}$ is
Lipschitz.

###### Proof.

We follow [CT21]. Assume for a moment that $X$ is smooth. Then by Liouville’s
Theorem,

$\frac{d}{dt}\det D\phi_{t}(x)=\text{div}(X)(\phi_{t}(x))\cdot\det
D\phi_{t}(x),$

which implies, via Gronwall’s inequality that

$\exp(-T\left\lVert\text{div}(X)\right\rVert_{L^{\infty}})\leq\det
D\phi_{t}(x)\leq\exp(T\left\lVert\text{div}(X)\right\rVert_{L^{\infty}}),$ (1)

for all $T>0$ and $-T\leq t\leq T$. Thus $\left\lVert\det
D\phi_{t}\right\rVert_{L^{\infty}}<\infty$, for each $t$.

To make this work for a $C^{Q}$ vector field $X$, consider $\det D\phi_{t}$ as
a density, and take the mollifications $X^{\varepsilon}$ of $X$ (see, e.g.,
[Eva98]); let $\phi_{t}^{\varepsilon}$ be the flow of $X^{\varepsilon}$. By
the stability of regular Lagrangian flows, we have

$\det
D\phi_{t}^{\varepsilon}\stackrel{{\scriptstyle\ast}}{{\rightharpoonup}}\det
D\phi_{t}$

as $\varepsilon\to 0$ in $L^{\infty}$, which again yields (1). Since
$\phi_{t}$ is also $K$-quasiconformal, it follows (see part (c) in Def. 2)
that

$\left\lVert D\phi_{t}\right\rVert_{L^{\infty}}\leq K^{1/n}\left\lVert\det
D\phi_{t}\right\rVert_{L^{\infty}}^{1/n}<\infty,$

for $-T\leq t\leq T$, as desired. In particular, for any essentially bounded
vector field $Y$, $\left\lVert D\phi_{t}(Y)\right\rVert_{L^{\infty}}<\infty$,
for $-T\leq t\leq T$. ∎

The following corollary is a consequence of Theorem 1.1 in [CT21] and Lemma 7.

######  8 Corollary.

Let $X,Y$ be bounded Q-vector fields with essentially bounded divergence, and
let $\Phi=\\{\phi_{t}\\}$, $\Psi=\\{\psi_{t}\\}$ be their flows. Then the
following statements are equivalent:

  1. (a)

$\Phi$ and $\Psi$ commute as flows, i.e.,

$\phi_{t}\circ\psi_{s}(x)=\psi_{s}\circ\phi_{t}(x),$

for a.e. $x\in\mathbb{R}^{n}$ and all $s,t\in\mathbb{R}$.

  2. (b)

$[X,Y]=\mathbf{0}$, almost everywhere.

##  3\. Proof of the main result

The proof is a generalization of the standard proof for the smooth case, which
can be found in, say, Lee [Lee13]. We will show that locally $E$ admits a
frame consisting of commuting $C^{Q}$ vector fields, the composition of whose
flows then defines the desired coordinate system.

Assume that $E$ is an involutive $k$-dimensional plane field of class $C^{Q}$
and let $p=(p_{1},\ldots,p_{n})\in\mathbb{R}^{n}$ be an arbitrary point.
Without loss we can assume that $E_{p}$ is transverse to the subspace of
$T_{p}\mathbb{R}^{n}$ spanned by

$\left.\frac{\partial}{\partial
x_{k+1}}\right|_{p},\ldots,\left.\frac{\partial}{\partial x_{n}}\right|_{p}.$

Let $\pi:\mathbb{R}^{n}\to\mathbb{R}^{k}\times\\{\mathbf{0}\\}$ be the
projection
$(x_{1},\ldots,x_{n})\mapsto(x_{1},\ldots,x_{k},\overbrace{0,\ldots,0}^{n-k})$.
Then there exists a neighborhood $W$ of $p$ such that for every $q\in W$,
$D_{q}\pi$ is injective when restricted to $E_{q}$. Let $U$ be a neighborhood
of $p$ such that $\overline{U}\subset W$.

Let $\beta:\mathbb{R}^{k}\to\mathbb{R}$ be a $C^{\infty}$ bump function such
that $0\leq\beta\leq 1$, $\beta=1$ on $\pi(U)$, and $\beta=0$ on the
complement of $\pi(W)$. For $1\leq i\leq k$, set

$V_{i}=\beta\frac{\partial}{\partial x_{i}}.$

Then $V_{i}$ is a $C^{\infty}$ vector field on $\mathbb{R}^{n}$ with compact
support in $\pi(U)$. Denote its lift to $E$ via $\pi$ by $X_{i}$; i.e.,

$X_{i}(q)=(D_{q}\pi|_{E_{q}})^{-1}(V_{i}(\pi(q)).$

Since $E$ is of class $C^{Q}$, $X_{i}$ is also $C^{Q}$. Moreover, on $U$, we
have

$\pi_{\ast}([X_{i},X_{j}])=[\pi_{\ast}(X_{i}),\pi_{\ast}(X_{j})]=[V_{i},V_{j}]=\left[\frac{\partial}{\partial
x_{i}},\frac{\partial}{\partial x_{j}}\right]=0.$

By involutivity of $E$, $[X_{i},X_{j}]$ is a section of $E$ a.e.. Since the
restriction of $D\pi$ to $E$ is injective, it follows that $[X_{i},X_{j}]=0$,
a.e. on $U$.

######  9 Lemma.

$X_{i}$ has essentially bounded divergence, for $1\leq i\leq k$.

###### Proof.

Fix $1\leq i\leq k$. It follows by construction of $X_{i}$ that on $U$ we
have:

$X_{i}=\frac{\partial}{\partial
x_{i}}+\sum_{j=k+1}^{n}a_{j}\frac{\partial}{\partial x_{j}},$

for some continuous a.e. differentiable functions $a_{j}$ on $U$. Since
$X_{i}$ is $C^{Q}$, $S(X_{i})$ is essentially bounded. It is easy to check
that the $(j,j)$-component of $S(X_{i})$ equals

$S(X_{i})_{jj}=-\frac{1}{n}\sum_{\ell=k+1}^{n}\frac{\partial
a_{\ell}}{\partial x_{\ell}}=-\frac{1}{n}\text{div}(X_{i}).$

Thus the divergence of $X_{i}$ is essentially bounded. ∎

Denote the flows of $X_{1},\ldots,X_{k}$ by
$\phi_{t}^{1},\ldots,\phi_{t}^{k}$, respectively. By Corollary 8, they
commute.

Define a map $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ by

$\Phi(x_{1},\ldots,x_{n})=(\phi^{1}_{x_{1}}\circ\cdots\phi^{k}_{x_{k}})(p_{1},\ldots,p_{k},p_{k+1}+x_{k+1},\ldots,p_{n}+x_{n}).$

Then $\Phi$ is continuous and differentiable a.e.. We claim that there exists
$\varepsilon>0$ such that the restriction of $\Phi$ to the cube
$C_{\varepsilon}=(-\varepsilon,\varepsilon)^{n}$ is injective. Observe that
were $\Phi$ of class $C^{1}$, this would follow immediately from the Inverse
Function Theorem.

Let $\varepsilon>0$ be small enough so that the closure of $C_{\varepsilon}$
is contained in $\Phi^{-1}(U)$. We claim that $\Phi$ is injective on the
closure of $C_{\varepsilon}$. Assume that

$\Phi(x_{1},\ldots,x_{n})=\Phi(y_{1},\ldots,y_{n}),$

i.e.,

$(\phi^{1}_{x_{1}}\circ\cdots\phi^{k}_{x_{k}})(p_{1},\ldots,p_{k},p_{k+1}+x_{k+1},\ldots,p_{n}+x_{n})=(\phi^{1}_{y_{1}}\circ\cdots\phi^{k}_{y_{k}})(p_{1},\ldots,p_{k},p_{k+1}+y_{k+1},\ldots,p_{n}+y_{n}),$

for some
$(x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n})\in\overline{C}_{\varepsilon}$.
Denote the flow of $\partial/\partial x_{i}$ by $\psi^{i}_{t}$. Since
$\pi\circ\phi_{t}^{i}=\psi_{t}^{i}\circ\pi$, by projecting
$\Phi(x_{1},\ldots,x_{n})$ and $\Phi(y_{1},\ldots,y_{n})$ via $\pi$, we obtain

$\displaystyle(\psi^{1}_{x_{1}}\circ\cdots\psi^{k}_{x_{k}})(p_{1},\ldots,p_{k})=(\psi^{1}_{y_{1}}\circ\cdots\psi^{k}_{y_{k}})(p_{1},\ldots,p_{k}),$

which implies that $x_{i}=y_{i}$, for $1\leq i\leq k$.

Thus

$(\phi^{1}_{x_{1}}\circ\cdots\phi^{k}_{x_{k}})(p_{1},\ldots,p_{k},p_{k+1}+x_{k+1},\ldots,p_{n}+x_{n})=(\phi^{1}_{x_{1}}\circ\cdots\phi^{k}_{x_{k}})(p_{1},\ldots,p_{k},p_{k+1}+y_{k+1},\ldots,p_{n}+y_{n})$

which clearly implies $x_{i}=y_{i}$, for $k+1\leq i\leq n$. Therefore, $\Phi$
is 1–1 on $\overline{C}_{\varepsilon}$. By the continuity of $\Phi$ and
compactness of $\overline{C}_{\varepsilon}$, it follows that
$\Phi:C_{\varepsilon}\to\Phi(C_{\varepsilon})$ is a homeomorphism.

Let $S_{c}$ be a slice $(-\varepsilon,\varepsilon)^{k}\times\\{c\\}\subset
C_{\varepsilon}$ (where $c\in\mathbb{R}^{n-k}$) and let

$\alpha(t)=(x_{1}(t),\ldots,x_{k}(t),c)$

be an arbitrary $C^{1}$ path in $S_{c}$. Then

$\gamma(t)=\Phi(\alpha(t))=\phi^{1}_{x_{1}(t)}\circ\cdots\circ\phi^{k}_{x_{k}(t)}(\text{const}).$

The chain rule and commutativity of the flows $\phi^{i}_{t}$ implies that
$\gamma^{\prime}(t)$ is a linear combination of $X_{1},\ldots,X_{k}$, hence
tangent to $E$. Therefore, $\Phi(S_{c})$ is an integral manifold of $E$.

Since the tangent bundle of each integral manifold $N$ of $E$ is a continuous
plane field (namely, $E$ restricted to $N$), it follows that $N$ is a $C^{1}$
manifold. This completes the proof. ∎

######  Remark.

The following questions would be of interest for further exploration:

  1. (a)

Does the main result still hold if a $C^{Q}$ plane field is defined as locally
spanned by $C^{Q}$ vector fields with compact support?

  2. (b)

What can be said about foliations tangent to integrable $C^{Q}$ plane fields?

## References

  * [Amb04] L. Ambrosio, _Transport equation and Cauchy problem for BV vector fields_ , Invent. Math. 158 (2004), no. 2, 227–260.
  * [CT21] Maria Colombo and Riccardo Tione, _On the commutativity of flows of rough vector fields_ , Journal de Mathématiques Pures et Appliquées 1 (2021), no. 159.
  * [dL89] R. J. diPerna and P. L. Lions, _Ordinary differential equations, transport theory and Sobolev spaces_ , Invent. Math. 98 (1989), no. 3, 511–547.
  * [Eva98] Lawrence C. Evans, _Partial Differential Equations_ , Graduate Studies in Mathematics, vol. 19, AMS, 1998.
  * [Kos09] P. Koskela, _Lectures on quasiconformal and quasisymetric mappings_ , Jyväskylä Lectures in Mathematics (2009).
  * [Lee13] John M. Lee, _Introduction to Smooth Manifolds_ , second ed., Grad. Text in Math., vol. 218, Springer, New York, 2013.
  * [Ram07] F. Rampazzo, _Frobenius-type theorems for Lipschitz distributions_ , Journal of Differential Equations 243 (2007), no. 2, 270–300.
  * [Rei76] H. M. Reimann, _Ordinary differential equations and quasiconformal mappings_ , Invent. Math. 33 (1976), 247–270.
  * [Sim96] Slobodan N. Simić, _Lipschitz distributions and Anosov flows_ , Proc. Amer. Math. Soc. 124 (1996), no. 6, 1869–1877.