Discrepancy-Based Active Learning for Domain Adaptation
Authors: Antoine de Mathelin
François Deheeger
Mathilde MOUGEOT
Nicolas Vayatis
Venue: ICLR 2022 Poster (2022)
Keywords: active learning
domain adaptation
discrepancy
kmedoids
single batch
covariate shift

Abstract: The goal of the paper is to design active learning strategies which lead to domain adaptation under an assumption of Lipschitz functions. Building on previous work by Mansour et al. (2009) we adapt the concept of discrepancy distance between source and target distributions to restrict the maximization over the hypothesis class to a localized class of functions which are performing accurate labeling on the source domain. We derive generalization error bounds for such active learning strategies in terms of Rademacher average and localized discrepancy for general loss functions which satisfy a regularity condition. A practical K-medoids algorithm that can address the case of large data set is inferred from the theoretical bounds. Our numerical experiments show that the proposed algorithm is competitive against other state-of-the-art active learning techniques in the context of domain adaptation, in particular on large data sets of around one hundred thousand images.

Published as a conference paper at ICLR 2022
DISCREPANCY-BASED ACTIVE LEARNING FOR Do- MAIN ADAPTATION
Antoine de Mathelin 1.2, François Deheeger', Mathilde Mougeot Michelin, "Centre Borelli, Université Paris-Saclay, CNRS, ENS Paris-Saclay, *ENSIIE
Niicolas Nicolas Vayatis²
ABSTRACT
The goal of the paper is to design active learning strategies which lead to domain adaptation under an assumption of Lipschitz functions. Building on previous work by Mansour et al. (2009) we adapt the concept of discrepancy distance between source and target distributions to restrict the maximization over the hypothesis class to a localized class of functions which are performing accurate labeling on the source domain. We derive generalization error bounds for such active learning strategies in terms of Rademacher average and localized discrepancy for general loss functions which satisfy a regularity condition. A practical K- medoids algorithm that can address the case of large data set is inferred from the theoretical bounds. Our numerical experiments show that the proposed algorithm is competitive against other state-of-the-an active learning techniques in the context domain adaptation, in particular on large data sets of around one hundred thousand images.
INTRODUCTION
Machine learning models trained on labeled data set from source domain may fail to generalize on new larger domains of interest (Saenko et al. (010)) This issue, which can be caused by domain shift, can be handled when target labels are available through unsupervised domain adaptation methods (Ganin et al. 2016). Using a small sample of labeled target data can, besides, greatly improve the model performances (Motian et al.) (017). Acquiring such new labels is often expensive (Seules) 2010) and one seeks to query as few labels as possible. This explains why strategies of optimal labels acquisition, referred active learning (Cohn al., 1994) seem very promising for domain adaptation (Su et al. 2020).
Active learning is challenging task and broad literature exists. On the one hand, some active learning methods introduce heuristic approaches which provide the benefit of using practical algorithm
based on simple criteria. For instance, the spatial coverage of the target domain (Hu et al. (0010)
Bodó et al. 2011) or the minimization of target uncertainties (RayChaudhuri & Hamey] 1995| 55,..G Gal
al. 2017 are considered, as well as combination of these heuristies (Wei al. 2015 Kaushal et al.
2019). ). However finding the proper heuristics is not straightforward and previous methods do not
link their query strategy with the target risk (Viering et al. 2019). On the other hand, active learning methods based distribution matching aim at minimizing a distribution distance between the labeled set and the unlabeled one (Balcan et al.) 2009) Wang & Ye 2013 Viering et al., 2019). These methods provide theoretical guarantees on the target risk through generalization bounds. However the computation of the distances is either not scalable to large-scale data sets (Balcan et al.) 2009
Wang & Ye, 2015 Viering et al. 2019) based adversarial training (Su et al.) 2020 Shui et al. 2020) which involves complex hyper-parameter calibration (Kurach et al. 2019).
In this work, we propose to address the issue of active learning for general loss functions under domain shift through a distribution matching approach based on discrepancy minimization (Mansour et al. 2009). In Section [ we derive theoretical results by adopting localized discrepancy distance (Zhang et al. 2020) between the labeled and unlabeled empirical distributions. This localized discrepancy is defined as the plain discrepancy considered on hypothesis space restricted to hypotheses close to the labeling function on the labeled data set. This distance has the benefit to focus only on relevant
*Correspondence ant.oi www.mmaeeedeaaaaeeeeee de-mathel n-de- ---deppppignaaiicccmmmmmm gny chel com

---

Published as a conference paper at ICLR 2022
candidates for approximating the labeling function and thus provides tighter bound of the target risk under some given assumptions (Zhang et al. 2020). Based on this distance, we provide a generalization bound of the target risk involving pairwise distances between sample points (Theorem D. Inspired by this generalization error bound, we propose in Section [ an accelerated K-medoids query algorithm which scales to large data set. In Section + we present the related works and analytically show that our proposed approach displays tighter theoretical control of the target risk than the one provided by recent active learning methods. We finally present in Section 5 the benefit of the proposed approach on several empirical regression and classification active learning problems in the context of domain adaptation.
DISCREPANCY BASED ACTIVE LEARNING
Setup and theory develop in this section mainly focus regression tasks. Section 4.3 presents how the algorithm derived from the theoretical results can be extended to classification tasks.
2.1 SETUP AND DEFINITIONS
Given two subsets X C IRP and y C R2 and : X' x X' - RR+ distance on X. we denote the source data set S = {I1, .... Immi } E Xm and the target data set T = { ..., Jn E Xm, We consider the domain shift setting where the respective data sets S and T are drawn according to two different distributions Q and P on X. We consider a loss function L y x x - R, and a hypothesis space H of k-Lipschitz functions from X' to V. We denote by (n h¹) Eg-n(L(h(ar) J (x)) the average loss (or risk) over any distribution D on X' between two hypotheses h h E H. We also define the expected Rademacher complexity of H for the distribution Pas:
sup Σ ooMless
RR, (H)
E
E
(a:)~
KEH i=1
with or drawn according to U the uniform distribution on {-1,
We consider labeling function for each distribution: SQ xx' + X to be possible, the two labeling functions are supposed to be close (Mansour et al. 2009). We finally consider the single-shot batch active learning framework (Viering et al. 2019) where all queried data picked in one single batch of fixed budget of K >> 0 queries. In this framework, algorithm takes as inputs the source data set S along with its corresponding recorded labels as well as the target data set T. The algorithm then returns batch of K queried target data denoted Txx T. The corresponding labels for TK are then recorded through an oracle and used along with the source labeled data to fit an hypothesis h H. We denote by LK S U Tk the labeled data set. The goal is to select the K target data to label in order to minimize the target risk of h Lp(h,
and fp X + y. For adaptation
active learning
2.2 LOCALIZED DISCREPANCY
To formulate the problem of active learning under domain shift as a distribution matching problem, one needs to consider a measure of divergence between distributions. Recent interest focuses on the discrepancy (Mansour al., 2009) which proves to be useful for domain adaptation (Cortes & Mohri 2014 Zhang et al. 2019) and is recently used on the active learning setting (Viering et al. 2019). However this metric, defined as a maximal difference between domain losses over the whole hypothesis space, is relatively conservative as it includes hypotheses that the learner might not ever consider as candidates for the labeling function (Cortes et al. 2019c] Zhang et al.) 2020). Based on this consideration, we introduce a localized discrepancy (Zhang al. 2020h to restrict the measure of divergence between domains on a set of relevant candidate hypotheses for approximating the labeling function:
Definition 1. Localized Discrepancy, Let K > 0 be the number of queries and e 2 O. Let TK be a queried batch of size K, the empirical distributions of Lx = SUUTK and T are respectively denoted k and P. Let H be hypothesis space and L loss function. The localized discrepancy is defined as:
disc (QK.P)
max | (h,h') (h,
(1)
A.E'H
with H.K [h E H; (Q(x)) Vx Lx)
2

---

Published as a conference paper at ICLR 2022
The localized space H. includes hypotheses "consistent" with fo on the labeled data, i... hypotheses fitting the labeled data with enror below e. The parameter drives the size of H. Obviously, needs to be high enough to ensure that H. K is not an empty subset. Under appropriate assumptions on a preliminary result is an empirical target risk bound for the localized discrepancy:
Proposition 1. Let K O be the number of queries and H a hypothesis space. Let P and Qx be the empirical distributions of the respective sets T and LK = = U Tk of respective size nt and m + K. We assume that L is a symmetric, y-Lipschitz and bounded loss function verifying the triangular inequality. We denote by M the bound of L. Let TH be the ideal maximal error on S U SUT:
TH
min max (L(h(()) + ((h(x),f(xx))
(2)
REH #ESUT
Then, for any 2 AH, any hypothesis h E H and any 8 > 0, the following generalization bound holds with at least probability 1-8:
Lr(h,fr) S fox (h. SQ) + disc (Qx, P) + TH + RH) + M (1
(1og(() 2n
log({))
(3)
This bound share a similar form than the one derived in Cortes et al. (2019c) for the discrepancy. The ideal maximal error THи characterizes the difficulty of the adaptation problem well as the ability to learn the labeling functions with the considered hypothesis set H. If íp and SQ significantly differ on S U U, T)и will be high and the proposed bound will lack of informativeness. We then follow the common domain adaptation assumption that the difference between the two functions is small (Mansour et al.
2009 Zhang et al. 2020).
2.3
MAIN RESULTS: GENERALIZATION BOUNDS FOR ACTIVE LEARNING
Considering the previous bound (Proposition it appears that natural way of choosing the K queries an active learning perspective is to pick the target data minimizing the localized discrepancy. Unfortunately this is a difficult problem for an arbitrary functional space H, since it leads to compute a maximum over the set space H.K. Our main idea is then to further bound the localized discrepancy with computable criterion:
Theorem Let K > 0 be the number of queries, H a hypothesis space of k- L-Linschitzfuunctoons functions and Z THE Let LK = =UUT be the labeled set and T the target drawn according P. We assume that is a symmetric, j-Lipschitz and bounded loss function verifying the triangular inequality. We define M such that L(y. v/) S M for any y, y E Y. For any hypothesis h H and any 5 > 0, the following generalization bound holds with at least probability 1-8:
2kμ
M log(?)
Lp(h, S Can (h, f2)
+ Σ 2 NH + 2pDR (H) +
(4)
2n
FEE
With d(z', _x) 2x d(a', xx) and d(z', x) the distance from x to x'.
Visual insights to understand Theorem are presented in Figure [ the main idea is to approximate the maximal hypotheses h, h E H.K returning the localized discrepancy by the k-Lipschitz envelope of the labeling function fq. consistent with fQ on the labeled points, i.c. at most e close to fo on these points. Indeed, for any target point x' T, the gap between h, h' on x' I(hh(a')) h(x')) is upper bounded by twice the distance from x' to its closest labeled point times the Lipschitz constants of L, and It' plus the error on the labeled point: L(k(xx'), h(x))) S d(x' d(z',Lk) + 2e.
The generalization bound of Theorem | highlights the trade-off that exists between the Lipschitz constant i: of the hypothesis space H and the parameters 7/ and c. To reduce the term 2 + fJ in order to obtain tighter controls over the target risk, one needs to consider more complex set of hypothesis and thus to increase the Lipschitz constant k. Then, to benefit from the theoretical guarantees of this bound, careful choice of hypothesis set have to be made (cf Section 4.3)
The important benefit the derived bound is to bring out the bounding criterion Egen M(',.E which is independent of the hypothesis complexity (characterized by k) and the loss function, it only involves pairwise distances between sample points. As this criterion is computable and depends on the queried batch Tk, we can then propose an active learning strategy.
3

---

Published as a conference paper at ICLR 2022
(A) Before Query
(B) After Query
Source oct Target set
Saurce set
h
Target set Bost Query
h
P
24
h'
h
Eeer M(x') - M('') 2.79
EEET Max) - [aa')) = 1.47
X
X
Figure Visual insights of Theorem Any potential candidate for fP in H.K returns values between h and h' : two hypotheses close to fo the labeled points and with slopes of factor everywhere. Thus, an approximation of the localized discrepancy given by the mean of gaps between h and h' (mean length of orange arrows) which be approximated by the distance the labeled set in X' times k. The best target point to label is chosen in order to minimize this sum.
DISCREPANCY-BASE ALGORITHM
Theorem I
directly implies that selecting the K queries minimizing Ener (l', leads to minimize an upper bound of the target risk. We can thus propose an algorithm dedicated to active learning which provides theoretical guarantees the target risk.
Seeking the K queries minimizing Ex'ET d(z', Lxx) corresponds to solve K-medoids problem (Kaufmann & Rousseeuw 1987). Notice however that it does not consist of K-medoids performed directly on the target domain as the source data are already labeled and considered as medoids. The presented algorithm only differs the initialization process, where the distance between each target and its nearest source neighbour needs to be computed.
Several algorithms exist solve approximate the K-medoids (Kaufman Rousseeuw 2009). Ng & Han 2002), (Park & Jun 2009). Here we use the greedy version of the algorithm. It can be shown that the gain the greedy algorithm (the amount of decrease of the criterion by selecting K points) is at least a (1 - 1/ approxxmaatii of the optimal gain (cf Appendix).
is well known that K-medoids algorithms suffer from computational burdens or memory issues on large and moderately large data sets (~ 100K data) (Newling & Fleuret 2017). Indeed they require to compute huge pairwise distance matrix between the source and target samples as well between targets. Precisely, the greedy K-medoids algorithm presents complexity of Opp(nm + n²²) + Kn²) and a memory usage O(nm n²²) with m, n, K the respective size of S, T and Tk. p is the dimension of X.
To handle this issue, we propose an adaptation the K-medoids greedy algorithm with better scalability (Algorithm[]) This algorithm performs the following steps:
1) Computation of the distance to the closest source for each target points via a KD-trees random forest algorithm (Silpa-Anan & Hartley 2008) of complexity O(T + pn) log(m)?) with T the number of trees.
2) Medoids initialization using the greedy algorithm random target batch of B samples with complexity O(KK + B²).
3) An iterative algorithm the model of (Park & Jun 2009 combining assignment of each target point to its closest medoid (O(K) pn)) and medoid update inside each cluster.
4) The medoid update for each cluster is done through original Branch-and and-Bound algorithm (Land & Doig 2010) which estimates the criterion by iteration over which criterion bigger than statistical threshold are left aside. Thus, the number of pairwise
target points for
4

---

Published as a conference paper at ICLR 2022
distances to compute is reduced at each iteration until the maximal iteration number is reached or all target points are left aside. Under some assumptions, we can show that the complexity of the update for all cluster O(n3/2K K-1/2) (the proof is given in the supplementary material).
The overall complexity then ( + pn) log(m)) (m)² + (K+ p) + Km + pm p 1/2) which provides reasonable computational time for moderately large data set (n, 10y and p 10"). Empirical comparison of computational time is also provided the supplementary material.
Algorithm Accelerated K-medoids
1: [d(s', (S)
# Compute distances to source
2: Tk = [ j.l. + Greedy (T, B, K, (d(x', S) (ZeT) # Initialize medoids
min d((', 43) A d(x', 8)} *Assign targets closest cluster C ( Ld'ETId(az TId(''' j=I.K
4: while any medoid x; can be updated do
5: for from 1 K do
6:
x -argmin Σ d(x', ) Branch-and-Bound((C, x'EC, E'EC,
# Update medoid
7: end for
8: For all x' E compute ,ff for all updated medoids and reassign x' the closest C
9:
end while
4 RELATED WORK AND DISCUSSION
4.1 RELATED WORK
Active learning as distribution matching. Active learning methods based on distribution matching aim at reducing the gap between the distributions of the labeled sample and the unlabeled one with minimal query budget. Several metries are used measure the gap between distributions as the Transductive Rademacher Complexity (Gu & Han 2012), the MMD WWang & Yel 2015 Kim
al. [2066] Viering et al.) 2019) the Disagreement Coefficient (Hanneke 2007] Balcan al. 2009)
Beygelzimer et al. 2009; Cortes et al. 2019a b 2020), the H-divergencce (Sinha et al. [019 9 Gissin
& Shalev-Shwarr
2019; Su et al. (0200 or the Wasserstein distance (Shui et al.) 2020). To the best of our knowledge, only paper deals with the discrepancy for active learning (Viering et al. 2019). The authors consider the discrepancy on the space of RKHS hypotheses with PSD kernels and provide an explicit way of computing the discrepancy using eigen- value analysis. However, the corresponding algorithm encounters computational burden and could hardly be applied on large sets.
K-medoids algorithm heuristic measure of representativeness (Lin et al. 2209) Gomes & Krausel (010); Wei et al.] 2013] [yer & Bilmes [2013] Zheng al., 2014). The K-medoids is in general computed
K-medoids for active learning. Many active learning methods
smaller set of
selected targets with the higher uncertainties (Wei et al. 2015 Kaushal et al. 2019). In this present work, we provide theoretical insights for this algorithm by highlighting the link with discrepancy minimization.
Active learning for domain adaptation. Our work is related to the recent advances on active learning for domain adaptation as we also consider the domain shift hypothesis (Rai et al. 2010 Saha et al. DDeg et al. 2018 Su et al., 2020). These works use in general the output of domain classifier to measure the informativeness of target samples. In our work, we consider instead the distance to the source sample to capture informative target data.
Lipschitz consistent functions for active learning. In the context of function optimization, some methods consider the set of Lipschitz or locally Lipschitz functions consistent with the observations (Vakko et al., 2013: Grill et al.) 2015; Malherbe & Vayatis 2017). We use similar functions to approximate the maximal hypotheses returning the localized discrepancy. Notice that the goal of the previous papers differ from ours as they aim at finding the maximum of the labeling function.
4.2 COMPARISON WITH EXISTING CENERALIZATION BOUNDS FOR ACTIVE LEARNING
Some previous works on active learning also propose theoretical bound on the target risk. In this section, will compare them with our derived bound of equation (4) in order relate our
5

---

Published as a conference paper at ICLR 2022
contribution with existing works. As their framework is the pure active learning setting which differs from the setting consider here, we make the comparisons under the simplifying assumptions: f= fr fq. f E H and é O. In this case, our bound is written:
Lp(h, f) (2kp/n)
d(r' + Rn (H) + log((1(1/)) E'ET
Σ
(5)
The paper by Sener & Savarese
2018) proposes the K-centers algorithm for active learning based on
an easily computable criterion offering theoretical guarantees. For regression loss I. and under the previous assumptions, it controls the target risk as follows:
(h f) S 2kp max d(d', LK) E'ET
) + 2nTR (H) + (
(6)
We directly observe that this bound is looser than the one of equation 5 Indeed, in our case the target risk is controlled with the mean of distances between unlabeled points and the labeled set whereas K-centers considers the maximum of these distances. Notice however that both algorithms greedy selection approximation. Thus, in some cases, the queries from K-centers may lead to smaller bound than the ones from K-medoids.
A generalization bound for active learning involving the Wasserstein distance W1 has also been proposed (Shui et al.] (020).. An adaptation of this bound for the proposed scenario with the aforementioned assumptions could be written as follows:
(h, f) s ( P) 2n, + (VM2 log log/))/(//
Where W2(QK. P) = arg min Ez-âu Eor x') with I' = {7 (mx(m+
1: 7 m+K 1).
Thus, in observing that d(xr, 2 d(Ø' [Ix) for any x' T and E Lx we show that presented bound of equation (5) is tighter than the one above.
4.3 DISCUSSION ABOUT THE ASSUMPTIONS AND LIMITATIONS
One crucial point of the present work is the setting of the parameter of the hypothesis set H.K In practice, the parameter is determined by the hypothesis set and the training algorithm that the learner considers. For instance, if the learner uses aver-parameterizee hypotheses overfitted on the labeled data set, the parameter e will be small because for any h, h(x)) = fo(x) on Lx. This could leads to c < лi and the bound would not be valid anymore. This highlights the trade-off between fitting the source data and generalizing to the target domain. As, in practice, the parameter тıи is hard to estimate, choosing larger e (by regularizing the hypotheses) safer, but will lead to larger bounds.
To deal with this difficulty, we use, in our experiments, set of neural networks H regularized through weight clipping. The value the clipping parameter is directly linked to the Lipschitz constant of H. By selecting adequate clipping parameter and network architecture, enough to learn the task on the source domain but sufficiently regularized to avoid over-fitting (and thus avoid < T)H). For this purpose, select the architecture and the clipping parameter through validation on the source labeled data.
ensure that H is complex
Regularity assumptions on the loss function L are essentially verified by norms the Lp which common losses for regression problems. However, they are are not verified by most classification losses. In fact, classification loss the cross-entropy is bounded between 0 and and can not increase linearly with the distance to the closest labeled point. In this context, considering target points far away from sources as informative points is not efficient. In fact, the most interesting points are the ones in the margin between classes (Balcan et al. 2007). Thus, in order to focus the K-medoids selection in the margin, and thus extent the proposed algorithm to classification task, we propose an improved version of our algorithm, the Weighted K K-medoids (K-medoids+W) This algorithm performs the K-medoids algorithm with weighted criterion. To compute the weights, we consider the Best-vs-Second-Ber (BV criterion (Joshi et al. (2009 which is the difference between the probabilities of the best class and the second best class, given by a hypothesis pre-trained on source data set. The Weighted K-medoids optimization can be written follows:
min Tk
bvsb(x')
min d(x,
#ESUTK
a' ET

---

Published as a conference paper at ICLR 2022
5 EXPERIMENTS
We choose to compare the performances of our algorithm to classical active learning methods on regression and classification problems in domain shift context. We consider the single-batch active learning setting (Viering et al.) 2019) where all queries are taken at the same time in one batch. We compare the results obtained on the target domain for different query and training methods. The experiments have been run on a (2.7GHz, 16G RAM) computer. The source code is provided on GitHub We use the open source code of the corresponding authors for BADGE (Ash al., 2019) and the implementations from A de Mathelin et al. 2021 for the domain adaptation methods.
5.1 COMPETITORS
We compare the proposed approach with the following query methods: : Random Sampling: K- means (Hu et al., 2010); K-centers (Sener & Savarese 2018); Diversity (Jain & Grauman (0166);
QBC (RayChaudhur
& Hamey] 1995); BVSB (Joshi al. 2009); AADA (Su et al. (0220) an
hybrid active learning method for domain adaptation using a combination of entropy measure from
a classifier and the outputs of a domain discriminator; BADGE (Ash et al. 2019): an hybrid deep
active learning method optimizing for both uncertainty and diversity. CLUE (Prabhu al. 2020) an active domain adaptation strategy that select instances that are both uncertain and diverse.
We select four different training methods Uniform Weighting: Balanced Weighting : Assign balanced total weight between source and target instances; TrAdaBoost (Pardoe & Stone, (010))
Transfer learning regression method based reverse boosting principle; Adversarial training
unsupervised features transformation on the model of DANN (Ganin et al., 2016))
To make fair comparison between the different query strategies. we use for all experiments, the same set of training hypotheses H. We define H as the set of neural networks composed of two fully connected hidden layers of 100 neurons, with ReLU activations and projection constraints on the layer norms (< 1.). We use the Adam optimizer (Kingma & Ba 2015). The network architecture is defined be complex enough that the network provides a good approximation of the labeling function on the source domain in all experiments. Besides, for each experiment, fine-tuning of the optimization hyper-parane seper-parameters (epochs, batch sizes...) is performed using only source labeled data. We assume that the architecture and the resulting dlper-parameee after adding the queried target data to the training set (see Section 4.3). Finally, for distance- based algorithm, consider the Ln distance computed in the penultimate layer of network pre-trained on sources. We use an ensemble of 10 models in QBC and the greedy version of K-centers.
will still be appropriate
5.2 SUPERCONDUCTIVVIT DATA SET
As there very few public data sets for domain adaptation with regression tasks (Teshima al., 2020). we choose an UCI data set with a reasonable amount of instances and split it in different domains using the setup of (Pardoe Stone, 2010). We choose Superconductivity (Hamidieh) 2018
Dua & Graff 2017) which is composed of features extracted from superconductors chemical formula. tempera temperature.
The task consists in predicting their critical
Experimental setup: The data set is divided in four domains following (Pardoe & Stone 2010) low ()), middle-low (ml), middle-high (mh) and high (h) of around 4000 instances and 166 features. We use learning rate of 0.001, number of epochs of 100, batch size of 1 128 and the mean squared error as loss function. We conduct an experiment for the 12 pairs of domains. We vary K from 5 to 300 and repeated each experiment 8 times with different random seeds. We report the mean absolute error (MAE) on the target unlabeled data for all experiments when K = 20 in Table I We present the MAE evolution for the adaptation from mè to h in Figure 2
Results: We observe on Figure 2 that, for any K >> O, the K-medoids algorithm presents the lowest MAE on the target data for the three different training methods. In particular we observe significant performance gain of K-medoids when using TrAdaBoost which provides the lowest MAE for the majority of fixed budget K compared to other training methods. These observations are confirmed on Table [ where we observe that K-medoids presents the lowest MAE in 11 experiments over 12. We
7

---

Published as a conference paper at ICLR 2022
Table I: MAE the critical temperature for the Superconductivity experiments with Balanced
Weighting and K 20. Standard deviation are given in the supplementary material.
Experiment
1-
1-
1-+h
ml-+1
ml-+mh
ml-=b
mh++1
mh-+ml
mh++h
h-+1
h=+ml
h mh
Random
15.33
15.80
17.45
16.53
11.39
14.70
17.65
12.83
10.36
18.75
14.86
10.54
Kmsans
14.43
13.60
13.98
15.79
10.19
12.73
17.18
12.67
10.02
22.10
14,69
9.76
Koenters
19.21
15.73
16.85
15.75
11.62
13.44
22.17
12.74
10.24
36,50
19.00
10.39
Diversity
19.46
18.21
18.68
16.01
11.94
15.36
23.92
14.31
10.70
37.97
20.89
10.78
Kmnedoids
12.70
13.57
14.11
14.49
10.02
12.52
15.36
12.37
9.79
16.62
14.14
9.32
also observe here that methods based on spatial consideration as K-medoids, K-means and K-centers select more informative target points than the uncertainty based method QBC. This comes from the fact that, in batch mode, QBC is selecting close target points with similar uncertainty level. Finally, K-medoids outperforms K-means because takes into account the distance to source points and then queries less redundant information.
(A) Uniform Weighting
(B) Balanced Weighting
(C) TrAdaBoost
MAt on urieree sagg
11.0
11.0
11.0
10.5
10.5
10.5
10.0
10.0
10.0
8.5
8.5
8.5
8.0
8.0
0
50
250 Nuwber of lbbe target
100
150
200
300
50
100
150
200 250
300
50
100
150
20C
250
300
Number of labeled target
Number of labelee terget Diversity
Krrears
CBC
Kicontrrs
Figure 2: Results for the Superconductivvty data set (mh h experiment). Evolution of the MAE function of the budget K for three different training methods and six query methods.
in
5.3 OFFICE DATA SET
The office data set (Saenko al. 2010) consists in pictures of office items coming from different domains: amazon or webcam. The task is a multiclaassifiatioo problem with 31 classes (chairs, printers, ...). The goal use data from the amazon domain where labels are easily available learn good model on the webcam domain where a few labels are chosen using active learning methods.
Experimental setup: We consider the adaptation from "amazon" with 2817 labeled images to "webcam" " with 795 unlabeled images. We use, as input features, the outputs of the ResNet-50 network (He et al., (016)) pretrained on ImageNet. We vary K from 5 300, repeating each experiment times. The learning rate is 0.001, the number of epochs 60 and the batch size 128.
Results: Figure A presents the results obtained. We observe that the K-medoids+ algorithm provides the best performances for almost any K and in particular for small values of K. We then present the visualization the two first components observe that the K-medoids+ algorithm queries points at the center of the target distribution but at a reasonable distance from the sources. The Random and K-means algorithms select a representative subset of the target distribution but without taking into account the sources and therefore query redundant information. K-centers selects data far from the source domain but which less representative of the the target distribution.
the PCA transform on Figure 4 We
5.4 DIGITS DATA SET
We consider the experiment proposed in (Ganin et al. 2016) where synthetic digits data set: SYNTH used to learn classification task for a data set of real digits pictures: SVHN (Street- View House Number) (Ntzer al. 2011). Both data sets composed of around 65k images of size 28 x 28.
8

---

Published as a conference paper at ICLR 2022
(A) Office Belanced Weighting
(B) Digits Balanzed Weighting
(C) Digits Adversarial Training
2.00
0.95
Aenraay or (eleeee buge
0.50
0.80
0.80
0.35
0.50
8.75
0.70
0.65
0.70
0.76
200
300
100)
310
4.0
100
2.0
500
400)
500
Number labeld cara
Namber
loded torget
Namber of lidddd target
Kimedoda--
Fandom
K moans
BVS8
contar
Diweriy
BADGE
CLUE
MGA
Figure 3: Office and digits results. Evolution of the accuracy in function of the budget K.
(-medoiis:
Random
conters
Figure 4: Visualization of the PCA first components of the Office data set input space. Queries are reported with black points for each query method with = 20.
Experimental setup: To handle the large number of data, we use the accelerated K-medoids algorithm (Algorithm) 1 with = 50 trees and a initial batch size of = 5000. We use the KD-trees random forest nearest neighbour algorithm in Diversity and K-centers to approximate the distance of each target data to the source data set. We consider two kinds of input features: the ones obtained with the convulational part of a Lenet (LeCun et al.) 1998) trained with the source labeled data and the ones coming from the same network but trained with adversarial training following the model of DANN (Ganin et al. 2016). In both cases, the network is pre-trained on 30 epochs with batch size of 128 and a learning rate of 0.001, for the adversarial training the trade-off parameter À is set to 0.1 following the setup of (Su et al. 2020 After the query process, Balance Weighting training is performed with the source and target labeled data using the same optimization saper-parameters than before. Experiments are conducted 8 times for between 10 and 500.
Results:
Figure B and C correspond to the evolution of accuracy with respect to K for the experiments conducted with the features obtained respectively without and with adversarial training. We observe that, for any K >> 0, K-medoids+VV W provides improved results over other query strategies in both cases. This highlights the ability of the method to select informative target points variety of scenarios.
CONCLUSION AND FUTURE WORK
This work introduces a novel active learning approach based on localized discrepancy between the labeled and unlabeled distributions. We provide both theoretical guarantees of this approach and an active learning algorithm scaling to large data sets. Several experiments show very competitive results of the proposed approach. Future work will focus on considering a more appropriate distance on the input space, giving more importance relevant features with respect to the task.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
To help the reproducibility of the results presented in this work, the source code of the experiments is available at hhttps://ggtttii com onto nedema the h 1
Furthermore, the presented methods and the majority of the competitors have been implemented with "pythonic" objects which implement a fit and predict methods. Thus, the code can easily be used on other data sets than the ones considered in this work.
Finally, notehooks are provided in the repository enable rapid access the methods and the possibility to try for different syper-parameters
ACKNOWLEDGMENTS
Part of this research was funded by the Manufacture Française des Pneumatiques Michelin and the Industrial Data Analytics and Machine Learning chair of Centre Borelli from ENS Paris Saclay,
REFERENCES
Jordan T' Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In International Conference on Learning Representations, 2019.
Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International
Conference on Computational Learning Theory, pp. 35-50. Springer, 2007.
Maria-Florina Balean, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-88) 89, 2009.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance Weighted Active Learning, pp. 49-56. Association for Computing Machinery, 2009.
Zalán Bodó, Zsolt Minier, and Lehel Csató. Active learning with clustering. In Active Learning and Experimental Design Workshop in Conjunction with AISTATS 2010, pp. 127-139. JMLR Workshop and Conference Proceedings, 2011.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):201-221, 1994.
Corinna Cortes and Mehryar Mohri. Domain adaptation and sample bias correction theory and algorithm for regression. Theoretical Computer Science, 519, 2014.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Region- based active learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2801-2809, 2019a.
Corinna Cortes, Giulia DeSalvo, Mehryar Mohri, Ningshan Zhang, and Claudio Gentile. Active learning with disagreement graphs. In International Conference on Machine Learning, pp. 1379- 1387, 2019b.
Corinna Cortes, Mehryar Mohri, and Andrés Muñoz Medina. Adaptation based generalized discrepancy. J. Mach. Learn. Res., 20(1):1-30, January 2019c. ISSN 1532-4435.
Corinna Cortes, Giulia Desalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Adaptive region-based active learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2144-2153, PMLR, 13-18 Jul 2020.
Antoine de Mathelin, François Deheeger, Guillaume Richard, Mathilde Mougeot, and Nicolas Vayatis. Adapt: Awesome domain adaptation python toolbox. arXiv preprint arXiv:2107.0m 03049,, 2021.
Cheng Deng, Xianglong Liu, Chao Li, and Dacheng Tao. Active hyperspectral image classification. Patlern Recognition, 77:306-315, 2018.
domain adaptation for
10

---

Published as a conference paper at ICLR 2022
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive
ics. wui.eeeuu edu/mll
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep Bayesian active learning with image data. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1183-1192, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. Mach. Learn. Res., 17(1):2096-200 2030, January 2016. ISSN 1532-4435.
Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning. arXiv preprint arXiv: 06347, 2019.
Ryan Gomes and Andreas Krause. Budgeted nonparametric learning from data streams. In Pro- ceedings of the 27th International Conference on International Conference on Machine Learning. ICML' 10, pp. 391-398, Madison, WI, USA, 2010. Omnipress.
Bean-Bastien Grill, Michal Valko, and Rémi Munos. Black-box optimization of noisy functions with unknown smoothness. In Neural Information Processing Systems, 2015.
Q. Gu and J. Han. Towards active learning on graphs: An error bound minimization approach. In 2012 IEEE 12th International Conference on Data Mining. pp. 882-887, 2012.
Kam Hamidieh. A data-driven statistical model for predicting the critical temperature of a supercon- ductor. Computational Materials Science, 154:346-354, 2018. URL htttttt///archiveee ics
uei www.eeuwmmmmeeeee http:///daaatttsssssa htt.aa/ssstttetteeee.ooooottttta
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference on Machine learning, pp. 353-360, 2007.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffdiing pp. 409-426 Springer, 1994.
Rong Hu, Brian Mac Namee, and Sarah Jane Delany. Off to good start: Using clustering to select the initial training in active learning. FLAIRS Conference, 2010.
Rishabh K Iyer and Jeff Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances in Neural Information Processing Systems, pp. 2436-2444 2013.
S. D. Jain and K. Grauman. Active image segmentation propagation. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2864-2873, 2016.
A. J. Joshi, Porikli, and N. Papanikolopoulos. Multi-class active learning for image classification. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2372-23799 2009.
Leonard Kaufman and Peter J Rousseeuw. Finding groups in data: introduction to cluster analysis, volume 344. John Wiley & Sons, 2009.
Leonard Kaufmann and Peter Roussceuw: Clustering by means of medoids. Data Analysis based on the LI Ll-Norm and Related Methods, pp. 405-416, 01 1987.
V. Kaushal, R. Iyer, S. Kothawade, R. Mahadev, K. Doctor, and G. Ramakrishnan. Learning from less data: A unified data subset selection and active learning framework for computer vision. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 1289-1299, 2019.
Been Kim, Rajiv Khanna, and Oluwasanmi Koyejo. Examples are not enough, learn to criticize! criticism for interpretability. Advances neural information processing systems, 29, 2016.

---

Published as a conference paper at ICLR 2022
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015.
Karol Kurach, Mario Lučié, Xiaohua Zhai, Marcin Michalski, and Sylvain Gelly, A large-scale study on regularization and normalization in gans. In International Conference on Machine Learning. pp. 3581-3590. PMLR, 2019.
Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008, pp. 105-132. Springer, 2010.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):227--2324, 1998.
Hui Lin, Jeff Bilmes, and Shasha Xie. Graph- based submodular selection for extractive summarization.
In 2009 IEEE Workshop on Automatic Speech Recognition & Understanding, pp. 381-386. IEEE, 2009.
Cédric Malherbe and Nicolas Vayatis. Global optimization of lipschitz functions. In International Conference on Machine Learning, pp. 2314-2323. PMLR, 2017.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In COLT, 2009.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. arXiv preprini arXiv:0907.3740, 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Saeid Motian, Marco Piccirilli, Donald A Adjeroh, and Gianfranco Doretto. Unified deep supervised domain adaptation and generalization. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5715-5725, 2017.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions Mathematical programming, 14(1):265-29) 294, 1978.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011.
James Newling and François Fleuret. A sub-quadratic exact medoid algorithm. In Artificial Intelli- gence and Statistics, pp. 185-193. PMLR, 2017.
Raymond T. Ng and Jiawei Han. Clarans: method for clustering objects for spatial data mining. IEEE transactions knowledge and data engineering. 14(5):1003-1011 2002.
David Pardoe and Peter Stone. Boosting for regression transfer. In Proceedings of the 27th Interna- tional Conference on Machine Learning (ICML), June 2010.
Hae-Sang Park and Chi-Hyuck Jun. A simple and fast algorithm for k-medoids clustering, Expert systems with applications, 36(2):3336-3344 2009.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Viraj Prabhu, Arjun Chandrasekaran, Kate Saenko, and Judy Hoffman. Active domain adaptation via clustering eebertainty-weighhee embeddings. arXiv preprint arXiv:2010.08666, 2020.
Piyush Rai, Avishek Saha, Hal Daumé III, and Suresh Venkatasubramanian. Domain adaptation meets active learning. In Proceedings of the NAACL HLT 2010 Workshop on Active Learning for Natural Language Processing, pp. 27-32, 2010.
12

---

Published as a conference paper at ICLR 2022
T. RayChaudhuri and L. G. C. Hamey. Minimisation of data collection by active learning. In Proceedings of ICNN'95 International Conference on Neural Networks, volume 3, pp. 1338-1341 vol.3, 1995.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In Proceedings of the 11th European Conference on Computer Vision: Part IV, ECCV' pp. 213-226, Berlin, Heidelberg, 2010. Springer-Verlag.
Avishek Saha, Piyush Rai, Hal Daumé, Suresh Venkatasubramanian, and Scott L DuVall. Active supervised domain adaptation. In Joint European Conference on Machine Learning and Knowledge Discovery Databases, pp. 97-112. Springer, 2011.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations, 2018.
Burr Settles. Active learning literature survey. University of Wisconsin, Madison, 52, 07 2010.
Changjian Shui, Fan Zhou, Christian Gagné, and Boyu Wang. Deep active learning: Unified and principled method for query and training. In International Conference on Artificial Intelligence and Statistics, pp. 1308- 1318. PMLR, 2020.
Chanop Silpa-Anan and Richard Hartley. Optimised kd-trees for fast image descriptor matching. In 2008 IEEE Conference Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2008
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1972-5981, 2019.
J. Su, Y. Tsai, K. Sohn, B. Liu, S. Maji, and M. Chandraker. Active adversarial domain adaptation. In 2020 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 728-737, 2020.
Takeshi Teshima, Issei Sato, and Masashi Sugiyama. Few-shot domain adaptation by causal mecha- nism transfer. In International Conference on Machine Learning. pp. 9458-9469. PMLR, 2020.
Michal Valko, Alexandra Carpentier, and Rémi Munos. Stochastic simultaneous optimistic optimiza- tion. In International Conference on Machine Learning, pp. 19-27. PMLR, 2013.
Tom Viering, Jesse Krijthe, and Marco Loog. Nuclear discrepancy for single-shot batch active learning. Machine Learning, 06 2019.
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Trans. Knowl. Discov. Data, 9(3), February 2015.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Using document summarization techniques for speech data subset selection. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp.
721-726, Atlanta, Georgia, June 2013. Association for Computational Linguisties.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In Francis Bach and David Blei (eds.), International Conference Machine Learning. volume 37 of Proceedings of Machine Learning Research, pp. 1954-1963, Lille, France, 07-09 Jul 2015. PMLR.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 7404-7413, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Yuchen Zhang, Mingsheng Long, Jianmin Wang, and Michael Jordan. On localized discrepancy for domain adaptation. arXiv preprint arXiv:2008. 06242, 2020.
Jingjing Zheng, Zhuolin Jiang, Rama Chellappa, and Jonathon P Phillips. Submodular attribute selection for action recognition in video. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27, pp. 1341- 1- 1349. Curran Associates, Inc., 2014.
13

---

Published as a conference paper at ICLR 2022
Appendix
We recall here the notations and definitions used in the following:
X C IP and y C R are the respective input and output subsets.
d X' x X' R+ is distance on X'
P Pand Q are two distributions on X. {=',.... = "...,,"n) E X is the unlabeled target data set and S Zm,) E xm the labeled source data set drawn respectively from and Q.
TT=
+L: + R+ is loss function.
H is hypothesis set of k-Lipschitz functions from X' to V.
Eez (l>.)[((())......))))))))))))>)) h (x))] is the average loss (or risk) over any distribution D on X' between two hypotheses h, h' H.
(H) = (x/ (o. IIEH ==1
sup 1
Lo,
is the expected Rademacher complex-
ity of H, with U the uniform distribution on {-1,1}.
fq :x - the source labeling function.
x - is the target labeling function.
K> is the number of queries
Tk c T with |Tx| = K is queried batch or subset.
=x= = SUT is the labeled data set.
Q. Qx and p are the respective empirical distributions on X' of S Tk and
H = the (((z)) fo(x)) e E LK} is the localized hypothesis space.
disc (Qk, P) max,,eeHK (h, Cp h()l the localized discrepancy between QK and P.
A PROOF OF PROPOSITION 1
Proposition 1. Let K > O be the number of queries and H a hypothesis space. Let P and Qx be the empirical distributions of the respective sets T and Lx S TK respective size n and m + K. We assume that L. is symmetric, μ-Lipschitz and bounded loss function verifying the triangular inequality. We denote by M the bound L. Let тH be the ideal maximal error on U
TH
min max (L(M(z).f(x))) + ((((x),
(8)
REH RESUT
Then, for any 2 MH, any hypothesis h E H.K. and any 5 > 0, the following generalization bound holds with at least probability 1-8:
(Vieg
Cp(h, S Can (h. fq) + disc (Qx, P) + nH + 2p +
(9)
2n
Proof. Let's consider h H. According to (Mohri et al. 2018) we have for any 8 > 0, with
probability at least 1 8:
log( +
Lp(h, Jp) S Cp(h, + 2n00,, MV
(10)
2n
Besides, we have for any h ho E HKK
14

---

Published as a conference paper at ICLR 2022
Lp(h,Sr) θxx (o) + Lp(h, Sp) @xx (1)
S qx SQ) + p ha) + (p) Qux (h, ho) + fxxx (ho.
0x (h, fQ) max
(Cp(h,h') Lāx (h, h'1 I1 Lp(ho, L (ho, fQ)
(11)
As the inequality is true for any ho E H we have in particular:
Cp fp) S L@x (h, + max
1Cp(h, Lax (h, (1,1')l+ min be
(Ep(ho, fP) + LGx (ho. (ho:
WNEHH
(12)
notice that, for any ho H.K:
Cp fr) + Qux (ha.fQ) S max fQ(x)) + (((())) (13)
#ES.T
From which we deduce that,
min (Ep(ho, I) + f@x ( & THE b HK
(14)
Let's consider h² E H, such that:
h = arg min max (I(M(z).f(z)) + (())) bElf #ESUT
(15)
By assumption have Tu I e, and thus:
[L (0M()).))))))
max zESUT
(16)
This implies that for any x E SUT:
(x), Se
(17)
In particular, ((h) S for any E Lk. which implies that h" is in H.K. We then deduce that:
(18)
Thus conclude that for any h E H.K and any 8 > O. we have with probability at least 5:
(oo((a)
Lr(h,f) 5 Lox SQ) disc (xx, P) + 1/ RPH + M
(19)
2n
15

---

Published as a conference paper at ICLR 2022
B PROOF OF THEOREM
Theorem 1. Let > be the number of queries, H a hypothesis space of k-Liisccitz functions and 2 1H.- Let LK S U TK be the labeled set and T the target set drawn according to P. We assume that L is a symmetric, j--ipschitz and bounded loss function verifying the triangular inequality. We denote by M the bound of L. For any hypothesis h H and any 6 > 0, the following generalization bound holds with at least probability 1-8:
Cp(h, < Qxx (Q) 2kp n #ET
M log(()))
, + + 1/ + 2p
(20)
2n
With d(x', Lx) min d(z',z)
Proof. Let E 2 and 0 - K S n. For all h, h/ H for all x' E T for all LK we have:
((h(z'), <
+
S + S ((h(()) [M) +
s 2kz'(zz,z)) 2
(21)
The two first inequalities come from the triangular inequality, the others from the lipschitzness of h, h' and definition of H.K.
As the above inequality true for any x E Lx. we have particular for any x' TT:
((2))),N(z')) < 2kμ min d(x,x') + 2e
zE.RK
(22)
2kμ _x) + 2
Leading to:
2kp
(x(M(z'),N'(''))
Σ d(x',Lk) 2c
(23)
n
x'ET
We then deduce the following, for all h h E H.K:
disc (QK, P)
1p(hh (ox
K.
< max
max h.
Sp(h,h';
max hNN'MM
f (h,
2kp
(24)
Σ d(x', ( + 2e, 2E
< max
ZTET
< 2kμ
Σ d(z', (.) +
n
E'ET
Finally, according to Proposition 1, we have for all h, h'' H
Cp(h, f) s C2x (2) + 2kp
M log( {
d(d', LK) + + 7H + 2noR, +
(25)
n FET
2n
16

---

Published as a conference paper at ICLR 2022
C APPROXIMATION ERROR BETWEEN PROPOSITION 1 AND THEOREM 1
We present in this section the approximation error of the relaxation between the bounds of Proposition I and Theorem 1.
We will show that, with the assumption of Theorem I and in the case L L1. we have, for any labeled Lk:
2k
Σ
,()'
S 1: k- ki
discH! x (Q K; P)
(26)
#'ET
With ky the Lipschitz constant of the source labeling function fq. We assume that & > k
For this purpose we will look for two hypotheses h, h' E H verifying:
Cp( 2(k: kt)
Σ , Lx)
(27)
n
EEET
Let's define W' = k - ky, and h. x - y such that, for any x E N:
h(x) = fQ(x) + ke min d(z, = fa(x) + k/ d() Lx)
SE
(28)
n'(x) fo(x) - K' min d(x,ā) So(Ø) K/ dd(x,, Lx)
BE
We will now prove that h, h are in H.K: Let's consider æ1, 22 E X, we define:
$1 arg min d(i, x1)
(29)
82 arg min d(i, F22
26.2x
Assuming without restriction that ((x1, > d(I2 .2)), we have:
[Mxx)) 1(x221
< W [d(x,, d(z EK] + hy d((1,
$ (d(x),01) d(z2, 8z2) + k, d(x1, 22)
$ (d(x1, .2) - d(I2, x2)) + k d( d(I1, 22)
(30)
$ W d(x1, x2) + ky d( d(x1, X2)
< d((1)
Using the triangular inequality and the fact that d(x1, .1) d(x1, .22) by definition of ø1.
Using a similar development we can prove the k-Lipschitzness h'. Let's now consider LK. we have
L(h()), = L(So(*) + 2x), =(fg(z).fo(z)) = 0
(31)
In the same way (x), and we have h. H' E H.K.
17

---

Published as a conference paper at ICLR 2022
Furthermore, we have:
Cp(h, = Σ L(h(c'),((z'))
ET
Σ
(32)
N'ET
2(k: kf)
Σ 1(I'
ET
Thus,
2(k kz)
disc H (0x, P) (C)( -0
Σ
dddd' (
(33)
ZET
From which we conclude.
D COMPARISON WITH OTHER ACTIVE LEARNING BOUNDS (CF SECTION 4.2)
In this section assume that f = fp fo and f E H with H set of k-Lipschitz functions.
D.I K-CENTER BOUNDS
Sener and Savarese (Sener & Savarese 2018 propose the following generalization bounds for and h H.K:
fp 8(2' MCX") (v
(Vog((t)
log(()) 2n
(34)
which leads to:
(V
(v
(log(t) 2n
Cp(,, < 8( MCX" + (H) 2M
(35)
With 8 = max [(l'',Lk' C' the class number and X the Lipschitz constant of class-specific regression function. is the Lipsehitz constant of the loss function verifying I (x. h) [xx ()) =
we consider a regression problem, we can drop the term corresponding to the class-spectie function and we have:
(MMPloO(3
Ma
(r( 58x 2p (H) +
OO
(36)
2n
Let's consider h H and xr, x' X, we have for k-Lipschitz f
18

---

Published as a conference paper at ICLR 2022
[(,,[(,)))) (ldd)) (L(((1) (I())) $ (I((N()),(2))
I(h(z))
$ ((( L(((()))
s -
- 2 - =
(37)
The two first inequalities are obtained with triangular inequalities, then we use Lipschitz assumptions on h, f and L.
Thus, we have X = 24ck from which we deduce:
M2 log(()
Cp S 2kμ maxd(a' d('', (Kk (1) +0
(38)
z'ET
2n
D.2 WASSERSTEIN BOUNDS
To adapt the bound from (Shui et al. 2020) Corollary to our setting, we identify the distributions H and Q from Shui et al. (2020) with respectively the distributions P and QK. We then have the following generalization bound:
(v
fp S fax ff. + 2nkW (ŌK, P) 2n +0
(39)
2n
Notice that the term corresponding to the labeling function "decay property" in the bound of Shui al. 2020) is null when considering Lipschitz labeling function (f E H).
Thus for c = and for any E H.K. we have:
M2 Molog log(
(r( S 2k/ P) (H)+
2n
(40)
M2 (2
=2k4 E E TTET zELx
Ve d(z' 240 (H) +
2n
With y" = arg minleer Eneer ET Exelen Trzdda' xx) and I' = tr E k2x(m+
71 =
m 1}.
Thus, in observing that:
ΣΣ werdl')))) Σ Σ
Ye's min d(x',z) x)
xELK
#E ZEłK
W'ET r'ET IE
2 Σ Lik Σ x
#ET
xESK
2 Σ d( Lk)
T'ET
We deduce that our presented bound of Theorem is also tighter than the one proposed in (Shui et al. 2020) in the case of 0 and k-Lipschitz f and h.
19

---

Published as a conference paper at ICLR 2022
E ALGORITHMS (CF SECTION 3)
E. K-MEDOIDS
Algorithm 2 K-Medoids Greedy
1: Input: B, K, S, (d(x', S) (
2: Output: Tx = tajlisk CT
3: T ( ",,,,//))))))) with {x ( H'an picked randomly in T without replacement.
4: Initialize query subset: To =
5: For all x' E ET, d=
d(z', S)) msn d(a',a) 6: For all x, E T compute d d(x,x')
7: for from to K do
8: 3i 4 arg min Exer min (d ,d
9: S S U {
10: For all x' E T, update d' min(d _dad
end for
Algorithm 3 Branch & Bound Medoid (B & B)
1: Input: Cluster C' E _R previous medoid criterion C*,, batch size B
2: Output: New medoid x=
3: Initialize candidates Ö C=C C
4: Initialize computed distance set D2 = O for all æ E Ò.
5: Initialize criterion C. 0 and standard deviation 0 for all x E Č.
6: Initialize threshold
C*
7: for i from to n.. B do
8: G. {r CC; (B - 1)1 Sis Bi}
9:
for x E C do
10:
D, - D2 (d(x,x)); x' E C.).
11:
C - Bi EsED,
Oo V Bi EdeD, (d C2
13:
end for
t arg min éeC C2
15: 1 min(l, Cr. + 20,-
vBi
16:
Ö+ { x Ō Cz
<
/Bi
17: end for
18: x² c arg min ancn Cx
E.2 APPROXIMATION BOUND FOR THE GREEDY ALGORITHM
This section is dedicated to the proof of the bound for the greedy K-medoids algorithm which is expressed as follows:
The gain of selecting K new medoids with the greedy algorithm is an (1 approxxmtaiiii of the optimal gain.
Let Tx be a batch of K target points selected with the greedy algorithm. The gain is the difference between the initial objective and the final objective after selecting Tk:
gTin
Σ d(d's))
d(x' (U'') Σ ZET
(41)
TEE
With d(z',8) min (z)
20

---

Published as a conference paper at ICLR 2022
We will prove now that the gain is monotone submodular.
Let A c C T and I E T B.
We denote T fz's & T;d(æ', ( x) d(æ', A)) and T = TT: < d(z', BB}.
As A C B, we have d(z', A) 2 d(x', B) for any x' T. Thus,
T CT
(42)
Besides, for any x' E T,
d(x', A) - d(x', 2 d(x', B) d(x',x))
(43)
We deduce then that,
(ii(AAUx)) gain(A)
Σ d(d', A) -d(''
r'ETA
Σ d(d', A) Nal ,
ETETB
(44)
2
Σ
d(z', B) - d(z',z)
EEETB
gain B U {x}} gain B)
Then, the gain is submodular.
Besides, as A C B appears clearly that,
gain A) C (gain(
(45)
and the gain is monotone.
Finally, by noticing that the gain is always positive and according to (Nemhauser et al. 1978). we
conclude that the gain of selecting K new medoids with the greedy algorithm is an (1 1/e)- approximation the optimal gain.
E.3 COMPLEXITY COMPUTATION
In the following, distance computation is considered to be done in O(p).
1. KD-Trees Random Forest:
Each of the T trees is built by splitting one sample, each root, at the median of random feature until the leaf-sizes are ~ log(m). The median computation for each root with m, data is in O (m, log (og(m))). Thus the overall complexity to build one O(m log(m) EM 1) with M log(m/ (m)(
is O 2 log(2-'m)22) which becomes Om log(m))). Then, each target is assigned to a leaf by performing (log(m)) computations, inside the assigned leaf all distance computations are done in O(plog(m)). Thus an approximate nearest neighbour given for all targets with complexity (T((m pn) log(m)²).
2. Medoids Initialization: Using the greedy algorithm, O(pB²) distance computations are over the target data is computed each of the K steps. Thus the complexity is O(KK + p) B²).
first done, then, for all targets,
3. Assignation the Closest Medoid: The distance between all target and the medoids is computed in O pm).
4. Branch & Bound Medoid Computation
B & algorithm (Algorithm 3) takes as input one cluster C of n. unlabeled data from T. It also takes batch size B and the previous cluster medoid criterion C* which is used as
21

---

Published as a conference paper at ICLR 2022
an initial threshold. The use of the initialization C* may accelerate the algorithm, in the following we do not take into account this initialization, i.c we consider that C = +00.
Besides, to use notations consistent with the common notations in statistics, we will denote the batch size B by (B n). Notice that it is redundant with the size of the unlabeled data set T. An explicit mention will be made, if n does not refer to the batch size.
Definitions and notations: Let's consider one cluster C' C T with nh data. We consider the uniform norm as underlying distance d, defined for all Iy 23 E C as d(z,, =
max (Ie.") - x (1) (1., (P) - ==(²1) with I; = (a. (1) ;..., .?()) E TRP.
Computing the complexity of the B & B algorithm for any distribution of the xy would be too difficult. We make here the simplifying assumption that the x; in C are uniformly distributed on the hyper-cube C' of edge size 2 and centered on x* = (O...., 0) E R² We define for any E []1, nel] and any j E [11, nell, the variables Zj d(xi,,z)). We also define Zj = d(x", 22)) for any j E [11, nel). We suppose that for any i E [[], Zi:.., ..., Zn. are iid and that for any E [[,, the Zj are independents. We define, for any + Saee d(x;;; x)) and the variance of = Var = 1 [ (d(z;; 22- - )2) -c))- We consider a first batch of distance computations of size n < nc- []1, nell the empirical mean f.. - Zj and the empirical We define for any Σソ= p.)²². We denote by μ² and a²² the mean and variance of variance -7-
E [[l, the mean μi E| = 27
22
Lo and fL' and /- their respective empirical estimator.
We first observe that μ4 and o; are finite for any i E nell as the x; are uniformly distributed on the hyper-cube centered x² E C. We also notice that Z3 E [0, 2] for any j.j E nell-
Preliminary results: We make the assumption that p >> 1. We aim at giving bounds for any μr and o; We admit the intuitive results that for any I; = (I. .....
C and for any E []1, p4 2 10-00 and o; 2 of 0/-00 with 1 and of the mean and variance of the variable d(x: .) with x.. = (a; ,...., _i -(0-1) 0, x. (1+1) .!?) We consider indeed that the more x; is close to the center of the hyper-cube smaller is pr and o,
Considering this fact, we have, for any i E []1, nell:
pº S 14
(46)
o" S
(47)
Besides, for any S S. the sample density in the elementary surface between the balls centered on x² and of respective radius + dr and r is pr dr. Thus, we can notice that Zū follows a beta distribution of parameters a= p and 1, from which we deduce that:
P
(48)
p 1+1
P
(49)
(p- 1) + 2)
We further notice that for any S a S and for any E [|, nel] such that d(x", .x4)
we have 14 2 Ma with Ma the criterion of the sample Ia = (a, 0.....)) 0) E IP.
To compute Pa 20 Seec 2(),,)),, we split the integral on three parts: d(Ia: x)
S d(Fa, x) and 1 S d(Fa; x/) I + a:
dr /''
2/// rdr
1 lta
Na=
pr
(pre-1 + (p - 1)(1 a)r dr +
r-=1-a
p
p
+ (1 a) P p-1 (1 a)pt3 ( p
p+1 + P -P-1) )}
2 1+ 2
+
p+1
2
1p+1 1
p
a
a
+ 2
+ 2
2
a²
2 +1+
4
(50)
22

---

Published as a conference paper at ICLR 2022
Using the simplifying approximation - p-1 p>>>>>>>> 1. Thus for any 0 S a S 1 and for any i [[1, nel] such that d(æ*, Fi) we have:
p
a 4
M4 2 1
(51)
An upper bound of the of is given by the variance of of the variable d( with Iee = (I, 1) which corresponds to one corner of the hyper-cube C:
2 pr dr
2D J
pr
2
0
2
P
p+2
pp+1
(52)
p
(p +
()²
+
4
From which we deduce that for any ||1, nel::
S o; S 20¹
(53)
To simplify the calculations, make the approximation ã; = o, for any i [[1, nell, which
is relevant for sufficiently large n as E|Z < +o0.
Probability of rejecting all optimal medoid candidates: Let > 0 be an approximation factor of μ=" The goal of the Branch & Bound algorithm is identify one sample x, E C such that μ4 S μ (1 + e) with less distance computations as possible. The process consists in removing all candidates z; such that Pr empirical mean.
20
f4p
25 with fu, the current minimal
vn
We aim now at computing the probability of rejecting all optimal medoid candidates T; verifying μ4 S 1=11+++ c) during the B & B process. For this, define B.(x") = {i [1, pi S (1+++e)) the index set of optimal medoid candidates and (x²))) {i E
[1, p4 (1+++)) the index set of sub-optimal medoid candidates. We assume that B & B returns an optimal candidate if at least one sample of B (, ) is kept after the first batch computation. We define the following probabilities:
Pi = ( Bi E BE(") The
4a
S <1((1
(54)
Vn
PB P(FiE The (1 (1+++e44))
(55)
We observe that the probability of rejecting all optimal medoid candidates is upper bounded by: (1 - P2) + P2P1 considering the approximation o; = and the fact that o; 2 a² for any i [[1, nell.
We now define, for E (x()):
P. = P (1
40
Vn 1 11 (1++ (1+1))/4))
(56)
Leading to:
P. P ((
40
c4
< mr))
(57)
4
On the other hand, according to the Bennett's inequality from (Maurer & Pontil 2009
Hoeffding 1994) we have, for any i (z()") and for any 8 0:
of (
+ log(l/0) S u:/2 8
ps/2+
(58)
2n
3n
23

---

Published as a conference paper at ICLR 2022
Notice that apply the inequality to the Zj/2. Then, considering the fact that o; S 20*
and that pr > nr (1 (1+6 E) we have:
V20"
2 llg(1166)
Nh + P
vn Vlog(1/5)+
S (1(
(59)
3n
Leading to:
V20" Vlog(1/8) - ep² +
2 2log(1/6)
p4
S 42²
S 8
(60)
vn
3n
Let's consider > such that the following equality holds:
22
=p¹ + 2log(1/6)
40 915
Vlog(1/5)
(61)
vn
3n
n2
4
Thus:
u² + Au B
(62)
With:
v 1og(110)
(63)
A 2 V2nia*
(64)
3n
400
3ef4
B
(65)
2
nn
4
(66)
We then set:
(- (-(2-1)
)
2
exp
(67)
2
A v VA² A2 + 4B
(68)
We have for the ô defines above and for any E (p()):
P < 8
(69)
Thus, the probability Pi can be upper bounded as follows:
Pi < 1 - (1 8)
(70)
Considering the fact that (x(")) < ne. 1 (1 - 5)me is the probability of getting at least one success for the binomial law of parameters 6).
We now looking for upper bound of Ps. We observe that, least the index i such that
Di = x= in (jr"). Besides, as x" is the center of the hyper-cube, Zj is in [0, 1] for any
j E [I1, nell. We can then apply the Bennett's inequality to the Zj, and for any 7 > 0 we
have:
20 22 log(1/0
18)
log(1/5)
P 1 11" +
2 1--
(71)
3n
We set:
C + 40 - C
exp
(72)
2
C = 3/'no
(73)
D 3n 6/p
(74)
24

---

Published as a conference paper at ICLR 2022
We then have:
P2 2 P 1p )) 2 -2
(75)
Leading to:
1- 5y
(76)
Finally the probability of rejecting all optimal candidates is upper bounded by - (1 8)* + 7- To give order of magnitude of this probability, consider the scenario where nc = 10", = 100, n = Vne and c = 0.05. Then we have: = 3.6 10 and
= 7.7 10-5, which leads to a probability of rejection around 3.6 Thus, in this case, there is least a probability 0.995 that B & B returns medoid candidate with criterion less than 1.05 the optimal.
Complexity computation: We are now looking for the number of distance computations performed by B & B. For this, we need to compute the number of z; kept at each batch. An upper bound of this number is given by the number of æ; verifying t4 S p + e/44 /n
Se"
We further assume that the previous upper bound can be approximated by the number of of; verifying μi S 1 (1 + e/4)+
S
Vn.
We have shown in the preliminary results that for any E [[1, 14; 2 1 + a² with ((x;,."), Thus an upper bound of the number of candidates z; kept after the first batch is given by the number x; the ball radius a with a verifying:
80
2
(77)
Vn
Using the approximation n² p+I ~ 1. Besides, as o² O (1/p) we can suppose that for sufficiently large p and large n, previously, we have Ser Vn 0.005 and fe ~ 0.03). Thus:
80 /ū 1
1 3 (For instance with ne: n, and e considered
S 2/E
(78)
Finally the number of candidates kept after the first batch is in O (n. el/2) which is very
small (for the values of ne, p and considered previously, we have n. c0/2 10-60), If
consider batch size of O (nne), the number of distance computations after the first batch is negligible behind O (neyTe)).
We then conclude that the complexity of medoid computation in one cluster is in O (pnev/Te) as each of the K cluster has approximately The = n/K K samples (with n the sample size of T), the overall complexity of B & B is in O (pn3/2k-1/2)
F EMPIRICAL COMPLEXITIES
This section presents the empirical time computation recorded for K-medoids Greedy, Accelerated K-medoids, K-centers and K-centers KD-Trees which corresponds to the K-centers algorithm with initialization of the nearest source neighbour distances computed through the KD-Trees Random Forest algorithm. The experiments are conducted on the Digits data set.
The experiments are run (2.7GHz, 16G RAM) computer using Python 3.8. The scikit-learn (Pedregosa et al. (20IT) implementation of the pairwise euclidean distance used. No parallel computing is performed.
The parameters are set to K 100, = 50 for the KD-Trees Random Forest algorithm and an initial batch size B 5000 for the Accelerated K-medoids algorithm. The euclidean distance is used as base distance The results are reported on Figure The evolution of computational time is a function of the size of the source and target samples (m and n).
We first observe on Figure Segure3Sthtt that the K-medoids Greedy algorithm encounters computational burden 60kk, the K-centers algorithm encounters
for samples larger than 10k instances. For
25

---

Published as a conference paper at ICLR 2022
K-medoids Greedy
Accelerated K meddols
K-centers
Recorded in second
300
K-centers KD-Trees
250
200
150
100
33000
60000
Sample sizes of source and target data sets
Figure 5: Visualization of empirical computational times in function of the sample sizes.
similar issue due the computation of the distance matrix between the source and target data sets. Using the KD-Trees Random Forest algorithm decreases in this case the computational time by factor of 5. We also notice that the accelerated K-medoids algorithm has similar complexity performance to K-medoids for m < 5000 which is the maximum size of the initial batch. Then, the computation time of the algorithm increases slightly from n, m 5k to n, m 60k while remaining at acceptable level. For n, = 60k the complexities of the accelerated K-medoids and the K-centers + KDDTrees are almost similar but with a level of performance favor of the accelerated K-medoids (see Section 5.4).
We also present the evolution of the objective function the different algorithm in function of the 60k (cf Figure
number of queries K for
Evolution the objective function for the different algorithm
Kmeddlds Greedy
16
Accelearated K-medoids
K-centers
14
12
6-
40
Figure 6: Visualization of empirical objectives in function of the number of queries for a sample size of 60k.
We observe that the objective of the K-center algorithm is higher than the one of the K-medoids algorithms. We also observe that K-medoids Greedy provide slightly smaller objectives than K- medoids Accelerated.
26

---

Published as a conference paper at ICLR 2022
G EXPERIMENTS
G.1 SUPERCONDUCTIVITY
Setup The UCI data set "Supereconductivity"" (Hamidich 2018 Dua Graff 2017) is composed of features extracted from the chemical formula of several superconductors along with their critical temperature. There is two kind features: some features correspond to the chemical element number's s in the superconductor chemical formula, others are statistical features derived from the chemical formula as the mean and variance of the atomic mass.
We the setup of (Pardoe & Stone 2010) divide the data set in separate domains. We select an input feature with a moderate correlation factor with the output (~ 0.3). We then sort the set according this feature and split in four parts: low (),, middle-low (ml), middle-high (mh), high (h). Each part defining a domain with around 4000 instances and 166 features. The considered feature then withdrawn from the data set.
A standard scaling preprocessing is performed using the source data on the input statistical features and the output feature. A max scaling performed features corresponding the chemical element number's. A visualization of the first components of the PCA as well as the output distribution is provided in Figure
PCA input features X
Output Distribution
midle-low
midle-low
midle-high
midle-high high
high
0.06
5-
0.02
-5
25
20
60
80
100
120
140
PCA first component
Critical Temperature (in
Figure 7: Visualization of the domain shift of the superconductivity data set. The visualization the two first components of the PCA on the input features is given the left. The output distribution is given on the right. One domain represented by one color.
Standard deviation Table 2 presents the standard deviation of the MAEs obtained on the repetitions of the 12 experiments with the Balanced Weighting training and K 20. We observe that K-medoids provides the smallest standard deviations in the majority of the experiments. K-medoids is indeed a deterministic algorithm and thus selects a determined batch of target points. Besides, K-medoids selects the target batch to label in distribution matching perspective, i.e. produces training set with distribution close to the one of the testing set (cf Section 2). This can explain why the training more stable with the training set provided by K-medoids.
Table 2: Standard deviations the MAE on the unlabeled data for the superconductivity experiments. The deviations are computed using the results of repetitions of each experiment.
Experiment
1-2mh
Random
1.007
2.599
1.597
1.232
1.679
1.291
1.363
0.787
0.266
1.900
1.228
0.595
Kineans
1.05
0.93
0.78
1.93
0.54
0.64
1.0
1.36
0.58
6.51
1.51
0.59
QRC
1.469
2.370
1.882
0.571
0.564
0.707
2.151
0.767
0.394
7,240
3.250
0.620
Keenters
0.807
1.761
1.926
0.626
0.343
0.794
2.188
0.885
0.503
5.403
2.838
Diversity
1.34
1.2
3.28
0.52
0.8
1.86
2.46
0.79
0-42
5.49
1.44
0.32
Kinedoiis
27

---

Published as a conference paper at ICLR 2022
Table 3: MAE the critical temperature for the Superconducttivtyy experiments with Balanced
Weighting and K 20.
Experiment
1-
1-
1-+h
mi-+1
ml-+ph
ml--b
mhh+1
mh-+ml
mh++h
h-+1
h=+ml
h mh
Random
15.33
15.80
17.45
16.53
11.39
14.70
17.65
12.83
10.36
18.75
14.86
10.54
Kmsans
14.43
13.60
13.98
15.79
10.19
12.73
17.18
12.67
10.02
22.10
14,69
9.76
Koenters
19.21
15.73
16.85
15.75
11.62
13.44
22.17
12.74
10.24
36,50
19.60
10.39
Diversity
19.46
18.21
18.68
16.01
11.94
15.36
23.92
14.31
10.70
37.97
20.89
10.78
Kmeedoids
12.70
13.57
14.11
14.49
10,02
12.52
15.36
12.37
9.79
16.62
14.14
9.32
(high to low) analysis An interesting fact to notice in the results of the superconductivity experiments (for which recap is given in 3 the asymmetry of results between the low-to-high experiment and the high-to-low experiment. Indeed, the results on the latter experiment are worse than the ones of the former, except for the Random and K-medoids algorithms.
first appears, in Figure 8 that this difference in performance for the low-to-high experiment compared the high-to-low experiment comes from the difference in the output distributions of the low and high domains. Indeed, the output distribution of the high domain is made of one mode concentrated in the low temperature while the output distribution of low is made of modes, one in the low and the other in the high temperature. Thus, the model trained with the low domain data will generalize better the high domain since the model has seen the full range of temperature. In the inverse problem (high-to-low), the model has only seen low temperatures and thus poorly predict a part of the low domain. Then, for this difficult experiment (high-to-low), the difference in performance between the different query algorithms lies mainly in the number of data with high temperature the low domain that are queried (see Figure It appears that K K-medoids and Random query more of this type of data, they are highly concentrated and relatively far from the sources (see Figure 10 11
PCA on input features X
Output Distribution
10.0
High Low
High
0.75
Low
7.5
5.
PCA second componett
25
Probabilies
0.125
0.100
0.775
-75
0.025
-100
0.000
160
PCA first component
Cr tical Temperature (in
Figure 8: Visualization of the domain shift of the superconductivity data set for the high-to-low experiment. The visualization of the two first components the PCA on the input features given on the left. The output distribution is given on the right. One domain is represented by one color.
28

---

Published as a conference paper at ICLR 2022
K-medoids Score: 15.802
Random Score: 17.305
K-centers Score: 37.360
0.375
High Low
0.75
High
Low
High
Low
0125
0125
0.125
0100
0100
0100
0050
0050
0.059
0.000
0.000
11
0.000
20
100
140
100
140
120
Diversity
22.240
High
High
High
0.175
0.75
0175
0.000
0100
0100
0.50
0.50
0.000
0825
0.05
0.025
1,1
20
40
60
100
120
160
40
60
80
100
120
140
40
60
80
100
120
340
Criical Temperature (in
Cr Oriical lemperature (m
Cr Cribcal lemperature (m
Figure 9: Visualization the queries in the output space for the high-to-low experiment with K = 20.
K-medoids Score: 15.802
Random Score: 17.305
K-centers 37.360
High
Low Queries
Diversity Score: 33.937
K-means Score: 22.240
QBC Score: 35,292
Figure 10: Visualization of the queries in the input space for the high-to-low experiment with K = 20.
29

---

Published as a conference paper at ICLR 2022
PCA input features X
10.0
Low
5.0
PCA second component
Critical temperature
0.0
-25
-75
-10.0
15
PCA first component
Figure 11: Visualization of the the input space for the high-to-low experiment. The heatmap gives the output labels for the "low" domain.
G.2 OFFICE
back pack
belmet
bottle
dosk lamp
dasktop computer
cabineet
bendlloones
keybouod
baplop compuiee
letter tasy
Goe AMDAE
mobill plune
monitor
monte
msgg
pagez sotebook
plune
peinter
projedue
punchets
ring binder
milrr
scisoes
spenker
stapher
dippmer
trash can
Figure 12: Office data set: examples of images from amazon domain
30

---

Published as a conference paper at ICLR 2022
back pack
Ieler
Ielas belone
booloase
buttle
calcolator
deek chair
desk Ismu
dosktop computter
file cabinee
hendphonss
keyboood
laplop comprate
letter taay
mobile phome
monilor
urgg
paper sotebook
phone
peintiee
projecto
punchets
ring bindes
riler
scisoes
speaker
stapler
dipenser
trash can
Figure 13: Office data set: examples of images from webcam domain
31

---

Published as a conference paper at ICLR 2022
G.3
DIGITS
47
40
13
2
13
254
6
7
08
9
Figure 14: Digits data set: examples of SYNTH images
2
3
122
43
6
88
9
Figure 15: Digits data set: examples of SVHN images
32


Reviews:
[{"review_id": "udLiTbx1K0p", "reviewer": "Reviewer_bRBm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1) Overall, the paper addresses an important problem and formalizes the task of active learning for domain adaptation. \n2) It is interesting to see that the minimization of the target risk maps to the k-medoid problem.\n\nCons:\n\n1) One of the main concerns is that the final algorithm used is a classical clustering algorithm based on k-medoids. K-medoids is well studied and has been used in the active learning context before and several efficient implementations of the k-center have been studied. \n\n2) In addition to datasets such as UCI and superconductivity, it would be good to show results on standard datasets such as CIFAR10, CIFAR100, and MNIST by treating one as source and the other one as target?\n\n3) While the paper says that k-medoid can be solved using greedy and provides a bound of 1-1/e it does not explain how this is achievable. One possible interpretation is that k-medoid can be seen as the maximization of submodular functions and this leads to an approximation guarantee of 1-1/e. The bound (1-1/e)-approximation only applies to the original objective function of k-medoid where we use greedy to compute all the elements of the subset. Here we use all the points from the source set and only label K elements in the target set. The authors need to carefully provide all the details of this bound as it may not directly translate from the original problem. \n\n4) There is also a close connection to the use of MMD for subset selection shown in [Kim et al. 2016]. This paper looks at the MMD measure and shows that the selection of prototypes and criticisms can be mapped to the maximization of submodular functions and solved using greedy as well. Kim et al. Examples are not enough, learn to criticize! Criticism for Interpretability, 2016.\n\n5) I find this comparison with k-center a bit vague. The paper makes simplifying assumptions such as f=f_P = f_Q and \\epsilon = 0 and shows that the bound using k-medoids is tighter than k-center in equations (5) and (6).  While max_{x’\\in T} d(x’,L_k) is higher than (1/n)\\sum_{x’ \\in T}d(x’L_k), both k-center and k-medoids are solved with greedy algorithms with approximation guarantees, and it is not clear whether such a comparison can be treated as a formal result. \n\n6) It would be good to provide more intuition on the choice of weighted k-medoids algorithm with weights multiplied with the min d(x,x’)? Typically, when we do a weighted extension, we can consider two terms in many active learning objective functions where one term models the uncertainty that looks for points near the decision boundary and the other term models the uncertainty. The paper uses uncertainty weights loosely in equation (7) without sufficient justification as to why multiplying the weights would be better than using this as an additive term. \n", "summary_of_the_paper": "This paper proposes a k-medoid solution for active learning in the context of domain adaptation. The paper builds on top of Mansour et al. (2009) and looks at the discrepancy between source and target distributions. Looking at the whole hypothesis space is very conservative since this would include hypotheses that the learner would never consider as a labeling function. In order to deal with this problem, this paper only considers localized discrepancy (Zhang et al. 2020) where we only consider the hypotheses that are epsilon away from labeling function for source domain, i.e. we are only considering labeling functions that are epsilon away from the source labeling function. Generalization bounds are derived using Rademacher average and localized discrepancy for general loss functions. From these bounds, the paper shows that one can minimize the target risk by solving a k-medoid problem. \n", "summary_of_the_review": "While the formalizes and motivates the proposed solution, I don't see any novelty in the final algorithm used for domain adaptation. There are also many loose ends that I feel that the authors should address. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JWlPWVBGg24", "reviewer": "Reviewer_Nd1E", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Studying the domain adaptive active learning problem on both theoretical and methodological levels in a consistent way is a strong side of the paper. On the other hand, the novelty of the methodological contribution is limited as the proposed adaptation of the K-medoids method is simply put forward as a combination of a couple of baseline strategies from previous literature. Another aspect that could be improved is the presentation of the proposed algorithm: The discussion of the proposed method is given at a very high level, without explaining, motivating or describing the involved steps in much detail.\n\nMore detailed remarks:\n\n1. In Theorem 1:\n- Please define explicitly what the distance d(x',x) stands for. \n- \"We denote by M the bound of L\": Please define this mathematically.\n- I guess the term L_P(h,f) should have been L_P(h,f_P) rather.\n\n2. In the experimental results, there are some algorithms used in the comparisons in Figure 3, but skipped in the results of Figure 2 (like BADGE, CLUE, ...). Is there a reason for this (not suitable for regression tasks, etc.)?", "summary_of_the_paper": "The paper studies the problem of active learning for domain adaptation. The paper has two main contributions. First, the problem of the selection of a query target sample set is studied theoretically. A generalization bound is presented, which is based on the recently proposed concept of localized discrepancy as opposed to rather classical discrepancy measures that can be too conservative. The second contribution of the paper is an algorithm for the batch selection of K target queries, which is motivated by the theoretical findings. ", "summary_of_the_review": "While the proposed methodology is of limited novelty and not described in a self-contained manner, when considered along with the proposed theoretical framework, the contributions of the paper may be worth sharing with the community. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CMcL99drJ4i", "reviewer": "Reviewer_Xjwo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1. The authors provide a computable way to conduct batch active learning for domain adaptation, and the method shows empirical advantages over existing ones.\n2. The authors provided an accelerated version of the K medoids algorithm, and also analyzed its computational complexity.\n3. The paper is generally well-written, and the authors also provide visual insights to help understand the paper. \n\nWeaknesses:\n1. Since the localized discrepancy is proposed in Zhang et al 2020 (as noted by the authors in the paper as well), I think it's fair to say that, on the theoretical side, the main contributions are (1) the relaxation of the localized discrepancy under Lipschitzness and (2) the accelerated K-medoids algorithm (for the relaxation). That being said, the proposed algorithms only apply to restricted cases.\n2. Following the previous point, my biggest concern is how well the relaxation is, even under Lipschitzness? The authors didn't provide a thorough comparison between bounds in Eq (3) and Eq (4). As a result, the relaxation could be meaningless if Eq (4) is much larger than Eq (3) (say, in some cases).\n3. The algorithm is restricted to the batched active learning case, where the learner picks the queried data in a single batch. What would can in the more general sequential case?\n4. I'm guessing that the requirement $\\epsilon \\geq \\eta_H$ in the theoretical guarantees is to make $H^K_{\\epsilon}$ is not empty, is that right? But I wonder why choose $\\eta_H$ as the threshold value? Seems that we could have $H^K_{\\epsilon}$ being non-empty for an $\\epsilon$ smaller than $\\eta_H$ since the definition of $\\eta_H$ has a summation of two things.\n5. In Section 4.3 the authors wrote \"... the parameter $\\epsilon$ will be small because ... This would lead to $\\epsilon < \\eta_H$ and the bound would not be valid anymore\". Isn't it true that $\\eta_H$ would get smaller as well when $H$ has a great approximation power. Also, a related question is that I thought $\\epsilon$ is a parameter that the learner gets to choose, i.e., one can simply choose an $\\epsilon$ larger than $\\eta_H$ (if it's known). \n", "summary_of_the_paper": "This paper studies active learning for domain adaption for a set of Lipschitz functions. The paper proposes to use a localized discrepancy to restrict the relevant candidate hypotheses. Under Lipschitzness, the localized discrepancy is further relaxed into a distance measure over the X domain; the authors also design an accelerated K-medoid algorithm to minimize such distance. In special cases (under certain simplifying assumptions), theoretical guarantees presented in this paper show advantages over previous ones. The proposed algorithm also shows empirical advantages over existing ones.", "summary_of_the_review": "Based on the strengths and weaknesses listed above, I think overall the paper is marginally above the threshold. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9i71ilgvmYV", "reviewer": "Reviewer_jrGL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### strength \n\n- In the conventional active learning methods, it has been the mainstream to select the input of the target domain to be labeled based on the output of the domain classifier trained at the same time (in general, the relationship between this criterion and the expected risk of the target domain is unclear). On the other hand, this paper proposes an single-shot active learning method that chooses the data to be labeled in the target domain in such a way that the expected risk of the target domain is directly reduced. \n\n- The part corresponding to the discrepancy in the theoretically derived upper bound of the target risk does not depend on the complexity of the hypothesis set (strength of Lipschitz condition) and the shape of the loss function. This has the advantage that the algorithm for active learning can be constructed in the way of hypothesis set-free or loss function-free. Actually, the proposed algorithm can be interpreted as a clustering algorithm that minimizes the sum of the distances between the data.\n\n- The proposed method, Accelerated K-medoids, is not only a method for selecting K inputs to be labeled in the target domain, but also an algorithm for clustering. In fact, it is an improved version of Greedy K-medoids method in which the computational complexity with respect to sample size is improved from n^2 to n^3/2.\n\n\n### weakness\n- In the appendix, the authors compare the empirical computational time of the Greedy K-medoids and the Accelerated one, and show the effectiveness of the latter.　On the other hand, it is not specifically mentioned how these two algorithms relate in terms of the expected risk of the target domain. If the two algorithms produce identical output, it is better to explain that, and if not, the two algorithms should be compared not only in terms of computational time but also in terms of the expected risk of the target domain.\n\n\n### questions\n- In the results shown in Table 1, the accuracy of l → h (low to high) and h → l (high to low) seem to change significantly (the latter is worse) except for random and Kmedoids. What could be the reason for this? Also, can you argue that the proposed method gives more robust results even when this phenomenon (asymmetry) occurs using other methods?\n\n- For the Localized Discrepancy, how much can we expect the situation that \"the restricted hypothesis set H^K_{\\epsilon} is not empty and the tolerance \\epsilon is reasonably small\"?\n\n- Although this paper deals with 1-shot active learning, can I understand that if we iterate this method, we can also empirically approximate the risk in the target domain and evaluate the joint error \\eta_H in the risk upper bound?\n\n- In Sec 5.1, the author claim that \"We assume that the architecture and the resulting hyper-parameters will still be appropriate after adding the queried target data to the training set\" while could you give an example of possible situations where this assumption does not hold? I would like to know how reasonable this assumption is.", "summary_of_the_paper": "This paper proposes an active learning method to efficiently select data in the target domain that is suitable for learning hypotheses together with data in the source domain in domain adaptation problems. \n\nThe authors first propose to evaluate the dissimilarity between the source and target domains by localized discrepancy, where the hypothesis set is restricted to includes only hypothesithes with sufficiently small errors with the label function of the source domain on the training data (the union set of the input of the source domain and the input of the target domain to be labeled). Then an upper bound of the expected risk for the target domain based on this discrepancy. The main theoretical contribution is that the authors have shown that the discrepancy term in this upper bound is further bounded from above by the sum of the distances between the inputs of the training data and the inputs of the target domain, and this is the background for the design of the active learning algorithm. \n\nIn domain adaptation, the goal is to solve the problem of minimizing the discrepancy between the two domains. From the statements of this theorem, it can be replaced by the problem of selecting K data in the target domain so as to minimize the sum of the distances between the inputs of the training data and the inputs of the target domain. The latter problem is equivalent to solving the K-medoids problem for clustering, and the authors' technical contribution is that they have proposed an accelerated algorithm for this problem. \n\nFinally, the authors conduct an evaluation experiment of the proposed method under various scenarios of domain shift using three types of benchmark data.\n", "summary_of_the_review": "This paper deals with the important topic of active transfer learning and is considered to be a contribution to both theory and experiment.　Although there are some shortcomings in the experiments and some questions, I can generally support the acceptance of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper deals with the important topic of active transfer learning. All reviewers agree that
while the paper presents some shortcomings , it is considered to be a worth contribution.
Decision: Accept (Poster)