# Feedback Coding for Active Learning

Gregory Canal Matthieu Bloch Christopher Rozell

School of Electrical and Computer Engineering
Georgia Institute of Technology, Atlanta, GA
{gregory.canal, matthieu<EMAIL_ADDRESS>
###### Abstract

The iterative selection of examples for labeling in active machine learning is
conceptually similar to feedback channel coding in information theory: in both
tasks, the objective is to seek a minimal sequence of actions to encode
information in the presence of noise. While this high-level overlap has been
previously noted, there remain open questions on how to best formulate active
learning as a communications system to leverage existing analysis and
algorithms in feedback coding. In this work, we formally identify and leverage
the structural commonalities between the two problems, including the
characterization of encoder and noisy channel components, to design a new
algorithm. Specifically, we develop an optimal transport-based feedback coding
scheme called _Approximate Posterior Matching_ (APM) for the task of active
example selection and explore its application to Bayesian logistic regression,
a popular model in active learning. We evaluate APM on a variety of datasets
and demonstrate learning performance comparable to existing active learning
methods, at a reduced computational cost. These results demonstrate the
potential of directly deploying concepts from feedback channel coding to
design efficient active learning strategies.

##  1 Introduction

Active learning is an area of modern machine learning that studies how data
points can be sequentially selected for labeling to train a model with as few
labeled examples as possible (Settles,, 2009). Minimizing the number of
labeled examples is critical in any learning scenario where labels are
expensive to obtain, such as in healthcare applications where a medical expert
must hand-label each training example (Liu,, 2004), or where only a limited
number of examples can be evaluated, such as in drug discovery (Warmuth et
al.,, 2003).

The active selection of data points shares many technical parallels with
channel coding with feedback, where a message is encoded into a sequence of
symbols transmitted across a noisy channel and each symbol is selected based
on the message and past channel outputs. In active learning, the optimal
classifier parameters play the role of the “message” while the sequence of
examples with noisy labels plays the role of “channel outputs” available
through feedback to select the next example for labeling. Both feedback
channel coding and active learning seek to minimize the number of encoder
actions, leverage a history of noisy observations to select the next most
informative action, must account for observation noise, and should operate in
a computationally efficient manner. Although there exists a large literature
studying the intersection of information theory with machine learning (Xu and
Raginsky,, 2017) and specifically active learning (Naghshvar et al.,, 2015),
there remain open questions about the best ways to directly leverage
techniques in channel coding for active example selection.

The main contribution of this work is a formulation of general active learning
problems in terms of a feedback coding system, and a demonstration of this
approach through the application and analysis of active learning in logistic
regression. To motivate this approach, we first examine active learning
through the lens of feedback channel coding by identifying communications
system components, including a deterministic encoder, noisy channel, channel
input constraints, and capacity-achieving distribution. With these components
identified, we show how typical structural constraints in active learning
problems prevent the direct application of existing feedback coding approaches
such as _posterior matching_ (Ma and Coleman,, 2011). We address this
challenge by proposing _Approximate Posterior Matching_ (APM), an optimal
transport-based active learning scheme that extends posterior matching to
account for the type of encoder constraints found in active learning problems.

To demonstrate the power of this approach, we apply APM to Bayesian logistic
regression, a popular model in active learning. We identify the communication
system components in logistic regression, derive a corresponding APM selection
scheme (APM-LR), provide analytical results concerning each selected example’s
information content, and empirically demonstrate on several datasets how APM-
LR attains a sample complexity comparable to other active logistic regression
methods at a reduced computational cost. While this example scenario
highlights the capabilities of APM as a specific data selection method, the
feedback communications framework we develop provides a unified approach for
designing and analyzing active learning systems in general.

###  1.1 Related Work

Modern active learning methods vary considerably in their approach to example
selection, ranging from coreset construction (Pinsler et al.,, 2019; Sener and
Savarese,, 2018) and adversarial learning of informative examples (Sinha et
al.,, 2019) to ensemble measures of example utility (Beluch et al.,, 2018) and
Bayesian information acquisition methods (Gal et al.,, 2017; Kirsch et al.,,
2019). Bayesian active learning methods are intimately related to concepts in
information and coding theory, and the intersection between these topics has a
long history rooted in the study of sequential design of experiments
(Lindley,, 1956; Chernoff,, 1959) and active hypothesis testing (Burnashev and
Zigangirov,, 1974). Since this early work, direct estimation and maximization
of information gain has emerged as a popular active learning method (MacKay,,
1992), and has been approximated for computational tractability (Houlsby et
al.,, 2011). More recently, Naghshvar et al., (2015) have studied the direct
application of an information-theoretic active hypothesis testing method to
active learning problems. This method is limited to discriminating between a
finite number of hypotheses (as opposed to estimating arbitrary model
parameters) and to our knowledge has not been applied to popular machine
learning models such as logistic regression. Other works have described at a
high-level the similarities between active learning and coding with feedback
over a noisy channel but do not exploit this observation to leverage existing
coding schemes for example selection (Chen et al.,, 2015; Arias-Castro et
al.,, 2013).

Posterior matching (Shayevitz and Feder,, 2011; Ma and Coleman,, 2011) is a
general feedback coding scheme that has been applied to tasks beyond
telecommunications such as brain-computer interfacing (Omar et al.,, 2010;
Tantiongloc et al.,, 2017) and aircraft path planning (Akce et al.,, 2010),
but has limited application to example selection in active learning. Castro
and Nowak, (2008) study an active learning algorithm related to posterior
matching that learns decision boundaries in discretized spaces, but does not
directly maximize information about hyperplane parameters in a continuous
space as we do here. More generally, to our knowledge existing work has not
framed the task of active learning as a feedback communications system for the
purpose of identifying an equivalent capacity-achieving distribution and
selecting examples whose channel input distribution most closely approximates
it, as we do here.

Logistic regression is a popular setting for the study of active learning, and
has served as a testbed for the evaluation of competing example selection
techniques. Yang and Loog, (2018) surveyed modern active learning methods for
logistic regression and evaluated them on many datasets. They generally found
that uncertainty sampling and random sampling match or exceed the performance
of more sophisticated (and computationally intensive) example selection
methods. Uncertainty sampling, where examples closest to the estimated
decision boundary are selected for labeling, is arguably the most popular
active learning method for linear classification (Tong and Koller,, 2001).
Other active learning methods for linear classifiers are discussed in the
literature related to learning halfspaces under bounded noise (Zhang et al.,,
2020).

##  2 Active Learning as a Communications Model

Let $\mathcal{U}\subseteq\mathbb{R}^{d}$ denote a pool of unlabeled examples
from which at each training iteration $n\in\mathbb{N}$ an example
$x_{n}\in\mathcal{U}$ is selected for labeling by an expert, who assigns label
$Y_{n}\in\\{1,2,\dots K\\}$ according to a probabilistic model (all random
variables are capitalized in this work). We consider a Bayesian framework in
which we assume the existence of ground-truth model parameters
$\theta\in\Theta$ distributed according to a prior $p_{\theta}$ that
parameterizes a distribution $p(Y\mid x,\theta)$ governing the expert’s
labeling behavior. As is common in active learning, we assume that the labels
$\\{Y_{n}\\}$ are independent when conditioned on $\theta$. At each iteration
$n$, a learning algorithm $\operatorname{A}$ is trained on a labeled dataset
$\mathcal{L}_{n}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ (using lowercase to denote
previously observed labels), resulting in a trained model with parameters
$\widehat{\theta}_{n}\in\Theta$. The task of active learning is to design a
policy $\pi_{n}$ that, at each iteration, uses the label history
$\mathcal{L}_{n-1}$ to select example $x_{n}$ from the remaining unlabeled
examples
$\mathcal{U}_{n}\coloneqq\mathcal{U}\setminus\\{x_{i}\\}_{i=1}^{n-1}$, such
that the classifier trains a generalizable model with as few labeled examples
as possible.

(a)

(b)

(c)

Figure 1: (a) Decomposition of logistic regression into an inner product
between hyperplane $\theta$ and example $x_{n}$, and a logistic label
distribution that depends only on this product. (b) Active learning decomposed
into a deterministic function $h$, label distribution $p(Y\mid L)$, and
feedback of the labeling history $\mathcal{L}_{n-1}$ to example selection
policy $\pi_{n}$. (c) Coding with feedback, where a message is transmitted
across a noisy channel as a sequence of symbols and subsequently decoded. By
comparing (b) and (c), one can draw direct connections between active learning
and coding with feedback.

In active logistic regression, $\theta$ encodes the weights of a linear
separator, with $\Theta=\mathbb{R}^{d}$ (we consider only homogeneous logistic
regression in this work). We assume a Gaussian prior
$p_{\theta}\sim\mathcal{N}(0,\frac{1}{\lambda}I)$ with hyperparameter
$\lambda>0$. The label $Y\in\\{-1,1\\}$ for data example $x$ is assumed to be
distributed according to

$p(Y=1\mid x,\theta)=\frac{1}{1+e^{-x^{T}\theta}}.$ (1)

Given a labeled dataset $\mathcal{L}$, we consider a maximum a posteriori
(MAP) learning algorithm given by the convex program

$\displaystyle\operatorname{A}(\mathcal{L})$
$\displaystyle=\operatorname*{arg\,max}_{\theta\in\mathbb{R}^{d}}\enspace\ln\,p_{\theta}\\!\prod_{(x,y)\in\mathcal{L}}p(y\mid
x,\theta)$
$\displaystyle=\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{d}}\enspace\frac{\lambda}{2}\lVert\theta\rVert_{2}^{2}\,+\\!\sum_{(x,y)\in\mathcal{L}}\ln(1+e^{-yx^{T}\theta}).$
(2)

Our key insight in this work is to define an intermediate variable
$L=h_{\theta}(x)$, where $h_{\theta}(x)\coloneqq x^{T}\theta$, and decompose
the labeling distribution in (1) into $p(Y=1\mid x,\theta)=p(Y=1\mid
L)=\frac{1}{1+e^{-L}}$. This decomposition of the labeling distribution into a
deterministic function $h_{\theta}(x)$ and conditional distribution $p(Y\mid
L)$ can be found in many machine learning models. For instance, in Bayesian
neural networks (Gal et al.,, 2017), $h_{\theta}(x)$ is typically given by the
composition of several nonlinear layers with $L=h_{\theta}(x)$ encoding the
final layer feature vector, and $p(Y\mid L)$ is given by the softmax function.
Figure 1(a) depicts this decomposition for logistic regression, and Figure
1(b) illustrates the full active learning decomposition in the general case.

By decomposing active learning in this manner, we are able to draw direct
connections to feedback channel coding, in which a message $\theta$ is encoded
into a sequence of symbols $\\{L_{n}\\}$, transmitted across a channel with
transition probability $p(Y\mid L)$ yielding noisy output symbols
$\\{Y_{n}\\}$, and subsequently decoded into an estimated message
$\widehat{\theta}_{n}$. The availability of noiseless feedback from the
channel output to the encoder provides the encoder with the history of
received symbols, and allows it to adaptively select an informative channel
input (Figure 1(c)). By comparing Figures 1(b) and 1(c), we can see the direct
correspondence between active learning and channel coding with feedback: model
parameters $\theta$ serve as the message, which is encoded by function $h$
(parameterized by $x_{n}$) into channel input $L_{n}=h_{\theta}(x_{n})$. Label
distribution $p(Y\mid L)$ can be interpreted as a noisy channel, with label
$Y_{n}$ as the channel output. Algorithm $\operatorname{A}$ decodes labeled
data $\mathcal{L}_{n}$ into a decoded message $\widehat{\theta}_{n}$, and
$\mathcal{L}_{n}$ is passed as noiseless feedback to the encoder. This
formulation of active learning as a feedback communications system allows one
to leverage existing tools in channel coding for the design of an example
selection scheme $\pi_{n}$. While similar decompositions have been observed in
prior work (Naghshvar et al.,, 2015; Chen et al.,, 2015), we believe our work
is the first to use this approach to analyze active learning in a real-world
setting such as logistic regression.

###  2.1 Optimal Feedback Coding

In devising a feedback coding scheme for selecting a sequence of channel
inputs $\\{L_{n}\\}$, there are several quantities that characterize optimal
performance. We denote the _mutual information_ $I(L;Y)$ between random
variables $L$ and $Y$ as a function of marginal distribution $p_{L}$ and
conditional distribution $p_{Y\mid L}$ (using the notation $p_{L}$ and
$p_{Y\mid L}$ interchangeably with $p(L)$ and $p(Y\mid L)$) given by
$I(p_{L},p_{Y\mid L})$:

$I(p_{L},p_{Y\mid L})\coloneqq\int_{L,Y}p_{L}\,p_{Y\mid
L}\log_{2}\frac{p_{Y\mid L}}{p_{Y}},$

where $p_{Y}$ denotes the output distribution of channel $p_{Y\mid L}$ with
input distribution $p_{L}$. Letting $y^{i}\coloneqq\\{y_{1},\dots y_{i}\\}$
denote the history of observed channel outputs, at iteration $n$ we seek to
maximize the _information gain_ $I(\theta;Y_{n}\mid y^{n-1})$, which measures
the one-step decrease in uncertainty about the message upon receiving each
channel output. For deterministic encoders, information gain is equal to
$I(L_{n};Y_{n}\mid y^{n-1})=I(p_{L_{n}\mid y^{n-1}},p_{Y\mid L})$ (Cover and
Thomas,, 2006). Note that for a fixed channel $p_{Y\mid L}$, information gain
is only a function of the channel input distribution $p_{L_{n}\mid y^{n-1}}$,
conditioned on the history of channel outputs.

A key quantity in channel coding is the _channel capacity_ $C$, defined as the
maximum mutual information across the channel for any channel input
distribution $p_{L}$ within some class $\mathcal{C}$:

$p^{*}_{L}(\mathcal{C})\coloneqq\operatorname*{arg\,max}_{p_{L}\in\mathcal{C}}\,I(p_{L},p_{Y\mid
L})\quad C\coloneqq I(p^{*}_{L},p_{Y\mid L}).$

The _capacity-achieving distribution_ $p^{*}_{L}(\mathcal{C})$ is the input
distribution in $\mathcal{C}$ that maximizes information across the channel.
Through achievability and converse arguments, a central result in information
theory is that optimal coding schemes, when marginalized over the message set,
should induce the capacity-achieving distribution on the channel input
(Shannon,, 1948). In working towards applying existing feedback coding schemes
to active example selection, we first characterize the capacity-achieving
distribution for logistic regression, which is a core contribution of our work
and forms the basis of our novel active logistic regression scheme in Section
3.

#### Channel Capacity in Logistic Regression.

Letting $f(\ell)\coloneqq\frac{1}{1+e^{-\ell}}$, we observe from Figure 1(a)
that logistic regression has a binary output channel with transition
probability $p(Y=1\mid L)=f(L)$. Without constraints on the channel input, the
information gain can be maximized by placing masses of equal weight at
$\pm\infty$. However, logistic regression imposes the structural constraint
$L=x^{T}\theta$, so that such a distribution would require data points of
infinite energy for finite model weights. Therefore, to characterize logistic
regression capacity in practice, we consider the capacity-achieving
distribution within the class of power-constrained distributions given by
$\mathcal{C}_{P}\coloneqq\\{p_{L}:\operatorname{\mathbb{E}}[L^{2}]\leq P\\}$;
we discuss the selection of $P$ in Section 3. With this class defined, we have
our first result.

######  Proposition 2.1 (Capacity of Logistic Regression).

For $p(Y=1\mid L)=f(L)$, we have $p^{*}_{L}(\mathcal{C}_{P})=B_{\sqrt{P}}$,
where $B_{t}$ is defined as
$B_{t}(\ell)\coloneqq\frac{1}{2}\delta(\ell-t)+\frac{1}{2}\delta(\ell+t)$ and
$\delta$ denotes the Dirac delta function. Furthermore, we have
$C=I(B_{\sqrt{P}},f)=1-h_{b}(f(\sqrt{P}))$, where $h_{b}$ denotes the binary
entropy function.

The proof follows closely to that of Singh et al., (2009) for the one-bit
quantized Gaussian channel; the proofs of Proposition 2.1 and all subsequent
results are presented in Appendix A.

###  2.2 Posterior Matching

By characterizing the channel capacity and capacity-achieving distribution of
active learning models, we enable the use of existing feedback coding schemes
that achieve capacity. Recently, a capacity-achieving feedback coding scheme
known as _posterior matching_ has been developed to select a sequence of
channel inputs $\\{L_{n}\\}$ to maximize the information gain across a given
channel $p_{Y\mid L}$. The central concept is to construct an encoder that by
definition induces $p_{L_{n}\mid y^{n-1}}=p^{*}_{L}$ for every $n$, which in
essence hands the decoder the information that it is still “missing” (Ma and
Coleman,, 2011). This involves the construction of an encoder mapping
$S_{y^{n-1}}\colon\theta\to L$ parameterized by ${y^{n-1}}$ such that
$S_{y^{n-1}}(\theta)\sim p^{*}_{L}$ for every $n$.

While posterior matching is an attractive feedback coding scheme, there are
challenges in applying it to active learning: given the structural constraints
of any particular active learning problem as depicted in Figure 1(b), it may
not always be the case that a mapping from $p_{\theta\mid\mathcal{L}_{n-1}}$
to $p^{*}_{L}$ exists, since the encoder is constrained to the set of mappings
given by $\\{h_{\theta}(x):x\in\mathcal{U}_{n}\\}$.111The analogous
distribution to $p_{L_{n}\mid y^{n-1}}$ in active learning is
$p_{L_{n}\mid\mathcal{L}_{n-1}}$. When considering only deterministic example
selection schemes, $p_{L_{n}\mid\mathcal{L}_{n-1}}$ is induced directly from
$p_{\theta\mid\mathcal{L}_{n-1}}$, through $h_{\theta}(x)$. For example, in
active logistic regression under mild assumptions, there exists no $x$ such
that $h_{\theta}(x)\sim p^{*}_{L}$, as shown in the following proposition.

######  Proposition 2.2.

Under a log-concave prior distribution $p_{\theta}$, in Bayesian logistic
regression for any $n$ there exists no $x_{n}$ that induces
$p_{L_{n}\mid\mathcal{L}_{n-1}}\sim p^{*}_{L}$.

Since we assume a Gaussian prior $p_{\theta}$ (which is log-concave),
Proposition 2.2 applies and therefore there exists no active logistic
regression scheme $\pi_{n}$ corresponding to a posterior matching mapping from
$\theta$ to $p^{*}_{L}$. We suspect that the infeasibility of $p^{*}_{L}$
holds generally in other real-world machine learning models (e.g., Bayesian
neural networks) due to similar structural constraints imposed by
$h_{\theta}(x)$, preventing the direct application of posterior matching for
example selection. In the next section, we extend concepts from posterior
matching to a novel active learning scheme compatible with this constrained
encoder structure.

###  2.3 Approximate Posterior Matching

To address the impossibility of finding $x\in\mathcal{U}$ that induces
$p^{*}_{L}$ on $L$, we introduce a scheme that instead selects an example
$x_{n}$ such that $p_{L\mid\mathcal{L}_{n-1}}$ is distributed “as close as
possible” to $p^{*}_{L}$, as measured by a distance between distributions.
Specifically, we use the 2-Wasserstein distance because of its convenient
geometric properties and compatibility with non-overlapping distribution
supports (Arjovsky et al.,, 2017). The $p$-Wasserstein distance between
distributions $\mu$ and $\nu$ is given by

$W_{p}(\mu,\nu)=\biggl{(}\inf_{\gamma\in\Pi(\mu,\nu)}\int_{u}\int_{v}\lvert
u-v\rvert^{p}\gamma(u,v)\biggr{)}^{\frac{1}{p}},$

where $\Pi(\mu,\nu)$ is the set of couplings with marginal distributions $\mu$
and $\nu$ (Villani,, 2008). Our selection scheme, called Approximate Posterior
Matching (APM), is then given by

$x_{n}=\pi_{n}(\mathcal{L}_{n-1})\coloneqq\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}\enspace
W_{2}(p_{L_{n}\mid\mathcal{L}_{n-1}},p^{*}_{L}).$ (3)

While APM is intuitively appealing because it steers the induced channel
distribution as close as possible to $p^{*}_{L}$, we justify this strategy in
the next section for the case of logistic regression by showing that
information gain does in fact approach its maximum possible value as
$W_{2}(p_{L\mid\mathcal{L}_{n-1}},p^{*}_{L})$ is minimized.

##  3 APM in Logistic Regression

Under the power constraint $\operatorname{\mathbb{E}}[L^{2}]\leq P$,
Proposition 2.1 establishes that the capacity-achieving distribution in the
logistic regression system is given by $B_{\sqrt{P}}$. We now show an
information continuity result for this capacity-achieving distribution, which
provides a mathematical justification for the APM Wasserstein distance
minimization in (3).

######  Theorem 3.1.

Let
$\widetilde{C}_{n}=\max_{x\in\mathcal{U}_{n}}I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)$
denote the maximum information gain from _any_ example selected at iteration
$n$, and suppose $P>0$ is selected such that
$p_{L_{n}\mid\mathcal{L}_{n-1}}\in\mathcal{C}_{P}$ for any
$x\in\mathcal{U}_{n}$. Then for any $x\in\mathcal{U}_{n}$,

$\widetilde{C}_{n}-I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)\leq
K_{P}W_{2}(p_{L_{n}\mid\mathcal{L}_{n-1}},B_{\sqrt{P}}),$

where $K_{P}>0$ is a constant that only depends on $P$.

For decreasing $W_{2}(p_{L},B_{\sqrt{P}})$, this result bounds
$I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)$ towards its maximum possible information
gain $\widetilde{C}_{n}$. In other words, minimizing the distance to the
_known_ capacity-achieving distribution (even if not achievable in practice)
ensures that the information gain approaches its maximum value within the set
of possible input distributions — a value which is _unknown_ a priori. As we
shall see in the results and experiments that follow, targeting the known
capacity-achieving distribution affords geometric simplifications and
computational benefits over the strategy of directly selecting the example
that achieves $\widetilde{C}_{n}$. Unlike APM, the latter method does not
benefit from analytical knowledge of the information structure of the channel
and constraint set, and so it must instead conduct an expensive brute-force
maximization of information gain.

[2pt]Labeled data pool

[2pt]Uncertainty utility: initial

[2pt]50 Uncertainty queries

[2pt]Uncertainty utility: 50 queries

[2pt]Hyperplane prior

(a)

[2pt]APM-LR utility: initial

(b)

[2pt]50 APM-LR queries

(c)

[2pt]APM-LR utility: 50 queries

(d)

Figure 2: (a) Top: linearly separable dataset (optimal hyperplane is diagonal)
demonstrating the failure of uncertainty sampling (dataset adapted from Huang
et al., (2010)). Bottom: samples from hyperplane posterior, given two seed
labels. The black hyperplane and corresponding normal vector depict the
initial logistic regression solution, the cyan arrow indicates the normal
vector to the posterior mean hyperplane, and the purple arrow indicates the
maximal eigenvector of the posterior. (b) Utility function heatmap for
uncertainty sampling (top) and APM-LR (bottom) — the unlabeled example with
the highest utility is selected for labeling. Uncertainty sampling selects
examples close to the current hyperplane, while APM-LR selects examples that
are both close to the posterior mean hyperplane and align with the direction
of largest posterior variance. (c-d) After 50 queries, uncertainty sampling
(c-top) has not selected samples in the dataset corners, leading to sampling
bias and continued sampling of the center clusters (d-top). Meanwhile, APM-LR
(c-bottom) has sufficiently explored the dataset, while continuing to sample
examples in only the most ambiguous regions (d-bottom).

###  3.1 Closed-form Results

For logistic regression, the calculation of $W_{2}(p_{L},B_{t})$ takes a
convenient closed-form expression, which simplifies the example selection in
(3):

######  Proposition 3.2.

For $t>0$, with $\operatorname{med}_{p_{L}}(L)$ denoting the median of $L$
according to distribution $p_{L}$,

$W_{2}^{2}(p_{L},B_{t})=\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]-2t\operatorname{\mathbb{E}}_{p_{L}}[\lvert
L-\operatorname{med}_{p_{L}}(L)\rvert]+t^{2}$

We can simplify this expression even further when $p_{L}$ is normally
distributed.

######  Corollary 3.2.1.

For $L\sim\mathcal{N}(\mu,\sigma^{2})$,

$W_{2}^{2}(p_{L},B_{t})=\mu^{2}+\biggl{(}\sigma-\sqrt{\frac{2}{\pi}}t\biggr{)}^{2}+\biggl{(}1-\frac{2}{\pi}\biggr{)}t^{2}.$

At iteration $n$, suppose that $p_{\theta\mid\mathcal{L}_{n-1}}$ is
approximated by $\mathcal{N}(\mu_{n},\Sigma_{n})$, resulting in channel input
$L_{n}=\theta^{T}x_{n}$ being distributed as
$\mathcal{N}(\mu_{n}^{T}x_{n},x_{n}^{T}\Sigma_{n}x_{n})$. Although
$p_{\theta\mid\mathcal{L}_{n-1}}$ is not normally distributed in logistic
regression, it is common to make this approximation in practice (Bishop,,
2006). By applying Corollary 3.2.1 and omitting constant terms, we derive our
APM selection policy for logistic regression with power constraint $P$.

######  Definition 3.1.

Approximate Posterior Matching for Logistic Regression (APM-LR):

$\pi_{n}(\mathcal{L}_{n-1})=\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}\enspace(\mu_{n}^{T}x)^{2}+\biggl{(}\sqrt{x^{T}\Sigma_{n}x}-\sqrt{\frac{2}{\pi}P}\biggr{)}^{2}.$
(4)

This objective is a combination of two terms: the first term corresponds to
minimizing the distance between example $x$ and the posterior mean hyperplane.
If $\mu_{n}$ is taken as an estimate of $\theta$, this term corresponds to the
well-known _uncertainty sampling_ active learning method, which samples points
close to the current hyperplane estimate (Tong and Koller,, 2001). The second
term prefers examples that align with the direction of maximum posterior
covariance. Specifically, for $x^{T}\Sigma_{n}x<\frac{2}{\pi}P$, the second
term is a decreasing function of $x^{T}\Sigma_{n}x$, encouraging $x$ to align
with posterior covariance eigenvectors with large eigenvalues.

These two terms together can be interpreted as encouraging “exploitation” and
“exploration,” respectively: the first term encourages the selection of
examples that are close to the current estimate of $\theta$, exploiting this
estimate to only query examples whose labels are ambiguous. The second term
balances this exploitation by probing in directions of the hyperplane
posterior that have not yet been sufficiently explored, reducing uncertainty
about the hyperplane itself. Figure 2 visualizes this tradeoff in comparison
to uncertainty sampling, which only queries examples close to the current
hyperplane estimate and does not account for the fact that there may be
directions of the hyperplane posterior that have not been sufficiently
explored. This myopic behavior is an instance of _sampling bias_ , a well-
known phenomenon in active learning where a policy continually selects
examples that reinforce the learner’s belief in an incorrect hypothesis
(Dasgupta,, 2011; Beygelzimer et al.,, 2009; Farquhar et al.,, 2021). The
balance of exploitation and exploration terms in APM-LR helps prevent this
type of sampling bias, in a spirit similar to other active learning methods
that balance uncertainty reduction with diverse example selection (Dasgupta
and Hsu,, 2008; Huang et al.,, 2010).

An attractive computational feature of (4) is that the posterior mean and
covariance can be estimated _once_ at each selection iteration and then simply
projected onto each candidate example, resulting in a computational cost of
only $O(d^{2})$ per example evaluation. Note that these computational
advantages along with the natural balance between exploration and exploitation
in APM-LR emerged naturally from first-principles of feedback coding,
demonstrating the potential of identifying the capacity-achieving distribution
and applying APM as a universal means of designing geometrically intuitive,
computationally efficient active selection schemes.

##  4 Experimental Results

We evaluate the performance of APM-LR against baseline example selection
methods for logistic regression on a variety of datasets from different tasks,
as measured by holdout test accuracy and selection compute time.222Code at
https://github.com/siplab-gt/APM-LR For each method, we follow Yang and Loog,
(2018) and set the regularization parameter in (2) to $\lambda=0.01$, which we
solve with the LIBLINEAR solver (Fan et al.,, 2008). After each example is
labeled, we approximate $p_{\theta\mid\mathcal{L}_{n-1}}$ with a normal
distribution by applying the variational approximation described in Jaakkola
and Jordan, (2000), which is solved in only a few iterations of an
expectation-maximization procedure (referred to here as “VariationalEM”). The
final component needed to apply APM-LR is the selection of power constraint
$P$ in (4).

#### Selecting Power Constraint

Although our approach is rooted in feedback coding theory, regarding the power
constraint there are two key differences between our model and traditional
communications systems. First, unlike telecommunications systems that have
physical restrictions such as limited battery levels, in our framework there
is no external prescription of the power budget $P$ and therefore we can
select any valid upper bound on the channel input power induced by the
unlabeled examples. Secondly, unlike coding schemes which globally maximize
information gain over the entire trajectory of channel inputs, we seek to
myopically maximize the one-step information gain at every channel input.
Since the goal at each iteration is to separately solve a local information
maximization problem, there is no need for the power constraint $P$ to be
constant across iterations, and therefore we set a separate power constraint
$P_{n}$ for each iteration.

Since the selection of $P_{n}$ parameterizes the target distribution in APM-
LR, it is important for $P_{n}$ to be set as tight as possible so that the
target capacity-achieving distribution is well-matched to the set of feasible
channel input distributions. This is because at each iteration the capacity-
achieving distribution serves as a proxy for the optimal input distribution
induced by a real example, and a setting of $P_{n}$ that is too loose will
result in APM targeting a proxy that is not well-matched to the feasible input
distributions. To select a satisfactory setting of $P_{n}$, we derive an upper
bound on the channel input power to use as an implicit constraint.

Algorithm 1 Approximate Posterior Matching for Logistic Regression (APM-LR)

0: data pool $\mathcal{X}$, hyperparameter $\lambda>0$, horizon $N$, initial
training set $\mathcal{L}$

1: $\mu\leftarrow 0$, $\Sigma\leftarrow\frac{1}{\lambda}I$

2: $B\leftarrow\max_{x\in\mathcal{U}}\lVert x\rVert_{2}$

3: $\mathcal{U}\leftarrow\mathcal{X}$

4: for $n=1$ to $N$ do

5: $P\leftarrow B^{2}\lambda_{1}(\Sigma)$

6:
$x^{*}\leftarrow\operatorname*{arg\,min}_{x\in\mathcal{U}}(\mu^{T}x)^{2}+\Bigl{(}\sqrt{x^{T}\Sigma
x}-\sqrt{\frac{2}{\pi}P}\,\Bigr{)}^{2}$

7: $y^{*}\leftarrow\operatorname{ExpertLabel}(x^{*})$

8: $\mathcal{U}\leftarrow\mathcal{U}\setminus\\{x^{*}\\}$,
$\mathcal{L}\leftarrow\mathcal{L}\cup(x^{*},y^{*})$

9: $\mu,\Sigma\leftarrow\operatorname{VariationalEM}(\mathcal{L})$

10: $\theta^{*}\leftarrow\operatorname{A}(\mathcal{L})$ i.e., eq. (2)

11: end for

11: hyperplane $\theta^{*}$

Suppose for a given dataset that there exists a known $B>0$ such that $\lVert
x\rVert_{2}<B$ (this is a reasonable assumption in many real-world settings).
Let $\lambda_{1}(M)$ denote the largest magnitude eigenvalue of matrix $M$. We
then have (with expectations taken with respect to
$p_{L_{n}\mid\mathcal{L}_{n-1}}$)

$\operatorname{\mathbb{E}}[L_{n}^{2}]=x^{T}(\mu_{n}\mu_{n}^{T}+\Sigma_{n})x\leq
B^{2}\lambda_{1}(\mu_{n}\mu_{n}^{T}+\Sigma_{n}).$

For each $n$ we can therefore set
$P_{n}=B^{2}\lambda_{1}(\mu_{n}\mu_{n}^{T}+\Sigma_{n})$. In our experiments we
select a slightly modified parameter $P_{n}=B^{2}\lambda_{1}(\Sigma_{n})$,
which we justify as a more practical heuristic in Appendix B.1. We summarize
APM-LR in full in Algorithm 1, including power constraint calculation and
variational posterior updating.

#### Datasets

We follow previous work in active learning for logistic regression (Huang et
al.,, 2010; Yang and Loog,, 2018) and test each method on several UCI datasets
(Dua and Graff,, 2017) including _vehicle_ , _letter_ , _austra_ , and _wdbc_.
We also evaluate performance on several synthetic datasets including the
dataset depicted in Figure 2 (adapted from Huang et al., (2010)), which we
refer to as _cross_ (see Appendix B.2 for details on all datasets). For each
simulation trial, we first randomly divide the dataset into an equally-sized
data pool ($\mathcal{U}$) and held-out test set. We normalize $\mathcal{U}$ to
zero-mean and coordinate-wise unit-variance, and apply the same transformation
to the test set. Before evaluating each example selection method, the training
dataset ($\mathcal{L}$) is seeded to consist of one randomly selected labeled
example from each class.333Our experiments are synchronized across data
selection methods: each trial uses the same training/test split and seed
examples for each tested method.

#### Baseline Methods

We evaluate the following baseline methods, each described with their
computational cost per candidate example evaluation (see Appendix B.3 for
details):

  * •

_Uncertainty_ : select closest example to current hyperplane estimate (i.e.
$\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}x^{T}\widehat{\theta}_{n-1}$)
at cost $O(d)$. The action of Uncertainty sampling is comparable to that of
the first term in (4).

  * •

_Random_ : each example is selected uniformly at random from
$\mathcal{U}_{n}$, at $O(1)$ cost.

  * •

_MaxVar_ : to isolate the effect of the second term in (4), we evaluate a
control strategy that selects the example that induces the largest channel
input variance (i.e.
$\operatorname*{arg\,max}_{x\in\mathcal{U}_{n}}x^{T}\Sigma_{n}x$), at cost
$O(d^{2})$.

  * •

_InfoGain_ : selects the example with the largest information gain
$I(\theta;Y_{n}\mid\mathcal{L}_{n-1})$, estimated by sampling $s$ times from
the normally approximated hyperplane posterior (here we set $s=100$) and for
each candidate example evaluating a Monte Carlo approximation of information
gain, at $O(ds)$ cost.

  * •

_BALD_ : we approximate the logistic function $f(\ell)$ with a probit function
and apply the probit regression active learning method of Houlsby et al.,
(2011), at cost $O(d^{2})$. Like APM-LR, BALD approximates the action of
InfoGain and only requires the mean and covariance of the normally
approximated hyperplane posterior.

InfoGain is the most computationally intensive selection method, since it
requires a brute-force Monte Carlo approximation of information gain for each
candidate example. BALD and APM-LR have the next least expensive cost per
example at $O(d^{2})$, followed by Uncertainty and Random sampling.

(a) _letterDP_

(b) _austra_

(c) _cross_

Figure 3: Average test classification accuracy plotted against number of
labeled examples (error bars show $\pm 1$ standard error) across select UCI
datasets (a-b) and the synthetic _cross_ dataset (c, with legend shared with
a-b and omitted for visual clarity). Overall, APM-LR performs comparably to
other methods seeking to approximately maximize information gain. While
uncertainty sampling performs well on some datasets (a-b), it can fail in
cases where it suffers from sampling bias (c). Most of the tested active
learning methods (except the control, MaxVar) outperform random sampling. For
visual clarity we show different numbers of queried examples for each dataset.

#### Performance Comparison

In Figure 3, we compare the learning performance of each data selection method
by plotting holdout test accuracy against number of queried examples
(excluding the seed set) across select datasets (see Appendix B.4 for full
results). We generally find that the tested active data selection methods
outperform random sampling. The exception is MaxVar, which performs comparably
to random selection and worse than APM-LR. Although simple Uncertainty
sampling matches the performance of other active methods on several datasets
(Figure 3a-b) as previously observed by Yang and Loog,, in additional tests on
synthetic datasets we find that APM-LR outperforms uncertainty sampling. This
is the case for the _cross_ dataset (Figure 3(c)), demonstrating how
Uncertainty sampling can be susceptible to sampling bias that leads to
insufficient exploration (see Appendix B.6 for additional failure mode
analysis). These tests together lend evidence to the mixture of terms in (4)
having combined benefits over pure exploration of directions with large
posterior variance or pure exploitation of ambiguous examples with respect to
the current hyperplane estimate. Finally, APM-LR generally performs similarly
to InfoGain and BALD, both of which directly approximate the action of
information gain maximization, in contrast to APM’s geometric, indirect
approach.

| _letterDP_ | _austra_ | _cross_
---|---|---|---
APM-LR | $0.336$ | $0.150$ | $0.125$
Uncertainty | $0.149$ | $0.063$ | $0.053$
BALD | $4.230$ | $1.770$ | $1.521$
InfoGain | $12.755$ | $5.089$ | $2.722$
Random | $0.005$ | $0.003$ | $0.002$
MaxVar | $0.118$ | $0.050$ | $0.040$
Table 1: Comparison of median cumulative time (s) for each method to select
the first 40 examples (excluding seed points and time for model retraining).
Generally, APM-LR has a cost an order of magnitude lower than InfoGain and
BALD (which directly approximate the action of information maximization),
while Uncertainty, MaxVar, and Random sampling have the cheapest cost.

Table 1 depicts the computational cost for each method across select datasets
(see Appendix B.5 for full results and expanded timing evaluations). Similar
to the analysis in Yang and Loog, (2018), for each method we evaluate the
cumulative compute time to select the first 40 examples (excluding seed
examples and time for model retraining), and compute the median time over all
trials. We see that InfoGain is the most expensive of all methods, since it
directly approximates information gain with Monte Carlo sampling. BALD has the
next highest cost, followed by APM-LR — the two latter methods only require a
single computation of posterior mean and variance, which can be projected onto
each candidate example. Uncertainty sampling and random sampling have the
lowest computational cost.

Although BALD can also be computed using only the posterior mean and
covariance, it is unclear how the approximation in BALD can be applied beyond
probit regression. In contrast, the APM formulation in (3) can be applied
generally to _any_ active learning problem that can be decomposed into a
deterministic encoder and noisy channel, along with a known capacity-achieving
distribution. The combined results of Figure 3 and Table 1 suggest that the
universal APM approach of leveraging this analytical knowledge of the
capacity-achieving distribution affords a geometric active selection approach
that performs well in terms of both sample and computational complexity.

##  5 Conclusion

To our knowledge, our work is the first effort to both reframe active learning
as a feedback communications system and utilize analytical knowledge of the
corresponding capacity-achieving distribution to derive an active learning
scheme. The analytical and empirical results in this work for the special case
of logistic regression demonstrate the potential of this coding-based active
learning approach: information continuity results show how examples selected
with APM-LR have information gain approaching their maximum possible value,
APM-LR has a convenient geometrical formulation resulting from analytical
knowledge of the capacity-achieving distribution for logistic regression
(characterized here for the first time) that can lead to computationally
efficient example selection, and when tested on multiple datasets APM-LR
performs comparably to baseline active learning methods including brute-force
information maximization. APM-LR’s attractive balance between exploration and
exploitation emerged naturally from first-principles of channel coding,
extending beyond the common approach of uncertainty sampling.

More generally, a fundamental feature of Approximate Posterior Matching is
that analytical knowledge of the capacity-achieving distribution converts the
usually unwieldy _information maximization_ problem in active learning to a
_geometric_ problem. In logistic regression, this geometry led to
computational advantages over direct information maximization, and we
conjecture that similar benefits may emerge in more complex settings.
Additionally, the general formulation of APM in (3) presents several
opportunities to leverage existing computational algorithms to aid example
selection, including estimating $p^{*}_{L}$ when it is analytically unknown
(Blahut,, 1972; Arimoto,, 1972) and optimizing Wasserstein distances with
state-of-the-art methods (Peyré and Cuturi,, 2019). Overall, we believe that
our coding-theoretic approach opens several new directions for future work in
active learning.

## Acknowledgements

We thank the reviewers for their useful feedback and comments, as well as Rob
Nowak, John Lee, and other colleagues for insightful discussions. This work
was supported by NSF grant CCF-1350954, ONR grant N00014-15-1-2619, and the
IDEaS-TRIAD Research Scholarship under NSF grant 1740776. This research was
also supported in part through research cyberinfrastructure resources and
services provided by the Partnership for an Advanced Computing Environment
(PACE) at the Georgia Institute of Technology, Atlanta, Georgia, USA.

## References

  * Akce et al., (2010) Akce, A., Johnson, M., and Bretl, T. (2010).  Remote teleoperation of an unmanned aircraft with a brain-machine interface: Theory and preliminary results.  In 2010 IEEE International Conference on Robotics and Automation, pages 5322–5327.
  * Arias-Castro et al., (2013) Arias-Castro, E., Candes, E. J., and Davenport, M. A. (2013).  On the fundamental limits of adaptive sensing.  IEEE Transactions on Information Theory, 59(1):472–481.
  * Arimoto, (1972) Arimoto, S. (1972).  An algorithm for computing the capacity of arbitrary discrete memoryless channels.  IEEE Transactions on Information Theory, 18(1):14–20.
  * Arjovsky et al., (2017) Arjovsky, M., Chintala, S., and Bottou, L. (2017).  Wasserstein gan.
  * Ash et al., (2020) Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J., and Agarwal, A. (2020).  Deep batch active learning by diverse, uncertain gradient lower bounds.  In International Conference on Learning Representations.
  * Beluch et al., (2018) Beluch, W. H., Genewein, T., Nürnberger, A., and Köhler, J. M. (2018).  The power of ensembles for active learning in image classification.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
  * Beygelzimer et al., (2009) Beygelzimer, A., Dasgupta, S., and Langford, J. (2009).  Importance weighted active learning.  In Bottou, L. and Littman, M., editors, Proceedings of the 26th International Conference on Machine Learning, pages 49–56, Montreal. Omnipress.
  * Bishop, (2006) Bishop, C. M. (2006).  Pattern recognition and machine learning.  Information science and statistics. Springer, New York, NY.  Softcover published in 2016.
  * Blahut, (1972) Blahut, R. (1972).  Computation of channel capacity and rate-distortion functions.  IEEE Transactions on Information Theory, 18(4):460–473.
  * Burnashev and Zigangirov, (1974) Burnashev, M. V. and Zigangirov, K. (1974).  An interval estimation problem for controlled observations.  Problems of Information Transmission, 10(3):223––231.
  * Castro and Nowak, (2008) Castro, R. M. and Nowak, R. D. (2008).  Minimax bounds for active learning.  IEEE Transactions on Information Theory, 54(5):2339–2353.
  * Chen et al., (2015) Chen, Y., Hassani, S. H., Karbasi, A., and Krause, A. (2015).  Sequential information maximization: When is greedy near-optimal?  volume 40 of Proceedings of Machine Learning Research, pages 338–363, Paris, France. PMLR.
  * Chernoff, (1959) Chernoff, H. (1959).  Sequential design of experiments.  The Annals of Mathematical Statistics, 30(3):755–770.
  * Cover and Thomas, (2006) Cover, T. M. and Thomas, J. A. (2006).  Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing).  Wiley-Interscience, USA.
  * Dasgupta, (2011) Dasgupta, S. (2011).  Two faces of active learning.  Theoretical Computer Science, 412(19):1767–1781.  Algorithmic Learning Theory (ALT 2009).
  * Dasgupta and Hsu, (2008) Dasgupta, S. and Hsu, D. (2008).  Hierarchical sampling for active learning.  pages 208–215.
  * Dua and Graff, (2017) Dua, D. and Graff, C. (2017).  UCI machine learning repository.
  * Fan et al., (2008) Fan, R.-E., Chang, K.-W., Hsieh, C.-J., Wang, X.-R., and Lin, C.-J. (2008).  Liblinear: A library for large linear classification.  J. Mach. Learn. Res., 9:1871–1874.
  * Farquhar et al., (2021) Farquhar, S., Gal, Y., and Rainforth, T. (2021).  On statistical bias in active learning: How and when to fix it.  In International Conference on Learning Representations.
  * Gal et al., (2017) Gal, Y., Islam, R., and Ghahramani, Z. (2017).  Deep Bayesian active learning with image data.  volume 70 of Proceedings of Machine Learning Research, pages 1183–1192, International Convention Centre, Sydney, Australia. PMLR.
  * Houlsby et al., (2011) Houlsby, N., Huszár, F., Ghahramani, Z., and Lengyel, M. (2011).  Bayesian active learning for classification and preference learning.
  * Huang et al., (2010) Huang, S., Jin, R., and Zhou, Z.-H. (2010).  Active learning by querying informative and representative examples.  In Lafferty, J. D., Williams, C. K. I., Shawe-Taylor, J., Zemel, R. S., and Culotta, A., editors, Advances in Neural Information Processing Systems 23, pages 892–900. Curran Associates, Inc.
  * Jaakkola and Jordan, (2000) Jaakkola, T. S. and Jordan, M. I. (2000).  Bayesian parameter estimation via variational methods.  Statistics and Computing, 10(1):25–37.
  * Kirsch et al., (2019) Kirsch, A., van Amersfoort, J., and Gal, Y. (2019).  Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * Lindley, (1956) Lindley, D. V. (1956).  On a measure of the information provided by an experiment.  The Annals of Mathematical Statistics, 27(4):986–1005.
  * Liu, (2004) Liu, Y. (2004).  Active learning with support vector machine applied to gene expression data for cancer classification.  Journal of Chemical Information and Computer Sciences, 44(6):1936–1941.  PMID: 15554662.
  * Lovász and Vempala, (2007) Lovász, L. and Vempala, S. (2007).  The geometry of logconcave functions and sampling algorithms.  Random Structures & Algorithms, 30(3):307–358.
  * Ma and Coleman, (2011) Ma, R. and Coleman, T. P. (2011).  Generalizing the posterior matching scheme to higher dimensions via optimal transportation.  In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 96–102.
  * Ma et al., (2018) Ma, Y., Nowak, R., Rigollet, P., Zhang, X., and Zhu, X. (2018).  Teacher improves learning by selecting a training subset.
  * MacKay, (1992) MacKay, D. J. C. (1992).  Information-based objective functions for active data selection.  Neural Computation, 4(4):590–604.
  * Mérigot, (2011) Mérigot, Q. (2011).  A multiscale approach to optimal transport.  Computer Graphics Forum, 30(5):1583–1592.
  * Naghshvar et al., (2015) Naghshvar, M., Javidi, T., and Chaudhuri, K. (2015).  Bayesian active learning with non-persistent noise.  IEEE Transactions on Information Theory, 61(7):4080–4098.
  * Omar et al., (2010) Omar, C., Akce, A., Johnson, M., Bretl, T., Ma, R., Maclin, E., McCormick, M., and Coleman, T. P. (2010).  A feedback information-theoretic approach to the design of brain–computer interfaces.  International Journal of Human–Computer Interaction, 27(1):5–23.
  * Peyré and Cuturi, (2019) Peyré, G. and Cuturi, M. (2019).  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607.
  * Pinsler et al., (2019) Pinsler, R., Gordon, J., Nalisnick, E., and Hernández-Lobato, J. M. (2019).  Bayesian batch active learning as sparse subset approximation.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  * Saumard and Wellner, (2014) Saumard, A. and Wellner, J. A. (2014).  Log-concavity and strong log-concavity: a review.  Statistics surveys, 8:45–114.  27134693[pmid].
  * Sener and Savarese, (2018) Sener, O. and Savarese, S. (2018).  Active learning for convolutional neural networks: A core-set approach.  In International Conference on Learning Representations.
  * Settles, (2009) Settles, B. (2009).  Active learning literature survey.  Technical report, University of Wisconsin-Madison Department of Computer Sciences.
  * Shannon, (1948) Shannon, C. E. (1948).  A mathematical theory of communication.  The Bell System Technical Journal, 27(3):379–423.
  * Shayevitz and Feder, (2011) Shayevitz, O. and Feder, M. (2011).  Optimal feedback communication via posterior matching.  IEEE Transactions on Information Theory, 57(3):1186–1222.
  * Siebert, (1987) Siebert, J. (1987).  Vehicle recognition using rule based methods.  Project report, Turing Institute, Glasgow.
  * Singh et al., (2009) Singh, J., Dabeer, O., and Madhow, U. (2009).  On the limits of communication with low-precision analog-to-digital conversion at the receiver.  IEEE Transactions on Communications, 57(12):3629–3639.
  * Sinha et al., (2019) Sinha, S., Ebrahimi, S., and Darrell, T. (2019).  Variational adversarial active learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV).
  * Tantiongloc et al., (2017) Tantiongloc, J., Mesa, D. A., Ma, R., Kim, S., Alzate, C. H., Camacho, J. J., Manian, V., and Coleman, T. P. (2017).  An information and control framework for optimizing user-compliant human–computer interfaces.  Proceedings of the IEEE, 105(2):273–285.
  * Tong and Koller, (2001) Tong, S. and Koller, D. (2001).  Support vector machine active learning with applications to text classification.  Journal of machine learning research, 2(Nov):45–66.
  * Villani, (2008) Villani, C. (2008).  Optimal transport: old and new, volume 338.  Springer Science & Business Media.
  * Warmuth et al., (2003) Warmuth, M. K., Liao, J., Rätsch, G., Mathieson, M., Putta, S., and Lemmen, C. (2003).  Active learning with support vector machines in the drug discovery process.  Journal of Chemical Information and Computer Sciences, 43(2):667–673.  PMID: 12653536.
  * Winkelbauer, (2014) Winkelbauer, A. (2014).  Moments and absolute moments of the normal distribution.
  * Xu and Raginsky, (2017) Xu, A. and Raginsky, M. (2017).  Information-theoretic analysis of generalization capability of learning algorithms.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems 30, pages 2524–2533. Curran Associates, Inc.
  * Yang and Loog, (2018) Yang, Y. and Loog, M. (2018).  A benchmark and comparison of active learning for logistic regression.  Pattern Recognition, 83:401 – 415.
  * Zhang et al., (2020) Zhang, C., Shen, J., and Awasthi, P. (2020).  Efficient active learning of sparse halfspaces with arbitrary bounded noise.

##  Appendix A Proofs of Analytical Results

###  A.1 Proof of Proposition 2.1

###### Proof.

Our proof follows closely to that of Singh et al., (2009) for the capacity of
the one-bit quantized Gaussian channel. We start by writing
$I(L;Y)=H(Y)-H(Y\mid L)$, where $H$ denotes the entropy of a discrete random
variable (Cover and Thomas,, 2006). $H(Y)$ is maximized at 1 bit, when
$p(Y=1)=p(Y=-1)=0.5$. Expanding $H(Y\mid L)$, we have $H(Y\mid
L)=\operatorname{\mathbb{E}}_{p_{L}}[h_{b}(p(Y=1\mid
L))]=\operatorname{\mathbb{E}}_{p_{L}}[h_{b}(f(L))]$.

For distribution $p_{L}$, consider its symmetrized distribution
$\widetilde{p}_{L}(\ell)=\frac{1}{2}p_{L}(\ell)+\frac{1}{2}p_{L}(-\ell)$ and
the expectation of any even function $e(\cdot)$ over
$\widetilde{p}_{L}(\ell)$:

$\displaystyle E_{\widetilde{p}_{L}}[e(L)]$
$\displaystyle=\int_{-\infty}^{\infty}\biggl{(}\frac{1}{2}p_{L}(\ell)+\frac{1}{2}p_{L}(-\ell)\biggr{)}e(\ell)d\ell$
$\displaystyle=\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)e(\ell)d\ell+\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(-\ell)e(\ell)d\ell$
$\displaystyle=\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)e(\ell)d\ell+\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)e(-\ell)d\ell$
change of variables
$\displaystyle=\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)e(\ell)d\ell+\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)e(\ell)d\ell$
$e(\ell)$ is even
$\displaystyle=\frac{1}{2}E_{p_{L}}[e(L)]+\frac{1}{2}E_{p_{L}}[e(L)]$
$\displaystyle=E_{p_{L}}[e(L)]$

Observe that $h_{b}$ is symmetric about $0.5$, i.e. for $x\in[-0.5,0.5]$,
$h_{b}(0.5+x)=h_{b}(0.5-x)$. Combining this with the fact that $f(\ell)-0.5$
is an odd function (i.e. $f(-\ell)-0.5=-(f(\ell)-0.5))$, we have

$h_{b}(f(-\ell))=h_{b}(f(-\ell)-0.5+0.5)=h_{b}(-(f(\ell)-0.5)+0.5)=h_{b}((f(\ell)-0.5)+0.5)=h_{b}(f(\ell))$

and so $h_{b}(f(\ell))$ is an even function. Therefore, the conditional
entropy $H(Y\mid L)$ is equivalent when $L$ is distributed as $p_{L}$ or
$\widetilde{p}_{L}$, i.e.
$E_{\widetilde{p}_{L}}[h_{b}(f(L))]=E_{p_{L}}[h_{b}(f(L))]$.

We also have

$\displaystyle E_{\widetilde{p}_{L}}[f(L)]$
$\displaystyle=E_{\widetilde{p}_{L}}[f(L)-0.5]+0.5$
$\displaystyle=\int_{-\infty}^{\infty}\biggl{(}\frac{1}{2}p_{L}(\ell)+\frac{1}{2}p_{L}(-\ell)\biggr{)}(f(\ell)-0.5)d\ell+0.5$
$\displaystyle=\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)(f(\ell)-0.5)d\ell+\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(-\ell)(f(\ell)-0.5)d\ell+0.5$
$\displaystyle=\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)(f(\ell)-0.5)d\ell+\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)(f(-\ell)-0.5)d\ell+0.5$
change of variables
$\displaystyle=\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)(f(\ell)-0.5)d\ell-\frac{1}{2}\int_{-\infty}^{\infty}p_{L}(\ell)(f(\ell)-0.5)d\ell+0.5$
$(f(\ell)-0.5)$ is odd $\displaystyle=0.5$

and so under $\widetilde{p}_{L}$,
$p(Y=1)=\operatorname{\mathbb{E}}_{\widetilde{p}_{L}}[f(L)]=0.5$ and $H(Y)$ is
maximized at 1 bit.

Combining these facts, we have

$I(\widetilde{p}_{L},f)=1-E_{\widetilde{p}_{L}}[h_{b}(f(L))]=1-E_{p_{L}}[h_{b}(f(L))]\geq
h_{b}(E_{p_{L}}[f(L)])-E_{p_{L}}[h_{b}(f(L))]=I(p_{L},f)$

and so symmetrizing a distribution can only increase $I(L;Y)$. Furthermore,
since $\ell^{2}$ is even we have
$\operatorname{\mathbb{E}}_{\widetilde{p}_{L}}[L^{2}]=\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]$.
Therefore, when evaluating the capacity of channel with transition probability
$f$ under power constraint $P$, we only consider symmetric distributions since
for every $p_{L}\in\mathcal{C}_{P}$ there exists a symmetric distribution
$\widetilde{p}_{L}\in\mathcal{C}_{P}$ satisfying $I(\widetilde{p}_{L},f)\geq
I(p_{L},f)$. We solve for the capacity-achieving distribution over the set of
symmetric distributions in $\mathcal{C}_{P}$:

$\displaystyle p_{L}^{*}$
$\displaystyle=\operatorname*{arg\,max}_{\begin{subarray}{c}\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]\leq
P\\\ p_{L}(\ell)=p_{L}(-\ell)\end{subarray}}I(p_{L},f)$ (5)
$\displaystyle=\operatorname*{arg\,max}_{\begin{subarray}{c}\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]\leq
P\\\ p_{L}(\ell)=p_{L}(-\ell)\end{subarray}}1-E_{p_{L}}[h_{b}(f(L))]$
$\displaystyle=\operatorname*{arg\,min}_{\begin{subarray}{c}\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]\leq
P\\\ p_{L}(\ell)=p_{L}(-\ell)\end{subarray}}E_{p_{L}}[h_{b}(f(L))]$ (6)

Since $h_{b}(f(\ell))$ is even,
$h_{b}(f(\ell))=h_{b}(f(\lvert\ell\rvert))=h_{b}(f(\sqrt{\ell^{2}}))$.
Omitting calculations, we have

$\frac{d^{2}}{du^{2}}h_{b}(f(\sqrt{u}))=(\log_{2}e)\frac{\tanh(\frac{\sqrt{u}}{2})\operatorname{sech}^{2}(\frac{\sqrt{u}}{2})}{16\sqrt{u}}$

which is non-negative for $u>0$ and therefore $h_{b}(f(\sqrt{u}))$ (which is
continuous on $u\geq 0)$ is convex on $u\geq 0$. We then have

$E_{p_{L}}[h_{b}(f(L))]=E_{p_{L}}\bigl{[}h_{b}\bigl{(}f\bigl{(}\sqrt{L^{2}}\bigr{)}\bigr{)}\bigr{]}\stackrel{{\scriptstyle(a)}}{{\geq}}h_{b}\Bigl{(}f\Bigl{(}\sqrt{E_{p_{L}}[L^{2}]}\Bigr{)}\Bigr{)}\stackrel{{\scriptstyle(b)}}{{\geq}}h_{b}\bigl{(}f\bigl{(}\sqrt{P}\bigr{)}\bigr{)}$

where Jensen’s inequality is used in (a) (Cover and Thomas,, 2006), with
equality if and only if $L^{2}$ is constant, and (b) results from the power
constraint $E_{p_{L}}[L^{2}]\leq P$ and the fact that $h_{b}(f(\sqrt{u}))$ is
monotonically decreasing for $u\geq 0$. For symmetric $p_{L}$, equality in (a)
is achieved if $p_{L}=B_{t}$ for some $t>0$. By setting $t=\sqrt{P}$, equality
in (b) is also achieved, and so $B_{\sqrt{P}}$ minimizes (6) (and therefore
maximizes (5)). The maximum value in (5), which is equal to capacity $C$, is
then

$I(B_{\sqrt{P}},f)=1-\operatorname{\mathbb{E}}_{B_{\sqrt{P}}}[h_{b}(f(L))]=1-\frac{1}{2}h_{b}(f(\sqrt{P}))-\frac{1}{2}h_{b}(f(-\sqrt{P}))=1-h_{b}(f(\sqrt{P})).\qed$

###  A.2 Proof of Proposition 2.2

###### Proof.

Since $p_{\theta}$ is log-concave, then
$p_{\theta\mid\mathcal{L}_{n-1}}(\theta)\propto
p_{\theta}(\theta)\prod_{i=1}^{n-1}p(Y=y_{i}\mid x_{i},\theta)$ is also log-
concave since it is the product of log-concave functions (Saumard and
Wellner,, 2014). Since marginals of log-concave distributions are log-concave
(Lovász and Vempala,, 2007), $L_{n}=x_{n}^{T}\theta$ is log-concave for any
$x_{n}$ under the distribution $p_{\theta\mid\mathcal{L}{n-1}}$. However, we
know from Proposition 2.1 that $p^{*}_{L}$ for logistic regression is a sum of
mass points, which is not log-concave. Therefore no $x_{n}$ exists which can
induce $p^{*}_{L}$ from $h$. ∎

###  A.3 Proof of Theorem 3.1

###### Proof.

In the following, suppose that $p_{L}\in\mathcal{C}_{P}$, and let
$H_{p_{L}}(Y)=h_{b}(\operatorname{\mathbb{E}}_{p_{L}}[f(L)])$ and
$H_{p_{L}}(Y\mid L)=\operatorname{\mathbb{E}}_{p_{L}}[h_{b}(f(L))]$. $f(\ell)$
is $K_{1}$-Lipschitz, where $K_{1}=0.25$, and $h_{b}(f(\ell))$ is
$K_{2}$-Lipschitz, where $K_{2}\approx 0.32$.

$\displaystyle\lvert I(p_{L},f)-I(B_{t},f)\rvert$ $\displaystyle=\lvert
H_{p_{L}}(Y)-H_{p_{L}}(Y\mid L)-(H_{B_{t}}(Y)-H_{B_{t}}(Y\mid L))\rvert$
$\displaystyle\leq\lvert H_{p_{L}}(Y)-H_{B_{t}}(Y))\rvert+\lvert
H_{p_{L}}(Y\mid L)-H_{B_{t}}(Y\mid L)\rvert$ $\displaystyle=\lvert
h_{b}(\operatorname{\mathbb{E}}_{p_{L}}[f(L)])-h_{b}(\operatorname{\mathbb{E}}_{B_{t}}[f(L)])\rvert+\biggl{\lvert}\int_{\ell}h_{b}(f(\ell))p_{L}(\ell)d\ell-\int_{\ell}h_{b}(f(\ell))B_{t}(\ell)d\ell\biggr{\rvert}$

Assume that there exists $\varepsilon\in(0,0.5)$ such that
$\varepsilon\leq\operatorname{\mathbb{E}}_{p_{L}}[f(L)]\leq 1-\varepsilon$.
For $\ell\in(\varepsilon,1-\varepsilon)$, $h_{b}$ is
$\log_{2}\frac{1-\varepsilon}{\varepsilon}$-Lipschitz. Since
$\varepsilon<\operatorname{\mathbb{E}}_{p_{L}}[f(L)]<1-\varepsilon$ by
assumption and $B_{t}$ satisfies
$\varepsilon<\operatorname{\mathbb{E}}_{B_{t}}[f(L)]<1-\varepsilon$ since
$\operatorname{\mathbb{E}}_{B_{t}}[f(L)]=0.5$, we have

$\displaystyle\lvert
h_{b}(\operatorname{\mathbb{E}}_{p_{L}}[f(L)])-h_{b}(\operatorname{\mathbb{E}}_{B_{t}}[f(L)])\rvert$
$\displaystyle\leq\log_{2}\Bigl{(}\frac{1-\varepsilon}{\varepsilon}\Bigr{)}\lvert\operatorname{\mathbb{E}}_{p_{L}}[f(L)]-\operatorname{\mathbb{E}}_{B_{t}}[f(L)]\rvert$
$\displaystyle=\log_{2}\Bigl{(}\frac{1-\varepsilon}{\varepsilon}\Bigr{)}\biggl{\lvert}\int_{\ell}f(\ell)p_{L}(\ell)d\ell-\int_{\ell}f(\ell)B_{t}(\ell)d\ell\biggr{\rvert}$

which implies

$\lvert
I(p_{L},f)-I(B_{t},f)\rvert\leq\log_{2}\Bigl{(}\frac{1-\varepsilon}{\varepsilon}\Bigr{)}\biggl{\lvert}\int_{\ell}f(\ell)p_{L}(\ell)d\ell-\int_{\ell}f(\ell)B_{t}(\ell)d\ell\biggr{\rvert}+\biggl{\lvert}\int_{\ell}h_{b}(f(\ell))p_{L}(\ell)d\ell-\int_{\ell}h_{b}(f(\ell))B_{t}(\ell)d\ell\biggr{\rvert}$
(7)

To continue, we use the following result from Villani, (2008): defining
$P_{1}(\mathbb{R})\coloneqq\\{\mu^{\prime}:\operatorname{\mathbb{E}}_{\mu^{\prime}}[\lvert
L\rvert]<\infty\\}$, for any $\mu,\nu\in P_{1}(\mathbb{R})$ we have

$\sup_{\lVert f\rVert_{\mathrm{Lip}}\leq
1}\int_{\ell}f(\ell)\mu(\ell)d\ell-\int_{\ell}f(\ell)\nu(\ell)d\ell=W_{1}(\mu,\nu).$

Therefore, for any $K$-Lipschitz function $g$ we have that $\frac{g}{K}$ is
1-Lipschitz and so

$\displaystyle\biggl{\lvert}\int_{\ell}g(\ell)\mu(\ell)d\ell-\int_{\ell}g(\ell)\nu(\ell)d\ell\biggr{\rvert}$
$\displaystyle=K\biggl{\lvert}\int_{\ell}\frac{g(\ell)}{K}\mu(\ell)d\ell-\int_{\ell}\frac{g(\ell)}{K}\nu(\ell)d\ell\biggr{\rvert}$
$\displaystyle=K\max\biggl{\\{}\int_{\ell}\frac{g(\ell)}{K}\mu(\ell)d\ell-\int_{\ell}\frac{g(\ell)}{K}\nu(\ell)d\ell,\int_{\ell}\frac{-g(\ell)}{K}\mu(\ell)d\ell-\int_{\ell}\frac{-g(\ell)}{K}\nu(\ell)d\ell\biggr{\\}}$
$\displaystyle\leq K\sup_{\lVert f\rVert_{\mathrm{Lip}}\leq
1}\int_{\ell}f(\ell)\mu(\ell)d\ell-\int_{\ell}f(\ell)\nu(\ell)d\ell$
$\displaystyle\leq KW_{1}(\mu,\nu)$ $\displaystyle\leq KW_{2}(\mu,\nu)$ (8)

where the last inequality is from $W_{1}(\mu,\nu)\leq W_{2}(\mu,\nu)$
(Villani,, 2008).

To apply this inequality to both expressions in (7), we first verify that
$p_{L},B_{t}\in P_{1}(\mathbb{R})$. $\operatorname{\mathbb{E}}_{B_{t}}[\lvert
L\rvert]=t<\infty$, and

$\operatorname{\mathbb{E}}_{p_{L}}[\lvert
L\rvert]=\operatorname{\mathbb{E}}_{p_{L}}\Bigl{[}\sqrt{L^{2}}\Bigr{]}\stackrel{{\scriptstyle(a)}}{{\leq}}\sqrt{\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]}\stackrel{{\scriptstyle(b)}}{{\leq}}\sqrt{P}<\infty$

where (a) results from Jensen’s inequality with the concavity of
$\sqrt{\cdot}$, and (b) is since $\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]\leq
P$ by assumption and $\sqrt{\cdot}$ is monotonically increasing. Applying (8)
separately to both terms in (7), we have

$\lvert
I(p_{L},f)-I(B_{t},f)\rvert\leq\biggl{(}K_{1}\log_{2}\Bigl{(}\frac{1-\varepsilon}{\varepsilon}\Bigr{)}+K_{2}\biggr{)}W_{2}(p_{L},B_{t})$
(9)

Finally, we compute a valid value of $\varepsilon$ for all
$p_{L}\in\mathcal{C}_{P}$. First note that $f(\ell)<0.5$ for $\ell<0$ and
$f(\ell)\geq 0.5$ for $\ell\geq 0$, implying that $f(\ell)\leq
f(\lvert\ell\rvert)\;\forall\ell$. Next note that $f(\sqrt{u})$ is concave on
$u\geq 0$, since for any $u,v\in[0,\infty)$ and any $0<\phi<1$

$\displaystyle f(\sqrt{\phi u+(1-\phi)v})$ $\displaystyle\geq
f(\phi\sqrt{u}+(1-\phi)\sqrt{v})$ since $f$ is monotonically increasing and
$\sqrt{\cdot}$ is concave. $\displaystyle\geq\phi
f(\sqrt{u})+(1-\phi)f(\sqrt{v})$

since $f$ is concave on $\mathbb{R}_{\geq 0}$. This can be shown by
considering

$\frac{d^{2}}{du^{2}}f(u)=\frac{e^{u}}{(1+e^{u})^{3}}(1-e^{u})\leq 0\;\forall
u\geq 0$

Combining these facts, we have

$\displaystyle\operatorname{\mathbb{E}}_{p_{L}}[f(L)]$
$\displaystyle\leq\operatorname{\mathbb{E}}_{p_{L}}[f(\lvert L\rvert)]$ since
$f(\ell)\leq f(\lvert\ell\rvert)$
$\displaystyle=\operatorname{\mathbb{E}}_{p_{L}}\bigl{[}f\bigl{(}\sqrt{L^{2}}\bigr{)}\bigr{]}$
$\displaystyle\leq
f\Bigl{(}\sqrt{\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]}\Bigr{)}$ from
Jensen’s inequality with the concavity of $f(\sqrt{\cdot})$ $\displaystyle\leq
f(\sqrt{P})$

since $f(\sqrt{\cdot})$ is monotonically increasing, and by assumption
$E_{p_{L}}[L^{2}]\leq P$. Similarly,
$\operatorname{\mathbb{E}}_{p_{L}}[1-f(L)]\leq f(\sqrt{P})$, and therefore we
can set $\varepsilon=1-f(\sqrt{P})$. Applying this choice of $\varepsilon$ to
(9) we have

$\lvert
I(p_{L},f)-I(B_{t},f)\rvert\leq\biggl{(}K_{1}\log_{2}\biggl{(}\frac{f(\sqrt{P})}{1-f(\sqrt{P})}\biggr{)}+K_{2}\biggr{)}W_{2}(p_{L},B_{t})$

and can set
$K_{P}=K_{1}\log_{2}\biggl{(}\frac{f(\sqrt{P})}{1-f(\sqrt{P})}\biggr{)}+K_{2}$
to obtain $\lvert I(p_{L},f)-I(B_{t},f)\rvert\leq K_{P}W_{2}(p_{L},B_{t})$.

Recall that $C=\max_{p_{L}\in\mathcal{C}_{P}}I(p_{L},f)=I(B_{\sqrt{P}},f)$ and
$\widetilde{C}_{n}=\max_{x\in\mathcal{U}_{n}}I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)$.
By assumption, $P$ is selected such that
$p_{L_{n}\mid\mathcal{L}_{n-1}}\in\mathcal{C}_{P}$ for any
$x\in\mathcal{U}_{n}$, which implies $I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)\leq
C$ for any $x\in\mathcal{U}_{n}$ and hence $\widetilde{C}_{n}\leq C$.
Combining these facts, we have

$\widetilde{C}_{n}-I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)\leq
C-I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)=\lvert
I(B_{\sqrt{P}},f)-I(p_{L_{n}\mid\mathcal{L}_{n-1}},f)\rvert\leq
K_{P}W_{2}(p_{L_{n}\mid\mathcal{L}_{n-1}},B_{\sqrt{P}}).\qed$

###  A.4 Proof of Proposition 3.2

###### Proof.

Adopting notation from Mérigot, (2011), let $S$ denote a finite set of points
in $\mathbb{R}$, and $w\colon S\to\mathbb{R}$ a weight vector. Define
$\operatorname{Vor}_{S}^{w}(p)=\\{\ell:\lVert\ell-p\rVert_{2}^{2}-w(p)\leq\lVert\ell-q\rVert_{2}^{2}-w(q)\enspace\forall
q\in S\\}$.

Let $\mu$ be a given probability measure with density $p_{L}$. Consider
$S=\\{-t,t\\}$, with the corresponding measure $B_{t}=\sum_{p\in
S}\frac{1}{2}\delta_{p}=\frac{1}{2}\delta_{-t}+\frac{1}{2}\delta_{t}$. Let
$w^{*}(-t)=2t\operatorname{med}_{p_{L}}(L)$, and
$w^{*}(t)=-2t\operatorname{med}_{p_{L}}(t)$. We have

$\displaystyle\operatorname{Vor}_{S}^{w^{*}}(-t)$
$\displaystyle=\\{\ell:\lVert\ell+t\rVert_{2}^{2}-w^{*}(-t)\leq\lVert\ell-q\rVert_{2}^{2}-w^{*}(q)\enspace\forall
q\in\\{-t,t\\}\\}$
$\displaystyle=\\{\ell:\lVert\ell+t\rVert_{2}^{2}-w^{*}(-t)\leq\lVert\ell-t\rVert_{2}^{2}-w^{*}(t)\\}$
$\displaystyle=\\{\ell:\lVert\ell+t\rVert_{2}^{2}-2t\operatorname{med}_{p_{L}}(L)\leq\lVert\ell-t\rVert_{2}^{2}+2t\operatorname{med}_{p_{L}}(L)\\}$
$\displaystyle=\\{\ell:\ell\leq\operatorname{med}_{p_{L}}(L)\\}$

and similarly
$\operatorname{Vor}_{S}^{w^{*}}(t)=\\{\ell:\ell\geq\operatorname{med}_{p_{L}}(L)\\}$.
We have

$\int_{\operatorname{Vor}_{S}^{w^{*}}(-t)}p_{L}(\ell)d\ell=\int_{\ell\leq\operatorname{med}_{p_{L}}(L)}p_{L}(\ell)d\ell=\frac{1}{2}$

and similarly
$\int_{\operatorname{Vor}_{S}^{w^{*}}(t)}p_{L}(\ell)d\ell=\frac{1}{2}$.
Therefore, $w^{*}$ is _adapted_ to $(\mu,B_{t})$. By Theorem 2 of Mérigot,
(2011), a map $T_{S}^{w^{*}}\colon\mathbb{R}\to\mathbb{R}$ exists which
realizes an optimal transport between $\mu$ and $B_{t}$. By Mérigot, (2011)
Theorem 1, we have

$\displaystyle W_{2}^{2}(\mu,B_{t})$
$\displaystyle=\int_{\operatorname{Vor}_{S}^{w^{*}}(-t)}\lVert\ell+t\rVert_{2}^{2}\;p_{L}(\ell)d\ell+\int_{\operatorname{Vor}_{S}^{w^{*}}(t)}\lVert\ell-t\rVert_{2}^{2}\;p_{L}(\ell)d\ell$
$\displaystyle=\int_{\ell\leq\operatorname{med}_{p_{L}}(L)}\lVert\ell+t\rVert_{2}^{2}\;p_{L}(\ell)d\ell+\int_{\ell\geq\operatorname{med}_{p_{L}}(L)}\lVert\ell-t\rVert_{2}^{2}\;p_{L}(\ell)d\ell$
$\displaystyle=\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]+t^{2}-2t\biggl{(}\int_{\ell\geq\operatorname{med}_{p_{L}}(L)}\ell\;p_{L}(\ell)d\ell-\int_{\ell\leq\operatorname{med}_{p_{L}}(L)}\ell\;p_{L}(\ell)d\ell\biggr{)}$
$\displaystyle=\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]+t^{2}-2t\biggl{(}\int_{\ell\geq\operatorname{med}_{p_{L}}(L)}(\ell-\operatorname{med}_{p_{L}}(L))\;p_{L}(\ell)d\ell+\int_{\ell\leq\operatorname{med}_{p_{L}}(L)}(\operatorname{med}_{p_{L}}(L)-\ell)\;p_{L}(\ell)d\ell\biggr{)}$
$\displaystyle=\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]+t^{2}-2t\biggl{(}\int_{\ell\geq\operatorname{med}_{p_{L}}(L)}\lvert\ell-\operatorname{med}_{p_{L}}(L)\rvert\;p_{L}(\ell)d\ell+\int_{\ell\leq\operatorname{med}_{p_{L}}(L)}\lvert\ell-\operatorname{med}_{p_{L}}(L)\rvert\;p_{L}(\ell)d\ell\biggr{)}$
$\displaystyle=\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]+t^{2}-2t\operatorname{\mathbb{E}}_{p_{L}}[\lvert
L-\operatorname{med}_{p_{L}}(L)\rvert]\qed$

###  A.5 Proof of Corollary 3.2.1

###### Proof.

Let $p_{L}\sim\mathcal{N}(\mu,\sigma^{2})$. We have
$\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]=\operatorname{\mathbb{E}}_{p_{L}}[L]^{2}+\operatorname{Var}_{p_{L}}(L)=\mu^{2}+\sigma^{2}$,
and $\operatorname{\mathbb{E}}_{p_{L}}[\lvert
L-\operatorname{med}_{p_{L}}(L)\rvert]=\operatorname{\mathbb{E}}_{p_{L}}[\lvert
L-\mu\rvert]=\sigma\sqrt{\frac{2}{\pi}}$ (Winkelbauer,, 2014). Hence
$W_{2}^{2}(p_{L},B_{t})=\operatorname{\mathbb{E}}_{p_{L}}[L^{2}]+t^{2}-2t\operatorname{\mathbb{E}}_{p_{L}}[\lvert
L-\operatorname{med}_{p_{L}}(L)\rvert]=\mu^{2}+\sigma^{2}+t^{2}-2\sqrt{\frac{2}{\pi}}t\sigma$.
Completing the square, we have the desired result. ∎

##  Appendix B Experiment Details

###  B.1 Selection of Power Constraint

Recall that APM-LR minimizes an objective function consisting of a mixture of
two terms, reprinted below:

$\pi_{n}(\mathcal{L}_{n-1})=\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}\enspace(\mu_{n}^{T}x)^{2}+\biggl{(}\sqrt{x^{T}\Sigma_{n}x}-\sqrt{\frac{2}{\pi}P_{n}}\biggr{)}^{2}.$
(10)

The first term in (10), which is independent of $P_{n}$, encourages $x$ to lie
orthogonal to the hyperplane posterior mean, $\mu_{n}$. For all such $x$
satisfying $\mu_{n}^{T}x=0$, we have
$\operatorname{\mathbb{E}}[L_{n}]=\mu_{n}^{T}x=0$ and

$\operatorname{\mathbb{E}}[L_{n}^{2}]=(\mu_{n}^{T}x)^{2}+x^{T}\Sigma_{n}x=x^{T}\Sigma_{n}x\leq
B^{2}\lambda_{1}(\Sigma_{n})$

where expectations are taken with respect to $p_{L_{n}\mid\mathcal{L}_{n-1}}$.
Therefore $P_{n}=B^{2}\lambda_{1}(\Sigma_{n})$ is a valid power constraint for
the set of examples that induce zero-mean input distributions. This set
arguably contains the “best” candidate examples, since if
$(\mu_{n}^{T}x)^{2}\gg 0$ then the objective in (10) will be large. For this
reason we set $P_{n}=B^{2}\lambda_{1}(\Sigma_{n})$ in our experiments, as
opposed to the power constraint of
$B^{2}\lambda_{1}(\mu_{n}\mu_{n}^{T}+\Sigma_{n})$ which is valid for all
examples but is loose for examples encouraged by the first term in (10).

###  B.2 Dataset Information

In Table 2 we describe the datasets used in our experiments. Several datasets
have multiple classes: in this case, we select a two-class dataset partition
by either grouping individual classes together into super-classes, or simply
training on a subset of the classes. In our experiments we treat each class
partition as its own dataset, and refer to each partition by a nickname. All
datasets except for _clouds_ , _cross_ , and _horseshoe_ come from the UCI
Machine Learning Repository (Dua and Graff,, 2017); several UCI datasets have
additional citations, which are listed next to their names.

Nickname |  Dataset |  Class partition |  # of features |  # of examples
---|---|---|---|---
_vehicle-full_ |  Vehicle Silhouettes (Siebert,, 1987) |  $Y=-1$: ‘saab’ or ‘opel’
$Y=1$: ‘bus’ or ‘van’ |  18 |  846
_vehicle-cars_ |  Vehicle Silhouettes (Siebert,, 1987) |  $Y=-1$: ‘saab’
$Y=1$: ‘opel’ |  18 |  429
_vehicle-transport_ |  Vehicle Silhouettes (Siebert,, 1987) |  $Y=-1$: ‘bus’
$Y=1$: ‘van’ |  18 |  417
_letterDP_ |  Letter Recognition |  $Y=-1$: ‘D’
$Y=1$: ‘P’ |  16 |  1608
_letterEF_ |  Letter Recognition |  $Y=-1$: ‘E’
$Y=1$: ‘F’ |  16 |  1543
_letterIJ_ |  Letter Recognition |  $Y=-1$: ‘I’
$Y=1$: ‘J’ |  16 |  1502
_letterMN_ |  Letter Recognition |  $Y=-1$: ‘M’
$Y=1$: ‘N’ |  16 |  1575
_letterUV_ |  Letter Recognition |  $Y=-1$: ‘U’
$Y=1$: ‘V’ |  16 |  1577
_letterVY_ |  Letter Recognition |  $Y=-1$: ‘V’
$Y=1$: ‘Y’ |  16 |  1550
_austra_ |  Australian Credit Approval |  $Y=-1$: ‘0’
$Y=1$: ‘1’ |  14 |  690
_wdbc_ |  Breast Cancer Wisconsin (Diagnostic) |  $Y=-1$: ‘M’
$Y=1$: ‘B’ |  30 |  569
_clouds_ |  Synth1
(Yang and Loog,, 2018) |  $Y=-1$: ‘-1’
$Y=1$: ‘1’ |  2 |  600
_cross_ |  Synth2
(Yang and Loog,, 2018) |  $Y=-1$: ‘-1’
$Y=1$: ‘1’ |  2 |  600
_horseshoe_ |  Synth3
(Yang and Loog,, 2018) |  $Y=-1$: ‘-1’
$Y=1$: ‘1’ |  2 |  600
Table 2: Full dataset information

###  B.3 Baseline Methods Details

Below we elaborate on the BALD and InfoGain baseline selection methods:

#### InfoGain

We can directly approximate information gain
$I(\theta;Y\mid\mathcal{L}_{n-1})$ with a Monte Carlo approximation over $s$
samples from
$p_{\theta\mid\mathcal{L}_{n-1}}\sim\mathcal{N}(\mu_{n},\Sigma_{n})$:

$\displaystyle I(\theta;Y\mid\mathcal{L}_{n-1})$
$\displaystyle=h_{b}(\operatorname{\mathbb{E}}_{p_{\theta\mid\mathcal{L}_{n-1}}}[f(\theta^{T}x_{n})])-\operatorname{\mathbb{E}}_{p_{\theta\mid\mathcal{L}_{n-1}}}[h_{b}(f(\theta^{T}x_{n}))]$
$\displaystyle\approx
h_{b}\biggl{(}\frac{1}{s}\sum_{i=1}^{s}f(\theta_{i}^{T}x_{n})\biggr{)}-\frac{1}{s}\sum_{i=1}^{s}h_{b}\biggl{(}f(\theta_{i}^{T}x_{n})\biggr{)}\qquad\theta_{i}\sim
p_{\theta\mid\mathcal{L}_{n-1}}$ $\displaystyle\approx
h_{b}\biggl{(}\frac{1}{s}\sum_{i=1}^{s}f(\theta_{i}^{T}x_{n})\biggr{)}-\frac{1}{s}\sum_{i=1}^{s}h_{b}\biggl{(}f(\theta_{i}^{T}x_{n})\biggr{)}\qquad\theta_{i}\sim\mathcal{N}(\mu_{n},\Sigma_{n})$
(11)

Our “InfoGain” baseline selects the example $x_{n}\in\mathcal{U}_{n}$ that
maximizes the expression in (11), computed in $O(sd)$ time per candidate
example.

#### BALD

Consider a probit regression label distribution $p(Y=1\mid L)=\Phi(L)$, where
$\Phi$ is the standard normal cumulative distribution function. For
$p_{L}\sim\mathcal{N}(\mu,\sigma^{2})$, Houlsby et al., (2011) use a Taylor
expansion in the BALD algorithm to approximate $I(p_{L},\Phi(L))$ as

$I(p_{L},\Phi(L))\approx
h_{b}\biggl{(}\Phi\biggl{(}\frac{\mu}{\sqrt{\sigma^{2}+1}}\biggr{)}\biggr{)}-\frac{D\operatorname{exp}\Bigl{(}-\frac{\mu^{2}}{2(\sigma^{2}+D^{2})}\Bigr{)}}{\sqrt{\sigma^{2}+D^{2}}}$
(12)

where $D=\sqrt{\frac{\pi\ln 2}{2}}$. By equalizing derivatives at $L=0$, we
can approximate $f(L)\approx\Phi(kL)$ where $k=\sqrt{\frac{\pi}{8}}$ (Bishop,,
2006). Define $\widetilde{L}=kL$ and note that
$\widetilde{L}\sim\mathcal{N}(\widetilde{\mu},\widetilde{\sigma}^{2})$ for
$\widetilde{\mu}=k\mu$ and $\widetilde{\sigma}^{2}=k^{2}\sigma^{2}$. We can
then use the BALD approximation in (12) for logistic regression:

$\displaystyle I(p_{L},f(L))$ $\displaystyle\approx I(p_{L},\Phi(kL))$
$\displaystyle=h_{b}(\operatorname{\mathbb{E}}_{p_{L}}(\Phi(kL)))-\operatorname{\mathbb{E}}_{p_{L}}(h_{b}(\Phi(kL)))$
$\displaystyle=h_{b}(\operatorname{\mathbb{E}}_{p_{\widetilde{L}}}(\Phi(\widetilde{L})))-\operatorname{\mathbb{E}}_{p_{\widetilde{L}}}(h_{b}(\Phi(\widetilde{L})))$
$\displaystyle=I(p_{\widetilde{L}},\Phi(\widetilde{L}))$ $\displaystyle\approx
h_{b}\Biggl{(}\Phi\Biggl{(}\frac{k\mu}{\sqrt{k^{2}\sigma^{2}+1}}\Biggr{)}\Biggr{)}-\frac{D\operatorname{exp}\Bigl{(}-\frac{k^{2}\mu^{2}}{2(k^{2}\sigma^{2}+D^{2})}\Bigr{)}}{\sqrt{k^{2}\sigma^{2}+D^{2}}}$

Approximating
$p_{\theta\mid\mathcal{L}_{n-1}}\sim\mathcal{N}(\mu_{n},\Sigma_{n})$, we have
$p_{L_{n}\mid\mathcal{L}_{n-1}}\sim\mathcal{N}(\mu_{n}^{T}x_{n},x_{n}^{T}\Sigma_{n}x_{n})$
and so we can approximate

$I(p_{L_{n}\mid\mathcal{L}_{n-1}},f(L))\approx
h_{b}\Biggl{(}\Phi\Biggl{(}\frac{k\mu_{n}^{T}x_{n}}{\sqrt{k^{2}x_{n}^{T}\Sigma_{n}x_{n}+1}}\Biggr{)}\Biggr{)}-\frac{D\operatorname{exp}\Bigl{(}-\frac{k^{2}(\mu_{n}^{T}x_{n})^{2}}{2(k^{2}x_{n}^{T}\Sigma_{n}x_{n}+D^{2})}\Bigr{)}}{\sqrt{k^{2}x_{n}^{T}\Sigma_{n}x_{n}+D^{2}}}$
(13)

where $D=\sqrt{\frac{\pi\ln 2}{2}}$ and $k=\sqrt{\frac{\pi}{8}}$. Our “BALD”
baseline method selects the example $x_{n}\in\mathcal{U}_{n}$ that maximizes
the expression in (13), computed in $O(d^{2})$ time per candidate example.

#### Summary

For completeness, below we summarize all selection methods used in our
experiments. For any method utilizing a normal approximation to the hyperplane
posterior, let
$p_{\theta\mid\mathcal{L}_{n-1}}\sim\mathcal{N}(\mu_{n},\Sigma_{n})$. Let
$\widehat{\theta}_{n-1}=\operatorname{A}(\mathcal{L}_{n-1})$,
$D=\sqrt{\frac{\pi\ln 2}{2}}$, and $k=\sqrt{\frac{\pi}{8}}$.

APM-LR: $\displaystyle\quad
x_{n}=\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}\enspace(\mu_{n}^{T}x)^{2}+\biggl{(}\sqrt{x^{T}\Sigma_{n}x}-\sqrt{\frac{2}{\pi}P_{n}}\biggr{)}^{2}$
(14) Uncertainty: $\displaystyle\quad
x_{n}=\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}\enspace
x^{T}\widehat{\theta}_{n-1}$ Random: Select $x_{n}$ uniformly at random from
$\mathcal{U}_{n}$ MaxVar: $\displaystyle\quad
x_{n}=\operatorname*{arg\,max}_{x\in\mathcal{U}_{n}}\enspace x^{T}\Sigma_{n}x$
InfoGain: $\displaystyle\quad
x_{n}=\operatorname*{arg\,max}_{x\in\mathcal{U}_{n}}\enspace
h_{b}\biggl{(}\frac{1}{s}\sum_{i=1}^{s}f(\theta_{i}^{T}x_{n})\biggr{)}-\frac{1}{s}\sum_{i=1}^{s}h_{b}\biggl{(}f(\theta_{i}^{T}x_{n})\biggr{)}\qquad\theta_{i}\sim\mathcal{N}(\mu_{n},\Sigma_{n})$
BALD: $\displaystyle\quad
x_{n}=\operatorname*{arg\,max}_{x\in\mathcal{U}_{n}}\enspace
h_{b}\Biggl{(}\Phi\Biggl{(}\frac{k\mu_{n}^{T}x_{n}}{\sqrt{k^{2}x_{n}^{T}\Sigma_{n}x_{n}+1}}\Biggr{)}\Biggr{)}-\frac{D\operatorname{exp}\Bigl{(}-\frac{k^{2}(\mu_{n}^{T}x_{n})^{2}}{2(k^{2}x_{n}^{T}\Sigma_{n}x_{n}+D^{2})}\Bigr{)}}{\sqrt{k^{2}x_{n}^{T}\Sigma_{n}x_{n}+D^{2}}}$

###  B.4 Extended Test Accuracy Results

Below we plot average holdout test accuracy against number of queried
examples, excluding one initial seed point selected uniformly at random per
class. Error bars show $\pm 1$ standard error over 150 trials per method. For
visual clarity, we display different numbers of queried examples for each
dataset.

Figure 4 shows test accuracy across several two-class partitions of the
Vehicle Silhouettes dataset (see Table 2). In _vehicle-cars_ , Uncertainty,
InfoGain, and BALD fail to perform as well as MaxVar, Random, and APM-LR. As
noted in Yang and Loog, (2018), there are cases where Random sampling — or
more generally, selection methods that encourage dataset exploration — can
outperform methods that maximize information. In _vehicle-cars_ , it’s
possible that the “exploration” component in APM-LR encourages the selection
of satisfactory examples, which we investigate further in Section B.6.

(a) _vehicle-full_

(b) _vehicle-cars_

(c) _vehicle-transport_

Figure 4: Test accuracy on “Vehicle Silhouettes”

Figure 5 shows test accuracy across several two-class partitions of the Letter
Recognition dataset. All partitions show similar trends to _letterDP_ , which
was included in the paper body.

(a) _letterDP_

(b) _letterEF_

(c) _letterIJ_

(d) _letterMN_

(e) _letterUV_

(f) _letterVY_

Figure 5: Test accuracy on “Letter Recognition”

Figure 6 shows test accuracy across the remaining UCI datasets in Table 2. On
_wdbc_ , the active methods appear to have an average test accuracy that peaks
early and then gradually decreases. While this behavior merits further
investigation, we note that it is possible in some cases for a selected subset
of the full data pool to generalize better than when training on the entire
pool (Ma et al.,, 2018).

(a) _austra_

(b) _wdbc_

Figure 6: Miscellaneous UCI datasets

Figure 7 shows test accuracy across several synthetic datasets. On _clouds_
and _cross_ , Uncertainty sampling is outperformed by the other baseline
active learning methods, except MaxVar.

(a) _clouds_

(b) _cross_

(c) _horseshoe_

Figure 7: Synthetic datasets

###  B.5 Extended Computational Cost Results

All experiments were run on Intel Xeon Gold 6226 CPUs at 2.7 GHz. In Table 3
we present for all datasets the cumulative compute time (in seconds) needed
for each method to select the first 40 examples (excluding seed points). In
this first table, we exclude the compute time needed to retrain the logistic
regression model and perform the VariationalEM posterior update after each
example is selected, since these steps are common to all selection methods.
While some methods do not directly utilize the variational posterior in
selecting examples, we perform variational posterior updates for all data
selection methods since we consider the variational posterior to be part of
the Bayesian model produced by the training routine.

| APM-LR | Uncertainty | BALD | InfoGain | Random | MaxVar
---|---|---|---|---|---|---
_vehicle-full_ | $0.173$ | $0.077$ | $2.212$ | $7.166$ | $0.003$ | $0.061$
_vehicle-cars_ | $0.089$ | $0.039$ | $1.078$ | $3.462$ | $0.002$ | $0.030$
_vehicle-transport_ | $0.087$ | $0.037$ | $1.036$ | $3.306$ | $0.002$ | $0.029$
_letterDP_ | $0.336$ | $0.149$ | $4.230$ | $12.755$ | $0.005$ | $0.118$
_letterEF_ | $0.318$ | $0.143$ | $4.044$ | $12.188$ | $0.005$ | $0.113$
_letterIJ_ | $0.314$ | $0.139$ | $3.941$ | $11.879$ | $0.004$ | $0.110$
_letterMN_ | $0.331$ | $0.147$ | $4.170$ | $12.531$ | $0.005$ | $0.117$
_letterUV_ | $0.330$ | $0.145$ | $4.129$ | $12.429$ | $0.005$ | $0.115$
_letterVY_ | $0.318$ | $0.143$ | $4.063$ | $12.284$ | $0.004$ | $0.114$
_austra_ | $0.150$ | $0.063$ | $1.770$ | $5.089$ | $0.003$ | $0.050$
_wdbc_ | $0.125$ | $0.052$ | $1.480$ | $6.415$ | $0.003$ | $0.042$
_clouds_ | $0.119$ | $0.053$ | $1.522$ | $2.735$ | $0.002$ | $0.041$
_cross_ | $0.125$ | $0.053$ | $1.521$ | $2.722$ | $0.002$ | $0.040$
_horseshoe_ | $0.116$ | $0.053$ | $1.517$ | $2.731$ | $0.002$ | $0.040$
Table 3: Cumulative selection time: comparison of median cumulative time (s)
for each method to select the first 40 examples (excluding seed points).

Table 4 isolates the compute time needed for performing VariationalEM at each
input, summed over the first 40 examples. Interestingly, methods which are
primarily focused on data space exploration (MaxVar, Random) require more time
for variational posterior updating than exploitation methods (Uncertainty).
Since VariationalEM is an iterative procedure that we run with an adaptive
stopping rule (with convergence defined as the relative variational parameter
difference falling below $1\mathrm{e}{-6}$ between iterations), it presumably
requires more iterations to adjust to significant changes in the posterior
distribution due to variability in examples. Although less accurate of an
approximation than VariationalEM, using a Laplace posterior approximation
instead would have a constant update time per method (Jaakkola and Jordan,,
2000).

| APM-LR | Uncertainty | BALD | InfoGain | Random | MaxVar
---|---|---|---|---|---|---
_vehicle-full_ | $10.088$ | $4.540$ | $10.118$ | $9.729$ | $7.469$ | $18.064$
_vehicle-cars_ | $5.420$ | $4.412$ | $5.605$ | $5.475$ | $3.280$ | $4.558$
_vehicle-transport_ | $9.609$ | $5.814$ | $9.289$ | $9.083$ | $11.216$ | $21.058$
_letterDP_ | $7.618$ | $6.412$ | $6.904$ | $6.758$ | $10.694$ | $11.851$
_letterEF_ | $6.866$ | $5.701$ | $6.320$ | $6.160$ | $11.302$ | $10.755$
_letterIJ_ | $7.367$ | $5.724$ | $6.924$ | $6.708$ | $10.019$ | $9.846$
_letterMN_ | $8.190$ | $6.281$ | $7.615$ | $7.375$ | $10.082$ | $13.236$
_letterUV_ | $8.029$ | $6.556$ | $7.137$ | $7.075$ | $10.746$ | $12.585$
_letterVY_ | $7.463$ | $5.760$ | $7.142$ | $6.910$ | $8.234$ | $9.975$
_austra_ | $12.513$ | $6.451$ | $12.009$ | $11.645$ | $8.541$ | $13.580$
_wdbc_ | $17.966$ | $10.880$ | $14.183$ | $13.874$ | $20.763$ | $29.778$
_clouds_ | $1.221$ | $1.172$ | $1.156$ | $1.322$ | $3.201$ | $5.318$
_cross_ | $1.386$ | $2.417$ | $1.474$ | $1.537$ | $3.138$ | $4.453$
_horseshoe_ | $0.996$ | $0.908$ | $0.863$ | $0.931$ | $0.802$ | $1.208$
Table 4: Cumulative VariationalEM time: comparison of median cumulative time
(s) for each method to perform VariationalEM over the first 40 examples
(excluding seed points).

Table 5 depicts the total compute time needed for selecting each example,
performing VariationalEM, and retraining the logistic regression classifier at
each iteration, summed over the first 40 examples. The median time needed for
retraining the logistic regression classifier lies within 0.01 to 0.03 seconds
across all methods and datasets, and therefore contributes only marginally to
the total. While the spread of running times is more narrow than it would be
when only evaluating selection time, the same general trend holds that
InfoGain is more expensive than BALD and APM-LR.

| APM-LR | Uncertainty | BALD | InfoGain | Random | MaxVar
---|---|---|---|---|---|---
_vehicle-full_ | $10.288$ | $4.637$ | $12.365$ | $16.943$ | $7.493$ | $18.148$
_vehicle-cars_ | $5.532$ | $4.474$ | $6.727$ | $8.980$ | $3.306$ | $4.616$
_vehicle-transport_ | $9.721$ | $5.876$ | $10.341$ | $12.419$ | $11.238$ | $21.116$
_letterDP_ | $7.992$ | $6.583$ | $11.139$ | $19.534$ | $10.730$ | $11.995$
_letterEF_ | $7.215$ | $5.868$ | $10.396$ | $18.414$ | $11.330$ | $10.887$
_letterIJ_ | $7.716$ | $5.892$ | $10.896$ | $18.619$ | $10.048$ | $9.981$
_letterMN_ | $8.561$ | $6.455$ | $11.813$ | $19.991$ | $10.124$ | $13.374$
_letterUV_ | $8.399$ | $6.724$ | $11.294$ | $19.552$ | $10.781$ | $12.724$
_letterVY_ | $7.802$ | $5.931$ | $11.233$ | $19.233$ | $8.260$ | $10.118$
_austra_ | $12.690$ | $6.538$ | $13.801$ | $16.804$ | $8.574$ | $13.655$
_wdbc_ | $18.130$ | $10.968$ | $15.711$ | $20.323$ | $20.787$ | $29.842$
_clouds_ | $1.358$ | $1.241$ | $2.706$ | $4.122$ | $3.224$ | $5.385$
_cross_ | $1.534$ | $2.490$ | $3.028$ | $4.291$ | $3.159$ | $4.515$
_horseshoe_ | $1.134$ | $0.978$ | $2.405$ | $3.741$ | $0.819$ | $1.264$
Table 5: Cumulative running time: comparison of median cumulative run time (s)
for each method to select each example, perform VariationalEM, and retrain the
logistic regression classifier over the first 40 examples (excluding seed
points).

###  B.6 Failure Mode Analysis

While in many cases APM-LR performs comparably to InfoGain, BALD, and
Uncertainty while outperforming Random and MaxVar, the main exception in our
experiments is on _vehicle-cars_ (Figure 4(b)), where APM-LR, Random, and
MaxVar outperform InfoGain, BALD, and Uncertainty. Conceptually, what
differentiates these two classes of methods is that APM-LR, Random, and MaxVar
have explicit exploration components to their selection policies, while
InfoGain, BALD, and Uncertainty only seek to directly maximize information or
uncertainty. As we will demonstrate below, on _vehicle-cars_ this difference
in exploration correlates with significant differences in generalization
performance.

To isolate the effect of each term in APM-LR (eq. (14)) — corresponding to
exploitation and exploration — we simulated two pseudo-APM policies where only
one of the terms is active at once. In _APM-LR-U_ , examples are selected that
minimize the first term, which has an action similar to uncertainty sampling:

$\displaystyle\text{\emph{APM-LR-U}:}\quad x_{n}$
$\displaystyle=\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}\enspace(\mu_{n}^{T}x)^{2}.$
In _APM-LR-V_ , examples are selected that minimize the second term, which
prefers examples that probe in directions of high posterior variance:
$\displaystyle\text{\emph{APM-LR-V}:}\quad x_{n}$
$\displaystyle=\operatorname*{arg\,min}_{x\in\mathcal{U}_{n}}\enspace\biggl{(}\sqrt{x^{T}\Sigma_{n}x}-\sqrt{\frac{2}{\pi}P_{n}}\biggr{)}^{2}.$

We start in Figure 8 by plotting generalization performance as in Figure 4(b),
with the addition of APM-LR-U and APM-LR-V. In all plots below, error bars are
removed for visual clarity, and the query horizon spans the entire training
sequence (until the training pool is exhausted). As expected, APM-LR-V
performs comparably to MaxVar, since both methods prefer examples that probe
in directions of large posterior variance. Similarly, APM-LR-U performs
comparably to Uncertainty, since both methods minimize distance to a
hyperplane estimate (the former using the posterior mean hyperplane, the
latter using a MAP estimate). These results support the hypothesis that it is
the exploration component of APM-LR which leads to improved performance on
_vehicle-cars_ over non-exploration methods, including its own exploitation
variant APM-LR-U.

Figure 8: Test accuracy on _vehicle-cars_ , over expanded method set.

We can explore this hypothesis further by directly evaluating metrics for
exploitation and exploration of each method. To measure exploitation, in
Figure 9, we plot the average distance from each selected example to the MAP
hyperplane estimate. Since distance from the classifier hyperplane directly
corresponds to label uncertainty in logistic regression, this distance is a
direct measure of how often a policy selects uncertain examples. By
definition, Uncertainty begins by querying examples that are closest to the
hyperplane estimate, maximally exploiting the estimate to query examples with
the highest model uncertainty. The remaining methods vary in their levels of
initial distance from the hyperplane estimate, but all eventually query close
to their respective estimates, either by design or due to exhausting the full
training pool. Notably, the level of initial distance from the hyperplane
corresponds almost exactly to test accuracy performance: high-performing
MaxVar and APM-LR-V initially query far from their hyperplane estimates, while
the poorly performing Uncertainty queries examples close by.

Figure 9: Exploitation metric for _vehicle-cars_ : average distance of
selected example to estimated hyperplane. Small distances reflect high levels
of policy exploitation since this reflects examples being queried that are
uncertain with respect to the current hyperplane estimate.

To measure policy exploration, we use two metrics and plot their average
values in Figure 10. In the first metric, we measure the Euclidean distance
from each unlabeled example to its nearest labeled neighbor, and take the
maximum such distance over all unlabeled examples. This quantity measures the
worst-case level of isolation of an unlabeled point to its nearest labeled
neighbor, with lower values corresponding to higher degrees of policy
exploration. A similar quantity is involved in the construction of coresets
for active learning to promote diversity among selected examples (Sener and
Savarese,, 2018). As our second metric, we consider windows of $d$ examples
(recall that $d$ denotes the data space dimension) and plot the log
determinant of the Gram matrix of the examples selected in each window, which
can be used as a measure of example diversity (higher values correspond to
higher levels of example diversity) (Ash et al.,, 2020). In Figure 10(a),
MaxVar, APM-LR-V, APM-LR, and Random have the lowest average maximin
distances, corresponding to lower levels of isolated unlabeled examples.
Similarly, these methods generally have large initial Gram matrix log
determinants, as depicted in Figure 10(b).

(a)

(b)

Figure 10: Exploration metrics for _vehicle-cars_ : (a) maximum distance from
an unlabeled example to its closest labeled example. Smaller values indicate
lower levels of unlabeled data isolation, and correspond to higher levels of
exploration. (b) Log determinant of Gram matrix, where larger values
correspond to higher levels of exploration.

The ablation of individual terms in APM-LR and direct measurement of
exploitation and exploration of each active learning method suggests that when
tested on _vehicle-cars_ , exploration-based methods outperform methods that
do not explicitly optimize for diverse selection. While this extended analysis
is limited to a single dataset, it provides evidence that the exploration term
in APM-LR can lead to higher levels of performance on a real-world dataset,
where methods that do not directly account for exploration might fail.