Active learning is a machine learning approach for reducing the data labeling effort. Given an instance space X or a pool of unlabeled data provided by a distribution , the learner focuses its labeling effort only on the most “informative” points so that a model built from them can achieve the best possible guarantees (Dasgupta, 2011). Such guarantees are particularly interesting when they are significantly better than those obtained in passive learning (Hanneke and Yang, 2015). In the context of this work, we consider binary classification (where the label Y of X takes its value in {0, 1}) in a nonparametric setting. Extensions to multiclass classification and adaptive algorithms are discussed at the end of this paper (Section 6).

The nonparametric setting has the advantage of providing guarantees with many informations such as the dependence on the dimensional and distributional parameters by using some hypotheses on the regularity of the decision boundary (Castro and Nowak, 2008), on the regression function (Minsker, 2012; Locatelli et al., 2017), and on the geometry of instance space (called strong density assumption) (Audibert and Tsybakov, 2007; Locatelli et al., 2017; Minsker, 2012). One of the initial works on nonparametric active learning (Castro and Nowak, 2008) assumed that the decision boundary is the graph of a smooth function, that a margin assumption very similar to Tsybakov’s noise assumption (Mammen and Tsybakov, 1999) holds, and that distribution is uniform. This led to a better guarantee than in passive learning. Instead of the assumption on the decision boundary, other works (Minsker, 2012; Locatelli et al., 2017) supposed rather that the regression function is smooth (in some sense). This assumption, along with Tsybakov’s noise assumption and the strong density assumption also gave a better guarantee than in passive learning. Moreover, unlike in (Castro and Nowak, 2008), they provided algorithms that are adaptive with respect to the margin’s noise and to the smoothness parameters.

However, recent work (Chaudhuri and Dasgupta, 2014) pointed out some disadvantages of the preceding smoothness assumption, and extended it in the context of passive learning with k-nearest neighbors (k-NN) by using a more general smoothness assumption that is able to sharply characterize the rate of convergence for all probability distributions that satisfy it.

In this paper, we thus extend the work of (Chaudhuri and Dasgupta, 2014) to the active learning setting, and provide a novel algorithm that outputs a clas-sifier with the same rate of convergence as other recent algorithms with more restrictive hypotheses, as for example (Minsker, 2012; Locatelli et al., 2017). Section 2 introduces general definitions, Section 3 presents previous work on convergence rates in active and passive non-parametric learning, with a special emphasis on the assumptions related to our work. Section 4 provides an outline of our algorithm while Section 5 describes its theoretical motivations and Section 6 contains the conclusion and some perspectives for future work.

We begin with some general definitions and notations about active learning in binary classification, then recall the concept of k-NN classifiers. Finally, the main assumptions that are used in nonparametric active learning are explained.

2.1 Active learning setting

Let () be a metric space. In this paper we set and refer to it as the instance space, and take as the Euclidean metric. Let Y = {0, 1} the label space. We assume that the pairs (X, Y ) are random variables distributed according to an unknown probability P over . Let us denote the marginal distribution of P over X.

Given and an i.i.d. sample () drawn according to probability P, the learning problem consists in minimizing the risk R(f) = )) over all measurable functions, called classifiers, .

In active learning, the labels are not available from the beginning but we can request iteratively at a certain cost (to a so-called oracle) a given number n of samples, called the budget (). In passive learning, all labels are available and n = w. At any time, we choose to request the label of a point X according to the previous observations. The point X is chosen to be most “informative”, which amounts to belonging to a region where classification is difficult and requires more labeled data to be collected. Therefore, the goal of active learning is to design a sampling strategy that outputs a classifier whose excess risk (see below) is as small as possible with high probability over the requested samples, as reviewed in (Dasgupta, 2011; Hanneke and Yang, 2015; Dasgupta, 2017).

Given x in X, let us introduce the regression function ) = E(Y |X = x) = P(Y = 1| X = x). It is easy to show (Lugosi, 2002) that the function ) = achieves the minimum risk and that ) = (min())). Because P is unknown, the function is unreachable and thus the aim of a learning algorithm is to return a classifier with minimum excess risk R( ) with high probability over the sample ().

2.2 k-Nearest Neighbors (k-NN) classifier

Given two integers k, n such that k < n, and a test point , the k-NN classifier predicts the label of X by giving the majority vote of its k nearest neighbors amongst the sample . For k = 1, the k-NN classifier returns the label of the nearest neighbor of X amongst the sample . If k is allowed to grow with n, the method is called -NN. For a complete discussion of nearest neighbors classification, see for example (Biau and Devroye, 2015; Shalev-Shwartz and Ben-David, 2014; Chaudhuri and Dasgupta, 2014).

2.3 Regularity, noise and strong density assumptions

Let B(x, r) = and ¯B(x, r) = the open and closed balls (with respect to the Euclidean metric ), respectively, centered at with radius r > 0. Let supp() = 0the support of the marginal distribution .

Let [0, 1] be the regression function defined as ) = P(Y = 1|X = x). We say that is ()-(0 and 1) if ,

The notion of H¨older continuity ensures that the proximity between two closest (according to the metric ) points is reflected in a similar value of the conditional probability .

This definition remains true for a general metric space, but when is the Euclidean metric, we should always have 0 1, otherwise becomes constant(Pugh, 2002).

In most of the previous works (for example (Audibert and Tsybakov, 2007; Minsker, 2012; Ga¨ıffas, 2007)), the definition H1a is used along with the following notion (H1b) for technical reasons.

Let P be the probability distribution defined over and the marginal distribution of P over X. We say that P satisfies the strong density assumption if there exists some constants 0, 0, 0 such that for all supp():

where is the density function of the marginal distribution and is the Lebesgue measure.

The strong density assumption ensures that, given a realisation X = x according to , there exists an infinite number of realisations = in a neighborhood of x.

Sometimes, the notion of strong density is used to geometrically characterize the set where the classification is difficult (Locatelli et al., 2017), and then combined with the following definition of Margin noise, allows to nicely control the error of classification beyond a given number of label requests.

The probability distribution P satisfies the margin noise assumption (sometimes called assumption (Audibert and Tsybakov, 2007)) with parameter 0 if for all 0 1, there is [1[ such that

The margin noise assumption gives a bound on the probability that the label of the points in the neigborhood of a point x differs from the label of x given by the conditional probability ). It also describes the behavior of the regression function in the vicinity of the decision boundary ) = . When goes to infinity, we observe a “jump” of around the decision boundary, and then we obtain Massart’s noise condition (Massart and N´ed´elec, 2006). Small values of allow for to “cuddle” when we approach the decision boundary.

Let 0 1 and L > 1. The regression function is (if for all supp() we have:

where d is the dimension of the instance space.

Equivalently, (H3) can be rewritten as:

It is important to note that the ()-smooth assumption (H3) is more general than the H¨older continuity assumption (H1a), as stated in Theorem 1 below.

Suppose that , that the regression function is ()-H¨older continuous, and that satisfies H1b. Then there is a constant L > 1 such that for any supp(), we have:

The marginal distribution is a doubling-probability if there exists a constant 0 such that for any , and r > 0, we have:

This notion was initially introduced for geometric purposes in the setting of measure theory (Heinonen, 2012; Federer, 2014). It helps for constructing a subcover of a metric space by also minimizing the overlap between the elements of the subcover. Doubling-probability has been used in a machine learning context, particularly k-NN classification (or regression), where the constant is interpreted as the intrinsic dimension of the region where the data belong (Kpotufe, 2011). This allows to reduce considerably the complexity of the clas-sification problem and to bypass the so-called curse of dimension. Also, it is also proved (Kpotufe, 2011) that the notion of doubling-probability generalizes the strong density assumption H1b. It is thus more universal, and does not require a probability density.

In this paper, doubling-probability is used only for geometrical purposes. It is later relaxed, so that it becomes sufficient to consider only balls B(x, r) with )) sufficiently large to satisfy the doubling-probability condition (H4).

3.1 Previous work

Active learning theory has been mostly studied during the last decades in a parametric setting, see for example (Balcan et al., 2010; Hanneke, 2011; Dasgupta, 2017) and references therein. One of the pioneering works studying the achievable limits in active learning in a nonparametric setting (Castro and Nowak, 2008) required that the decision boundary is the graph of a H¨older continuous function with parameter (H1a). Using a notion of margin noise (with parameter ) very similar to (H2), the following minimax rate was obtained:

where = and d is the dimension of instance space ().

Note that this result assumes the knowledge of the smoothness and margin noise parameters, whereas an algorithm that achieves the same rate, but that adapts to these parameters was proposed recently in (Locatelli et al., 2018).

In passive learning, by assuming that the regression function is H¨older continuous (H1a), along with (H1b) and (H2), the following minimax rate was established (Audibert and Tsybakov, 2007):

In active learning, using the same assumptions (H1a), (H1b) and (H2), with the additional condition , the following minimax rate was obtained (Locatelli et al., 2017)

where ˜O indicates that there may be additional logarithmic factors. This active learning rate given by (3) thus represents an improvement over the passive learning rate (2) that uses the same hypotheses.

With another assumption on the regression function relating the and approximation losses of certain piecewise constant or polynomial approximations of in the vicinity of the decision boundary, the same rate (3) was also obtained (Minsker, 2012).

3.2 Link with k-NN classifiers

For practicals applications, an interesting question is whether k-NN classifiers attain the rate given by (2) in passive learning and by (3) in active learning. In passive learning, under assumptions (H1a), (H1b) and (H2), and for suitable , it was shown in (Chaudhuri and Dasgupta, 2014) that -NN indeed achieves the rate (2).

In active learning a pool-based algorithm that outputs a k-NN classifier has been proposed in (Kontorovich et al., 2016), but its assumptions differ from ours in terms of smoothness and noise. Similarly, the algorithm proposed in (Hanneke) outputs a 1-NN classifier based on a subsample of a given pool of data, such that the label of each instance of this subsample is determined with high probability by the labels of its neighbors within the pool. The number of neighbors is adaptively chosen for each instance in the subsample, leading to the minimax rate (3) under the same assumptions as in (Locatelli et al., 2017).

To obtain more general results on the rate of convergence for k-NN classifiers in metric spaces under minimal assumptions, the more general smoothness assumption given by (H3) was used in (Chaudhuri and Dasgupta, 2014). By using a k-NN algorithm, and under assumptions (H2) and (H3), the rate of convergence obtained in (Chaudhuri and Dasgupta, 2014) is also of the order of (2). Additionally, using assumption (H3) instead of (H1a) removes the need for the strong density assumption (H1b), which therefore allows for more probability classes.

3.3 Contributions of the current work

In this work, we will use the assumptions that were used in the context of passive learning in (Chaudhuri and Dasgupta, 2014), and show that is is possible to use them in active learning as well.

For the sake of clarity, let us restate here these assumptions that will be used throughout this paper. We assume that the assumptions (H3), (H2), (H4) simultaneously hold respectively with parameters (), (.

In this paper, we provide an active learning algorithm under assumptions (H3), (H2) that were used in passive learning in (Chaudhuri and Dasgupta, 2014). We additionally assume that the underlying marginal probability satisfies (H4) mostly for geometrical convenience. Our algorithm has several advantages:

• According to the assumption (H2), as we will see, our algorithm also (as in (Minsker, 2012)) covers the most interesting case where the regression function is allowed to cross the boundary decision ) =

As explained in Section 2.1, we consider an active learning setting with a pool of i.i.d. unlabeled examples . Let the budget, that is the maximum number of points whose label we are allowed to query to the oracle. The objective of the algorithm is to build a 1-NN classifier, based on a labelled set of carefully chosen points. This set contains a subset of most informative points in K and is called the active set. More precisely, a point is considered informative if its label cannot be inferred (see below) from the previous observations (with ). The set starts with chosen arbitrarily in K and stops when the budget n is reached or when is attained.

When a point is informative, instead of requesting directly its label to the (noisy) oracle, we infer it by requesting the labels of its nearest neighbors in K, as was done in (Hanneke). This is reasonable for practical situations where the uncertainty about the label of has to be overcome, and it is related to the assumption (H3). Note that it differs from the setting of (Locatelli et al., 2018), where the label of is requested several times. The number of neighbors used for inferring that label of is determined such that, while respecting the budget, we can predict with high confidence the true label as ) of by the empirical mean of the labels of its nearest neighbors.

The labelled active set output by the algorithm will comprise only the informative points on which we have sufficient guarantees when considering the inferred label as the right label. Finally, we show that the labelled active set is sufficient to predict the label of any new point with a 1-NN classification rule .

4.2 Algorithm

The KALLS algorithm (Algorithm 1) aims at determining the active set defined in Section 4.1 and the related 1-NN classifier under the assumption (H3) and (H2).

Before beginning the description of KALLS, let us introduce some variables and notations, whose precise form will be justified in Section 5. The latter contains the proof sketch of the convergence of KALLS, while the complete proofs are in Appendix A.

For (0, 1), 1, set:

where

Let

For , we denote henceforth by its k-th nearest neighbor in K, and the corresponding label. For an integer 1, let

The inputs of KALLS are a pool K of unlabelled data of size w, the budget n, the smoothness parameters () from (H3), the margin noise parameters (, C) from (H2), a confidence parameter (0, 1) and an accuracy parameter (0, 1). For the moment, these parameters are fixed from the beginning but adaptive algorithms such as (Locatelli et al., 2017) could be exploited, in particular for the and parameters.

At any given stage, the current version of the labelled active set is denoted by . Based on , with high confidence, the 1-NN classifier agrees with the Bayes classifier at points that lie beyond some margin 0 of the decision boundary. Formally, given such that , we have ) = with high confidence. We will show in Section 5 that, with a suitable choice of , the assumption (H2) leads to the desired rate of convergence (3).

KALLS uses two main subroutines : Reliable and ConfidentLabel, which are detailed below in Sections 4.3 and 4.4, respectively.

4.3 Reliable subroutine

The Reliable subroutine is a binary test that checks if the label of a current point X can be inferred with high confidence from some previously informative points before reaching X. These points are obtained via a set called current active set. Each element of can be seen as a triplet () where is an informative point, its inferred label, and c > 0 can be thought as

a guarantee for predicting the right label Y of as . Formally, we have when (and is relatively far from the decision boundary. If ) outputs True, the point X is not considered to be informative, and will not be updated. By convention, ) always returns False.

The inputs are the current point X, a confidence parameter , the smoothness parameters () from (H3), and the set before examining the point X.

If entails the same confidence lower bound O(c) as that of some previous informative point (with (), there is a low degree of uncertainty on the label of X, and X is considered to be uninformative.

Using the assumption (H3), it suffices to have

Because the appearing in (9) are unknown, it has to be replaced by an estimate. We will show that it can be estimated with arbitrary precision and confidence using only unlabelled data from K. The Reliable subroutine uses 50) (inspired from (Kontorovich et al., 2016)) as follows:

1. Call the subroutine 50). 2. To draw a single in 50), sample randomly an example from K, and set .

The subroutine BerEst consists in estimating adaptively with high probability the expectation of a Bernoulli variable . In our setting, we estimate a probability-ball, so that a realisation of Z can be set as = 1. The variables are sampled at the beginning for theoretical analysis where we want a concentration inequality to hold for a number of samples greater than 4 (see (Kontorovich et al., 2016; Maurer and Pontil, 2009) for more details).

However, it is not dramatic if is supposed to be known by the learner. This is not a limitation, since it can be assumed that the pool K of data is large enough such that can be estimated to any desired accuracy.

If a point X is considered informative, it is introduced in the ConfidentLabel (Algorithm(5)), along with an integer , a budget parameter t and a confi-dence parameter . This subroutine infers with high confidence (at least 1) the label of X, by using the labels of its nearest neighbors, knowing that we can request at most t labels. The parameter is chosen such that, with high probability, the empirical majority of the -NN labels differs from the majority in expectation by less than some margin, and all the -NN are at most at some distance from X. The ConfidentLabel subroutine outputs , Q where Q represents the set of labeled nearest neighbors in the subroutine, and represents the majority label in Q.

This Section provides the main results and theoretical motivations behind the KALLS algorithm. Let us recall is the pool of unlabeled data and n is the budget.

Let us denote by the set of active learning algorithms on K, and ) the set of probabilities that satisfy assumption (H3) and (H2).

Additionally, let us introduce the set of probabilities ) on . A probability ) if ) and its marginal probability is a doubling-probability. For , we denote by := the classifier that is provided by A.

Theorem 2 and its equivalent form in Theorem 3 are the main results of this paper. They provide bounds on the excess risk for the KALLS algorithm in terms of the set ). The main idea of the proof is sketched in Section 5.2, while a detailed proof can be found in Appendix A.

5.1 Main results

Let the set ) such that where d is the dimension of the input space . For ), if is the 1 classifier provided by KALLS, then we have:

The result (10) is also stated below (Theorem 3) in a more practical form using label complexity. This latter form will be used in the proof.

Before proving this theorem, a couple of important remarks should be made:

1. The rate of convergence (10) obtained in Theorem 2 is an improvement over

2. The rate (10) is also minimax. Indeed, let us introduce the set of probabilities ¯) that satisfy the H¨older continuous assumption (H1a) (with parameter ), strong density assumption (H1b), and margin noise assumption (H2).

Let us assume that . It was proven in (Minsker, 2012) that if [0, 1], there exists a constant 0 such that for all n large enough and for any active classifier , we have:

Moreover, the strong density assumption implies the doubling-probability assumption (Kpotufe, 2011), and according to Theorem 1, the lower bound obtained in (17) is also valid for the family of probabilities ).

For a classifier , it is well known(Lugosi, 2002) that the excess of risk is:

We thus aim to prove that (11) is a sufficient condition to guarantee (with probability ), that agrees with on the set , for a suitable choice of 0.

Introducing in (18) leads to:

Therefore, if then we have immediately, . On the other hand, if , by hypothesis (H2), we have 2In the latter case, setting guarantees . Altogether, using for the value = max( ) guarantees R( . This explains the expression (6).

We present the proof sketch of Theorem 3 in three main steps, and refer to the corresponding Lemmas and Theorems in the Appendix A for more details.

will be violated after at most ˜) requests, with ˜). Also, the label inferred after ˜) label requests corresponds to the true label ). The intuition behind is to adapt the number of labels requested with respect to the noise; i.e., fewer label requests on a less noisy point (i.e., ), and more label requests on a noisy point. This provides significant savings in the number of requests needed to predict with high probability the correct label.

• In the event , any informative point falls in a high density region such that all the ) nearest neighbors of are within at most some distance to , and the condition (12) is sufficient to have .

(21) In this case, let be such a point that satisfies (20) and (21), we can easily prove that when is relatively far from the boundary, i.e.,

and easily deduce by using the smoothness assumption, (21) and (22), that the points and have the same label, then we do not need to use in the subroutine ConfidentLabel (Algorithm 5) and is an uninformative point. In addition, (13) is a sufficient condition such that the number of

The set I is introduced in KALLS (Algorithm(1)) as the set of informative points indexes. Let = max I, the index of the last informative point.

For (0defined in (6), and () the smoothness parameters, let us introduce

where is the nearest neighbor of x in , and the 1-NN classifier on . Additionally, on we prove that (11) is sufficient to obtain (23).

In this paper we first reviewed the main results for convergence rates in a non-parametric setting for active learning, with a special emphasis on the relative merits of the assumptions about the smoothness and the margin noise. Then, by putting active learning in perspective with recent work on passive learning, we provided a novel active learning algorithm with a particular smoothness assumption customized for k-NN.

We showed that our algorithm has a convergence rate comparable to state-of-the art active learning algorithms, but using less restrictive assumptions.

This removes unnecessary restrictions on the distribution that would exclude important densities (e.g., Gaussian). Additionally, our algorithm can readily be extended to multi-class classifi-cation, and then compared to recent results obtained in passive learning by (Reeve and Brown, 2017) which extended the work of (Chaudhuri and Dasgupta, 2014) to multi-class classification. Finally, an important direction for further work is to extend our results to the case where the key parameters of the problem (defining smoothness and noise) are unknown. Ongoing work in this direction builds upon previous results in an adaptive setting (Locatelli et al., 2017), (Minsker, 2012), (Balcan and Hanneke, 2012), (Hanneke, 2011).

Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of statistics, 35(2):608–633, 2007.

Maria Florina Balcan and Steve Hanneke. Robust interactive learning. In Conference on Learning Theory, pages 20–1, 2012.

Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Machine learning, 80(2-3):111– 139, 2010.

G´erard Biau and Luc Devroye. Lectures on the nearest neighbor method. Springer, 2015.

Rui M Castro and Robert D Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):2339–2353, 2008.

Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for near- est neighbor classification. In Advances in Neural Information Processing Systems, pages 3437–3445, 2014.

Sanjoy Dasgupta. Two faces of active learning. Theoretical computer science, 412(19):1767–1781, 2011.

Sanjoy Dasgupta. Active learning theory. Encyclopedia of Machine Learning and Data Mining, pages 14–19, 2017.

Maik D¨oring, L´aszl´o Gy¨orfi, and Harro Walk. Rate of convergence of k-nearest- neighbor classification rule. The Journal of Machine Learning Research, 18 (1):8485–8500, 2017.

Gerald A Edgar. Packing measure in general metric space. Real Analysis Exchange, 26(2):831–852, 2000.

Herbert Federer. Geometric measure theory. Springer, 2014.

St´ephane Ga¨ıffas. Sharp estimation in sup norm with random design. Statistics & probability letters, 77(8):782–794, 2007.

Steve Hanneke. Nonparametric active learning, part 1: Smooth regression functions.

Steve Hanneke. Rates of convergence in active learning. The Annals of Statistics, 39(1):333–361, 2011.

Steve Hanneke and Liu Yang. Minimax analysis of active learning. The Journal of Machine Learning Research, 16(1):3487–3602, 2015.

Juha Heinonen. Lectures on analysis on metric spaces. Springer Science & Business Media, 2012.

Wassily Hoeffding. Probability inequalities for sums of bounded random vari- ables. Journal of the American Statistical Association, 58(301):13–30, 1963.

Emilie Kaufmann, Olivier Capp´e, and Aur´elien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1–42, 2016.

Aryeh Kontorovich, Sivan Sabato, and Ruth Urner. Active nearest-neighbor learning in metric spaces. In Advances in Neural Information Processing Systems, pages 856–864, 2016.

Samory Kpotufe. k-nn regression adapts to local intrinsic dimension. In Advances in Neural Information Processing Systems, pages 729–737, 2011.

Andrea Locatelli, Alexandra Carpentier, and Samory Kpotufe. Adaptivity to noise parameters in nonparametric active learning. Proceedings of Machine Learning Research vol, 65:1–34, 2017.

Andrea Locatelli, Alexandra Carpentier, and Samory Kpotufe. An adaptive strategy for active learning with smooth decision boundary. In Algorithmic Learning Theory, pages 547–571, 2018.

G´abor Lugosi. Pattern classification and learning theory. In Principles of nonparametric learning, pages 1–56. Springer, 2002.

Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6):1808–1829, 1999.

Pascal Massart and ´Elodie N´ed´elec. Risk bounds for statistical learning. The Annals of Statistics, 34(5):2326–2366, 2006.

Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740, 2009.

Stanislav Minsker. Plug-in approach to active learning. Journal of Machine Learning Research, 13(Jan):67–90, 2012.

Wolfgang Mulzer. Five proofs of Chernoff’s bound with applications. arXiv preprint arXiv:1801.03365, 2018.

Charles Chapman Pugh. Real mathematical analysis. Springer, 2002.

Henry WJ Reeve and Gavin Brown. Minimax rates for cost-sensitive learn- ing on manifolds with approximate nearest neighbours. In International Conference on Algorithmic Learning Theory, pages 11–56, 2017.

Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.

Mathukumalli Vidyasagar. Learning and generalisation: with applications to neural networks. Springer Science & Business Media, 2013.

A Detailed proof of Theorem 3

This Appendix is organized as follows: in Section A.1, we introduce some additional no-

tations. In Section A.2 we adaptively determine the number of label requests needed to

accurately predict the label of an informative point that is relatively far from the bound-

ary decision. In Section A.4, we provide some lemmas that give a sufficient condition for

a point to be informative. In Section A.5, we give theorems that allow us to classify each

instance relatively far from the decision boundary. Finally in Section A.6, we provide the

label complexity and establish Theorem 3.

A.1 Notations

Some notations that will be used throughout the proofs are listed here for convenience.

As defined in Section 2.3, let

the open and closed balls with respect to the Euclidean metric

tively, centered at with radius r > 0. Let supp(

0} the support of the marginal distribution

For ), let us define

Let us recall for , we denote by -th nearest neighbor in

the corresponding label.

For an integer

A.2 Adaptive label requests on informative points

Lemma 1 (Chernoff bounds, (Mulzer, 2018))

Suppose are independent random variables taking value in {0, 1}. Let X denote

their sum and its expected value. Then,

Lemma 2 (Logarithmic relationship, (Vidyasagar, 2013))

Lemma 3 (Chaudhuri and Dasgupta, 2014)

For , let us define

all

Theorem 4

Let

parameters used in (H2) and (H3).

For , let us introduce

, such that on

then the nearest neighbors of (in the pool K) belong to the ball

Additionally, the condition

is sufficient to have (29).

Proof

Fix , let us denote nearest neighbor of x in the pool.

we have,

Then, by using Lemma 1 and Lemma 3, and if satisfies (29), we have:

Fix , there exists an event , such that

on

we have . By setting

1 , for all 1

Now, let us proof that the condition (30) is sufficient to guarantee (29).

The relation (29) implies

We can see by a bit of calculus, that

where

Now, we are going to apply the Lemma 2. If we set in Lemma 2

we can easily see that 4 and then

Then, the relation

is sufficient to guarantee (32).

Let us note that the guarantee obtained in the preceding theorem corresponds to that

obtained in passive setting (w = n).

A.3 Motivation for choosing for

Lemma 4 (Hoeffding’s inequality,(Hoeffding, 1963))

– Second version: Let be independent random variables such that We define the empirical mean of these variables by

Lemma 5 (Kaufmann et al., 2016)

Let

tributed, such that, for all . For every positive integer t, let

. Then, for all

Lemma 6

Let . Then we have:

Proof

Define )), and let )). We have:

It can be shown numerically that

Also, we have: (notice that

Then it is easy to see that . This establishes the lemma.

Theorem 5

Let . Let us assume that

where

Then, there exists an event , such that

1. For

Where is the number of requests made in

Proof

1. Let us begin with the proof of the first part of Theorem 5. Here, we follow the proof of Theorem 8 in (Kaufmann et al., 2016), with few additional modifications.

)) = 0, and the random variablesare independent. Then by Lemma 4, given ) takes values in [have 0. Furthermore, set , and by Lemma 5, with 2, we have: P

Then, we have, given , there exists an event 1 , and simultaneously for all 1, we have:

(39) On the other hand, the right-hand side is smaller than:

We can apply the Lemma 6 in (42) by taking: 20 and then, a sufficient condition to have (42) is:

As , we can easily see that ˜). By taking the minimum value ¯) that satisfies (44), we can see that when the budget allows us, the subroutine labels, and we have:

By setting 16, and we can deduce (34). We have on

Thus we can easily deduce (35). By setting , the item 1 and item 2 hold simultaneously.

A.4 Sufficient condition to be an informative point

As noticed in Section 4.3, a sufficient condition for a point ) to be considered

as not informative is:

for some previous informative point

before attaining (Algorithm(1))). Because is unknown, we provide a com-

putational scheme sufficient to obtain (49).

Firstly we follow the general procedure used in (Kontorovich et al., 2016) to estimate adap-

tively the expectation of a Bernoulli random variable. And secondly, we apply it to the

Bernoulli variable

Lemma 7 (Kontorovich et al., 2016)

Bernoulli random variables with expectation be the output of

exists an event , such that

1. If , otherwise, we have

2. The number of random draws in the BerEst subroutine (Algorithm 4) is at most

where

Lemma 8

Let . Let us assume that w satisfies (13).

There exists an event , such that , we have, on

If there exists , such that is an informative point, and

(the current active set just before attaining

satisfies:

where

and

then

Otherwise, if (50) does not holds, i.e:

then min(

Proof

By following the scheme of subroutine Estprob, this Lemma is a direct application of Lemma

7 by taking for all

And then, if we set 16, and on the event

can easily deduce (51) and (52) in each cases.

On the other hand, for all , the number of draws in

(respectively )) is always lower than w. In-

deed, by Lemma 7, the number of draws is at most:

Then we have:

In equation (53), is defined by (4), and represents the number of label requests

used in the subroutine ConfidentLabel(Algorithm (5)) at the stage

A.5 Label the instance space

Let I the set of indexes of informative points used in KALLS (Algorithm 1). Let us consider

its last update in KALLS (Algorithm 1) and also denoted it by I.

Then, set the index of the last informative point. Let be the active set

obtained in KALLS (Algorithm 1) and denote by the output . There exists an

event

2. If w satisfies (12) and (13) and the following condition holds

then, for all , there exists that:

Proof This proof is based on results from (Hanneke) with few additional modifications. 1. Let us begin by proving the first part of Theorem 6. For ), let us introduce

By Lemma 3, we have . Then each ¯to )) with probability at least ˜. If we denote the probability over the data, we have:

Then, there exists an event , such that 8 and (55) holds on then, we can easily conclude the first part.

2. For the second part of Theorem 6, let ). By (55), on there exists such that:

As , then there exists passes through the subroutine Reliable. We have two cases: a) . Then there exists , such that is an informative point, and

that contradicts (62), then we have . Therefore, by (63), (64), we have:

b) . In this case, and then we always obtains the equation (69), which becomes

On , by Theorem 5, the subroutine ) uses at most ˜request labels, and returns the correct label (with respect to the Bayes classifier) of Let us proof that ). Let us assume without loss of generality that 0. We will show that 0. We have:

Then As , by using Theorem 5 (the second part), we can easily see that (is the inferred label of provided by the subroutine ConfidentLabel in KALLS(Algorithm (1))). Let the nearest neighbor of

Then, and by Theorem 5, the subroutine ConfidentLabel

A.6 Label complexity

Lemma 9

Let us assume that . Then, there exists an event such that . The condition (11) is sufficient to guarantee (56).

Before beginning the proof, let us define a notion that will be used through the proof.

Definition 5

Let a set 1]. We say that the set

F is a p-probability-packing set of F if:

where is defined by (25), and

This notion of p-probability-packing comes from the Definition 1.4 in (Edgar, 2000). It will

be used on a particular set of the form

0 ). This allows us to upper bound the number of informative points where we have

a very high confidence for inferring their labels.

Proof

Let us consider the last update of I, the set of indexes of informative points used in

KALLS(Algorithm 1).

Set , the index of the last informative point. We consider two cases:

1. : we can easily see that (56) is satisfied, and we have trivially that the condition (11) is sufficient to guarantee (56). 2. : then the total number of label requests up to

) implicitly assumes that the process of label request do not takes into account the constraint related to the budget n (very large budget with respect to )) such that ) . Then we have:

On the other hand, we want to guarantee the condition (56). For this, necessary for all s , such that , at the end of the subroutine the budget n is not yet reached and then we can replace the relation (77) by

Then, necessarily, (56) holds when (78) holds. Also, for , by theorem5, if we assume that , we have that ˜), and the subroutine terminates when the cut-off condition (34) is satisfied. The right hand side of (78) is equal to:

Let any two informative points that belong to . Let us assume that As and by Theorem 5, the number of label requests ¯) satisfies:

where are respectively defined by (26) and (4). Then

Additionally, as are both informative points, by Lemma 8, we necessary have on event (see Lemma 8), that

(89) Let us introduction the quantity ¯) defined by (26). We have, by Theorem 5, on the event (see Theorem 5),

(93) As the same way, we also obtain (93) if Then, if we set

Therefore, the set of informative points that belong to -probability-packing set.

(b) As second step, let us determine an upper bound of the cardinal of any -probability-packing set of -probability-packing set of For all , we obviously have:

On the other hand, if 2) for some , by the assumption (H3), equation (25), and the fact that

Now, it remains to upper bound the second term in (79). Denote it by 1, (equation(28)), there exists an event have:

Because ) (according to the subroutine and where ˜) is defined in (5). Consequently, we have:

As 1, the term (128)in (103) is greater than 1. Thus, (103) becomes:

Thus, if the label budget n satisfies n

We have that n satisfies (78), and (56) is necessary satisfied.

Proof of Theorem 3

Finally, we are able to prove Theorem 3.

Previously, we have designed five events , such that if the event A :=

, and if the label budget (105) (where ˜O

assumes the existence of polylogarithmic factor in ), then (56) is necessary satisfied,

therefore , by Theorem 6, if w satisfies (12) and (13), and the event A holds, the classifier

provided by the algorithm KALLS agrees with the Bayes classifier on

Consequently, we have:

Thus with probability at least 1 , (14) holds.