# Boosting Fairness and Robustness in Over-the-Air Federated Learning*
††thanks: * This work has been funded by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC
2002/1 “Science of Intelligence” – project number 390523135. ††thanks: 1 H.Y.
Oksuz, F. Molinari, and J. Raisch are with the Control Systems Group at
Technische Universität Berlin, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS> ††thanks: 2 H.Y. Oksuz, H. Sprekeler,
and J. Raisch are with Exzellenzcluster Science of Intelligence, Technische
Universität Berlin, Marchstr. 23, 10587, Berlin, Germany. ††thanks: 3 H.
Sprekeler is with the Modelling Cognitive Processes Group at Technische
Universität Berlin, Germany.

Halil Yigit Oksuz1,2, Fabio Molinari1, Henning Sprekeler2,3, Jörg Raisch1,2

###### Abstract

Over-the-Air Computation is a beyond-5G communication strategy that has
recently been shown to be useful for the decentralized training of machine
learning models due to its efficiency. In this paper, we propose an Over-the-
Air federated learning algorithm that aims to provide fairness and robustness
through minmax optimization. By using the epigraph form of the problem at
hand, we show that the proposed algorithm converges to the optimal solution of
the minmax problem. Moreover, the proposed approach does not require
reconstructing channel coefficients by complex encoding-decoding schemes as
opposed to state-of-the-art approaches. This improves both efficiency and
privacy.

##  I INTRODUCTION

In a traditional federated learning setting (as in [1, 2, 3, 4], and some
references therein), we consider a system of $N$ agents connected to a central
unit, and their objective is to accomplish a machine learning task in a
decentralized manner. In a supervised learning setting, each agent $i$ has its
own local dataset represented by $D_{i}=\\{d^{n}_{i}\\}_{n=1}^{|D_{i}|}$,
where $|D_{i}|$ is the number of data points and $i=1,2,\cdots,N$. The dataset
$D_{i}$ consists of pairs of inputs $u^{n}_{i}$ and labels $z^{n}_{i}$, i.e.,
$d^{n}_{i}=(u^{n}_{i},z^{n}_{i})$, and the objective is to build a global
parametric model that is able to predict the correct labels of the given data
points. To this end, each agent $i$ uses the private local cost function

$g_{i}(\theta)=\frac{1}{|D_{i}|}\sum_{n=1}^{|D_{i}|}\mathcal{L}_{i}(d^{n}_{i},\theta),$
(1)

where $\mathcal{L}_{i}(d^{n}_{i},\theta)$ is the error function representing
the difference between the predicted output of the model with parameter
$\theta$ and the actual label of the given data point $d^{n}_{i}$. If we
define the average of all local cost functions as the global cost function
$g(\theta)$, the objective of the overall system is to solve the constrained
optimization problem

$\theta^{*}=\operatorname*{arg\,min}_{\theta\in\Theta}g(\theta)=\operatorname*{arg\,min}_{\theta\in\Theta}\frac{1}{N}\sum_{i=1}^{N}g_{i}(\theta),$
(2)

where $\Theta\subset\mathbb{R}^{m}$ is a nonempty constraint set. If the
central unit had access to the datasets of all agents, a centralized gradient
descent-based optimization could be employed to address the global learning
task at hand [5]. However, in a federated learning setting, e.g., [3, 6, 7],
each agent has access only to its own local (possibly private) dataset. Having
carried out the local optimization steps, they transmit the updated versions
of the local parameter estimates to the central unit. Subsequently, the
central unit aggregates these local parameter estimates and transmits the
aggregated version to the agents for the next optimization steps.

For large-scale systems, where information exchange and cooperation are vital,
one critical challenge for the averaging-based federated learning algorithms
is heterogeneity [8, 9, 10]. When the data is heterogeneous, i.e., the fact
that agents observe data from different distributions, the parameter vectors
minimizing the local cost functions will in general vary significantly between
different agents, and minimizing the cost function (2) may not be desirable.
Instead, using a worst-case optimization problem may reflect practical
requirements more accurately. Another problem that we encounter in large-scale
networks is that the communication load on the overall system increases with
the number of agents [11, 12, 13, 14]. When multiple agents transmit
information at the same time and in the same frequency band, signals are
affected by the physical phenomenon of interference. Standard communication
protocols111In TDMA (Time Division Multiple Access), agents are assigned
different time slots when they can transmit, whereas in FDMA (Frequency
Division Multiple Access), different frequency bands are allocated to
different users. prevent interference by transmitting signals orthogonally.
However, these techniques are not resource-efficient in the sense that they
increase the need for bandwidth or the number of communication rounds, which
in general leads to a decrease in total throughput and efficiency [15, 16].

In this paper, we present a federated learning algorithm that aims to improve
the performance of the worst-performing agent in the system, thus providing
fairness and robustness against heterogeneity. We leverage a beyond-5G
communication strategy, called Over-the-Air Computation, which is more
efficient as the number of agents grows [16]. Unlike the existing literature
on Over-the-Air computation, e.g, [17, 8], the proposed algorithm can operate
despite the inherently unknown nature of channel coefficients. We do not
assume any knowledge of (nor the capability to reconstruct) channel
coefficients, and therefore we will not need extra pre-processing efforts to
reconstruct the channel, which makes the proposed scheme more time and
resource-efficient. Moreover, since the channel coefficients are completely
unknown, privacy is inherently guaranteed, as discussed in [18].

The remainder of this paper is organized as follows: we present the problem
setup in Section II. In Section III, we introduce the proposed algorithm,
whose convergence analysis is presented in Section IV. A numerical example is
presented in Section V. Concluding remarks are given in Section VI.

##  II PROBLEM SETUP

The set of real numbers is denoted by $\mathbb{R}$, and $\mathbb{R}^{m}$
represents $m$-dimensional Euclidean space. $\mathbb{N}$ and $\mathbb{N}_{0}$
respectively denote the set of natural numbers and the set of nonnegative
integers. Given a finite set $T$, its cardinality is denoted by $|T|$. For a
vector $x\in\mathbb{R}^{m}$, $x^{T}$ denotes its transpose. Euclidean norm of
the vector $x\in\mathbb{R}^{m}$ is denoted by $||x||$. The projection of
$x\in\mathbb{R}^{m}$ onto a nonempty closed convex set
$S\subset\mathbb{R}^{m}$ is denoted by $\mathbf{P}_{S}(x)$, i.e.,
$\mathbf{P}_{S}(x)=\operatorname*{arg\,min}_{s\in S}||s-x||$. Projection is
non-expansive, i.e.,
$||\mathbf{P}_{\Theta}(x)-\mathbf{P}_{\Theta}(y)||\leq||x-y||$ holds for all
$x,y\in\mathbb{R}^{m}$ if $\Theta$ is a nonempty closed convex set (see [19]).
For given $a,b\in\mathbb{R}$, the function $\max\\{a,b\\}$ takes value $a$ if
$a>b$, and $b$ otherwise. The expected value of a random variable $p$ is
denoted by $\mathbb{E}[p]$. Given a logical argument $g_{i}(x)$,
$\mathbf{1}_{\\{g_{i}(x)\\}}$ denotes the function that takes value 1 when
$g_{i}(x)$ is true and 0 when $g_{i}(x)$ is false. For a function
$f:\mathbb{R}^{m}\to(-\infty,\infty\mathbf{]}$, we define
$D_{f}=\\{x\in\mathbb{R}^{m}\big{|}f(x)<\infty\\}$. Then, for a subgradient of
a convex function $f$ with respect to $x$ at $\tilde{x}\in D_{f}$, denoted by
$\partial_{x}f(\tilde{x})$, the inequality $f(\mathbf{\tilde{x}})+\partial
f^{T}(\mathbf{\tilde{x}})(\mathbf{x}-\mathbf{\tilde{x}})\leq f(\mathbf{x})$
holds for all $\mathbf{x}\in D_{f}$.

###  II-A Minmax Reformulation

In a federated learning setting with $N$ agents, where $V=\\{1,2,\cdots,N\\}$
denotes the index set, we are interested in improving the performance of the
worst-performing agent by solving the following optimization problem:

$\displaystyle\min_{\theta\in\Theta}\text{}\max_{i\in V}g_{i}(\theta),$ (3)

We aim to compute a parameter vector estimate minimizing the worst-case loss
observed among all agents, thus providing some form of fairness [20, 21].
However, it is difficult and inefficient to use (3) directly for federated
learning purposes. Instead, we can consider an alternative (epigraph) form:

$\displaystyle\min_{\alpha\in\mathbb{R}}\quad$ $\displaystyle\alpha$ subject
to $\displaystyle g_{i}(\theta)\leq\alpha\qquad\forall\theta\in\Theta,\;i\in
V;$ (4)

where the optimal value $\alpha^{*}$ is assumed to be finite. Moreover,
$g_{i}(\theta^{*})\leq\alpha^{*}$ holds if $\theta^{*}\in\Theta$ is optimal
for (II-A). Let
$\bar{g}_{i}\big{(}(\theta,\alpha)\big{)}=\max\\{g_{i}(\theta)-\alpha,0\\}$
and $p_{i}>0$ respectively denote a penalty for violating the constraint in
(II-A) for $i\in V$ and a weight of this penalty. Then, by following [22] and
[23], one can rewrite (II-A) as

$\displaystyle\min_{\theta\in\Theta,\alpha\in\mathbb{R}}\quad\alpha+\sum_{i=1}^{N}p_{i}\bar{g}_{i}\big{(}(\theta,\alpha)\big{)}.$
(5)

It has been shown in [22] that any solution for (5) is also a solution of
(II-A) if $p_{i}>1$ for all $i\in V$. Hence, (5) can be considered as the
global loss function for the federated learning setting.

###  II-B Over-the-Air Communication Model

In wireless communication systems, the wireless multiple access channel (WMAC)
model has been extensively used to characterize communication between multiple
transmitters and a single receiver over fading channels, e.g., [24, 25].
Throughout this paper, we employ the WMAC-based communication model described
by [15, 26]. Let each agent $i\in V$ simultaneously transmit information
$\mathbf{s}_{i}(k)\in\mathbb{R}^{m}$ to the central unit in the same frequency
band at each time step $k\in\mathbb{N}_{0}$. However, this information is
corrupted by the channel and superimposed by the receiver, i.e., the received
information by the central unit is given by

$\mathbf{s}^{rec}(k)=\sum_{i=1}^{N}\lambda_{i}(k)\mathbf{s}_{i}(k),$ (6)

where the $\lambda_{i}(k)$ are unknown time-varying positive channel
coefficients, i.e., $\lambda_{i}(k)>0$ for all $i=1,2,\cdots,N$.

Note that employing Over-the-Air computation has two main advantages: $(i)$
the channel coefficients $\lambda_{i}(k)$ in (6) are unknown, and it is
impossible to reconstruct $s_{i}(k)$ from $\mathbf{s}^{rec}(k)$, which
inherently provides privacy; $(ii)$ our approach does not require any
knowledge of the channel coefficients, nor do they need to be reconstructed.
This makes our algorithm highly efficient, in particular for large $N$. This
is demonstrated in numerical experiments in Section V.

##  III FEDERATED FAIR OVER-THE-AIR LEARNING (FedFAir) ALGORITHM

Algorithm 1: FedFAir

0: $\theta(0)\in\Theta$, $\alpha(0)\in\mathbb{R}$, and $p_{i}\in\mathbb{R}$

0:

1: for each time step $k\in\mathbb{N}_{0}$ do

2: The central unit computes: $\displaystyle v(k)=\alpha(k)-\frac{\eta(k)}{N}$
(7)

3: The central unit broadcasts $\theta(k)$ and $v(k)$

4: Each agent $i$ updates its local variables:
$\displaystyle\theta_{i}(k)=\theta(k)-\eta(k)p_{i}\partial_{\theta}\bar{g}_{i}\big{(}(\theta(k),v(k))\big{)}$
(8)
$\displaystyle\alpha_{i}(k)=v(k)-\eta(k)p_{i}\partial_{\alpha}\bar{g}_{i}\big{(}(\theta(k),v(k))\big{)}$
(9) $\displaystyle\varrho_{i}(k)=1$ (10)

5: Each agent $i$ transmits $\theta_{i}(k)$, $\alpha_{i}(k)$, and
$\varrho_{i}(k)$

6: The central unit receives: $\displaystyle\theta^{\text{rec}}(k)$
$\displaystyle=\sum_{i=1}^{N}\lambda_{i}(k)\theta_{i}(k)$ (11)
$\displaystyle\alpha^{\text{rec}}(k)$
$\displaystyle=\sum_{i=1}^{N}\lambda_{i}(k)\alpha_{i}(k)$ (12)
$\displaystyle\varrho^{\text{rec}}(k)$
$\displaystyle=\sum_{i=1}^{N}\lambda_{i}(k)\varrho_{i}(k)$ (13)

7: The central unit updates: $\displaystyle\theta(k+1)$
$\displaystyle=\mathbf{P}_{\Theta}\Bigg{(}\frac{\theta^{\text{rec}}(k)}{\varrho^{\text{rec}}(k)}\Bigg{)}$
(14) $\displaystyle\alpha(k+1)$
$\displaystyle=\frac{\alpha^{\text{rec}}(k)}{\varrho^{\text{rec}}(k)}$ (15)

8: end for

The FedFAir algorithm is summarized in Algorithm 1. At the beginning, the
central unit selects $\theta(0)\in\Theta$ and $\alpha(0)\in\mathbb{R}$. Then,
through iterations, the central unit computes (7) and broadcasts $v(k)$ and
$\theta(k)$. Subsequently, each agent computes its own $\alpha_{i}(k)$ and
$\theta_{i}(k)$ by using the local update rules (8) and (9) with the step size
$\eta(k)$, respectively. Afterward, in the first round of agent-to-central
unit communications, all agents transmit simultaneously (and in the same
frequency band) their local values $\alpha_{i}(k)$ to the central unit. In the
second round, each agent transmits simultaneously (and in the same frequency
band) their local parameter vectors $\theta_{i}(k)$. Finally, in the third
round, the constant $\varrho_{i}(k)=1$ is transmitted by all agents again
simultaneously and in the same frequency band. We assume that the delays
between the three rounds are sufficiently small such that the channel
coefficients can be considered constant over the three rounds. According to
the WMAC model, the central unit receives the vector (11) and two scalars
given in (12) and (13) at each time step $k\in\mathbb{N}_{0}$. Finally, the
central unit computes (14) and (15), which can be rewritten in the following
form:

$\displaystyle\theta(k+1)$
$\displaystyle=\mathbf{P}_{\Theta}\Bigg{(}\sum_{i=1}^{N}h_{i}(k)\theta_{i}(k)\Bigg{)},$
(16) $\displaystyle\alpha(k+1)$
$\displaystyle=\sum_{i=1}^{N}h_{i}(k)\alpha_{i}(k),$ (17)

where $\mathbf{P}_{\Theta}$ is the projection operator onto the set $\Theta$,
$h_{i}(k)=\frac{\lambda_{i}(k)}{\sum_{i=1}^{N}\lambda_{i}(k)}$ are the
normalized channel coefficients, and the $\lambda_{i}(k)$ are the unknown
time-varying positive real channel coefficients. By construction, the
$h_{i}(k)$ are also positive, and, for all $k\geq 0$,

$\sum_{i=1}^{N}h_{i}(k)=1.$ (18)

Next, we state our assumptions on individual objective functions and the step
size as follows:

###### Assumption 1

The constraint set $\Theta\subset\mathbb{R}^{m}$ is convex and compact. As a
consequence (see [27, Theorem 2.41, p.40]), $\Theta$ is then also closed and
bounded.

###### Assumption 2

The individual objective functions $g_{i}(\theta)$ are convex over
$\mathbb{R}^{m}$. Consequently, the minimax problem (3) is also convex since
the point-wise maximum of convex functions preserves convexity [19,
Proposition 1.2.4]. In addition, the local cost functions
$\bar{g}_{i}\big{(}(\theta,\alpha)\big{)}$ are also convex but
nondifferentiable, and their sets of subdifferentials are nonempty for all
$x\in\mathbb{R}$, and $i\in V$ [19, Proposition 4.2.1].

###### Assumption 3

The step size $\eta(k)$ in the FedFAir algorithm is chosen to satisfy
$\eta(k)>0$, $\sum_{k=0}^{\infty}\eta(k)=\infty$, and
$\sum_{k=0}^{\infty}\eta^{2}(k)<\infty$.

###### Assumption 4

The unknown time-varying positive real channel coefficients $\lambda_{i}(k)$
($i=1,2,\cdots,N$) are assumed to be independent across time and agents.

We refer here to [28, Ch 2.3, Ch 2.4] and [29, Ch 5.4], thus considering
channel coefficients independent realizations (see [30]).

##  IV CONVERGENCE PROPERTIES

We start with the following lemmas that are essential for the proofs presented
in the paper.

######  Lemma 1 ([31, Thm. 3.4.2])

If a sequence $\\{a(k)\\}$ of real numbers converges to a real number $x$,
then any subsequence $\\{a(k_{t})\\}$ of $\\{a(k)\\}$ also converges to $x$.

######  Lemma 2 ([32, Lem. 11, p.50])

Let $\\{v(k)\\}$, $\\{b(k)\\}$, $\\{u(k)\\}$, and $\\{c(k)\\}$ be nonnegative
sequences of random variables. Suppose that

  * $(i)$

$\sum_{k=0}^{\infty}b(k)<\infty$ and $\sum_{k=0}^{\infty}c(k)<\infty$ hold
almost surely,

  * $(ii)$

For each $k\in\mathbb{N}_{0}$, the following holds almost surely

$\displaystyle\mathbb{E}\big{[}v(k+1)|F_{k}\big{]}\leq\big{(}1+b(k)\big{)}v(k)-u(k)+c(k),$
(19)

where $\mathbb{E}\big{[}v(k+1)|F_{k}\big{]}$ denotes the conditional
expectation for the given $F_{k}=\\{v(t),u(t),c(t),t=0,1,\cdots,k\\}$.

Then, $\\{v(k)\\}$ converges to some $v\geq 0$ and
$\sum_{k=0}^{\infty}u(k)<\infty$ almost surely.

######  Lemma 3 ([33, Prop. 2])

Let $\\{a(k)\\}$ be a nonnegative sequence and $\\{b(k)\\}$ an eventually
nonnegative sequence, i.e., $\exists\tilde{k}\geq 0$ such that $b(k)\geq 0$
$\forall k\geq\tilde{k}$. Let $\sum_{k=0}^{\infty}a(k)=\infty$ and
$\sum_{k=0}^{\infty}a(k)b(k)<\infty$. Then, there exists a subsequence
$\\{b(k_{t})\\}$ of $\\{b(k)\\}$ such that $\lim_{t\to\infty}b(k_{t})=0$.

###### Lemma 4

[23] Let $\alpha^{*}=\min_{\theta\in\Theta}\text{}\max_{i\in V}g_{i}(\theta)$,
$\theta^{*}=\operatorname*{arg\,min}_{\theta\in\Theta}\max_{i\in
V}g_{i}(\theta)$, and $p_{i}>1$ for all $i\in V$. Then, for
$\bar{g}_{i}\big{(}(\theta,\alpha)\big{)}=\max\\{g_{i}(\theta)-\alpha,0\\}$,
we have
$\sum_{i=1}^{N}p_{i}\bar{g}_{i}\big{(}(\theta,\alpha)\big{)}+\alpha\geq\alpha^{*}$
for all $\theta\in\Theta$ and $\alpha\in\mathbb{R}$, where equality holds if
and only if $\theta=\theta^{*}$ and $\alpha=\alpha^{*}$.

We are now ready to present the main result.

###### Theorem 1

Suppose that Assumptions 1, 2, 3, and 4 hold. Let $\theta^{*}\in\Theta$ and
$\alpha^{*}\in\mathbb{R}$ respectively be an optimal solution and the optimal
value for problem (3). If
$p_{i}>\max\Big{(}1,\frac{1}{N\mathbb{E}[h_{i}(k)]}\Big{)}$ for all $i\in V$,
then $\lim_{k\to\infty}\theta(k)=\theta^{*}$ and
$\lim_{k\to\infty}\alpha(k)=\alpha^{*}$ with probability 1.

###### Proof:

We start by introducing
$\beta(k)=\begin{bmatrix}\theta(k)^{T}\;\;\alpha(k)\end{bmatrix}^{T}$,
$y(k)=\begin{bmatrix}\theta(k)^{T}\;\;v(k)\end{bmatrix}^{T}$. Then, for any
$\beta^{*}=\begin{bmatrix}\theta^{*}{}^{T}\;\;\alpha^{*}\end{bmatrix}^{T}\in\Theta\times\mathbb{R}$,
by using (7)-(17), the non-expansive property of the projection
$\mathbf{P}_{\Theta}$, and the fact that
$\theta^{*}=\mathbf{P}_{\Theta}(\theta^{*})$, we have

$\displaystyle||\beta(k+1)-\beta^{*}||^{2}=\Bigg{|}\Bigg{|}\begin{bmatrix}\mathbf{P}_{\Theta}\Big{(}\sum_{i=1}^{N}h_{i}(k)\theta_{i}(k)\Big{)}-\mathbf{P}_{\Theta}(\theta^{*})\\\
\sum_{i=1}^{N}h_{i}(k)\alpha_{i}(k)-\alpha^{*}\end{bmatrix}\Bigg{|}\Bigg{|}^{2}$
$\displaystyle\leq\Bigg{|}\Bigg{|}\begin{bmatrix}\theta(k)-\theta^{*}-\eta(k)\sum_{i=1}^{N}h_{i}(k)p_{i}\partial_{\theta}\bar{g}_{i}\big{(}(\theta(k),v(k))\big{)}\\\
v(k)-\alpha^{*}-\eta(k)\sum_{i=1}^{N}h_{i}(k)p_{i}\partial_{\alpha}\bar{g}_{i}\big{(}(\theta(k),v(k))\big{)}\end{bmatrix}\Bigg{|}\Bigg{|}^{2}$
$\displaystyle=\Big{|}\Big{|}y(k)-\beta^{*}-\eta(k)\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}_{i}\big{(}y(k)\big{)}\Big{)}\Big{|}\Big{|}^{2},$
(20)

where
$\partial\bar{g}_{i}\big{(}y(k)\big{)}=\begin{bmatrix}\partial_{\theta}g_{i}\big{(}\theta(k)\big{)}&-1\end{bmatrix}^{T}\mathbf{1}_{\\{g_{i}(\theta)\geq\alpha\\}}.$
We can further expand (IV) as

$\displaystyle||\beta(k+1)-\beta^{*}||^{2}$
$\displaystyle\leq\bigg{|}\bigg{|}y(k)-\eta(k)\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}_{i}\big{(}y(k)\big{)}-\beta^{*}\bigg{|}\bigg{|}^{2}$
$\displaystyle=\big{|}\big{|}y(k)-\beta^{*}\big{|}\big{|}^{2}$
$\displaystyle\quad-2\eta(k)\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}^{T}_{i}\big{(}y(k)\big{)}\big{(}y(k)-\beta^{*}\big{)}$
$\displaystyle\qquad\qquad+\Big{|}\Big{|}\eta(k)\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}_{i}\big{(}y(k)\big{)}\Big{|}\Big{|}^{2}.$
(21)

For the first term on the right-hand side of (IV), we have

$\displaystyle\big{|}\big{|}y(k)-\beta^{*}\big{|}\big{|}^{2}$
$\displaystyle=\Bigg{|}\Bigg{|}\begin{bmatrix}\theta(k)-\theta^{*}\\\
\alpha(k)-\alpha^{*}\end{bmatrix}-\begin{bmatrix}0\\\
\frac{\eta(k)}{N}\end{bmatrix}\Bigg{|}\Bigg{|}^{2}$
$\displaystyle=\big{|}\big{|}\beta(k)-\beta^{*}\big{|}\big{|}^{2}-\frac{2\eta(k)}{N}\big{(}\alpha(k)-\alpha^{*}\big{)}+\frac{\eta^{2}(k)}{N^{2}}.$
(22)

which follows from (7). Note that the boundedness of the constraint set
$\Theta$ implies $\exists L_{\Theta}>0$ such that
$\big{|}\big{|}\partial\bar{g}_{i}\big{(}y(k)\big{)}\big{|}\big{|}\leq
L_{\Theta}$, which together with (18), the convexity of the function
$||\cdot||^{2}$, and the fact that $1<p_{i}\leq p_{max}$ with
$p_{max}=\max_{i}p_{i}$ ($i\in V$) can be used to find an upper-bound for the
last term on the right-hand side of (IV) as

$\displaystyle\Big{|}\Big{|}\eta(k)\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}_{i}\big{(}y(k)\big{)}\Big{|}\Big{|}^{2}$
$\displaystyle=\eta^{2}(k)\Big{|}\Big{|}\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}_{i}\big{(}y(k)\big{)}\Big{|}\Big{|}^{2}$
$\displaystyle\leq\eta^{2}(k)\sum_{i=1}^{N}h_{i}(k)p_{i}^{2}\Big{|}\Big{|}\partial\bar{g}_{i}\big{(}y(k)\big{)}\Big{|}\Big{|}^{2}$
$\displaystyle\leq\eta^{2}(k)M_{1}.$ (23)

where $M_{1}=p^{2}_{max}L_{\Theta}^{2}$. Let $F_{k}$ represent the past
iterates of $\alpha(k)$ and $\theta(k)$, i.e.,
$F_{k}=\\{\alpha(t),\>\theta(t),t=0,1,\cdots,k\\}$ for $k\in\mathbb{N}_{0}$.
Subsequently, by using (IV), (IV), and taking the expectation conditioned on
$F_{k}$ of both sides of (IV) together with the linearity of the expectation,
we obtain

$\displaystyle\mathbb{E}\big{[}||\beta(k+1)$
$\displaystyle-\beta^{*}||^{2}|F_{k}\big{]}\leq\big{|}\big{|}\beta(k)-\beta^{*}\big{|}\big{|}^{2}-\frac{2\eta(k)}{N}(\alpha(k)-\alpha^{*})$
$\displaystyle-2\eta(k)\mathbb{E}\big{[}\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}^{T}_{i}\big{(}y(k)\big{)}\big{(}y(k)-\beta^{*}\big{)}|F_{k}\big{]}$
$\displaystyle\qquad\qquad\qquad+\eta^{2}(k)M_{2},$ (24)

where $M_{2}=M_{1}+\frac{1}{N^{2}}$. Note that due to Assumption 4, the
statistics of $h_{i}(k)$ ($i=1,2,\cdots,N$) are independent of $h_{i}(t)$ for
$t<k$, which also implies that $y(k)$ and $h_{i}(k)$ are statistically
independent at time $k$ since the statistics of $y(k)$ are dependent only on
$h_{i}(t)$ for $t<k$ and $i=1,2,\cdots,N$. Hence,
$\mathbb{E}\big{[}h_{i}(k)|F_{k}\big{]}=\mathbb{E}\big{[}h_{i}(k)\big{]}$
holds for all $k\in\mathbb{N}_{0}$. Then, by using the linearity of the
expectation again, we can write the third term on the right-hand side of (IV)
as

$\displaystyle-2\eta(k)\mathbb{E}\big{[}\sum_{i=1}^{N}h_{i}(k)p_{i}\partial\bar{g}^{T}_{i}\big{(}y(k)\big{)}\big{(}y(k)-\beta^{*}\big{)}|F_{k}\big{]}$
$\displaystyle=-2\eta(k)\sum_{i=1}^{N}\mathbb{E}\big{[}h_{i}(k)p_{i}\partial\bar{g}^{T}_{i}\big{(}y(k)\big{)}\big{(}y(k)-\beta^{*}\big{)}|F_{k}\big{]}$
$\displaystyle=-2\eta(k)\sum_{i=1}^{N}\mathbb{E}\big{[}h_{i}(k)\big{]}p_{i}\partial\bar{g}^{T}_{i}\big{(}y(k)\big{)}\big{(}y(k)-\beta^{*}\big{)}.$
(25)

Moreover, by Assumption 2 (convexity of $\bar{g}_{i}(\cdot)$), we have

$\displaystyle\sum_{i=1}^{N}p_{i}\partial_{y}\bar{g}^{T}_{i}\big{(}y(k)\big{)}\big{(}y(k)-\beta^{*}\big{)}$
$\displaystyle\geq\sum_{i=1}^{N}p_{i}\Big{(}\bar{g}_{i}\big{(}y(k)\big{)}-\bar{g}_{i}\big{(}\beta^{*}\big{)}\Big{)}$
$\displaystyle=\sum_{i=1}^{N}p_{i}\bar{g}_{i}\big{(}y(k)\big{)},$ (26)

which follows from the fact that for any
$\beta^{*}=\begin{bmatrix}\theta^{*}{}^{T}\;\;\alpha^{*}\end{bmatrix}^{T}\in\Theta\times\mathbb{R}$,
we have $g_{i}(\theta^{*})-\alpha^{*}\leq 0$, and therefore
$\bar{g}_{i}(v^{*})=\max\\{g_{i}(\theta^{*})-\alpha^{*},0\\}=0$ for all $i\in
V$ and $k\in\mathbb{N}_{0}$. Thus, by using (IV), (IV) can be written as

$\displaystyle-2\eta(k)\sum_{i=1}^{N}\mathbb{E}\big{[}h_{i}(k)\big{]}p_{i}\partial\bar{g}_{i}\big{(}y(k)\big{)}\big{(}y(k)-\beta^{*}\big{)}$
$\displaystyle\leq-2\eta(k)\sum_{i=1}^{N}\mathbb{E}\big{[}h_{i}(k)\big{]}p_{i}\bar{g}_{i}\big{(}y(k)\big{)},$
(27)

which can then be used to rewrite (IV) as

$\displaystyle\mathbb{E}\big{[}||\beta(k+1)-\beta^{*}||^{2}|F_{k}\big{]}$
$\displaystyle\leq\big{|}\big{|}\beta(k)-\beta^{*}\big{|}\big{|}^{2}+\eta^{2}(k)M_{2}$
$\displaystyle-\frac{2\eta(k)}{N}\Big{(}\alpha(k)-\alpha^{*}+N\sum_{i=1}^{N}\bar{p}_{i}\bar{g}_{i}\big{(}y(k)\big{)}\Big{)}$
(28)

where $\bar{p}_{i}=\mathbb{E}\big{[}h_{i}(k)\big{]}p_{i}$. We can add and
subtract the term
$2\eta(k)\big{(}\sum_{i=1}^{N}\bar{p}_{i}\bar{g}_{i}\big{(}\beta(k)\big{)}\big{)}$
from the right hand side of (IV) to get

$\displaystyle\mathbb{E}\big{[}||\beta(k+1)-\beta^{*}||^{2}|F_{k}\big{]}$
$\displaystyle\leq\big{|}\big{|}\beta(k)-\beta^{*}\big{|}\big{|}^{2}+\eta^{2}(k)M_{2}$
$\displaystyle-\frac{2\eta(k)}{N}\Big{(}\alpha(k)-\alpha^{*}+N\sum_{i=1}^{N}\bar{p}_{i}\bar{g}_{i}\big{(}\beta(k)\big{)}\Big{)}$
$\displaystyle+2\eta(k)\bar{p}_{max}\sum_{i=1}^{N}\big{|}\bar{g}_{i}\big{(}\beta(k)\big{)}-\bar{g}_{i}\big{(}y(k)\big{)}\big{|},$
(29)

which follows from the fact that

$\sum_{i=1}^{N}\bar{p}_{i}\bar{g}_{i}\big{(}\beta(k)\big{)}-\sum_{i=1}^{N}\bar{p}_{i}\bar{g}_{i}\big{(}y(k)\big{)}\leq\bar{p}_{max}\sum_{i=1}^{N}\big{|}\bar{g}_{i}\big{(}\beta(k)\big{)}-\bar{g}_{i}\big{(}y(k)\big{)}\big{|}$

where $\bar{p}_{max}=\max_{i}\bar{p}_{i}$ ($i\in V$). By using (7) and the
relation $|\text{max}\\{x_{1},0\\}-\text{max}\\{x_{2},0\\}|\leq|x_{1}-x_{2}|$
for scalars $x_{1}$ and $x_{2}$, one can obtain

$\displaystyle|\bar{g}_{i}\big{(}\beta(k)\big{)}-\bar{g}_{i}\big{(}y(k)\big{)}|$
$\displaystyle\leq|g_{i}\big{(}\theta(k)\big{)}-\alpha(k)-g_{i}\big{(}\theta(k)\big{)}+v(k)|$
$\displaystyle=\frac{\eta(k)}{N},$ (30)

which can then be used to obtain

$\displaystyle\mathbb{E}\big{[}||\beta(k+1)-\beta^{*}||^{2}|F_{k}\big{]}$
$\displaystyle\leq\big{|}\big{|}\beta(k)-\beta^{*}\big{|}\big{|}^{2}$
$\displaystyle-\frac{2\eta(k)}{N}\Big{(}\alpha(k)-\alpha^{*}+\sum_{i=1}^{N}w_{i}\bar{g}_{i}\big{(}\beta(k)\big{)}\Big{)}$
$\displaystyle\qquad\qquad\qquad+\eta^{2}(k)M_{3}.$ (31)

where $w_{i}=N\bar{p}_{i}$ and $M_{3}=M_{2}+2p_{max}$. Suppose that
$p_{i}>\max\Big{(}1,\frac{1}{N\mathbb{E}[h_{i}(k)]}\Big{)}$. Then,

$\displaystyle w_{i}=N\bar{p}_{i}=N\mathbb{E}\big{[}h_{i}(k)\big{]}p_{i}>1.$
(32)

Note that since $\alpha^{*}=\min_{\theta\in\Theta}\text{}\max_{i\in
V}g_{i}(\theta)$, by Lemma 4, we have

$\displaystyle\alpha(k)-\alpha^{*}+\sum_{i=1}^{N}w_{i}\bar{g}_{i}\big{(}\beta(k)\big{)}\geq
0$ (33)

for all $k\in\mathbb{N}_{0}$. Moreover, by Assumption 3, we have
$\sum_{k=0}^{\infty}\eta^{2}(k)<\infty$, which together with (IV) and Lemma 2
give

$\displaystyle\lim_{k\to\infty}\big{|}\big{|}\beta(k)-\beta^{*}\big{|}\big{|}^{2}=\vartheta\geq
0,$ (34)
$\displaystyle\sum_{k=0}^{\infty}\eta(k)\Big{(}\alpha(k)-\alpha^{*}+\sum_{i=1}^{N}w_{i}\bar{g}_{i}\big{(}\beta(k)\big{)}\Big{)}<\infty,$
(35)

for any
$\beta^{*}=\begin{bmatrix}\theta^{*}{}^{T}\;\;\alpha^{*}\end{bmatrix}^{T}\in\Theta\times\mathbb{R}$
and $\alpha^{*}\in\mathbb{R}$ with probability 1. Additionally,
$\sum_{k=0}^{\infty}\eta(k)=\infty$ also holds by Assumption 3, which together
with Lemma 3 imply that there exists a subsequence such that the following
holds with probability 1,

$\displaystyle\lim_{l\to\infty}\Big{(}\alpha(k_{l})-\alpha^{*}+\sum_{i=1}^{N}w_{i}\bar{g}_{i}\big{(}\beta(k_{l})\big{)}\Big{)}=0,$
(36)

which also implies that along a further subsequence, we have limit points
$\lim_{l\to\infty}\alpha(k_{l})=\bar{\alpha}$ and
$\lim_{l\to\infty}\beta(k_{l})=\bar{\beta}$ with probability 1, which satisfy

$\displaystyle\bar{\alpha}-\alpha^{*}+\sum_{i=1}^{N}w_{i}\bar{g}_{i}\big{(}\bar{\beta}\big{)}=0.$
(37)

Hence, by Lemma 4 and the fact that $w_{i}>1$ for all $i\in V$, it follows
that $\bar{\alpha}=\alpha^{*}$ and $\bar{\theta}=\theta^{*}$ are optimal for
the minmax problem (3) with probability 1. This implies that
$\lim_{l\to\infty}\big{|}\big{|}\beta(k_{l})-\beta^{*}\big{|}\big{|}^{2}=0$
with probability 1. Hence, by Lemma 1, we have $\vartheta=0$ in (34) with
probability 1 and that concludes the proof. ∎

##  V NUMERICAL EXAMPLE

Figure 1: Comparison of the performances FedFAir and FedAVG algorithms on
unseen data during training in terms of their accuracy.

We consider a federated logistic regression problem, where each agent has its
own private data. The objective is to collaboratively build a global model
that can carry out a binary classification task. In this setting, each agent
has 2 different classes of data, labeled by 0 or 1. We represent the dataset
of the $i$-th agent by $D_{i}=\\{d^{n}_{i}\\}_{n=1}^{|D_{i}|}$, where
$d^{n}_{i}=(u^{n}_{i},z^{n}_{i})\in\mathbb{R}^{m}\times\\{0,1\\}$. The
objective is to find a separation rule so that agents can identify the correct
classes of some unseen data from different classes. To this end, the following
convex loss function is used by each agent:

$\displaystyle g_{i}(\theta,d_{i})=-\frac{1}{|D_{i}|}\bigg{(}$
$\displaystyle\sum_{n=1}^{|D_{i}|}z^{n}_{i}\log\big{(}S(\theta^{T}u^{n}_{i})\Big{)}$
$\displaystyle+(1-z^{n}_{i})\log\big{(}1-S(\theta^{T}u^{n}_{i})\Big{)}\bigg{)}$
(38)

where $S(x)=\frac{1}{1+e^{-x}}$ and $z^{n}_{i}$ is the local estimate of the
$i$-th agent. The step size is chosen as $\eta(k)=\frac{0.1}{(k+1)^{0.6}}$.

To demonstrate the fairness and robustness of the FedFAir algorithm, we
consider a system of $12$ agents, each with a different number of training
samples and with noise injected into the data available to each agent. Note
that the noise injected into the datasets of different agents is sampled from
different distributions. The parameter vector is of dimension $4$, i.e.,
$\theta\in\mathbb{R}^{4}$, and $p_{i}>1$ is chosen for all agents
$i=1,2,\cdots,12$. Additionally, the constraint set is given by
$\Theta=\\{\theta\in\mathbb{R}^{4}|\hskip 2.84526pt||\theta||\leq 10\\}$. In
order to monitor the performance of the system, we randomly sample some
previously unseen test data at every iteration, and then we measure
performance of the global model on this test data by computing its
classification accuracy during training. As it can be seen from Fig. 1, the
FedFAir algorithm achieves around $90\%$ accuracy after approximately 5000
iterations.

Notice that the FedAVG algorithm achieves approximately $70-75\%$ of
classification accuracy after 100000 iterations as it can also be seen in Fig.
1. However, due to the heterogeneity in distribution of the data, we observe
that the FedAVG algorithm cannot properly identify the samples of data with
labels 0. This can be seen from the confusion matrices in Fig. 2, where the
FedAVG model cannot successfully recognize the data labeled as 0, whereas the
FedFAir algorithm performs much better by recognizing a large percentage of
data, both labelled 0 and 1.

Additionally, we compare the FedFAir algorithm and the standard FedAVG [1]
algorithm in terms of communication efficiency. For the latter, the TDMA
scheme is used for communication between agents and the central unit. In this
case, individual time slots are allocated for each agent to transmit its
parameter vector at each communication round. After receiving parameter
vectors, the central unit computes the average of them and sends it back to
the agents. Since we consider a system with $N=12$ agents, it takes $N=12$
time slots per communication round for each agent to transmit its updated
parameter vector while only $3$ are needed for the FedFAir algorithm (see
(13)), independent of the value of $N$. This makes the execution of one
iteration of the FedFAir algorithm $N/3=4$ times faster than the execution of
an iteration of the FedAVG algorithm.

(a) Confusion Matrix for FedAVG

(b) Confusion Matrix for FedFAir

Figure 2: Comparison of Confusion Matrices

##  VI CONCLUSION

In this paper, we have introduced the FedFAir algorithm which uses Over-the-
Air Computation to carry out efficient decentralized learning while providing
fairness and improved performance. We have shown that the FedFAir algorithm
converges to an optimal solution of the minimax problem. Furthermore, we have
also illustrated our theoretical findings with a numerical example.

Future research will include the development of resilient federated learning
algorithms when there are malicious agents in the system.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [2] V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar, “Federated multi-task learning,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [3] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. Kiddon, J. Konečnỳ, S. Mazzocchi, B. McMahan _et al._ , “Towards federated learning at scale: System design,” _Proceedings of Machine Learning and Systems_ , vol. 1, pp. 374–388, 2019.
  * [4] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [5] A. Nedic, “Distributed gradient methods for convex machine learning problems in networks: Distributed optimization,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 92–101, 2020.
  * [6] V. P. Chellapandi, A. Upadhyay, A. Hashemi, and S. H. Żak, “On the convergence of decentralized federated learning under imperfect information sharing,” _IEEE Control Systems Letters_ , 2023.
  * [7] T. Omori and K. Kashima, “Combinatorial optimization approach to client scheduling for federated learning,” _IEEE Control Systems Letters_ , 2023\.
  * [8] T. Sery, N. Shlezinger, K. Cohen, and Y. C. Eldar, “Over-the-air federated learning from heterogeneous data,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 3796–3811, 2021.
  * [9] T. Gafni, N. Shlezinger, K. Cohen, Y. C. Eldar, and H. V. Poor, “Federated learning: A signal processing perspective,” _IEEE Signal Processing Magazine_ , vol. 39, no. 3, pp. 14–41, 2022.
  * [10] M. Ye, X. Fang, B. Du, P. C. Yuen, and D. Tao, “Heterogeneous federated learning: State-of-the-art and research challenges,” _ACM Computing Surveys_ , vol. 56, no. 3, pp. 1–44, 2023.
  * [11] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv preprint arXiv:1610.05492_ , 2016.
  * [12] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 50–60, 2020.
  * [13] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, 2021\.
  * [14] H. Y. Oksuz, F. Molinari, H. Sprekeler, and J. Raisch, “Federated learning in wireless networks via over-the-air computations,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_ , 2023, pp. 4379–4386.
  * [15] F. Molinari, N. Agrawal, S. Stańczak, and J. Raisch, “Max-consensus over fading wireless channels,” _IEEE Transactions on Control of Network Systems_ , vol. 8, no. 2, pp. 791–802, 2021.
  * [16] M. Frey, I. Bjelaković, and S. Stańczak, “Over-the-air computation in correlated channels,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 5739–5755, 2021.
  * [17] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning via over-the-air computation,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 3, pp. 2022–2035, 2020.
  * [18] F. Molinari and J. Raisch, “Exploiting wireless interference for distributively solving linear equations,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 2999–3006, 2020.
  * [19] D. Bertsekas, A. Nedic, and A. Ozdaglar, _Convex analysis and optimization_. Athena Scientific, 2003, vol. 1.
  * [20] M. Mohri, G. Sivek, and A. T. Suresh, “Agnostic federated learning,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 4615–4625.
  * [21] Z. Hu, K. Shaloudegi, G. Zhang, and Y. Yu, “Federated learning meets multi-objective optimization,” _IEEE Transactions on Network Science and Engineering_ , vol. 9, no. 4, pp. 2039–2051, 2022.
  * [22] D. P. Bertsekas, “Necessary and sufficient conditions for a penalty method to be exact,” _Mathematical programming_ , vol. 9, no. 1, pp. 87–99, 1975.
  * [23] K. Srivastava, A. Nedić, and D. Stipanović, “Distributed min-max optimization in networks,” in _2011 17th International Conference on Digital Signal Processing (DSP)_. IEEE, 2011, pp. 1–8.
  * [24] R. Ahlswede, “Multi-way communication channels,” in _Second International Symposium on Information Theory: Tsahkadsor, Armenia, USSR, Sept. 2-8, 1971_ , 1973.
  * [25] A. Giridhar and P. Kumar, “Toward a theory of in-network computation in wireless sensor networks,” _IEEE Communications Magazine_ , vol. 44, no. 4, pp. 98–107, apr 2006.
  * [26] F. Molinari, N. Agrawal, S. Stańczak, and J. Raisch, “Over-the-air max-consensus in clustered networks adopting half-duplex communication technology,” _IEEE Transactions on Control of Network Systems_ , 2022.
  * [27] W. Rudin _et al._ , _Principles of mathematical analysis_. McGraw-hill New York, 1976, vol. 3.
  * [28] D. Tse and P. Viswanath, _Fundamentals of Wireless Communication_. Cambridge University Press, 2012.
  * [29] A. F. Molisch, _Wireless communications_. John Wiley & Sons, 2012.
  * [30] B. Sklar, “Rayleigh fading channels in mobile digital communication systems. i. characterization,” _IEEE Communications magazine_ , vol. 35, no. 7, pp. 90–100, 1997.
  * [31] R. G. Bartle and D. R. Sherbert, _Introduction to real analysis_. Wiley New York, 2000.
  * [32] B. T. Polyak, _Introduction to optimization. optimization software_. Inc., Publications Division, New York, 1987.
  * [33] Y. I. Alber, A. N. Iusem, and M. V. Solodov, “On the projected subgradient method for nonsmooth convex optimization in a hilbert space,” _Mathematical Programming_ , vol. 81, pp. 23–35, 1998.


# Query-specific Variable Depth Pooling via Query Performance Prediction
towards Reducing Relevance Assessment Effort

Debasis Ganguly  University of GlasgowGlasgowUnited Kingdom
<EMAIL_ADDRESS>and  Emine Yilmaz  University College
LondonLondonUnited Kingdom<EMAIL_ADDRESS>
(2023)

###### Abstract.

Due to the massive size of test collections, a standard practice in IR
evaluation is to construct a ‘pool’ of candidate relevant documents comprised
of the top-$k$ documents retrieved by a wide range of different retrieval
systems - a process called depth-$k$ pooling. A standard practice is to set
the depth ($k$) to a constant value for each query constituting the benchmark
set. However, in this paper we argue that the annotation effort can be
substantially reduced if the depth of the pool is made a variable quantity for
each query, the rationale being that the number of documents relevant to the
information need can widely vary across queries. Our hypothesis is that a
lower depth for the former class of queries and a higher depth for the latter
can potentially reduce the annotation effort without a significant change in
retrieval effectiveness evaluation. We make use of standard query performance
prediction (QPP) techniques to estimate the number of potentially relevant
documents for each query, which is then used to determine the depth of the
pool. Our experiments conducted on standard test collections demonstrate that
this proposed method of employing query-specific variable depths is able to
adequately reflect the relative effectiveness of IR systems with a
substantially smaller annotation effort.

IR Model Evaluation, Depth Pooling, Query Performance Prediction

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
46th International ACM SIGIR Conference on Research and Development in
Information Retrieval; July 23–27, 2023; Taipei, Taiwan††booktitle:
Proceedings of the 46th International ACM SIGIR Conference on Research and
Development in Information Retrieval (SIGIR ’23), July 23–27, 2023, Taipei,
Taiwan††price: 15.00††doi: 10.1145/3539618.3592046††isbn:
978-1-4503-9408-6/23/07††ccs: Information systems Query intent††ccs:
Information systems Information retrieval query processing

##  1\. Introduction

The most widely used approach used in evaluating quality of retrieval systems
is based on constructing test collections via the Cranfield paradigm
(Cleverdon, 1967), which assumes that relevance judgments for each query are
complete. However, due to the cost of obtaining relevance judgments, it is
often impractical to obtain relevance judgments for all documents in a
collection.

A commonly used approach to reduce the need for extensive judging effort in
test collection construction is depth-$k$ pooling, which is based on
constructing a pool of documents that consists of the top-$k$ documents
retrieved by various systems and then obtaining relevance judgments for these
documents, assuming that the rest of the documents are non-relevant. Most
existing test collections, such as the ones constructed by TREC are
constructed using depth-100 pools, i.e., using a depth of $k=100$ (Voorhees
and Harman, 2000). However, depth-100 pools still tend to be quite large and
hence significant research has been devoted to reducing the number of
judgments needed in constructing test collections (Yilmaz et al., 2008;
Carterette et al., 2006). In order to reduce the pool depth, some recent test
collections are instead constructed using much shallower depths, such as
depth-10 pools used by the recent Deep Learning Track collections (Craswell et
al., 2020b).

Most previous work assumes that a constant depth ($k$) should be used across
all the queries in the test collection. However, some queries may contain more
relevant documents than the others, and using the same depth across all
queries could lead to wasting a significant proportion of annotation budget on
those queries where fewer judgments could have been sufficient (Yilmaz et al.,
2008, 2014).

Some previous work based on active learning proposed approaches employed
deeper depths for systems that are more likely to retrieve a higher number of
relevant documents (Sanderson, 2010; Losada et al., 2016; Cormack et al.,
1998) \- a process which often leads to _different rank cutoffs for different
systems_. Optimising the resultlist presentation to search system users
motivated a similar thread of work that involves chopping off a ranked list of
documents at different cut-off points based on the statistics of their score
distributions (Arampatzis et al., 2009; Lien et al., 2019). More recently,
supervised learning via neural networks has been applied to address this
problem (Bahri et al., 2020).

While previous work has investigated cutting off ranked lists at variable
depths to reduce the information finding effort of search engine users
(Sanderson, 2010; Losada et al., 2016; Cormack et al., 1998; Arampatzis et
al., 2009; Bahri et al., 2020), we, in contrast, use the concept of variable
depths for reducing the assessment effort. The rationale behind the idea is
that some queries have a smaller number of documents in the collection that
are relevant to their corresponding information needs, whereas for some other
queries this number may be substantially larger. Our hypothesis is that a
lower depth for the former class of queries and a higher depth for the latter
can potentially reduce the annotation effort without a significant change in
the relative evaluation of different retrieval systems.

In particular, to estimate the number of potentially relevant documents for
each query we make use of a standard query performance prediction (QPP) based
approach (specifically, NQC (Shtok et al., 2012) in this paper). This number
of relevant documents estimated for a query in the top-documents retrieved by
an IR system is then used to determine the number of documents that contribute
to the pool for that particular query and IR system combination.

##  2\. Proposed Methodology

###  2.1. A Review of QPP

QPP approaches can broadly be categorized into the pre-retrieval and post-
retrieval types. A pre-retrieval estimator uses aggregated collection-level
statistics (e.g., maximum or average of the inverse document frequencies of
the query terms) as an estimated performance measure of a query (Hauff et al.,
2008; He and Ounis, 2004; Zhao et al., 2008). A post-retrieval estimator, on
the other hand, makes use of the information from the set of top-retrieved
documents to estimate the quality of the retrieved list. In general, the QPP
score for a post-retrieval estimator $\phi$ is a function of the query and the
set of top-retrieved documents, i.e.,

(1) $\phi:Q\times M^{(k)}(Q)\mapsto\mathbb{R},$

where $M^{(k)}(Q)$ denotes the set of top-$k$ documents retrieved for query
$Q$ with a model $M$. From hereon, $M^{(k)}(Q)$ is abbreviated as $M^{(k)}$,
the query being understood from the context.

Various evidences extracted from the top-retrieved documents have been shown
to be useful for different post-retrieval QPP estimation methods, such as the
KL divergence between the language model of the top-retrieved documents and
the collection model as in Clarity (Cronen-Townsend et al., 2002), the
aggregated values of the information gains of each top-retrieved document with
respect to the collection as in WIG (Weighted Information Gain) (Zhou and
Croft, 2007), the skewness of the retrieval status values (RSVs) measured with
variance as in NQC (Normalized Query Commitment) (Shtok et al., 2012), ideas
based on the clustering hypothesis for a pairwise document similarity matrix
(Diaz, 2007), topology of the embedded word vectors (Roy et al., 2016) and
even supervised approaches using neural networks (Datta et al., 2022a, c).

In our work, as an unsupervised QPP approach we employ NQC (Normalized Query
Commitment) (Shtok et al., 2012), which is a simple yet effective post-
retrieval QPP method (Zendel et al., 2019; Datta et al., 2022b) (we leave the
investigation with other QPP approaches as future work). NQC predicts the
retrieval effectiveness of a query using the variance of the document scores,
the rationale being that a query with a well-defined information need is
likely to lead to a more non-uniform (heavy-tailed) distribution of the RSVs.
Formally speaking, the generic $\phi$ function of Equation 1 takes the form

(2)
$\phi_{\mathrm{NQC}}(Q,M^{(k)})\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\frac{\sqrt{\frac{1}{k}\sum_{i=1}^{k}(P(D_{i}|Q)-\bar{P}(D|Q))^{2}}}{P(Q|C)},$

where $P(D_{i}|Q)$ denotes the RSV of the document $D_{i}$ to $Q$,
$\bar{P}(D|Q)$ denotes the mean of the RSVs, and $P(Q|C)$ denotes the
similarity of $Q$ to the collection, which is computed by aggregating
collection statistics (e.g., idf) over the query terms.

Although for our experiments we specifically use the NQC method, our proposed
method of variable depth pooling strategy (to be discussed in the next
section) is a general one allowing application of any other QPP model as a
concrete realisation of $\phi$ (Equation 2).

###  2.2. Depth Estimation using QPP

Given a set of $n$ queries $\mathcal{Q}=\\{Q_{1},\ldots,Q_{n}\\}$, a standard
depth-$k$ pooling process first involves employing a number of different
retrieval systems (models), say $\mathcal{M}=\\{M_{1},\ldots,M_{p}\\}$ to
construct a _pool_ of the top-$k$ documents retrieved with each $M_{i}$
($i=1,\ldots,p$). Formally speaking, this pool of depth $k$,
$\mathcal{P}_{k}(Q)$ for query $Q\in\mathcal{Q}$ is constructed as

(3) $\mathcal{P}_{k}(Q)=\cup_{i=1}^{p}M^{(k)}_{i},$

where $M^{(k)}_{i}$ denotes the top-$k$ documents retrieved with model
$M_{i}$.

The key idea now is to make this depth $k$ a function of $Q$ itself rather
than it being a constant across all queries. We propose to make this integer-
valued depth of a query a function of the generic form of the real-valued QPP
estimate $\phi$ (which depends on $M^{(k)}_{i}$) as shown in Equation 1, and
denote this integer-valued depth function as
$\zeta(Q,M_{i})\in\mathbb{Z}^{+}$.

One important point to note is that we make the variable depth a function of
the query and of the retrieval model. Specifically, after computing the depth
$\zeta(Q,M_{i})$ for a ‘query and system’ combination $(Q,M_{i})$, we use this
depth to determine the number of documents top documents from
$M^{(\zeta(Q,M_{i}))}_{i}$ to add to the pool. In other words, we obtain a
more generic version of Equation 3 as

(4) $\mathcal{P}_{\zeta(Q)}=\cup_{i=1}^{p}M^{(\zeta(Q,M_{i}))}_{i}.$

We now explore two different ways by which this variable depth of a query may
depend on the QPP estimator. Each of these two choices of $\zeta(Q,M)$ has its
own set of supporting arguments; more details follow.

####  2.2.1. Inverse Linear Dependence

The first choice for $\zeta(Q,M)$ is a linearly inverse proportional function,
the intuition for which is that the higher the value of the estimate - the
higher is the likelihood of the ranked list (as retrieved by $M$) to contain a
higher proportion of relevant documents towards the top ranks. This, in turn,
means that a smaller depth for such a query is likely to be adequate to
include an adequate set of potentially relevant documents in the constructed
pool for a robust evaluation of IR systems.

On the other hand, a relatively low value of the QPP estimate for a query
potentially indicates that more documents should perhaps be included in the
pool by employing a higher depth value for that query. Formally speaking,
using the generic notation of the QPP function of Equation 1, the depth of a
query $Q$ is then

(5)
$\zeta(Q,M_{i})=d_{min}+\lfloor(1-\phi(Q,M^{(d_{max})}_{i}))(d_{max}-d_{min})\rfloor,$

where the parameters $d_{min}$ denotes the minimum depth, and $d_{max}$
denotes the maximum depth ($d_{min},d_{max}\in\mathbb{Z}^{+}$, i.e., they both
are positive integers).

Normalized values of the QPP $\phi(Q,M^{(d_{max})}_{i})$ estimates ensure that
the depth of a query is an integer between the integer bounds $d_{min}$ and
$d_{max}$. Note that, in particular, for computing the QPP estimates
themselves we use $k=d_{max}$ (the maximum depth), and we apply max-
normalization for the QPP estimates.

####  2.2.2. Linear Dependence

The argument for this choice of $\zeta(Q,M)$ is that a higher value of
$\phi(Q,M^{(k)})$ is likely to indicate that a higher number of potentially
relevant documents for $Q$ exists in the collection. This, in turn, means that
one may consider probing at higher depths to collect those candidates for
assessment for a more comprehensive evaluation of IR systems. Similarly, a
smaller estimate for $\phi(Q,M^{(d_{max})})$ means that it is not worthwhile
to use a high depth for $Q$ because the candidates collected from lower down
the ranked lists of such IR systems may end up in the ground-truth set
indicating wasted manual effort. Formally,

(6)
$\zeta(Q,M_{i})=d_{min}+\lfloor\phi(Q,M^{(d_{max})}_{i})(d_{max}-d_{min})\rfloor,$

where the only difference of Equation 6 with that of 5 is that in the former
an increase in the $\phi(Q,M^{(d_{max})}_{i})$ increases the depth to a higher
integer value within the bounds $[d_{min},d_{max}]$ instead of decreasing it
as is the case for the latter.

##  3\. Evaluation

###  3.1. Experiment Details

####  3.1.1. Research Questions

We conduct experiments to investigate the following two research questions.

  * •

RQ-1: Is an NQC-based variable depth pooling strategy beneficial to reduce
annotation effort without causing significant changes in the relative system
ranks?

  * •

RQ-2: Which depth selection function (linear or inverse linear - Equations 5
or 6) turns out to be the more effective of the two?

####  3.1.2. Datasets

Our retrieval experiments are conducted on two standard datasets used for the
ad-hoc IR task, namely the TREC Robust (Voorhees and Harman, 2000) and the
TREC DL datasets (Nguyen et al., 2016). While the former is comprised of news
articles, the latter is a collection of passages accumulated with Bing
queries. The set of relevant documents comprising the ground-truth of the TREC
Robust dataset was constructed via depth-100 pooling (Voorhees and Harman,
2000). On the other hand, in TREC DL a combination of depth-10 pooling and an
active learning based strategy (Abualsaud et al., 2018) was used to compile
the ground-truth (Craswell et al., 2020c, a). We leave out TREC 6 topic sets
from our experiments for consistency with the remaining topic sets, the
ground-truths of which do not include the congressional records (CR). Table 1
summarises the datasets used for our experiments.

####  3.1.3. Setup

For each topic set used in our experiments, we make use of the officially
submitted runs as downloaded from the TREC
archive111https://trec.nist.gov/results/. We conduct our experiments on each
topic set separately so as to compute the effect of the relative changes in
the systems (officially submitted runs) in each.

In each experiment, the value of the minimum depth ($d_{min}$ of Equations 5
and 6) was set to $10\%$ of the true depth used to construct the pool of the
respective datasets, i.e., $0.1\times 100=10$ for TREC Robust, and $0.1\times
10=1$ for TREC DL. Similarly, the value of the maximum depth ($d_{max}$) was
set to half the value of the true depths, i.e., $100/2=50$ and $10/2=5$ for
TREC Robust and TREC DL datasets, respectively. As the QPP estimate
$\phi(Q,M^{(k)})$, we use the standard unsupervised QPP approach - NQC.

Table 1.  Summary of the datasets used in our experiments. The columns
‘$\bar{|Q|}$’ and ‘$\bar{\\#Rel}$’ denote the average number of query terms
and average number of relevant documents, respectively. The column $p$ denotes
the number of official runs submitted, all of which is used to construct the
pools (Equation 3) for each topic set.

Collection #Docs Topics #Topics $\bar{|Q|}$ $\bar{\\#Rel}$ $p$ Robust 528,155
TREC 7 50 2.42 93.48 103 (disks 4,5 - CR) TREC 8 50 2.38 94.56 129 MS MARCO
8,841,823 DL’19 43 5.40 58.16 37 Passage DL’20 54 6.04 30.85 59

####  3.1.4. Pooling Methods Investigated

As baselines, we employ the standard procedure of constant-depth pooling (CDP)
(Equation 3). Since our proposed methodology uses depths that varies across
queries, for a fair comparison we compare our proposed approach with several
CDP baselines, as enumerated below.

  * •

CDP-Max involves setting $k=d_{max}$ in Equation 3, where $d_{max}$ is the
upper bound of the depth used in the VDP approach ($d_{max}$ in Equations 5
and 6). This method thus represents an apex-line or oracle scenario with a
larger pool size thus implying a larger effort for relevance assessments.

  * •

CDP-Min is a baseline which sets $k=d_{min}$ in Equation 3 thus implying that
this represents the lower end of the spectrum with a much smaller pool size.

  * •

CDP-Avg is a baseline with the depth of the pool being set to the closest
integer of the mid-point of the interval $[d_{min},d_{max}]$, i.e., setting
$k=\lfloor(d_{max}-d_{min})/2\rfloor$ in Equation 3. This baseline yields a
pool that is expected to be of a size similar to those obtained by the VDP-
based methods.

As variants of our proposed methodology of variable-depth pooling (VDP), we
explore the following.

  * •

VDP-IL: this denotes variable-depth pooling by means of an inverse linear
dependence (Equation 5).

  * •

VDP-L: this denotes variable-depth pooling with a linear dependence (Equation
6)222The implementation of all the methods investigated is available at
https://github.com/gdebasis/vardepthpooling.

####  3.1.5. Evaluation Metrics

As per the standard practice of a simulated pooling setup (Aslam and Yilmaz,
2007), the pool of documents obtained with each method is a subset of the
existing relevance assessments. This allows provision to compute the quality
of a pool by comparing the correlation of the relative system ranks measured
via the ground-truth induced on the subset as against the entire existing pool
of the respective datasets.

A smaller pool is considered to be of good quality if the relative system
ranks measured via an IR metric (e.g., AP) on this smaller set of ground-truth
does not change substantially in comparison to those measured with the larger
pool. In particular, as correlation measures between IR models we employ
Pearson’s $r$ and Kendall’s $\tau$. We employed mean average precision (MAP)
to induce an order on the different officially submitted runs (systems). As
per the standard practice, AP on the TREC DL dataset treated graded judgments
higher than or equal to 2 as relevant (Craswell et al., 2020c, a).

In addition to the relative rank stability of systems, we also report the
recall or coverage, measured as the fraction of relevant documents found in a
depth restricted pool averaged across all the queries of a benchmark topic
set. Formally,

(7)
$\mathcal{C}=\frac{1}{|R_{max}(\mathcal{Q})|}\sum_{Q\in\mathcal{Q}}\sum_{D\in\mathcal{P}_{\zeta}(Q)}\mathbb{I}(\mathrm{Rel}(D,Q)=1),$

where $\mathrm{Rel}(D,Q)=1$ if a document $D$ is judged as relevant to $Q$,
$\mathcal{Q}$ is a set of benchmark queries, $\mathbb{I}(.)$ denotes the
indicator function, and $R_{max}(\mathcal{Q})$ represents the total number of
relevant documents known for a static collection, e.g., the ones obtained by
employing $\zeta(Q)=100\,\forall Q\in\mathcal{Q}$, i.e, the true depth used to
compile the ground-truth of the TREC Robust topic sets.

We also measure the average pool size $\overline{|\mathcal{P}|}$, as the
number of unique documents occurring in a depth restricted pool - again
averaged over the queries. Note that this measure is related to the assessment
effort. Formally,

(8)
$\overline{|\mathcal{P}|}=\frac{1}{\mathcal{Q}}\sum_{Q\in\mathcal{Q}}|\bigcup_{i=1}^{p}M_{i}^{\zeta(Q)}|,$

Since a high coverage (Equation 7) and a low average pool size (Equation 8)
indicate an effective pooling strategy, for the sake of convenient comparisons
we combine these two measures into a single metric. Since the average pool
size per query is much larger than the recall values (bounded in $[0,1]$), we
compute the ratio after taking a $\log$ of the average pool size, akin to the
tf-idf combination where the document frequencies being much larger than the
tfs are used with a $\log$ transformation. Formally, we define Pool-size
Normalized Coverage (PNC) as $\mathcal{C}/\log\overline{|\mathcal{P}|}$, a
higher value of which indicates a better coverage obtained with a low average
pool size.

Table 2. A comparison of QPP-based VDP with CDP approaches (including the
oracle case, denoted as ‘AL’ or apex-line, shown in green) on the TREC Robust
topic sets. The best results along each column of the non-oracle results are
bold-faced. A higher value of all the metrics except
$\overline{|\mathcal{P}|}$ (average pool size) indicates a more effective
pooling strategy.

Avg. Evaluation Metrics Set Type Pool Depth P-$r$ K-$\tau$ $\mathcal{C}$
$\overline{|\mathcal{P}|}$ PNC TREC 7 BL CDP-Min 10 0.9897 0.9261 0.3988
187.66 0.0762 CDP-Avg 30 0.9988 0.9714 0.6711 484.00 0.1086 Ours VDP-L 16.36
0.9985 0.9760 0.7021 579.52 0.1104 VDP-IL 42.72 0.9986 0.9718 0.6467 414.50
0.1073 AL CDP-Max 50 0.9996 0.9886 0.8223 759.00 0.1240 TREC 8 BL CDP-Min 10
0.9922 0.9215 0.4052 239.54 0.0740 CDP-Avg 30 0.9987 0.9683 0.6596 620.96
0.1026 Ours VDP-L 22.90 0.9978 0.9680 0.6827 721.00 0.1037 VDP-IL 36.14 0.9991
0.9714 0.6600 540.00 0.1049 AL CDP-Max 50 0.9997 0.9864 0.8201 959.62 0.1194

Table 3. Evaluation on TREC DL topic sets, the organization of the table being
identical to that of Table 2.

Avg. Evaluation Metrics Set Type Pool Depth P-$r$ K-$\tau$ $\mathcal{C}$
$\overline{|\mathcal{P}|}$ PNC TREC DL’19 BL CDP-Min 1 0.9022 0.6336 0.2229
8.65 0.1033 CDP-Avg 3 0.9559 0.7147 0.4703 20.46 0.1558 Ours VDP-L 3.37 0.9686
0.8559 0.5398 24.76 0.1682 VDP-IL 1.67 0.9241 0.7297 0.2814 10.83 0.1181 AL
CDP-Max 5 0.9850 0.9399 0.6542 30.67 0.1911 TREC DL’20 BL CDP-Min 1 0.9760
0.8656 0.2448 12.27 0.0976 CDP-Avg 3 0.9944 0.9299 0.4878 29.48 0.1442 Ours
VDP-L 3.87 0.9960 0.9334 0.5740 37.50 0.1584 VDP-IL 1.16 0.9866 0.9030 0.3161
15.75 0.1146 AL CDP-Max 5 0.9977 0.9568 0.6671 45.24 0.1750

###  3.2. Results

Tables 2 and 3 present the results of our experiments on the TREC Robust and
the TREC DL datasets. We observe the following trends in the results. First,
our proposed variable-depth pooling (VDP) approaches outperform the constant
depth pooling approaches with the depth being set to minimum and average
values of the depth range, as can be seen from the better correlation values
measured with $r$ and $\tau$. Moreover, these high correlations are observed
with better coverage and PNC, which answers RQ-1 in affirmative. CDP-Max, the
apex-line setting (shown as the green rows in the tables) yields better
results at the cost of higher annotation effort ($\overline{|\mathcal{P}|}$).

Second, in relation to RQ-2, it can be observed that there is no clear winner
between the VDP-L (Equation 6) and VDP-IL (Equation 5) variants. While the
linear dependence method works better than its inverse-linear counterpart for
3 topic-sets (TREC 7 and the two TREC DL sets as seen by the higher rank
correlation, coverage and PNC), the inverse linear works slightly better for
TREC 8.

Third, CDP approaches are more robust when the depth is a relatively high
value; this can be seen from the better improvements in the Kendall’s $\tau$
rank correlations of systems observed on the TREC DL topic sets in comparison
to the TREC Robust ones (compare the CDP-Avg values with the VDP ones). It can
thus be concluded that VDP approaches are more suitable in cases where the
depth range used for VDP is comprised of smaller values, as is the case for
the TREC DL ($[1,5]$) vs. TREC Robust ($[10,50]$).

Lastly, the VDP methods consistently yield better values of PNC (Pool-size
normalized coverage) in comparison to the baseline CDP approaches. This means
that a higher number of relevant documents could be found for a set of
benchmark queries with reduced manual assessment effort.

##### Concluding Remarks

In this initial investigation of employing variable depth-pooling (VDP)
strategies for constructing ground-truth relevance data, our experiments
demonstrated encouraging trends. Specifically, we observe that a standard
unsupervised QPP method, such as NQC, leads to satisfactory results in terms
of high correlation of relative system ranks and also high coverage at the
expense of smaller average pool-size. Thus, this indicates stable evaluation
results with minimized annotation effort.

There are a number of ways in which we can extend this initial exploration.
First, it would be interesting to compare the relative effects of different
QPP methods on VDP. It would also be interesting to see if the use of query
variants, such as (Zendel et al., 2019; Datta et al., 2022b), can further
optimise the depth prediction of VDP.

##### Acknowledgement

The first author thanks Procheta Sen (University of Liverpool) for suggesting
this idea during an informal conversation.

## References

  * (1)
  * Abualsaud et al. (2018) Mustafa Abualsaud, Nimesh Ghelani, Haotian Zhang, Mark D. Smucker, Gordon V. Cormack, and Maura R. Grossman. 2018.  A System for Efficient High-Recall Retrieval. In _Proc. of SIGIR’18_. 1317–1320.  https://doi.org/10.1145/3209978.3210176
  * Arampatzis et al. (2009) Avi Arampatzis, Jaap Kamps, and Stephen Robertson. 2009\.  Where to Stop Reading a Ranked List? Threshold Optimization Using Truncated Score Distributions. In _Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Boston, MA, USA) _(SIGIR ’09)_. Association for Computing Machinery, New York, NY, USA, 524–531.  https://doi.org/10.1145/1571941.1572031
  * Aslam and Yilmaz (2007) Javed A. Aslam and Emine Yilmaz. 2007.  Inferring document relevance from incomplete information. In _CIKM_. ACM, 633–642.
  * Bahri et al. (2020) Dara Bahri, Yi Tay, Che Zheng, Donald Metzler, and Andrew Tomkins. 2020.  Choppy: Cut Transformer for Ranked List Truncation. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Virtual Event, China) _(SIGIR ’20)_. Association for Computing Machinery, New York, NY, USA, 1513–1516.  https://doi.org/10.1145/3397271.3401188
  * Carterette et al. (2006) Ben Carterette, James Allan, and Ramesh K. Sitaraman. 2006\.  Minimal test collections for retrieval evaluation. In _SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, Washington, USA, August 6-11, 2006_ , Efthimis N. Efthimiadis, Susan T. Dumais, David Hawking, and Kalervo Järvelin (Eds.). ACM, 268–275.  https://doi.org/10.1145/1148170.1148219
  * Cleverdon (1967) Cyril Cleverdon. 1967\.  The Cranfield tests on index languages devices.  (1967).  http://www3.interscience.wiley.com/journal/114214228/abstract
  * Cormack et al. (1998) Gordon V. Cormack, Christopher R. Palmer, and Charles L. A. Clarke. 1998.  Efficient Construction of Large Test Collections. In _Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Melbourne, Australia) _(SIGIR ’98)_. Association for Computing Machinery, New York, NY, USA, 282–289.  https://doi.org/10.1145/290941.291009
  * Craswell et al. (2020a) Nick Craswell, Bhaskar Mitra, Emine Yilmaz, and Daniel Campos. 2020a.  Overview of the TREC 2020 Deep Learning Track. In _Proc. 29th Text REtrieval Conference, TREC 2020_ _(NIST Special Publication, Vol. 1266)_.
  * Craswell et al. (2020b) Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M. Voorhees. 2020b.  Overview of the TREC 2019 deep learning track.  arXiv:2003.07820 [cs.IR]
  * Craswell et al. (2020c) Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M. Voorhees. 2020c.  Overview of the TREC 2019 deep learning track.  arXiv:2003.07820 [cs.IR]
  * Cronen-Townsend et al. (2002) Steve Cronen-Townsend, Yun Zhou, and W. Bruce Croft. 2002\.  Predicting Query Performance. In _Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ _(SIGIR ’02)_. Association for Computing Machinery, New York, NY, USA, 299–306.
  * Datta et al. (2022a) Suchana Datta, Debasis Ganguly, Derek Greene, and Mandar Mitra. 2022a.  Deep-QPP: A Pairwise Interaction-based Deep Learning Model for Supervised Query Performance Prediction. In _Proc. of WSDM’22_. 201–209.
  * Datta et al. (2022b) Suchana Datta, Debasis Ganguly, Mandar Mitra, and Derek Greene. 2022b.  A Relative Information Gain-Based Query Performance Prediction Framework with Generated Query Variants.  _ACM Trans. Inf. Syst._ 41, 2, Article 38 (dec 2022), 31 pages.
  * Datta et al. (2022c) Suchana Datta, Sean MacAvaney, Debasis Ganguly, and Derek Greene. 2022c.  A ’Pointwise-Query, Listwise-Document’ based Query Performance Prediction Approach. In _SIGIR_. ACM, 2148–2153.
  * Diaz (2007) Fernando Diaz. 2007\.  Performance Prediction Using Spatial Autocorrelation. In _Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ _(SIGIR ’07)_. Association for Computing Machinery, New York, NY, USA, 583–590.
  * Hauff et al. (2008) Claudia Hauff, Djoerd Hiemstra, and Franciska de Jong. 2008\.  A Survey of Pre-Retrieval Query Performance Predictors. In _Proceedings of the 17th ACM Conference on Information and Knowledge Management_ _(CIKM ’08)_. Association for Computing Machinery, New York, NY, USA, 1419–1420.
  * He and Ounis (2004) Ben He and Iadh Ounis. 2004\.  Inferring Query Performance Using Pre-retrieval Predictors. In _String Processing and Information Retrieval_. Springer Berlin Heidelberg, Berlin, Heidelberg, 43–54.
  * Lien et al. (2019) Yen-Chieh Lien, Daniel Cohen, and W. Bruce Croft. 2019\.  An Assumption-Free Approach to the Dynamic Truncation of Ranked Lists. In _Proceedings of the 2019 ACM SIGIR International Conference on Theory of Information Retrieval_ (Santa Clara, CA, USA) _(ICTIR ’19)_. Association for Computing Machinery, New York, NY, USA, 79–82.  https://doi.org/10.1145/3341981.3344234
  * Losada et al. (2016) David E. Losada, Javier Parapar, and Álvaro Barreiro. 2016\.  Feeling Lucky? Multi-Armed Bandits for Ordering Judgements in Pooling-Based Evaluation. In _Proceedings of the 31st Annual ACM Symposium on Applied Computing_ (Pisa, Italy) _(SAC ’16)_. Association for Computing Machinery, New York, NY, USA, 1027–1034.
  * Nguyen et al. (2016) Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016.  MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. In _Proc. of CoCo@NIPS_.
  * Roy et al. (2016) Dwaipayan Roy, Debasis Ganguly, Mandar Mitra, and Gareth J. F. Jones. 2016.  Word Vector Compositionality based Relevance Feedback using Kernel Density Estimation. In _Proc. of CIKM 2016_. 1281–1290.
  * Sanderson (2010) Mark Sanderson. 2010\.  Test Collection Based Evaluation of Information Retrieval Systems.  _Found. Trends Inf. Retr._ 4, 4 (2010), 247–375.  http://dblp.uni-trier.de/db/journals/ftir/ftir4.html#Sanderson10
  * Shtok et al. (2012) Anna Shtok, Oren Kurland, David Carmel, Fiana Raiber, and Gad Markovits. 2012.  Predicting Query Performance by Query-Drift Estimation.  _ACM Trans. Inf. Syst._ 30, 2, Article 11 (2012).
  * Voorhees and Harman (2000) Ellen M Voorhees and Donna K Harman. 2000.  _The eighth text retrieval conference (TREC-8)_.  Technical Report.
  * Yilmaz et al. (2008) Emine Yilmaz, Evangelos Kanoulas, and Javed A. Aslam. 2008\.  A simple and efficient sampling method for estimating AP and NDCG. In _Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2008, Singapore, July 20-24, 2008_ , Sung-Hyon Myaeng, Douglas W. Oard, Fabrizio Sebastiani, Tat-Seng Chua, and Mun-Kew Leong (Eds.). ACM, 603–610.
  * Yilmaz et al. (2014) Emine Yilmaz, Manisha Verma, Nick Craswell, Filip Radlinski, and Peter Bailey. 2014.  Relevance and Effort: An Analysis of Document Utility. In _Proc. of CIKM’14_. 91–100.
  * Zendel et al. (2019) Oleg Zendel, Anna Shtok, Fiana Raiber, Oren Kurland, and J. Shane Culpepper. 2019.  Information Needs, Queries, and Query Performance Prediction. In _Proc. of SIGIR ’19_. Association for Computing Machinery, New York, NY, USA, 395–404.
  * Zhao et al. (2008) Ying Zhao, Falk Scholer, and Yohannes Tsegay. 2008.  Effective Pre-Retrieval Query Performance Prediction Using Similarity and Variability Evidence. In _Proc. ECIR’08_. Springer-Verlag, Berlin, Heidelberg, 52–64.
  * Zhou and Croft (2007) Yun Zhou and W. Bruce Croft. 2007.  Query Performance Prediction in Web Search Environments. In _Proc. of SIGIR’07_. 543–550.