# Nonparametric active learning for cost-sensitive classification.

Boris Ndjia Njike, Xavier Siebert
Mathematics and Operational Research, University of Mons, Belgium

(August 28, 2024)

###### Abstract

Cost-sensitive learning is a common type of machine learning problem where
different errors of prediction incur different costs. In this paper, we design
a generic nonparametric active learning algorithm for cost-sensitive
classification. Based on the construction of confidence bounds for the
expected prediction cost functions of each label, our algorithm sequentially
selects the most informative vector points. Then it interacts with them by
only querying the costs of prediction that could be the smallest. We prove
that our algorithm attains optimal rate of convergence in terms of the number
of interactions with the feature vector space. Furthermore, in terms of a
general version of Tsybakov’s noise assumption, the gain over the
corresponding passive learning is explicitly characterized by the probability-
mass of the boundary decision. Additionally, we prove the near-optimality of
obtained upper bounds by providing matching (up to logarithmic factor) lower
bounds.

Keywords: Cost-sensitive classification, active learning, nonparametric
classification.

##  1 Introduction

For many real-world machine learning tasks, while unlabelled data are
abundant, getting a pool of labelled data is very expensive and time-
consuming. In this case, it is interesting to only label the points that could
significantly affect the prediction decision. This is the main purpose of
active learning (Cohn _et al._ , 1994; Dasgupta, 2011) which is a machine
learning approach that attemps to provide an optimal decision rule while using
as few labelled data as possible. Contrary to standard models of machine
learning (namely passive learning) where the labelled data are provided
beforehand, in active learning, the learner only has access to a set of
unlabelled points at the beginning, and has to progressively request (to a so-
called oracle) at some cost the label of some points during the learning
process. At the end, based on these selected labelled points, a prediction
decision rule is provided. In this paper, we consider the classification task
which consists in providing a prediction rule or classifier that maps each
unlabelled point $x$ from $\mathcal{X}$, the instance space, to an element $y$
$\in$ $\mathcal{Y}=\\{1,\ldots,M\\}$ the label space $($where $M\geq 2$ is an
integer$)$. Both in active and in passive learning, the performance of a
prediction rule is measured in terms of its ability to predict the label of a
new instance by keeping the error of classification as small as possible.
However, while fruitful in many domains applications, measuring the
performance of a classifier by only considering its ability to maintain the
error of classification as small as possible is sometimes inappropriate
because some type of classification errors (even small) could have significant
negative effects on the underlying problem. For many real world domain
applications, it is thus valuable to consider learning classification
approaches that pay attention to each error of classification. For example, in
fraud detection tasks, a classification error that deems a fraudulent
transaction as legitimate may incur huge losses for the banking institution,
such as financial or reputational, while refusing a legitimate transaction is
less serious because the banking institution only loses the transaction fee.
The learning classification problem can be reformulated in terms of the cost
incurred by a label prediction, so that a prediction rule will predict the
label which has the smallest negative effect on the underlying problem. Such
learning problem is called cost-sensitive classification (Elkan, 2001;
Dmochowski _et al._ , 2010). Let us emphazise that the prediction cost differs
from the labeling cost mentioned above in the definition of active learning.
Labeling cost in active learning corresponds to the effort (for example, it
could be expressed in terms of time) made to determine the label of an
instance while prediction cost in cost-sensitive classification refers to the
cost incurred by making some prediction as in the fraud detection example.

In this paper, we design an active learning algorithm that provides a
classifier suitable for cost-sensitive classification. Our analysis falls into
the nonparametric setting under assumptions related to those used in (Audibert
& Tsybakov, 2007; Minsker, 2012; Locatelli _et al._ , 2017; Kpotufe _et al._ ,
2022). At each step, our algorithm is able to select any point from the
instance space and to interact with it by requesting the prediction costs that
could be the smallest (with high probability). Under some smoothness and
margin noise assumptions, we prove that the resulting classifier achieves an
optimal rate of convergence in terms of the number of interactions with the
instance space. Additionally, we show the (near) optimality of our rate of
convergence by providing matching (up to a logarithmic factor) lower bounds.
These results compare favorably with those obtained in the passive learning
counterpart (Reeve, 2019). The paper is organized as follows: Section 2
presents backgrounds and related works on active learning, cost-sensitive
classification and active learning for cost-sensitive classification. In
Section 3 we summarize our main contributions while in Section 4 we introduce
the main notations, assumptions used in this work, the overall description of
our algorithm and the theoretical properties of our algorithm. We conclude
with Section 5. Section A contains all detailed proofs.

##  2 Related works

Active learning. Over the last fifteen years, a lot of progress has been made
on understanding the principles of active learning, and its benefits over
passive learning (see for example (Balcan _et al._ , 2007; Dasgupta, 2011;
Castro & Nowak, 2008; Minsker, 2012; Hanneke & Yang, 2015; Locatelli _et al._
, 2017; Kpotufe _et al._ , 2022)). Some of the studies considered the
nonparametric setting by focusing on plug-in methods in classification
(Minsker, 2012; Locatelli _et al._ , 2017). The overall principle is to
progressively estimate the class-conditional regression functions by only
focusing in the region where the classification is most difficult. Under some
standard smoothness and noise assumptions, (Minsker, 2012; Locatelli _et al._
, 2017) provided a rate of convergence that shows the improvement (over some
range of smoothness and noise parameters) of active learning over passive
learning (Audibert & Tsybakov, 2007). A deep analysis of these bounds and of
their the proof details reveals that these improvements over passive learning
strongly depend on the behavior of the class-conditional regression functions
around the boundary decision. Very recently, (Kpotufe _et al._ , 2022) went
further by introducing a more general noise assumption than that used in
(Minsker, 2012; Locatelli _et al._ , 2017). This assumption takes into account
the probability-mass of the boundary decision and allows to prove that no
improvement is possible over passive learning when there is a large amount of
instances exactly on the decision boundary. The overall principle of our
algorithm is inspired by (Minsker, 2012; Locatelli _et al._ , 2017; Shekhar
_et al._ , 2021), and is adapted for the cost-sensitive classification. When
interacting with the oracle, the prediction costs are requested instead of the
label as was done in (Minsker, 2012; Locatelli _et al._ , 2017). Moreover, we
use a more general noise assumption, and depending on how large the
probability-mass of the boundary decision is, we explicitly identify when a
gain is possible in cost-sensitive active learning over its passive learning
counterpart (Reeve, 2019).

Cost-sensitive learning. As mentioned in Section 1, formulating the objective
only in terms of the error of classification is inappropriate in some
practical situations. Some works have pointed out this disadvantage by
considering the cost-sensitive approach to classification (Elkan, 2001;
Dmochowski _et al._ , 2010; Reeve & Brown, 2017; Reeve, 2019) where the costs
incurred by each error of classification are taken into account. Since the
pioneering work by (Elkan, 2001), a plethora of cost-sensitive learning
approaches have been proposed, but we consider here three that are closely
related to our present setting.
First, (Elkan, 2001) introduced a cost-sensitive approach where an $M\times
M$-matrix $\Gamma$ is given to the learner before the learning process. The
matrix $\Gamma$ represents a cost matrix, and $\Gamma_{ij}\geq 0$ represents
the cost incurred by predicting the label $i$ whereas the true label is $j$.
When $\Gamma_{ij}=1$ if $i\neq j$ and $\Gamma_{ii}=0,$ it reduces to the
standard approach where the cost of misclassification is not taken into
account. The learning objective is thus to find a prediction rule that
minimizes the expected cost with respect to the cost matrix $\Gamma$. This
approach was also considered by other works such as (Reeve & Brown, 2017;
Reeve, 2019). These works were built upon (Audibert & Tsybakov, 2007), which
considered the standard learning approach by implicitly making the assumption
of symmetric prediction costs.
The second cost-sensitive approach consists in making $\Gamma$ a feature-
dependent matrix cost (Elkan, 2001; Reeve, 2019). This makes sense in some
real-world applications such as medical diagnosis where the prediction cost
may depend on the patient (medical history for instance).
The third cost-sensitive approach, which will be considered in this paper, is
more general than the two previous ones. It considers the case where the cost
matrix $\Gamma$ $($or $\Gamma(x))$ is not available to the learner. This is
very common in practice such as medical diagnosis where it is sometimes very
difficult to evaluate the cost that would have been incurred if an unhealthy
patient was predicted as healthy. In this case, an instance $X$ does not come
directly to the learner with a label $y$, but, it is associated with a
(random) cost-vector of size $M$, where the $i$-th component represents the
prediction cost incurred by the label $i$.

The three aforementioned cost-sensitive approaches were considered in the case
of passive learning (Reeve, 2019). In the third approach, they advocated for
maximizing rewards rather than minimizing costs as in the present work. In
nonparametric passive learning setting, they studied minimax learning rate
under some smoothness and noise assumptions which are closely related to ours.
Their analysis and results appear to be more general than the work of
(Audibert & Tsybakov, 2007). In this paper, we study for the first time the
cost-sensitive classification problem in nonparametric active learning setting
in the same line of research as (Audibert & Tsybakov, 2007) and compare our
statistical guarantees results to the corresponding passive learning setup
(Reeve, 2019).
Active learning for cost-sensitive classification. Cost-sensitive multi-class
classification in active learning has received attention in the last decade
mostly in parametric setting (Agarwal, 2013; Krishnamurthy _et al._ , 2017,
2019). Through the online selective sampling framework, (Agarwal, 2013)
designed an algorithm for cost-sensitive multiclass-classification and showed
improvement of active learning over passive learning. However, they considered
learning models where the query strategies are tailored to linear
representation (Gentile & Orabona, 2012) which is too specific and difficult
to extend to other hypothesis classes. Additionally, they used the cost-
sensitive setting where the cost-matrix is fixed and available to the learner
before the learning process. Later, (Krishnamurthy _et al._ , 2017) considered
active learning for cost-sensitive multi-class classification in parametric
setting and where the prediction costs are unknown. For every considered
example $X$, their algorithm computes upper and lower bounds of the expected
prediction cost of each label and then only queries labels with relatively
large prediction range. However, their computational techniques leads to sub-
optimal results in label complexity. This latter drawback was overcome in
(Krishnamurthy _et al._ , 2019), where an efficient cost range computation is
provided and leads to optimal results in terms of label complexity. In this
paper, we rather consider the nonparametric setting. We derive new techniques
for computing with high confidence, the upper and lower bounds on the expected
prediction costs. This allows us to make optimal predictions and then provide
a classifier suitable for cost-sensitive classification that achieves optimal
rate of convergence.

##  3 Contributions

In this present work, we propose a generic nonparametric active learning
algorithm for cost-sensitive multiclass-classification by considering a more
general noise assumption than that used in earlier works such as (Reeve,
2019). Our contributions are as follows:

  * •

Our resulting classifier achieves an optimal rate of convergence which
involves a noise parameter that allows to precisely determine when gain is
possible over the passive learning counterpart (Reeve, 2019). Moreover, our
algorithm is adaptive to this noise parameter.

  * •

We provide a lower bound that matches (up to a logarithmic factor) the
obtained rate of convergence achieved by our algorithm.

##  4 Algorithm

In this Section, we first introduce some notations, then we provide a brief
description and analysis of our active learning algorithm. For clarity
purposes, some key quantities that will be used in the analysis of our
algorithm are summarized in Table 1. We conclude by giving some theoretical
results that show that our active learning algorithm enjoys good statistical
guarantees.

###  4.1 Setting

Let $\mathcal{X}\subset\mathbb{R}^{d}$ be a metric space, referred to as the
instance space. We assume that $\mathcal{X}=[0,1]^{d}$ is equipped with the
Euclidean distance $\|.\|.$ Let $\mathcal{Y}=\\{1,\ldots,M\\}$ be the set of
labels. Let $P$ be a (unknown) probability defined on
$\mathcal{X}\times[0,1]^{M}.$ In this case, if $(X,c)\sim P$, with
$c=(c(1),\ldots,c(M))$, then for $y=1,\ldots,M$, the quantity $c(y)$
represents the prediction cost induced by the use of label $y$. In cost-
sensitive learning, instead of dealing with a labelled sample from
$\mathcal{X}\times\mathcal{Y}$, the learner observes an i.i.d sample
$(X_{1},c_{1}),\ldots,(X_{n},c_{n})$ generated according to $P.$ The random
quantity $c_{k}$ $(k=1,\ldots,n)$ represents the cost vector
$c_{k}=(c_{k}(1),\ldots,c_{k}(M))$. In this context, the main objective is to
construct a mapping $g:\mathcal{X}\longrightarrow\mathcal{Y}$ which minimizes
the cost-sensitive expected cost:

$R_{cs}(g)=\mathbb{E}_{(X,c)}(c(g(X))).$

Let $y\in\mathcal{Y}$ be a given label, and the function:
$f(.;y):\mathcal{X}\longrightarrow[0,1]$ such that
$f(x;y)=\mathbb{E}(c(y)|X=x)$. The oracle mapping
$f_{cs}^{*}:\mathcal{X}\longrightarrow\mathcal{Y}$ defined by

$f_{cs}^{*}(x)\in\operatorname*{arg\,min}_{y\in\mathcal{Y}}\;f(x;y)$

and known as the Bayes cost-sensitive classifier, achieves the minimum cost-
sensitive expected cost (Krishnamurthy _et al._ , 2019). The excess expected
cost for a mapping $g:\mathcal{X}\longrightarrow\mathcal{Y}$ is:

$\varepsilon_{cs}(g)=R_{cs}(g)-R_{cs}(f^{*}_{cs})=\mathbb{E}_{X}\left(f(X;g(X))-f(X;f_{cs}^{*}(X))\right).$

######  Remark 4.1.

Cost-sensitive learning is more complex than standard classification problem.
In fact, in cost-sensitive learning, labels just serve as indices for the cost
vector, and the distribution of data is over pairs of $(x,c)$ rather than
$(x,y)$ as seen in (active) binary and multiclass classification (Kpotufe _et
al._ , 2022). Moreover, cost-sensitive decision-making involves minimizing the
expected cost of a decision, which may involve predicting a label that is less
probable (with respect to the standard classification) but has a lower
prediction cost associated with it. However, in certain specific cases, a
cost-sensitive problem can be transformed into a classification problem. (see
for instance Proposition 5.8.1 from (Reeve, 2019)).

###  4.2 Our model

We consider a hierarchical structure on the instance space: for integers
$h\geq 0$, $K\geq 2$, the instance space is partitioned into $K^{h}$ subsets
$\mathcal{X}_{h,i}$ $(1\leq i\leq K^{h})$ which are referred to as cells. This
partitioning is seen as a spatial $K$-tree where the root is the whole space
$\mathcal{X}=\mathcal{X}_{0,1}$ and at each depth $h\geq 0$, we have
$\displaystyle\cup_{i=1}^{K^{h}}\mathcal{X}_{h,i}=\mathcal{X}$ and each cell
$\mathcal{X}_{h,i}$ induces $K$ children
$\\{\mathcal{X}_{h+1,i_{j}},j=1,\ldots,K\\}$ which forms a partition of
$\mathcal{X}_{h,i}$. Additionally, for each cell $\mathcal{X}_{h,i}$, we
associate a fixed point $x_{h,i}$ $\in$ $\mathcal{X}_{h,i}$ called the center
of $\mathcal{X}_{h,i}$ such that
$\mathcal{X}_{h,i}=\\{x\in\mathcal{X},\;\|x-x_{h,i}\|\leq\|x-x_{h,j}\|,\;\;j\neq
i\\}$ and where ties are broken in an arbitrary, but deterministic way.
Moreover, we suppose:

  * •

there exists some constants $\rho\in(0,1)$, $\nu_{1},\nu_{2}>0$, with
$0<\nu_{1}\leq 1\leq\nu_{2}$ such that for all $h,i$:

$B(x_{h,i},\nu_{1}\rho^{h})\subset\mathcal{X}_{h,i}\subset
B(x_{h,i},\nu_{2}\rho^{h}).$ (4.1)

where $B(x,r)=\\{z\in\mathcal{X},\;\|x-z\|<r\\}$ for $x\in\mathcal{X}$, and
$r>0$.

  * •

that $K=2$, and $\mathcal{X}_{h,i}$ is partitioned as
$\mathcal{X}_{h,i}=\mathcal{X}_{h+1,2i-1}\cup\mathcal{X}_{h+1,2i}.$

A similar model was also considered in different settings such as bandit
theory (Munos _et al._ , 2014). In this paper, we consider an active learning
algorithm for cost-sensitive multi-class classification that exploits the
hierarchical structure of the instance space. Given a hierarchical partition
of the instance space, and some integers $h$ and $i$, we aim at estimating the
Bayes cost-sensitive classifier in $\mathcal{X}_{h,i}$ and thereby in the
whole space. Our algorithm proceeds by only interacting with cells
$\mathcal{X}_{h,i}$ $($for some $h,i)$ where there is substantial
classification uncertainty. It interacts with $\mathcal{X}_{h,i}$ via its
center $x_{h,i}$ by requesting some of its label costs. In the following
sections, we will sometimes consider $x_{h,i}$ as the cell $\mathcal{X}_{h,i}$
if no ambiguity is present.

One of the main reasons for which we use the hierarchical structure on the
instance space in this paper is to align with the majority of previous works
on standard nonparametric active learning, such as (Castro & Nowak, 2008;
Minsker, 2012; Locatelli _et al._ , 2017; Kpotufe _et al._ , 2022). However,
We could also use the pool-based approach considered in (Njike & Siebert,
2022) where a k-NN active learner has been proposed.

###  4.3 Overall description of our algorithm

With a fixed number of interactions $n$ (considered as the budget), our main
objective is to provide an active learning algorithm for cost-sensitive multi-
class classification, which outputs a classifier with good statistical
guarantees. Our algorithm is inspired from that provided in (Shekhar _et al._
, 2021) in the context of active learning with reject option, and also from
that provided in (Krishnamurthy _et al._ , 2019) where a bookkeeping procedure
is used in order to only deal with labels that could be the optimal one.
Our algorithm works iteratively over a finite number of steps, until the
budget $n$ has been reached.
At step $t$, the instance space is hierarchically partitioned into two
subsets: $\mathcal{X}^{(t)}_{u}$ the set of unclassified cells (for example,
filled in red on Figure 1), and $\mathcal{X}^{(t)}_{c}$ the set of classified
cells (for example, filled in green on Figure 1).

$\mathcal{X}_{0,1}$ $\mathcal{X}_{1,1}$ $\mathcal{X}_{2,1}$
$\mathcal{X}_{3,1}$ $\mathcal{X}_{3,2}$ $\mathcal{X}_{2,2}$
$\mathcal{X}_{1,2}$ $\mathcal{X}_{2,3}$ $\mathcal{X}_{3,5}$
$\mathcal{X}_{3,6}$ $\mathcal{X}_{2,4}$ Figure 1: An example of a possible
partition of the instance space at a given step: the classified regions are
represented by the cell filled in green, and the unclassified region by the
cells filled in red:
$\mathcal{X}^{(t)}_{u}=\\{\mathcal{X}_{2,4},\mathcal{X}_{3,1},\mathcal{X}_{3,2},\mathcal{X}_{3,5},\mathcal{X}_{3,6}\\},\;\mathcal{X}^{(t)}_{c}=\\{\mathcal{X}_{2,2}\\}$
and $\mathcal{X}=\mathcal{X}^{(t)}_{u}\cup\mathcal{X}^{(t)}_{c}$.

Subsequently, it proceeds as follows: it selects the cell
$\mathcal{X}_{h_{t},i_{t}}$ in $\mathcal{X}^{(t)}_{u}$ that has the largest
classification uncertainty. In this case, two outcomes are possible:

  * •

First, it could interact with $\mathcal{X}_{h_{t},i_{t}}$ by requesting the
cost $c_{h_{t},i_{t}}(y)$ of some labels at the center $x_{h_{t},i_{t}}$.
Based on these later requests $($and possibly other requests made before the
step $t$), a subset $\mathcal{Y}_{h_{t},i_{t}}^{(t)}\subset\mathcal{Y}$ of
candidate labels is built. This is done by discarding suboptimal labels $y$,
that is those with $f(x;f_{cs}^{*}(x))<f(x;y)$ for all
$x\in\mathcal{X}_{h_{t},i_{t}}$ with high probability. Thus, if the subset
$\mathcal{Y}^{(t)}_{h_{t},i_{t}}$ only contains one label, the cell
$\mathcal{X}_{h_{t},i_{t}}$ is added to the current classified region
$\mathcal{X}^{(t)}_{c}$ and removed from $\mathcal{X}^{(t)}_{u}$.

  * •

Second, the cell $\mathcal{X}_{h_{t},i_{t}}$ could be expanded or refined.
This happens when the algorithm has interacted with
$\mathcal{X}_{h_{t},i_{t}}$ a substantial number of times. In this case, the
cell $\mathcal{X}_{h_{t},i_{t}}$ is replaced by
$\mathcal{X}_{h_{t}+1,2i_{t}}\cup\mathcal{X}_{h_{t}+1,2i_{t}-1}$ and removed
(for example, filled in black on Figure 1) from $\mathcal{X}^{(t)}_{u}$.

After the iteration process, our algorithm provides a classifier as detailed
in Section 4.4.

$\mathcal{Y}_{h,i}^{(t)}$ | set of candidate labels for $\mathcal{X}_{h,i}$ at step $t.$
---|---
$c_{h,i}^{v}(y)$ |  $v^{th}$ requested cost associated to the label $y$ at the center $x_{h,i}$
$\mathcal{X}_{c}^{(t)}$ | current classified region at step $t$
$\mathcal{X}_{u}^{(t)}$ | current unclassified region at step $t$
$I_{t}(\mathcal{X}_{h,i})$ | classification uncertainty of the cell $\mathcal{X}_{h,i}$ at step $t$
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ | upper confidence bound of the expected
| prediction cost $f(:,y)$ in $\mathcal{X}_{h,i}$ at step $t$
$L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ | lower confidence bound of the expected prediction cost $f(:,y)$ in $\mathcal{X}_{h,i}$ at step $t$
$A_{r}^{(t)}(\mathcal{X}_{h,i})$ | Boolean variable linked on the refinement of $\mathcal{X}_{h,i}$ at step $t$
Table 1: Main quantities that appears in the analysis of Algorithm 1

###  4.4 Analysis of our algorithm

This Section is devoted to a brief analysis of our algorithm while the
theoretical results are in Section 4.5. We provide some intuitions behind the
construction of the set of candidate labels and describe the refinement and
uncertainty criteria used in our algorithm. Our techniques are built upon the
construction of upper and lower bounds of the expected prediction cost
functions. We therefore first introduce the following definition:

######  Definition 4.1.

Given a set $A\subset[0,1]^{d}$, and a deterministic function $g$ defined in
$A$ that takes values in $[0,1]$, we say that $g$ has confidence bounds
$L_{g}(A)$, $U_{g}(A)$ at level $\delta$ in the set $A$ if with probability at
least $1-\delta$,

$L_{g}(A)\leq g(x)\leq U_{g}(A)\quad\text{for all}\;x\in A.$

As we will consider in Section 4.5.2, the quantities $L_{g}(A)$, $U_{g}(A)$
are randomized and the probability $(1-\delta)$ is with respect to their
uncertainty. Importantly, the dependence of these confidence bounds with
respect to $\delta$ is omitted for clarity purposes.

How can we accurately construct the (random) set of candidate labels
$\bm{\mathcal{Y}^{(t)}_{h,i}?}$ For any cell $\mathcal{X}_{h,i}$, the
corresponding set of candidate labels is initialized to
$\mathcal{Y}_{h,i}^{(0)}=\mathcal{Y}$. For $t\geq 1$, let
$\mathcal{X}_{h_{t},i_{t}}$ be the cell chosen from the unclassified region by
our algorithm at step $t.$ To compute $\mathcal{Y}^{(t)}_{h_{t},i_{t}}$, we
first need to provide confidence bounds on the expected prediction cost
functions $f(.;y)$ for all $y\in\mathcal{Y}^{(t-1)}_{h_{t},i_{t}}$. That is,
according to Definition 4.1, for a given parameter $\delta^{\prime}\in(0,1)$,
we have to provide the quantities
$L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$,
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$ such that with probability at
least $1-\delta^{\prime}$, we have for all $x\in\mathcal{X}_{h_{t},i_{t}}$,

$L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})\leq f(x;y)\leq
U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$ (4.2)

Once confidence bounds are constructed, the set of candidate labels
$\mathcal{Y}^{(t)}_{h,i}$ only contains labels $y$ from
$\mathcal{Y}^{(t-1)}_{h,i}$ that satisfy:

$L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})\leq\min_{y\in\mathcal{Y}^{(t-1)}_{h_{t},i_{t}}}\,U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}}),$
(4.3)

Particularly, under some smoothness assumption, for all $x$ $\in$
$\mathcal{X}_{h_{t},i_{t}}$, $f^{*}_{cs}(x)$ is never discarded and
$\mathcal{X}_{h_{t},i_{t}}$ is therefore correctly labelled when it is added
to the classified region $\mathcal{X}_{c}^{(t)}.$ Importantly, for any cell
$\mathcal{X}_{h,i}$, the confidence bounds can be initialized to
$L_{f(:;y)}^{(0)}(\mathcal{X}_{h,i})=-\infty$ and
$U_{f(:;y)}^{(0)}(\mathcal{X}_{h,i})=+\infty$ and are progressively improved
as costs are requested. These confidence bounds could take various forms
depending on assumptions made on the considered problem of cost-sensitive
classification. For instance in Section 4.5.2, under some smoothness
assumption on the expected prediction cost function $f(.;y)$, we will provide
specific expressions of $L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ and
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ which can be used by our algorithm.

How can we choose the most uncertain cell from the unclassified region? To
measure the level of uncertainty of a cell $\mathcal{X}_{h,i}$ from the
unclassified region $\mathcal{X}_{u}^{(t)}$, we can use the confidence bounds
of each expected prediction cost function $f(.;y).$ For $\mathcal{X}_{h,i}$
from $\mathcal{X}_{u}^{(t)}$, let $I_{t}(x_{h,i})$ be the quantity defined as:

$I_{t}(\mathcal{X}_{h,i})=\min_{y\in\mathcal{Y}^{(t)}_{h,i}}\,U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})-\min_{y\in\mathcal{Y}^{(t)}_{h,i}}L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$
(4.4)

According to Equation (4.3), the quantity $I_{t}(\mathcal{X}_{h,i})$ is non-
negative (with high probability). The algorithm therefore chooses to interact
with the cell $\mathcal{X}_{h,i}$ that has the largest value
$I_{t}(\mathcal{X}_{h,i})$ over all the cells that belong to the unclassified
region.

Refinement criterion. Once selecting the cell $\mathcal{X}_{h_{t},i_{t}}$ from
$\mathcal{X}_{u}^{(t)}$, the algorithm decides to refine when it becomes
difficult to differentiate labels from the current set of candidate labels
after a large number of interactions. In Algorithm 1, the refinement criteria
is characterized by a Boolean variable
$A^{(t)}_{r}(\mathcal{X}_{h_{t},i_{t}})$ such that

$A_{r}^{(t)}(\mathcal{X}_{h_{t},i_{t}})=\text{True}\;\Longleftrightarrow\;\mathcal{X}_{h_{t},i_{t}}\;\text{has
to be refined at step $t$}.$ (4.5)

For the refinement criteria, we could consider a cut-off (possibly depending
on the current depth $h_{t}$ and some complexity parameters) such that if the
cell $\mathcal{X}_{h_{t},i_{t}}$ has not been added to the classified region
within a given number of interactions with the algorithm, the value $True$ is
assigned to the variable $A^{(t)}_{r}(\mathcal{X}_{h_{t},i_{t}})$ and thus the
cell $\mathcal{X}_{h_{t},i_{t}}$ has to be refined. In this case, as we
pointed out in Section 4.3, it is replaced by its children
$\mathcal{X}_{h_{t}+1,2i_{t}},\mathcal{X}_{h_{t}+1,2i_{t}-1}$ in the
unlabelled region $\mathcal{X}_{u}^{(t)}$. Moreover, the cells
$\mathcal{X}_{h_{t}+1,2i_{t}}$, $\mathcal{X}_{h_{t}+1,2i_{t}-1}$ inherit of
some properties of $\mathcal{X}_{h_{t},i_{t}}$ namely confidence bounds and
the set of candidate labels.

Estimator of the Bayes cost-sensitive classifier. Let $T_{n}$ be the last step
in Algorithm 1. The resulting active learning classifier provided by Algorithm
1 is defined as follows:

$\hat{g}_{n}(x)=\operatorname*{arg\,min}_{y\in\mathcal{Y}_{h,i}^{(T_{n})}}\;U_{f(:;y)}^{(T_{n})}(\mathcal{X}_{h,i}),$
(4.6)

for $x$ $\in$ $\mathcal{X}_{h,i}$, with
$\mathcal{X}_{h,i}\in\mathcal{X}^{(T_{n})}_{u}\cup\mathcal{X}^{(T_{n})}_{c}.$
As detailed in section 4.5.3, it enjoys goods statistical guarantees for cost-
sensitive classification under some noise and smoothness assumptions.

###  4.5 Theoretical results

This Section is devoted to theoretical guarantees achieved by our algorithm.
We first begin by presenting theoretical properties of our algorithm under
some assumptions and therefore the rate of convergence achieved by the
resulting classifier $\hat{g}_{n}$ in Algorithm 1. Secondly, we complete the
result on the rate of convergence by providing a (near) matching lower bound.
For Clarity purpose, the proofs of these results are relegated to Section A.

####  4.5.1 Assumptions

In this Section, we consider three assumptions which are commonly used in the
nonparametric setting for the analysis of the rates of convergence both in
active and passive learning.

######  Assumption 4.2 (Hölder-smoothness assumption).

There exist $\alpha\leq 1$ and $L>0$ such that, for all $y$ $\in$
$\mathcal{Y}$,

$|f(x;y)-f(z;y)|\leq L\parallel x-z\parallel^{\alpha}\quad\text{for
all}\;x,z\in\mathcal{X}.$

This assumption means that two close points tend to have the same prediction
cost.

######  Assumption 4.3 (Strong density assumption).

The marginal probability on $\mathcal{X}$ admits a density $p_{X}$ and there
exist $\mu_{min},\mu_{max}>0$ such that for all $x$ with $p_{X}(x)>0$,

$\mu_{min}\leq p_{X}(x)\leq\mu_{max}.$

The Assumption 4.3 is standard both in passive and active learning (Audibert &
Tsybakov, 2007; Minsker, 2012; Reeve, 2019). However, it can be weakened by
considering a particular hierarchical partition as stated in Section 4.2. For
instance, we can consider a partition of the space with cells (balls for
example) in a hierarchical way, so that at depth $h>0$, for any cell
$\mathcal{X}_{h,i}$ at level $h$, we have $c_{2}\rho^{hd}\leq
P_{X}(\mathcal{X}_{h,i})\leq c_{1}\rho^{hd}$ (where $c_{1}$ and $c_{2}$ and
$\rho$ are absolute constants and $P_{X}$ the marginal probability defined on
$\mathcal{X})$ and such that the covering $($at depth $h)$ is somewhat tight,
that is $Supp(P_{X})\subset\bigcup_{i}\mathcal{X}_{h,i}$ and
$\sum_{i}P_{X}(\mathcal{X}_{h,i})\leq C$ where $C$ is some universal constant.

Next, let us state the noise assumption that characterizes the behavior of the
expected cost functions at the decision boundary.

For $y\in\mathcal{Y}$, let $\Delta(x,y)$ be defined as:

$\Delta(x,y)=f(x;y)-\min_{y^{\prime}\in\mathcal{Y}}\,f(x;y^{\prime}).$ (4.7)

We define $\Delta(x)$ as

$\Delta(x)=\left\\{\begin{array}[]{ll}\min_{y\in\mathcal{Y}}\\{\Delta(x,y):\;\Delta(x,y)>0\\}&\mbox{If
there exists }y\in\mathcal{Y}\;\text{such that}\;\Delta(x,y)>0\\\
\infty&\mbox{otherwise.}\end{array}\right.$ (4.8)

Given an instance $x$, let $f(x;y^{(1)})\leq f(x;y^{(2)})\leq...\leq
f(x;y^{(M)})$ denote order statistic on $f(x,y)$, $y\in\mathcal{Y}$. we define
$\Delta^{\prime}(x)=f(x;y^{(2)})-f(x;y^{(1)}).$

######  Assumption 4.4 (Refined margin noise assumption).

There exist parameters $\beta,C_{\beta},C^{\prime}_{\beta},\tau\geq 0$ such
that for all $\epsilon>0$,

$P_{X}(x\in\mathcal{X},\;\;\Delta(x)\leq\epsilon)\leq
C_{\beta}\epsilon^{\beta},\quad\text{and}\quad
P_{X}(x\in\mathcal{X},\;\;\Delta^{\prime}(x)\leq\epsilon)\leq\tau+C^{\prime}_{\beta}\epsilon^{\beta}$
(4.9)

An equivalent version of Assumption 4.4 was recently introduced in the setting
of classical active learning (Kpotufe _et al._ , 2022). Assumption 4.4
generalizes the Tsybakov’s noise assumption used in previous works on cost-
sensitive active learning, especially in parametric setting (Krishnamurthy _et
al._ , 2017, 2019). The probability mass of the region where the Bayes cost-
sensitive classifier is not unique is taken into account by $\tau$.
Particularly, when $\tau=0$, we recover the assumption used in (Krishnamurthy
_et al._ , 2019) which assumes the uniqueness of the Bayes cost-sensitive
classifier.

####  4.5.2 Specific choice of confidence bounds

In this Section, we will provide precise expressions of confidence bounds
(4.2) on the expected prediction cost function under Assumption 4.2. Before,
let us introduce the following quantities:

$B_{h}=\left(\nu_{2}\rho^{h}\right)^{\alpha},\quad
V(n_{a})=\sqrt{\frac{\log(2n^{3}M)}{2n_{a}}}$ (4.10)

where $\nu_{2},\rho$ come from (4.1), $\alpha$ comes from Assumption 4.2, $n$
is the label budget, $M$ the number of labels, and $n_{a}\leq n$ an integer.
Let $y$ $\in$ $\mathcal{Y}^{(t)}_{h,i}$, and $c_{h,i}^{v}(y)$ the $v$-th
requested prediction cost associated to $y$ at $x_{h,i}.$ For all $y$ $\in$
$\mathcal{Y}^{(t)}_{h,i}$, we consider the following estimator of
$f(x_{h,i};y)$ at step $t$:

$\hat{f}^{(t)}(x_{h,i};y)=\frac{1}{n_{h,i}(t)}\sum_{v=1}^{n_{h,i}(t)}c_{h,i}^{v}(y),$
(4.11)

where $n_{h,i}(t)$ is the number of times the algorithm has interacted with
the cell $\mathcal{X}_{h,i}$ up to step $t$.

Additionally, for all $x$ $\in$ $\mathcal{X}_{h,i}$, for all $y$ $\in$
$\mathcal{Y}^{(t)}_{h,i}$, we define the estimator $\hat{f}^{(t)}(x;y)$ of
$f(x;y)$ at step $t$ as:

$\hat{f}^{(t)}(x;y):=\hat{f}^{(t)}(x_{h,i};y).$

The expression of the confidence bounds are built upon the following
decomposition for all $x\in\mathcal{X}_{h,i}$

$|\hat{f}^{(t)}(x;y)-f(x;y)|\leq|\hat{f}^{(t)}(x_{h,i};y)-f(x_{h,i};y)|+|f(x;y)-f(x_{h,i};y)|$

Let us assume that there exists a favorable event $E$ (which will be
explicitly clarified in Section A), in which for any step $t$, for any cell
$\mathcal{X}_{h,i}$ that has interacted with the algorithm, we have for all
$y$ $\in$ $\mathcal{Y}^{(t)}_{h,i}$:

$|\hat{f}^{(t)}(x_{h,i};y)-f(x_{h,i};y)|\leq V(n_{h,i}(t))$ (4.12)

In this case, by using Assumption 4.2, and Equation (4.1), we have for any $x$
$\in$ $\mathcal{X}_{h,i}$, for all $y$ $\in$ $\mathcal{Y}_{h,i}^{(t)}$:

$f(x;y)\geq\bar{L}_{f(:;y)}^{(t)}(\mathcal{X}_{h,i}):=\hat{f}^{(t)}(x_{h,i};y)-V(n_{h,i}(t))-B_{h},$
(4.13)
$f(x;y)\leq\bar{U}_{f(:;y)}^{(t)}(\mathcal{X}_{h,i}):=\hat{f}^{(t)}(x_{h,i};y)+V(n_{h,i}(t))+B_{h}.$
(4.14)

The confidence bounds are thus defined as:

$L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})=\max\left(\bar{L}_{f(:;y)}^{(t)}(\mathcal{X}_{h,i}),L_{f(:;y)}^{(t-1)}(\mathcal{X}_{h,i})\right),$
(4.15)
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})=\min\left(\bar{U}_{f(:;y)}^{(t)}(\mathcal{X}_{h,i}),U_{f(:;y)}^{(t-1)}(\mathcal{X}_{h,i})\right).$
(4.16)

with
$L_{f(:;y)}^{(0)}(\mathcal{X}_{h,i})=-\infty,\;U_{f(:;y)}^{(0)}(\mathcal{X}_{h,i})=+\infty$
for all $h,i.$

####  4.5.3 Rate of convergence

Before providing the result on the rate of convergence, let us introduce the
following definition:

######  Definition 4.2 (Cost-sensitive classification measure).

Let $\Xi=(0,1)\times(0,+\infty)^{4}\times[0,1]\times(0,1)\times(0,\infty)$.
For any
$\zeta=(\alpha,L,\beta,C_{\beta},C^{\prime}_{\beta},\tau,\mu_{\min},\mu_{\max})\in\Xi$,
we denote $\mathcal{P}_{cs}(\zeta)$ the class of probability measures $P$ on
$\mathcal{X}\times[0,1]^{M}$ such that: (a) The expected conditional cost
functions $($associated to $P)$ satisfy Assumption 4.2 with parameter
$\alpha$, and $L$. (b) The probability $P$ satisfies Assumption 4.4 with
parameters $\beta,C_{\beta},C^{\prime}_{\beta},\tau$. (c) The probability $P$
satisfies Assumption 4.3 with parameters $\mu_{\min},\mu_{\max}$.

Input: Budget $n$

1 Initialization $\ell=0$ (current budget), $t=0$,
$\mathcal{X}_{0,1}=[0,1]^{d}$

2 $\mathcal{X}_{u}^{(t)}=\\{\mathcal{X}_{0,1}\\}$ //The unclassified region

3 $\mathcal{X}_{c}^{(t)}=\\{\\}$ //The classified region

4 $\mathcal{Y}_{h,i}^{(t)}=[M]$ the candidate labels for $\mathcal{X}_{h,i}$
$\in$ $\mathcal{X}_{u}^{(t)}$

5 For all $\mathcal{X}_{h,i}$ $\in$ $\mathcal{X}_{u}^{(t)}$, for all $y$ $\in$
$\mathcal{Y}_{h,i}^{(t)}$, $L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})=-\infty$ and
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})=+\infty$

6 $A_{r}^{(t)}(\mathcal{X}_{h,i})=False$ for all $\mathcal{X}_{h,i}$ $\in$
$\mathcal{X}_{u}^{(t)}$

7 while  _$\ell\leq n$_ do

8 //Choose a candidate cell with most uncertainty according to (4.4)

9
$\mathcal{X}_{h_{t},i_{t}}\in\operatorname*{arg\,max}_{\mathcal{X}_{h,i}\in\mathcal{X}_{u}^{(t)}}\;I_{t}(\mathcal{X}_{h,i})$

10 if  _$A_{r}^{(t)}(\mathcal{X}_{h_{t},i_{t}})=True$_ then

11 //Refine and pass information to the next depth

12
$\mathcal{X}_{u}^{(t)}=\mathcal{X}_{u}^{(t)}\setminus\\{\mathcal{X}_{h_{t},i_{t}}\\}\cup\\{\mathcal{X}_{h_{t}+1,2i_{t}-1};\mathcal{X}_{h_{t}+1,2i_{t}}\\}$

13 $\mathcal{Y}_{h_{t}+1,2i_{t}-1}^{(t)}=\mathcal{Y}_{h_{t},i_{t}}^{(t)}$

14 $\mathcal{Y}_{h_{t}+1,2i_{t}}^{(t)}=\mathcal{Y}_{h_{t},i_{t}}^{(t)}$

15
$L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t}+1,2i_{t}-1})=L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$

16
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t}+1,2i_{t}-1})=U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$

17
$L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t}+1,2i_{t}})=L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$

18
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t}+1,2i_{t}})=U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$

19 $A_{r}^{(t)}(\mathcal{X}_{h_{t}+1,2i_{t}})=False$

20 $A_{r}^{(t)}(\mathcal{X}_{h_{t}+1,2i_{t}-1})=False$

21 else

22 //Interact with $\mathcal{X}_{h_{t},i_{t}}$ via its center
$x_{h_{t},i_{t}}$

23 Query cost of predicting $y$ for any $y$
$\in\mathcal{Y}_{h_{t},i_{t}}^{(t)}$ at $x_{h,i}$

24 $\ell=\ell+1$

25 Update $A_{r}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$

26 for  _$y\in\mathcal{Y}_{h_{t},i_{t}}^{(t)}$_ do

27 Update the confidence bounds $L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$
and $U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$.

28
$\mathcal{Y}_{h_{t},i_{t}}^{(t)}=\\{y\in\mathcal{Y}^{(t)}_{h_{t},i_{t}},\;L_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})\leq\min_{y\in\mathcal{Y}^{(t)}_{h_{t},i_{t}}}\,U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})\\}$

29 if  _$|\mathcal{Y}_{h_{t},i_{t}}^{(t)}|=1$_ then

30
$\mathcal{X}_{c}^{(t)}=\mathcal{X}_{c}^{(t)}\cup\\{\mathcal{X}_{h_{t},i_{t}}\\}$

31
$\mathcal{X}_{u}^{(t)}=\mathcal{X}_{u}^{(t)}\setminus\\{\mathcal{X}_{h_{t},i_{t}}\\}$

32

33 $t=t+1$

Output: Classifier $\hat{g}_{n}$ defined by (4.6)

Algorithm 1 Nonparametric active learning algorithm for cost-sensitive
classification

######  Theorem 4.5 (Rate of convergence).

For any
$\zeta=(\alpha,L,\beta,C_{\beta},C^{\prime}_{\beta},\tau,\mu_{\min},\mu_{\max})\in\Xi$
(introduced in Definition 4.2) with $\alpha\beta\leq d$, there exists an
absolute constant $c_{cs}$ such that for all $\delta$ $\in$ $(0,\frac{1}{2})$,
for any $P$ $\in$ $\mathcal{P}_{cs}(\zeta)$, and label budget
$n\geq\frac{1}{\delta}$, if at each step $t$ of Algorithm 1, we consider:

  * •

$A_{r}^{(t)}(\mathcal{X}_{h_{t},i_{t}})=True$ is equivalent to
$V(n_{h_{t},i_{t}}(t))\leq 2B_{h_{t}}$, where $n_{h,i}(t)$ is the number of
interactions made with the cell $\mathcal{X}_{h,i}$ up to step $t$, $V(.)$ and
$B_{h}$ are defined in (4.10).

  * •

The confidence bounds are updated according to (4.15) and (4.16).

Then, the classifier provided by Algorithm 1 satisfies with probability at
least $1-\delta$,

$\varepsilon_{cs}(\hat{g}_{n})\leq\left\\{\begin{array}[]{ll}\left(\frac{\tau}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}}\quad\text{if}\;\tau\geq\tau_{0}\\\
\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\;\text{if}\;\tau\leq\tau_{0},\end{array}\right.$
(4.17)

where
$\tau_{0}=\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}.$

Our result shows that improvement over passive learning (Reeve, 2019) depends
on the probability mass $\tau$ of region where the Bayes cost-sensitive
classifier is non unique. When $\tau$ is small enough, the obtained rate is
better than the classical rate obtained in passive learning (Reeve, 2019)
which is of order of $n^{-\frac{\alpha(\beta+1)}{2\alpha+d}}$. On the other
hand, when $\tau$ is large enough, the obtained rate has the same order as in
the passive learning counterpart (Reeve, 2019).

####  4.5.4 Lower bounds

In this Section, we provide a result that shows the optimality of the rate of
convergence provided in Theorem 4.5. The result is stated for the binary case
$(M=2)$. However, the extension to multi-class is not difficult as we can
always consider the subset of probabilities $P\in\mathcal{P}_{cs}(\zeta)$ with
the expected prediction cost functions $f(.;3)\equiv\ldots f(.;M)\equiv 1$ and
work only with $f(.;1),\;f(.;2)$ to obtain the corresponding lower bounds.

######  Theorem 4.6 (Lower bound for cost-sensitive classification).

Let us consider the cost-sensitive classification problem with $M=2$ and
$\mathcal{Y}=\\{0,1\\}$. Let
$\zeta=(\alpha,L,\beta,C_{\beta},C^{\prime}_{\beta},\tau,\mu_{\min},\mu_{\max})\in\Xi$
introduced in Definition 4.2. We assume that
$L,C_{\beta},C^{\prime}_{\beta}\in(1,\infty)$, $\alpha\beta\leq d$ and
$\mu_{min}\in(0,\tau)$. There exist constants $C_{cs}$, $C_{cs}^{\prime}$
(independent of $n$) such that:

$\inf_{\hat{g}_{n}}\sup_{P\in\mathcal{P}_{cs}(\zeta)}\mathbb{E}(R_{cs}(\hat{g}_{n}))-R_{cs}(f^{*}_{cs}))\geq\min(a_{n,\tau},a^{\prime}_{n,\tau}),$

where

$a_{n,\tau}=C_{cs}\max\left(\left(\frac{\tau}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}},\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\right),\quad
a^{\prime}_{n,\tau}=C^{\prime}_{cs}\max\left(\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}},\left(\frac{1}{\tau}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}}\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\right),$

the infimum is taken over all active learning algorithms that provide a
classifier $\hat{g}_{n}:\mathcal{X}\longrightarrow\\{0,1\\}$ based on sample
(strategy) $S_{n}=\\{(X_{1},c_{1}),\ldots,(x_{n},c_{n})\\}$ and the supremum
runs over all probability $P$ $\in$ $\mathcal{P}_{cs}(\zeta).$

The above Theorem 4.6 provides a lower bound that matches (up to a logarithmic
factor) the upper bound provided in Theorem 4.5. Moreover, we can get an
improvement over the lower bound obtained in the passive learning counterpart
(Reeve, 2019). Indeed, our result states that an active learner can outperform
the passive counterpart when $\tau$ is small. In this case, the minimax rate
is of order of $n^{-\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}$, whereas
in passive learning, it is of order of
$n^{-\frac{\alpha(\beta+1)}{2\alpha+d}}.$ On the other hand, when the
probability-mass $\tau$ is large enough, no active learner can outperform the
passive counterpart and the minimax rate remains the same as in the passive
learning counterpart.

##  5 Conclusion and perspectives

In this paper, we studied nonparametric active learning for cost-sensitive
multi-class classification. We designed an active learning algorithm that
provided a classifier for cost-sensitive multi-class classification. Under a
general noise assumption, we proved that our algorithm achieves optimal rate
of convergence, and the gain over the corresponding passive learning is
explicitly determined by the probability-mass of the boundary decision. An
interesting future direction is to evaluate the gain over passive learning
under our general noise assumption, when considering the parametric setting as
in (Krishnamurthy _et al._ , 2019).

##  Appendix A Missing proofs

This Section is organized as follows: in Section A.1, we introduce some
additional notations. In Section A.2 we formally prove Theorem 4.5 from the
main manuscript, and in Section A.3 we also formally prove Theorem 4.6.

###  A.1 Notations

Let $T_{n}$ be the last step in Algorithm 1, that is when the label budget is
exhausted. Let $\mathcal{X}^{(t)}$ be the set of cells with which the
algorithm has interacted at least once up to the end of a given step $t$, and
$\tilde{\mathcal{X}}=\cup_{t\leq T_{n}}\mathcal{X}^{(t)}$ the set of all cells
with which the algorithm has interacted along the learning process. For a
fixed $t$, and $\mathcal{X}_{h,i}$ $\in$ $\mathcal{X}^{(t)}$, for all $y$
$\in$ $\mathcal{Y}_{h,i}^{(t)}$, let $\hat{f}^{(t)}(x_{h,i};y)$ be the
empirical estimate of $f(x_{h,i};y)$ as defined by:

$\hat{f}^{(t)}(x_{h,i},y)=\frac{1}{n_{h,i}(t)}\sum_{v=1}^{n_{h,i}(t)}c_{h,i}^{v}(y),$
(A.1)

where $n_{h,i}(t)$ is the number of times the algorithm has interacted with
the cell $\mathcal{X}_{h,i}$ up to the end of step $t$, and $c_{h,i}^{v}(y)$
the $v$-th requested prediction cost associated to $y$ at $x_{h,i}.$ Let us
introduce the following parameters

$B_{h}=\left(\nu_{2}\rho^{h}\right)^{\alpha},\quad
V(n_{a})=\sqrt{\frac{\log(2n^{3}M)}{2n_{a}}}$ (A.2)

where $\nu_{2},\rho$ come from Section 4.2, $\alpha$ comes from Assumption
4.2, $n$ is the label budget, $M$ the number of labels, and $n_{a}\leq n$ an
integer.

###  A.2 Proof of Theorem 4.5

Our proof is inspired by (Munos _et al._ , 2014; Shekhar _et al._ , 2021;
Krishnamurthy _et al._ , 2019), and built on the definition of the following
event defined as $E=\cap_{t\geq 0}E_{t}$ where:

$E_{t}=\left\\{\forall\;\mathcal{X}_{h,i}\in\mathcal{X}^{(t)},\forall\,y\in\mathcal{Y}_{h,i}^{(t)},\;|\hat{f}^{(t)}(x_{h,i};y)-f(x_{h,i},y)|\leq
V(n_{h,i}(t))\right\\}$

In the following Lemma, we prove that the event $E$ happens with high
probability when $n$ is large enough.

######  Lemma A.1.

We have: $P(E)\geq 1-\tfrac{1}{n}$

###### Proof.

Let $N=|\tilde{\mathcal{X}}|$ (where $\tilde{\mathcal{X}}$ is defined in
Section A.1) and $T_{n}$ the last step in our algorithm. For
$\mathcal{X}_{h_{i},j_{i}}\in\tilde{\mathcal{X}}$, let
$n_{h_{i},j_{i}}(T_{n})$ the number of times the algorithm has interacted with
$\mathcal{X}_{h_{i},j_{i}}$ up to step $T_{n}$ and for $u\leq
n_{h_{i},j_{i}}(T_{n})$ let $\mathcal{Y}_{{h_{i},j_{i}}}^{(u)}$ the remaining
set of labels at the $u$-th interaction. Given
$y\in\mathcal{Y}_{h_{i},j_{i}}^{(u)}$, we note $c_{h_{i},j_{i}}^{u}(y)$ the
associated cost. Clearly, we have:

$E=\left\\{\forall\;1\leq i\leq N,\;\forall\,1\leq u\leq
n_{h_{i},j_{i}}(T_{n}),\;\forall
y\in\mathcal{Y}_{h_{i},j_{i}}^{(u)},\;\left|\frac{1}{u}\sum_{v=1}^{u}c_{h_{i},j_{i}}^{v}(y)-f(x_{h_{i},j_{i}};y)\right|\leq\sqrt{\frac{\log(2n^{3}M)}{2u}}\right\\}$

Given $\mathcal{X}_{h_{i},j_{i}}$, we have
$\mathbb{E}(c_{h_{i},j_{i}}^{v}(y))=f(x_{h_{i},j_{i}};y)$ for all $u\leq
n_{h_{i},j_{i}}(T_{n})$, $v\leq u$ and $y\in\mathcal{Y}_{h_{i},j_{i}}^{(u)}$.
Then by Hoeffding’s inequality, we have:

$\displaystyle\mathbb{P}(E^{c})$ $\displaystyle\leq\mathbb{E}\left(\sum_{i\leq
N}\sum_{u\leq
n_{h_{i},j_{i}}(T)}\sum_{y\in\mathcal{Y}_{h_{i},j_{i}}^{(u)}}\mathbb{P}\left(\left|\frac{1}{u}\sum_{v=1}^{u}c_{h_{i},j_{i}}^{v}(y)-f(x_{h_{i},j_{i}};y)\right|\geq\sqrt{\frac{\log(2n^{3}M)}{2u}}\mid\tilde{\mathcal{X}}\right)\right)$
$\displaystyle\leq\mathbb{E}\left(\sum_{i\leq N}\sum_{u\leq
n_{h_{i},j_{i}}(T)}\sum_{y\in\mathcal{Y}_{h_{i},j_{i}}^{(u)}}2\exp(\log(\frac{1}{2Mn^{3}}))\right)$
$\displaystyle\leq\frac{1}{n}\quad\text{as}\;N,n_{h_{i},j_{i}}(T)\leq
n,\text{and}\;|\mathcal{Y}_{h_{i},j_{i}}^{(u)}|\leq M,$

which leads to $\mathbb{P}(E)\geq 1-\frac{1}{n}$. ∎

######  Lemma A.2.

Let us assume that Assumption 4.2 holds. On the event $E$, suppose that the
Algorithm 1 has progressed up to step $t\geq 1$ and that the update of upper
and lower confidence bounds are made according to Equations (4.16), (4.15) in
he main text. Let $\mathcal{X}_{h_{t},i_{t}}$ be the chosen cell from
$\mathcal{X}^{(t)}_{u}$. For all $x$ $\in$ $\mathcal{X}_{h_{t},i_{t}}$, the
labels $y^{\prime}$ $\in$ $\operatorname*{arg\,min}_{y\in\mathcal{Y}}\;f(x,y)$
are never eliminated from $\mathcal{Y}_{h_{t},i_{t}}^{(t)}$. Consequently, the
cell $\mathcal{X}_{h_{t},i_{t}}$ is correctly labelled it is added to
$\mathcal{X}^{(t+1)}_{c}$.

###### Proof.

Let $y$ $\in$ $\mathcal{Y}_{h_{t},i_{t}}^{(t)}$ and $x$ $\in$
$\mathcal{X}_{h_{t},i_{t}}$. By Assumption 4.2, we have:

$|f(x;y)-f(x_{h_{t},i_{t}};y)|\leq B_{h_{t}}.$

By the definition of the event $E$, we have

$|f(x_{h_{t},i_{t}};y)-\hat{f}^{(t)}(x_{h_{t},i_{t}};y)|\leq
V(n_{h_{t},i_{t}}),$

and thus,

$\displaystyle|f(x;y)-\hat{f}^{(t)}(x;y)|$
$\displaystyle=|f(x;y)-\hat{f}^{(t)}(x_{h_{t},i_{t}};y)|$ $\displaystyle\leq
V(n_{h_{t},i_{t}})+B_{h_{t}}.$

Consequently,

$\hat{f}(x_{h_{t},i_{t}};y)-V(n_{h_{t},i_{t}})-B_{h_{t}}\leq
f(x;y)\leq\hat{f}(x_{h_{t},i_{t}};y)+V(n_{h_{t},i_{t}})+B_{h_{t}}$ (A.3)

By applying (A.3) at time $t-1$ $($ that could be either at depth $h_{t}-1$,
or $h_{t})$, we obtain:

$L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})\leq f(x,y)\leq
U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i}),$ (A.4)

where $L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ and
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ are defined by (4.15) and (4.16) in the
main text.
Let $y^{\prime}$ $\in$ $\operatorname*{arg\,min}_{y\in\mathcal{Y}}\;f(x;y)$.
If $y^{\prime}$ $\in$ $\mathcal{Y}_{h_{t},i_{t}}^{(t)}$ and $y^{\prime}$
$\notin$ $\mathcal{Y}_{h_{t},i_{t}}^{(t+1)}$, then

$\displaystyle f(x;y^{\prime})\geq
L_{f(:;y^{\prime})}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$
$\displaystyle>\min_{y\in\mathcal{Y}_{h_{t},i_{t}}^{(t)}}\,U_{f(:;y)}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$
$\displaystyle=U_{f(:;\hat{y})}^{(t)}(\mathcal{X}_{h_{t},i_{t}})\quad\text{where}\;\hat{y}\in\operatorname*{arg\,min}_{y\in\mathcal{Y}_{h_{t},i_{t}}^{(t)}}\,U_{f(:;\hat{y})}^{(t)}(\mathcal{X}_{h_{t},i_{t}})$
$\displaystyle\geq f(x;\hat{y})$

which contradicts the fact that
$y^{\prime}\in\operatorname*{arg\,min}_{y\in\mathcal{Y}}\,f(x;y).$ Then
$y^{\prime}$ is never eliminated and then, the cell
$\mathcal{X}_{h_{t},i_{t}}$ is correctly labelled if it is added to
$\mathcal{X}^{(t+1)}_{c}$.

∎

######  Lemma A.3.

Let $h\geq 0$, and some $i\in\\{1,\ldots,2^{h}\\}$. Let us assume that the
assumption 4.2 holds. For a fixed step $t\geq 1$, let us assume that for some
$\mathcal{X}_{h,i}$ $\in$ $\mathcal{X}_{u}^{(t)}$

  * •

We have $\Delta(x)>12B_{h}$ (where $\Delta(.)$ is defined by 4.7) for some $x$
$\in$ $\mathcal{X}_{h,i}$.

  * •

In Algorithm 1, the update of upper and lower confidence bounds are made
according to Equations (4.16), (4.15) which are stated in the main text.

  * •

In Algorithm 1, the refinement condition $A_{r}^{(t)}(\mathcal{X}_{h,i})=True$
is equivalent to $V(n_{h,i}(t))\leq 2B_{h}$, where $n_{h,i}(t)$ is the number
of interactions made with the cell $\mathcal{X}_{h,i}$ up to step $t$.

Then, on the event $E$: either the cell $\mathcal{X}_{h,i}$ will never be
refined, or the cell will be refined at some step $t$ and the remaining set of
candidate labels $\mathcal{Y}_{h,i}^{(t)}$ at that step only contains
$y^{\prime}\in\operatorname*{arg\,min}_{y\in\mathcal{Y}}\,f(x;y)$.

###### Proof.

Let $x$ $\in$ $\mathcal{X}_{h,i}$ with $\Delta(x)>12B_{h}$. If
$\Delta(x)=+\infty$, the Lemma is proven. Now, let us assume
$\Delta(x)<\infty$, and let $\bar{y}\in\mathcal{Y}$ with
$\Delta(x,\bar{y})>12B_{h}$. The Lemma is completely proven if we prove that
$\bar{y}$ will be eliminated before a possible refinement.
Let $y^{\prime}\in\operatorname*{arg\,min}_{y\in\mathcal{Y}}\,f(x;y)$. By
Assumption (4.2),

$f(x;\bar{y})-f(x;y^{\prime})\leq
2B_{h}+f(x_{h,i};\bar{y})-f(x_{h,i};y^{\prime}).$ (A.5)

If the cell $\mathcal{X}_{h,i}$ is refined at some step $1\leq t\leq T_{n}$
(where $T_{n}$ is the step at which the budget is reached), then
$|\mathcal{Y}_{h,i}^{(t)}|\geq 2$. By LemmaA.2, we have $y^{\prime}$ $\in$
$\mathcal{Y}_{h,i}^{(t)}$. Let $\hat{y}$ be defined as:

$\hat{y}\in\operatorname*{arg\,min}_{y\in\mathcal{Y}_{h,i}^{(t)}}\,\hat{f}^{(t)}(x_{h,i};y).$

If $\bar{y}\in\mathcal{Y}_{h,i}^{(t)}$, we have on the event $E$, and by
(A.5):

$\displaystyle f(x;\bar{y})-f(x;y^{\prime})$ $\displaystyle\leq
2V(n_{h,i}(t))+2B_{h}+\hat{f}^{(t)}(x_{h,i},\bar{y})-\hat{f}^{(t)}(x_{h,i},\hat{y})$

Then, as $12B_{h}<f(x;\bar{y})-f(x;y^{\prime})$, we get

$12B_{h}<2V(n_{h,i}(t))+2B_{h}+\hat{f}^{(t)}(x_{h,i};\bar{y})-\hat{f}^{(t)}(x_{h,i};\hat{y})$

and thus by using the refinement rule $(V(n_{h,i}(t))\leq 2B_{h})$, we obtain:

$\hat{f}^{(t)}(x_{h,i};\hat{y})+B_{h}+V(n_{h,i}(t))<\hat{f}^{(t)}(x_{h,i};\bar{y})-B_{h}-V(n_{h,i}(t))$

and

$U_{f(:;\hat{y})}^{(t)}(\mathcal{X}_{h,i})<L_{f(:;\bar{y})}^{(t)}(\mathcal{X}_{h,i}),$

which contradicts the fact that $\bar{y}$ $\in$ $\mathcal{Y}_{h,i}^{(t)}$ (see
line 28 in algorithm 1). ∎

######  Definition A.1 (Active cell).

Let $h>0$ an integer, and a cell $\mathcal{X}_{h,i}$ $(i=1,\ldots,2^{h})$. Let
$T_{n}$ be the last step at which the algorithm 1 stops. We define

$\hat{t}(x_{h,i})=\min\;\\{1\leq t\leq
T_{n},\;\;\mathcal{X}_{h,i}\in\mathcal{X}_{u}^{(t)}\\}$

By convention, $\hat{t}(x_{h,i})=+\infty$ if
$\mathcal{X}_{h,i}\notin\mathcal{X}_{u}^{(t)}$ for all $1\leq t\leq T_{n}.$

The cell $\mathcal{X}_{h,i}$ is said to be active if
$\hat{t}(x_{h,i})<+\infty.$

######  Lemma A.4.

(Number of active cells at depth h)
Let $T_{n}$ be the last step at which Algorithm 1 stops. Let $h\geq 1$ and
$N_{act,h}(T_{n})$ be the number of active cells at depth $h$. Let us assume
that Assumptions 4.2, 4.4, (4.3) hold and that:

  * •

In Algorithm 1, the update of upper and lower confidence bounds are made
according to Equations (4.16), (4.15) which are stated in the main text.

  * •

In Algorithm 1, for all $1\leq t\leq T_{n}$, the refinement condition
$A_{r}^{(t)}(\mathcal{X}_{h,i})=True$ is equivalent to $V(n_{h,i}(t))\leq
2B_{h}$, where $n_{h,i}(t)$ is the number of interactions made with the cell
$\mathcal{X}_{h,i}$ up to step $t$.

Then on the event $E$, we have:

$N_{act,h}(T_{n})\leq
C\frac{\tau}{\rho^{hd}}+C^{\prime}\rho^{h(\alpha\beta-d)},$ (A.6)

where $C$ and $C^{\prime}$ are absolute constants.

###### Proof.

Let $h\geq 1$ be an integer, and $\tilde{\mathcal{X}}_{h}$ be the set of
active cells at depth $h$ and at step $T_{n}$. We have that, on the event $E$
and by Assumption 4.3:

$P_{X}\left(\bigcup_{\mathcal{X}_{h,i}\in\tilde{\mathcal{X}}_{h}}\mathcal{X}_{h,i}\right)=\sum_{i=1}^{N_{act,h}(T_{n})}P_{X}\left(\mathcal{X}_{h,i}\right)\geq
C^{\prime}_{0}N_{act,h}(T_{n})\nu_{1}^{d}\rho^{hd},$ (A.7)

where $C^{\prime}_{0}$ is an absolute constant which only depends on $d$.

Besides, by Lemma A.3 and Assumption 4.4, we have:

$P_{X}\left(\bigcup_{\mathcal{X}_{h,i}\in\tilde{\mathcal{X}}_{h}}\mathcal{X}_{h,i}\right)\leq\tau+C_{0}\rho^{h\alpha\beta},$

where
$C_{0}=\frac{C_{\beta}12^{\beta}}{\rho^{\alpha\beta}}\nu_{2}^{\alpha\beta}.$
Consequently, combining with (A.7), we get

$N_{act,h}(T_{n})\leq
C\frac{\tau}{\rho^{hd}}+C^{\prime}\rho^{h(\alpha\beta-d)}.$

∎

######  Lemma A.5.

(Largest depth $h_{max})$
Let $T_{n}$ the step at which the budget has been reached. Let $h_{max}(n)$ be
the largest depth at that step. Let us assume that Assumptions 4.2, 4.4, (4.3)
hold and that:

  * •

In Algorithm 1, the update of upper and lower confidence bounds are made
according to Equations (4.16), (4.15) which are stated in the main text.

  * •

In Algorithm 1, for all $1\leq t\leq T_{n}$, the refinement condition
$A_{r}^{(t)}(\mathcal{X}_{h,i})=True$ is equivalent to $V(n_{h,i}(t))\leq
2B_{h}$, where $n_{h,i}(t)$ is the number of interactions made with the cell
$\mathcal{X}_{h,i}$ up to step $t$.

Then, on the event $E$ we have:

$\rho^{h_{\max}(n)}\leq\left\\{\begin{array}[]{ll}\left(\frac{\tau}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d}}\quad\text{if}\;\tau\geq\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}\\\
\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d-\alpha\beta}}\;\text{if}\;\tau\leq\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}},\end{array}\right.$
(A.8)

where $c_{cs}$ is a constant independent of $n$.

###### Proof.

Let $\mathcal{X}_{h,i}$ be an active cell (as introduced in Definition A.1).
By construction, the Algorithm 1 does not interact with the cell
$\mathcal{X}_{h,i}$ indefinitely, and an upper bound on the number of
interactions is determined by the refinement criterion. In this case, the
number of interactions with $x_{h,i}$ is then upper bounded as follows for all
$t\leq T_{n}$:

$n_{h,i}(t)\leq\nu_{2}^{-2}\rho^{-2h\alpha}\log\left(2n^{3}M\right),$ (A.9)

then, in the event $E$, the label budget $n$ is therefore upper bounded by:

$n\leq
2\sum_{h=0}^{h_{max}(n)}N_{act,h}(T_{n})\left(\nu_{2}^{-2}\rho^{-2h\alpha}\log\left(2n^{3}M\right)\right).$
(A.10)

Besides, we have for $h\geq 1$, by Lemma A.4:

$N_{act,h}(T_{n})\left(\nu_{2}^{-2}\rho^{-2h\alpha}\log\left(2n^{3}M\right)\right)\leq\nu_{2}^{-2}\log\left(2n^{3}M\right)\left(C\tau\rho^{-h(2\alpha+d)}+C^{\prime}\rho^{-h(2\alpha+d-\alpha\beta)}\right).$

Equation (A.10) becomes:

$\displaystyle n$ $\displaystyle\leq
C_{1}\log\left(2n^{3}M\right)\left(C\sum_{h=0}^{h_{max}(n)}\tau\rho^{-h(2\alpha+d)}+C^{\prime}\sum_{h=0}^{h_{max}(n)}\rho^{-h(2\alpha+d-\alpha\beta)}\right)\quad\text{where}\,C_{1}=2\nu_{2}^{-2}$
$\displaystyle\leq
C_{1}\log\left(2n^{3}M\right)\left(C_{2}\tau\rho^{-h_{\max}(n)(2\alpha+d)}+C_{3}\rho^{-h_{\max}(n)(2\alpha+d-\alpha\beta)}\right)\quad\text{for
some constants}\;C_{2},C_{3}>0$ $\displaystyle\leq
C_{4}\log\left(2n^{3}M\right)\max\left(\tau\rho^{-h_{\max}(n)(2\alpha+d)},\rho^{-h_{\max}(n)(2\alpha+d-\alpha\beta)}\right)\quad\text{where}\;C_{4}=2\max(C_{3},C_{2})C_{1}.$

If
$\tau\rho^{-h_{\max}(n)(2\alpha+d)}\geq\rho^{-h_{\max}(n)(2\alpha+d-\alpha\beta)}$,
that is $\tau\geq\rho^{h_{\max}\alpha\beta}$, then we can easily obtain

$\rho^{h_{\max}(n)}\leq\left(\frac{\tau}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d}}$

Similarly, if
$\tau\rho^{-h_{\max}(n)(2\alpha+d)}\leq\rho^{-h_{\max}(n)(2\alpha+d-\alpha\beta)}$,
we get

$\rho^{h_{\max}(n)}\leq\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d-\alpha\beta}}.$

Consequently,

$\rho^{h_{\max}(n)}\leq\max\left(\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d-\alpha\beta}},\left(\frac{\tau}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d}}\right),$

which can be rewritten as:

$\rho^{h_{\max}(n)}\leq\left\\{\begin{array}[]{ll}\left(\frac{\tau}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d}}\quad\text{if}\;\tau\geq\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}\\\
\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{1}{2\alpha+d-\alpha\beta}}\;\text{if}\;\tau\leq\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}\end{array}\right.$
(A.11)

∎

######  Lemma A.6.

(monotonicity of the classification uncertainty)
For a fixed $t\geq 1$, let $I(t)$ be defined as:

$I(t)=\max_{\mathcal{X}_{h,i}\in\mathcal{X}_{u}^{(t)}}\;\left(\min_{y\in\mathcal{Y}^{(t)}_{h,i}}\,U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})-\min_{y\in\mathcal{Y}^{(t)}_{h,i}}L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})\right),$
(A.12)

where for $y\in\mathcal{Y}^{(t)}_{h,i}$, the quantities
$U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ and
$L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ are respectively the upper and lower
confidence bounds of $f(.;y)$ at step $t.$ Let us assume that

  * •

The Assumption 4.2 holds.

  * •

In Algorithm 1, the update of upper and lower confidence bounds are made
according to Equations (4.16), (4.15) which are stated in the main text.

Then, in the event $E$, the function $I$ is non increasing with respect to
$t$.

###### Proof.

This follows from the definition of $U_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ and
$L_{f(:;y)}^{(t)}(\mathcal{X}_{h,i})$ in Equations (4.16), (4.15). ∎

######  Lemma A.7.

(Rate of convergence)
Let us assume that Assumptions 4.2, 4.4, (4.3) hold and that:

  * •

In Algorithm 1, the update of upper and lower confidence bounds are made
according to Equations (4.16), (4.15) which are stated in the main text.

  * •

In Algorithm 1, for all $1\leq t\leq T_{n}$, the refinement condition
$A_{r}^{(t)}(\mathcal{X}_{h,i})=True$ is equivalent to $V(n_{h,i}(t))\leq
2B_{h}$, where $n_{h,i}(t)$ is the number of interactions made with the cell
$\mathcal{X}_{h,i}$ up to step $t$.

Then, with probability at least $1-\frac{1}{n}$, the excess risk of the
classifier $\hat{g}_{n}$ provided by Algorithm 1 satisfies:

$\varepsilon_{cs}(\hat{g}_{n})\leq\left\\{\begin{array}[]{ll}C_{6}\left(\frac{\tau}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}}\quad\text{if}\;\tau\geq\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}\\\
C_{9}\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\;\text{if}\;\tau\leq\left(\frac{1}{n}.c_{cs}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}},\end{array}\right.$
(A.13)

where $c_{cs},C_{6},C_{9}$ are absolute constants.

###### Proof.

On the event $E$, the excess can be rewritten as:

$\displaystyle\varepsilon_{cs}(\hat{g}_{n})$
$\displaystyle=\mathbb{E}_{X,c}(c(\hat{g}_{n})-c(f_{cs}^{*}(x)))$
$\displaystyle=\mathbb{E}_{X}\left[f(X;\hat{g}_{n}(X))-f(X;f_{cs}^{*}(X))\right]$
$\displaystyle=\mathbb{E}_{X}\left[f(X;\hat{g}_{n}(X))-f(X;f_{cs}^{*}(X))\mathds{1}_{X\in\bigcup_{\mathcal{X}_{h,i}\in\mathcal{X}_{u}^{(T_{n})}}\mathcal{X}_{h,i}}\mathds{1}_{f(X,\hat{g}_{n}(X))\neq
f(X,f_{cs}^{*}(X))}\right]\quad\text{by Lemma \ref{lemma:correct}},$

where $T_{n}$ is introduced in Lemma A.5.
Let $x$ $\in$ $\mathcal{X}_{h,i}$, with
$\mathcal{X}_{h,i}\in\mathcal{X}_{u}^{(T_{n})}$, then on the event $E$, we
have by definition of $\hat{g}_{n}$ and Equation (A.4)

$f(x,\hat{g}_{n}(x))-f(x,f_{cs}^{*}(x))\leq\min_{y\in\mathcal{Y}^{(T_{n})}_{h,i}}\,U_{f(:;y)}^{(T_{n})}(\mathcal{X}_{h,i})-\min_{y\in\mathcal{Y}^{(T_{n})}_{h,i}}L_{f(:;y)}^{(T_{n})}(\mathcal{X}_{h,i})$
(A.14)

At step $T_{n}$, let $\mathcal{X}_{h_{\max}(n),i_{\max}}$ be denoted as the
deepest active cell and $x_{h_{\max}(n),i_{\max}}$ its corresponding center.
As introduced in Definition A.1, let $\hat{t}(x_{h_{max}})\leq T_{n}$. To
simplify the notations, we denote $\hat{t}:=\hat{t}(x_{h_{max}}).$

Furthermore, let us consider $\mathcal{X}_{h_{\max}(n)-1,\tilde{i}}$ (for some
$\tilde{i}=1,\ldots 2^{h_{\max}(n)-1}$) the cell at the previous depth which
contains $x_{h_{\max}(n),i_{\max}}$ and we denote by
$x_{h_{\max}(n)-1,\tilde{i}}$ its corresponding center. Then by Lemma A.6, the
r.h.s of (A.14) can be upper bounded:

$f(x,\hat{g}_{n}(x))-f(x,f_{cs}^{*}(x))\leq\min_{y\in\mathcal{Y}^{(\hat{t})}_{h_{\max}(n)-1,\tilde{i}}}\,U_{f(:;y)}^{(\hat{t})}(\mathcal{X}_{h_{max}(n)-1,\tilde{i}})-\min_{y\in\mathcal{Y}^{(\hat{t})}_{h_{\max}(n)-1,\tilde{i}}}\,L_{f(:;y)}^{(\hat{t})}(\mathcal{X}_{h_{max}(n)-1,\tilde{i}})$
(A.15)

As the refinement criterion is satisfied at that time (at the beginning of
step $\hat{t}$) at $\mathcal{X}_{h_{\max}(n)-1,\tilde{i}}$, we have:

$V(n_{h_{\max}(n)-1,\tilde{i}}(\hat{t}))\leq 2B_{h_{\max}(n)-1},$

and Equation (A.15) becomes:

$f(x,\hat{g}_{n}(x))-f(x,f^{*}(x))\leq 6B_{h_{\max}(n)-1}.$ (A.16)

Besides, let $x$ $\in$
$\cup_{\mathcal{X}_{h,i}\in\mathcal{X}_{u}^{(T_{n})}}\mathcal{X}_{h,i}$ with
$f(x,\hat{g}_{n}(x))\neq f(x,f_{cs}^{*}(x))$, then we have:

$\displaystyle\Delta(x)$ $\displaystyle\leq f(x,\hat{g}_{n}(x))-f(x,f^{*}(x))$
$\displaystyle\leq 6B_{h_{\max}(n)-1}\quad\text{by
Equation}\;\eqref{eq:excess3}.$

Consequently, by using Assumption 4.4, we get:

$\varepsilon_{cs}(\hat{g}_{n})\leq 6B_{h_{\max}(n)-1}P_{X}\left(\Delta(x)\leq
6B_{h_{\max}(n)-1}\right)$

and by Lemma A.5, if

$\tau\geq\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}},$

we obtain:

$\displaystyle\varepsilon_{cs}(\hat{g}_{n})$ $\displaystyle\leq
C_{6}\rho^{h_{\max}(n)\alpha(\beta+1)}\quad\text{where}\;C_{6}=36C_{\beta}\frac{\nu_{2}^{\alpha(\beta+1)}}{\rho^{\alpha(\beta+1)}}$
$\displaystyle\leq
C_{6}\left(\frac{\tau}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}}.$

Similarly, if

$\tau\leq\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}},$
(A.17)

we have:

$\displaystyle\varepsilon_{cs}(\hat{g})$ $\displaystyle\leq
6b_{h_{\max}(n)-1}P_{X}\left(\Delta^{\prime}(x)\leq 6b_{h_{\max}(n)-1}\right)$
$\displaystyle\leq
C_{7}\rho^{h_{\max}(n)\alpha}\left(\tau+C_{8}\rho^{h_{\max}(n)\alpha\beta}\right)\quad\text{where}\;C_{7}=6\frac{\nu_{2}^{\alpha}}{\rho^{\alpha}},C_{8}=6C_{\beta}\frac{\nu_{2}^{\alpha(\beta+1)}}{\rho^{\alpha\beta}}.$

By using (A.17) and (A.8), we get:

$\displaystyle\varepsilon_{cs}(\hat{g})$
$\displaystyle\leq\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha}{2\alpha+d-\alpha\beta}}\left(\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}+C_{8}\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}\right)$
$\displaystyle\leq
C_{9}\left(\frac{1}{n}.C_{4}\log\left(2n^{3}M\right)\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}.$

∎

###  A.3 Proof of Theorem 4.6

This Section is devoted to provide the lower bounds corresponding to the upper
bounds provided in Theorem 4.5. We will firstly state the relation that exists
between problems from standard multiclass classification and cost-sensitive
classification. By referring to Assumptions respectively from Section 4.5.1,
this preliminary result will allow us to obtain our lower bound in cost-
sensitive setting through a lower bound obtained in standard classification.

####  A.3.1 Relation with multi-class classification

Let us consider the setting of the standard multi-class classification which
is defined as follows: let $\mathcal{Y}$ be the set of labels
$\\{1,\ldots,M\\}$, and an unknown probability $P$ defined on
$\mathcal{X}\times\mathcal{Y}$. We consider an i.i.d sample
$S_{n}=\\{(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})\\}$ generated according to the
probability $P.$ Based on the sample $S_{n}$, the aim is to construct a
classifier $\hat{g}:\mathcal{X}\longrightarrow\mathcal{Y}$ that minimizes the
error of classification

$R_{c\ell}(g)=P(g(X)\neq Y).$

Let $\eta(x)=(\eta_{1}(x),\ldots,\eta_{M}(x))$ be the regression function with
$\eta_{j}(x)=P(Y=j\,|X=x)$ for all $j$ $\in$ $\\{1,\ldots,M\\}$. It is well-
known that the oracle mapping

$f_{c\ell}^{*}(x)\in\operatorname*{arg\,max}_{j\in\\{1,\ldots,M\\}}\;\eta_{j}(x)$

minimizes the risk $R_{c\ell}(g)$ over all measurable classifiers.
For $x$ $\in$ $\mathcal{X}$, and $y\in\mathcal{Y}$, let $\Delta_{\eta}(x,y)$
be defined as:

$\Delta_{\eta}(x,y)=\max_{y^{\prime}\in\mathcal{Y}}\,\eta_{y^{\prime}}(x)-\eta_{y}(x),$

and

$\Delta_{\eta}(x)=\left\\{\begin{array}[]{ll}\min_{y\in\mathcal{Y}}\\{\Delta_{\eta}(x,y):\;\Delta_{\eta}(x,y)>0\\}\;\;\mbox{If}&\;\;\;\exists\;y\in\mathcal{Y},\;\Delta_{\eta}(x,y)>0\\\
\infty&\;\;\;\mbox{Otherwise.}\end{array}\right.$

Given an instance $x$, let us consider the order statistic on $\eta(x):$

$\eta_{(1)}(x)\geq\eta_{(2)}(x)\geq...\geq\eta_{(M)}(x).$

We define:

$\Delta^{\prime}_{\eta}(x)=\eta_{(1)}(x)-\eta_{(2)}(x).$

Equivalently as in the cost-sensitive setting, we introduce consider the
following assumptions standard multi-class classification:

######  Assumption A.8 (Refined margin noise assumption in multi-class
classification).

There exist parameters
$\beta_{\eta},C_{\beta_{\eta}},C^{\prime}_{\beta_{\eta}},\tau\geq 0$ such that
for all $\epsilon>0$

$P_{X}(x\in\mathcal{X},\;\;\Delta_{\eta}(x)\leq\epsilon)\leq
C_{\beta_{\eta}}\epsilon^{\beta_{\eta}},$

and

$P_{X}(x\in\mathcal{X},\;\;\Delta^{\prime}_{\eta}(x)\leq\epsilon)\leq\tau+C^{\prime}_{\beta_{\eta}}\epsilon^{\beta_{\eta}}.$

######  Assumption A.9 (Smoothness assumption on the regression function).

There exist two parameters $\alpha_{\eta}$, $L_{\eta}>0$ such that for all
$x$, $z$ $\in$ $\mathcal{X}$, we have

$|\eta_{y}(x)-\eta_{y}(z)|\leq L_{\eta}\parallel
x-z\parallel_{2}^{\alpha_{\eta}}\quad\text{for all}\;y\in\mathcal{Y}.$

Similarly as in Definition 4.2 in the main text, we introduce the class of
probabilities in standard classification setting.

######  Definition A.2 (Multi-class classification measure).

Let $\Xi=(0,1)\times(0,+\infty)^{4}\times[0,1]\times(0,1)\times(0,\infty)$.
For any
$\zeta=(\alpha_{\eta},L_{\eta},\beta_{\eta},C_{\beta_{\eta}},C^{\prime}_{\beta_{\eta}},\tau,\mu_{\min},\mu_{\max})\in\Xi$,
we denote $\mathcal{P}_{c\ell}(\zeta)$ the class of probability measures $P$
on $\mathcal{X}\times\mathcal{Y}$ such that:

  * •

The regression function $($associated to $P)$ $\eta$ satisfies Assumption A.9
with parameters $\alpha_{\eta},L_{\eta}$.

  * •

The probability $P$ satisfies Assumption A.8 with parameters
$\beta_{\eta},C_{\beta_{\eta}},C^{\prime}_{\beta_{\eta}},\tau$.

  * •

The probability $P$ satisfies Assumption 4.3 with parameters
$\mu_{\min},\mu_{\max}$.

Below, we state a result from (Reeve, 2019) which relates multi-class
classification problem to the corresponding problems within the cost-sensitive
framework.

######  Proposition A.10 ((Reeve, 2019)).

Let us suppose we have a classification problem which consists in minimising
over all measurable classifiers $g:\mathcal{X}\longrightarrow\mathcal{Y}$ the
error of classification $R_{c\ell}(g)=P(g(X)\neq Y)$ given an i.i.d sample
$(X_{1},Y_{1})\ldots,(X_{n},Y_{n})$ distributed according to a probability $P$
over $\mathcal{X}\times\mathcal{Y}$. To each couple $(X,Y)$, we associate
$(X,c)$ with $c=\Gamma^{(c\ell)}\Phi_{\mathcal{Y}}(Y)$ where
$\Gamma^{(c\ell)}$ is a $M\times M$ matrix defined by:
$\Gamma^{(c\ell)}_{ij}=1$ if $i\neq j$, $\Gamma^{(c\ell)}_{ii}=0$ and
$\Phi_{\mathcal{Y}}(Y)$ is a $M\times 1$ matrix with
$\Phi_{\mathcal{Y}}(Y)_{j1}=0$ if $j\neq Y$ and
$\Phi_{\mathcal{Y}}(Y)_{YY}=1$. This leads to a cost-sensitive problem $P^{*}$
with the following properties:

  * •

The oracle mapping $f_{cs}^{*}(x)$ $\in$
$\operatorname*{arg\,min}\\{y\in\mathcal{Y},f(x;y)\\}$ where
$f(x;y)=\mathbb{E}(c(y)|X=x)$.

  * •

Given any classifier $g:\mathcal{X}\longrightarrow\mathcal{Y}$, we have:

$\displaystyle\varepsilon_{cs}(g)$
$\displaystyle=\mathbb{E}\left[f(X;g(X))-f(X;f_{cs}^{*}(X))\right]$
$\displaystyle=\varepsilon_{c\ell}(g)=\mathbb{E}\left[\eta_{f_{c\ell}^{*}(X)}(X)-\eta_{g(X)}(X)\right].$

  * •

Let
$\zeta=(\alpha_{\eta},L_{\eta},\beta_{\eta},C_{\beta_{\eta}},C^{\prime}_{\beta_{\eta}},\tau,\mu_{\min},\mu_{\max})\in\Xi$
introduced in Definition A.2. Whenever the classification problem $P$ belongs
to $\mathcal{P}_{c\ell}(\zeta)$, the corresponding cost-sensitive problem
$P^{*}$ belongs to $\mathcal{P}_{cs}(\zeta)$.

The above proposition is very important as it allows to translate multi-class
classification problem to a corresponding one in cost-sensitive framework; in
this case, providing a lower bound in multi-class classification implies a
lower bound in the cost-sensitive framework.

Next, we state our result which provides a lower bound in active learning
classification. For simplicity, we will use $M=2$, but the extension to $M>2$
is straightforward.

####  A.3.2 Lower bounds for standard multi-class classification

######  Theorem A.11 (Lower bound for multi-class classification).

Let us consider a multi-class classification problem with $M=2$. Let
$\zeta=(\alpha,L,\beta,C_{\beta},C^{\prime}_{\beta},\tau,\mu_{\min},\mu_{\max})\in\Xi$
introduced in Definition A.2. We assume that
$L,C_{\beta},C^{\prime}_{\beta}\in(1,\infty)$, $\alpha\beta\leq d$ and
$\mu_{min}\in(0,\tau)$. There exist constants $C_{c\ell}$,
$C_{c\ell}^{\prime}$ (independent of $n$) such that for any active classifier
$\hat{g}_{n}$, we have:

$\inf_{\hat{g}_{n}}\sup_{P\in\mathcal{P}_{c\ell}(\zeta)}\mathbb{E}(R_{c\ell}(\hat{g}_{n}))-R_{c\ell}(g^{*}))\geq\min(a_{n,\tau},a^{\prime}_{n,\tau}),$

where

$a_{n,\tau}=C_{c\ell}\max\left(\left(\frac{\tau}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}},\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\right)$

and

$a^{\prime}_{n,\tau}=C^{\prime}_{c\ell}\max\left(\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}},\left(\frac{1}{\tau}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}}\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\right).$

The proof of Theorem A.11 consists in using some standard tools for minimax
lower bounds strategy where the aim is to firstly reduce the risk to a
multiple hypothesis problem, and thereafter apply Theorem 2.5 from (Tsybakov,
2009) presented below. Our proof is mainly based on the use of some universal
tools such as packing set. Consequently, it can be extended to general metric
spaces.

######  Theorem A.12 ((Tsybakov, 2009), Theorem 2.5).

Let $\Theta$ be a class of models and
$\tilde{d}:\Theta\times\Theta\longrightarrow\mathbb{R}$ a pseudo metric
defined on $\Theta$. Let $\\{P_{g},\;g\in\Theta\\}$ be a collection of
probability measures associated with $\Theta$. Let us assume there exists a
subset $\\{g_{0},\ldots,g_{\tilde{m}}\\}\subset\Theta$, with $\tilde{m}>1$
such that:

  * •

$\tilde{d}(g_{i},g_{j})>2s>0$ for all $0\leq i<j\leq\tilde{m},$

  * •

$P_{g_{j}}\ll P_{g_{0}}$ for every $1\leq j\leq\tilde{m},$

  * •

$\frac{1}{\tilde{m}}\sum_{j=1}^{\tilde{m}}KL\left(P_{g_{j}},P_{g_{0}}\right)\leq\gamma\log(\tilde{m})$,
where $0<\gamma<\frac{1}{8},$ and $KL(.,.)$ is the Kullback-Leibler
divergence.

Then,

$\inf_{\hat{g}}\sup_{g\in\Theta}\;P_{g}\left(\tilde{d}(\hat{g},g)>s\right)\geq\frac{\sqrt{\tilde{m}}}{1+\sqrt{\tilde{m}}}\left(1-2\gamma-\sqrt{\frac{2\gamma}{\log(\tilde{m})}}\right),$

where the infimum is taken over all possible estimators based on a sample
generated from $P_{g}.$

Proof of Theorem A.11

The proof consists in applying Theorem A.12 to a suitable family of
distributions $P$ from $\mathcal{P}(\zeta)$. In doing so, we will proceed in
several steps as follows:

  1. 1.

Construction of the family of measures

Let $\bar{x}=(\frac{1}{2},\ldots,\frac{1}{2})$ and $\bar{r}\in(0,1)$ small
enough, for example $\bar{r}=\frac{1}{128}.$ Let $r\in(0,1)$ small enough,
with $r\leq\bar{r}$ and $\\{x_{1},\ldots,x_{Q(r)}\\}$ a (maximal) packing set
of $B(\bar{x},\bar{r}).$ Let $m(r)\leq Q(r)$ be a positive quantity. Let us
consider the subset $\\{x_{1},\ldots,x_{m(r)}\\}$, and the set

$S(r)=\bigcup_{i=1}^{m(r)}\bar{B}(x_{i},\frac{r}{2}),$

where $B(x,r)=\\{z\in\mathcal{X},\;\|x-z\|<r\\}$ and
$\bar{B}(x,r)=\\{z\in\mathcal{X},\;\|x-z\|\leq r\\}$.
Let $r^{*}$ be defined as:

$r^{*}=\inf\\{r_{0}>0,\;S(r)\subset\bar{B}(\bar{x},r_{0})\\}.$ (A.18)

The quantity $r$ will be chosen small enough in order to have
$\bar{B}(\bar{x},r^{*})\subset[0,1]^{d}$. Let $a$ $\in[0,1]^{d}$, $c_{0}$,
$c_{1}$ $\in$ $(0,1)$ small enough and the Euclidean ball
$B(a,c_{0}r^{\frac{\alpha\beta}{d}})$ such that

$B(a,c_{1}r^{\frac{\alpha\beta}{d}})\bigcap
B(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})=\emptyset.$

Let $\phi$ be the function defined as:

$\displaystyle\phi\colon$ $\displaystyle[0,\,+\infty)\longrightarrow[0,1]$
$\displaystyle\phantom{++++}x\mapsto\min((2-3x)_{+},1),$

where $(z)_{+}=\max(z,0)$ for $z\in\mathbb{R}.$ The function $\phi$ is
3-Lipschitz.
As $\\{x_{1},\ldots,x_{m(r)}\\}$ is a $r-$ separated set, we have that
$B(x_{i},\frac{r}{2}),\;i=1\ldots,m(r)$ are disjoints sets. We thus define the
following functions for all $i$ $\in$ $\\{1,\ldots,m(r)\\}$ and $r$ small
enough:

$\displaystyle f_{i}\colon$ $\displaystyle[0,\,+\infty)\longrightarrow[0,1]$
$\displaystyle\phantom{++++}x\mapsto\frac{c_{2}}{d^{\frac{d}{2\beta}}}Lr^{\alpha}\phi\left(\frac{2}{r}\parallel
x-x_{i}\parallel\right)\mathds{1}_{B(x_{i},\frac{r}{2})},$

Where $c_{2}\in(0,\tfrac{1}{12L})$ is small enough. Finally, for all $\sigma$
$\in$ $\\{-1,1\\}^{m(r)}$, we define:

$\eta_{\sigma}(x)=\left\\{\begin{array}[]{ll}\frac{1}{2}+\sum_{i=1}^{m(r)}\sigma_{i}f_{i}(x)&\mbox{if
}\;x\in\bar{B}(\bar{x},r^{*})\\\
\frac{1}{2}+\frac{L}{d^{\frac{d}{2\beta}}}.dist(x,\bar{B}(\bar{x},r^{*}))^{\frac{d}{\beta}}&\mbox{if}\;x\in\bar{B}(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})\setminus\bar{B}(\bar{x},r^{*}).\\\
\frac{1}{2}+\frac{L}{d^{\frac{d}{2\beta}}}c_{0}^{d/\beta}r^{\alpha}&\mbox{elsewhere}\end{array}\right.$
(A.19)

where $dist(x,A)=\inf\\{\parallel x-y\parallel,\;y\in A\\}$ for
$x\in[0,1]^{d}$, and $A\subset[0,1]^{d}$. To ensure the smoothness condition,
we will chose $c_{2}\leq\frac{1}{12L}$ and
$c_{0}\leq\min\left(\frac{1}{12L},\left(\frac{1}{4L}\right)^{\beta/d}\right)$.

Besides, we define the marginal probability through the density:

$p(x)=\left\\{\begin{array}[]{ll}\frac{w}{Vol(B(x_{i},\frac{r}{6}))}&\mbox{if
}\;x\in\bar{B}(x_{i},\frac{r}{6}),i=1,\ldots,m(r).\\\
\frac{\tau}{Vol(A_{1})}&\mbox{if}\;x\in A_{1}.\\\
\frac{1-m(r)w-\tau}{Vol(A_{2})}&\mbox{if}\;x\in A_{2}.\\\
0&\mbox{elsewhere}.\end{array}\right.$ (A.20)

Where $0<w\leq\frac{1}{m(r)}$, $\tau$ comes from the Assumption 4.4,
$A_{1}=\bar{B}(\bar{x},r^{*})\setminus\bigcup\limits_{i=1}^{m(r)}B(x_{i},\frac{r}{3})$,
and $A_{2}=\bar{B}(a,c_{0}r^{\frac{\alpha\beta}{d}}).$

  2. 2.

Proof of the smoothness condition : we prove that the family of regression
functions defined above is well defined and satisfies the smoothness condition
A.9. The proof is closely related to the one provided in (Reeve, 2019).
By definition, the regression $\eta_{\sigma}$ is well-defined; in fact,
$\eta_{\sigma}(x)\in[0,1]$ for all $x\in[0,1]^{d}$.
Let $x,x^{\prime}\in[0,1]^{d}$. We firstly assume that $x,x^{\prime}$ $\in$
$\bar{B}(\bar{x},r^{*})$. If
$\eta_{\sigma}(x)=\eta_{\sigma}(x^{\prime})=\frac{1}{2}$, obviously, we have
$|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|\leq L\parallel
x-x^{\prime}\parallel^{\alpha}.$

Without loss of generality, let us assume $\eta_{\sigma}(x)\neq\frac{1}{2}$.
Then $x$ $\in$ $\bar{B}(x_{i},\frac{r}{3})$ for some $i=1,\ldots,m(r)$. If
$x^{\prime}$ $\in$ $B(x_{i},\frac{r}{2})$, then we have:

$\displaystyle|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|$ $\displaystyle\leq
6c_{2}\frac{L}{r}r^{\alpha}\left(\parallel x-x_{i}\parallel-\parallel
x^{\prime}-x_{i}\parallel\right)$ $\displaystyle\leq Lr^{\alpha-1}\parallel
x-x^{\prime}\parallel$ $\displaystyle\leq L\parallel
x-x^{\prime}\parallel^{\alpha}\quad\text{as}\;\parallel
x-x^{\prime}\parallel\leq r\;\text{and}\;\alpha\leq 1.$

If $x^{\prime}$ $\notin B(x_{i},\frac{r}{2})$, we have:

$\parallel x-x^{\prime}\parallel\geq\parallel
x_{i}-x^{\prime}\parallel-\parallel x_{i}-x\parallel\geq\frac{r}{6}.$

Consequently,

$\displaystyle|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|$
$\displaystyle=c_{2}Lr^{\alpha}\phi\left(\frac{2}{r}\parallel
x-x_{i}\parallel\right)$ $\displaystyle\leq L\parallel
x-x^{\prime}\parallel^{\alpha}$

If $x^{\prime}$ $\in$
$\bar{B}(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})\setminus\bar{B}(\bar{x},r^{*})$
and $x$ $\in$ $\bar{B}(\bar{x},r^{*})$ with $\eta(x)\neq\frac{1}{2}$, then $x$
$\in$ $B(x_{i},\frac{r}{3})$ for some $i=1,\ldots,m(r).$ In this case, we
have:

$\parallel x-x^{\prime}\parallel\geq\frac{r}{6}.$

Consequently,

$\displaystyle|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|$ $\displaystyle\leq
c_{2}Lr^{\alpha}\phi\left(\frac{2}{r}\parallel
x-x_{i}\parallel\right)+L.dist(x,\bar{B}(\bar{x},r^{*}))^{\frac{d}{\beta}}$
$\displaystyle\leq L\parallel x-x^{\prime}\parallel^{\alpha}.$

If $x^{\prime}$ $\in$
$\bar{B}(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})\setminus\bar{B}(\bar{x},r^{*})$
and $\eta(x)=\frac{1}{2}$, then we have:

$\displaystyle|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|$ $\displaystyle\leq
L.dist(x^{\prime},\bar{B}(\bar{x},r^{*}))^{\frac{d}{\beta}}$
$\displaystyle\leq L\parallel x-x^{\prime}\parallel^{\alpha}\quad.$

If $x,x^{\prime}$ $\in$
$\bar{B}(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})\setminus\bar{B}(\bar{x},r^{*})$,
by using the fact that $z\mapsto dist(z,\bar{B}(\bar{x},r^{*}))$ is Lipschitz,
we have:

$|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|\leq L\parallel
x-x^{\prime}\parallel^{\alpha}.$

If $x^{\prime}$ $\in$
$\bar{B}(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})\setminus\bar{B}(\bar{x},r^{*})$
and $x$ $\in$
$[0,1]^{d}\setminus\bar{B}(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})$ then
we have:

$dist(x,\bar{B}(\bar{x},r^{*}))\geq c_{0}r^{\frac{\alpha\beta}{d}}\geq
dist(x^{\prime},\bar{B}(\bar{x},r^{*}))$

we have thus:

$\displaystyle|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|$
$\displaystyle=\frac{L}{d^{\frac{d}{2\beta}}}c_{0}^{d/\beta}r^{\alpha}-\frac{L}{d^{\frac{d}{2\beta}}}.dist(x^{\prime},\bar{B}(\bar{x},r^{*}))^{\frac{d}{\beta}}$
$\displaystyle\leq\frac{L}{d^{\frac{d}{2\beta}}}(dist(x,\bar{B}(\bar{x},r^{*})^{d/\beta}-dist(x^{\prime},\bar{B}(\bar{x},r^{*})^{d/\beta})$
$\displaystyle\leq\frac{L}{d^{\frac{d}{2\beta}}}\parallel
x-x^{\prime}\parallel^{d/\beta}$ $\displaystyle\leq L\parallel
x-x^{\prime}\parallel^{\alpha}.$

If $x$, $x^{\prime}$ $\in$
$[0,1]^{d}\setminus\bar{B}(\bar{x},r^{*}+c_{0}r^{\frac{\alpha\beta}{d}})$,
obviously, we have:

$|\eta_{\sigma}(x)-\eta_{\sigma}(x^{\prime})|\leq L\parallel
x-x^{\prime}\parallel^{\alpha}.$

  3. 3.

Proof of the margin noise condition: we prove that the family
$(\eta_{\sigma},P_{X})$ satisfies Assumption A.8. This is crucial as it allows
us to provide an effective choice of $m(r)$ and $w$. On the support of $P_{X}$
except the set $A_{1}$, we have: $|\eta(x)-\frac{1}{2}|\geq c_{3}r^{\alpha}$,
where $c_{3}=\frac{L}{d^{\frac{d}{2\beta}}}\min(c_{2},c_{0}^{d/\beta})$.
Therefore, for $t>1$, we have:

$\displaystyle
P_{X}(x\in[0,1]^{d},\;0<|\eta(x)-\frac{1}{2}|<c_{3}tr^{\alpha})$
$\displaystyle\leq m(r)w+P_{X}(x\in
A_{2},\;0<|\eta(x)-\frac{1}{2}|<c_{3}tr^{\alpha})$ $\displaystyle\leq
m(r)w+P_{X}(B(a,c_{1}t^{\beta/d}r^{\alpha\beta/d}))\quad\text{as}\;t\geq 1$
$\displaystyle\leq m(r)w+c_{4}(tr^{\alpha})^{\beta}\quad\text{for some
constant }\;c_{4}$

By taking

$m(r)w=c_{5}r^{\alpha\beta},$ (A.21)

with $c_{5}$ is small enough, we get:

$P_{X}(x\in[0,1]^{d},\;0<|\eta(x)-\frac{1}{2}|<c_{3}tr^{\alpha})\leq
C_{\beta}\left(c_{3}tr^{\alpha}\right)^{\beta}.$ (A.22)

Besides, we have:

$P_{X}(\eta_{\sigma}(x)=\frac{1}{2})=P_{X}(A_{1})=\tau.$ (A.23)

Finally, by combining (A.22) and (A.23), we have that Assumption A.8 is
satisfied.

Moreover, we can easily check that Assumption 4.3 (with a suitable choice of
$m$ and $w$, which will be stated later) is also satisfied.

  4. 4.

Application of Theorem A.12

In order to apply Theorem A.12, we proceed as follows:

     * •

We choose $\Theta=\\{\eta_{\sigma},\;\sigma\in\\{-1,1\\}^{m(r)}\\}.$

     * •

In order to satisfy the first condition in Theorem A.12, we construct in a
wise way a well-separated subset of $\\{-1,1\\}^{m(r)}$ by invoking the
Gilbert-Varshamov’s Lemma (Tsybakov, 2009, Lemma 2.9): assuming $m(r)>8$,
there exists a subset $\\{\sigma^{0},\ldots,\sigma^{\tilde{m}(r)}\\}$ of
$\\{-1,1\\}^{m(r)}$ such that:

$\sigma^{0}=(1,\ldots,1)$

and for all $i\neq j$,

$d_{H}(\sigma^{i},\sigma^{j})>\frac{m(r)}{8},\quad\quad\tilde{m}(r)\geq
2^{m(r)/8},$ (A.24)

where $d_{H}$ stands for the Hamming distance.

     * •

We define the pseudo distance on
$\tilde{\Theta}=\\{\eta_{\sigma^{0}},\ldots,\eta_{\sigma^{\tilde{m}(r)}}\\}$:
for all $\sigma$, $\sigma^{\prime}\in$
$\\{\sigma^{0},\ldots,\sigma^{\tilde{m}(r)}\\}$,

$\tilde{d}(\eta_{\sigma},\eta_{\sigma^{\prime}})=P_{X}\left(\operatorname*{sign}(\eta_{\sigma}-\frac{1}{2})\neq\operatorname*{sign}(\eta_{\sigma^{\prime}}-\frac{1}{2})\right).$

By using (A.24), we have for all $\sigma$ $\neq$ $\sigma^{\prime}\in$
$\\{\sigma^{0},\ldots,\sigma^{\tilde{m}(r)}\\}$,

$\tilde{d}(\eta_{\sigma},\eta_{\sigma^{\prime}})\geq\frac{m(r)w}{8}.$ (A.25)

     * •

Next, for $\sigma$ $\in$ $\\{\sigma^{0},\ldots,\sigma^{\tilde{m}(r)}\\}$, let
us consider the corresponding probability $P_{\sigma}$ with regression
function $\eta_{\sigma}$ $\in$ $\tilde{\Theta}$, and marginal probability
$P_{X}$. Following the Lemma 1 in (Castro & Nowak, 2008), and Equation 10 in
(Minsker, 2012), we have:

$KL(P_{\sigma,n},P_{\sigma^{0},n})\leq 32nc_{5}r^{2\alpha}$ (A.26)

where

$c_{5}=2\left(\frac{c_{2}}{d^{\frac{d}{2\beta}}}L\right)^{2}$

and $P_{\sigma,n}$ is the joint probability of sample
$(X_{1},Y_{1}),\ldots,(X_{n},Y_{n})$ provided by any active learning
algorithm, with $(X_{i},Y_{i})\sim P_{\sigma}$ for all $1\leq i\leq n.$

We thus have to choose $m(r),r$ appropriately in order to have:

$KL(P_{\sigma,n},P_{\sigma^{0},n})\leq 32nc_{5}r^{2\alpha}\leq\gamma
m(r)\quad\text{with}\;0<\gamma<\frac{1}{8}.$

In that case, by (A.24), we obtain:

$\frac{1}{\tilde{m}}\sum_{j=1}^{\tilde{m}}KL\left(P_{g_{j}},P_{g_{0}}\right)\leq\gamma\log(\tilde{m}.)$

By setting $m(r)=\lfloor c_{6}r^{\alpha\beta-d}\rfloor$ and

$r=c_{7}\max\left(\left(\frac{\tau}{n}\right)^{\frac{1}{2\alpha+d}},\left(\frac{1}{n}\right)^{\frac{1}{2\alpha+d-\alpha\beta}}\right).$

Assuming $\tau\leq n^{-\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}$, we get:

$32nc_{5}r^{2\alpha}\leq\gamma^{\prime}m(r),$

for some constant $\gamma^{\prime}$. The constants $c_{6},c_{7}$ will be
chosen such that $0<\gamma^{\prime}<\frac{1}{8}$, $m(r)>8,$ and $m(r)\leq
Q(r).$

Let us take $w=c_{8}r^{d}$, with $c_{8}$ small enough in order to satisfy
(A.21), and make the marginal probability well-defined. In that case,
following (A.25), we have for all $\sigma\neq\sigma^{\prime}$ $\in$
$\\{\sigma^{0},\ldots,\sigma^{\tilde{m(r)}}\\}$:

$\tilde{d}(\eta_{\sigma},\eta_{\sigma^{\prime}})\geq
c_{9}\max\left(\left(\frac{\tau}{n}\right)^{\frac{\alpha\beta}{2\alpha+d}},\left(\frac{1}{n}\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}\right).$

We can conclude that for any active learning algorithm $\hat{\eta}:$

$\underset{\hat{\eta}}{inf}\;\underset{\sigma\in\\{\sigma_{0},\ldots,\sigma^{\tilde{m}(r)}\\}}{sup}\;\mathbb{P}\left(P_{X}(\operatorname*{sign}(\eta_{\sigma}(x)-\tfrac{1}{2})\neq\operatorname*{sign}(\hat{\eta}(x)-\tfrac{1}{2})\geq
c_{10}\max\left(\left(\frac{\tau}{n}\right)^{\frac{\alpha\beta}{2\alpha+d}},\left(\frac{1}{n}\right)^{\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}\right)\right)\geq\frac{1}{8},$

and then for any active learning algorithm $\hat{\eta}$ with corresponding
classifier $g_{\hat{\eta}}$, we have by using Proposition 3.1 from (Chzhen _et
al._ , 2021):

$\underset{\hat{\eta}}{inf}\;\underset{P\in\mathcal{P}_{cl}}{sup}\;\mathbb{P}\left(R_{cl,P}(g_{\hat{\eta}})-R_{cl,P}(g^{*})\geq
c_{11}\max\left(\left(\frac{\tau}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}},\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\right)\right)\geq\frac{1}{8},$

and finally, by Markov’s inequality, we get the required lower bound:

$\underset{\hat{\eta}}{inf}\;\underset{P\in\mathcal{P}_{cl}}{sup}\;\mathbb{E}\left(R_{cl,P}(g_{\hat{\eta}})-R_{cl,P}(g^{*})\right)\geq\frac{c_{11}}{8}\max\left(\left(\frac{\tau}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d}},\left(\frac{1}{n}\right)^{\frac{\alpha(\beta+1)}{2\alpha+d-\alpha\beta}}\right).$

In the case $\tau\geq n^{-\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}$, the
proof is nearly similar to the proof with $\tau\leq
n^{-\frac{\alpha\beta}{2\alpha+d-\alpha\beta}}$, differing only on the
bounding of the Kullback Leibler divergence and the choice of parameters $r$,
$m(r)$, $w$. Instead, we choose $r,m(r),w$ such that:

$r=c_{12}\max\left(\left(\frac{1}{n}\right)^{\frac{1}{2\alpha+d}},\left(\frac{1}{\tau}\right)^{\frac{1}{2\alpha+d}}\left(\frac{1}{n}\right)^{\frac{1}{2\alpha+d-\alpha\beta}}\right),$

$m(r)=\lfloor c_{13}r^{-d}\rfloor$, $w=c_{14}r^{d+\alpha\beta}$ with $c_{12}$,
$c_{14}$ small enough, and $c_{13}$ chosen such that $m(r)\leq Q(r)$,
$m(r)>8$.

####  A.3.3 Proof of Theorem 4.6

Theorem A.11 states that there are some constants $C_{cl}$, $C^{\prime}_{cl}$
(independent of $n$), such that any active learning classification algorithm
$\hat{g}$ which provides a sample $S_{n}:=(X_{i},Y_{i})_{1\leq i\leq n}$, and
thus a classifier $\hat{g}_{n,c\ell}$ based on $S_{n}$, there exists some
$\mathbb{P}$ $\in$ $\mathcal{P}_{c\ell}(\zeta)$ with:

$\mathbb{E}_{\sim\mathbb{P}^{n}}(R_{c\ell}(\hat{g}_{n,c\ell}))-R_{c\ell}(g^{*}))\geq\min(a_{n,\tau},a^{\prime}_{n,\tau}).$
(A.27)

Now, let us suppose we have an active learning algorithm $\hat{g}$, which,
through a sampling strategy, provides a sample
$S_{n,c\ell}=:(X_{i},Y_{i})_{1\leq i\leq n}$, and then a classifier
$\hat{g}_{n,c\ell}$ based on $S_{n}$. For some $\mathbb{P}$ $\in$
$\mathcal{P}_{c\ell}(\zeta)$, Equation (A.27) holds. Moreover, the active
learning algorithm $\hat{g}$ can be converted into an active learning
algorithm for cost-sensitive classification as follows:

  * •

Consider the same sampling strategy.

  * •

After getting the sample $(X_{t},Y_{t})$ at step $t$, we convert it into a
cost-sensitive vector $(X_{t},c_{t})$ following the procedure considered in
Proposition A.10.

Finally, we obtain the sample $S_{n,cs}:=(X_{i},c_{i})_{1\leq i\leq n}$, and
we provide the cost-sensitive classifier defined as
$\hat{g}_{n,cs}:=\hat{g}_{n,c\ell}.$ As considered in Proposition A.10, the
corresponding probability $P^{*}$ such that $((X_{t},Y_{t})\sim P$ implies
$(X_{t},c_{t})\sim P^{*})$ belongs to $\mathcal{P}_{cs}(\zeta)$ and again, by
Proposition A.10, we have:

$\displaystyle\mathbb{E}_{\sim(P*)^{n}}(R_{cs}(\hat{g}_{n,cs}))-R_{cs}(g^{*}))$
$\displaystyle=\mathbb{E}_{\sim
P^{n}}(R_{c\ell}(\hat{g}_{n,c\ell}))-R_{c\ell}(g^{*}))$
$\displaystyle\geq\min(a_{n,\tau},a^{\prime}_{n,\tau}).$

Thus, we get the same lower bounds in the cost-sensitive learning:

$\inf_{\hat{g}_{n}}\sup_{P\in\mathcal{P}_{cs}(\zeta)}\mathbb{E}(R_{cs}(\hat{g}_{n}))-R_{cs}(g^{*}))\geq\min(a_{n,\tau},a^{\prime}_{n,\tau}).$

## References

  * Agarwal (2013) Agarwal, A. (2013).  Selective sampling algorithms for cost-sensitive multiclass prediction.  In _International Conference on Machine Learning_ , pp. 1220–1228. PMLR.
  * Audibert & Tsybakov (2007) Audibert, J.-Y. & Tsybakov, A. B. (2007).  Fast learning rates for plug-in classifiers.  _The Annals of statistics_ 35, 608–633.
  * Balcan _et al._ (2007) Balcan, M.-F., Broder, A. & Zhang, T. (2007).  Margin based active learning.  In _International Conference on Computational Learning Theory_ , pp. 35–50. Springer.
  * Castro & Nowak (2008) Castro, R. M. & Nowak, R. D. (2008).  Minimax bounds for active learning.  _IEEE Transactions on Information Theory_ 54, 2339–2353.
  * Chzhen _et al._ (2021) Chzhen, E., Denis, C. & Hebiri, M. (2021).  Minimax semi-supervised set-valued approach to multi-class classification.  _Bernoulli_ 27, 2389–2412.
  * Cohn _et al._ (1994) Cohn, D., Atlas, L. & Ladner, R. (1994).  Improving generalization with active learning.  _Machine learning_ 15, 201–221.
  * Dasgupta (2011) Dasgupta, S. (2011).  Two faces of active learning.  _Theoretical computer science_ 412, 1767–1781.
  * Dmochowski _et al._ (2010) Dmochowski, J. P., Sajda, P. & Parra, L. C. (2010).  Maximum likelihood in cost-sensitive learning: Model specification, approximations, and upper bounds.  _Journal of Machine Learning Research_ 11.
  * Elkan (2001) Elkan, C. (2001).  The foundations of cost-sensitive learning.  In _International joint conference on artificial intelligence_ , vol. 17, pp. 973–978. Lawrence Erlbaum Associates Ltd.
  * Gentile & Orabona (2012) Gentile, C. & Orabona, F. (2012).  On multilabel classification and ranking with partial feedback.  _Advances in Neural Information Processing Systems_ 25.
  * Hanneke & Yang (2015) Hanneke, S. & Yang, L. (2015).  Minimax analysis of active learning.  _The Journal of Machine Learning Research_ 16, 3487–3602.
  * Kpotufe _et al._ (2022) Kpotufe, S., Yuan, G. & Zhao, Y. (2022).  Nuances in margin conditions determine gains in active learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 8112–8126. PMLR.
  * Krishnamurthy _et al._ (2017) Krishnamurthy, A., Agarwal, A., Huang, T.-K., Daumé III, H. & Langford, J. (2017).  Active learning for cost-sensitive classification.  In _International Conference on Machine Learning_ , pp. 1915–1924. PMLR.
  * Krishnamurthy _et al._ (2019) Krishnamurthy, A., Agarwal, A., Huang, T.-K., III, H. D. & Langford, J. (2019).  Active learning for cost-sensitive classification.  _Journal of Machine Learning Research_ 20, 1–50.  URL http://jmlr.org/papers/v20/17-681.html.
  * Locatelli _et al._ (2017) Locatelli, A., Carpentier, A. & Kpotufe, S. (2017).  Adaptivity to noise parameters in nonparametric active learning.  In _Proceedings of the 2017 Conference on Learning Theory, PMLR_.
  * Minsker (2012) Minsker, S. (2012).  Plug-in approach to active learning.  _Journal of Machine Learning Research_ 13.
  * Munos _et al._ (2014) Munos, R. _et al._ (2014).  From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning.  _Foundations and Trends® in Machine Learning_ 7, 1–129.
  * Njike & Siebert (2022) Njike, B. N. & Siebert, X. (2022).  Multi-class classification in nonparametric active learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 7124–7162. PMLR.
  * Reeve & Brown (2017) Reeve, H. W. & Brown, G. (2017).  Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours.  In _International Conference on Algorithmic Learning Theory_ , pp. 11–56.
  * Reeve (2019) Reeve, H. W. J. (2019).  _Learning in high dimensions with asymmetric costs_.  The University of Manchester (United Kingdom).
  * Shekhar _et al._ (2021) Shekhar, S., Ghavamzadeh, M. & Javidi, T. (2021).  Active learning for classification with abstention.  _IEEE Journal on Selected Areas in Information Theory_ 2, 705–719.
  * Tsybakov (2009) Tsybakov, A. B. (2009).  Springer series in statistics.