However, since $\gamma^{\ast}=\pi^{\ast}$ when
$n^{\textup{\text{tr}}}=\infty$, it follows that the display above is equal to

$\displaystyle\pi^{\ast}+\frac{\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[s_{\pi^{\ast}}]}{\mathbb{E}_{1}[s_{\pi^{\ast}}]-\mathbb{E}_{0}[s_{\pi^{\ast}}]},$

which is identical to display (15) because
$\mathbb{E}_{1}[s_{\pi^{\ast}}]-\mathbb{E}_{0}[s_{\pi^{\ast}}]=\mathcal{I}(\pi^{\ast})$
by virtue of Lemma (2.2). Therefore, when $n^{\textup{\text{tr}}}=\infty$, the
quantifier $\widehat{\pi}_{s_{\gamma^{\ast}}}^{(a)}$ mimics the mixture MLE
typically employed when the component densities are known. Thus, overall, the
optimality of $s_{\gamma^{\ast}}$ makes sense in this special setting, since
it agrees with what is already known about efficient estimation in parametric
statistics.

###  2.6 SELSE vs. EMQ & MLLS

Having provided intuition for using $f=s_{\gamma^{\ast}}$, we briefly compare
$\widehat{\pi}_{s_{\gamma^{\ast}}}^{(a)}$ against EMQ and MLLS. We motivate
this by confronting an important question: what is the need for a new
quantifier, in the first place? On the one hand, if we focus only on existing
ACC / PACC quantifiers, then we have already discussed the answer to this in
detail: $\widehat{\pi}_{s_{\gamma^{\ast}}}^{(a)}$ has the smallest possible
asymptotic variance matrix among all ACC / PACC quantifiers. However, as
subsection (1.3.2) thoroughly points out, there are many other quantifiers
besides CC variants in use. Since our optimality result only holds for the ACC
/ PACC family, one should therefore wonder: how do those other quantifiers
compare against $\widehat{\pi}_{s_{\gamma^{\ast}}}^{(a)}$?

This question will be answered rigorously in the Theoretical Results section
for a broad class of quantifiers, so for now, we restrict ourselves to a high-
level comparison against specifically EMQ and MLLS, as we have already
introduced these approaches in detail. As discussed in subsection (2.2.2), EMQ
and MLLS are both based on the maximum likelihood principle: under ideal
conditions, EMQ approximates the standard MLE for the classical mixture
problem described at the end of subsection (2.5.2), and MLLS approximates the
MLE for the version of the classical mixture problem that arises when the
original test set has been transformed, i.e., $X_{i}^{\textup{\text{te}}}$ in
the test set has been replaced by $f(X_{i}^{\textup{\text{te}}})$ for some
calibrated, soft classifier $f$.

The fact that both EMQ and MLLS are based on the maximum likelihood principle
imply that EMQ and MLLS are optimal when the assumptions of the classical
mixture setting are met, which includes the assumption that the component
densities $p_{y}$ are known. However, as discussed at the end of subsection
(2.5.2), unless $n^{\textup{\text{tr}}}>>n^{\textup{\text{te}}}$, this
assumption is not valid for quantification tasks. This should cause one to be
skeptical about the optimality of EMQ and MLLS for quantification, because
intuitively, those methods are based on maximizing approximations of
likelihood functions formed via the train data, yet their final quantifiers
are not adjusted to account for the error in those very approximations. This
can be problematic when $n^{\textup{\text{tr}}}\asymp n^{\textup{\text{te}}}$
or $n^{\textup{\text{tr}}}<<n^{\textup{\text{te}}}$, because in those
situations, the relative uncertainty in the approximated likelihoods are
higher. In contrast, $\widehat{\pi}_{s_{\gamma^{\ast}}}^{(a)}$ accounts for
the uncertainty in the component densities $p_{y}$, as seen from our earlier
analysis in subsection (2.5.1). To recap, this is because
$f=s_{\gamma^{\ast}}$ minimizes
$A_{f}^{-1}\textup{\text{Var}}_{\gamma^{\ast}}[f]A_{f}^{-T}$, and the
dependence of $\gamma^{\ast}$ on
$n^{\textup{\text{te}}},n^{\textup{\text{tr}}}$ and $\pi^{\textup{\text{tr}}}$
enables $\textup{\text{Var}}_{\gamma^{\ast}}[f]$ to properly balance the
varying levels of uncertainty among the different sources of data. For this
reason, we would expect $\widehat{\pi}_{s_{\gamma^{\ast}}}$ to perform better
than EMQ and MLLS, especially when $n^{\textup{\text{tr}}}\asymp
n^{\textup{\text{te}}}$ or $n^{\textup{\text{tr}}}<<n^{\textup{\text{te}}}$.

###  2.7 Auxiliary Lemmas & Proofs

######  Lemma 2.4 (Cauchy-Schwarz Equality Condition).

Suppose that $\phi$ and $\zeta$ are $\mathbb{R}^{m}$-valued random vectors,
and that $\Upsilon$ is the density function for their joint distribution. If
$\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]$ is invertible and

$\lambda_{\textup{max}}\big{(}\mathbb{E}_{\Upsilon}[\phi\phi^{\prime}]-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\mathbb{E}_{\Upsilon}[\zeta\phi^{\prime}]\big{)}=0,$

then

$\phi=\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\quad\textup{
a.e. }[\Upsilon].$

######  Proof of Lemma (2.4).

The proof of this Lemma is partially modeled after the proof of Lemma 1.1 in
Tripathi, [1999]. First, observe that, for each $\alpha\in\mathbb{R}^{m}$:

$\displaystyle\alpha^{\prime}\mathbb{E}_{\Upsilon}\Big{[}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}^{\prime}\Big{]}\alpha$
$\displaystyle=\mathbb{E}_{\Upsilon}\Big{[}\big{\\{}\alpha^{\prime}\phi-\alpha^{\prime}\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}^{2}\Big{]}$
$\displaystyle\geq 0.$

At the same time, since
$\lambda_{\textup{max}}\big{(}\mathbb{E}_{\Upsilon}[\phi\phi^{\prime}]-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\mathbb{E}_{\Upsilon}[\zeta\phi^{\prime}]\big{)}=0$,
we also have that:

$\displaystyle\alpha^{\prime}\mathbb{E}_{\Upsilon}\Big{[}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}^{\prime}\Big{]}\alpha$
$\displaystyle=\alpha^{\prime}\mathbb{E}_{\Upsilon}\Big{[}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}\big{\\{}\phi^{\prime}-\zeta^{\prime}\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\mathbb{E}_{\Upsilon}[\zeta\phi^{\prime}]\big{\\}}\Big{]}\alpha$
$\displaystyle=\alpha^{\prime}\big{\\{}\mathbb{E}_{\Upsilon}[\phi\phi^{\prime}]-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\mathbb{E}_{\Upsilon}[\zeta\phi^{\prime}]\big{\\}}\alpha$
$\displaystyle\leq||\alpha||_{2}^{2}\lambda_{\textup{max}}\big{(}\mathbb{E}_{\Upsilon}[\phi\phi^{\prime}]-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\mathbb{E}_{\Upsilon}[\zeta\phi^{\prime}]\big{)}$
$\displaystyle=0,$

for each $\alpha\in\mathbb{R}^{m}$. Thus, whenever
$\lambda_{\textup{max}}\big{(}\mathbb{E}_{\Upsilon}[\phi\phi^{\prime}]-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\mathbb{E}_{\Upsilon}[\zeta\phi^{\prime}]\big{)}=0$,
it follows that:

$\displaystyle\implies\alpha^{\prime}\mathbb{E}_{\Upsilon}\Big{[}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}^{\prime}\Big{]}\alpha=0\qquad\forall\
\alpha\in\mathbb{R}^{m}$
$\displaystyle\implies\mathbb{E}_{\Upsilon}\Big{[}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}^{\prime}\Big{]}=0_{m\times
m}$
$\displaystyle\implies\text{Tr}\Big{\\{}\mathbb{E}_{\Upsilon}\Big{[}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}\big{\\{}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{\\}}^{\prime}\Big{]}\Big{\\}}=0$
$\displaystyle\implies\mathbb{E}_{\Upsilon}\Big{[}\big{|}\big{|}\phi-\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\big{|}\big{|}_{2}^{2}\Big{]}=0$
$\displaystyle\implies\phi=\mathbb{E}_{\Upsilon}[\phi\zeta^{\prime}]\mathbb{E}_{\Upsilon}[\zeta\zeta^{\prime}]^{-1}\zeta\quad\text{a.e.}\quad[\Upsilon],$

as desired. ∎

######  Proof of Lemma (2.2).

Let any $i\in[q]$ and any $y\in[m]$ be given. The ${(i,y)}^{\text{th}}$ entry
of $A_{f}$ can be rewritten as:

$\displaystyle\big{[}A_{f}\big{]}_{i,y}$
$\displaystyle=\mathbb{E}_{y}[f_{i}]-\mathbb{E}_{0}[f_{i}]$
$\displaystyle=\int_{\mathcal{X}}(p_{y}(x)-p_{0}(x))f_{i}(x)d\mu(x)$
$\displaystyle=\int_{\mathcal{X}}p_{\beta}(x)\frac{p_{y}(x)-p_{0}(x)}{p_{\beta}(x)}f_{i}(x)d\mu(x)$
$\displaystyle=\int_{\mathcal{X}}p_{\beta}(x)s_{\beta,y}(x)f_{i}(x)d\mu(x)$
$\displaystyle=\mathbb{E}_{\beta}\big{[}f_{i}s_{\beta,y}\big{]}.$

This implies that $A_{f}=\mathbb{E}_{\beta}\big{[}fs_{\beta}^{T}\big{]}$. Also
note that $\mathbb{E}_{\beta}[s_{\beta}]=0$, so
$\mathbb{E}_{\beta}\big{[}fs_{\beta}^{T}\big{]}=\mathbb{E}_{\beta}\big{[}fs_{\beta}^{T}\big{]}-\mathbb{E}_{\beta}[f]\mathbb{E}_{\beta}[s_{\beta}]^{T}=\textup{\text{Cov}}_{\beta}[f,s_{\beta}]$,
and so

$A_{f}=\mathbb{E}_{\beta}\big{[}fs_{\beta}^{T}\big{]}=\textup{\text{Cov}}_{\beta}[f,s_{\beta}],$

as claimed. ∎

######  Lemma 2.5 (Covariance Matrix of a Finite Mixture).

Let $\beta$ be a vector in the $m+1$ dimensional probability simplex. Then,
for any function $f:\mathcal{X}\mapsto\mathbb{R}^{q}$, $q\geq 1$, we have
that:

$\textup{\text{Var}}_{\beta}[f]=\sum_{y=0}^{m}\beta_{y}\textup{\text{Var}}_{y}[f]+A_{f}\mathcal{I}(\beta;\textup{Cat})^{-1}A_{f}^{T},$

where

$\mathcal{I}(\beta;\textup{Cat})^{-1}:=\begin{bmatrix}\beta_{1}(1-\beta_{1})&-\beta_{1}\beta_{2}&\ldots&-\beta_{1}\beta_{m}\\\
-\beta_{2}\beta_{1}&\beta_{2}(1-\beta_{2})&\ldots&-\beta_{2}\beta_{m}\\\
\vdots&\vdots&\ddots&\vdots\\\
-\beta_{m}\beta_{1}&-\beta_{m}\beta_{2}&\ldots&\beta_{m}(1-\beta_{m})\end{bmatrix}\in\mathbb{R}^{m\times
m}.$

######  Proof of Lemma (2.5).

Observe that:

$\displaystyle\textup{\text{Var}}_{\beta}[f]$
$\displaystyle=\mathbb{E}_{\beta}[ff^{T}]-\mathbb{E}_{\beta}[f]\mathbb{E}_{\beta}[f]^{T}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\mathbb{E}_{y}[ff^{T}]-\mathbb{E}_{\beta}[f]\mathbb{E}_{\beta}[f]^{T}.$

And that:

$\displaystyle\mathbb{E}_{\beta}[f]\mathbb{E}_{\beta}[f]^{T}$
$\displaystyle=\Bigg{(}\sum_{y=0}^{m}\beta_{y}\mathbb{E}_{y}[f]\Bigg{)}\Bigg{(}\sum_{y=0}^{m}\beta_{y}\mathbb{E}_{y}[f]\Bigg{)}^{T}$
$\displaystyle=\sum_{y=0}^{m}\sum_{z=0}^{m}\beta_{y}\beta_{z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}$
$\displaystyle=\sum_{y=0}^{m}(\beta_{y})^{2}\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}+\sum_{y\neq
z}\beta_{y}\beta_{z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}.$

Thus:

$\displaystyle\implies\textup{\text{Var}}_{\beta}[f]$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\mathbb{E}_{y}[ff^{T}]-\sum_{y=0}^{m}(\beta_{y})^{2}\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}-\sum_{y\neq
z}\beta_{y}\beta_{z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\Big{[}\mathbb{E}_{y}[ff^{T}]-\beta_{y}\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}\Big{]}-\sum_{y\neq
z}\beta_{y}\beta_{z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\Big{[}\big{(}\mathbb{E}_{y}[ff^{T}]-\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}\big{)}+\big{(}\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}-\beta_{y}\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}\big{)}\Big{]}$
$\displaystyle\qquad\qquad-\sum_{y\neq
z}\beta_{y}\beta_{z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\Big{[}\textup{\text{Var}}_{y}[f]+\big{(}1-\beta_{y}\big{)}\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}\Big{]}-\sum_{y\neq
z}\beta_{y}\beta_{z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\textup{\text{Var}}_{y}[f]+\sum_{y=0}^{m}\beta_{y}\big{(}1-\beta_{y}\big{)}\mathbb{E}_{y}[f]\mathbb{E}_{y}[f]^{T}-\sum_{y\neq
z}\beta_{y}\beta_{z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}.$

Define:

$c_{y,z}=\begin{cases}\beta_{y}\big{(}1-\beta_{y}\big{)}&y=z\\\
-\beta_{y}\beta_{z}&y\neq z.\end{cases}$

Then we have that:

$\displaystyle\textup{\text{Var}}_{\beta}[f]$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\textup{\text{Var}}_{y}[f]+\sum_{y=0}^{m}\sum_{z=0}^{m}c_{y,z}\mathbb{E}_{y}[f]\mathbb{E}_{z}[f]^{T}.$

Now, the above equality holds for any function
$f:\mathcal{X}\mapsto\mathbb{R}^{m}$, so it also holds for the function given
by $f(x)-\mathbb{E}_{0}[f]$. Thus, we have that:

$\displaystyle\implies\textup{\text{Var}}_{\beta}\Big{[}f-\mathbb{E}_{0}[f]\Big{]}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\textup{\text{Var}}_{y}\Big{[}f-\mathbb{E}_{0}[f]\Big{]}+\sum_{y=0}^{m}\sum_{z=0}^{m}c_{y,z}\mathbb{E}_{y}\Big{[}f-\mathbb{E}_{0}[f]\Big{]}\mathbb{E}_{z}\Big{[}f-\mathbb{E}_{0}[f]\Big{]}^{T}.$
$\displaystyle\implies\textup{\text{Var}}_{\beta}[f]$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\textup{\text{Var}}_{y}[f]+\sum_{y=0}^{m}\sum_{z=0}^{m}c_{y,z}\big{(}\mathbb{E}_{y}[f]-\mathbb{E}_{0}[f]\big{)}\big{(}\mathbb{E}_{z}[f]-\mathbb{E}_{0}[f]\big{)}^{T}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\textup{\text{Var}}_{y}[f]+\sum_{y=1}^{m}\sum_{z=1}^{m}c_{y,z}\big{(}\mathbb{E}_{y}[f]-\mathbb{E}_{0}[f]\big{)}\big{(}\mathbb{E}_{z}[f]-\mathbb{E}_{0}[f]\big{)}^{T}$
$\displaystyle=\sum_{y=0}^{m}\beta_{y}\textup{\text{Var}}_{y}[f]+A_{f}\mathcal{I}(\beta;\text{Cat})^{-1}A_{f}^{T}.$

∎

######  Proof of Lemma (2.1).

By the assumed independence properties of our data, we have that:

$\displaystyle\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{I}}}}\Big{[}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[f]-\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[f]\Big{]}$
$\displaystyle=\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{te,I}}}}\Big{[}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[f]\Big{]}+\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{tr,I}}}}\Big{[}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[f]\Big{]}$
$\displaystyle=\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{te,I}}}}\Big{[}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[f]\Big{]}+\sum_{y=0}^{m}(\pi_{y}^{\ast})^{2}\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{tr,I}}}}\Big{[}\widehat{\mathbb{E}}_{y}^{\textup{\text{tr,I}}}[f]\Big{]}$
$\displaystyle=\frac{1}{\tfrac{1}{2}n^{\textup{\text{te}}}}\textup{\text{Var}}_{\pi^{\ast}}[f]+\frac{1}{\tfrac{1}{2}n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\textup{\text{Var}}_{y}[f]$
$\displaystyle=\frac{1}{\tfrac{1}{2}n^{\textup{\text{te}}}}\Bigg{(}\sum_{y=0}^{m}\pi_{y}^{\ast}\textup{\text{Var}}_{y}[f]+A_{f}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}A_{f}^{T}\Bigg{)}$
$\displaystyle\qquad\qquad+\frac{1}{\tfrac{1}{2}n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\textup{\text{Var}}_{y}[f],$

where the last equality follows from Lemma (2.5). Thus,

$\displaystyle\frac{1}{2}\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{I}}}}\Big{[}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[f]-\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[f]\Big{]}$
$\displaystyle=\frac{1}{n^{\textup{\text{te}}}}\Bigg{(}\sum_{y=0}^{m}\pi_{y}^{\ast}\textup{\text{Var}}_{y}[f]+A_{f}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}A_{f}^{T}\Bigg{)}$
$\displaystyle\qquad\qquad+\frac{1}{n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\textup{\text{Var}}_{y}[f]$
$\displaystyle=\sum_{y=0}^{m}\Bigg{(}\frac{\pi_{y}^{\ast}}{n^{\textup{\text{te}}}}+\frac{1}{n^{\textup{\text{tr}}}}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\Bigg{)}\textup{\text{Var}}_{y}[f]+\frac{1}{n^{\textup{\text{te}}}}A_{f}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}A_{f}^{T}$
$\displaystyle=\Bigg{[}\frac{1}{n^{\textup{\text{te}}}}+\frac{1}{n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\Bigg{]}\sum_{y=0}^{m}\gamma_{y}^{\ast}\textup{\text{Var}}_{y}[f]+\frac{1}{n^{\textup{\text{te}}}}A_{f}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}A_{f}^{T}$
$\displaystyle=\Bigg{[}\frac{1}{n^{\textup{\text{te}}}}+\frac{1}{n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\Bigg{]}\Big{(}\textup{\text{Var}}_{\gamma^{\ast}}[f]-A_{f}\mathcal{I}(\gamma^{\ast};\text{Cat})^{-1}A_{f}^{T}\Big{)}$
$\displaystyle\qquad+\frac{1}{n^{\textup{\text{te}}}}A_{f}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}A_{f}^{T},$

where the last equality again follows from Lemma (2.5). Thus, if $q=m$ and
$A_{f}$ is positive definite, it follows that:

$\displaystyle\frac{1}{2}\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{I}}}}\Big{[}A_{f}^{-1}(\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[f]-\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[f])\Big{]}$
$\displaystyle=\frac{1}{2}A_{f}^{-1}\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{I}}}}\Big{[}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[f]-\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[f]\Big{]}A_{f}^{-T}$
$\displaystyle=\Bigg{[}\frac{1}{n^{\textup{\text{te}}}}+\frac{1}{n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\Bigg{]}\Big{(}A_{f}^{-1}\textup{\text{Var}}_{\gamma^{\ast}}[f]A_{f}^{-T}-\mathcal{I}(\gamma^{\ast};\text{Cat})^{-1}\Big{)}$
$\displaystyle\qquad+\frac{1}{n^{\textup{\text{te}}}}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1},$
(16)

as desired. ∎

######  Proof of Lemma (2.3).

First, note that
$A_{s_{\beta}}=\textup{\text{Var}}_{\beta}[s_{\beta}]\equiv\mathcal{I}(\beta)$
by Lemma (2.2), so $A_{s_{\beta}}$ is positive definite as claimed because
$\mathcal{I}(\beta)$ is assumed to be positive definite. Thus, the inverses of
both matrices are well-defined. This also means that

$\displaystyle
A_{s_{\beta}}^{-1}\textup{\text{Var}}_{\beta}[s_{\beta}](A_{s_{\beta}}^{T})^{-1}$
$\displaystyle=\mathcal{I}(\beta)^{-1}\mathcal{I}(\beta)\mathcal{I}(\beta)^{-1}$
$\displaystyle=\mathcal{I}(\beta)^{-1},$

as was also claimed. Next, we need to show that
$\mathcal{I}(\beta)^{-1}\preceq
A_{f}^{-1}\textup{\text{Var}}_{\beta}[f](A_{f}^{T})^{-1}$ for all functions
$f:\mathcal{X}\mapsto\mathbb{R}^{m}$ for which $A_{f}$ is positive definite.
However, before we do that, it will aid us greatly in our endeavor if we first
take a small digression, and prove the following two facts:

  * •

$\textup{\text{Var}}_{\beta}[f]$ is positive definite.

  * •

$\textup{\text{Var}}_{\beta}[g]\preceq\mathcal{I}(\beta)$ for any
$g:\mathcal{X}\mapsto\mathbb{R}^{m}$ satisfying
$\textup{\text{Var}}_{\beta}[g]=A_{g}$ and $\mathbb{E}_{\beta}[g]=0$.

So, let us start by showing that $\textup{\text{Var}}_{\beta}[f]$ is positive
definite. Note that the positive definiteness of $A_{f}$ means that its rows
are linearly independent, and so:

$\displaystyle A_{f}\text{ is positive definite}$
$\displaystyle\implies\nexists\alpha\in\mathbb{R}^{m}/0_{m}\ \text{ s.t. }\
\alpha^{\prime}A_{f}=0_{m}^{\prime}$
$\displaystyle\implies\nexists\alpha\in\mathbb{R}^{m}/0_{m}\ \text{ s.t. }\
\alpha^{\prime}(\mathbb{E}_{j}[f]-\mathbb{E}_{0}[f])=0\ \forall j\in[m]$
$\displaystyle\implies\nexists\alpha\in\mathbb{R}^{m}/0_{m}\ \text{ s.t. }\
\mathbb{E}_{j}[\alpha^{\prime}f]=\mathbb{E}_{0}[\alpha^{\prime}f]\ \forall
j\in[m]$ $\displaystyle\implies\forall\alpha\in\mathbb{R}^{m}/0_{m},\ \exists
j\in[m]\ \text{ s.t. }\
\mathbb{E}_{j}[\alpha^{\prime}f]\neq\mathbb{E}_{0}[\alpha^{\prime}f].$

Next, we will prove that

$\forall\alpha\in\mathbb{R}^{m}/0_{m},\ \exists j\in[m]\ \text{ s.t. }\
\mathbb{E}_{j}[\alpha^{\prime}f]\neq\mathbb{E}_{0}[\alpha^{\prime}f]\implies\forall\alpha\in\mathbb{R}^{m}/0_{m},\
\nexists\eta\in\mathbb{R}\ \text{ s.t. }\
\mathbb{P}_{\beta}[\alpha^{\prime}f=\eta]=1$ (17)

by proving the contrapositive, i.e., that:

$\exists\alpha\in\mathbb{R}^{m}/0_{m},\eta\in\mathbb{R}\ \text{ s.t. }\
\mathbb{P}_{\beta}[\alpha^{\prime}f=\eta]=1\implies\exists\alpha\in\mathbb{R}^{m}/0_{m}\
\text{ s.t. }\
\mathbb{E}_{j}[\alpha^{\prime}f]=\mathbb{E}_{0}[\alpha^{\prime}f]\ \forall
j\in[m].$

Towards that end, note that since
$\mathbb{P}_{\beta}[\alpha^{\prime}f=\eta]=\sum_{y=0}^{m}\beta_{y}\mathbb{P}_{y}[\alpha^{\prime}f=\eta]$
and $\beta_{y}>0$ for all $y\in\mathcal{Y}$, if
$\mathbb{P}_{\beta}[\alpha^{\prime}f=\eta]=1$ then it must be that
$\mathbb{P}_{y}[\alpha^{\prime}f=\eta]=1$ for all $y\in\mathcal{Y}$ as well.
Ergo:

$\displaystyle\exists\alpha\in\mathbb{R}^{m}/0_{m},\eta\in\mathbb{R}\ \text{
s.t. }\ \mathbb{P}_{\beta}[\alpha^{\prime}f=\eta]=1$
$\displaystyle\implies\exists\alpha\in\mathbb{R}^{m}/0_{m},\eta\in\mathbb{R}\
\text{ s.t. }\ \mathbb{P}_{y}[\alpha^{\prime}f=\eta]=1\ \forall
y\in\mathcal{Y}$
$\displaystyle\implies\exists\alpha\in\mathbb{R}^{m}/0_{m},\eta\in\mathbb{R}\
\text{ s.t. }\ \mathbb{E}_{y}[\alpha^{\prime}f]=\eta\ \forall y\in\mathcal{Y}$
$\displaystyle\implies\exists\alpha\in\mathbb{R}^{m}/0_{m}\ \text{ s.t. }\
\mathbb{E}_{j}[\alpha^{\prime}f]=\mathbb{E}_{0}[\alpha^{\prime}f]\ \forall
j\in[m].$

Thus, the implication in display (17) is indeed true, so it follows that:

$\displaystyle A_{f}\text{ is positive definite}$
$\displaystyle\implies\forall\alpha\in\mathbb{R}^{m}/0_{m},\
\nexists\eta\in\mathbb{R}\ \text{ s.t. }\
\mathbb{P}_{\beta}[\alpha^{\prime}f=\eta]=1$
$\displaystyle\implies\forall\alpha\in\mathbb{R}^{m}/0_{m},\
\textup{\text{Var}}_{\beta}[\alpha^{\prime}f]>0$
$\displaystyle\implies\forall\alpha\in\mathbb{R}^{m}/0_{m},\
\alpha^{\prime}\textup{\text{Var}}_{\beta}[f]\alpha>0$
$\displaystyle\implies\textup{\text{Var}}_{\beta}[f]\text{ is positive
definite}.$

Next, we establish that
$\textup{\text{Var}}_{\beta}[g]\preceq\mathcal{I}(\beta)$ for any
$g:\mathcal{X}\mapsto\mathbb{R}^{m}$ satisfying
$\textup{\text{Var}}_{\beta}[g]=A_{g}$ and $\mathbb{E}_{\beta}[g]=0$. Towards
that end, observe that by Lemma (2.2), we have that
$A_{g}=\mathbb{E}_{\beta}[gs_{\beta}^{T}]$, meaning that
$\textup{\text{Var}}_{\beta}[g]=\mathbb{E}_{\beta}[gs_{\beta}^{T}]$. So, for
any vector $w\in\mathbb{R}^{m}$:

$\displaystyle w^{T}\textup{\text{Var}}_{\beta}[g]w$
$\displaystyle=w^{T}\mathbb{E}_{\beta}[gs_{\beta}^{T}]w$
$\displaystyle=\mathbb{E}_{\beta}\big{[}(w^{T}g)(w^{T}s_{\beta})\big{]}$
$\displaystyle\leq\sqrt{\mathbb{E}_{\beta}\big{[}(w^{T}g)^{2}\big{]}\mathbb{E}_{\beta}\big{[}(w^{T}s_{\beta})^{2}\big{]}}$
$\displaystyle=\sqrt{\textup{\text{Var}}_{\beta}[w^{T}g]\textup{\text{Var}}_{\beta}[w^{T}s_{\beta}]}$
$\displaystyle=\sqrt{w^{T}\textup{\text{Var}}_{\beta}[g]w\cdot
w^{T}\mathcal{I}(\beta)w},$

where the second to last line is because
$\mathbb{E}_{\beta}[g]=0=\mathbb{E}_{\beta}[s_{\beta}]$. Thus, we have that
$w^{T}\textup{\text{Var}}_{\beta}[g]w\leq w^{T}\mathcal{I}(\beta)w$, meaning
that $\textup{\text{Var}}_{\beta}[g]\preceq\mathcal{I}(\beta)$.

Having completed our digression, we now turn to proving that
$\mathcal{I}(\beta)^{-1}\preceq
A_{f}^{-1}\textup{\text{Var}}_{\beta}[f](A_{f}^{T})^{-1}$ for all functions
$f:\mathcal{X}\mapsto\mathbb{R}^{m}$ for which $A_{f}$ is positive definite.
Note that this is equivalent to proving that
$A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\preceq\mathcal{I}(\beta)$.
Now, given any function $f$ such that $A_{f}$ is positive definite, it follows
from our digression that $\textup{\text{Var}}_{\beta}[f]$ is also positive
definite, so its inverse exists and we can define a new function
$g_{f}:\mathcal{X}\mapsto\mathbb{R}^{m}$ as follows:

$g_{f}:=A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}(f-\mathbb{E}_{\beta}[f]).$

Observe that:

$\displaystyle A_{g_{f}}\textup{\text{Var}}_{\beta}[g_{f}]^{-1}A_{g_{f}}^{T}$
$\displaystyle=\Big{(}A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\Big{)}\Big{(}A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}\textup{\text{Var}}_{\beta}[f]\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\Big{)}^{-1}\Big{(}A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\Big{)}^{T}$
$\displaystyle=\Big{(}A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\Big{)}\Big{(}A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\Big{)}^{-1}\Big{(}A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\Big{)}$
$\displaystyle=A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}.$

Thus, given any $f$ for which $A_{f}$ is positive definite, in order to show
that
$A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\preceq\mathcal{I}(\beta)$,
it suffices to instead show that
$A_{g_{f}}\textup{\text{Var}}_{\beta}[g_{f}]^{-1}A_{g_{f}}^{T}\preceq\mathcal{I}(\beta)$.
Next, note that

$\displaystyle\textup{\text{Var}}_{\beta}[g_{f}]$
$\displaystyle=A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}\textup{\text{Var}}_{\beta}[f]\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}$
$\displaystyle=A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}$
$\displaystyle=A_{A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}f}$
$\displaystyle=A_{g_{f}},$

so $\textup{\text{Var}}_{\beta}[g_{f}]=A_{g_{f}}$. Thus,
$A_{g_{f}}\textup{\text{Var}}_{\beta}[g_{f}]^{-1}A_{g_{f}}^{T}=\textup{\text{Var}}_{\beta}[g_{f}]$,
so it suffices to instead show that
$\textup{\text{Var}}_{\beta}[g_{f}]\preceq\mathcal{I}(\beta)$. By our
digression from earlier, this is indeed true, because
$\textup{\text{Var}}_{\beta}[g_{f}]=A_{g_{f}}$ and
$\mathbb{E}_{\beta}[g_{f}]=0$. Therefore, we indeed have that
$\mathcal{I}(\beta)^{-1}\preceq
A_{f}^{-1}\textup{\text{Var}}_{\beta}[f](A_{f}^{T})^{-1}$ for all $f$ for
which $A_{f}$ is positive definite.

Finally, we will prove that if the eigenvalues of
$A_{f}^{-1}\textup{\text{Var}}_{\beta}[f](A_{f}^{T})^{-1}$ and
$\mathcal{I}(\beta)^{-1}$ are identical, then there exists a constant vector
$c\in\mathbb{R}^{m}$ and a constant invertible matrix $B\in\mathbb{R}^{m\times
m}$ such that $f=Bs_{\beta}+c$ a.e. $[p_{\beta}]$. Towards that end, note that
if the eigenvalues of
$A_{f}^{-1}\textup{\text{Var}}_{\beta}[f](A_{f}^{T})^{-1}$ and
$\mathcal{I}(\beta)^{-1}$ are identical, then the eigenvalues of
$A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}$ and $\mathcal{I}(\beta)$
are as well. So,
$\text{Tr}\big{\\{}A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\big{\\}}=\text{Tr}\big{\\{}\mathcal{I}(\beta)\big{\\}}$,
i.e.,
$\text{Tr}\big{\\{}\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\big{\\}}=0$.
But, we just showed that $\mathcal{I}(\beta)^{-1}\preceq
A_{f}^{-1}\textup{\text{Var}}_{\beta}[f](A_{f}^{T})^{-1}$, so
$\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}$ is
positive semidefinite, i.e., all the eigenvalues of
$\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}$ must be
non-negative. Thus, the fact that
$\text{Tr}\big{\\{}\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\big{\\}}=0$
means that the eigenvalues of
$\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}$ must
actually all be equal to zero. In particular, we have that
$\lambda_{\textup{max}}\big{(}\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\big{)}=0$.

In addition, note that
$\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}$ can be
rewritten as:

$\displaystyle\mathbb{E}_{\beta}[s_{\beta}s_{\beta}^{T}]-\mathbb{E}_{\beta}[s_{\beta}(f-\mathbb{E}_{\beta}[f])^{T}]\mathbb{E}_{\beta}[(f-\mathbb{E}_{\beta}[f])(f-\mathbb{E}_{\beta}[f])^{T}]^{-1}\mathbb{E}_{\beta}[(f-\mathbb{E}_{\beta}[f])s_{\beta}^{T}].$

So, since
$\lambda_{\textup{max}}\big{(}\mathcal{I}(\beta)-A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}A_{f}\big{)}=0$
and $\textup{\text{Var}}_{\beta}[f]$ is positive definite, it follows from
Lemma (2.4) that

$\displaystyle s_{\beta}$
$\displaystyle=\mathbb{E}_{\beta}[s_{\beta}(f-\mathbb{E}_{\beta}[f])^{T}]\mathbb{E}_{\beta}[(f-\mathbb{E}_{\beta}[f])(f-\mathbb{E}_{\beta}[f])^{T}]^{-1}(f-\mathbb{E}_{\beta}[f])\quad\textup{
a.e. }[p_{\beta}]$
$\displaystyle=\mathbb{E}_{\beta}[s_{\beta}f^{T}]\textup{\text{Var}}_{\beta}[f]^{-1}(f-\mathbb{E}_{\beta}[f])\quad\textup{
a.e. }[p_{\beta}]$
$\displaystyle=A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}(f-\mathbb{E}_{\beta}[f])\quad\textup{
a.e. }[p_{\beta}].$

Since $A_{f}$ and $\textup{\text{Var}}_{\beta}[f]^{-1}$ are both invertible,
it follows that $A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1}$ is also
invertible. Thus, the display above implies that:

$\displaystyle f$
$\displaystyle=(A_{f}^{T}\textup{\text{Var}}_{\beta}[f]^{-1})^{-1}s_{\beta}+\mathbb{E}_{\beta}[f]\quad\textup{
a.e. }[p_{\beta}]$
$\displaystyle=\textup{\text{Var}}_{\beta}[f]A_{f}^{-T}s_{\beta}+\mathbb{E}_{\beta}[f]\quad\textup{
a.e. }[p_{\beta}].$

Set $c=\mathbb{E}_{\beta}[f]$ and
$B=\textup{\text{Var}}_{\beta}[f]A_{f}^{-T}$, where $B$ is invertible because
$\textup{\text{Var}}_{\beta}[f]$ and $A_{f}^{-T}$ are both invertible. Thus,
we have found a constant invertible matrix $B\in\mathbb{R}^{m\times m}$ and
constant vector $c\in\mathbb{R}^{m}$ such that $f=Bs_{\beta}+c\textup{ a.e.
}[p_{\beta}]$, which proves the desiderata. ∎

##  3 Theoretical Results

In this section, we dive into some of SELSE’s theoretical properties, with the
ultimate goal of showing that SELSE is semiparametric efficient. Towards that
end, the section is organized as follows. First, we make the Methodology
section’s discussion of SELSE’s asymptotic behavior rigorous by providing a
mathematical foundation for the intuitive arguments used in that section. This
includes a more precise analysis of SELSE’s first order error term, and a
characterization of the rate of its second order error term. All of this is
done in the traditional quantification setting discussed in the Methodology
section.

Second, having established SELSE’s asymptotic behavior in the traditional
quantification setting, we then set out to prove that SELSE is semiparametric
efficient. To that end, we motivate why a semiparametric framework is
appealing for studying quantification in the first place, and in particular,
the performance of quantifiers. We then argue why adjusting the generative
process for our data is necessary if we want to utilize existing results from
the semiparametrics literature in our derivation of the bound.

Third, we describe two new data generating regimes that are readily handled by
the semiparametric literature and retain all key aspects of the traditional
quantification problem, as was originally described in the Methodology
section. We explain how these two regimes compare to the original, and provide
a high-level game plan of how we will use the new regimes and our previous
analysis of SELSE’s asymptotic behavior to prove that SELSE is semiparametric
efficient.

Fourth, with this game plan in mind, we then dive into the details of the two
new regimes. This includes reviewing their data generating mechanisms, as well
as stating the assumptions we make about their parameter spaces. We make sure
to present the intuition behind these assumptions, and provide justifications
for why they are either necessary or reasonable to assume. We also introduce a
large family of quantifiers $\mathcal{E}$ that we plan to develop the
semiparametric efficiency bound for.

Fifth, having described the two new regimes in precise mathematical detail, we
execute our aforementioned game plan, touring the intermediate lemmas and
theorems in the two new regimes that strategically position us to prove our
main result for SELSE. We also provide the intuition behind these intermediate
results, and in doing so, we take a deeper dive into the concept of
semiparametric efficiency.

Finally, with this groundwork in place, we present the semiparametric
efficiency bound, and show that SELSE is semiparametric efficient. We then
conclude the section by analyzing the bound, and we discuss how it reveals
deep connections between the general problem of quantification and two other
statistical estimation tasks.

###  3.1 Asymptotics of SELSE in Fixed Sequence Regime

In order to rigorously show that SELSE has the smallest possible asymptotic
variance, we first needed to formalize the intuitive arguments that were used
in subsection (2.5) to identify that matrix, and more broadly, characterize
SELSE’s overall asymptotic behavior. In particular, while those arguments were
able to correctly deduce the form of SELSE’s asymptotic variance matrix, this
conclusion could only be reached by assuming that the true score function
$s_{\gamma^{\ast}}$ was known. However, in reality, SELSE only has access to
an estimate $\widehat{s}_{\widehat{\gamma}}$. Thus, we begin this subsection
by describing the lemmas that enabled us to show that
$\widehat{s}_{\widehat{\gamma}}$ converges to $s_{\gamma^{\ast}}$, and
determine the rate at which this occurs. We then show how this result allowed
us to formally characterize the first and second order terms in SELSE’s
normalized error.

The backbone of our proof for showing the convergence of
$\widehat{s}_{\widehat{\gamma}}$ to $s_{\gamma^{\ast}}$ is a moment condition
that characterizes $s_{\gamma^{\ast}}$. As mentioned in subsection (2.5.2),
the components of $s_{\gamma^{\ast}}$ possess a special property: for each
$y\in[m]$, $s_{\gamma^{\ast},y}$ is a member of

$C_{\gamma^{\ast},y}:=\Big{\\{}h_{y}\ \Big{\lvert}\
h_{y}:\mathcal{X}\mapsto\mathbb{R},\
\textup{\text{Var}}_{\gamma^{\ast}}[h_{y}]=\mathbb{E}_{y}[h_{y}]-\mathbb{E}_{0}[h_{y}]\Big{\\}},$
(18)

and among all functions $h_{y}$ in that set,
$\mathbb{E}_{y}[h_{y}]-\mathbb{E}_{0}[h_{y}]$ is uniquely maximized by
choosing $h_{y}=s_{\gamma^{\ast},y}$. This property follows directly from
Lemma (2.3), and was our motivation for how we form the estimate
$\widehat{s}_{\widehat{\gamma},y}$ in Step 3 of our algorithm. Indeed, the
constraint set

$\widehat{C}_{\widehat{\gamma},y}=\Big{\\{}h_{y}\in\mathcal{H}_{y}\text{
}:\text{
}\widehat{\textup{\text{Var}}}_{\widehat{\gamma}}^{\textup{\text{tr,II}}}[h_{y}]=\widehat{\mathbb{E}}_{y}^{\textup{\text{tr,II}}}[h_{y}]-\widehat{\mathbb{E}}_{0}^{\textup{\text{tr,II}}}[h_{y}]\Big{\\}}$

in Step 3 is the empirical counterpart to $C_{\gamma^{\ast},y}$ in display
(18), and in that step, we are choosing $\widehat{s}_{\widehat{\gamma},y}$ to
be the $h_{y}\in\widehat{C}_{\widehat{\gamma},y}$ that maximizes the
difference
$\widehat{\mathbb{E}}_{y}^{\textup{\text{tr,II}}}[h_{y}]-\widehat{\mathbb{E}}_{0}^{\textup{\text{tr,II}}}[h_{y}]$,
which is the empirical counterpart to
$\mathbb{E}_{y}[h_{y}]-\mathbb{E}_{0}[h_{y}]$. This correspondence suggests a
strategy for proving the convergence of $\widehat{s}_{\widehat{\gamma}}$:
since it seems reasonable to believe that $\widehat{s}_{\widehat{\gamma}}$
will be inside of $C_{\gamma^{\ast},y}$ for large sample sizes (with high
probability), and the unique maximization property of $s_{\gamma^{\ast}}$
implies that $\widehat{s}_{\widehat{\gamma}}=s_{\gamma^{\ast}}$ whenever it is
the case that $\widehat{s}_{\widehat{\gamma}}\in C_{\gamma^{\ast},y}$ and
$\mathbb{E}_{y}[\widehat{s}_{\widehat{\gamma},y}]-\mathbb{E}_{0}[\widehat{s}_{\widehat{\gamma},y}]=\mathbb{E}_{y}[s_{\gamma^{\ast},y}]-\mathbb{E}_{0}[s_{\gamma^{\ast},y}]$,
then in order to argue that $\widehat{s}_{\widehat{\gamma},y}\approx
s_{\gamma^{\ast},y}$, it may suffice to show that
$\mathbb{E}_{y}[\widehat{s}_{\gamma^{\ast},y}]-\mathbb{E}_{0}[\widehat{s}_{\gamma^{\ast},y}]\approx\mathbb{E}_{y}[s_{\gamma^{\ast},y}]-\mathbb{E}_{0}[s_{\gamma^{\ast},y}]$.
That is, it is reasonable to believe that bounding the magnitude of the
difference

$\big{(}\mathbb{E}_{y}[s_{\gamma^{\ast},y}]-\mathbb{E}_{0}[s_{\gamma^{\ast},y}]\big{)}-\big{(}\mathbb{E}_{y}[\widehat{s}_{\gamma^{\ast},y}]-\mathbb{E}_{0}[\widehat{s}_{\gamma^{\ast},y}]\big{)}$
(19)

will lead to a bound on
$\widehat{s}_{\widehat{\gamma},y}-s_{\gamma^{\ast},y}$. To bound the
difference above, we consider its positive and negative parts separately. The
following lemma addresses its positive part.

######  Lemma 3.1 (Rate for Learning Diagonal of $\mathcal{I}(\gamma^{\ast})$,
When $\gamma^{\ast}$ is Known.).

Under Assumptions (A1), (• ‣ A2), (A3), (A5), and (A6) in the Appendix, we
have for each $y\in[m]$ that

$\big{(}\mathbb{E}_{y}[s_{\gamma^{\ast},y}]-\mathbb{E}_{0}[s_{\gamma^{\ast},y}]\big{)}-\big{(}\mathbb{E}_{y}[\widehat{s}_{\gamma^{\ast},y}]-\mathbb{E}_{0}[\widehat{s}_{\gamma^{\ast},y}]\big{)}\leq
T_{y},$

where $T_{y}>0$ is a random variable that satisfies

$\mathbb{E}_{\mathcal{D}^{\textup{\text{tr,II}}}}[T_{y}]=O\Bigg{(}\frac{1}{\sqrt{n^{\textup{\text{tr}}}}}+\lambda_{y}\Omega^{2}(s_{\gamma^{\ast},y})+\mathbb{E}_{\mathcal{D}^{\textup{\text{tr,II}}}}[\mathcal{U}_{y}(\lambda_{y})]+\frac{1}{\sqrt{\lambda_{y}}}e^{-C_{1}n^{\textup{\text{tr}}}}\Bigg{)},$

for some constant $C_{1}>0$ independent of $n^{\textup{\text{tr}}}$ or
$n^{\textup{\text{te}}}$. Further, there exists constants $C_{2},C_{3}>0$
independent of $n^{\textup{\text{tr}}}$ and $n^{\textup{\text{te}}}$ such
that, for all $a>0$,

$\displaystyle\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}[T_{y}\geq a]$
$\displaystyle\leq
16(2m+1)\Big{(}\exp\Big{\\{}-C_{2}n^{\textup{\text{tr}}}\tau(a)\Big{\\}}+\exp\Big{\\{}-C_{3}n^{\textup{\text{tr}}}\sqrt{\tau(a)}\Big{\\}}\Big{)}$
$\displaystyle\qquad+\mathbbold{1}{\Big{\\{}\lambda_{y}\Omega^{2}(s_{\gamma^{\ast},y})\geq\frac{1}{12}a\Big{\\}}}$
$\displaystyle\qquad+\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Bigg{[}\sup_{\Omega(h_{y})\leq\frac{1}{L\sqrt{\lambda_{y}}}}\Big{|}\widehat{\mathbb{E}}_{y}^{\textup{\text{tr,II}}}[h_{y}]-\mathbb{E}_{y}[h_{y}]\Big{|}\geq\frac{1}{6}a\Bigg{]}$
$\displaystyle\qquad+\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Bigg{[}\sup_{\Omega(h_{y})\leq\frac{1}{L\sqrt{\lambda_{y}}}}\Big{|}\widehat{\mathbb{E}}_{0}^{\textup{\text{tr,II}}}[h_{y}]-\mathbb{E}_{0}[h_{y}]\Big{|}\geq\frac{1}{6}a\Bigg{]},$

where
$\tau(a):=\min\big{\\{}1,a^{2},\frac{a}{\lambda_{y}\Omega^{2}(s_{\gamma^{\ast},y})}\big{\\}}$.

The proof for Lemma (3.1) can be found in the Appendix. Assumptions (A1)-(A7)
are actually analogous to the assumptions presented and thoroughly
investigated in the upcoming subsections (3.5.1)-(3.5.4), and are phrased in
terms of the semiparametric framework soon to be introduced in subsection
(3.5). The main reason for this redundancy is that it was far more convenient
to prove the lemmas and theorems in the present subsection using Assumptions
(A1)-(A7) than their semiparametric counterparts. However, to avoid
unnecessary confusion and in anticipation of subsections (3.5.1)-(3.5.4), we
hold off on describing Assumptions (A1)-(A7) here, though the curious reader
can read about them in the Appendix. The quantities $L$ and
$\mathcal{U}_{y}(\lambda_{y})$ in the statement of Lemma (3.1) will also be
formally defined in subsections (3.5.1)-(3.5.4), but essentially,
$L\in\mathbb{R}$ is a constant that can be shown to uniformly lower bound the
components of $\gamma^{\ast}$ (proven in Lemma (6.1) in the Appendix), and
$\mathcal{U}_{y}(\lambda_{y})$ denotes a sum of uniform deviation terms that
reflect the tension between the (potentially growing) complexity of the space
$\mathcal{H}_{y}$ and $n^{\textup{\text{tr}}}$, and should satisfy
$\mathbb{E}_{\mathcal{D}^{\textup{\text{tr,II}}}}[\mathcal{U}_{y}(\lambda_{y})]\to
0$ as $n^{\textup{\text{tr}}}\to\infty$.

In a nutshell, Lemma (3.1) shows that the positive part of the difference

$\big{(}\mathbb{E}_{y}[s_{\gamma^{\ast},y}]-\mathbb{E}_{0}[s_{\gamma^{\ast},y}]\big{)}-\big{(}\mathbb{E}_{y}[\widehat{s}_{\gamma^{\ast},y}]-\mathbb{E}_{0}[\widehat{s}_{\gamma^{\ast},y}]\big{)}$

approaches $0$ at a rate which depends on the number of train samples used to
approximate $s_{\gamma^{\ast}}$, the complexity of $s_{\gamma^{\ast}}$ and the
function space it lives in, as well as the amount of regularization. Provided
that $n^{\textup{\text{tr}}}\to\infty$ sufficiently quickly and
$\lambda_{y}\to 0$ sufficiently slowly, we will have that
$T_{y}=o_{\mathbb{P}}(1)$. Of course, what is considered “sufficiently quick”
or “sufficiently slow” will depend on how the complexity of $\mathcal{H}_{y}$
grows; to provide the reader a sense of what these rates look like, we
consider an example where $\mathcal{H}_{y}$ is assumed to be a union of
different RKHSs in Lemma (6.15.2) in the Appendix. Also note that Lemma (3.1)
is phrased in terms of $\widehat{s}_{\gamma^{\ast}}$, but we are interested in
$\widehat{s}_{\widehat{\gamma}}$. To be precise, $\widehat{s}_{\gamma^{\ast}}$
is the version of $\widehat{s}_{\widehat{\gamma}}$ that would have been
obtained if $\widehat{\gamma}=\gamma^{\ast}$ in Step 2 of our algorithm. The
analogue of Lemma (3.1) for $\widehat{s}_{\widehat{\gamma}}$ is Lemma (6.10)
in the Appendix– we merely opted to describe the result for
$\widehat{s}_{\gamma^{\ast}}$, since it is conceptually identical to the
result for $\widehat{s}_{\widehat{\gamma}}$ but the actual statement for the
latter is much more complicated, as it also depends on the rate at which
$\widehat{\gamma}$ estimates $\gamma^{\ast}$.

Bounding the magnitude negative part of display (19) is far easier to do than
its positive counterpart, and also depends on $T_{y}$. The main idea is that
if $\widehat{C}_{\widehat{\gamma},y}=C_{\gamma^{\ast},y}$, then the
maximization property of $s_{\gamma^{\ast},y}$ implies that (19) should be
non-negative, so if $\widehat{C}_{\widehat{\gamma},y}\approx
C_{\gamma^{\ast},y}$, then we have reason to believe it should typically not
be too negative. The degree to which $\widehat{C}_{\widehat{\gamma},y}\approx
C_{\gamma^{\ast},y}$ depends on the extent to which empirical moments can be
used to approximate population moments, and this is captured by
$\mathcal{U}_{y}(\lambda_{y})$ and hence by $T_{y}$. Combining this intuition
for the magnitude of the negative part of display (19) with Lemma (3.1)’s
bound on the positive part, we were able to prove the following result about
the error of our score function estimate.

######  Lemma 3.2 (Rate for Learning the Score Function, When $\gamma^{\ast}$
is Known.).

Under Assumptions (A1), (• ‣ A2), (A3), (A5) and (A6) in the Appendix, we have
for each $y\in[m]$ that

$\mathbb{E}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Big{[}\textup{\text{Var}}_{\gamma^{\ast}}[\widehat{s}_{\gamma^{\ast},y}-s_{\gamma^{\ast},y}]\Big{]}=O\Big{(}\mathbb{E}_{\mathcal{D}^{\textup{\text{tr,II}}}}[T_{y}]\Big{)}.$

Further, for all $a>0$,

$\displaystyle\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Big{[}\textup{\text{Var}}_{\gamma^{\ast}}[\widehat{s}_{\gamma^{\ast},y}-s_{\gamma^{\ast},y}]\geq
a\Big{]}$
$\displaystyle\leq\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}\bigg{[}T_{y}\geq\frac{1}{4}a\bigg{]}$
$\displaystyle\qquad+\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Bigg{[}\sup_{\Omega(h_{y})\leq\frac{1}{L\sqrt{\lambda_{y}}}}\Big{|}\widehat{\textup{\text{Var}}}_{\gamma^{\ast}}^{\textup{\text{tr,II}}}[h_{y}]-\textup{\text{Var}}_{\gamma^{\ast}}[h_{y}]\Big{|}\geq\frac{1}{4}a\Bigg{]}$
$\displaystyle\qquad+\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Bigg{[}\sup_{\Omega(h_{y})\leq\frac{1}{L\sqrt{\lambda_{y}}}}\Big{|}\widehat{\mathbb{E}}_{y}^{\textup{\text{tr,II}}}[h_{y}]-\mathbb{E}_{y}[h_{y}]\Big{|}\geq\frac{1}{4}a\Bigg{]}$
$\displaystyle\qquad+\mathbb{P}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Bigg{[}\sup_{\Omega(h_{y})\leq\frac{1}{L\sqrt{\lambda_{y}}}}\Big{|}\widehat{\mathbb{E}}_{0}^{\textup{\text{tr,II}}}[h_{y}]-\mathbb{E}_{0}[h_{y}]\Big{|}\geq\frac{1}{4}a\Bigg{]}.$

Note that Lemma (3.2) only applies to $\widehat{s}_{\gamma^{\ast},y}$, but we
are interested in $\widehat{s}_{\widehat{\gamma},y}$. Our reason for
presenting Lemma (3.2) is the same as our reason for presenting Lemma (3.1)
instead of Lemma (6.10) from earlier: namely, the result for the estimation
error $\widehat{s}_{\widehat{\gamma},y}-s_{\gamma^{\ast},y}$ is nearly
identical to the result for the estimation error
$\widehat{s}_{\gamma^{\ast},y}-s_{\gamma^{\ast},y}$, but the statement for the
latter is far more complicated than the former, and so it is saved for the
Appendix in Lemma (6.11).

Overall, Lemma (3.2) shows that the quality of
$\widehat{s}_{\widehat{\gamma},y}$ as an estimate of the score function
depends on the same factors as $T_{y}$: the amount of training samples and the
complexity of the space $\mathcal{H}_{y}$. Provided that these quantities grow
at appropriate rates, we can expect that the true score function can be
learned. Most importantly, this convergence result opens the floodgates for
the results previously described in the Methodology section to be used, which
had assumed that SELSE had access to the true score function. In particular,
we can now rigorously show that the first order term of SELSE’s total error is
$\mathcal{I}(\gamma^{\ast})^{-1}\big{(}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[s_{\gamma^{\ast}}]-\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[s_{\gamma^{\ast}}]\big{)}$,
which is the error incurred when
$\widehat{s}_{\widehat{\gamma}}=s_{\gamma^{\ast}}$ and is due to using
$\mathcal{D}^{\textup{\text{I}}}$ to approximate the population moments in
equation (5). In fact, we were able to fully characterize this first order
term up to its asymptotic distribution, as seen in the following lemma.

######  Lemma 3.3 (First Order Term).

Under Assumptions (A4), (A5), and (A6) in the Appendix, we have that

$\Bigg{(}\textup{\text{Var}}_{\mathcal{D}^{\textup{\text{I}}}}\Big{[}\mathcal{I}(\gamma^{\ast})^{-1}\big{(}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[s_{\gamma^{\ast}}]-\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[s_{\gamma^{\ast}}]\big{)}\Big{]}\Bigg{)}^{-\frac{1}{2}}\mathcal{I}(\gamma^{\ast})^{-1}\big{(}\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{te,I}}}[s_{\gamma^{\ast}}]-\widehat{\mathbb{E}}_{\pi^{\ast}}^{\textup{\text{tr,I}}}[s_{\gamma^{\ast}}]\big{)}\xrightarrow{\enskip
d\enskip}\mathcal{N}(0,I_{m}).$

The proof for Lemma (3.3) is in the Appendix and makes use of standard
triangular array central limit theorems. The following theorem expands on
Lemma (3.3), providing both a closed form for the variance of SELSE’s first
order error term and a rate-exact characterization of its second order error
term.

######  Theorem 3.4 (Normalized Error of $\widehat{\pi}$).

Under Assumptions (A1), (• ‣ A2), (A3), (A4), (A5), (A6) and (A7) in the
Appendix, we have that

$\displaystyle\Bigg{(}\Bigg{[}\frac{1}{n^{\textup{\text{te}}}}+\frac{1}{n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\Bigg{]}\Big{(}\mathcal{I}(\gamma^{\ast})^{-1}-\mathcal{I}(\gamma^{\ast};\textup{Cat})^{-1}\Big{)}+\frac{1}{n^{\textup{\text{te}}}}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}\Bigg{)}^{-\frac{1}{2}}(\widehat{\pi}-\pi^{\ast})$
$\displaystyle=Z+\epsilon,$

where

$\displaystyle Z$
$\displaystyle=\Bigg{(}\Bigg{[}\frac{1}{n^{\textup{\text{te}}}}+\frac{1}{n^{\textup{\text{tr}}}}\sum_{y=0}^{m}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}\Bigg{]}\Big{(}\mathcal{I}(\gamma^{\ast})^{-1}-\mathcal{I}(\gamma^{\ast};\textup{Cat})^{-1}\Big{)}+\frac{1}{n^{\textup{\text{te}}}}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}\Bigg{)}^{-\frac{1}{2}}\frac{1}{n}\sum_{i=1}^{n}\psi_{i}^{\textup{eff}}$
$\displaystyle\xrightarrow{\enskip d\enskip}\mathcal{N}(0,I_{m})$

where $n=n^{\textup{\text{tr}}}+n^{\textup{\text{te}}}$,
$\psi_{i}^{\textup{eff}}\in\mathbb{R}^{m}$ is a function of the
${i}^{\text{th}}$ data point and is defined in Lemma (6.8) in the Appendix,
and $\epsilon\in\mathbb{R}^{m}$ is a random vector satisfying

$\displaystyle||\epsilon||_{2}$
$\displaystyle=O_{\mathbb{P}}\Bigg{(}\sqrt{\frac{1}{\sqrt{n^{\textup{\text{tr}}}}}+\max_{y}\lambda_{y}\Omega(s_{\gamma^{\ast},y})^{2}+\frac{1}{\sqrt{\min_{y}\lambda_{y}}}e^{-Cn^{\textup{\text{tr}}}}}\Bigg{)}$
$\displaystyle\qquad+O_{\mathbb{P}}\Bigg{(}\sqrt{\max_{y}\mathbb{E}_{\mathcal{D}^{\textup{\text{tr,II}}}}\Big{[}\mathcal{U}_{y}(\lambda_{y})\Big{]}+\sqrt{\mathbb{E}_{\mathcal{D}^{\textup{\text{II}}}}\Big{[}||\widehat{\gamma}-\gamma^{\ast}||_{2}^{2}\Big{]}}}\Bigg{)}$
$\displaystyle\qquad+O_{\mathbb{P}}\Bigg{(}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{1}{\sqrt{1/n^{\textup{\text{te}}}+1/n^{\textup{\text{tr}}}}}}\bigg{\\{}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}e^{-C(\min_{y}\lambda_{y})^{2}n^{\textup{\text{tr}}}}}+\mathbb{P}_{\mathcal{D}^{\textup{\text{II}}}}\Big{[}\big{|}\big{|}\widehat{\gamma}-\gamma^{\ast}\big{|}\big{|}_{2}\geq
C\Big{]}\bigg{\\}}\Bigg{)},$

for some global constant $C>0$.

Whereas the first order error was due to the method of moments approximation
of equation (5), Theorem (3.4) makes clear that the second order error
$\epsilon$ depends on how fast
$\textup{\text{Var}}_{\gamma^{\ast}}[\widehat{s}_{\gamma^{\ast},y}-s_{\gamma^{\ast},y}]$
goes to $0$, as seen by how the rates for both $\epsilon$ and
$\textup{\text{Var}}_{\gamma^{\ast}}[\widehat{s}_{\gamma^{\ast},y}-s_{\gamma^{\ast},y}]$
depend on the same factors used to bound $T_{y}$, i.e.,
$n^{\textup{\text{tr}}}$ and the complexity of $\mathcal{H}_{y}$. Provided
that $n^{\textup{\text{tr}}}$ grows sufficiently fast relative to this
complexity, Theorem (3.4) implies that $\epsilon=o_{\mathbb{P}}(1)$, in which
case asymptotically, the normalized error is fully characterized by the
aforementioned first order term. Furthermore, it is important to note that,
unlike the other lemmas previously presented in this subsection, Theorem (3.4)
applies to the complete SELSE algorithm, in that it accounts for the fact that
$\gamma^{\ast}$ must be estimated via $\widehat{\gamma}$. Theorem (3.4) is
also able to remove the factor of $2$ that appeared when we first stated
SELSE’s asymptotic variance in subsection (2.5) as a result of Step 1’s sample
splitting. This was achievable because of Step 5, which takes $\widehat{\pi}$
to be the average of $\widehat{\pi}^{(a)}$ and $\widehat{\pi}^{(b)}$.
Ultimately, Theorem (3.4) paints a comprehensive picture of SELSE’s asymptotic
behavior, and in doing so, it provides a much needed theoretical backbone to
support the arguments made in the Methodology section.

###  3.2 Motivation for Semiparametric Statistics

Having established SELSE’s asymptotic behavior in the traditional
quantification setting, our next goal is to show that SELSE is semiparametric
efficient. However, before we can do that, we first must answer two
fundamental questions: what even is semiparametric statistics, and why are we
using it in the first place? This subsection serves to address precisely those
questions, and in doing so, will provide motivation for the work we do later
on.

In virtually all data analysis settings, it is often desirable to make the
weakest possible assumptions about the data at hand– that is, rather than
“speaking” for the data, we would like the dataset to speak for itself. From a
statistician’s point of view, this often translates to restricting oneself to
a nonparametric model for the data generating mechanism. However, there are
also times when one has prior knowledge about certain parts of the underlying
mechanism, and incorporating that knowledge would help to improve both the
quality and accuracy of the statistical models we fit.

A simple way of incorporating such knowledge is to allow certain components of
the model to be parametric, rather than nonparametric. Typically, the
nonparametric components reflect those aspects of the data generating
mechanism that we cannot confidently make assumptions about, and so we must
model them flexibly; in contrast, the parametric components reflect those
aspects which we feel comfortable making strong assumptions about, and so we
can model them rigidly. This is directly applicable to quantification tasks.
In quantification tasks, the problem definition assumes that the hidden label
of a test sample follows the $\textup{Cat}(\pi^{\ast})$ distribution for some
$\pi^{\ast}$ in the $m+1$ dimensional probability simplex, which is a
parametric model. However, we do not know anything about the conditional
density of the covariate given the label, except of course that they are
unchanged between train and test by virtue of the label shift assumption; as
such, those component densities are modeled nonparametrically.

Semiparametric statistics studies precisely these situations. In the language
of that field, $\pi^{\ast}$ is the finite-dimensional parameter of interest,
and $\mathbf{p}$ is the infinite-dimensional nuisance parameter. The goal is
to learn the parameter of interest in an effective fashion. Since the nuisance
parameter is generally hard to estimate because it is infinite-dimensional,
this goal typically translates to learning the parameter of interest in a
fashion that requires us to learn the least about the nuisance parameter. In
other words: how can we learn $\pi^{\ast}$, given that we don’t care about
learning $\mathbf{p}$?

The question stated above articulates both the attitude and objective of the
quantification field, and it is for this reason that we believe using a
semiparametric framework is appropriate. Moreover, for our own goals, this
framework is also actively desirable: as discussed previously, we would like
to prove that SELSE has the smallest possible asymptotic variance. So far, we
have only been able to establish SELSE’s optimality among ACC/PACC
quantifiers, but ideally, we would like to universalize this result to
quantifiers in general. Fortunately, the semiparametric literature is equipped
with the tools to do exactly that. For an excellent and mathematically
rigorous presentation of those tools, we refer the interested reader to the
seminal book by Bickel et al., [1993]; for a simplified and more user-friendly
version of those same tools, we point the reader to the paper by Newey,
[1990].

###  3.3 Derivation Roadmap

Despite the aforementioned appeal of the semiparametric framework, one
limitation of that literature is that its most important results tend to be
isolated to regimes where the data is generated IID from a single population.
This deviates from the traditional quantification setting which we had
presented in the Methodology section, where due to label shift, the train and
test sets are generated from two different populations. As we developed our
research, this put us in an especially awkward position: we saw that analyzing
the asymptotic behavior of SELSE was conceptually easier to do in the
traditional quantification setting, yet to show that our variance was the
smallest among a large class of quantifiers, it seemed like the best approach
was to use the single population setting that was ubiquitous in the
semiparametric literature.

Faced with this conflict, we decided to make the best of both worlds. On a
high level, our approach was as follows. First, we established the asymptotic
properties of SELSE in the traditional quantification setting, which included
identifying SELSE’s asymptotic variance matrix. In the Appendix, this setting
is referred to as the “Fixed Sequence Regime”. The results of those efforts
have already been presented in subsection (3.1). Second, we also separately
considered a modified version of the traditional quantification setting,
wherein all samples are generated IID from a single density, and a random
indicator $D\in\\{0,1\\}$ determines whether a sample belongs to test or
train; i.e., $D_{i}$ decides whether the ${i}^{\text{th}}$ sample is drawn
from $p_{\pi^{\ast}}$ or $p_{X,Y}^{\textup{\text{tr}}}$. This setting is
referred to as the “Fixed $\tau$-IID Regime” in the Appendix, because it is
assumes that $D\sim\text{Bern}(\tau)$ for some fixed $\tau\in(0,1)$.
Crucially, notice that the Fixed $\tau$-IID Regime preserves the essence of
the quantification problem: we receive labeled train and unlabeled test
samples, with the sole distributional discrepancy still being due to label
shift. The only difference is that now the number of train and test samples is
also random. In this regime, our goal was to derive a preliminary version of
the semiparametric efficiency bound– the bound was “preliminary” because it
could only apply to settings where $\tau$ was fixed. This was inadequate for
us, because we also wanted it to cover settings where the train set size grows
far faster than the test set size (or vice versa), which requires $\tau\to 0$
(or $\tau\to 1$) as $n\to\infty$. However, we made the strategic choice to
obtain the semiparametric efficiency bound for this simplified setting first,
as it made achieving the desired, more flexible bound far easier.

This is where the “$\tau_{n}$-IID Regime” comes in. This third regime is
nearly identical to the Fixed $\tau$-Regime, differing only in that $\tau$ is
replaced with $\tau_{n}$, which may change with $n$. In this regime, we had
three goals. First, using the results from the Fixed Sequence Regime as our
stepping stone, we translated the asymptotic properties of SELSE to the
$\tau_{n}$-IID Regime. Second, we generalized the semiparametric efficiency
bound in the Fixed $\tau$-Regime to accomodate the fact that $\tau_{n}$
changes with $n$. Third, combining the results from our first and second
goals, we showed that SELSE’s asymptotic variance matrix was equal to the
aforementioned semiparametric efficiency bound. Ultimately, by using the three
regimes in this way, we were able to show that SELSE is semiparametric
efficient.

###  3.4 Data Generation

We now formally introduce the mechanism used in the $\tau_{n}$-IID Regime. As
alluded to in subsection (3.3), the modification is conceptually
straightforward: rather than observing $n^{\textup{\text{te}}}$ IID test
samples from $p_{\pi^{\ast}}$ and $n^{\textup{\text{tr}}}$ IID train samples
from $p_{X,Y}^{\textup{\text{tr}}}$, we now obtain $n\geq 1$ IID copies of a
random vector $Z=(X,Y,D)$, which is generated as follows:

  * •

$D\sim\text{Bern}(\tau_{n})$

  * •

If $D=0$, then $(X,Y)\sim p_{X,Y}^{\textup{\text{tr}}}$

  * •

If $D=1$, then $X\sim p_{\pi^{\ast}}$ and $Y=-1$.

If $D=0$, then $(X,Y)$ is a labeled training sample, and if $D=1$, then $X$ is
an unlabeled test sample (hence the dummy value of $Y=-1$). The probability of
generating a test sample from this process is $\tau_{n}\in(0,1)$, which may
depend on $n$. For simplicity, we assume that both $\tau_{n}$ and
$\pi^{\textup{\text{tr}}}$ are known. Based on the process displayed above,
the density function for the distribution of $Z$ is given by

$\displaystyle\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}(z)$
$\displaystyle:=\big{(}\tau_{n}p_{\pi^{\ast}}(x)\big{)}^{d}\big{(}(1-\tau_{n})p_{X,Y}^{\textup{\text{tr}}}(x,y)\big{)}^{1-d}\
\mathbbold{1}{\big{\\{}x\in\mathcal{X},\text{ }y\in\mathcal{Y},\text{
}d\in\\{0,1\\}\big{\\}}}$
$\displaystyle=\big{(}\tau_{n}p_{\pi^{\ast}}(x)\big{)}^{d}\Bigg{(}(1-\tau_{n})\prod_{j=0}^{m}\big{(}\pi_{j}^{\textup{\text{tr}}}p_{j}(x)\big{)}^{\mathbbold{1}{\\{y=j\\}}}\Bigg{)}^{1-d}\mathbbold{1}{\big{\\{}x\in\mathcal{X},\text{
}y\in\mathcal{Y},\text{ }d\in\\{0,1\\}\big{\\}}}.$ (20)

The final dataset is then
$Z_{1},\dots,Z_{n}\overset{\text{iid}}{\sim}\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}$,
with the number of test and train samples given by
$N^{\textup{\text{te}}}:=\sum_{i=1}^{n}D_{i}$ and
$N^{\textup{\text{tr}}}:=n-N^{\textup{\text{te}}}$, respectively. Although
$N^{\textup{\text{te}}}$ and $N^{\textup{\text{tr}}}$ are now random, recall
that the benefit of working with this data generation mechanism is that all
data points are from a single population (i.e., $n$ IID samples from a single
density), which is studied by the semiparametric literature far more often
than settings where there are multiple sets of samples from different
populations (i.e., $n^{\textup{\text{te}}}$ test samples and
$n^{\textup{\text{tr}}}$ train samples). This regime therefore enables us to
make the most out of existing results in the semiparametric literature when
proving our efficiency bound.

###  3.5 Model Specification

Having described the new data generating mechanism, we now present several
modeling assumptions. We assume that
$\pi^{\ast},\pi^{\textup{\text{tr}}}\in\Delta$, where $\Delta$ is a subset of
the $m+1$ dimensional probability simplex. We also assume that
$\mathbf{p}\in\mathcal{Q}$, where
$\mathcal{Q}:=\mathcal{Q}_{0}\times\dots\times\mathcal{Q}_{m}$ and each
$\mathcal{Q}_{y}$ is a set of densities. The full parameter space is
$\Theta^{\text{semi}}=\Delta\times\mathcal{Q}$, and our semiparametric model
is

$\textbf{M}^{\text{semi},\tau_{n}}:=\big{\\{}\mathcal{J}^{\pi,\mathbf{q},\tau_{n}}\
\big{\lvert}\ (\pi,\mathbf{q})\in\Theta^{\text{semi}}\big{\\}},$

where for each parameter $(\pi,\mathbf{q})\in\Theta^{\text{semi}}$,
$\mathcal{J}^{\pi,\mathbf{q},\tau_{n}}$ is a density function for the random
vector $Z$ described in the previous subsection, except with $\mathbf{q}$
replacing $\mathbf{p}$ and $\pi$ replacing $\pi^{\ast}$ in equation (20).

####  3.5.1 Assumptions on $\pi^{\ast}$ and $\pi^{\textup{\text{tr}}}$

We make several restrictions on both $\Delta$ and $\mathcal{Q}$. For $\Delta$,
we assume that there exists a constant $\xi\in(0,\tfrac{1}{2})$ such that

$\Delta:=\Bigg{\\{}(\pi_{1},\dots,\pi_{m})\in\mathbb{R}^{m}\ \Bigg{\lvert}\
\pi_{0}=1-\sum_{y=1}^{m}\pi_{y},\quad\xi<\pi_{y}<1-\xi\quad\forall
y\in\mathcal{Y}\Bigg{\\}}.$

Since $\pi^{\ast},\pi^{\textup{\text{tr}}}\in\Delta$, this form for $\Delta$
ensures that each class is sufficiently represented in both the train and test
sets. For the test set, this is not strictly necessary, but it is reasonable
if one chooses $\xi$ to be extremely small, and the assumption is convenient
for our proofs. However, this type of assumption is necessary for the training
set: clearly, learning about the mixing parameter used in $p_{\pi^{\ast}}$ is
only possible if we have some knowledge about each of the component densities
involved in the mixture. Requiring that
$\pi_{y}^{\textup{\text{tr}}}\in\Delta$ guarantees this, because it ensures
that the average amount of training samples from each component density is
greater than $n\xi$.

####  3.5.2 Assumptions on $\mathbf{p}$

Next, we state assumptions about $\mathcal{Q}$. Towards that end, define:

$L:=\frac{1}{1+m\big{(}\frac{1-\xi}{\xi}\big{)}^{3}}\qquad
U:=\max\Bigg{(}1-\xi,\
\frac{1}{1+m\big{(}\frac{\xi}{1-\xi}\big{)}^{3}}\Bigg{)}$
$\Gamma:=\Bigg{\\{}(\gamma_{1},\dots,\gamma_{m})\in\mathbb{R}^{m}\
\Bigg{\lvert}\ \gamma_{0}=1-\sum_{y=1}^{m}\gamma_{y},\quad L\leq\gamma_{y}\leq
U\quad\forall y\in\mathcal{Y}\Bigg{\\}}.$

We assume that there exists constants $\nu,\Lambda,B>0$ such that the
following conditions hold for all $\mathbf{q}\in\mathcal{Q}$ and
$\gamma\in\Gamma$:

  1. B1.

$\sigma_{\textup{min}}\big{(}\mathcal{I}(\gamma)\big{)}>\sqrt{\Lambda}$.

  2. B2.

$\sigma_{\textup{min}}\big{(}\mathcal{I}(\gamma;\textup{Cat})-\mathcal{I}(\gamma)\big{)}>\nu$.

  3. B3.

$(q_{0}e^{\rho^{\prime}\zeta_{0}s_{\gamma}-c_{0}(\rho)},\dots,q_{m}e^{\rho^{\prime}\zeta_{m}s_{\gamma}-c_{m}(\rho)})\in\mathcal{Q}$
for all $\rho\in\mathbb{R}^{m}$ satisfying $||\rho||_{2}<B$ and scalars
$\zeta_{j}$ satisfying $0\leq\zeta_{j}<\frac{1-\xi}{\xi}$.

Assumptions (B1) and (B2) place bounds on the information that a test sample
can contain about $\pi^{\ast}$. Here’s how. On the one hand, Assumption (B1)
ensures that no two component densities are the same: if it were the case that
$\sigma_{\textup{min}}\big{(}\mathcal{I}(\gamma)\big{)}=0$ for any
$\gamma\in\Gamma$, then it is easy to show that there would exist at least two
component densities which are equal to each other with probability 1, and
$\pi^{\ast}$ would be unidentifiable. A simple example of this
unidentifiability comes from the binary class case: if $p_{0}=p_{1}$, then
$p_{\beta}$ would be the same for all $\beta\in(0,1)$, in which case it is
impossible to learn $\pi^{\ast}$ from the test data. That is, even though
$X\sim p_{\pi^{\ast}}$, $X$ contains zero information about $\pi^{\ast}$.

On the other hand, Assumption (B2) ensures that the component densities’
supports are not all disjoint. This insight comes from the following lemma:

######  Lemma 3.5 (Relationship between $\mathcal{I}(\beta)$ and
$\mathcal{I}(\beta;\textup{Cat})$).

Let $\beta$ be a vector in the $m+1$ dimensional probability simplex, and
suppose that the entries in $\beta$ are bounded away from $0$ and $1$. Then,
we have that

$\mathcal{I}(\beta)\preceq\mathcal{I}(\beta;\textup{Cat}),$

where equality is achieved if and only if the supports of the class
distributions are all disjoint, i.e.,

$\mathcal{I}(\beta;\textup{Cat})=\mathcal{I}(\beta)\iff\mathbb{P}_{y}\Bigg{[}\sum_{j=0\neq
y}^{m}p_{j}(X)=0\Bigg{]}=1\qquad\forall y\in\mathcal{Y}.$

Lemma (3.5) implies that equality between $\mathcal{I}(\gamma;\textup{Cat})$
and $\mathcal{I}(\gamma)$ happens if and only if all the component densities’
supports are disjoint; since Assumption (B2) prevents this equality, it
follows that (B2) ensures that the component densities have at least some
overlap.

Actually, overlapping component densities is not a necessary requirement for
establishing the performance of SELSE; indeed, the more separated the
densities are, the better quantifiers tend to perform. This can be easily seen
for SELSE by examining its asymptotic variance, as presented in Theorem (3.9).
However, it is necessary if we want the efficiency bound to be achievable. To
see why, suppose that the supports were all disjoint. Then, every
$x\in\mathcal{X}$ corresponds to a single class $y\in\mathcal{Y}$, i.e.,
$\varrho(x)=y$ for some deterministic function $\varrho$. It is easy to show
that $\varrho$ is a sufficient statistic for $\pi^{\ast}$, implying that the
information that each test sample $X$ contains about $\pi^{\ast}$ equals the
information that the missing test label $Y$ contains about $\pi^{\ast}$ (hence
the equality of Fisher Informations in Lemma (3.5)). The fact that these
information contents are equal despite us having only imperfect knowledge
about $\varrho$ via the training data is problematic: it implies that, in
order for a quantifier to be “efficient”, its first-order error must be just
as small as what is possible when $\varrho$ is known perfectly! Of course,
this requirement can be satisfied if the number of training samples grows far
faster than the number of test samples (i.e., $\tau_{n}\to 0$ sufficiently
quickly), because then the error incurred for having to learn $\varrho$ will
not be part of the first order error. However, rather than place restrictions
on the relationship between the train and test sample sizes, we prefer to
simply assume (B2), since in most interesting problems, the supports of the
component densities are not all disjoint.

Finally, to understand Assumption (B3), it is helpful to first clarify ideas
on what is meant by an “efficiency bound” in semiparametric statistics.
Towards that end, suppose that $\mathcal{M}^{\text{sub},\tau_{n}}$ was such
that
$\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}\in\mathcal{M}^{\text{sub},\tau_{n}}\subseteq\mathcal{M}^{\text{semi},\tau_{n}}$.
Intuitively, the task of learning $\pi^{\ast}$ (without necessarily learning
$\mathbf{p}$) when the assumed model is $\mathcal{M}^{\text{sub},\tau_{n}}$
cannot be harder than when the assumed model is
$\mathcal{M}^{\text{semi},\tau_{n}}$, and this holds true for the special case
of when the density vector $\mathbf{q}$ involved in defining each
$\mathcal{J}^{\pi,\mathbf{q},\tau_{n}}\in\mathcal{M}^{\text{sub},\tau_{n}}$
belongs to a smooth parametric family. Moreover, for any such smooth
parametric submodel, this estimation difficulty can be measured by the Cramer
Rao Lower Bound (CRLB). Thus, it is intuitive to consider the supremum of all
such CRLBs (one CRLB for each possible smooth parametric submodel of
$\mathcal{M}^{\text{semi},\tau_{n}}$) as the semiparametric efficiency bound
for learning $\pi^{\ast}$ when the assumed model is
$\mathcal{M}^{\text{semi},\tau_{n}}$.

Now ideally, we would want $\mathcal{Q}$ to be as large as possible, because
this corresponds to making fewer assumptions about $\mathbf{p}$. However,
making $\mathcal{Q}$ larger can only increase the semiparametric efficiency
bound, i.e., make it more difficult to learn $\pi^{\ast}$, because it would
expand the set of smooth parametric submodels that the aforementioned supremum
indexes over. This is precisely where Assumption (B3) comes in. Under this
assumption, it is possible to construct a parametric submodel with a CRLB that
is greater than or equal to the CRLB of any other possible parametric
submodel. In the semiparametric literature, this is often called the “least
favorable” submodel. This result is presented in Lemma (6.20), with the
specific submodel described in Lemma (6.17), both located in the Appendix
section. This result is significant, because it means that if Assumption (B3)
holds true, then $\mathcal{Q}$ can be assumed to be arbitrarily large, without
the extra expense of making it harder to learn $\pi^{\ast}$!

####  3.5.3 Assumptions on $s_{\gamma^{\ast}}$

In addition to Assumptions (B1), (B2) and (B3), we also place constraints on
the score function formed from $\mathbf{p}$. Such assumptions are necessary
because SELSE assumes that it is possible to learn $s_{\gamma^{\ast}}$.
However, before diving into those assumptions, it will be helpful to first
establish some new notation.

Let
$(\bar{n}^{\textup{\text{te}}},\bar{n}_{0}^{\textup{\text{tr}}},\dots,\bar{n}_{m}^{\textup{\text{tr}}})$
denote any sequence depending on $n$ such that
$\bar{n}^{\textup{\text{te}}}+\sum_{y=0}^{m}n_{y}^{\textup{\text{tr}}}=n$,
with each component approaching infinity. For each
$(\pi,\mathbf{q})\in\Theta^{\text{semi}}$, let
$\bar{\mathcal{D}}^{\textup{\text{tr,I}}}$ and
$\bar{\mathcal{D}}^{\textup{\text{tr,II}}}$ denote datasets each containing
$\tfrac{1}{2}\bar{n}_{y}^{\textup{\text{tr}}}$ IID samples from $q_{y}$ for
every $y\in\mathcal{Y}$, and let $\bar{\mathcal{D}}^{\textup{\text{te,I}}}$
and $\bar{\mathcal{D}}^{\textup{\text{te,II}}}$ denote datasets each
containing $\tfrac{1}{2}\bar{n}^{\textup{\text{te}}}$ IID samples from
$q_{\pi}$. Define
$\bar{\mathcal{D}}^{\textup{\text{I}}}:=(\bar{\mathcal{D}}^{\textup{\text{tr,I}}},\bar{\mathcal{D}}^{\textup{\text{te,I}}})$
and
$\bar{\mathcal{D}}^{\textup{\text{II}}}:=(\bar{\mathcal{D}}^{\textup{\text{tr,II}}},\bar{\mathcal{D}}^{\textup{\text{te,II}}})$.
These datasets are analogous to what was described in the Methodology Section.
Also define $\bar{\gamma}:=(\bar{\gamma}_{1},\dots,\bar{\gamma}_{m})$ where

$\bar{\gamma}_{y}:=\frac{\frac{\pi_{y}}{\bar{n}^{\textup{\text{te}}}}+\frac{(\pi_{y})^{2}}{\bar{n}_{y}^{\textup{\text{tr}}}}}{\frac{1}{\bar{n}^{\textup{\text{te}}}}+\sum_{k=0}^{m}\frac{(\pi_{k})^{2}}{\bar{n}_{k}^{\textup{\text{tr}}}}}\qquad\forall\
y\in\mathcal{Y},$ (21)

and define

$\mathcal{H}^{\text{pre}}:=\Bigg{\\{}s_{\gamma}\ \Bigg{\lvert}\
s_{\gamma}:=\frac{(q_{1}-q_{0},\dots,q_{m}-q_{0})^{\prime}}{\sum_{j=0}^{m}\gamma_{j}q_{j}},\quad(q_{0},\dots,q_{m})\in\mathcal{Q},\quad\gamma\in\Gamma\Bigg{\\}}.$

Finally, let $\mathcal{H}$ be any set for which
$\mathcal{H}^{\text{pre}}\subseteq\mathcal{H}$. We assume that:

  1. 4.

$\mathcal{H}$ is closed under scalar multiplication.

  2. 5.

For each $j\in[m]$, $\Omega:\mathcal{H}_{j}\mapsto[0,\infty)$ satisfies the
following properties for each $h_{j}\in\mathcal{H}_{j}$:

     * •

$\Omega(ch_{j})=|c|\Omega(h_{j})$ for all $c\in\mathbb{R}$

     * •

$\Omega(h_{j})\geq D||h_{j}||_{\infty}$ where $D>0$ is a global constant.

We also make the following assumptions about the complexity of $\mathcal{H}$:

  1. 6.

For each $j\in[m]$, $(\pi,\mathbf{q})\in\Theta^{\text{semi}}$ and sequence
$(\bar{n}^{\textup{\text{te}}},\bar{n}_{0}^{\textup{\text{tr}}},\dots,\bar{n}_{m}^{\textup{\text{tr}}})$,
we assume that there exists a corresponding sequence
$\lambda_{j}\in(0,\infty)$ which satisfies the following properties:

     * •

$\lambda_{j}\sup_{\gamma\in\Gamma}\Omega^{2}\Big{(}\frac{q_{j}-q_{0}}{q_{\gamma}}\Big{)}\to
0$

     * •

$\lambda_{j}^{2}\sum_{k=0}^{m}\bar{n}_{k}^{\textup{\text{tr}}}\to\infty$

     * •

$\mathbb{E}_{\bar{\mathcal{D}}^{\textup{\text{tr,II}}}}\Big{[}\bar{\mathcal{U}}_{j}(\lambda_{j})\Big{]}\to
0$, where

$\displaystyle\bar{\mathcal{U}}_{j}(\lambda_{j})$
$\displaystyle:=\sup\limits_{\Omega(h_{j})\leq\frac{1}{L\sqrt{\lambda_{j}}}}\Big{|}\widehat{\mathbb{E}}_{q_{0}}^{\textup{\text{tr,II}}}[h_{j}]-\mathbb{E}_{q_{0}}[h_{j}]\Big{|}+\sup\limits_{\Omega(h_{j})\leq\frac{1}{L\sqrt{\lambda_{j}}}}\Big{|}\widehat{\mathbb{E}}_{q_{j}}^{\textup{\text{tr,II}}}[h_{j}]-\mathbb{E}_{q_{j}}[h_{j}]\Big{|}$
$\displaystyle\qquad\qquad+\sup\limits_{\Omega(h_{j})\leq\frac{1}{L\sqrt{\lambda_{j}}}}\Big{|}\widehat{\textup{\text{Var}}}_{q_{\bar{\gamma}}}^{\textup{\text{tr,II}}}[h_{j}]-\textup{\text{Var}}_{q_{\bar{\gamma}}}[h_{j}]\Big{|}.$

$\mathcal{H}^{\text{pre}}$ is the set of all possible score functions that can
be created from density vectors $\mathbf{q}\in\mathcal{Q}$ (hence
$s_{\gamma^{\ast}}\in\mathcal{H}^{\text{pre}}$), so ideally, we would choose
$\widehat{s}_{\widehat{\gamma}}$ in Step 3 of SELSE by running the
optimization routine on $\mathcal{H}^{\text{pre}}$. However, since there is no
reason one should know $\mathcal{H}^{\text{pre}}$ ahead of time, we instead
run the optimization on a more conveniently known function space $\mathcal{H}$
that is a superset of $\mathcal{H}^{\text{pre}}$. Fortunately, many of the
common choices for spaces $\mathcal{H}$ and penalty terms $\Omega$ satisfy
Assumptions (4) and (5). For example, if $\mathcal{H}$ is a Sobolev Space or a
RKHS, and $\Omega$ the appropriate norm, then both multiplication properties
in (4) and (5) hold true. The condition involving the $L_{\infty}$ norm is
also satisfied in both cases; see Theorem 8.8 in Brezis, [2010] for when
$\mathcal{H}$ is a Sobolev space and see page 124 in Steinwart and Christmann,
[2008] for when $\mathcal{H}$ is a RKHS with a bounded reproducing kernel.

Even though $\mathcal{H}^{\text{pre}}$ is unknown, the hope is that this
superset property holds if $\mathcal{H}$ is chosen to be a sufficiently rich
and complex function class which is allowed to grow with $n$. Indeed, the
larger $\mathcal{H}$ is, the more likely the superset property is satisfied.
However, $\mathcal{H}$ also cannot be allowed to grow “too” fast: based on how
$\widehat{s}_{\widehat{\gamma},j}$ is constructed for each $j\in[m]$, the
quality of $\widehat{s}_{\widehat{\gamma},j}$ as an estimator of
$s_{\gamma^{\ast},j}$ hinges on the degree to which
$\mathbb{E}_{q_{0}}[h_{j}]$, $\mathbb{E}_{q_{j}}[h_{j}]$ and
$\textup{\text{Var}}_{q_{\bar{\gamma}}}[h_{j}]$ can be well approximated by
their empirical counterparts for each $h_{j}\in\mathcal{H}_{j}$. Indeed, if
$\mathcal{H}_{j}$ is too large relative to the sample size, then this
approximation may be poor for some $h_{j}$. This is an interesting form of
tension, and has been studied for decades within statistical learning theory
in the context of excess risk bounds for classification and regression tasks
[Vapnik,, 1999]. In line with that tradition, our algorithm addresses the
foregoing concern via regularization in Step 3, which effectively constrains
the optimization over each $\mathcal{H}_{j}$ to a ball in which
$\Omega(h_{j})$ is bounded. Assumption (6) requires that this ball’s radius
tends to infinity, but at a rate that is sufficiently slow, so as to ensure
that the first and second moments of those $h_{j}$ inside the ball can be
accurately learned.

Finally, even if $\mathcal{H}$ grows extremely slowly, the particular form of
the score functions in $\mathcal{H}^{\text{pre}}$ may actually be enough to
ensure that the superset property holds for small $n$. This is because each
member of $\mathcal{H}^{\text{pre}}$ only depends on the ratio between the
component densities, not the actual densities themselves. For example, when
$m=1$, it is easy to show that

$\frac{q_{1}(x)-q_{0}(x)}{q_{\gamma}(x)}=\frac{1}{\gamma+\frac{1}{q_{1}(x)/q_{0}(x)-1}}\qquad\forall
x\in\mathcal{X},$

meaning that the score is an elementary transformation of the density ratio
$q_{1}(x)/q_{0}(x)$, with a similar result holding for the more general $m\geq
1$ setting. Essentially, this means that even if SELSE is applied to
situations where the component densities are complicated, as long as their
density ratios are not too complex, then the corresponding score functions
will not be too complex either. Hence, in these situations, even if
$\mathcal{H}$ is not an expressive function class, it may be reasonable to
assume that $\mathcal{H}^{\text{pre}}\subset\mathcal{H}$. An example of one of
these situations is when the component densities belong to the same
exponential family with an elementary sufficient statistic function $T$, but a
complicated reference density. In this case, the reference density causes
$q_{0},q_{1}$ to be complicated functions, yet for some constant $c$, we have
that $q_{1}(x)/q_{0}(x)\propto e^{\langle c,T(x)\rangle}$, which is relatively
simple as it only depends on $T$.

####  3.5.4 Assumptions on $\widehat{\gamma}$

We also require that there exists an estimator $\widehat{\gamma}$ with the
following properties:

  1. 7.

For each $\mathbf{q}\in\mathcal{Q}$, $\pi\in\Delta$ and sequence
$(\bar{n}^{\textup{\text{te}}},\bar{n}_{0}^{\textup{\text{tr}}},\dots,\bar{n}_{m}^{\textup{\text{tr}}})$,
there exists an estimator $\widehat{\gamma}$ of $\bar{\gamma}$ such that:

     * •

$\widehat{\gamma}\in\Gamma$ for each $n$

     * •

$\mathbb{E}_{\bar{\mathcal{D}}^{\textup{\text{II}}}}\Big{[}||\widehat{\gamma}-\bar{\gamma}||_{2}^{2}\Big{]}\to
0$

     * •

For each $a>0$,
$\mathbb{P}_{\bar{\mathcal{D}}^{\textup{\text{II}}}}\big{[}||\widehat{\gamma}-\bar{\gamma}||_{2}\geq
a\big{]}=o\Big{(}\sqrt{\frac{1}{\bar{n}^{\textup{\text{te}}}}+\frac{1}{\sum_{k=0}^{m}\bar{n}_{k}^{\textup{\text{tr}}}}}\Big{)}$

These assumptions are easily satisfied when we have access to a preliminary
quantifier for $\pi^{\ast}$ which can be used with equation (21) to form a
plug-in estimate $\widehat{\gamma}$ of $\bar{\gamma}$, much like in our
original algorithm.

####  3.5.5 Assumptions on $\tau_{n}$

We also make the following assumptions about $\tau_{n}$:

  1. 8.

$\tau_{n}\in(0,1)$ for each $n$.

  2. 9.

$n\tau_{n}(1-\tau_{n})\to\infty$.

Assumption (8) ensures that the dataset contains both test and train samples
with high probability. Assumption (9) ensures that the expected number of test
and train samples goes to infinity, even if the expected proportion of the
data that is test or train goes to zero in the limit; that is, both
$n\tau_{n},n(1-\tau_{n})\to\infty$ even if $\tau_{n}\to 1$ or $\tau_{n}\to 0$.
These conditions enable us to consider many different sequences of $\tau_{n}$,
creating a flexible model for the relationship between the two sample sizes.
Examples of such sequences include:

  * •

$\tau_{n}=\frac{1}{n^{\alpha}}$ for some $\alpha\in(0,1)$

  * •

$\tau_{n}=1-\frac{1}{n^{\alpha}}$ for some $\alpha\in(0,1)$

  * •

$\tau_{n}=\frac{1}{2}$.

The first two choices for $\tau_{n}$ describe a relationship between the train
and test sample sizes, wherein one grows faster than the other. On the one
hand, when $\tau_{n}=\frac{1}{n^{\alpha}}$, it can be shown that
$\mathbb{E}\big{[}N^{\textup{\text{tr}}}\big{]}\asymp\mathbb{E}\big{[}N^{\textup{\text{te}}}\big{]}^{\frac{1}{1-\alpha}}$
where $\frac{1}{1-\alpha}\in(1,\infty)$, meaning that the average number of
train samples grows polynomially in the average number of test samples. As
such,
$\mathbb{E}[N^{\textup{\text{tr}}}]>>\mathbb{E}[N^{\textup{\text{te}}}]$. On
the other hand, when $\tau_{n}=1-\frac{1}{n^{\alpha}}$, then
$\mathbb{E}\big{[}N^{\textup{\text{te}}}\big{]}\asymp\mathbb{E}\big{[}N^{\textup{\text{tr}}}\big{]}^{\frac{1}{1-\alpha}}$,
i.e., the average number of test samples grows polynomially in the average
number of train samples. As such,
$\mathbb{E}[N^{\textup{\text{te}}}]>>\mathbb{E}[N^{\textup{\text{tr}}}]$.
Later in this section, we will interpret the semiparametric efficiency bound
in situations where $\tau_{n}\to 0$ and $\tau_{n}\to 1$, and show how in each
setting, the task of quantification reduces to other statistical estimation
problems. The simple case of when $\tau_{n}$ equals or converges to a constant
in $(0,1)$ can then be thought of as an intermediate “blend” of those two
extremes.

###  3.6 Family of Quantifiers

Next, we describe a large family of quantifiers $\mathcal{E}$ whose asymptotic
variance matrix is lower bounded by our semiparametric efficiency bound, which
will be presented in the subsequent subsection. This family is extremely
large, containing not only SELSE and ACC/PACC quantifiers, but also other
popular competitors such as HDy, EMQ and MLLS. We say that a quantifier
$\widetilde{\pi}_{n}$ is contained in $\mathcal{E}$ if $\widetilde{\pi}_{n}$
satisfies the following criteria:

  1. C1.

For each fixed $\tau\in(0,1)$, $\widetilde{\pi}_{n}$ is regular with respect
to $\mathcal{M}^{\text{semi},\tau}$ and asymptotically linear with influence
function $\psi_{\tau}$ and second order error $\delta_{\tau}$.

  2. C2.

If $\tau_{n}$ is a sequence satisfying Assumptions (8) and (9), then:

    1. (a)

$\mathbb{P}_{Z_{1:n}\overset{\text{iid}}{\sim}\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}\big{|}\delta_{\tau_{n}}(Z_{1:n})\big{|}\geq
c\Big{]}\to 0$ for all $c>0$.

    2. (b)

$\frac{(1-\tau_{n})^{2}}{\tau_{n}n}\mathbb{E}_{\pi^{\ast}}\Big{[}||\tau_{n}\psi_{\tau_{n}}(X,-1,1)||_{2}^{4}\Big{]}+\frac{\tau_{n}^{2}}{(1-\tau_{n})n}\sum\limits_{y=0}^{m}\pi_{y}^{\textup{\text{tr}}}\mathbb{E}_{y}\Big{[}||(1-\tau_{n})\psi_{\tau_{n}}(X,y,0)||_{2}^{4}\Big{]}\to
0$.

Regularity and asymptotic linearity are important concepts in semiparametric
statistics. Intuitively, a regular estimator is one that is not systematically
biased towards certain values of the estimand. For example, quantifiers that
are set equal to or shrunk towards a specific estimand value, or are
superefficient for particular values (cf. Hodge’s estimator) are all non-
regular. The idea is that, by having an a priori preference towards certain
estimand values, these quantifiers are making use of information contained
outside of the semiparametric model, and thus should be excluded from
consideration [Newey,, 1990]. Further, a quantifier that is asymptotically
linear with influence function $\psi_{\tau}$ and second order error
$\delta_{\tau}$ is one whose normalized estimation error can be written as

$\sqrt{n}(\widetilde{\pi}_{n}-\pi^{\ast})=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\psi_{\tau}(Z_{i})+\delta_{\tau}(Z_{1:n}),$

where $\psi_{\tau},\delta_{\tau}$ are $\mathbb{R}^{m}$-valued functions,
$\psi_{\tau}(Z_{i})$ is mean zero with a finite and nonsingular covariance
matrix, and $\delta_{\tau}(Z_{1:n})\xrightarrow{\enskip p\enskip}0$.
Quantifiers of this form are unbiased to the first order, and more
specifically, have an asymptotic error distribution of
$\mathcal{N}\big{(}0,\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau}}[\psi_{\tau}]\big{)}$.
This leads to a natural way of comparing asymptotically linear quantifiers: if
$\psi_{\tau,1}$ and $\psi_{\tau,2}$ are influence functions for two different
quantifiers and
$\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau}}[\psi_{\tau,1}]\preceq\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau}}[\psi_{\tau,2}]$,
then the quantifier with $\psi_{\tau,1}$ as its influence function is more
desirable, since its first order error is stochastically smaller.
Traditionally, the influence function with the smallest variance matrix is
called the efficient influence function. The variance matrix of the efficient
influence function is called the semiparametric efficiency bound, and a
quantifier which is asymptotically linear in the efficient influence function
is called semiparametric efficient, because its first order variance achieves
the semiparametric efficiency bound. For a rigorous treatment of regularity
and asymptotic linearity, we refer the reader to Newey, [1990] and Bickel et
al., [1993].

While condition (C1) places requirements on the asymptotic behavior of
quantifiers for fixed $\tau\in(0,1)$, we would also like to analyze this
behavior in settings where one of the train or test sample sizes grows far
faster than the other, i.e., when $\tau_{n}$ approaches either $0$ or $1$.
Since the influence function and the second order error may vary for different
$\tau$, analyzing the foregoing behavior requires placing restrictions on
$\\{(\psi_{\tau},\delta_{\tau})\mid\tau\in(0,1)\\}$. This is where conditions
(C2a) and (C2b) come in. By requiring that
$\big{|}\delta_{\tau_{n}}(Z_{1:n})\big{|}\xrightarrow{\enskip p\enskip}0$ even
as $\tau_{n}$ changes, condition (C2a) ensures that the asymptotic variance of
$\widehat{\pi}_{n}$ is completely determined by $\psi_{\tau_{n}}$. On top of
that, condition (C2b) is a simple moment condition that controls the size of
the influence function. It is also easy to satisfy: for example, the condition
holds whenever the norm of the influence function is uniformly bounded.

###  3.7 Intermediate Results

Having fully described our semiparametric model and the assumptions we make
about its parameter space, we now walk through some of the intermediate
results that were key to establishing SELSE’s semiparametric efficiency.
Towards that end, we start by taking a deeper dive into the concept of a
semiparametric efficiency bound, which we had introduced in subsection
(3.5.2). This will be done first for the Fixed $\tau$-IID Regime, and
generalized later on to the $\tau_{n}$-IID Regime.

####  3.7.1 Fixed $\tau$-IID Regime

As mentioned previously, an intuitive way to think about a semiparametric
efficiency bound is that it is the largest possible CRLB for a smooth
parametric submodel, i.e., it is the CRLB for the least favorable parametric
submodel. However, for any given smooth parametric submodel, what exactly is
the form of the CRLB? Answering this question will be quite helpful for our
purposes, so we turn to that now.

Recall that a parametric submodel differs from a semiparametric model in that
the infinite dimensional nuisance parameter in the semiparametric model is now
parameterized by a finite dimensional vector. That is, in the context of the
Fixed $\tau$-IID Regime, a parametric submodel
$\mathcal{M}^{\text{sub},\tau}\subset\mathcal{M}^{\text{semi},\tau}$ assumes
that $\mathbf{p}$ belongs to a parametric family. Accordingly, each density
vector $\mathbf{q}$ in this family can be parameterized by some
$\rho\in\mathcal{R}$, where $\mathcal{R}$ is some open set of finite
dimensional vectors. The full parameter space for general $(\pi,\rho)$ is then
$\Delta\times\mathcal{R}$, and the submodel is given by
$\mathcal{M}^{\text{sub},\tau}=\\{\mathcal{J}^{\pi,\rho,\tau}\mid(\pi,\rho)\in\Delta\times\mathcal{R}\\}$.
For example, if the covariates were all one dimensional and we were confident
that the component densities were gaussian pdfs with unit variance, then
$\mathcal{R}=\mathbb{R}^{m+1}$ and each $\rho\in\mathcal{R}$ corresponds to a
different vector of $m+1$ means, with one mean for each of the $m+1$ classes.

Now, the fact that the parameter space is finite dimensional for
$\mathcal{M}^{\text{sub},\tau}$ means that the score function for the joint
vector $(\pi,\rho)$ is easy to compute: it is simply
$S_{\pi,\rho}(z):=(S_{\pi}(z),S_{\rho}(z))$, where

$\displaystyle S_{\pi}(z)$
$\displaystyle:=\frac{\delta}{\delta{\pi}}\log\mathcal{J}^{\pi,\rho^{\ast},\tau}(z)$
$\displaystyle=ds_{\pi}(x)$ (22)

and

$S_{\rho}(z):=\frac{\delta}{\delta{\rho}}\log\mathcal{J}^{\pi^{\ast},\rho,\tau}(z),$

where $\rho^{\ast}$ is the parameter vector that the parametric submodel
identifies with $\mathbf{p}$. Note that our use of the word “score” here is in
line with the semiparametric literature, but it should not be confused with
the score function $s_{\pi}(x)$ that we have typically referred to throughout
this thesis, although they are related by line (22). $S_{\pi}$ is the score
function for the parameter of interest, and $S_{\rho}$ is the score function
for the nuisance parameter (aka the nuisance score function). Intuitively,
$S_{\pi}$ captures the sensitivity of the density
$\mathcal{J}^{\pi,\rho^{\ast},\tau}$ to changes in $\pi$, or equivalently, the
degree of dependence of $\mathcal{J}^{\pi,\rho^{\ast},\tau}$ on $\pi$, when
the component densities are fixed at the truth $\mathbf{p}$. Likewise,
$S_{\rho}$ captures the degree of dependence of
$\mathcal{J}^{\pi^{\ast},\rho,\tau}$ on $\rho$, when the parameter of interest
is fixed at the truth $\pi^{\ast}$. This perspective encourages an interesting
interpretation of the magnitude for both types of score functions. On the one
hand, one can think of the magnitude of $S_{\pi^{\ast}}(Z)$ as a measure of
the amount of information contained in a random variable
$Z\sim\mathcal{J}^{\pi^{\ast},\rho^{\ast},\tau}$ about $\pi^{\ast}$ when
$\rho^{\ast}$ is already known. On the other hand, one can think of the
magnitude of $S_{\rho^{\ast}}(Z)$ as a measure of the amount of information
contained in $Z\sim\mathcal{J}^{\pi^{\ast},\rho^{\ast},\tau}$ about
$\rho^{\ast}$ when $\pi^{\ast}$ is already known.

These information-centric interpretations of $S_{\pi^{\ast}}$ and
$S_{\rho^{\ast}}$ are vital for understanding the CRLB in a parametric
submodel. As argued in Newey, [1990], one way to interpret the CRLB for
learning $\pi^{\ast}$ (without necessarily learning $\mathbf{p}$) is that it
is the inverse of the variance matrix of the residual we obtain from
projecting $S_{\pi^{\ast}}(Z)$ onto $S_{\rho^{\ast}}(Z)$, where in this case,
the projection is in terms of mean-square distance, which is generally defined
as $\mathbb{E}||V_{1}-V_{2}||_{2}^{2}$ for any two random vectors
$V_{1},V_{2}$. Notationally, this means that for some conformable matrix $B$,
the aforementioned CRLB is equal to

$\bigg{(}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau}}\Big{[}\big{(}S_{\pi^{\ast}}-BS_{\rho^{\ast}}\big{)}\big{(}S_{\pi^{\ast}}-BS_{\rho^{\ast}}\big{)}^{T}\Big{]}\bigg{)}^{-1}$
(23)

In other words, from a semiparametric perspective, the average information
content contained in a single sample $Z$ about $\pi^{\ast}$ absent a priori
knowledge about $\mathbf{p}$ is equal to the variance (i.e., average
magnitude) of what is left over from $S_{\pi}(Z)$ after we remove the part of
$S_{\pi}(Z)$ that lies in the same direction as $S_{\rho^{\ast}}(Z)$. Based on
our previous interpretations of $S_{\pi}$ and $S_{\rho}$, this “removed” part
of $S_{\pi}(Z)$ can be thought of in terms of
$\log\mathcal{J}^{\pi^{\ast},\rho,\tau}$’s sensitivity to changes in
$\pi^{\ast}$: that is, the “removed” part is the part of that sensitivity
which had been due to freezing $\rho$ at $\rho^{\ast}$, as opposed to any
other member of $\mathcal{R}$.

This interpretation of a CRLB is useful for understanding how we were able to
identify the semiparametric efficiency bound in the Fixed $\tau$-IID Regime.
As mentioned earlier, the semiparametric bound can be thought of as the
supremum of CRLBs for estimating $\pi^{\ast}$ in the presence of unknown
$\mathbf{p}$, where the supremum indexes over all possible smooth parametric
submodels. While intuitive as a definition, this does not lend itself to easy
evaluation– indeed, how would one even find that supremum? The trick lies in
the CRLB interpretation we established in the previous paragraph. First, note
that $S_{\pi^{\ast}}$ is the same for all smooth parametric submodels in
question; this is because in the definition of $S_{\pi^{\ast}}$, the finite
dimensional nuisance parameter $\rho$ is always frozen at $\rho=\rho^{\ast}$,
and the underlying truth $\mathbf{p}$ is the same for all submodels. Thus, to
make the aforementioned residual as small as possible, we need to choose a
parametric family for $\mathbf{p}$ for which the distance between
$S_{\pi^{\ast}}(Z)$ and the resulting linear span of the nuisance score is as
small as possible. However, rather than looking over all possible parametric
families separately and computing the residual each time so as to find the one
that is the smallest stochastically, one should note that the minimum of those
individual residuals is the same as the residual obtained from the projection
of $S_{\pi^{\ast}}(Z)$ onto the union of all the aforementioned nuisance
scores. Indeed, this is a simple consequence of the fact that a projection is
always based on the shortest distance between $S_{\pi^{\ast}}(Z)$ and the set
in question.

Of course, in semiparametric statistics, this “union” is replaced by a more
formal notion of taking the mean square closure of all $m$-dimensional linear
combinations of nuisance score functions, but the fundamental idea is the
same. This mean square closure is often called the nuisance tangent set, and
once one is able to identify the residual obtained from projecting
$S_{\pi^{\ast}}$ onto this set, finding the semiparametric efficiency bound
becomes a routine calculation that mimics what is done in display (23) for the
CRLB of smooth parametric submodels. Indeed, as Newey, [1990] states in their
Theorem 3.2, the semiparametric bound is precisely the inverse of the variance
matrix of the aforementioned residual!

At last, having motivated the steps necessary to identify the semiparametric
efficiency bound for the fixed $\tau$-IID Regime, we can finally walk through
those exact steps as it applies to quantification. As mentioned in the
previous paragraph, there are two steps. The first step consists of
identifying the residual of the projection of $S_{\pi^{\ast}}(Z)$ onto the
nuisance tangent set. This is concisely summarized via the following lemma.

######  Lemma 3.6 (Projection of $S_{\pi^{\ast}}$ onto $\mathcal{T}$).

Let $\mathcal{T}$ denote the semiparametric nuisance tangent set defined in
the Appendix. Under Assumptions (B1), (B2) and (B3), we have that

$ds_{\pi^{\ast}}-\mathbf{V}^{\textup{eff}}(\tau)^{-1}\psi_{\tau}^{\textup{eff}}\in\mathcal{T}$

and

$\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau}}\Big{[}t^{\prime}\big{(}S_{\pi^{\ast}}-\big{(}Ds_{\pi^{\ast}}-\mathbf{V}^{\textup{eff}}(\tau)^{-1}\psi_{\tau}^{\textup{eff}}\big{)}\big{)}\Big{]}=0\qquad\forall\
t\in\mathcal{T},$

where

$\displaystyle\psi_{\tau}^{\textup{eff}}(z)$
$\displaystyle:=\frac{d}{\tau}\mathcal{I}(\gamma^{\ast}(\tau))^{-1}\big{(}s_{\gamma^{\ast}(\tau)}(x)-\mathbb{E}_{\pi^{\ast}}[s_{\gamma^{\ast}(\tau)}]\big{)}$
$\displaystyle\qquad-\frac{1-d}{1-\tau}\mathcal{I}(\gamma^{\ast}(\tau))^{-1}\sum_{j=0}^{m}\mathbbold{1}{\\{y=j\\}}\frac{\pi_{j}^{\ast}}{\pi_{j}^{\textup{\text{tr}}}}\big{(}s_{\gamma^{\ast}(\tau)}(x)-\mathbb{E}_{j}[s_{\gamma^{\ast}(\tau)}]\big{)}$

and

$\displaystyle\mathbf{V}^{\textup{eff}}(\tau):=\bigg{[}\frac{1}{\tau}+\frac{1}{1-\tau}\sum_{k=0}^{m}\frac{(\pi_{k}^{\ast})^{2}}{\pi_{k}^{\textup{\text{tr}}}}\bigg{]}\Big{(}\mathcal{I}(\gamma^{\ast}(\tau))^{-1}-\mathcal{I}(\gamma^{\ast}(\tau);\textup{Cat})^{-1}\Big{)}+\frac{1}{\tau}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}.$

Lemma (3.6) tells us that the projection of $S_{\pi^{\ast}}$ onto the nuisance
tangent set $\mathcal{T}$ is given by
$Ds_{\pi^{\ast}}(X)-\mathbf{V}^{\textup{eff}}(\tau)^{-1}\psi_{\tau}^{\textup{eff}}(Z)$,
and that the residual from this projection is equal to
$\mathbf{V}^{\textup{eff}}(\tau)^{-1}\psi_{\tau}^{\textup{eff}}(Z)$. The proof
for this lemma can be found in the Appendix. Next, having identified the
residual, the second step is to compute the inverse of the variance of
$\mathbf{V}^{\textup{eff}}(\tau)^{-1}\psi_{\tau}^{\textup{eff}}(Z)$ when
$Z\sim\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau}$, as the resulting matrix will
be equal to the semiparametric efficiency bound. This is a simple but
algebraically intense calculation, the results of which are summarized in the
following theorem.

######  Theorem 3.7 (Semiparametric Efficiency Bound in Fixed $\tau$-IID
Regime).

Under Assumptions (B1), (B2) and (B3), the efficient influence function is
$\psi^{\textup{eff}}_{\tau}$, the semiparametric efficiency bound is
$\mathbf{V}^{\textup{eff}}(\tau)$, and
$\mathbf{V}^{\textup{eff}}(\tau)=\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau}}[\psi^{\textup{eff}}_{\tau}]$.

Theorem (3.7) identifies $\mathbf{V}^{\textup{eff}}(\tau)$ as the
semiparametric efficiency bound for quantifiers that are regular and
asymptotically linear within the Fixed $\tau$-IID Regime. This result is
extremely encouraging, because upon inspection,
$\mathbf{V}^{\textup{eff}}(\tau)$ is the Fixed $\tau$-IID Regime’s analogue of
the variance matrix identified for SELSE in the Fixed Sequence Regime within
subsection (3.1) in Theorem (3.4). Furthermore, in establishing this result,
we were also able to identify $\psi_{\tau}^{\textup{eff}}$ as the efficient
influence function, which we had first mentioned in subsection (3.6). Also,
recall from that same subsection that the variance of the efficient influence
function should be equal to the semiparametric efficiency bound. As a sanity
check, Theorem (3.7) verifies that this is indeed the case.

####  3.7.2 $\tau_{n}$-IID Regime

The parallel between the asymptotic variance matrix identified for SELSE in
the Fixed Sequence Regime and the semiparametric efficiency bound identified
in the Fixed $\tau$-IID Regime was exciting, because it suggested that the two
variance matrices would align upon translating our results into the final
$\tau_{n}$-IID Regime.

Encouraged by this, we first focused on the translation for the asymptotic
results of SELSE. While algebraically tedious, the strategy was quite
straightforward. Essentially, the main insight comes from recognizing that the
stochastic behavior of SELSE in the Fixed Sequence Regime can be thought of as
its behavior in the $\tau_{n}$-IID Regime when we condition on the event that
$N^{\textup{\text{tr}}}=(1-\tau_{n})n$ and $N^{\textup{\text{te}}}=\tau_{n}n$.
Since $N^{\textup{\text{tr}}}/n$ and $N^{\textup{\text{te}}}/n$ will
concentrate around $1-\tau_{n}$ and $\tau_{n}$ respectively, it follows that
the behavior of SELSE in the Fixed Sequence Regime based on setting
$n^{\textup{\text{tr}}}=(1-\tau_{n})n$ and $n^{\textup{\text{te}}}=\tau_{n}n$
is representative of its behavior in the $\tau_{n}$-IID Regime. Hence,
combining this intuition with Theorem (3.4) from the Fixed Sequence Regime, we
were well positioned to prove the following lemma.

######  Lemma 3.8 (First and Second Order Error of SELSE in $\tau_{n}$-IID
Regime).

Under Assumptions (B1), (B2), (4), (5), (6), (7), (8) and (9), the SELSE
quantifier $\widehat{\pi}_{n}$ satisfies

$\sqrt{n}(\widehat{\pi}_{n}-\pi^{\ast})=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\psi_{\tau_{n}}^{\textup{eff}}(Z_{i})+\delta_{\tau_{n}}$

where $\psi_{\tau_{n}}^{\textup{eff}}:\mathcal{Z}\mapsto\mathbb{R}^{m}$ is as
defined in Lemma (3.6) and satisfies

$\frac{(1-{\tau}_{n})^{2}}{{\tau}_{n}n}\mathbb{E}_{\pi^{\ast}}\Big{[}||{\tau}_{n}\psi^{\textup{eff}}_{{\tau}_{n}}(X,-1,1)||_{2}^{4}\Big{]}+\frac{{\tau}_{n}^{2}}{(1-{\tau}_{n})n}\sum_{y=0}^{m}\pi_{y}^{\textup{\text{tr}}}\mathbb{E}_{y}\Big{[}||(1-{\tau}_{n})\psi^{\textup{eff}}_{{\tau}_{n}}(X,y,0)||_{2}^{4}\Big{]}\to
0,$

and $\delta_{\tau_{n}}\in\mathbb{R}^{m}$ satisfies

$\displaystyle||\delta_{\tau_{n}}||_{2}$
$\displaystyle=O_{\mathbb{P}}\Bigg{(}\frac{1}{\sqrt{n\tau_{n}(1-\tau_{n})}}+\sqrt{\frac{1}{\sqrt{\bar{n}^{\textup{\text{tr}}}}}+\max_{y}\lambda_{y}\Omega(s_{\bar{\gamma},y})^{2}+\frac{1}{\sqrt{\min_{y}\lambda_{y}}}e^{-C\bar{n}^{\textup{\text{tr}}}}}\Bigg{)}$
$\displaystyle\qquad+O_{\mathbb{P}}\Bigg{(}\sqrt{\max_{y}\mathbb{E}_{\bar{\mathcal{D}}^{\textup{\text{tr,II}}}}\Big{[}\bar{\mathcal{U}}_{y}(\lambda_{y})\Big{]}+\sqrt{\mathbb{E}_{\bar{\mathcal{D}}^{\textup{\text{II}}}}\Big{[}||\widehat{\gamma}-\bar{\gamma}||_{2}^{2}\Big{]}}}\Bigg{)}$
$\displaystyle\qquad+O_{\mathbb{P}}\Bigg{(}\sqrt{\tau_{n}(1-\tau_{n})n}e^{-C(\min_{y}\lambda_{y})^{2}\bar{n}^{\textup{\text{tr}}}}+\sqrt{\tau_{n}(1-\tau_{n})n}\mathbb{P}_{\bar{\mathcal{D}}^{\textup{\text{II}}}}\Big{[}\big{|}\big{|}\widehat{\gamma}-\bar{\gamma}\big{|}\big{|}_{2}\geq
C\Big{]}\Bigg{)},$

where $\bar{\mathcal{D}}^{\textup{\text{tr,II}}}$,
$\bar{\mathcal{D}}^{\textup{\text{II}}}$, $\bar{\gamma}$ and
$\bar{\mathcal{U}}_{y}(\lambda_{y})$ are as defined in subsection (3.5.3) and
correspond to some sequence
$(\bar{n}^{\textup{\text{te}}},\bar{n}_{0}^{\textup{\text{tr}}},\dots,\bar{n}_{m}^{\textup{\text{tr}}})$
that satisfies
$\big{|}\bar{n}^{\textup{\text{te}}}/n-\tau_{n}\big{|},\big{|}\bar{n}_{y}^{\textup{\text{tr}}}/n^{\textup{\text{tr}}}-(1-\tau_{n})\pi_{y}^{\textup{\text{tr}}}\big{|}\to
0$ where $\bar{n}^{\textup{\text{tr}}}:=n-\bar{n}^{\textup{\text{te}}}$.

The proof for Lemma (3.8) is in the Appendix. Lemma (3.8) establishes several
facts about SELSE. First, it shows that SELSE is asymptotically linear in the
efficient influence function under the $\tau_{n}$-IID Regime. Since the Fixed
$\tau$-IID Regime is a special case of the $\tau_{n}$-IID Regime, this means
that SELSE satisfies property (C1), modulo the regularity condition, which we
prove SELSE satisfies in Lemma (6.25) in the Appendix. Second, Lemma (3.8)
establishes that the second order $\delta_{\tau_{n}}$ satisfies property (C2a)
and that its efficient influence function $\psi_{\tau_{n}}^{\textup{eff}}$
satisfies property (C2b). Thus, overall, Lemma (3.8) verifies all the
conditions needed to show that SELSE is a member of $\mathcal{E}$. The fact
that the efficient influence function appears again in SELSE’s first order
error but now in the context of the $\tau_{n}-IID$ Regime is also exciting, as
it means that we have only a single step remains for establishing SELSE’s
semiparametric efficiency: we must now translate the semiparametric efficiency
bound from the Fixed $\tau$-IID Regime to the $\tau_{n}$-IID Regime. The
culmination of that endeavor, along with all of our results so far, is
presented in Theorem (3.9) in the next subsection.

###  3.8 Main Result

We now present our main theoretical result on SELSE’s performance and state
the semiparametric efficiency bound for quantification tasks, both in the
context of the $\tau_{n}$-IID Regime.

######  Theorem 3.9 (Semiparametric Efficiency in $\tau_{n}$-IID Regime).

Let $\tau_{n}$ denote any sequence satisfying Assumptions (8) and (9), and let
$\widetilde{\pi}_{n}$ denote any quantifier and $\psi_{\tau_{n}}$ its
influence function. Under the Assumptions in subsections (3.5.1), (3.5.2),
(3.5.3) and (3.5.4), if $\widetilde{\pi}_{n}\in\mathcal{E}$, then there exists
a corresponding random vector $G_{n}$ such that $G_{n}\xrightarrow{\enskip
d\enskip}\mathcal{N}(0,I_{m\times m})$ and

$\sqrt{\tau_{n}(1-\tau_{n})n}(\widetilde{\pi}_{n}-\pi^{\ast})=\Big{(}\tau_{n}(1-\tau_{n})\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}[\psi_{\tau_{n}}]\Big{)}^{\frac{1}{2}}G_{n}+o_{\mathbb{P}}(1),$

where
$\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}[\psi_{\tau_{n}}]\succeq\mathbf{V}^{\textup{eff}}(\tau_{n})$
for each $n$, and the matrix $\mathbf{V}^{\textup{eff}}(\tau_{n})$ is given by

$\mathbf{V}^{\textup{eff}}(\tau_{n}):=\bigg{[}\frac{1}{\tau_{n}}+\frac{1}{1-\tau_{n}}\sum_{k=0}^{m}\frac{(\pi_{k}^{\ast})^{2}}{\pi_{k}^{\textup{\text{tr}}}}\bigg{]}\Big{(}\mathcal{I}(\gamma^{\ast}(\tau_{n}))^{-1}-\mathcal{I}(\gamma^{\ast}(\tau_{n});\textup{Cat})^{-1}\Big{)}+\frac{1}{\tau_{n}}\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1},$

where
$\gamma^{\ast}(\tau_{n}):=(\gamma_{1}^{\ast}(\tau_{n}),\dots,\gamma_{m}^{\ast}(\tau_{n}))$
and

$\gamma_{y}^{\ast}(\tau_{n}):=\frac{\frac{\pi_{y}^{\ast}}{\tau_{n}}+\frac{1}{1-\tau_{n}}\frac{(\pi_{y}^{\ast})^{2}}{\pi_{y}^{\textup{\text{tr}}}}}{\frac{1}{\tau_{n}}+\frac{1}{1-\tau_{n}}\sum_{k=0}^{m}\frac{(\pi_{k}^{\ast})^{2}}{\pi_{k}^{\textup{\text{tr}}}}}\qquad\forall\
y\in\mathcal{Y}.$

Furthermore, our SELSE quantifier $\widehat{\pi}_{n}$ has an influence
function $\psi_{\tau_{n}}^{\textup{eff}}$ which satisfies

$\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}[\psi_{\tau_{n}}^{\textup{eff}}]=\mathbf{V}^{\textup{eff}}(\tau_{n})$

for each $n$, and $\widehat{\pi}_{n}\in\mathcal{E}$.

In a nutshell, Theorem (3.9) states that SELSE is a member of $\mathcal{E}$,
and that among all members of $\mathcal{E}$, SELSE has the smallest possible
asymptotic variance matrix for its normalized error. This variance matrix is
equal to $\tau_{n}(1-\tau_{n})\mathbf{V}^{\text{eff}}(\tau_{n})$, and it is
the acclaimed semiparametric efficiency bound for the $\tau_{n}$-IID Regime.
The main logic underlying this result is that the asymptotic variance of a
quantifier’s error is simply the variance (scaled by $\tau_{n}(1-\tau_{n})$)
of its own influence function, and the variance of our quantifier’s influence
function can be shown to be always less than or equal to the variance of any
other member’s. This result is largely due to SELSE’s usage of
$\widehat{s}_{\widehat{\gamma}}$ as a proxy for $s_{\gamma^{\ast}}$ in its
ACC/PACC approach: as indicated by the dependence of
$\mathbf{V}^{\text{eff}}(\tau_{n})$ on $\tau_{n}$, the “optimal” performance
for estimating $\pi^{\ast}$ varies greatly with $\tau_{n}$, and the dependence
of $\gamma^{\ast}$ on the number of train and test samples allows our
quantifier to account for this fact when estimating $\pi^{\ast}$.

The fact that SELSE has the smallest possible eigenvalues for its asymptotic
variance matrix is attractive from two different points of view. First, it
follows that our quantifier is optimal for learning $\pi^{\ast}$ under $L_{2}$
loss: for any other quantifier $\widetilde{\pi}\in\mathcal{E}$, the asymptotic
variance of $\sqrt{\tau_{n}(1-\tau_{n})n}||\widehat{\pi}_{n}-\pi^{\ast}||_{2}$
will always be less than or equal to that of
$\sqrt{\tau_{n}(1-\tau_{n})n}||\widetilde{\pi}_{n}-\pi^{\ast}||_{2}$. Second,
our quantifier is optimal for estimating smooth functions of $\pi^{\ast}$.
That is, for any integer $l\geq 1$ and smooth function
$\ell:\mathbb{R}^{m}\mapsto\mathbb{R}^{l}$, the asymptotic variance matrix of
$\sqrt{\tau_{n}(1-\tau_{n})n}(\ell(\widehat{\pi}_{n})-\ell(\pi^{\ast}))$ will
always be less than or equal to that of
$\sqrt{\tau_{n}(1-\tau_{n})n}(\ell(\widetilde{\pi}_{n})-\ell(\pi^{\ast}))$.
This can be easily deduced via a first order Taylor expansion of both
normalized errors. From a practical point of view, this means that our
quantifier is optimal for learning at least three different, interesting
scalar quantities, each of which correspond to setting $l=1$ and
$\ell(\beta)=c^{\prime}\beta+d$ for an appropriate choice of
$c\in\mathbb{R}^{m}$ and $d\in\mathbb{R}$: the probability of
$Y^{\textup{\text{te}}}$ belonging to a specific class (or group of classes),
the difference in probability of belonging to one class (or group) versus
another class (or group), and the expected value of a function of
$Y^{\textup{\text{te}}}$.

Lastly, in addition to verifying the optimality of our quantifier, the
semiparametric efficiency bound also provides us a deeper understanding of the
general problem of quantification. In particular, it reveals that
quantification problems are actually a “blend” of two other statistical
estimation tasks:

  1. (a)

estimating $\pi^{\ast}$ when $\mathbf{p}$ is known but $p_{\pi^{\ast}}$ is
unknown, and we have IID samples from $p_{\pi^{\ast}}$, and

  2. (b)

estimating $\pi^{\ast}$ when $p_{\pi^{\ast}}$ is known but $\mathbf{p}$ is
unknown, and we have IID samples from each density in $\mathbf{p}$.

The degree to which quantification is similar to problem (a) versus (b)
depends on $\tau_{n}$. If $\tau_{n}\to 0$, then quantification becomes
identical to problem (a), and if $\tau_{n}\to 1$, then quantification becomes
identical to problem (b). To see why, start by considering the former
situation when $\tau_{n}\to 0$. When this happens, there are far more train
samples than test samples, and so for large $n$, we essentially have perfect
knowledge of $\mathbf{p}$ and must estimate $\pi^{\ast}$ using samples from
the unknown $p_{\pi^{\ast}}$. This is exactly the definition of problem (a).
Furthermore, the equivalence between quantification and problem (a) when
$\tau_{n}\to 0$ also agrees with the limiting behavior of the semiparametric
efficiency bound. Indeed, since $\gamma^{\ast}(0)=\pi^{\ast}$, we have that

$\displaystyle\tau_{n}(1-\tau_{n})\mathbf{V}^{\textup{eff}}(\tau_{n})$
$\displaystyle=\bigg{[}(1-\tau_{n})+\tau_{n}\sum_{k=0}^{m}\frac{(\pi_{k}^{\ast})^{2}}{\pi_{k}^{\textup{\text{tr}}}}\bigg{]}\Big{(}\mathcal{I}(\gamma^{\ast}(\tau_{n}))^{-1}-\mathcal{I}(\gamma^{\ast}(\tau_{n});\textup{Cat})^{-1}\Big{)}$
$\displaystyle\qquad+(1-\tau_{n})\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}$
$\displaystyle\xrightarrow{\enskip\tau_{n}\to
0\enskip}\Big{(}\mathcal{I}(\pi^{\ast})^{-1}-\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}\Big{)}+\mathcal{I}(\pi^{\ast};\textup{Cat})^{-1}$
$\displaystyle=\mathcal{I}(\pi^{\ast})^{-1}.$

$\mathcal{I}(\pi^{\ast})^{-1}$ is the CRLB for estimating $\pi^{\ast}$ in
problem (a), and so the fact that
$\tau_{n}(1-\tau_{n})\mathbf{V}^{\textup{eff}}(\tau_{n})\to\mathcal{I}(\pi^{\ast})^{-1}$
as $\tau_{n}\to 0$ means that the difficulty of learning $\pi^{\ast}$ in
quantification becomes equal to the difficulty in problem (a), further
verifying the equivalence between the two problems.

The opposite happens when $\tau_{n}\to 1$: in this situation, there are far
more test samples than train samples, and so for large $n$, we essentially
have perfect knowledge of $p_{\pi^{\ast}}$ and must estimate $\pi^{\ast}$
using the samples obtained from each density in $\mathbf{p}$. This is exactly
the definition of problem (b). Now, similar to before, one can also show that
the semiparametric efficiency bound for quantification converges to the bound
for problem (b) when $\tau_{n}\to 1$, but proving the bound for problem (b) is
tedious since the problem is still semiparametric. Therefore, as a compromise,
we instead point out the equivalence for a special parametric case of problem
(b): namely, when $m=1$ and both $p_{\pi^{\ast}}$ and $p_{0}$ are known but
$p_{1}$ is unknown, and we obtain IID samples from $p_{1}$. This special case
of problem (b) corresponds to a quantification task where $\tau_{n}\to 1$ and
$\pi^{\textup{\text{tr}}}\to 0$, because when those limits hold, we will have
very few train samples from class $1$, but an abundance of train samples from
class $0$, as well as many test samples. As such, when $n$ is large, we will
have near perfect knowledge of $p_{\pi^{\ast}}$ and $p_{0}$, and must estimate
$\pi^{\ast}$ using the samples from $p_{1}$. This equivalence is corroborated
by the limiting behavior of the semiparametric efficiency bound, since

$\displaystyle\pi^{\textup{\text{tr}}}(1-\pi^{\textup{\text{tr}}})\tau_{n}(1-\tau_{n})\mathbf{V}^{\textup{eff}}(\tau_{n})$
$\displaystyle\xrightarrow{\enskip(\tau_{n},\pi^{\textup{\text{tr}}})\to(1,0)\enskip}(\pi^{\ast})^{2}\mathcal{I}(1)^{-1},$

where $(\pi^{\ast})^{2}\mathcal{I}(1)^{-1}$ is the CRLB for estimating
$\pi^{\ast}$ in the special parametric version of problem $(b)$.

###  3.9 Proof of Main Result

######  Proof of Theorem (3.9)..

First, we verify that $\widehat{\pi}_{n}\in\mathcal{E}$. Note that, under
Assumptions (B1), (B2), (B3), (4), (5), (6) and (7), we have by Lemma (6.25)
that, for each fixed $\tau\in(0,1)$, the estimator $\widehat{\pi}_{n}$ is
$\tau$-RAL with influence function $\psi_{\tau}^{\textup{eff}}$ and second
order error $\delta_{\tau}$. Thus, property (C1) holds for
$\widehat{\pi}_{n}$. Furthermore, under Assumptions (B1), (B2), (4), (5), (6)
and (7), for any sequence $\tau_{n}$ that satisfies Assumptions (8) and (9),
it follows from Lemma (3.8) that properties (C2a) and (C2b) also hold. Thus,
$\widehat{\pi}_{n}\in\mathcal{E}$.

Second, we verify the theorem’s asymptotic statements concerning an arbitrary
quantifier $\widetilde{\pi}_{n}\in\mathcal{E}$. Since $\widetilde{\pi}_{n}$ is
$\tau$-RAL for all $\tau\in(0,1)$ by virtue of property (C1), it follows that
for any $n$, the equation

$\sqrt{\tau_{n}(1-\tau_{n})n}(\widetilde{\pi}_{n}-\pi^{\ast})=\sqrt{\frac{\tau_{n}(1-\tau_{n})}{n}}\sum_{i=1}^{n}\psi_{\tau_{n}}(Z_{i})+\sqrt{\tau_{n}(1-\tau_{n})}\delta_{\tau_{n}}(Z_{1:n})$

holds for every dataset $Z_{1:n}$. Further, due to Assumptions (8) and (9), we
have by property (C2a) that $\delta_{\tau_{n}}(Z_{1:n})\xrightarrow{\enskip
p\enskip}0$. So, because $\sqrt{\tau_{n}(1-\tau_{n})}$ is bounded, it follows
that

$\implies\sqrt{\tau_{n}(1-\tau_{n})n}(\widetilde{\pi}_{n}-\pi^{\ast})=\sqrt{\frac{\tau_{n}(1-\tau_{n})}{n}}\sum_{i=1}^{n}\psi_{\tau_{n}}(Z_{i})+o_{\mathbb{P}}(1).$

Additionally, since $\widetilde{\pi}_{n}$ is $\tau$-RAL for all
$\tau\in(0,1)$, the matrix
$\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}$
is nonsingular for all $n$. Thus, the first order term above may be written
as:

$\displaystyle\sqrt{\frac{\tau_{n}(1-\tau_{n})}{n}}\sum_{i=1}^{n}\psi_{\tau_{n}}(Z_{i})$
$\displaystyle=\Big{(}\tau_{n}(1-\tau_{n})\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}\Big{)}^{\tfrac{1}{2}}\underbrace{\sum_{i=1}^{n}\overbrace{n^{-\frac{1}{2}}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}^{-\tfrac{1}{2}}\psi_{\tau_{n}}(Z_{i})}^{=:W_{n,i}}}_{=:G_{n}}.$

We will now prove that $G_{n}\equiv\sum_{i=1}^{n}W_{n,i}\xrightarrow{\enskip
p\enskip}\mathcal{N}(0,I_{m})$. Towards that end, observe that
$\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}[W_{n,i}]=0$ and
$\sum_{i=1}^{n}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}W_{n,i}W_{n,i}^{\prime}\big{]}=I_{m}$.
Also, for any $c>0$, we have that:

$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}||W_{n,i}||_{2}^{2}\mathbbold{1}{\big{\\{}||W_{n,i}||_{2}>c\big{\\}}}\Big{]}$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}||W_{n,i}||_{2}^{2}\mathbbold{1}{\big{\\{}||W_{n,i}||_{2}^{2}>c^{2}\big{\\}}}\Big{]}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}\psi_{\tau_{n}}(Z_{i})^{\prime}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}^{-1}\psi_{\tau_{n}}(Z_{i})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\times\mathbbold{1}{\big{\\{}\psi_{\tau_{n}}(Z_{i})^{\prime}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}^{-1}\psi_{\tau_{n}}(Z_{i})>nc^{2}\big{\\}}}\Big{]}$
$\displaystyle=\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}\psi_{\tau_{n}}(Z)^{\prime}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}^{-1}\psi_{\tau_{n}}(Z)\mathbbold{1}{\big{\\{}\psi_{\tau_{n}}(Z)^{\prime}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}^{-1}\psi_{\tau_{n}}(Z)>nc^{2}\big{\\}}}\Big{]}.$

Also note that:

$\displaystyle\psi_{\tau_{n}}(Z)^{\prime}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}^{-1}\psi_{\tau_{n}}(Z)$
$\displaystyle\leq||\psi_{\tau_{n}}(Z)||_{2}^{2}\lambda_{\textup{max}}\big{(}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}^{-1}\big{)}$
$\displaystyle=\frac{||\psi_{\tau_{n}}(Z)||_{2}^{2}}{\lambda_{\textup{min}}\big{(}\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}\big{)}}$
$\displaystyle\leq\frac{||\psi_{\tau_{n}}(Z)||_{2}^{2}}{\lambda_{\textup{min}}\big{(}\mathbf{V}^{\textup{eff}}(\tau_{n})\big{)}}$
$\displaystyle\leq\frac{\tau_{n}(1-\tau_{n})||\psi_{\tau_{n}}(Z)||_{2}^{2}}{(\xi)^{2}\nu\big{(}\frac{L}{m+1}\big{)}^{2}}.$

The third line is due to the fact that $\widetilde{\pi}_{n}$ is $\tau$-RAL for
each fixed $\tau\in(0,1)$, which under Assumptions (B1), (B2) and (B3),
implies that
$\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}^{\textup{eff}}\big{]}=\mathbf{V}^{\textup{eff}}(\tau_{n})\preceq\textup{\text{Var}}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\big{[}\psi_{\tau_{n}}(Z)\big{]}$
for each $n$ by virtue of Theorem (3.7). The fourth line is due to Lemma
(6.19) and Assumption (B1). For notational convenience, temporarily define
$b:=(\xi)^{2}\nu\big{(}\frac{L}{m+1}\big{)}^{2}$. Then, it follows that:

$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}||W_{n,i}||_{2}^{2}\mathbbold{1}{\big{\\{}||W_{n,i}||_{2}>c\big{\\}}}\Big{]}$
$\displaystyle\leq\frac{\tau_{n}(1-\tau_{n})}{b}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}||\psi_{\tau_{n}}(Z)||_{2}^{2}\mathbbold{1}{\big{\\{}||\psi_{\tau_{n}}(Z)||_{2}^{2}>nc^{2}\tfrac{b}{\tau_{n}(1-\tau_{n})}\big{\\}}}\Big{]}$
$\displaystyle=\frac{\tau_{n}(1-\tau_{n})}{b}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Bigg{[}\frac{||\psi_{\tau_{n}}(Z)||_{2}^{4}}{||\psi_{\tau_{n}}(Z)||_{2}^{2}}\mathbbold{1}{\big{\\{}||\psi_{\tau_{n}}(Z)||_{2}^{2}>nc^{2}\tfrac{b}{\tau_{n}(1-\tau_{n})}\big{\\}}}\Bigg{]}$
$\displaystyle\leq\frac{\tau_{n}^{2}(1-\tau_{n})^{2}}{nc^{2}b^{2}}\mathbb{E}_{\mathcal{J}^{\pi^{\ast},\mathbf{p},\tau_{n}}}\Big{[}||\psi_{\tau_{n}}(Z)||_{2}^{4}\Big{]}$
$\displaystyle=\frac{\tau_{n}^{2}(1-\tau_{n})^{2}}{nc^{2}b^{2}}\Bigg{\\{}\tau_{n}\mathbb{E}_{\pi^{\ast}}\Big{[}||\psi_{\tau_{n}}(X,-1,1)||_{2}^{4}\Big{]}+(1-\tau_{n})\sum_{y=0}^{m}\pi_{y}^{\textup{\text{tr}}}\mathbb{E}_{y}\Big{[}||\psi_{\tau_{n}}(X,y,0)||_{2}^{4}\Big{]}\Bigg{\\}}$
$\displaystyle=\frac{1}{c^{2}b^{2}}\Bigg{\\{}\frac{\tau_{n}^{3}(1-\tau_{n})^{2}}{n}\mathbb{E}_{\pi^{\ast}}\Big{[}||\psi_{\tau_{n}}(X,-1,1)||_{2}^{4}\Big{]}+\frac{\tau_{n}^{2}(1-\tau_{n})^{3}}{n}\sum_{y=0}^{m}\pi_{y}^{\textup{\text{tr}}}\mathbb{E}_{y}\Big{[}||\psi_{\tau_{n}}(X,y,0)||_{2}^{4}\Big{]}\Bigg{\\}}$
$\displaystyle=\frac{1}{c^{2}b^{2}}\Bigg{\\{}\frac{(1-\tau_{n})^{2}}{\tau_{n}n}\mathbb{E}_{\pi^{\ast}}\Big{[}||\tau_{n}\psi_{\tau_{n}}(X,-1,1)||_{2}^{4}\Big{]}+\frac{\tau_{n}^{2}}{(1-\tau_{n})n}\sum_{y=0}^{m}\pi_{y}^{\textup{\text{tr}}}\mathbb{E}_{y}\Big{[}||(1-\tau_{n})\psi_{\tau_{n}}(X,y,0)||_{2}^{4}\Big{]}\Bigg{\\}},$

where the last line goes to zero as $n\to\infty$ by virtue of property (C2b).
Therefore, by Theorem 11.1.6 in Athreya and Lahiri, [2006], we may conclude
that $G_{n}\xrightarrow{\enskip d\enskip}\mathcal{N}(0,I_{m})$. ∎

##  4 Numerical Experiments

We now study SELSE’s empirical performance. This is an important supplement to
our theoretical analysis, because while we have established the optimality of
SELSE’s first order error term, we have not discussed the optimality of its
higher order ones, and in practice, a quantifier’s total error always depends
on both. The experiments in this section therefore aim to provide a more
complete, practical picture of SELSE and its competitors.

###  4.1 Experimental Set-Up

We performed experiments on synthetic and real world data. The synthetic data
involved two classes, with the covariates from each class sampled from
different 2D gaussian distributions, each with identity covariance. For class
$0$, the associated mean vector was $(-1,-1)^{T}$, and for class $1$, the
associated mean vector was $(1,1)^{T}$. In terms of real world data, we
considered a blood transfusion dataset. This dataset was used as a benchmark
in Moreo et al., [2021]’s systematic comparison of different quantification
methods, which includes all the quantifiers considered here except for SELSE.

The experimental set-up for the synthetic and real world datasets were
similar. For a given combination of $n,\tau,\pi^{\textup{\text{tr}}}$ and
$\pi^{\ast}$, we generated $n^{\textup{\text{te}}}=\tau n$ test samples and
$n^{\textup{\text{tr}}}=(1-\tau)n$ train samples. For the real world data, the
train data for each class $y$ was generated by sampling with replacement from
the points in the original dataset that belonged to class $y$. The test data
was generated in a similar fashion, except for each test sample, the class
that we took the sample from was determined randomly according to
$\text{Cat}(\pi^{\ast})$. Then, once the train and test data were formed, we
computed six different quantifiers555The performance of SELSE and MLLS was
measured in the R programming language via our own in-house implementations of
those quantifiers, whereas the measurements for ACC, PACC, HDy and EMQ were
done via their Python implementations in the QuaPy package [Moreo et al.,,
2021].: ACC, PACC, HDy, EMQ, MLLS and SELSE, all of which were described in
the Methodology section. For each quantifier $\widetilde{\pi}$, the normalized
error $\sqrt{\tau_{n}(1-\tau_{n})n}||\widetilde{\pi}-\pi^{\ast}||_{2}$ was
recorded. This experiment was repeated 100 times, and for each quantifier, the
average of its normalized error across those experiments was calculated.

This average served as our main metric for the performance of a quantifier
under a given combination of $n,\tau,\pi^{\textup{\text{tr}}}$ and
$\pi^{\ast}$. The combinations we considered were as follows. For both
datasets, we set $n=500$ and $\pi^{\textup{\text{tr}}}=\frac{1}{2}$, and
computed our metric over all combinations of $\tau\in\\{0.2,0.5,0.8\\}$ and
$\pi^{\ast}\in\\{0.05,0.2,0.35,0.5,0.65,0.80,0.95\\}$. We froze
$\pi^{\textup{\text{tr}}}$ at $\frac{1}{2}$ to limit the amount of simulations
that needed to be done.

###  4.2 Quantifier Configuration Details

The configuration details of the six quantifiers are as follows. Recall that
all the quantifiers in question make use of some form of classifier. For ACC,
this is a hard classifier, and for PACC, HDy, EMQ and MLLS, this is a soft
classifier. SELSE also uses a soft classifier indirectly, since in Step 2, a
preliminary quantifier for $\pi^{\ast}$ is utilized to form the plug-in
estimator $\widehat{\gamma}$, and in our experiments, MLLS served as that
preliminary quantifier. For all six quantifiers and both datasets, the
classifier in question was a SVM with either a radial or polynomial kernel and
$\ell_{2}$ penalty (the exact kernel and penalization parameters were selected
via 3-fold cross validation) Finally, SELSE has several other unique
parameters in Step 3 that relate to how the score function is estimated, which
need to be chosen. Specifically, in our experiments, we chose each space
$\mathcal{H}_{y}$ to be a RKHS, with a gaussian reproducing kernel. The kernel
width and penalty parameters used to construct
$f=\widehat{s}_{\widehat{\gamma}}$ were chosen to minimize the maximum
eigenvalue of the empirical counterpart to
$A_{f}^{-1}\textup{\text{Var}}_{\widehat{\gamma}}[f]A_{f}^{-T}$, which was
computed on a separate validation set.

---

(a) $\tau=0.2$

(b) $\tau=0.8$

(c) $\tau=0.5$

(d) SELSE: True Score Correlation

Figure 1: Simulation Results on Synthetic Gaussian Mixture Data.

---

(a) $\tau=0.2$

(b) $\tau=0.5$

(c) $\tau=0.8$

Figure 2: Simulation Results on Transfusion Data.

###  4.3 Results & Discussion

We now turn to the results of our experiments. We begin by making two general
observations. First, in both experiments, all quantifiers tended to preform
worse for larger values of $\tau$ than for smaller values of $\tau$. This
means that, at least in these two types of data, a scarcity of training
samples is harder to handle than a scarcity of test samples. Second, when
$\tau$ is small, estimating $\pi^{\ast}$ when $\pi^{\ast}$ is close to $0$ or
$1$ is far easier than when $\pi^{\ast}$ is close to $\frac{1}{2}$. This makes
sense in light of our discussion at the end of the Theoretical Results
section, and holds for all datasets (not just the ones considered here). This
is because when $\tau\to 0$, the semiparametric efficiency bound approaches
the CRLB for the classic parametric mixture problem. The parametric problem is
easier when $\pi^{\ast}$ takes on extreme values, much in the same way that
estimating $p$ using independent flips of a $p$-biased coin is easier when
$p\approx 0$ or $p\approx 1$ than when $p\approx\frac{1}{2}$. However, this
pattern tends to weaken as $\tau$ increases.

Next, we comment on the performance of SELSE specifically. In our synthetic
data experiment, SELSE outperforms the other quantifiers for nearly all
combinations of $\tau$ and $\pi^{\ast}$. This makes sense in light of Figure
(1d), which shows that SELSE’s score function estimates tend to be highly
correlated with $s_{\gamma^{\ast}}$. This correlation is desirable when one
estimates $\pi^{\ast}$ because, as discussed in subsections (2.5.1) and
(2.5.2), using $s_{\gamma^{\ast}}$ allows one to strike the ideal balance
between one’s uncertainty about the mixture distribution (caused by the finite
amount of test data) and the component densities (caused by the finite amount
of train data). Correspondingly, the fact that the performance gap between
SELSE and the other quantifiers grows as $\tau\to 1$ suggests that the other
quantifiers are unable to effectively orchestrate this balance. This
especially makes sense for EMQ and MLLS, since both of those methods are based
on the maximum likelihood principle. As mentioned in subsection (2.2.2),
maximum likelihood assumes that either the $Y\mid X$ or $Y\mid f(X)$
conditional can be learned, which is a difficult requirement to satisfy when
the training set is extremely small. Finally, the same observations made about
SELSE for our synthetic data experiment also hold true for the transfusion
data experiment. The only exception to this is HDy, which tends to outperform
SELSE when $\tau$ is small. However, the performance of HDy also degrades for
extreme values of $\pi^{\ast}$ as $\tau\to 1$, making HDy unreliable in those
situations. In contrast, SELSE is able to avoid this pitfall: with the
exception of HDy, SELSE’s error is almost uniformly smaller than the error of
any other quantifier, regardless of the value of $\tau$, making it a
favorable, general-purpose quantifier to turn to when one does not want to
worry about the effect of $\tau$.

##  5 Conclusion

In summary, we proposed the SELSE quantifier as a method for inferring the
response distribution in the test set under the label shift assumption. We
proved that SELSE is semiparametric efficient for a broad class of
quantifiers, implying that SELSE’s first order error term is optimally small.
We also grounded our theoretical results of SELSE’s optimality in two
empirical studies, and numerically showed the distinct advantages of SELSE
over many of the existing approaches to quantification.

##  6 Appendix

###  6.1 Three Regimes

Here we provide a more in depth description of the three regimes initially
presented in subsection (3.3), as this will aid us in proving the supporting
lemmas and theorems in the Appendix. Recall that the regimes differ from each
other in two key regards: the data generation mechanism, and how the true
parameters behave as $n\to\infty$.

####  6.1.1 Fixed Sequence Regime

In the Fixed Sequence Regime, there exists a fixed sequence

$\big{\\{}(n^{\textup{\text{te}}},n^{\textup{\text{tr}}},\pi^{\ast},\pi^{\textup{\text{tr}}},p_{0},p_{1},\dots,p_{m})\big{\\}}_{n=1}^{\infty}$

where the sample sizes $0\leq
n^{\textup{\text{te}}},n^{\textup{\text{tr}}}\to\infty$ satisfy
$n^{\textup{\text{te}}}+n^{\textup{\text{tr}}}=n$, and the class probabilities
$\pi^{\ast},\pi^{\textup{\text{tr}}}$ and class densities $p_{0},\dots,p_{m}$
are subject to various restrictions that shall be described later. The class