# Statistical Inference of Optimal Allocations I: Regularities and their
Implications

Kai Feng Institute of Economics, Tsinghua University.
<EMAIL_ADDRESS>Han Hong Department of Economics, Stanford
University<EMAIL_ADDRESS>
Abstract. In this paper, we develp a functional differentiability approach for
solving statistical optimal allocation problems. We first derive Hadamard
differentiability of the value function through a detailed analysis of the
general properties of the sorting operator. Central to our framework are the
concept of Hausdorff measure and the area and coarea integration formulas from
geometric measure theory. Building on our Hadamard differentiability results,
we demonstrate how the functional delta method can be used to directly derive
the asymptotic properties of the value function process for binary constrained
optimal allocation problems, as well as the two-step ROC curve estimator.
Moreover, leveraging profound insights from geometric functional analysis on
convex and local Lipschitz functionals, we obtain additional generic Fréchet
differentiability results for the value functions of optimal allocation
problems. These compelling findings motivate us to study carefully the first
order approximation of the optimal social welfare. In this paper, we then
present a double / debiased estimator for the value functions. Importantly,
the conditions outlined in the Hadamard differentiability section validate the
margin assumption from the statistical classification literature employing
plug-in methods that justifies a faster convergence rate.

Keywords: Optimal treatment allocation, Functional differentiability and delta
method, Plug-in classification, ROC curve, Double / debiased machine learning

††This paper is developed based on the ideas from an earlier work-in-progress
project circulated under the title “Decision Making with Machine Learning and
ROC Curves”. The work-in-progress project latter has been developed into a
working paper series, where this manuscriptserves as the beginning of the
sequence. A large portion of the reported results of this paper was drafted
during the first author’s visit to Stanford University. We acknowledge helpful
and encouraging conservations with collaborators and colleagues including
Timothy Armstrong, Xiaohong Chen, Hongjun Li, Jessie Li, Thomas MaCurdy. We
are most grateful to Yuhao Xue for enlightening us with his knowledge of
geometry measure theory. Financial support was provided by the Tsinghua
University Short-Term Overseas Visit Funds.

##  1 Introduction

Currently, as a consequence of the rapid digitization of social-economic data,
characterizing individual heterogeneity has become crucial in the optimal
allocation of scarce resources. Consider, for instance, the medical treatment
assignment problem when doctors adopt different therapeutic approaches to
different patients; the pretrial bail problem when judges decide where
defendants will await trial; the college admission problem when committees
assign students to various educational programs. In order to address the
heterogeneity inherent in such problems, where the potential effects of a
treatment on an outcome vary among individuals, personalized allocation is
more of a necessity than just an option.

Based on past experimental or observational data, the core objective of a
typical allocation problem is to find an allocation strategy that can perform
well in the future. To achieve this goal, at least based on experience, an
effective approach of decision making is to rely on information provided by
prediction algorithms. (Kleinberg et al., 2018; Agrawal et al., 2019; Babina
et al., 2024). In empirical applications, a common practice is to form a
nonrandom treatment rule using an indicator function, in which a first step
regression estimate of individual level treatment effect is plugged-in and
benchmarked against certain decision thresholds. In this case, mathematically,
optimal allocation is treated as a weighted classification problem.

A plug-in strategy is based on a population solution to the optimal allocation
problem. For a joint distribution of $\\{X,Y\\}$,
$Y=\left(Y_{j},j=0,\ldots,J\right)$, consider the social welfare potential
function

$\displaystyle\begin{split}\gamma\left(\lambda,g\left(\cdot\right)\right)\coloneqq\max_{\phi\in\Phi}\mathbb{E}\left[\sum_{j}\lambda_{j}\phi_{j}\left(X\right)Y_{j}\right]=\max_{\phi\in\Phi}\mathbb{E}\left[\sum_{j}\lambda_{j}\phi_{j}\left(X\right)g_{j}\left(X\right)\right],\end{split}$
(1)

where $\Phi$ is the set of multi-critical functions, i.e.
$\phi=\left(\phi_{j},j=0,\ldots,J\right)$, $\phi_{j}:\Omega\rightarrow R$,
with $\left(\Omega,F,\mu\right)$ being a Borel probability space, such that
$\phi_{j}\in L^{\infty}\left(\mu\right),0\leq\phi_{j}\leq 1,\forall
j\in\\{0,\ldots,J\\}$, and such that
$\sum_{j=0}^{J}\phi_{j}\left(x\right)\equiv 1$ for all $x\in\Omega$;
$g\left(\cdot\right)=\left\\{g_{j}\left(\cdot\right),j=0,\ldots,J\right\\}$
and $g_{j}\left(x\right)=\mathbb{E}\left(Y_{j}|X=x\right)$. Under very general
conditions, the problem posed in (1) admits an intuitive solution where the
$j$th-category receives all allocation when
$\mathbb{E}\left(\lambda_{j}Y_{j}|X\right)$ is uniquely the largest. In other
words,

$\displaystyle\begin{split}\phi_{j}\left(X\right)=\left\\{\begin{array}[]{cc}1,&\text{if}\
\mathbb{E}\left(\lambda_{j}Y_{j}|X\right)>\mathbb{E}\left(\lambda_{l}Y_{l}|X\right),\
\forall l\neq j,\\\ 0,&\text{if}\
\mathbb{E}\left(\lambda_{j}Y_{j}|X\right)<\mathbb{E}\left(\lambda_{l}Y_{l}|X\right),\
\exists l\neq j.\end{array}\right.\end{split}$ (2)

If there exists some $l$ such that
$\mathbb{E}\left(\lambda_{j}Y_{j}|X\right)=\mathbb{E}\left(\lambda_{l}Y_{l}|X\right)$,
then $\phi\left(\cdot\right)$ can be divided among all the maximal indexes.

In this paper, we are interested in differentiating
$\gamma\left(\lambda,g\right)$ functionally with respect to both $\lambda$ and
$g\left(\cdot\right)$. The solution of such problem can help answering the
core problem of the statistical treatment rule literature, i.e. establishing
probabilistic regret guarantees for treatment rules obtained from empirical
data, as considered by Manski (2004) and the subsequent works. The regret
there is defined as the difference between the social welfare potential and
the expected utility achieved by an estimated decision rule. Our approach can
also provide answers for multiple other problems of interdisciplinary
interest. For instance, we will derive asymptotic distributions for the binary
optimal allocation subject to one resource constraint and the receiver
operating characteristic (ROC) curve.

Our paper is an attempt to synthesize the methodology and perspective of
several strands of literature. Hereafter, the core nature of issues, as will
be readily apparent, comes from the statistical treatment rule literature. A
widely-known surprising phenomenon in the plug-in classification literature is
that the second step classification is simpler than the first step regression,
in the sense that the former usually converges faster than the latter (Devroye
et al., 1996; Audibert and Tsybakov, 2007). Built on seminar works Chen et al.
(2003) and Chernozhukov et al. (2018b) on method of moments allowing
nonsmoothness, especially the latter, our paper can provide sets of conditions
to support $\sqrt{n}$ and faster convergence rates of both the regret and
other objective of interest. It will be shown that our differentiation results
allow for asymptotic analysis under settings for both classical empirical
processes and recent advances in double / debiased machine learning
(Chernozhukov et al., 2018a, 2022).

To get some intuition of our approach, consider the finite dimensional
derivatives of $\gamma\left(\lambda,g\right)$ with respect to $\lambda$ when
$J=1$. Assume that
$\mathbb{P}\\{\lambda_{1}g_{1}\left(X\right)=\lambda_{0}g_{0}\left(X\right)\\}=0$.
Then we can write,

$\displaystyle\begin{split}\gamma\left(\lambda_{0},\lambda_{1},g\right)=\mathbb{E}\left[1\left(\lambda_{0}g_{0}\left(X\right)>\lambda_{1}g_{1}\left(X\right)\right)\lambda_{0}g_{0}\left(X\right)\right]+\mathbb{E}\left[1\left(\lambda_{1}g_{1}\left(X\right)>\lambda_{0}g_{0}\left(X\right)\right)\lambda_{1}g_{1}\left(X\right)\right].\end{split}$
(3)

Formally, given the definition of
$\gamma\left(\lambda_{0},\lambda_{1},g\right)$, we expect that

$\displaystyle\begin{split}&\frac{\partial\gamma\left(\lambda_{0},\lambda_{1},g\right)}{\partial\lambda_{0}}=\mathbb{E}\left[1\left(\lambda_{0}g_{0}\left(X\right)>\lambda_{1}g_{1}\left(X\right)\right)g_{0}\left(X\right)\right],\\\
&\frac{\partial\gamma\left(\lambda_{0},\lambda_{1},g\right)}{\partial\lambda_{1}}=\mathbb{E}\left[1\left(\lambda_{1}g_{1}\left(X\right)>\lambda_{0}g_{0}\left(X\right)\right)g_{1}\left(X\right)\right].\end{split}$

A rigorous proof of the above is by direct calculation of the limit. It is not
hard to see that the terms of major difficulties are

$\displaystyle\begin{split}\lim_{h\to
0}&\frac{\mathbb{E}\left[1\left(\left(\lambda_{0}+h\right)g_{0}\left(X\right)>\lambda_{1}g_{1}\left(X\right)\right)-1\left(\lambda_{0}g_{0}\left(X\right)>\lambda_{1}g_{1}\left(X\right)\right)\lambda_{0}g_{0}\left(X\right)\right]}{h}\quad\text{and}\\\
\lim_{h\to
0}&\frac{\mathbb{E}\left[1\left(\lambda_{1}g_{1}\left(X\right)>\left(\lambda_{0}+h\right)g_{0}\left(X\right)\right)-1\left(\lambda_{1}g_{1}\left(X\right)>\lambda_{0}g_{0}\left(X\right)\right)\lambda_{1}g_{1}\left(X\right)\right]}{h}.\end{split}$
(4)

We will see later in section 3 that under mild conditions, the two terms in
(4) both converge to the same integral on the level set (i.e. fiber)
$\\{x:\lambda_{0}g_{0}\left(x\right)=\lambda_{1}g_{1}\left(x\right)\\}$ with
opposing signs, so that they cancel out. As a consequence, the desired partial
derivatives exist and take the displayed simple form.

Our approach in section 3 is greatly inspired by the integration on manifold
approach in Chernozhukov et al. (2018b). In particular, we reapproach and
generalize their results based on the concept of Hausdorff measure and
powerful integration formulas, i.e. area and coarea formulas from geometric
measure theory. By precise calculation, we manage to show that the Hadamard
derivative of $\gamma\left(\lambda,g\right)$ contains terms that are integrals
under certain Hausdorff measure. The Hadamard differentiability results are
derived under mild primitive conditions, which differentiates us from previous
works relying on differentibility or pathwise differentibility assumptions.
See for example Sherman (1993) and Luedtke and van der Laan (2016a).

Returning to the general multivariate setting, the social welfare potential
function in (1) is not only subadditive but also positive homogeneous of
degree one with respect to both $\lambda$ and $g\left(\cdot\right)$,
respectively, which implies that
$\gamma\left(\lambda,g\left(\cdot\right)\right)$ is convex in
$g\left(\cdot\right)$ given $\lambda$ and is convex in $\lambda$ given
$g\left(\cdot\right)$. For example,

$\displaystyle\begin{split}\gamma\left(\lambda,\alpha
g+\left(1-\alpha\right)g^{\prime}\right)&=\max_{\phi\in\Phi}\mathbb{E}\left[\sum_{j=0}^{J}\lambda_{j}\phi_{j}\left(X\right)\left(\alpha
g_{j}\left(X\right)+\left(1-\alpha\right)g_{j}^{\prime}\left(X\right)\right)\right]\\\
&\leq\max_{\phi\in\Phi}\mathbb{E}\left[\sum_{j=0}^{J}\alpha\lambda_{j}\phi_{j}\left(X\right)g_{j}\left(X\right)\right]+\max_{\phi\in\Phi}\mathbb{E}\left[\sum_{j=0}^{J}\left(1-\alpha\right)\lambda_{j}\phi_{j}\left(X\right)g_{j}^{\prime}\left(X\right)\right]\\\
&=\alpha\gamma\left(\lambda,g\right)+\left(1-\alpha\right)\gamma\left(\lambda,g^{\prime}\right).\end{split}$

However, $\gamma\left(\lambda,g\right)$ is not necessarily jointly convex in
$\left(\lambda,g\right)$. We can not be assured that

$\displaystyle\begin{split}\gamma\left(\alpha\lambda+\left(1-\alpha\right)\lambda^{\prime},\alpha
g+\left(1-\alpha\right)g^{\prime}\right)\leq\alpha\gamma\left(\lambda,g\right)+\left(1-\alpha\right)\gamma\left(\lambda^{\prime},g^{\prime}\right).\end{split}$

Interestingly, the above simple observations seem to have gone completely
unnoticed by the existing literature. In section 4, we apply deep results from
geometric functional analysis, in particular those by Stegall (1978), Preiss
(1990) and Lindenstrauss and Preiss (2003), to show that under nearly no
assumptions, the social welfare potential function
$\gamma\left(\lambda,g\right)$ is Fréchet differentiable on a generic set.

The surprising Fréchet differentiability property inpires us to reconsider the
first order approximation of $\gamma\left(\lambda,g\right)$. Section 4 shows
that the primitive conditions in section 3 can also be used to support the
faster convergence rate in classical classification literature. See for
example Audibert and Tsybakov (2007) among others. Further, the same
methodology can be combined with recent double / debiased machine learning
approach (Chernozhukov et al., 2018a, 2022) to speed up the estimation of
$\gamma\left(\lambda,g\right)$. The roles of the regularity conditions
clarified in this paper are fully demonstrated when they collaborate in tandem
with the insights from the corresponding previous literature.

##  2 Literature

The construction of optimal decision rules from experimental or observational
data have been considered by both the classical and recent literature in
multidisciplines. Different terminology have been used, such as treatment
allocation, policy learning in econometrics and individual treatment rule
(ITR) in statistics. A large body of the literature, including Manski (2004),
Qian and Murphy (2011), Zhao et al. (2012), Swaminathan and Joachims (2015),
Zhou et al. (2017), Kitagawa and Tetenov (2018), Luedtke and Chambaz (2020),
Athey and Wager (2021), Mbakop and Tabord-Meehan (2021), Zhou et al. (2023)
and Ben-Michael et al. (2024), among others, study in details this problem in
an empirical risk minimization (ERM) framework. The basic objective there is
to provide probabilistic bound for

$\displaystyle\begin{split}R\left(\hat{\phi},\phi^{*}\right)&=\mathbb{E}_{X,Y}\left[\sum_{j}\phi^{*}_{j}\left(X\right)Y_{j}\right]-\mathbb{E}_{X,Y}\left[\sum_{j}\hat{\phi}_{j}\left(X\right)Y_{j}\right],\\\
\text{ for
}\hat{\phi}&\in\mathop{\arg\max}\limits_{\phi\in\Phi_{0}}\sum_{i}\langle\phi\left(X_{i}\right),F\left(X_{i},D_{i},Y_{i}\right)\rangle,\end{split}$

where $\phi^{*}$ solves the population optimization program of (1). The
function $F\left(X,D,Y\right)$ usually takes the inverse propensity weighting
(IPW) or doubly robust (DR) form (see for example Kitagawa and Tetenov (2018)
and Athey and Wager (2021)), and $\Phi_{0}\subset\Phi$ is not too complex in
an entropy sense.

The difficulty involved in the optimal allocation problem is due to the
indicator function in the population solution which is hard to handle (Qian
and Murphy, 2011). Our solution of such a problem built on a divergent
literature motivated by very different purposes. To address the restoration of
monotonicity in conditional quantile estimation, the functional derivative of
the sorting operator in the univariate case is studied by Chernozhukov et al.
(2010). The analysis of the sorting operator is then extended to the
multivariate cases by Chernozhukov et al. (2018b) using calculus on manifold
techniques. Kim and Pollard (1990) also hinted at a rudimentary form of
calculus on manifold in the derivation of the large sample properties of cube
root consistent estimators. Sasaki (2015) incorporated the tools based on the
Hausdorff measure developed in fluid mechanics to characterize the information
content of quantile partial derivatives for general structural functions.

The optimal allocation problem has also been discussed under a plethora of
different but closely related settings. Examples include asymptotically
minimax optimal decision under the limits of experiments framework (Hirano and
Porter, 2009), optimal decision under minimax regret (Stoye, 2009; Tetenov,
2012; Ben-Michael et al., 2024), uniform confidence interval (Armstrong and
Shen, 2023), allocation with spillover effects (Kitagawa and Wang, 2023a, b)
and binary constrained optimal allocation (Bhattacharya and Dupas, 2012;
Luedtke and van der Laan, 2016a). Our general functional Hadamard derivative
results in subsection 3.3 are applicable for solving the last problem above.
This problem is also closely relevant to the receiver operating characteristic
(ROC) curve widely used in biostatistics and computer science. A previous
literature that has studied the inference of the ROC curves, including Hsieh
and Turnbull (1996), Lloyd (1998), Li et al. (1999), Hall et al. (2004) and
Bertail et al. (2008), did not account for the estimation error in the sample
propensity score. An exception is Luckett et al. (2021), where the authors
derive the uniform asymptotic results for estimated ROC curve when the
classification is done by a support vector machine (SVM). Unlike the studies
above, we derive the asymptotic properties of the ROC curves obtained by
plugging-in the propensity score estimators, which is consistent with the
usage of predictive classifiers in various disciplines.

The methodology in this paper also has intriguing connection with the faster
convergence phenomenon in the classification literature (Devroye et al., 1996;
Audibert and Tsybakov, 2007). Consider, especially, the margin assumption (MA)
evoked by works including Tsybakov (2004), Audibert and Tsybakov (2007) and
Boucheron et al. (2005), i.e.

$\displaystyle\begin{split}\mathbb{P}\left\\{|p\left(X\right)-c|<t\right\\}\leq
Ct^{\alpha}\end{split}$

for fixed $c$ and some constant $C>0$ and $\alpha\geq 0$. Our conditions in
section 3 directly imply the marginal assumption with $\alpha\geq 1$. This
observation can be further combined with the recent double / debiased machine
learning approach (Chernozhukov et al., 2018a, 2022) to form a relatively
primitive level, plug-in and non empirical process complement of the optimal
allocation literature.

##  3 Hadamard differentiability

Following the seminal research of Chernozhukov et al. (2018b), we consider (3)
as a functional mapping from $g\left(\cdot\right)$ to
$\gamma\left(\lambda,g\left(\cdot\right)\right)$, and are interested in the
differential change in $\gamma\left(\lambda,g\left(\cdot\right)\right)$
induced by a marginal change in $\left(\lambda,g\left(\cdot\right)\right)$.
More precisely, we rigorously derive the Hadamard derivative of
$\gamma\left(\lambda,g\left(\cdot\right)\right)$ with respect to
$\left(\lambda,g\left(\cdot\right)\right)$, which justifies and generalizes
the calculations in (4). In section 3, we assume that the underlying
distribution of $X$, denoted as $\mu$, is absolutely continuous with respect
to $\mathcal{L}_{n}$, the $n$-dimensional Lebesgue measure. Then we write

$\displaystyle\begin{split}\mathbb{E}\left[\sum_{j=0}^{J}\lambda_{j}\phi_{j}\left(X\right)g_{j}\left(X\right)\right]=\sum_{j=0}^{J}\int\lambda_{j}\phi_{j}\left(x\right)g_{j}\left(x\right)d\mu\left(x\right)=\sum_{j=0}^{J}\int\lambda_{j}\phi_{j}\left(x\right)g_{j}\left(x\right)f\left(x\right)dx.\end{split}$

where $f\left(x\right)$ is the density function. Typically, the optimizing
policy function takes the form of $\phi_{j}\left(x\right)=\prod_{l\neq
j}1\left(\lambda_{j}g_{j}\left(x\right)>\lambda_{l}g_{l}\left(x\right)\right).$
For simplicity, if we abbreviate $\lambda_{j}g_{j}\left(x\right)$ as
$g_{j}\left(x\right)$, then the main object that we are going turns out to be

$\displaystyle\begin{split}\int g_{j}\left(x\right)f\left(x\right)\prod_{l\neq
j}1\left(g_{j}\left(x\right)>g_{l}\left(x\right)\right)d\mathcal{L}_{n}\end{split}$

which can be further generalized to a form of the following sorting operator
(as defined by Chernozhukov et al. (2018b)),

$\displaystyle\begin{split}\int
g_{j}\left(x\right)f\left(x\right)\prod_{l}1\left(h_{l}\left(x\right)>c\right)d\mathcal{L}_{n},\end{split}$
(5)

where the number of terms in the product should be less than $n$, the
dimension of $X$.

###  3.1 Hausdorff measure and integration formulas

The following discussions are based on standard references by Federer (1969)
and Evans and Garzepy (2015). In order to rigorously present surface integral
in Chernozhukov et al. (2018b), this section first aims to define
extrinsically the intuitive notion of length, area, and volume. For this
purpose, the Carathéodory criterion is used to construct a measure space from
a $\sigma$-subadditive set function (outer measure) on power set of
$\mathbb{R}^{N}$. More specifically, we introduce Hausdorff’s construction,
which does not require any local parameterization on these sets. Therefore no
assumption of regularity is needed.

######  Definition 3.1.1.

(Outer measure) For a set $O$, an outer measure is a function

$\displaystyle\begin{split}\mu^{*}:2^{O}\to\left[0,\infty\right]\quad\text{such
that}\end{split}$

  1. (a)

$\mu^{*}\left(\emptyset\right)=0$.

  2. (b)

For arbitrary subsets $A,B$, $A\subset B\subset O$,
$\mu^{*}\left(A\right)\leq\mu^{*}\left(B\right)$.

  3. (c)

For arbitrary subsets $B_{1},B_{2},\ldots$ of $O$,

$\displaystyle\begin{split}\mu^{*}\left(\bigcup^{\infty}_{i=1}B_{i}\right)\leq\sum^{\infty}_{i=1}\mu^{*}\left(B_{i}\right).\end{split}$

If an outer measure $\mu^{*}$ is defined on a metric space $\left(O,d\right)$
and satisfies

$\displaystyle\begin{split}d\left(A,B\right)>0\Rightarrow\mu^{*}\left(A\cup
B\right)=\mu^{*}\left(A\right)+\mu^{*}\left(B\right),\quad\forall A,B\subset
O.\end{split}$

Then $\mu^{*}$ is called a metric outer measure.

In this paper, we use a series of metric outer measure with the following
specific construction, called Hausdorff outer measure.

######  Definition 3.1.2.

(Hausdorff outer measure) Let $d$ be the metric on $O$. For arbitrary subset
$E\subset O$, define its diameter as $\mathrm{diam}\ E=\sup_{x_{1},x_{2}\in
U}d\left(x_{1},x_{2}\right),\mathrm{diam}\ \emptyset=0.$ Let $\delta>0$,

$\displaystyle\begin{split}\alpha_{k}=\frac{\pi^{\frac{k}{2}}}{\Gamma\left(\frac{k}{2}+1\right)},\quad
k\in\mathbb{N}=\\{0,1,\ldots\\},\end{split}$

where $\Gamma\left(\cdot\right)$ is the gamma function. For arbitrary
$E\subset O$, define

$\displaystyle\begin{split}\mathcal{H}^{*}_{k,\delta}\left(E\right)=\inf\left\\{\sum_{j\geq
1}\alpha_{k}\left(\frac{\mathrm{diam}\
B_{j}}{2}\right)^{k}:E\subset\bigcup_{j\geq 1}B_{j},\mathrm{diam}\
B_{j}\leq\delta\right\\}.\end{split}$

The $k$-dimensional Hausdorff outer measure of $E$ is defined as
$\mathcal{H}^{*}_{k}\left(E\right)=\lim_{\delta\downarrow
0}\mathcal{H}^{*}_{k,\delta}\left(E\right)$, and can be verified to be a
metric outer measure on the metric space $\left(O,d\right)$.

######  Definition 3.1.3.

(Hausdorff measure) Let $k\in\mathbb{N}$,
$\mathcal{M}_{k}=\mathcal{M}_{k}\left(O\right)$ is the $\sigma$-algebra
generated by $\mathcal{H}^{*}_{k}$ by the Carathéodory criterion (See Theorem
T.1.1). Then the restriction of $\mathcal{H}^{*}_{k}$ to $\mathcal{M}_{k}$,
$\mathcal{H}_{k}=\mathcal{H}^{*}_{k}|_{\mathcal{M}_{k}}$ is called Hausdorff
measure on $\mathcal{M}_{k}$.

In $\mathbb{R}^{k}$, $\mathcal{H}^{*}_{k}=\mathcal{L}^{*}_{k}$,
$\mathcal{H}_{k}=\mathcal{L}_{k}$, where $\mathcal{L}^{*}_{k}$ is the Lebesgue
outer measure and $\mathcal{L}_{k}$ is the Lebesgue measure on
$\mathbb{R}^{k}$. $\mathcal{H}^{*}_{0}\left(E\right)$ measures the cardinality
of the set $E$:

$\displaystyle\begin{split}\mathcal{H}^{*}_{0}\left(E\right)=\mathcal{H}_{0}\left(E\right)=\left\\{\begin{array}[]{ll}\text{number
of element in }E,&E\text{ is empty or finite,}\\\ +\infty,&E\text{ is
infinite}.\end{array}\right.\end{split}$

In this application, we focus on the Hausdorff measure defined on Euclidean
spaces $\mathbb{R}^{k}$.

######  Definition 3.1.4.

(Jacobian) For $k\in\\{1,2,\ldots,n\\}$, define the Jacobian at $x$ as

$\displaystyle\begin{split}Jf\left(x\right)=\left\\{\begin{array}[]{ll}\sqrt{\det\left(f^{\prime}\left(x\right)^{T}f^{\prime}\left(x\right)\right)},&f:E\subset\mathbb{R}^{k}\mapsto\mathbb{R}^{n},\\\
\sqrt{\det\left(f^{\prime}\left(x\right)f^{\prime}\left(x\right)^{T}\right)},&f:E\subset\mathbb{R}^{n}\mapsto\mathbb{R}^{k}.\end{array}\right.\end{split}$

The following Theorem 3.1.1 for change of variable generalizes the
conventional integration change of variable formula for invertible mapping to
allow for non-invertible mapping and an increase in dimension.

######  Theorem 3.1.1.

Area formula
Let $E\subset\mathbb{R}^{k}$ be an open set, $k\in\\{1,2,\ldots,n\\}$,
$\psi:E\mapsto\mathbb{R}^{n}$ be a $C^{1}$ or Lipschitz function. Then for all
measurable $S\subset E$,

$\displaystyle\begin{split}\int_{S}J\psi\left(x\right)d\mathcal{L}_{k}x=\int_{\psi\left(S\right)}\mathcal{H}_{0}\left(S\cap\psi^{-1}\left(y\right)\right)d\mathcal{H}_{k}y.\end{split}$
(6)

If a measurable function $f:S\mapsto\mathbb{R}$ is nonnegative or if the left
hand side of (7) is finite, then the following equality holds,

$\displaystyle\begin{split}\int_{S}f\left(x\right)J\psi\left(x\right)d\mathcal{L}_{k}x=\int_{\psi\left(S\right)}\left[\int_{S\cap\psi^{-1}\left(y\right)}f\left(x\right)d\mathcal{H}_{0}x\right]d\mathcal{H}_{k}y.\end{split}$
(7)

Furthermore, the next curving Fubini-Tonelli theorem allows for slicing among
curving surfaces and mapping from a higher dimension to a lower dimension.

######  Theorem 3.1.2.

Coarea formula
Let $E\subset\mathbb{R}^{n}$ be an open set, $k\in\\{1,2,\ldots,n\\}$,
$\varphi:E\mapsto\mathbb{R}^{k}$ be a $C^{1}$ or Lipschitz function, then for
all measurable $S\subset E$,

$\displaystyle\begin{split}\int_{S}J\varphi\left(x\right)d\mathcal{L}_{n}x=\int_{\mathbb{R}^{k}}\mathcal{H}_{n-k}\left(S\cap\varphi^{-1}\left(y\right)\right)d\mathcal{H}_{k}y.\end{split}$
(8)

If a measurable function $f:S\mapsto\mathbb{R}$ is nonnegative or if the left
hand side of (9) is finite, then the following equality holds,

$\displaystyle\begin{split}\int_{S}f\left(x\right)J\varphi\left(x\right)d\mathcal{L}_{n}x=\int_{\mathbb{R}^{k}}\left[\int_{S\cap\varphi^{-1}\left(y\right)}f\left(x\right)d\mathcal{H}_{n-k}x\right]d\mathcal{H}_{k}y.\end{split}$
(9)

######  Remark 3.1.1.

(7) and (9) are direct corollaries of (6) and (8), respectively, by a standard
simple function approximation of measurable functions. (7), (9) and the
classical $\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$ change of variables formula,
can be collectively written in a unified formula:

$\displaystyle\begin{split}\int_{S}f\left(x\right)J\varphi\left(x\right)d\mathcal{L}_{n}x=\int_{\mathbb{R}^{m}}\left[\int_{S\cap\varphi^{-1}\left(y\right)}f\left(x\right)d\mathcal{H}_{\max\\{n-m,0\\}}x\right]d\mathcal{H}_{\min\\{n,m\\}}y.\end{split}$

To the best of our knowlegde, a result similar to Theorem 3.1.1 was first
published in Federer (1944). The coarea formula in the form of (9) was first
published in Federer (1959), one of the most important papers by Federer.
Results similar to Theorem 3.1.2 were presented earlier by Aleksandr
Semyonovich Kronrod, Herbert Federer, Laurence Chisholm Young (L.C.Young),
Ennio De Giorgi and maybe even others. The statements of the area and coarea
formulas in Theorems 3.1.1 and 3.1.2 are closer to Federer (1969) and the more
readable Evans and Garzepy (2015). Roughly speaking, generalizations of both
Theorem 3.1.1 and Theorem 3.1.2 can still work when the Euclidean spaces
therein are replaced by certain kind of surface, e.g. Riemannian manifolds and
rectifiable sets of Euclidean spaces, see 3.2.20-3.2.22 and 3.2.46 in Federer
(1969) for classical developments. In the technical addendum T behind the main
text, we provide readable proofs to both Theorem 3.1.1 and Theorem 3.1.2 with
a complete set of preliminary results needed in the derivation.

######  Definition 3.1.5.

(Critical and regular point and value) Let $n,m\in\\{1,2,\ldots\\}$,
$E\subset\mathbb{R}^{n}$ be an open set, $f:E\mapsto\mathbb{R}^{m}$ be a
$C^{1}$ function. A point $x\in E$ is called a critical point if
$Jf\left(x\right)=0$; otherwise $x$ is called a regular point. If
$c=f\left(x\right)$ for a critical point $x$, then $c$ is called a critical
value; otherwise $c$ is called a regular value. For simplicity, in the main
text we only consider regular value $c\in f\left(E\right)$.

The area and coarea formulas in Theorems 3.1.1 and 3.1.2 are closely related
to another important result called Morse-Sard Theorem, which essentially
states that the set of critical values is a null set. See for example Theorem
T.1.10. Corollary T.3.2, which follows directly from Theorem 3.1.1, is indeed
Theorem T.1.10 when $n=m$. In economics, one of the most well-known
applications of the Sard type theorem is Debreu (1970) which established that
except for a null set of economies, every economy has a finite set of
equilibria. For a relatively simple derivation of the Morse-Sard theorem, see
Figalli (2008). The basic ideas in Figalli (2008) is to make use of the Morrey
inequality, which is then combined with Whitney extension theorem T.1.3 to
prove the Morse-Sard theorem in a stronger Sobolev sense, which implies the
$C^{r}$ case. Evans and Garzepy (2015) shows in detail how to use the coarea
formula (9) to develop the Morrey inequality.

###  3.2 Hadamard derivatives of the sorting operator

In this section, we introduce our mathematics results on the Hadamard
differentiability of the sorting operator in (5), where we intend to compute

$\displaystyle\begin{split}\lim_{t\to
0}\frac{1}{t}\left[\int\left(g_{j}\left(x\right)+tG_{j}\left(x\right)\right)f\left(x\right)1\left(h\left(x\right)+tH\left(x\right)>c\right)d\mathcal{L}_{n}-\int
g_{j}\left(x\right)f\left(x\right)1\left(h\left(x\right)>c\right)d\mathcal{L}_{n}\right].\end{split}$

It should be clear that the main term that needs to account for is

$\displaystyle\begin{split}\lim_{t\to 0}\frac{1}{t}\left[\int
g_{j}\left(x\right)f\left(x\right)1\left(h\left(x\right)+tH\left(x\right)>c\right)d\mathcal{L}_{n}-\int
g_{j}\left(x\right)f\left(x\right)1\left(h\left(x\right)>c\right)d\mathcal{L}_{n}\right].\end{split}$

Therefore we focus on the following simplified form of the sorting operator
(with respect to the Lebesgue measure):

$\displaystyle\begin{split}F\left(h,c\right)\coloneqq\int_{h\left(x\right)>c}f\left(x\right)d\mathcal{L}_{n}x=\int\mathds{1}\left(h\left(x\right)>c\right)f\left(x\right)d\mathcal{L}_{n}x,\end{split}$
(10)

where, without loss of generality, the $g_{j}\left(x\right)f\left(x\right)$
term is replaced by $f\left(x\right)$ above.

First, consider a special case of the sorting operator where $h\left(x\right)$
is a scalar function, where the directions of differentiation are limited to
$1$. Let $h$ be a $C^{1}$ or Lipschitz function, with $|\nabla
h\left(x\right)|>0,\mathcal{L}_{n}\;a.e.\;x.$ Suppose also $f$ is a integrable
function. Then by the coarea formula Theorem 3.1.2

$\displaystyle\begin{split}\int_{h\left(x\right)>c}f\left(x\right)d\mathcal{L}_{n}x=\int^{\infty}_{c}\left[\int_{h^{-1}\left(c^{\prime}\right)}\frac{f\left(x\right)}{\left\|\nabla
h\left(x\right)\right\|}d\mathcal{H}_{n-1}x\right]d\mathcal{L}_{1}c^{\prime}.\end{split}$

Further, if $\operatorname*{ess\,inf}\left\|\nabla h\left(x\right)\right\|>0,$
and $f$ is integrable, then

$\displaystyle\begin{split}\frac{d}{dc}\left(\int_{h\left(x\right)>c}f\left(x\right)d\mathcal{L}_{n}x\right)=-\int_{h^{-1}\left(c\right)}\frac{f\left(x\right)}{\left\|\nabla
h\left(x\right)\right\|}d\mathcal{H}_{n-1}x\end{split}$

for $\mathcal{L}_{1}\;a.e.\;c$, by the Lebesgue differentiation theorem, where
the derivative is conventionally defined. The right hand side above is also a
derivative in the distributional (weak) sense.

######  Definition 3.2.1.

(Hadamard differentiability) Let $\mathcal{X}$ and $\mathcal{Y}$ be normed
spaces equipped with norms $\|\cdot\|_{\mathcal{X}}$ and
$\|\cdot\|_{\mathcal{Y}}$. Consider the map
$\phi:\mathcal{X}_{\phi}\subset\mathcal{X}\to\mathcal{Y}$. Then $\phi$ is
called Hadamard differentiable at $\theta\in\mathcal{X}_{\phi}$ tangentially
to $\mathcal{X}_{0}\subset\mathcal{X}$, if there is a continuous linear map
$\phi^{\prime}_{\theta}:\mathcal{X}_{0}\to\mathcal{Y}$ such that:

$\displaystyle\begin{split}\left\|\frac{\phi\left(\theta+t_{n}\mathcal{\mathcal{missing}}{x}_{n}\right)-\phi\left(\theta\right)}{t_{n}}-\phi^{\prime}_{\theta}\left(x\right)\right\|_{\mathcal{Y}}\to
0,\;\text{for all}\;t_{n}\to
0\;\text{and}\;\mathcal{\mathcal{missing}}{x}_{n}\to x,\end{split}$ (11)

as $n\to\infty$, where
$\\{\mathcal{\mathcal{missing}}{x}_{n}\\}\subset\mathcal{X}$,
$x\in\mathcal{X}_{0}$, and
$\theta+t_{n}\mathcal{\mathcal{missing}}{x}_{n}\in\mathcal{X}_{\phi}$ for $n$
large enough.

######  Remark 3.2.1.

  1. 1.

When $\mathcal{X}_{0}$ is a linear subspace, by Fang and Santos (2019)
Proposition 2.1, $t_{n}\to 0$ can be replaced by by $t_{n}\downarrow 0$ in the
definition of Hadamard differentiability without loss of generality.

  2. 2.

The derivative $\phi^{\prime}_{h}$ that satisfies equation (11) is necessarily
positively homogeneous of degree one but not necessarily continuous linear.
See Shapiro (1990).

To verify Hadamard differentiability and the corresponding derivative of the
sorting operator, we need to calculate

$\displaystyle\begin{split}\lim_{n\to\infty}\frac{1}{t_{n}}\int\left[\mathds{1}\left(h\left(x\right)+t_{n}\mathcal{\mathcal{missing}}{H}_{n}\left(x\right)>c\right)-\mathds{1}\left(h\left(x\right)>c\right)\right]f\left(x\right)d\mathcal{L}_{n}x,\end{split}$

where $\mathcal{\mathcal{missing}}{H}_{n}\to H$ and $t_{n}\downarrow 0$ as
$n\to\infty$. Intuitively, this limit should be closely related to a type of
integral along the surface $\\{x:h\left(x\right)=c\\}$. The concept of
Hausdorff measure $\mathcal{H}_{k}$ (see definition 3.1.3) essentially defines
area of surface of $k$-dimensional volume in $n$-dimensional space,
$k\in\\{1,\ldots,n\\}$. The important insight of Chernozhukov et al. (2018b)
is represented by the integral under $\mathcal{H}_{n-1}$.

Let $E\subset\mathbb{R}^{n}$ be an open set, $k\in\\{1,2,\ldots,n\\}$,
$h:E\mapsto\mathbb{R}^{k}$ be a $C^{1}$ function, $f:E\mapsto\mathbb{R}$ be a
continuous function. Let $C\left(E\right)$ denote the space of continuous
functions on $E$ equipped with the sup-norm. We need the following technical
assumptions about $h$ and $f$.

######  Assumption 3.2.1.

The function $f$ is continuous with compact support $K_{f}\subset E$.

######  Assumption 3.2.2.

The support $K_{f}$ consists of only regular points of the function $h$.

Assumption 3.2.1 guarantees that $K_{f}\cap\\{x:h\left(x\right)=c^{\prime}\\}$
is close to $K_{f}\cap\\{x:h\left(x\right)=c\\}$ when $c^{\prime}$ is close to
$c$. It can be replaced by alternative conditions, such as those in Assumption
3.2.1′. The purpose of the Assumption 3.2.2 is to guarantee that $h$ is
regular in a neighborhood of $K_{f}$ in order to apply the implicit function
theorem.

######  Assumption 3.2.1′.

For all $c\in h\left(E\right)$, there exists a neighborhood $\mathcal{N}_{c}$
of $c$ such that
$\overline{\bigcup_{c^{\prime}\in\mathcal{N}_{c}}h^{-1}\left(c^{\prime}\right)}\subset
E$ and is bounded. The function $f$ is continuous.

######  Theorem 3.2.1.

Let $h:E\to\mathbb{R}^{k}$ be a $C^{1}$ function, $E$ an open subset of
$\mathbb{R}^{n}$, $k\in\\{1,2,\ldots,n\\}$. Consider (10). Let Assumption
3.2.1 (or 3.2.1′) and Assumption 3.2.2 hold. Let $\mathcal{D}\subset
h\left(E\right)$ be a compact subset. Then, the map
$F\left(h,c\right):C\left(E\right)\to\mathbb{R}$ is Hadamard differentiable
uniformly on $\mathcal{D}$ at $h$ tangentially to $C\left(E\right)$
($C_{b}\left(E\right)$ under Assumption 3.2.1′). The derivative is given by

$\displaystyle\begin{split}F^{\prime}_{h,c}\left(H,0\right)=\sum_{i}\int_{y>\tau_{\neg
i}\left(c\right)}\left[\int_{h^{-1}\left(c^{\prime}\left[i\right]\right)}\frac{H_{i}\left(x\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-k}x\right]d\mathcal{L}_{k-1}y,\end{split}$

where $\tau_{\neg i}\left(c\right)$ denotes the
$\mathbb{R}^{k}\to\mathbb{R}^{k-1}$ coordinate projection except the $i$-th
coordinate, $c^{\prime}\left[i\right]$ is the $k$-dimensional vector such that
$\tau_{\neg i}\left(c^{\prime}\left[i\right]\right)=y$,
$\tau_{i}\left(c^{\prime}\left[i\right]\right)=c_{i}$.

The most common application of Theorem 3.2.1 is when $k=1$, which is listed
separably below as Theorem 3.2.2 with even weaker conditions.

######  Assumption 3.2.2′.

$\exists c\in h\left(E\right)$, $K_{f}\cap h^{-1}\left(c\right)$ consists of
only regular points of $h$.

######  Theorem 3.2.2.

Consider when $k=1$, i.e. when $h$ is a scalar-valued function. Let Assumption
3.2.1 (or 3.2.1′) and Assumption 3.2.2′ hold. Then, there exists a bounded
closed interval $\mathcal{D}\subset h\left(E\right)$, $c\in\mathcal{D}$, such
that the map $F\left(h,c\right):C\left(E\right)\to\mathbb{R}$ is Hadamard
differentiable uniformly on $\mathcal{D}$ at $h$ tangentially to
$C\left(E\right)$ ($C_{b}\left(E\right)$ under Assumption 3.2.1′). The
derivative is given by

$\displaystyle\begin{split}F^{\prime}_{h,c}\left(H,0\right)=\int_{h^{-1}\left(c\right)}\frac{H\left(x\right)f\left(x\right)}{\left\|\nabla
h\left(x\right)\right\|}d\mathcal{H}_{n-1}x.\end{split}$ (12)

Embedded in the proof of Theorem 3.2.2 is the continuity of the derivative of
the sorting operator, expressed in the following lemma, which also handle the
case when $k>1$.

######  Proposition 3.2.3.

Under the conditions in Theorem 3.2.1 or Theorem 3.2.2

$\displaystyle\begin{split}\int_{h^{-1}\left(c\right)}\frac{f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-k}x\end{split}$

is continuous on $h\left(E\right)$ or $\mathcal{D}$.

Proofs of Theorems 3.2.1, Theorem 3.2.2 and Proposition 3.2.3.  We will prove
these three results in several parts. We first prove a pointwise version of
Theorem 3.2.2 for the special case when $k=1$, before proceeding to the more
general case of $k>1$ in Theorem 3.2.1. We finalize by demonstrating the
uniformity of convergence. The following proof is derived under Assumption
3.2.1.

part 1 First consider Theorem 3.2.2. Proposition 3.2.3 can be proved by a
similar derivation in passing.
step 1 We claim that there exists an $\eta>0$ small enough such that for all
$c^{\prime}$ with $|c-c^{\prime}|<\eta$, we can get change of variable
formulas simultaneously. Consider

$\displaystyle\begin{split}\Psi\left(x_{1}^{\prime},\ldots,x_{n}^{\prime},c^{\prime}\right)\coloneq
h\left(x_{1}^{\prime},\ldots,x_{n}^{\prime}\right)-c^{\prime}.\end{split}$

Without loss of generality, we may assume that
$\nabla_{x_{1}}\Psi\left(x_{1},\ldots,x_{n},c\right)$ is full rank. Then by
the implict function theorem (see for example Theorem T.1.9), there exists an
open set $B_{x_{1}}\times B_{x_{2},\ldots,x_{n},c}\subset
U\subset\mathbb{R}^{n+1}$, where $U$ is a neighborhood of
$\left(x_{1},\ldots,x_{n},c\right)$, such that

$\displaystyle\begin{split}B_{x_{1}}&=\left\\{x_{1}^{\prime}\in\mathbb{R}:|x_{1}^{\prime}-x_{1}|<\alpha\right\\}\\\
B_{x_{2},\ldots,x_{n},c}&=\left\\{\left(x_{2}^{\prime},\ldots,x_{n}^{\prime},c^{\prime}\right)\in\mathbb{R}^{n}:|\left(x_{2}^{\prime},\ldots,x_{n}^{\prime},c^{\prime}\right)-\left(x_{2},\ldots,x_{n},c\right)|<\beta\right\\},\end{split}$

and a $C^{1}$ implicit function $\xi\left(\cdot\right)$ defined on
$B_{x_{2},\ldots,x_{n},c}$ such that

$\displaystyle\begin{split}\Psi\left(x_{1}^{\prime},\ldots,x_{n}^{\prime},c^{\prime}\right)=0\Leftrightarrow\left(x_{1}^{\prime}\right)=\xi\left(x_{2}^{\prime},\ldots,x_{n}^{\prime},c^{\prime}\right)\end{split}$

for all $\left(x_{1}^{\prime},\ldots,x_{n}^{\prime},c^{\prime}\right)\in
B_{x_{1}}\times B_{x_{2},\ldots,x_{n},c}$. For all $x\in
h^{-1}\left(c\right)\cap K_{f}$, we can intervals like $B_{x_{1}}\times
B_{x_{2},\ldots,x_{n},c}$ in the above. The implicit function theorem may not
be always about the first dimension. However, an implicit function for some
$x_{m}^{\prime},m\in\\{1,\ldots,n\\}$ always exists by the regular point
assumption 3.2.2′. By the compactness of $h^{-1}\left(c\right)\cap K_{f}$,
there exists a finite open cover denoted as
$\left\\{B_{j}\right\\}\coloneq\left\\{B_{x_{j,1}}\times
B_{x_{j,2},\ldots,x_{j,n}}\right\\}$ of $h^{-1}\left(c\right)\cap K_{f}$. Now,
we claim that there exists $\eta>0$, such that for all $c^{\prime}$ such that
$|c^{\prime}-c|<\eta$, $h^{-1}\left(c^{\prime}\right)\cap
K_{f}\subset\bigcup_{j}B_{j}$. This claim is proven by contradiction. Suppose
$\bigcup_{j}B_{j}$ will not cover $h^{-1}\left(c^{\prime}\right)\cap K_{f}$
for some $c^{\prime}\neq c$, such that $|c^{\prime}-c|<\eta$ where $\eta$ is
arbitrarily chosen. In other words, $\forall\eta>0$, $\exists c^{\prime}$,
$|c^{\prime}-c|<\eta$, such that $h^{-1}\left(c\right)\cap
K_{f}\not\subset\bigcup_{j}B_{j}$. Then there exists a sequence
$\left\\{\left(x_{i},c_{i}\right)\right\\}_{i=1}^{\infty}$ such that

$\displaystyle\begin{split}x_{i}\in h^{-1}\left(c_{i}\right)\cap
K_{f},x_{i}\notin\bigcup_{j}B_{j}.\end{split}$

By the compactness of $h^{-1}\left([a,b]\right)\cap K_{f}$ and the Bolzano-
Weierstrass theorem, there exists a convergent subsequence
$\\{x_{i_{l}}\\}_{l=1}^{\infty}$ such that
$\lim_{l\rightarrow\infty}h\left(x_{i_{l}}\right)=c$ and thus
$\lim_{l\rightarrow\infty}\subset
h^{-1}\left(c\right)\subset\bigcup_{j}B_{j}$. Therefore,
$x_{i_{l}}\in\bigcup_{j}B_{j}$ for all sufficiently large $l$, which is a
contradiction.
step 2 To calculate the change of variables formula analytically, consider

$\displaystyle\begin{split}\psi_{B_{j}}\left(x_{j,2}^{\prime},\ldots,x_{j,n}^{\prime},c^{\prime}\right)=\left(\xi_{B_{j}}\left(x_{j,2}^{\prime},\ldots,x_{j,n}^{\prime},c^{\prime}\right),x_{j,2}^{\prime},\ldots,x_{j,n}^{\prime}\right)^{T},\end{split}$

where $\left(x_{j,2}^{\prime},\ldots,x_{j,n}^{\prime}\right)$ are used by the
implicit function theorem to obtain the local explicit function
$\xi_{B_{j}}\left(\cdot\right)$ for $x_{j,1}^{\prime}$. Then, by the
generalized matrix determinant lemma (for clarity the subscript $j$ is
omitted), as used by Chernozhukov et al. (2018b),

$\displaystyle\begin{split}J\psi_{B_{j}}\left(x^{\prime}_{2,\ldots,n},c^{\prime}\right)&=\det\left(\left(\left(\left[\frac{\partial
h}{\partial
x_{1}}\right]^{-1}\nabla_{x_{2,\ldots,n}}h\right)^{T},I_{n-1}\right)\left(\begin{array}[]{c}\left[\frac{\partial
h}{\partial x_{1}}\right]^{-1}\nabla_{x_{2,\ldots,n}}h\\\
I_{n-1}\end{array}\right)\right)^{\frac{1}{2}}\\\
&=\det\left(I_{n-1}+\left(\left[\frac{\partial h}{\partial
x_{1}}\right]^{-1}\nabla_{x_{2,\ldots,n}}h\right)^{T}\left(\left[\frac{\partial
h}{\partial
x_{1}}\right]^{-1}\nabla_{x_{2,\ldots,n}}h\right)\right)^{\frac{1}{2}}\\\
&=\left(\det\left(I_{n-1}\right)\det\left(I_{1}+\left(\left[\frac{\partial
h}{\partial
x_{1}}\right]^{-1}\nabla_{x_{2,\ldots,n}}h\right)I_{n-1}\left(\left[\frac{\partial
h}{\partial
x_{1}}\right]^{-1}\nabla_{x_{2,\ldots,n}}h\right)^{T}\right)\right)^{\frac{1}{2}}\\\
&=\left(\det\left(\left[\frac{\partial h}{\partial
x_{1}}\right]\left[\frac{\partial h}{\partial
x_{1}}\right]^{T}+\left(\nabla_{x_{2,\ldots,n}}h\right)\left(\nabla_{x_{2,\ldots,n}}h\right)^{T}\right)\right)^{\frac{1}{2}}\left|\det\left(\left[\frac{\partial
h}{\partial x_{1}}\right]^{-1}\right)\right|\\\ &=\left(\det\left(\left(\nabla
h\right)\left(\nabla
h\right)^{T}\right)\right)^{\frac{1}{2}}\left|\det\left(\left[\frac{\partial
h}{\partial
x_{1}}\right]^{-1}\right)\right|=Jh\left|\det\left(\left[\frac{\partial
h}{\partial x_{1}}\right]^{-1}\right)\right|.\end{split}$

In the above, for simplicity, we omit the point at which the derivatives are
calculated, where

$\displaystyle\begin{split}\frac{\partial h}{\partial
x_{1}}&=\frac{\partial}{\partial
x_{1}}h\left(\xi_{B_{j}}\left(x^{\prime}_{2,\ldots,n},c^{\prime}\right),x_{2}^{\prime},\ldots,x_{n}^{\prime}\right)\
\text{and}\\\
\nabla_{x_{2,\ldots,n}}h&=\nabla_{x_{2,\ldots,n}}h\left(\xi_{B_{j}}\left(x^{\prime}_{2,\ldots,n},c^{\prime}\right),x_{2}^{\prime},\ldots,x_{n}^{\prime}\right).\end{split}$

step 3 For a sequence $t_{n}\downarrow 0$ and first let $H_{n}\equiv H$ for
all $n$. By definition of Hadamard differentiability, we need to calculate

$\displaystyle\begin{split}\lim_{n\to\infty}\frac{1}{t_{n}}\left[\int
1\left(h\left(x\right)+t_{n}H\left(x\right)>c\right)f\left(x\right)d\mathcal{L}_{n}x-\int
1\left(h\left(x\right)>c\right)f\left(x\right)d\mathcal{L}_{n}x\right].\end{split}$

By coarea formula Theorem 3.1.2,

$\displaystyle\begin{split}&\frac{1}{t_{n}}\left[\int
1\left(h\left(x\right)+t_{n}H\left(x\right)>c\right)f\left(x\right)d\mathcal{L}_{n}x-\int
1\left(h\left(x\right)>c\right)f\left(x\right)d\mathcal{L}_{n}x\right]\\\
&=\frac{1}{t_{n}}\int\left[\int_{h^{-1}\left(c^{\prime}\right)\cap
K_{f}}\frac{\left(1\left(c^{\prime}+t_{n}H\left(x\right)>c\right)-1\left(c^{\prime}>c\right)\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x\right]d\mathcal{L}_{1}c^{\prime}\\\
&=\int_{c-t_{n}M}^{c+t_{n}M}\left[\frac{1}{t_{n}}\int_{h^{-1}\left(c^{\prime}\right)\cap
K_{f}}\frac{\left(1\left(c^{\prime}+t_{n}H\left(x\right)>c\right)-1\left(c^{\prime}>c\right)\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x\right]d\mathcal{L}_{1}c^{\prime},\end{split}$

where $M=\max_{x\in K_{f}}|H\left(x\right)|<+\infty$. Then, we can apply the
area formula Theorem 3.1.1 to calculate

$\displaystyle\begin{split}&\frac{1}{t_{n}}\int\left[\int_{h^{-1}\left(c^{\prime}\right)\cap
B_{j}\cap
K_{f}}\frac{\left[1\left(c^{\prime}+t_{n}H\left(x\right)>c\right)-1\left(c^{\prime}>c\right)\right]f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x\right]d\mathcal{L}_{1}c^{\prime}\\\
&=\frac{1}{t_{n}}\int\left[\int_{B_{x_{j,2},\ldots,x_{j,n}}}\frac{\left[1\left(c^{\prime}+t_{n}H\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)>c\right)-1\left(c^{\prime}>c\right)\right]f\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)}{\left|\text{det}\left(\frac{\partial}{\partial
x_{1}}h\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)\right)\right|}d\mathcal{L}_{n-1}x\right]d\mathcal{L}_{1}c^{\prime}.\\\
\end{split}$

Next by the Fubini-Tonelli theorem, the above is equal to

$\displaystyle\begin{split}\int_{B_{x_{j,2},\ldots,x_{j,n}}}\left[\frac{1}{t_{n}}\int\frac{\left[1\left(c^{\prime}+t_{n}H\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)>c\right)-1\left(c^{\prime}>c\right)\right]f\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)}{\left|\text{det}\left(\frac{\partial}{\partial
x_{1}}h\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)\right)\right|}d\mathcal{L}_{1}c^{\prime}\right]d\mathcal{L}_{n-1}x.\end{split}$

Since

$\displaystyle\begin{split}&\frac{1}{t_{n}}\int\left[1\left(c^{\prime}+t_{n}H\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)>c\right)-1\left(c^{\prime}>c\right)\right]d\mathcal{L}_{1}c^{\prime}\\\
&=\frac{1}{t_{n}}\int_{c-t_{n}M}^{c+t_{n}M}\left[1\left(c^{\prime}+t_{n}H\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)>c\right)-1\left(c^{\prime}>c\right)\right]d\mathcal{L}_{1}c^{\prime}\to
H\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c\right)\right),\end{split}$

by the dominated convergence theorem (DCT) and with the help of the partition
of unity theorem T.1.11 (as in Chernozhukov et al. (2018b)), and by the area
formula again, we get

$\displaystyle\begin{split}\lim_{n\rightarrow\infty}\frac{1}{t_{n}}\left[1\left(h\left(x\right)+t_{n}H\left(x\right)>c\right)-1\left(h\left(x\right)>c\right)\right]f\left(x\right)d\mathcal{L}_{n}x=\int_{h^{-1}\left(c\right)}\frac{H\left(x\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x.\end{split}$

step 4 Now consider functions $H\left(x\right)+\zeta$, for arbitrary
$\zeta>0$. Since by assumption $\sup_{x\in
E}|H_{n}\left(x\right)-H\left(x\right)|\to 0$, for all $\zeta>0$, for
sufficiently large $n$, $H\left(x\right)+\zeta>H_{n}\left(x\right)$ for all
$x$. Therefore,

$\displaystyle\begin{split}\limsup_{n\rightarrow\infty}\frac{F\left(h+t_{n}H_{n},c\right)-F\left(h,c\right)}{t_{n}}\leq&\lim_{n\rightarrow\infty}\frac{F\left(h+t_{n}\left(H+\zeta\right),c\right)-F\left(h,c\right)}{t_{n}}\\\
=&\int_{h^{-1}\left(c\right)}\frac{\left(H\left(x\right)+\zeta\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x.\end{split}$

Similarly,

$\displaystyle\begin{split}\liminf_{n\rightarrow\infty}\frac{F\left(h+t_{n}H_{n},c\right)-F\left(h,c\right)}{t_{n}}\geq&\lim_{n\rightarrow\infty}\frac{F\left(h+t_{n}\left(H-\zeta\right),c\right)-F\left(h,c\right)}{t_{n}}\\\
=&\int_{h^{-1}\left(c\right)}\frac{\left(H\left(x\right)-\zeta\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x.\end{split}$

By the Hölder inequality (integration by Hausdorff measure is also in the
Lebesgue sense):

$\displaystyle\begin{split}\int_{h^{-1}\left(c\right)}\frac{\left|H\left(x\right)-H^{\prime}\left(x\right)\right|f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x\leq\sup_{x\in
E}|H\left(x\right)-H^{\prime}\left(x\right)|\int_{h^{-1}\left(c\right)}\left|\frac{f\left(x\right)}{Jh\left(x\right)}\right|d\mathcal{H}_{n-1}x.\end{split}$

Now by the arbitrariness of $\zeta$,

$\displaystyle\begin{split}\lim_{n\rightarrow\infty}\frac{F\left(h+t_{n}\left(H-\zeta\right),c\right)-F\left(h,c\right)}{t_{n}}=\int_{h^{-1}\left(c\right)}\frac{\left(H\left(x\right)-\zeta\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x.\end{split}$

step 5 Now we can also prove Proposition 3.2.3. Note that because the above
proof techniques of step 1 to step 3, including the area formula, partition of
unity, and generalized matrix determinant lemma, all work for $k>1$. As a
result, the proof is essentially a reconstruction of the proof of Theorem
3.2.2. Here, we only need to point out that

$\displaystyle\begin{split}\lim_{c^{\prime}\to
c}\int_{B_{x_{j,2},\ldots,x_{j,n}}}&\frac{f\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)}{\left|\text{det}\left(\frac{\partial}{\partial
x_{1}}h\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c^{\prime}\right)\right)\right)\right|}d\mathcal{L}_{n-1}x\\\
&=\int_{B_{x_{j,2},\ldots,x_{j,n}}}\frac{f\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c\right)\right)}{\left|\text{det}\left(\frac{\partial}{\partial
x_{1}}h\left(\psi_{B_{j}}\left(x_{2,\ldots,n},c\right)\right)\right)\right|}d\mathcal{L}_{n-1}x.\end{split}$

part 2 For $k>1$, we still have, by the coarea formula

$\displaystyle\begin{split}F\left(h,c\right)=\int_{h\left(x\right)>c}f\left(x\right)d\mathcal{L}_{n}x=\int_{c^{\prime}>c}\left[\int_{h^{-1}\left(c^{\prime}\right)}\frac{f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}\right]d\mathcal{L}_{k}c^{\prime}.\end{split}$

So for all $n$ large enough

$\displaystyle\begin{split}&\frac{1}{t_{n}}\int\left[1\left(h\left(x\right)+t_{n}H_{n}\left(x\right)>c\right)-1\left(h\left(x\right)>c\right)\right]f\left(x\right)d\mathcal{L}_{n}x\\\
&=\frac{1}{t_{n}}\int\left[\int_{h^{-1}\left(c^{\prime}\right)\cap
K_{f}}\frac{\left[1\left(c^{\prime}+t_{n}H_{n}\left(x\right)>c\right)-1\left(c^{\prime}>c\right)\right]f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-k}x\right]d\mathcal{L}_{k}c^{\prime}\end{split}$

By the telescoping identity of higher order expansion,

$\displaystyle\begin{split}\prod_{i=1}^{k}a_{i}^{\prime}-\prod_{i=1}^{k}a_{i}=\sum_{i=1}^{k}\left(a_{i}^{\prime}-a_{i}\right)\prod_{l\neq
i}a_{l}+\sum_{i\neq
j}\left(a_{i}^{\prime}-a_{i}\right)\left(a_{j}^{\prime}-a_{j}\right)\prod_{l\neq
i,l\neq
j}a_{l}+\cdots+\prod_{i=1}^{k}\left(a_{i}^{\prime}-a_{i}\right).\end{split}$

Now by a proof procedure similar to that of Theorem 3.2.2, the first order
term of the difference becomes

$\displaystyle\begin{split}&\sum_{i}\frac{1}{t_{n}}\int\left[\int_{h^{-1}\left(c^{\prime}\right)\cap
K_{f}}\frac{\left[1\left(c_{i}^{\prime}+t_{n}H_{n,i}\left(x\right)>c_{i}\right)-1\left(c^{\prime}_{i}>c_{i}\right)\right]\prod_{l\neq
i}1\left(c_{l}^{\prime}>c_{l}\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-k}x\right]d\mathcal{L}_{k}c^{\prime}\\\
&=\sum_{i}\sum_{l_{i}}\int_{y>\tau_{\neg i}\left(c\right)}\int_{B_{\neg
l_{i}}}d\mathcal{L}_{n-k}xdL_{k-1}y\\\
&\left[\int\frac{\left[1\left(c_{i}^{\prime}+t_{n}H_{n,i}\left(\psi_{B_{l_{i}}}\left(x,c^{\prime}\right)\right)>c_{i}\right)-1\left(c^{\prime}_{i}>c_{i}\right)\right]f\left(\psi_{B_{l_{i}}}\left(x,c^{\prime}\right)\right)\rho\left(\psi_{B_{l_{i}}}\left(x,c^{\prime}\right)\right)}{\left|\det\left(\frac{\partial}{\partial
x_{l_{i}}}h\left(\psi_{B_{l_{i}}}\left(x,c^{\prime}\right)\right)\right)\right|}\frac{1}{t_{n}}d\mathcal{L}_{1}c_{i}^{\prime}\right].\end{split}$

where $\rho\left(\psi_{B_{l_{i}}}\left(x,c^{\prime}\right)\right)$ is the
partition of unity, and $x_{l_{i}}$ denotes that $x_{l_{i}}$ is picked for
locally explicit function for change of variables by the implicit function
theorem We also note that in the above $y=\tau_{\neg
i}\left(c^{\prime}\right)$, and
$c^{\prime}_{i}=\tau_{i}\left(c^{\prime}\right)$ and we use the fact that

$\displaystyle\begin{split}1\left(c^{\prime}+t_{n}H_{n}\left(x\right)>c\right)=\prod_{i=1}^{k}1\left(c_{i}^{\prime}+t_{n}H_{n,i}\left(x\right)>c_{i}\right)\
\text{and}\
1\left(c^{\prime}>c\right)=\prod_{i=1}^{k}1\left(c^{\prime}_{i}>c_{i}\right).\end{split}$

Then by DCT and the area formula again, we obtain the limit of the first order
difference as

$\displaystyle\begin{split}\sum_{i}\int\left[\int_{h^{-1}\left(c^{\prime}[i]\right)}\frac{H_{j}\left(x\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-k}x\right]d\mathcal{L}_{k-1}y.\end{split}$

The convergence of the first order term also implies that the second and
higher order terms of the difference should vanish eventually.
part 3 By part 1 and part 2, we only need to consider the $k=1$ case since the
$k>1$ case is similar. Let $\\{c_{n}\\}_{n=1}^{\infty}$ be a sequence such
that $\lim_{n\rightarrow\infty}c_{n}=c$. Consider

$\displaystyle\begin{split}\lim_{n\rightarrow\infty}&\frac{1}{t_{n}}\left[F\left(h+t_{n}H_{n},c_{n}\right)-F\left(h,c_{n}\right)\right]\\\
&=\lim_{n\rightarrow\infty}\frac{1}{t_{n}}\int\left[1\left(h\left(x\right)+t_{n}H_{n}\left(x\right)>c_{n}\right)-1\left(h\left(x\right)>c_{n}\right)-\right]f\left(x\right)d\mathcal{L}_{n}x.\end{split}$

The proof in part 1 shows that we need to calculate, for $M=\sup_{x\in
K_{f}}|H\left(x\right)|$,

$\displaystyle\begin{split}&\frac{1}{t_{n}}\int_{c-t_{n}M-|c-c_{n}|}^{c+t_{n}M+|c-c_{n}|}\left[1\left(c^{\prime}+t_{n}H\left(\psi_{B_{j}}\left(\cdot,c^{\prime}\right)>c_{n}\right)\right)-1\left(c^{\prime}>c_{n}\right)\right]d\mathcal{L}_{1}c^{\prime}.\end{split}$

Note that

$\displaystyle\begin{split}\frac{1}{t_{n}}\int\left[1\left(c^{\prime}+t_{n}A+c-c_{n}>c\right)-1\left(c^{\prime}+c-c_{n}>c\right)\right]d\mathcal{L}_{1}c^{\prime}=A.\end{split}$

we can obtain

$\displaystyle\begin{split}\lim_{n\rightarrow\infty}\frac{1}{t_{n}}\int_{c-t_{n}M-|c-c_{n}|}^{c+t_{n}M+|c-c_{n}|}\left[1\left(c^{\prime}+t_{n}H\left(\psi_{B_{j}}\left(\cdot,c^{\prime}\right)>c_{n}\right)\right)-1\left(c^{\prime}>c_{n}\right)\right]d\mathcal{L}_{1}c^{\prime}.\end{split}$

by simple upper and lower bound of
$H\left(\psi_{B_{j}}\left(\cdot,c^{\prime}\right)\right)$ on
$\left[c-t_{n}M-|c-c_{n}|,c+t_{n}M+|c-c_{n}|\right]$. So we obtain, following
the idea in Chernozhukov et al. (2018b), that the limit in the calculation of
the Hadamard derivative actually converges continuously. By Lemma T.1.12, we
get that the Hadamard derivative can be taken in a uniform sense. In other
words, let $\mathcal{D}\in h\left(E\right)$ , then we have

$\displaystyle\begin{split}\lim_{n\rightarrow\infty}\sup_{c\in\mathcal{D}}\left|\frac{1}{t_{n}}\int\left[1\left(h\left(x\right)+t_{n}H_{n}\left(x\right)>c\right)-1\left(h\left(x\right)>c\right)\right]f\left(x\right)d\mathcal{L}_{n}x-\int_{h^{-1}\left(c\right)}\frac{H\left(x\right)f\left(x\right)}{Jh\left(x\right)}d\mathcal{H}_{n-1}x\right|=0.\end{split}$

This finishes the proof of Theorem 3.2.1.

###  3.3 Binary treatment allocation and the ROC curve

In this subsection, we derive asymptotic pointwise and uniform distributions
for binary treatment allocation under a resource constraint and for the
estimated ROC curve. Here, using Hadamard differentiability results from
subsection 3.2, we can directly analyze the plug-in two-step estimator of the
value function for the constraint optimal allocation problems. Our strategy is
concise. The functional delta methods alone (see for example van der Vaart and
Wellner (2023) and Fang and Santos (2019)) are sufficient to obtain asymptotic
results. The discussions in this subsection are conducted under the classical
empirical process theory in the Hoffman-Jørgensen-Dudley sense. The most
applicable result in this subsection might be a computationally feasible delta
method for bootstrap in probability of the plug-in two-step ROC estimator
which is commonly used in computer science and other fields.

Alternative theories can also be developed under other settings from different
perspectives. In subsection 4.3, we visit the recent double/debiased machine
learning methodology for unconstrained multi-classification problems.
Double/debiased method under resource constraints can also be developed. We
also note that the results in this subsection and in subsection 4.3 can be
further improved to demonstrate semiparametric efficiency, which is analyzed
in a follow-up manuscript Feng et al. (2024).

In binary applications of optimal constrained treatment allocation, we
consider

$\displaystyle\begin{split}\max_{\phi\in\Phi}\mathbb{E}&\left[Y_{1}\phi\left(X\right)+Y_{0}\left(1-\phi\left(X\right)\right)\right],\\\
s.t.\;\mathbb{E}&\left[Z_{1}\phi\left(X\right)+Z_{0}\left(1-\phi\left(X\right)\right)\right]\leq\alpha,\end{split}$

where $\Phi$ is the set of critical functions when $J=1$. Obviously, the
problem above is equivalent to

$\displaystyle\begin{split}\max_{\phi\in\Phi}\mathbb{E}&\left[\left(Y_{1}-Y_{0}\right)\phi\left(X\right)+Y_{0}\right],\\\
s.t.\;\mathbb{E}&\left[\left(Z_{1}-Z_{0}\right)\phi\left(X\right)+Z_{0}\right]\leq\alpha.\end{split}$
(13)

We will use the definition in (13) hereafter. By the classical Neyman-Pearson
lemma (see, for example Theorem 3.2.1 in Lehmann and Romano (2022)), for
$\alpha$ allowing feasible $\phi$ but not necessary to be binding, the
solution of the population optimization problem (13) exists and satisfies

$\displaystyle\begin{split}\phi\left(x\right)=\left\\{\begin{array}[]{cc}1,&\text{when}\
\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)>k\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right),\\\
0,&\text{when}\
\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)<k\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right),\end{array}\right.\end{split}$

for some constant $k$, where
$g_{1}\left(x\right)=\mathbb{E}\left(Y_{1}|X=x\right)$,
$g_{0}\left(x\right)=\mathbb{E}\left(Y_{0}|X=x\right)$,
$c_{1}\left(x\right)=\mathbb{E}\left(Z_{1}|X=x\right)$ and
$c_{0}\left(x\right)=\mathbb{E}\left(Z_{0}|X=x\right)$. When the fiber
$\left\\{x:\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)=k\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\right\\}$
is of zero probability mass, we can express the constraint and the value
function of (13) as

$\displaystyle\begin{split}\alpha\left(k\right)&=Q\left[\left(z_{1}-z_{0}\right)1\left(\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)>k\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\right)+z_{0}\right]\leq\alpha,\\\
\beta\left(k\right)&=Q\left[\left(y_{1}-y_{0}\right)1\left(\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)>k\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\right)+y_{0}\right].\end{split}$
(14)

Here, we adopt the functional notation where
$\left(Y_{1},Y_{0},Z_{1},Z_{0},X\right)\sim Q$, $X\sim\mu$. The Hadamard
differentiability results established in subsection 3.2 allow us to derive
asymptotic distribution of the sorting operator expression in (14) by the
functional delta method. Denote $\ell^{\infty}\left(E\right)$ as the set of
bounded real-valued functions on a set $E$. We need the following assumptions
to validate a functional delta method. Here, we largely adopt the styles in
Chernozhukov et al. (2018b).

######  Assumption 3.3.1.

The random variables $\left(Y_{1},Y_{0},Z_{1},Z_{0},X\right)\sim Q$,
$X\sim\mu$, where $\mu$ is absolutely continuous with respect to the
$n$-dimensional Lebesgue measure. The density $\mu^{\prime}$ is continuous on
an open set $E\subset\mathbb{R}^{n}$ and
$\operatorname{supp}{\mu^{\prime}}=K_{\mu^{\prime}}\subset E$.
$\left(Y_{1},Y_{0},Z_{1},Z_{0}\right)$ is bounded and $Z_{1}>Z_{0}$.

######  Assumption 3.3.2.

The estimators
$\left(\hat{g}_{0}\left(x\right),\hat{g}_{1}\left(x\right),\hat{c}_{0}\left(x\right),\hat{c}_{1}\left(x\right)\right)^{T}$
satisfy

$\displaystyle\begin{split}r_{n}\left(\left(\hat{g}_{0}\left(x\right),\hat{g}_{1}\left(x\right),\hat{c}_{0}\left(x\right),\hat{c}_{1}\left(x\right)\right)^{T}-\left(g^{\star}_{0}\left(x\right),g^{\star}_{1}\left(x\right),c^{\star}_{0}\left(x\right),c^{\star}_{1}\left(x\right)\right)^{T}\right)\rightsquigarrow\mathbb{H}\text{
in }{\ell\left(E\right)}^{4},\end{split}$

where $r_{n}\to\infty$ as $n\to\infty$, $\mathbb{H}$ is separable and its
support is included in ${C\left(E\right)}^{4}$.

######  Assumption 3.3.3.

The population limits satisfy
$\left(g^{\star}_{0}\left(\cdot\right),g^{\star}_{1}\left(\cdot\right),c^{\star}_{0}\left(\cdot\right),c^{\star}_{1}\left(\cdot\right)\right)\in{C^{1}\left(E\right)}^{4}$,
$c^{\star}_{1}\left(x\right)>c^{\star}_{0}\left(x\right)$, and $0$ is a
regular value of

$\displaystyle\begin{split}\Delta^{\star}\left(x;k\right)\coloneqq\left(g^{\star}_{1}\left(x\right)-g^{\star}_{0}\left(x\right)\right)-k\left(c^{\star}_{1}\left(x\right)-c^{\star}_{0}\left(x\right)\right),\end{split}$

where $k\in\mathcal{D}$, $\mathcal{D}\subset\mathbb{R}$ a bounded closed
interval.

######  Assumption 3.3.4.

Let
$\left(g^{\star}_{0}\left(x\right),g^{\star}_{1}\left(x\right),c^{\star}_{0}\left(x\right),c^{\star}_{1}\left(x\right)\right)^{T}\in\mathcal{G}$
and
$\left(\hat{g}_{0}\left(x\right),\hat{g}_{1}\left(x\right),\hat{c}_{0}\left(x\right),\hat{c}_{1}\left(x\right)\right)^{T}\in\mathcal{G}$
with outer probability tends to $1$, where
$\mathcal{G}\subset{C\left(E\right)}^{4}$. The function class

$\displaystyle\begin{split}\mathcal{F}\coloneqq\left\\{1\left(\left(g^{\prime}_{1}\left(x\right)-g^{\prime}_{0}\left(x\right)\right)>k\left(c^{\prime}_{1}\left(x\right)-c^{\prime}_{0}\left(x\right)\right)\right):\left(g^{\prime}_{0}\left(\cdot\right),g^{\prime}_{1}\left(\cdot\right),c^{\prime}_{0}\left(\cdot\right),c^{\prime}_{1}\left(\cdot\right)\right)\in\mathcal{G},k\in\mathcal{D}\right\\}\end{split}$

is Donsker, and the estimators and the empirical process converge jointly,
.i.e.

$\displaystyle\begin{split}t_{n}\left[\left(\begin{array}[]{c}\hat{g}_{0}\left(x\right)\\\
\hat{g}_{1}\left(x\right)\\\ \hat{c}_{0}\left(x\right)\\\
\hat{c}_{1}\left(x\right)\end{array}\right)-\left(\begin{array}[]{c}\hat{g}_{0}\left(x\right)\\\
\hat{g}_{1}\left(x\right)\\\ \hat{c}_{0}\left(x\right)\\\
\hat{c}_{1}\left(x\right)\end{array}\right),\mathbb{Q}_{n}-Q\right]\rightsquigarrow\left(t_{\Delta}\mathbb{H},t_{Q}\mathbb{Q}\right)\text{
in
}{C\left(E\right)}^{4}\times\ell^{\infty}\left(\mathcal{F}\right).\end{split}$

In the above, $t_{n}=\min\\{r_{n},\sqrt{n}\\}$ and
$\lim_{n\in\infty}\frac{t_{n}}{r_{n}}=t_{\Delta}\in\left[0,1\right]$,
$\lim_{n\to\infty}\frac{t_{n}}{\sqrt{n}}=t_{Q}\in\left[0,1\right]$.

######  Theorem 3.3.1.

Under Assumption 3.3.1 to 3.3.4, and assume that there exists a constant
$\epsilon>0$, such that

$\displaystyle\begin{split}\int_{\Delta^{\star}\left(x;k\right)}\frac{\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\left(c^{\star}_{1}\left(x\right)-c^{\star}_{0}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\right)\|}d\mathcal{H}_{n-1}x>\epsilon\end{split}$

for all $k\in\mathcal{D}$. Then, as a stochastic process on compact
$\Lambda^{\prime}\subsetneq\overset{\circ}{\Lambda}$, $\Lambda\coloneqq
Q\left[\left(z_{1}-z_{0}\right)1\left(\Delta\left(x;\mathcal{D}\right)>0\right)\right]$,

$\displaystyle\begin{split}&t_{n}\left(\beta\left(\mathbb{Q}_{n},\hat{\Delta},\alpha\right)-\beta\left(Q,\Delta^{\star},\alpha\right)\right)\rightsquigarrow\Biggl{\\{}t_{Q}\mathbb{Q}\left[\left(y_{1}-y_{0}\right)1\left(\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)>0\right)+y_{0}\right]\\\
&+t_{\Delta}\Biggl{[}\int_{\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)=0}\frac{\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)\left(\mathbb{H}_{1}-\mathbb{H}_{0}\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)\|}d\mathcal{H}_{n-1}x\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad-\int_{\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)=0}\frac{\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)\left(\mathbb{H}_{3}-\mathbb{H}_{2}\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)\|}d\mathcal{H}_{n-1}x\Biggl{]}\Biggl{\\}}\\\
&-\frac{f_{\beta}\left(Q,\Delta^{\star},k\left(Q,\Delta^{\star},\alpha\right)\right)}{f_{\alpha}\left(Q,\Delta^{\star},k\left(Q,\Delta^{\star},\alpha\right)\right)}\Biggl{\\{}t_{Q}\mathbb{Q}\left[\left(z_{1}-z_{0}\right)1\left(\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)>0\right)\right)+z_{0}\right]\\\
&+t_{\Delta}\Biggl{[}\int_{\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)=0}\frac{\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\left(\mathbb{H}_{1}-\mathbb{H}_{0}\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)\|}d\mathcal{H}_{n-1}x\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad-\int_{\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)=0}\frac{\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\left(\mathbb{H}_{3}-\mathbb{H}_{2}\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\left(Q,\Delta^{\star},\alpha\right)\right)\|}d\mathcal{H}_{n-1}x\Biggl{]}\Biggl{\\}},\end{split}$
(15)

where
$\left(\mathbb{H}_{0},\mathbb{H}_{1},\mathbb{H}_{2},\mathbb{H}_{3}\right)^{T}=\mathbb{H}$;

$\displaystyle\begin{split}f_{\beta}\left(Q,\Delta^{\star},k\right)&\coloneqq\frac{d\beta\left(Q,\Delta^{\star},k\right)}{dk}=-\int_{\Delta^{\star}\left(x;k\right)=0}\frac{\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)\left(c^{\star}_{1}\left(x\right)-c^{\star}_{0}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\right)\|}d\mathcal{H}_{n-1}x,\\\
f_{\alpha}\left(Q,\Delta^{\star},k\right)&\coloneqq\frac{d\alpha\left(Q,\Delta^{\star},k\right)}{dk}=-\int_{\Delta^{\star}\left(x;k\right)=0}\frac{\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\left(c^{\star}_{1}\left(x\right)-c^{\star}_{0}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\right)\|}d\mathcal{H}_{n-1}x.\end{split}$

The notation $\Delta$ ($\hat{\Delta},\Delta^{\star}$) denotes
$\left(g_{0}\left(\cdot\right),g_{1}\left(\cdot\right),c_{0}\left(\cdot\right),c_{1}\left(\cdot\right)\right)$
(their estimators and the estimators’ limits), and

$\displaystyle\begin{split}\beta\left(Q,\Delta,\alpha\right)\coloneqq\beta\left(Q,\Delta,k\left(Q,\Delta,\alpha\right)\right)=Q\left[\left(y_{1}-y_{0}\right)1\left(\Delta\left(x;k\left(Q,\Delta,\alpha\right)\right)>0\right)\right],\end{split}$

$k\left(Q,\Delta,\alpha\right)=\inf\left\\{k\in\mathbb{R}:\alpha\left(Q,\Delta,k\right)\leq\alpha\right\\}$111The
meaning of $\beta\left(Q,\Delta,k\right)$ and $\alpha\left(Q,\Delta,k\right)$
is clear in the context..

Proof of Theorem 3.3.1.  Note that under Assumption 3.3.1 and Assumption
3.3.3, we can evoke Theorem 3.2.1; under Assumption 3.3.4 we can evoke Lemma
A.2 in Chernozhukov et al. (2018b). Also by the chain rule of Hadamard
derivative (Lemma 3.10.3 in van der Vaart and Wellner (2023)),

$\displaystyle\begin{split}&\alpha^{\prime}_{Q,\Delta^{\star},k}\left(\mathcal{Q},H,0\right)=\mathcal{Q}\left[\left(z_{1}-z_{0}\right)1\left(\Delta^{\star}\left(x;k\right)>0\right)+z_{0}\right]\\\
&+\Biggl{[}\int_{\Delta^{\star}\left(x;k\right)=0}\frac{\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\left(H_{1}\left(x\right)-H_{0}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x,k\right)\|}d\mathcal{H}_{n-1}x\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad-\int_{\Delta^{\star}\left(x;k\right)=0}\frac{\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\left(H_{3}\left(x\right)-H_{2}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x,k\right)\|}d\mathcal{H}_{n-1}x\Biggl{]}.\end{split}$

By the assumption that

$\displaystyle\begin{split}\int_{\Delta^{\star}\left(x;k\right)}\frac{\left(c_{1}\left(x\right)-c_{0}\left(x\right)\right)\left(c^{\star}_{1}\left(x\right)-c^{\star}_{0}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x;k\right)\|}d\mathcal{H}_{n-1}x\end{split}$

is uniformly bounded away from zero, the Hadamard differentiability of the
inverse map in Lemma 3.10.24 of van der Vaart and Wellner (2023) and the chain
rule again imply that

$\displaystyle\begin{split}k^{\prime}_{Q,\Delta^{\star},\alpha}\left(\mathcal{Q},H,0\right)=\frac{\alpha^{\prime}_{Q,\Delta^{\star},k}\left(\mathcal{Q},H,0\right)}{f_{\alpha}\left(Q,\Delta^{\star},k\left(Q,\Delta^{\star},\alpha\right)\right)},\end{split}$

where the Hadamard differentiability is tangential to $\mathbf{Q}\times
C\left(E\right)$, $\mathbf{Q}\subset\ell^{\infty}\left(\mathcal{F}\right)$
consists of elements that are uniformly continuous on $\mathcal{F}$ with
respect to $L^{2}\left(Q\right)$ norm.

By exactly the same calculation, we can also get

$\displaystyle\begin{split}&\beta^{\prime}_{Q,\Delta^{\star},k}\left(\mathcal{Q},H,0\right)=\mathcal{Q}\left[\left(y_{1}-y_{0}\right)1\left(\Delta^{\star}\left(x;k\right)>0\right)+y_{0}\right]\\\
&+\Biggl{[}\int_{\Delta^{\star}\left(x;k\right)=0}\frac{\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)\left(H_{1}\left(x\right)-H_{0}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x,k\right)\|}d\mathcal{H}_{n-1}x\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad-\int_{\Delta^{\star}\left(x;k\right)=0}\frac{\left(g_{1}\left(x\right)-g_{0}\left(x\right)\right)\left(H_{3}\left(x\right)-H_{2}\left(x\right)\right)\mu^{\prime}\left(x\right)}{\|\nabla\Delta^{\star}\left(x,k\right)\|}d\mathcal{H}_{n-1}x\Biggl{]}.\end{split}$

By the chain rule the third time, there is

$\displaystyle\begin{split}\beta^{\prime}_{Q,\Delta^{\star},\alpha}\left(\mathcal{Q},H,0\right)=\beta^{\prime}_{Q,\Delta^{\star},k}\left(\mathcal{Q},H,0\right)\bigg{|}_{k=k\left(Q,\Delta^{\star},\alpha\right)}-\frac{f_{\beta}\left(Q,\Delta^{\star},k\left(Q,\Delta^{\star},\alpha\right)\right)}{f_{\alpha}\left(Q,\Delta^{\star},k\left(Q,\Delta^{\star},\alpha\right)\right)}\alpha^{\prime}_{q,\Delta^{\star},k}\left(\mathcal{Q},H,0\right)\bigg{|}_{k=k\left(Q,\Delta^{\star},\alpha\right)}.\end{split}$

Now, (LABEL:main_asymptotic_formula) follows from Theorem 3.10.4 in van der
Vaart and Wellner (2023).

A useful special case of (13) is when $Y_{1}\in\\{0,1\\}$, $Y_{0}=Z_{0}=0$,
$Z_{1}=1-Y_{1}$, and $g_{0}=c_{0}\equiv 0$,
$g_{1}\left(x\right)=p\left(x\right)$, $c_{1}\left(x\right)=1-p\left(x\right)$
where $p\left(x\right)=\mathbb{E}\left[Y|\ X=x\right]$. This special case,
i.e.

$\displaystyle\begin{split}\max_{\phi\in\Phi}\mathbb{E}\left[Y\phi\left(X\right)\right],\;s.t.\;\mathbb{E}\left[\left(1-Y\right)\phi\left(X\right)\right]\leq\alpha.\end{split}$

is closely related to the receiver operating characteristic (ROC) curve whose
population definition is

$\displaystyle\begin{split}\beta\left(\alpha\right)\coloneqq\max_{\phi\in\Phi}\frac{\mathbb{E}\left[Y\phi\left(X\right)\right]}{\mathbb{E}Y},\;s.t.\;\frac{\mathbb{E}\left[\left(1-Y\right)\phi\left(X\right)\right]}{\mathbb{E}\left(1-Y\right)}\leq\alpha.\end{split}$

In the following presentation of the uniform asymptotic distribution of the
ROC curve, we differentiate between misspecified models and correctly
specified models. The limit of misspecified models is essentially a direct
application of the general results in Theorem 3.3.1. When the parametric
propensity score model is correctly specified, or when it is estimated by
nonparametric techniques with a sufficiently fast rate of convergence, it will
be shown that the first stage estimation of the propensity score model has no
impact on the asymptotic distribution of the ROC curve. This property
simplifies the inference procedure when the propensity score is
nonparametrically estimated or correctly parametrically specified. In
particular, it is not necessary to reestimate the propensity score model in a
bootstrap procedure.

######  Corollary 3.3.2.

Under the conditions in Theorem 3.3.1, but let
$\left(g_{0}\left(x\right),g_{1}\left(x\right),c_{0}\left(x\right),c_{1}\left(x\right)\right)=\left(0,p\left(x\right),0,1-p\left(x\right)\right)$
(and the exact expression in Assumption 3.3.1 to 3.3.4 should adopt to this
change). Then we have

$\displaystyle\begin{split}&t_{n}\left(\beta\left(\mathbb{Q}_{n},\hat{p},\alpha\right)-\beta\left(Q,p^{\star},\alpha\right)\right)\rightsquigarrow\frac{1}{p}\Biggl{\\{}t_{Q}\mathbb{Q}\left[y\left(1\left(p^{\star}\left(x\right)>k\left(Q,p^{\star},\alpha\right)\right)-\beta\left(Q,p^{\star},\alpha\right)\right)\right]\\\
&+t_{\Delta}\int_{p^{\star-1}\left(k\left(Q,p^{\star},\alpha\right)\right)}\frac{p\left(x\right)\mathbb{H}\left(x\right)\mu^{\prime}\left(x\right)}{\|\nabla
p^{\star}\left(x\right)\|}d\mathcal{H}_{n-1}x\Biggl{\\}}-\frac{1}{p}\frac{f_{\beta}\left(Q,p^{\star},k\left(Q,p^{\star},\alpha\right)\right)}{f_{\alpha}\left(Q,p^{\star},k\left(Q,p^{\star},\alpha\right)\right)}\Biggl{\\{}\\\
&t_{Q}\mathbb{Q}\left[\left(1-y\right)\left(1\left(p^{\star}\left(x\right)>k\left(Q,p^{\star},\alpha\right)\right)-\alpha\right)\right]+t_{\Delta}\int_{p^{\star-1}\left(k\left(Q,p^{\star},\alpha\right)\right)}\frac{p\left(x\right)\mathbb{H}\left(x\right)\mu^{\prime}\left(x\right)}{\|\nabla
p^{\star}\left(x\right)\|}d\mathcal{H}_{n-1}x\Biggl{\\}}\end{split}$

on compact $\Lambda^{\prime}\subsetneq\overset{\circ}{\Lambda}$,
$\Lambda\coloneqq\frac{Q\left[\left(1-y\right)1\left(p^{\star}\left(x\right)>\mathcal{D}\right)\right]}{Q\left(1-y\right)}$.
Specially, when $p^{\star}$ is correctly, i.e.
$p^{\star}\left(x\right)=p\left(x\right)$, then we get

$\displaystyle\begin{split}t_{n}\left(\beta\left(\mathbb{Q}_{n},\hat{p},\alpha\right)-\beta\left(Q,p^{\star},\alpha\right)\right)\rightsquigarrow&\frac{t_{Q}}{p}\Biggl{\\{}\mathbb{Q}\left[y\left(1\left(p\left(x\right)>k\left(Q,p,\alpha\right)\right)-\beta\left(Q,p,\alpha\right)\right)\right]\\\
&-\frac{k\left(Q,p,\alpha\right)}{1-k\left(q,p,\alpha\right)}\mathbb{Q}\left[\left(1-y\right)\left(1\left(p\left(x\right)>k\left(Q,p,\alpha\right)\right)-\alpha\right)\right]\Biggl{\\}}.\end{split}$

Proof of Corollary 3.3.2.  The whole proof is similar to the proof of Theorem
3.3.1, we only need to point out that by chain rule

$\displaystyle\begin{split}\alpha^{\prime}_{Q,p^{\star},k}\left(\mathcal{Q},H,0\right)&=\frac{1}{1-p}\left[\mathcal{Q}\left[\left(1-y\right)1\left(p^{\star}\left(x\right)>c\right)\right]+\int_{p^{\star-1}\left(k\right)}\frac{\left(1-p\left(x\right)\right)H\left(x\right)\mu^{\prime}\left(x\right)}{\|\nabla
p^{\star}\left(x\right)\|}d\mathcal{H}_{n-1}x\right]\\\
&-\frac{\mathcal{Q}\left(1-y\right)}{1-p}\alpha\left(Q,p^{\star},c\right),\end{split}$

so we get an additional $\alpha$ term.

For the correctly specified case, corollary 3.3.2 implies a computationally
feasible functional delta method for bootstrap in probability. Here, we do not
need to recompute / reestimate the first step model for every bootstrapped
sample. On the contrary, the first step only need to be trained once.

######  Corollary 3.3.3.

Under the conditions in Theorem 3.3.1, let

$\displaystyle\begin{split}\left(\hat{p},\tilde{\mathbb{Q}}_{n}\right)\coloneqq\left(\hat{p}\left(\\{\left(X_{i},Y_{i}\right)\\}^{n}_{i=1}\right),\tilde{\mathbb{Q}}_{n}\left(\\{\left(X_{i},Y_{i}\right)\\}^{n}_{i=1},\\{M_{i}\\}^{n}_{i=1}\right)\right)\end{split}$

be the first step estimator and the empirical bootstrapped sample conditional
on $\\{\left(X_{i},Y_{i}\right)\\}^{n}_{i=1}$. Assume also $t_{n}=\sqrt{n}$,
then

$\displaystyle\begin{split}\sup_{l\in
BL_{1}\left(C\left(\mathcal{D}\right)\right)}&\left|\mathbb{E}_{M}l\left(\sqrt{n}\left(\beta\left(\tilde{\mathbb{Q}}_{n},\hat{p},\alpha\right)-\beta\left(\mathbb{Q}_{n},\hat{p},\alpha\right)\right)\right)-\mathbb{E}l\left(\beta^{\prime}_{Q,p,\alpha}\left(\mathbb{Q},0,0\right)\right)\to
0\right|,\\\
&\mathbb{E}_{M}l\left(\sqrt{n}\left(\beta\left(\tilde{\mathbb{Q}}_{n},\hat{p},\alpha\right)-\beta\left(\mathbb{Q}_{n},\hat{p},\alpha\right)\right)\right)^{*}-\mathbb{E}_{M}l\left(\sqrt{n}\left(\beta\left(\tilde{\mathbb{Q}}_{n},\hat{p},\alpha\right)-\beta\left(\mathbb{Q}_{n},\hat{p},\alpha\right)\right)\right)_{*}\to
0\end{split}$

in outer probability.

Proof of Corollary 3.3.3.  First note that by Assumption 3.3.4, we can evoke
Theorem 3.7.1 in van der Vaart and Wellner (2023) to get

$\displaystyle\begin{split}\sup_{l\in
BL_{1}\left(C\left(E\right)\times\ell^{\infty}\left(\mathcal{F}\right)\right)}&\left|\mathbb{E}_{M}l\left(\sqrt{n}\left(\left(\begin{array}[]{c}\hat{p}\\\
\tilde{\mathbb{Q}}_{n}\end{array}\right)-\left(\begin{array}[]{c}\hat{p}\\\
\mathbb{Q}_{n}\end{array}\right)\right)\right)-\mathbb{E}l\left(\left(\begin{array}[]{c}\hat{p}\\\
\mathbb{Q}\end{array}\right)\right)\right|\to 0,\\\
&\mathbb{E}_{M}l\left(\sqrt{n}\left(\left(\begin{array}[]{c}\hat{p}\\\
\tilde{\mathbb{Q}}_{n}\end{array}\right)-\left(\begin{array}[]{c}\hat{p}\\\
\mathbb{Q}_{n}\end{array}\right)\right)\right)^{*}-\mathbb{E}_{M}l\left(\sqrt{n}\left(\left(\begin{array}[]{c}\hat{p}\\\
\tilde{\mathbb{Q}}_{n}\end{array}\right)-\left(\begin{array}[]{c}\hat{p}\\\
\mathbb{Q}_{n}\end{array}\right)\right)\right)_{*}\to 0\end{split}$

in outer probability. Now we can simply use Theorem 3.10.11 in van der Vaart
and Wellner (2023).

##  4 Sub (sup) and Fréchet differentiability

We first recall the definition of sub (sup) differentiability. Let $E$ be an
open set of $\mathbb{R}^{n}$, and $f:E\to\mathbb{R}$ a function. Then $f$ is
said to be subdifferentiable at $x$, with subgradient $p$, if

$\displaystyle\begin{split}f\left(x^{\prime}\right)\geq
f\left(x\right)+\left\langle
p,x^{\prime}-x\right\rangle+o\left(\|x^{\prime}-x\|\right).\end{split}$

The convex set of all subgradients $p$ at $x$ will be denoted by
$\nabla^{-}f\left(x\right)$. If $\left(-f\right)$ is subdifferentiable, then
$f$ is said to be supdifferentiable, and the convex set of the negated
subgradients for $\left(-f\right)$ at $x$ is denoted as $\nabla^{+}f$.222We
follow the notation convention in Villani et al. (2009). It is well known that
a convex function $f$ is subdifferentiable with

$\displaystyle\begin{split}f\left(x^{\prime}\right)\geq
f\left(x\right)+\langle p,x^{\prime}-x\rangle\end{split}$

for some convex set of $p$. A concave function $h\left(\cdot\right)$ is
supdifferentiable with

$\displaystyle\begin{split}h\left(x^{\prime}\right)\leq
h\left(x\right)+\langle p,x^{\prime}-x\rangle\end{split}$

for some convex set of $p$.

###  4.1 Social welfare potential function

Given the convexity in $\lambda$ given $g\left(\cdot\right)$, a subgradient of
$\gamma\left(\lambda,g\right)$ in $\lambda$ is given by

$\displaystyle\begin{split}p\left(\lambda\right)=\left(\mathbb{E}\phi^{*}_{0}\left(X;\lambda,g\right)g_{0}\left(X\right),\ldots,\mathbb{E}\phi^{*}_{J}\left(X;\lambda,g\right)g_{J}\left(X\right)\right)^{T}.\end{split}$
(16)

where $\phi^{*}\left(\cdot;\lambda,g\right)$ is one of the optimal allocation
under the parameter $\left(\lambda,g\right)$. To verify by direct calcuation,

$\displaystyle\begin{split}&\gamma\left(\lambda,g\right)+\left\langle
p\left(\lambda\right),\lambda^{\prime}-\lambda\right\rangle\\\
&=\sum_{j}\mathbb{E}\lambda_{j}\phi_{j}^{*}\left(X;\lambda,g\right)g_{j}\left(X\right)+\sum_{j}\mathbb{E}\left(\lambda_{j}^{\prime}-\lambda_{j}\right)\phi_{j}^{*}\left(X;\lambda,g\right)g_{j}\left(X\right)\\\
&=\sum_{j}\mathbb{E}\lambda_{j}^{\prime}\phi_{j}^{*}\left(X;\lambda,g\right)g_{j}\left(X\right)\leq\sum_{j}\mathbb{E}\lambda_{j}^{\prime}\phi_{j}^{*}\left(X;\lambda^{\prime},g\right)g_{j}\left(X\right)=\gamma\left(\lambda^{\prime},g\right).\end{split}$

The rest of this subsection rigorously justifies calling
$\gamma\left(\lambda,g\right)$ a social welfare potential function, with
$p\left(\lambda\right)$ belonging to the vector field generated by
$\gamma\left(\lambda,g\right)$.

Recall by the concept of subgradients the set-valued map
$\nabla\gamma\left(\lambda,g\right):\mathbb{R}^{J+1}\rightrightarrows\mathbb{R}^{J+1}$,
where the symbol $\rightrightarrows$ indicates that the image of a point under
the map is a set. A common function is then understood as a set-valued map
where the image of a single point is a singleton set. The following definition
is needed:

######  Definition 4.1.1.

(Conservative set-valued fields, Bolte and Pauwels (2021)) Let
$D:\mathbb{R}^{p}\rightrightarrows\mathbb{R}^{p}$ be a set- valued map. $D$ is
a conservative (set-valued) field whenever it has closed graph, nonempty
compact values, and for any absolutely continuous loop
$\ell:\left[0,1\right]\to\mathbb{R}^{p}$, such that
$\ell\left(0\right)=\ell\left(1\right)$, the Aumann integral of
$t\rightrightarrows\left\langle\dot{\ell}\left(t\right),D\left(\ell\left(t\right)\right)\right\rangle$
is $\\{0\\}$, namely,

$\displaystyle\begin{split}\int^{1}_{0}&\left\langle\dot{\ell}\left(t\right),D\left(\ell\left(t\right)\right)\right\rangle
dt\\\ &\coloneqq\left\\{\int_{0}^{1}\omega(t)dt:\omega\left(t\right):[0,1]\to
R\text{ is a measurable selection
of}\left\langle\dot{\ell}\left(t\right),D\left(\ell\left(t\right)\right)\right\rangle\right\\}=\\{0\\}.\end{split}$
(17)

It is shown in Bolte and Pauwels (2021) (17) is equivalent to requiring that

$\displaystyle\begin{split}\int_{0}^{1}\max_{v\in
D\left(\ell\left(t\right)\right)}\left\langle\dot{\ell}\left(t\right),v\right\rangle
dt=0,\end{split}$

where the integral is understood in the Lebesgue sense, which is possible by
Theorem 18.19 and Theorem 18.20 in Aliprantis and Border (2006). See also
Lemma 1 in Bolte and Pauwels (2021). Another equivalent requirement is

$\displaystyle\begin{split}\int_{0}^{1}\min_{v\in
D\left(\ell\left(t\right)\right)}\left\langle\dot{\ell}\left(t\right),v\right\rangle
dt=0\quad\text{for all absolutely continuous loop $\ell$}.\end{split}$

The definition above involves an argmax (argmin) measurable selection, so for
any measurable selection
$v\left(t\right):\left[0,1\right]\to\mathbb{R}^{p},v\left(t\right)\in
D\left(\ell\left(t\right)\right)$, we have

$\displaystyle\begin{split}\int_{0}^{1}\left\langle\dot{\ell}\left(t\right),v\left(t\right)\right\rangle
dt=0.\end{split}$

Based on Definition (4.1.1), we introduce the following Definition (4.1.2):

######  Definition 4.1.2.

(Potential functions of conservative fields) A function
$f:\mathbb{R}^{p}\to\mathbb{R}$ is called a potential function of a
conservative field whenever there exists a conservative field
$D:\mathbb{R}^{p}\to\mathbb{R}^{p}$ such that

$\displaystyle\begin{split}f\left(x\right)=f\left(0\right)+\int^{1}_{0}\left\langle\dot{\mathtt{p}}\left(t\right),D\left(\mathtt{p}\left(t\right)\right)\right\rangle
dt\end{split}$

for all absolutely continuous path
$\mathtt{p}:\left[0,1\right]\to\mathbb{R}^{p}$ with
$\mathtt{p}\left(0\right)=0$ and $\mathtt{p}\left(1\right)=x$.

Bolte and Pauwels (2021) shows that a potential function must be locally
Lipschitz and their Theorem 1 states that if a function $f$ is a potential
function of the conservative field $D$ then $D$ coincides with the gradient of
$f$ on Lebesgue almost every point where the gradient exists. Therefore, we
can expect that certain kind of nonsmooth functions will generate conservative
fields by some generalized approach of taking derivatives. In addition, a
real-valued convex (or concave) function is locally Lipschitz and thus
Lebesgue almost everywhere differentiable by the Rademacher’s theorem. See for
example Theorem 3.7.3 in Niculescu and Persson (2018) and also Theorem T.1.2
in the technical addendum T.

######  Theorem 4.1.1.

Let $f:\mathbb{R}^{p}\to\mathbb{R}$ be a convex (or concave) function, then
$\nabla^{-}f\left(\nabla^{+}f\right)=\partial f$ is a conservative field,
where $\partial f$ is the Clarke subgradient defined below.

######  Definition 4.1.3.

(Clarke subgradients) Consider a local Lipschitz function $f:\Omega\to R$,
where $\Omega\subset\mathbb{R}^{n}$ is an open subset. For each $x\in\Omega$,
define

$\displaystyle\begin{split}f^{\circ}\left(x;v\right)&\coloneqq\limsup_{\begin{subarray}{c}y\to
x\\\ \lambda\downarrow 0\end{subarray}}\frac{f\left(y+\lambda
v\right)-f\left(y\right)}{\lambda}\\\
&=\lim_{\begin{subarray}{c}\varepsilon\to 0\\\ \epsilon\downarrow
0\end{subarray}}\sup\left\\{\frac{f\left(y+\lambda
v\right)-f\left(y\right)}{\lambda}:y\in\Omega\cap
B\left(x,\varepsilon\right),\lambda\in\left(0,\epsilon\right)\right\\},\forall
v\in\mathbb{R}^{n},y+\lambda v\in\Omega,\end{split}$

and the Clarke subgradient of $f$ at $x$:

$\displaystyle\begin{split}\partial
f\left(x\right)\coloneqq\left\\{\xi\in\mathbb{R}^{n}:f^{\circ}\left(x;v\right)\geq\left\langle
v,\xi\right\rangle,\forall v\in\mathbb{R}^{n}\right\\}.\end{split}$

Clarke (1975) provides an alternative characterization of Clarke subgradients
in $\mathbb{R}^{n}$: Let $f:\Omega\to R$ be a function in Definition 4.1.3 ,
then

$\displaystyle\begin{split}\partial
f\left(x\right)=\text{conv}\left\\{\lim_{k\to\infty}\nabla
f\left(x_{k}\right):x_{k}\to x,\nabla f\left(x_{k}\right)\
\text{exists}\right\\}.\end{split}$

Proof of Theorem 4.1.1.  By Proposition 1.2 in Clarke (1975), for convex
(concave) functions $f$, $\nabla^{-}f\left(\nabla^{+}f\right)=\partial f$.
Furthermore,
$\nabla^{-}f\left(x\right)\left(\nabla^{+}f\left(x\right)\right)=\partial_{g}f\left(x\right)$
by Proposition 8.12 in Rockafellar and Wets (2009), where
$\partial_{g}f\left(x\right)$ is the general subgradient as in definition 8.3
in Rockafellar and Wets (2009). Finally, by Theorem 10.49 in Rockafellar and
Wets (2009) and Corollary 2 in Bolte and Pauwels (2021), $\partial f$ is a
conservative field.

###  4.2 Envelope like theorem for social welfare potential function

Consider, for a given $g\left(\cdot\right)$,

$\displaystyle\begin{split}e\left(\lambda^{\prime};\phi^{*}\left(\cdot;\lambda,g\right)\right)=\mathbb{E}\left[\sum_{j}\lambda_{j}^{\prime}\phi_{j}^{*}g_{j}\right]-\gamma\left(\lambda^{\prime},g\right),\end{split}$

by construction,
$e\left(\lambda^{\prime};\phi^{*}\left(\cdot;\lambda,g\right)\right)$ achieves
its maximum of zero at $\lambda^{\prime}=\lambda$. When there is no
arbitrariness, we also denote
$\phi^{*}\left(\cdot\right)\coloneqq\phi^{*}\left(\cdot;\lambda,g\right)$ Note
first that
$\mathbb{E}\left[\sum_{j}\lambda_{j}^{\prime}\phi_{j}^{*}g_{j}\right]$ is
everywhere differentiable in $\lambda_{j}^{\prime}$ given
$\phi^{*}\left(\cdot\right)$ and $g\left(\cdot\right)$. Because of the
convexity of $\gamma\left(\lambda^{\prime},g\right)$ in $\lambda^{\prime}$
given $g\left(\cdot\right)$, $\gamma\left(\lambda^{\prime},g\right)$ is
differentiable in $\lambda^{\prime}$ given $g\left(\cdot\right)$ in a set
$\Lambda$ such that its complement $\Lambda^{c}$ is a Lebesgue null set. Then
for each $\lambda\in\Lambda$, and for each selection $\phi^{*}$ given this
choice of $\lambda$, $e\left(\lambda^{\prime};\phi^{*}\right)$ is
differentiable in $\lambda^{\prime}$ at $\lambda^{\prime}=\lambda$. Since zero
must be in the set of supgradients at a point of maximum of any function,
there is
$0\in\nabla^{+}e\left(\lambda^{\prime};\phi^{*}\right)\big{|}_{\lambda^{\prime}=\lambda}$
and thus $\nabla
e\left(\lambda^{\prime};\phi^{*}\right)\big{|}_{\lambda^{\prime}=\lambda}=0$,
implying

$\displaystyle\begin{split}\nabla\gamma\left(\lambda^{\prime},g\right)\Bigg{|}_{\lambda^{\prime}=\lambda_{0}}=\nabla\mathbb{E}\left[\sum_{j}\lambda_{j}^{\prime}\phi_{j}^{*}g_{j}\right]\Bigg{|}_{\lambda^{\prime}=\lambda}=\left(\mathbb{E}\phi_{j}^{*}g_{j},j=0,\ldots,J\right)^{T}.\end{split}$

An additional implication of the previous result is that for each
$\lambda\in\Lambda$, $\phi^{*}\left(x;\lambda,g\right)$ is unique in an almost
surly sense since the expectation
$\left(\mathbb{E}\phi_{j}^{*}g_{j},j=0,\ldots,J\right)^{T}$ is uniquely
defined.

Intuitively, we expect such envelope theorem like statement remains true with
respect to certain functional derivatives, so that we can discuss the
functional derivatives of

$\displaystyle\begin{split}e\left(\lambda^{\prime},g^{\prime};\phi^{*}\right)=\mathbb{E}\left[\sum_{j}\lambda_{j}^{\prime}\phi_{j}^{*}g_{j}^{\prime}\right]-\gamma\left(\lambda^{\prime},g^{\prime}\right)\end{split}$
(18)

at $\left(\lambda^{\prime},g^{\prime}\right)=\left(\lambda,g\right)$ (here,
$\phi^{*}\left(\cdot\right)\coloneqq\phi^{*}\left(\cdot;\lambda,g\right)$).
This conjecture will be subsequently verified. Surprisingly, some Fréchet
differentiability arguments can be established.

######  Definition 4.2.1.

(Fréchet differentiability) Let $\mathcal{X}$ and $\mathcal{Y}$ be normed
spaces equipped with norm $\|\cdot\|_{\mathcal{X}}$ and
$\|\cdot\|_{\mathcal{Y}}$, $E\subset\mathcal{X}$ be an open set. Consider the
map $\xi:E\to Y$. Then $\xi$ is called Fréchet differentiable at $\theta\in
E$, if there is a continuous linear map
$\xi^{\prime}\left(\theta\right):\mathcal{X}\to\mathcal{Y}$ such that:

$\displaystyle\begin{split}\left\|\xi\left(x\right)-\xi\left(\theta\right)-\xi^{\prime}\left(\theta\right)\left(x-\theta\right)\right\|_{\mathcal{Y}}=o\left(\|x-\theta\|_{\mathcal{X}}\right).\end{split}$

Before we describe the next result we need to recall several topological and
measure theoretic concepts. In a topological space $\mathcal{X}$, if a subset
$S\in\mathcal{X}$ satisfies $\overset{\circ}{\bar{S}}=\emptyset$, i.e. the
closure of $S$ has empty interior, then $S$ is called a nowhere dense subset
of $\mathcal{X}$. If $\mathcal{Z}\subset\mathcal{X}$ is a countable union of
nowhere dense subsets of $\mathcal{X}$, then $\mathcal{Z}$ is called a meager
subset of $X$, or of the first category in $\mathcal{X}$. A subset
$A\subset\mathcal{X}$ is called residually many (or just residual) in
$\mathcal{X}$ if $\mathcal{X}\setminus A$ is meager in $\mathcal{X}$. A set
$B\subset\mathcal{X}$ is called a $G_{\delta}$ set of $\mathcal{X}$ if $B$ is
a countable intersection of open sets; it is call a $F_{\sigma}$ set if it is
a countable union of closed sets.

In Lindenstrauss and Preiss (2003), the authors orginate an elaborate concept
to describe the magnitude of sets, call $\Gamma$-null sets. Let
$T=\left[0,1\right]^{\mathbb{N}}$, where $\mathbb{N}$ is the set of natural
numbers, be endowed with the product topology and product Lebesgue measure
$\mathcal{L}_{\infty}$. By the Tikhonov Theorem, $T$ is a compact space and
can be metrized by

$\displaystyle\begin{split}\rho\left(x,y\right)=\sum_{n=1}^{\infty}\frac{\rho_{n}\left(x_{n},y_{n}\right)}{2^{n}\left(1+\rho_{n}\left(x_{n},y_{n}\right)\right)}\end{split}$

where $\rho_{n}$ is some distance on $\left[0,1\right]$.

By the product $\sigma$-algebra on the space $\prod_{i}E_{i}$, we mean the
$\sigma$-algebra generated by all the coordinate projections. The product
measure then should satisfy

$\displaystyle\begin{split}\mu\left[\prod_{i}B_{i},B_{i}\subset\mathcal{E}_{i},\
\text{and}\ B_{i}\neq E_{i},\forall i\in\mathcal{I},B_{i}=E_{i},\forall
i\in\mathbb{N}\backslash\mathcal{I},\ \text{where}\
\mathcal{I}\subset\mathbb{N},0<|I|<\infty\right]=\prod_{i\in\mathcal{I}}\mu_{i}\left(B_{i}\right),\end{split}$

where $\left\\{\left(E_{i},\mathcal{E}_{i},\mu_{i}\right)\right\\}$ is a
family of measure spaces. The existence and uniqueness of the countable
product Lebesgue measure is guaranteed by the Kolmogorov extension theorem
(See for example Chapter 1 and 3 in Dellacherie and Meyer (1978)).

Now, let $\mathcal{X}$ be a Banach space and
$\Gamma\left(\mathcal{X}\right)=\\{\gamma:T\to\mathcal{X}\\}$ be the space of
continuous mappings having continuous partial derivatives $D_{j}\gamma$. Equip
$\Gamma\left(\mathcal{X}\right)$ with a topology generated by
$||\gamma||_{0}=\sup_{t\in T}||\gamma\left(t\right)||$, and all
$||\gamma||_{k}=\sup_{t\in T}||D_{k}\gamma\left(t\right)||$, $k\geq 1$.
Equivalently, the same topology is generated by all $||\gamma||_{\leq
k}=\max_{0\leq i\leq k}||\gamma||_{i},k\in\mathbb{N}$.

######  Definition 4.2.2.

($\Gamma$-null) A Borel set $N\subset\mathcal{X}$ is called $\Gamma$-null if
$\mathcal{L}_{\infty}\\{t\in T:\gamma\left(t\right)\in N\\}=0$ for residually
many $\gamma\in\Gamma\left(\mathcal{X}\right)$. If a set $A$ is contained in
such a $N$, then $A$ is also called $\Gamma$-null.

Now, we can state our result. In the following theorem statement, 1 and 2
follow from the convexity of $\gamma\left(\lambda,g\right)$ in $\lambda$ given
each $g$, and the convexity of $\gamma\left(\lambda,g\right)$ in $g$ given
each each $\lambda$, while 3 is needed to account for the non joint-convexity
of $\gamma\left(\lambda,g\right)$ in $\left(\lambda,g\right)$.

######  Theorem 4.2.1.

Let $\gamma\left(\lambda,g\right)$ be a real valued social welfare potential
function, where $\lambda\in\mathbb{R}^{J+1}$, $g\in\mathcal{X}$ where
$\mathcal{X}$ is a Banach space. Assume that $\gamma\left(\lambda,g\right)$ is
continuous at a point
$\left(\lambda_{0},g_{0}\right)\in\mathbb{R}^{J+1}\otimes\mathcal{X}$, then we
have:

  1. 1.

If every separable subspace $\mathcal{Y}$ of $\mathcal{X}$ has a separable
dual space $\mathcal{Y}^{*}$, then for any given $\lambda\in\mathbb{R}^{J+1}$,
$\gamma\left(\lambda,g\right)$ is Fréchet differentiable in $g$ on a dense
$G_{\delta}$ subset of $\mathcal{X}$.

  2. 2.

If the dual space $\mathcal{X}^{*}$ of $\mathcal{X}$ is separable, then for
any given $\lambda\in\mathbb{R}^{J+1}$, $\gamma\left(\lambda,g\right)$ is
$\Gamma$-almost everywhere Fréchet differentiable with respect to
$g\in\mathcal{X}$. In other words, for any given $\lambda\in\mathbb{R}^{J+1}$,
$\gamma\left(\lambda,g\right)$ is not Fréchet differentiable in $g$ on a
$\Gamma$-null set of $\mathcal{X}$.

  3. 3.

In addition, If every separable subspace $\mathcal{Y}$ of $\mathcal{X}$ has a
separable dual space $\mathcal{Y}^{*}$, and $\mathcal{X}$ can be continuously
embedded into $L^{1}\left(\Omega,\mu\right)$ (in the sense that for all
$x\in\mathcal{X}$, $\|x\|_{L^{1}\left(\Omega,\mu\right)}\leq
C\|x\|_{\mathcal{X}}$ for a constant $C$), then $\gamma\left(\lambda,g\right)$
is locally jointly Lipschitz in $\left(\lambda,g\right)$, and is also jointly
Fréchet differentiable with respect to
$\left(\lambda,g\left(\cdot\right)\right)$ on a dense subset of
$\mathbb{R}^{J+1}\otimes\mathcal{X}$.

When $\gamma\left(\lambda,g\right)$ is Fréchet differentiable (totally or
partially as in the theorem), the Fréchet derivative with respect to
$\left(\lambda,g\right)$ can be calculated to be

$\displaystyle\begin{split}\left(\left(\mathbb{E}\phi^{*}_{0}g_{0},\ldots,\mathbb{E}\phi^{*}_{J}g_{J}\right),\left(\mathbb{E}\lambda_{0}\phi^{*}_{0},\ldots,\mathbb{E}\lambda_{J}\phi^{*}_{J}\right)\right)^{T}\end{split}$
(19)

where

$\displaystyle\begin{split}\phi^{*}\left(\cdot\right)\coloneqq\phi^{*}\left(\cdot;\lambda,g\right)=\mathop{\arg\max}\limits_{\phi\left(\cdot\right)\in\Phi}\mathbb{E}\left[\sum_{j}\lambda_{j}\phi_{j}\left(X\right)g_{j}\left(X\right)\right]\end{split}$

in the $\mu$ almost surely sense, where $\mu$ is the distribution of $X$.

Proof of Theorem 4.2.1.
step 1 First, it is direct that $\gamma\left(\lambda,g\right)$ satisfies
subadditivity and is also positive homogeneous of degree one with respect to
both $\lambda$ and $g\left(\cdot\right)$, separately,

$\displaystyle\begin{split}\gamma\left(\lambda,g+g^{\prime}\right)\leq\gamma\left(\lambda,g\right)+\gamma\left(\lambda,g^{\prime}\right),&\quad\gamma\left(\lambda+\lambda^{\prime},g\right)\leq\gamma\left(\lambda,g\right)+\gamma\left(\lambda^{\prime},g\right),\\\
\gamma\left(\alpha\lambda,g\right)=\alpha\gamma\left(\lambda,g\right),&\quad\gamma\left(\lambda,\alpha
g\right)=\alpha\gamma\left(\lambda,g\right),\ \text{for all}\ \alpha\geq
0,\end{split}$

implying that $\gamma\left(\lambda,g\right)$ is convex in
$g\left(\cdot\right)$ given $\lambda$ and is convex in $\lambda$ given
$g\left(\cdot\right)$. Note that when $\mathcal{X}$ is infinite-dimensional, a
real-valued convex function is not necessarily continuous (there is always a
noncontinuous linear functional on $\mathcal{X}$). Fortunately, a real-valued
convex function on a Banach space is either continuous at evey point or
discontinuous at every point of its domain (see for example Proposition 3.1.11
of Niculescu and Persson (2018)). So by assumption,
$\gamma\left(\lambda,g\right)$ is a convex continuous function. Now, for
condition 1, we can directly evoke Theroem 2 in Stegall (1978); for condition
2, we can directly evoke Corollary 3.11 in Lindenstrauss and Preiss (2003).
step 2 From now, without loss of generality, we may assume that
$\mathbb{R}^{J+1}\times\mathcal{X}$ is equipped with the norm
$\left(\left\|r\right\|^{2}+\left\|x\right\|^{2}_{\mathcal{X}}\right)^{\frac{1}{2}}$.
Let $\mathcal{X}$ be a Banach space such that every separable subspace
$\mathcal{Y}$ has a separable dual space $\mathcal{Y}^{*}$,
$\mathcal{Z}\subset\mathbb{R}^{J+1}\times\mathcal{X}$ be a separable subspace
of $\mathbb{R}^{J+1}\times\mathcal{X}$. Then,
$\mathcal{X}^{\prime}=\left\\{x:\exists\left(r,x\right)\in\mathcal{Z}\right\\}$
is a subspace of $\mathcal{X}$,
$R^{\prime}=\left\\{r:\exists\left(r,x\right)\in\mathcal{Z}\right\\}$ is a
subspace of $\mathbb{R}^{J+1}$, and $\mathcal{Z}\subset
R^{\prime}\times\mathcal{X}^{\prime}$. The separability of $\mathcal{Z}$
implies the separability of $\mathcal{X}^{\prime}$. Note that the dual space
of $R^{\prime}\times\mathcal{X}^{\prime}$ isometrically isomorphic to
$\left(R^{\prime}\right)^{*}\times\left(\mathcal{X}^{\prime}\right)^{*}$.
Obviously, $\mathbb{R}^{J+1}$ is a separable Banach space with separable dual,
so by the separability of $\left(\mathcal{X}^{\prime}\right)^{*}$,
$\left(R^{\prime}\times\mathcal{X}^{\prime}\right)^{*}$ is separable. Let
$z^{*}\in\mathcal{Z}^{*}$, by Hahn-Banach theorem, there exists an element
$\left(r,x\right)^{*}\in\left(R^{\prime},\mathcal{X}^{\prime}\right)^{*}$ such
that $\left(r,x\right)^{*}|_{\mathcal{Z}}=z^{*}$ and
$\left\|z^{*}\right\|=\left\|\left(r,x\right)^{*}\right\|$. Therefore, with
some misuse of language, we can write that
$\mathcal{Z}^{*}\subset\left(R^{\prime}\times\mathcal{X}^{\prime}\right)^{*}$.
Therefore, the separability of
$\left(R^{\prime}\times\mathcal{X}^{\prime}\right)^{*}$ implies the
separability of $\mathcal{Z}^{*}$. In another word, if $\mathcal{Z}$ is a
separable subspace of $\mathbb{R}^{J+1}\times\mathcal{X}$, then
$\mathcal{Z}^{*}$ is separable.
step 3 We need to prove that $\gamma\left(\lambda,g\right)$ is locally
Lipschitz continuous. Note that

$\displaystyle\begin{split}\gamma\left(\lambda,g\right)=\sup_{\phi\in\Phi}\mathbb{E}\left[\sum_{j}\lambda_{j}\phi_{j}g_{j}\right]\leq\sup_{\phi\in\Phi}\mathbb{E}\left[\sum_{j}\left|\lambda_{j}\right|\left|g_{j}\right|\phi_{j}\right]\leq\left(\sum_{j}\left|\lambda_{j}\right|\right)\mathbb{E}\left|g_{i}\right|.\end{split}$

By the continuous embedding assumption $\mathbb{E}\left|g_{j}\right|\leq
C\left\|g_{j}\right\|_{\mathcal{X}}$ for some constant $C$. Consider an open
neighborhood $B_{\lambda,g,r}\coloneqq B\left(\lambda,r\right)\times
B\left(g,r\right)$ for arbitrarily chosen
$\left(\lambda,g\right)\in\mathbb{R}^{J+1}\times\mathcal{X}$, where open balls
$B\left(\lambda,r\right)$ and $B\left(g,r\right)$ are taken in
$\mathbb{R}^{J+1}$ and $\mathcal{X}$ respectively. Obviously, there exists a
constant $M$ such that $\forall\lambda^{\prime}\in B\left(\lambda,r\right)$,
$\|\lambda^{\prime}\|\leq M$. Therefore, for all
$\left(\lambda^{\prime},g^{\prime}\right)\in B_{\lambda,g,r}$,
$v\left(\lambda^{\prime},g^{\prime}\right)$ is upper bounded. Now, we can show
that $v\left(\lambda^{\prime},g^{\prime}\right)$ is also locally lower bounded
near $\lambda,g$. Let $z=g+\rho\left(g_{0}-g\right)$ such that
$g_{0}\in\mathcal{X}$, $z\in B\left(g,r\right)$ and $\rho>1$. It is not hard
to see such a point $z$ exists. For arbitrarily chosen $\lambda^{\prime}\in
B\left(\lambda,r\right)$, consider

$\displaystyle\begin{split}\mathcal{V}=\left\\{v:v=\left(1-\frac{1}{\rho}\right)g+\frac{1}{\rho}z,g\in
B\left(g,r\right)\right\\}.\end{split}$

$\mathcal{V}$ is equal to the ball in $\mathcal{X}$ with center
$g_{0}=\left(1-\frac{1}{\rho}\right)g+\frac{1}{\rho}z$ and radius
$\left(1-\frac{1}{\rho}\right)r$444This sort of construction is standard in
convex analysis.. For all $v\in\mathcal{V}$,
$\left(2g_{1}-v\right)\in\mathcal{V}$, so there is

$\displaystyle\begin{split}\gamma\left(\lambda^{\prime},g_{0}\right)\leq\frac{1}{2}\gamma\left(\lambda^{\prime},v\right)+\frac{1}{2}\gamma\left(\lambda^{\prime},2g_{1}-v\right)\end{split}$

which implies that

$\displaystyle\begin{split}\gamma\left(\lambda^{\prime},v\right)\geq
2\gamma\left(\lambda^{\prime},g_{1}\right)-\gamma\left(\lambda^{\prime},2g_{1}-v\right)\geq
2\gamma\left(\lambda^{\prime},g_{1}\right)-M.\end{split}$

Since $\gamma\left(\lambda^{\prime},g_{0}\right)$ is convex with respect to
$\lambda^{\prime}$ on $\mathbb{R}^{J+1}$, it is locally Lipschitz with respect
to $\lambda^{\prime}$, see for example Lemma 14.26 in Villani et al. (2009).
So we get that $\gamma\left(\lambda^{\prime},g\right)$ is locally bounded on a
neighborhood of $\left(\lambda,g\right)$. We may still denoted the bound as
$M$.
step 4 Now, we can prove that $\gamma\left(\cdot,\cdot\right)$ is jointly
locally Lipschitz. Let $g_{1},g_{2}\in B\left(g,r^{\prime}\right)$, $g_{1}\neq
g_{2}$ where $r^{\prime}$ is taken small enough such that for all
$\lambda^{\prime}\in B\left(\lambda,r\right)$,
$\left|\gamma\left(\lambda^{\prime},g^{\prime}\right)\right|\leq M$ for all
$g\in B\left(g,2r^{\prime}\right)$555This sort of construction is also
standard in problems involving convex structure.. Next, let
$w=g_{2}+\frac{r^{\prime}}{d}\left(g_{2}-g_{1}\right)$ where
$d=\left\|g_{1}-g_{2}\right\|_{\mathcal{X}}$. Obviously, $w\in
B\left(g,2r^{\prime}\right)$ and
$g_{2}=\frac{r^{\prime}}{r^{\prime}+d}g_{1}+\frac{d}{r^{\prime}+d}w$. By the
partial convexity of $\gamma\left(\cdot,\cdot\right)$ and let
$\lambda^{\prime}\in B\left(\lambda,r\right)$,

$\displaystyle\begin{split}\gamma\left(\lambda^{\prime},g_{2}\right)\leq\frac{r^{\prime}}{r^{\prime}+d}\gamma\left(\lambda^{\prime},g_{1}\right)+\frac{d}{r^{\prime}+d}\gamma\left(\lambda^{\prime},w\right).\end{split}$

Then, we have

$\displaystyle\begin{split}\gamma\left(\lambda^{\prime},g_{2}\right)-\gamma\left(\lambda^{\prime},g_{1}\right)&\leq\frac{d}{r^{\prime}+d}\left(\gamma\left(\lambda^{\prime},w\right)-\gamma\left(\lambda^{\prime},g_{1}\right)\right)\leq\frac{d}{r^{\prime}}\left(\gamma\left(\lambda^{\prime},w\right)-\gamma\left(\lambda,g_{1}\right)\right)\\\
&\leq\frac{2d}{r^{\prime}}M=\frac{2M}{r^{\prime}}\left\|g_{2}-g_{3}\right\|_{\mathcal{X}}.\end{split}$

Therefore, there exists a constant $M_{1}$, a neighborhood $\mathcal{N}_{g}$
of $g$ and a neighborhood $\mathcal{N}_{\lambda}$ of $\lambda$ such that for
all $\lambda^{\prime}\in\mathcal{N}_{\lambda}$,
$\gamma\left(\lambda^{\prime},\cdot\right)$ is Lipschitz with the constant
$M_{1}$ on $\mathcal{N}_{g}$. Similar, $\gamma\left(\cdot,g\right)$ is also
locally Lipschitz in the above uniform sense with a constant $M_{2}$. Now, in
a neighborhood of $\left(\lambda,g\right)$, we have

$\displaystyle\begin{split}\left|\gamma\left(\lambda^{\prime},g^{\prime}\right)-\gamma\left(\lambda^{\prime\prime},g^{\prime\prime}\right)\right|&\leq\left|\gamma\left(\lambda^{\prime},g^{\prime}\right)-\gamma\left(\lambda^{\prime},g^{\prime\prime}\right)\right|+\left|\gamma\left(\lambda^{\prime},g^{\prime\prime}\right)-\gamma\left(\lambda^{\prime\prime},g^{\prime\prime}\right)\right|\\\
&\leq\left(M_{1}+M_{2}\right)\left\|\left(\lambda,g\right)-\left(\lambda^{\prime},g^{\prime}\right)\right\|_{\mathbb{R}^{J+1}\times\mathcal{X}}.\end{split}$

Now, we can directly evoke the Theorem 2.5 of Preiss (1990) to get that
$\gamma\left(\cdot,\cdot\right)$ is Fréchet differentiable at least on a dense
subset of $\mathbb{R}^{J+1}\times\mathcal{X}$.
step 5 In order to calculate the Fréchet derivative of
$\gamma\left(\lambda,g\right)$ at those Fréchet differentiable points, we use
the auxiliary function defined in (18).
$\mathbb{E}\left[\sum_{j}\lambda_{j}^{\prime}\phi^{*}_{j}g_{j}^{\prime}\right]$
is continuous linear by Proposition 3.1.11 in Niculescu and Persson (2018) and
thus Fréchet differentiable with respect to $\left(\lambda,g\right)$ with the
derivate in the right hand side of (19). Obviously,
$e\left(\lambda^{\prime},g^{\prime};\phi^{*}\right)$ is concave and achieves
its maximum at $\left(\lambda,g\right)$. Therefore, by Theorem 3.6.11 of
Niculescu and Persson (2018), we have
$0\in\nabla^{+}e\left(\lambda^{\prime},g^{\prime};\phi^{*}\right)|_{\left(\lambda^{\prime},g^{\prime}\right)=\left(\lambda,g\right)}$.
So, if $\gamma\left(\lambda^{\prime},g^{\prime}\right)$ is Fréchet
differentiable at $\left(\lambda,g\right)$, by Propsoition 3.6.9 in Niculescu
and Persson (2018),

$\displaystyle\begin{split}\nabla^{+}\left(\lambda^{\prime},g^{\prime};\phi^{*}\right)|_{\left(\lambda^{\prime},g^{\prime}\right)=\left(\lambda,g\right)}=\left\\{e^{\prime}\left(\lambda^{\prime},g^{\prime};\phi^{*}|_{\left(\lambda^{\prime},g^{\prime}\right)=\left(\lambda,g\right)}\right)\right\\}=\\{0\\}.\end{split}$

Now, the proof ends with direct calculation.

The conditions for Fréchet differentiability stated in Theorem 4.2.1 originate
from the partial convexity of $\gamma\left(\lambda,g\right)$ in either
$\lambda$ or $g$, and the joint local Lipschitz property of
$\gamma\left(\lambda,g\right)$ in $\left(\lambda,g\right)$ and make use of the
key results Stegall (1978) (Theorem 2), Lindenstrauss and Preiss (2003)
(Corollary 3.11) and Preiss (1990) (Theorem 2.5). Namioka and Phelps (1975)
attributed a space $\mathcal{X}$ such that every separable subspace
$\mathcal{Y}$ of it has a separable dual space $\mathcal{Y}^{*}$ to Asplund
(1968) as an Asplund space.

Theorem 4.2.1 essentially shows that, under mild conditions, a generic
point666 A generic property is one that holds on a residual set. can support
taking the Fréchet derivative of $\gamma\left(\lambda,g\right)$. In
Chernozhukov et al. (2018b), Hadamard differentiability is verified by direct
calculations with great details of the partial effect quantile function
(called sorted effect therein). We have demonstrated how to reformate their
approach in section 3. Compared with Chernozhukov et al. (2018b), the
assumptions in Theorem 4.2.1 is not more restrictive in several senses. First,
Hadamard differentiability implies continuity (See for example Averbuh and
Smoljanov (1968)). Second, it is well known that for a measure space
$\left(\Omega,\mathcal{F},\mu\right)$ such that $\mathcal{F}$ is separable or
countably generated, and $\mu$ is $\sigma$-finite, $L_{p}\left(\Omega\right)$
is separable for $1<p<\infty$, which implies that $L_{p}\left(\Omega\right)$
is separable and reflexive when $\Omega$ is a Polish space, $\mathcal{F}$ is
the Borel $\sigma$-algebra, and $\mu$ is a probability measure. Furthermore,
when $\Omega$ is an open subset of $\mathbb{R}^{n}$ and $\mathcal{F}$ is the
$\sigma$-algebra of Lebesgue measure, and $\mu=\mathcal{L}_{n}$ the
$n$-dimensional Lebesgue measure, both $L_{p}\left(\Omega\right)$ and the
Sobolev space $W^{k,p}\left(\Omega\right)$ is also separable and reflexive.
Third, we do not directly make assumptions about the underlying distribution
$\mu$, such as requiring compact support or having a continuous density
function.

Given convexity and local Lipschitzness, Under the conditions of Theorem
4.2.1, generic Fréchet differentiability follows from convexity and local
Lipschitzness. Consequently, Fréchet differentiability (which is stronger than
Hadamard differentiability) is a reasonable assumption. The generic Fréchet
differentiability property here provides a conceptual justification of the
functional differential methodology in Chen et al. (2003) and Chernozhukov et
al. (2015). Theorem 4.2.1 also differs from the envelope theorems in Milgrom
and Segal (2002). Milgrom and Segal (2002) characterized possibly non-convex
problems for finite dimensional relevant parameters, while in this work,
Theorem 4.2.1 focuses on a generic property for larger relevant parameter
spaces.

Condition 2 in Theorem 4.2.1 requires that $\mathcal{X}^{*}$ is separable,
which is more restrictive than the Asplund space in condition 1. Theorem 2.4
in Lindenstrauss and Preiss (2003) shows that on $\mathbb{R}^{n}$, a
$\Gamma$-null set is equivalent to a set with Lebesgue zero. By the Rademacher
Theorem again, given $g$, $\gamma\left(\lambda,g\right)$ is $\Gamma$-almost
everywhere differentiable with respect to $\lambda$.

For a Banach space with a separable dual space, part 1 of Theorem 4.2.1 shows
that the set of non Fréchet-differentiable points is contained in a meager
$F_{\sigma}$ set, while part 2 of Theorem 4.2.1 shows that it is also a
$\Gamma$-null set. In other words, the set of non Fréchet differentiable
points is a $\Gamma$-null set, and is contained in a meager $F_{\sigma}$ set.
However, to the best of our knowledge, there is no general ordering between
$\Gamma$-null sets and meager $F_{\sigma}$ sets. Even in the simplest case
$\mathbb{R}$, there are interesting counterexamples. The Smith-Volterra-Cantor
set (or called fat Cantor set) is closed and nowhere dense and thus meager
$F_{\sigma}$ but of positive Lebesgue measure. It is also possible to
construct a dense $G_{\delta}$ subset $B$ of $\mathbb{R}$ with zero Lebesgue
measure that is not a meager $F_{\sigma}$ set (by the Baire theorem). To
construct $B$, enumerate the rational numbers as
$\mathbb{Q}=\\{q_{1},q_{2},\ldots\\}$, and put
$P_{n}=\bigcup_{j=1}^{\infty}B\left(q_{j},2^{-j}/n\right)$ for positive
integers $n$. Define $B=\bigcap_{n=1}^{\infty}P_{n}$. Since $P_{n}$ is open
for every positive integer $n$, we have $B$ is a $G_{\delta}$ set. The set $B$
has zero Lebesgue measure because

$\displaystyle\begin{split}\mu\left(B\right)\leq\mu\left(P_{n}\right)\leq\sum_{j=1}^{\infty}\mu\left(B\left(q_{j},2^{-j}/n\right)\right)=\sum_{j=1}^{\infty}\frac{2^{-j+1}}{n}=\frac{2}{n}\to
0\ \text{as}\ n\to\infty.\end{split}$

It is worth noting that the concepts of meager $F_{\sigma}$ sets (the
complement of dense $G_{\delta}$ sets) and $\Gamma$-null sets are among a
collection of related definitions used to describe the smallness of sets. Part
1 of Theorem 4.2.1 describes a pure topological property of the set of
$g\in\mathcal{X}$ at which $\gamma\left(\lambda,g\right)$ is Fréchet
differentiable, while part 2 of Theorem 4.2.1 is both topological and measure
theoretic in nature. Under the conditions of part 2 of Theorem 4.2.1, the set
of $g$ at which $\gamma\left(\lambda,g\right)$ is not Fréchet differentiable
satisfies other smallness properties. For example, on the one hand, by Theorem
1 in Preiss and Zajíček (1984), if $\mathcal{X}$ is a Banach space with
separable dual space, then a continuous convex function $f$ on $\mathcal{X}$
is Fréchet differentiable outside a $\sigma$-porous set. By Theorem 10.4.1 in
Lindenstrauss et al. (2012), a $\sigma$-porous set is also a $\Gamma_{1}$-null
set. On the other hand, by Proposition 5.4.3 in Lindenstrauss et al. (2012),
if $A\subset\mathcal{X}$ is a $\Gamma$-null and $F_{\sigma}$ set, then it is
$\Gamma_{n}$ null for every $n$. To recapitulate, $\sigma$-porous is a metric
space concept, while $\Gamma_{n}$-null is a topological and measure theoretic
concept. These relations are illustrated in Figure 1.

######  Definition 4.2.3.

(Porous and $\sigma$-porous) A set $A$ in a Banach space $\mathcal{X}$ is
called $\sigma$-porous if it is a countable union of porous sets. A porous set
$E\subset\mathcal{X}$ is such that there exists $0<c<1$, and for all
$x\in\mathcal{X}$, and for all $\epsilon>0$, there is a $y\in\mathcal{X}$
satisfying $0<d\left(x,y\right)<\epsilon$ and $B\left(y,c\cdot
d\left(x,y\right)\right)\cap E=\emptyset$.

######  Definition 4.2.4.

($\Gamma_{n}$-null) Consider
$\Gamma_{n}\left(\mathcal{X}\right)=C^{1}\left(\left[0,1\right]^{n},\mathcal{X}\right)$
equipped with the $\|\cdot\|_{\leq n}$ norm. Then a Borel set
$A\subset\mathcal{X}$ is called $\Gamma_{n}$-null if

$\displaystyle\begin{split}L^{n}\\{t\in\left[0,1\right]^{n}:\gamma\left(t\right)\in
A\\}=0.\end{split}$

for residually many $\gamma\in\Gamma_{n}\left(\mathcal{X}\right)$. If $A$ is
not Borel, it is also called $\Gamma_{n}$-null if it is contained in a
$\Gamma_{n}$-null Borel set.

Figure 1: Relation between different concepts of small
sets$\sigma$-porousnowhere dense$\Gamma_{1}$-nullmeager
$F_{\sigma}$$\Gamma$-null$\subset$

When $\lambda$ is given and fixed, a stronger global Lipschitz continuity
property can be seen to hold based on
$\left|\max_{j}\\{a_{j}\\}-\max_{j}\\{b_{j}\\}\right|\leq\max_{j}|a_{j}-b_{j}|$:

$\displaystyle\begin{split}\left|\max_{j}\lambda_{j}g_{j}^{\prime}\left(x\right)-\max_{j}\lambda_{j}g_{j}\left(x\right)\right|\leq\max_{j}|\lambda_{j}|\left|g_{j}^{\prime}\left(x\right)-g_{j}\left(x\right)\right|.\end{split}$

It then follows that

$\displaystyle\begin{split}&\left|\gamma\left(\lambda,\hat{g}\right)-\gamma\left(\lambda,g\right)\right|\leq\mathbb{E}\max_{j}|\lambda_{j}||\hat{g}_{j}\left(X\right)-g_{j}\left(X\right)|\\\
&\leq\max_{j}|\lambda_{j}|\times\mathbb{E}\max_{j}\left|\hat{g}_{j}\left(X\right)-g_{j}\left(X\right)\right|\\\
&\leq\max_{j}|\lambda_{j}|\times\mathbb{E}\left[\sum_{j}\left|\hat{g}_{j}\left(x\right)-g_{j}\left(x\right)\right|\right]=\max_{j}|\lambda_{j}|\left\|\hat{g}-g\right\|_{L^{1}}\leq\max_{j}|\lambda_{j}|\left\|\hat{g}-g\right\|_{L^{p}},\
p\geq 1,\end{split}$

where $\hat{g}$ is an estimator of $g$. Assuming measurability, we have

$\displaystyle\begin{split}\mathbb{E}_{n}\left|\gamma\left(\lambda,\hat{g}\right)-\gamma\left(\lambda,g\right)\right|\leq\max_{j}|\lambda_{j}|\mathbb{E}_{n}\left\|\hat{g}-g\right\|_{L^{p}},\
p\geq 1\end{split}$

where $\mathbb{E}_{n}$ applies to the estimation uncertainty in obtaining
$\hat{g}\left(\cdot\right)$.

###  4.3 Fast convergence rates

It is also worth noting that our analysis is closely related to the fast
learning rates for plug-in classifiers in Devroye et al. (1996) and Audibert
and Tsybakov (2007). To illustrate these results consider a weighted version
of the population accuracy measure defined as

$\displaystyle\begin{split}\gamma\left(\tau,p\left(\cdot\right),R\right)&=\mathbb{E}\left[\tau
Y1\left(X\in R\right)+\left(1-\tau\right)\left(1-Y\right)1\left(X\in
R^{c}\right)\right]\\\
&=\mathbb{E}\left[\left(1-\tau\right)\left(1-p\left(X\right)\right)\right]+\mathbb{E}\left[\left(p\left(X\right)-\left(1-\tau\right)\right)1\left(X\in
R\right)\right]\end{split}$ (20)

Then an optimal choice of $R$, which is
$1\left(p\left(x\right)>\left(1-\tau\right)\right)$, for a given $\tau$ leads
to

$\displaystyle\begin{split}\gamma\left(\tau,p\left(\cdot\right)\right)&=\max_{R}\gamma\left(\tau,p\left(\cdot\right),R\right)\\\
&=\mathbb{E}\left[\left(1-\tau\right)\left(1-p\left(X\right)\right)\right]+\mathbb{E}\left[\left(p\left(X\right)-\left(1-\tau\right)\right)1\left(p\left(X\right)>\left(1-\tau\right)\right)\right].\end{split}$

The welfare regret is defined as the difference between the optimized
population welfare and the feasible welfare based on an estimate of the
optimal policy $\hat{R}=1\left(\hat{p}\left(x\right)>1-\tau\right)$:

$\displaystyle\begin{split}\gamma\left(\tau,p\left(\cdot\right)\right)-\gamma\left(\tau,p\left(\cdot\right),\hat{R}\right)&=\mathbb{E}\left[\left(p\left(X\right)-\left(1-\tau\right)\right)\left(1\left(p\left(X\right)>1-\tau\right)-1\left(\hat{p}\left(X\right)>1-\tau\right)\right)\right]\\\
&=\mathbb{E}\left[\left|\left(p\left(X\right)-\left(1-\tau\right)\right)\right|\left|\left(1\left(p\left(X\right)>1-\tau\right)-1\left(\hat{p}\left(X\right)>1-\tau\right)\right)\right|\right].\end{split}$

The key insight for analyzing convergence speed of above regret is that on the
set where
$1\left(p\left(x\right)>\left(1-\tau\right)\right)-1\left(\hat{p}\left(x\right)>\left(1-\tau\right)\right)\neq
0$, or where either $\left\\{p\left(x\right)>1-\tau,\hat{p}\left(x\right)\leq
1-\tau\right\\}$ or $\left\\{p\left(x\right)\leq
1-\tau,\hat{p}\left(x\right)>1-\tau\right\\}$:

$\displaystyle\begin{split}\left|p\left(x\right)-\left(1-\tau\right)|\leq|p\left(x\right)-\hat{p}\left(x\right)\right|.\end{split}$

Therefore the regret can be bounded by,

$\displaystyle\begin{split}\left|\gamma\left(\tau,p\left(\cdot\right)\right)-\gamma\left(\tau,p\left(\cdot\right),\hat{R}\right)\right|&\leq\mathbb{E}\left[\left|p\left(X\right)-\hat{p}\left(X\right)\right|\left|\left(1\left(p\left(X\right)>1-\tau\right)-1\left(\hat{p}\left(X\right)>1-\tau\right)\right)\right|\right]\\\
&\leq\sup_{x\in\mathcal{X}}\left|p\left(x\right)-\hat{p}\left(x\right)\right|\mathbb{E}\left|\left(1\left(p\left(X\right)>1-\tau\right)-1\left(\hat{p}\left(X\right)>1-\tau\right)\right)\right|\\\
\end{split}$

As in Chen et al. (2003), for
$\delta_{n}=\sup_{x\in\mathcal{X}}\left|p\left(x\right)-\hat{p}\left(x\right)\right|$,

$\displaystyle\begin{split}\left|\left(1\left(p\left(x\right)>1-\tau\right)-1\left(\hat{p}\left(x\right)>1-\tau\right)\right)\right|\leq
1\left(1-\tau-\delta_{n}\leq p\left(x\right)\leq
1-\tau+\delta_{n}\right).\end{split}$

As such the regret can be further bounded by

$\displaystyle\begin{split}\left|\gamma\left(\tau,p\left(\cdot\right)\right)-\gamma\left(\tau,p\left(\cdot\right),\hat{R}\right)\right|\leq\delta_{n}\mathbb{P}\left(1-\tau-\delta_{n}\leq
p\left(X\right)\leq 1-\tau+\delta_{n}\right)\end{split}$

Under the conditions in section 3 (see for example Proposition 3.2.3) where
$p\left(x\right)$ has a bounded density at $1-\tau$, for a constant $C$,

$\displaystyle\begin{split}\mathbb{P}\left(1-\tau-\delta_{n}\leq
p\left(X\right)\leq 1-\tau+\delta_{n}\right)\leq C\delta_{n}.\end{split}$

In conclusion,
$\left|\gamma\left(\tau,p\left(\cdot\right)\right)-\gamma\left(\tau,p\left(\cdot\right),\hat{R}\right)\right|\leq
C\delta_{n}^{2}$. Many nonparametric estimators $\hat{p}\left(x\right)$
achieves $\delta_{n}=O_{\mathbb{P}}\left(n^{-\frac{\beta}{2\beta+d}}\log
n\right)$ where $d$ is the dimension of $x$, and $\beta$ a smoothness
parameter, implying that

$\displaystyle\begin{split}\left|\gamma\left(\tau,p\left(\cdot\right)\right)-\gamma\left(\tau,p\left(\cdot\right),\hat{R}\right)\right|=O_{\mathbb{P}}\left(n^{-\frac{2\beta}{2\beta+d}}\log^{2}n\right)\end{split}$

and whenever $\beta>d/2$,

$\displaystyle\begin{split}\left|\gamma\left(\tau,p\left(\cdot\right)\right)-\gamma\left(\tau,p\left(\cdot\right),\hat{R}\right)\right|=O_{\mathbb{P}}\left(n^{-\frac{1}{2}}\right).\end{split}$

Note that in the above, we provide primitive conditions that offer the case of
$\alpha\geq 1$ for the margin assumption (MA) in Mammen and Tsybakov (1999),
Tsybakov (2004), Boucheron et al. (2005), Audibert and Tsybakov (2007),
Kitagawa and Tetenov (2018) and Luedtke and Chambaz (2020).

The misclassification error rate in Audibert and Tsybakov (2007) is the most
important case of the weighted population accuracy (20) where
$\tau=\frac{1}{2}$, since

$\displaystyle\begin{split}\mathbb{P}\left(Y\neq 1\left(X\in
R\right)\right)&=1-\mathbb{P}\left(Y=1\left(X\in R\right)\right)\\\
&=1-2\left[\frac{1}{2}\mathbb{E}Y1\left(X\in
R\right)+\frac{1}{2}\mathbb{E}\left(1-Y\right)1\left(X\in
R^{c}\right)\right]=1-2\gamma\left(\frac{1}{2},p\left(\cdot\right),R\right),\end{split}$

where $p\left(x\right)=\mathbb{E}\left(Y|X=x\right)$.

Recall that in a general discrete allocation problem, we define welfare under
policy as

$\displaystyle\begin{split}\gamma\left(\lambda,g,\phi\right)=\mathbb{E}\left[\sum_{j=0}^{J}\lambda_{j}\phi_{j}\left(X\right)Y_{j}\right]=\mathbb{E}\left[\sum_{j=0}^{J}\lambda_{j}\phi_{j}\left(X\right)g_{j}\left(X\right)\right],\end{split}$

where $g_{j}\left(x\right)=\mathbb{E}\left(Y_{j}|X=x\right)$ and
$\phi_{j}\left(x\right)\geq 0,\forall j$,
$\sum_{j=0}^{J}\phi_{j}\left(x\right)=1$. Then an optimal choice of
$\phi\left(\cdot\right)$, which be given by (2), for a given $\lambda$ leads
to the social welfare potention function (1). The feasible analog based on an
estimate $\hat{g}\left(x\right)$ should then satisfy

$\displaystyle\begin{split}\hat{\phi}_{j}\left(X\right)=\left\\{\begin{array}[]{cc}1,&\text{if}\
\lambda_{j}\hat{g}_{j}\left(X\right)>\lambda_{l}\hat{g}_{j}\left(X\right),\
\forall l\neq j,\\\ 0,&\text{if}\
\lambda_{j}\hat{g}_{j}\left(X\right)<\lambda_{l}\hat{g}_{j}\left(X\right),\
\exists l\neq j.\end{array}\right.\end{split}$

If there exists some $l$ such that
$\lambda_{j}\hat{g}_{j}\left(X\right)=\lambda_{l}\hat{g}_{l}\left(X\right)$,
then $\hat{\phi}\left(\cdot\right)$ can be divided among all the maximal
indexes. In the following we adopt a convention of allocating the optimal
$\phi^{*}\left(x\right)$ and $\hat{\phi}\left(x\right)$ such that all the
weight among the maximal indexes is allocated to the smallest index member:

$\displaystyle\begin{split}\phi_{j}^{*}\left(x\right)&=\prod_{l=j+1}^{J}1\left(\lambda_{j}g_{j}\left(x\right)\geq\lambda_{l}g_{l}\left(x\right)\right)\prod_{l=0}^{j-1}1\left(\lambda_{j}g_{j}\left(x\right)>\lambda_{l}g_{l}\left(x\right)\right),\\\
\hat{\phi}_{j}\left(x\right)&=\prod_{l=j+1}^{J}1\left(\lambda_{j}\hat{g}_{j}\left(x\right)\geq\lambda_{l}\hat{g}_{l}\left(x\right)\right)\prod_{l=0}^{j-1}1\left(\lambda_{j}\hat{g}_{j}\left(x\right)>\lambda_{l}\hat{g}_{l}\left(x\right)\right).\end{split}$

The welfare regret is defined as the difference between the social welfare
function and its feasible version based on the plug-in estimate of the optimal
policy:

$\displaystyle\begin{split}\gamma\left(\lambda,g,\phi^{*}\right)-\gamma\left(\lambda,g,\hat{\phi}\right)=\sum_{j=0}^{J}\mathbb{E}\left[\lambda_{j}g_{j}\left(X\right)\left(\phi_{j}^{*}\left(X\right)-\hat{\phi}_{j}\left(X\right)\right)\right]\end{split}$

Note that by definition, for each $x$, $\phi_{j}^{*}\left(x\right)$ is either
$0$ or $1$ for each $j=0,\ldots,J$. Furthermore, one and only one of
$\phi_{j}^{*}\left(x\right)$ out of $j=0,\ldots,J$ takes the value $1$. The
same is also true for $\hat{\phi}_{j}\left(x\right)$ for each $x$. Therefore
we can write

$\displaystyle\begin{split}&\gamma\left(\lambda,g,\phi^{*}\right)-\gamma\left(\lambda,g,\hat{\phi}\right)\\\
&=\mathbb{E}\left[\sum_{i\neq
j}\left(\lambda_{i}g_{i}\left(X\right)-\lambda_{j}g_{j}\left(X\right)\right)\phi_{i}^{*}\left(X\right)\hat{\phi}_{j}\left(X\right)\right]\\\
&\leq\mathbb{E}\left[\sum_{i\neq
j}\left|\lambda_{i}g_{i}\left(X\right)-\lambda_{j}g_{j}\left(X\right)-\left(\lambda_{i}\hat{g}_{i}\left(X\right)-\lambda_{j}\hat{g}_{j}\left(X\right)\right)\right|\phi_{i}^{*}\left(X\right)\hat{\phi}_{j}\left(X\right)\right]\\\
&\leq\mathbb{E}\left[\sum_{i\neq
j}\left|\lambda_{i}g_{i}\left(X\right)-\lambda_{j}g_{j}\left(X\right)-\left(\lambda_{i}\hat{g}_{i}\left(X\right)-\lambda_{j}\hat{g}_{j}\left(X\right)\right)\right|1\left(\phi^{*}\left(X\right)\neq\hat{\phi}\left(X\right)\right)\right]\\\
&\leq\mathbb{E}\left[\sum_{i\neq
j}\left|\lambda_{i}g_{i}\left(X\right)-\lambda_{j}g_{j}\left(X\right)-\left(\lambda_{i}\hat{g}_{i}\left(X\right)-\lambda_{j}\hat{g}_{j}\left(X\right)\right)\right|\sum_{k\neq
l}\left|1_{kl}^{*}-\hat{1}_{kl}\right|\right]\end{split}$ (21)

where we define, for $k\neq l,k,l=0,\ldots,J$,

$\displaystyle\begin{split}1_{kl}^{*}\left(x\right)=1\left(k<l\right)1\left(\lambda_{k}g_{k}\left(x\right)\geq\lambda_{l}g_{l}\left(x\right)\right)+1\left(k>l\right)1\left(\lambda_{k}g_{k}\left(x\right)>\lambda_{l}g_{l}\left(x\right)\right).\end{split}$

and

$\displaystyle\begin{split}\hat{1}_{kl}\left(x\right)=1\left(k<l\right)1\left(\lambda_{k}\hat{g}_{k}\left(x\right)\geq\lambda_{l}\hat{g}_{l}\left(x\right)\right)+1\left(k>l\right)1\left(\lambda_{k}\hat{g}_{k}\left(x\right)>\lambda_{l}\hat{g}_{l}\left(x\right)\right).\end{split}$

As previously, following Chen et al. (2003), for
$\delta_{n}=\sup_{x\in\mathcal{X}}\max_{j=0,\ldots,J}|\lambda_{j}g_{j}\left(x\right)-\lambda_{j}\hat{g}_{j}\left(x\right)|$,

$\displaystyle\begin{split}|1_{kl}^{*}-\hat{1}_{kl}|\leq
1\left(-2\delta_{n}\leq\lambda_{k}g_{k}\left(x\right)-\lambda_{l}g_{l}\left(x\right)\leq
2\delta_{n}\right).\end{split}$ (22)

Then we can further bound the regret as

$\displaystyle\begin{split}&\gamma\left(\lambda,g,\phi^{*}\right)-\gamma\left(\lambda,g,\hat{\phi}\right)\leq
2\left(J+1\right)^{2}\delta_{n}\sum_{k\neq
l}\mathbb{P}\left(-2\delta_{n}\leq\lambda_{k}g_{k}\left(X\right)-\lambda_{l}g_{l}\left(X\right)\leq
2\delta_{n}\right).\end{split}$

Under the conditions in section 3 where for each pair $k\neq l$,
$\lambda_{k}g_{k}\left(x\right)-\lambda_{l}g_{l}\left(x\right)$ has a bounded
density at zero,
$\mathbb{P}\left(-2\delta_{n}\leq\lambda_{k}g_{k}\left(X\right)-\lambda_{l}g_{l}\left(X\right)\leq
2\delta_{n}\right)\leq C\delta_{n}$, leading to

$\displaystyle\begin{split}\gamma\left(\lambda,g,\phi^{*}\right)-\gamma\left(\lambda,g,\hat{\phi}\right)\leq
C\delta_{n}^{2}.\end{split}$

Given nonparametric estimates of $\hat{g}_{j}\left(x\right),j=0,\ldots,J$
achieving $\delta_{n}=O_{\mathbb{P}}\left(n^{-\frac{\beta}{2\beta+d}}\log
n\right)$, there is

$\displaystyle\begin{split}\left|\gamma\left(\lambda,g\right)-\gamma\left(\lambda,g,\hat{\phi}\right)\right|=O_{\mathbb{P}}\left(n^{-\frac{2\beta}{2\beta+d}}\log^{2}n\right)\end{split}$

and whenever $\beta>d/2$,
$|\gamma\left(\lambda,g\right)-\gamma\left(\lambda,g,\hat{\phi}\right)|=o_{\mathbb{P}}\left(n^{-\frac{1}{2}}\right)$.

The unknown social welfare potential function
$\beta_{0}=\gamma\left(\lambda,g\right)=\mathbb{E}\max_{j=0,\ldots,J}\lambda_{j}g_{j}\left(x\right)$
can be estimated by its sample analog
$\hat{\gamma}\left(\lambda,\hat{g}\left(\cdot\right)\right)=\frac{1}{n^{\prime}}\sum_{i=1}^{n^{\prime}}\max_{j=0,\ldots,J}\lambda_{j}\hat{g}_{j}\left(X_{i}\right)$.
Following Chernozhukov et al. (2018a) and Chernozhukov et al. (2022), we
consider a Neyman-orthogonal debiased version as, where with
$Y_{i}=\sum_{j=0}^{J}D_{ij}Y_{ij}$,

$\displaystyle\begin{split}\hat{\beta}=\frac{1}{n^{\prime}}\sum_{i=1}^{n^{\prime}}\sum_{j=0}^{J}\lambda_{j}\hat{\phi}_{j}\left(X_{i}\right)\left[\hat{g}_{j}\left(X_{i}\right)+\frac{D_{ij}}{\hat{p}_{j}\left(X_{i}\right)}\left(Y_{i}-\hat{g}_{j}\left(X_{i}\right)\right)\right]\end{split}$

where $D_{ij}=1$ if $D_{i}=j$,
$p_{j}\left(x_{i}\right)=\mathbb{P}\left(D_{ij}=1|X_{i}=x_{i}\right)$,
$g_{j}\left(x_{i}\right)=\mathbb{E}\left(Y_{j}|D_{ij}=1,X_{i}=x_{i}\right)$.
We should note that Luedtke and Van Der Laan (2016b) and Luedtke and Chambaz
(2020) utilize a formula similar to the one above for the binary case under
empirical process settings. In a split sample scheme,
$\hat{p}\left(\cdot\right)$ and $\hat{g}\left(\cdot\right)$ that are applied
to each $X_{i}$ are obtained in a different subsample that excludes
$\\{X_{i}\\}^{n^{\prime}}_{i=1}$. The goal is to show that