summaries: 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.   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.   The 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.   In 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.   Finally, the authors conduct an evaluation experiment of the proposed method under various scenarios of domain shift using three types of benchmark data.  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.  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.
abstractText: 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 Kmedoids 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.
authors.name: Antoine de Mathelin
authors.name: François Deheeger
authors.name: Mathilde Mougeot
authors.name: Nicolas Vayatis
references.authors: Jordan T Ash Chicheng Zhang Akshay Krishnamurthy John Langford Alekh Agarwal
references.title: Deep batch active learning by diverse, uncertain gradient lower bounds
references.venue: In International Conference on Learning Representations,
references.authors: Maria-Florina Balcan Andrei Broder Tong Zhang
references.title: Margin based active learning
references.venue: In International Conference on Computational Learning Theory,
references.authors: Maria-Florina Balcan Alina Beygelzimer John Langford
references.title: Agnostic active learning
references.venue: Journal of Computer and System Sciences,
references.authors: Alina Beygelzimer Sanjoy Dasgupta John Langford
references.title: Importance Weighted Active Learning, pp. 49–56
references.venue: Association for Computing Machinery,
references.authors: Zalán Bodó Zsolt Minier Lehel Csató
references.title: Active learning with clustering
references.venue: JMLR Workshop and Conference Proceedings,
references.authors: David Cohn Les Atlas Richard Ladner
references.title: Improving generalization with active learning
references.venue: Machine learning,
references.authors: Corinna Cortes Mehryar Mohri
references.title: Domain adaptation and sample bias correction theory and algorithm for regression
references.venue: Theoretical Computer Science,
references.authors: Corinna Cortes Giulia DeSalvo Claudio Gentile Mehryar Mohri Ningshan Zhang
references.title: Regionbased active learning
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics,
references.authors: Corinna Cortes Giulia DeSalvo Mehryar Mohri Ningshan Zhang Claudio Gentile
references.title: Active learning with disagreement graphs
references.venue: In International Conference on Machine Learning,
references.authors: Corinna Cortes Mehryar Mohri Andrés Muñoz Medina
references.title: Adaptation based on generalized discrepancy
references.venue: J. Mach. Learn. Res.,
references.authors: Corinna Cortes Giulia Desalvo Claudio Gentile Mehryar Mohri Ningshan Zhang
references.title: Adaptive region-based active learning
references.venue: Proceedings of the 37th International Conference on Machine Learning,
references.authors: Antoine de Mathelin François Deheeger Guillaume Richard Mathilde Mougeot Nicolas Vayatis
references.title: Adapt: Awesome domain adaptation python toolbox
references.venue: arXiv preprint arXiv:2107.03049,
references.authors: Cheng Deng Xianglong Liu Chao Li Dacheng Tao
references.title: Active multi-kernel domain adaptation for hyperspectral image classification
references.venue: Pattern Recognition,
references.authors: Dheeru Dua Casey Graff
references.title: UCI machine learning repository, 2017
references.venue: URL http://archive. ics.uci.edu/ml
references.authors: Yarin Gal Riashat Islam Zoubin Ghahramani
references.title: Deep Bayesian active learning with image data
references.venue: In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning,
references.authors: Yaroslav Ganin Evgeniya Ustinova Hana Ajakan Pascal Germain Hugo Larochelle François Laviolette Mario Marchand Victor Lempitsky
references.title: Domain-adversarial training of neural networks
references.venue: J. Mach. Learn. Res.,
references.authors: Daniel Gissin Shai Shalev-Shwartz
references.title: Discriminative active learning
references.venue: arXiv preprint arXiv:1907.06347,
references.authors: Ryan Gomes Andreas Krause
references.title: Budgeted nonparametric learning from data streams
references.venue: In Proceedings of the 27th International Conference on International Conference on Machine Learning,
references.authors: Jean-Bastien Grill Michal Valko Rémi Munos
references.title: Black-box optimization of noisy functions with unknown smoothness
references.venue: In Neural Information Processing Systems,
references.authors: Q. Gu J. Han
references.title: Towards active learning on graphs: An error bound minimization approach
references.venue: IEEE 12th International Conference on Data Mining,
references.authors: Kam Hamidieh
references.title: A data-driven statistical model for predicting the critical temperature of a superconductor
references.venue: Computational Materials Science,
references.authors: Steve Hanneke
references.title: A bound on the label complexity of agnostic active learning
references.venue: In Proceedings of the 24th international conference on Machine learning,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Wassily Hoeffding
references.title: Probability inequalities for sums of bounded random variables
references.venue: In The Collected Works of Wassily Hoeffding,
references.authors: Rong Hu Brian Mac Namee Sarah Jane Delany
references.title: Off to a good start: Using clustering to select the initial training set in active learning
references.venue: In FLAIRS Conference,
references.authors: Rishabh K Iyer Jeff A Bilmes
references.title: Submodular optimization with submodular cover and submodular knapsack constraints
references.venue: In Advances in Neural Information Processing Systems,
references.authors: S.D. Jain K. Grauman
references.title: Active image segmentation propagation
references.venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: A.J. Joshi F. Porikli N. Papanikolopoulos
references.title: Multi-class active learning for image classification
references.venue: In 2009 IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Leonard Kaufman Peter J Rousseeuw
references.title: Finding groups in data: an introduction to cluster analysis, volume 344
references.authors: Leonard Kaufmann Peter Rousseeuw
references.title: Clustering by means of medoids
references.venue: Data Analysis based on the L1-Norm and Related Methods, pp. 405–416,
references.authors: V. Kaushal R. Iyer S. Kothawade R. Mahadev K. Doctor G. Ramakrishnan
references.title: Learning from less data: A unified data subset selection and active learning framework for computer vision
references.venue: IEEE Winter Conference on Applications of Computer Vision (WACV),
references.authors: Been Kim Rajiv Khanna Oluwasanmi O Koyejo
references.title: Examples are not enough, learn to criticize! criticism for interpretability
references.venue: Advances in neural information processing systems,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations,
references.authors: Karol Kurach Mario Lučić Xiaohua Zhai Marcin Michalski Sylvain Gelly
references.title: A large-scale study on regularization and normalization in gans
references.venue: In International Conference on Machine Learning,
references.authors: Ailsa H Land Alison G Doig
references.title: An automatic method for solving discrete programming problems
references.venue: Years of Integer Programming
references.authors: Yann LeCun Léon Bottou Yoshua Bengio Patrick Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: Hui Lin Jeff Bilmes Shasha Xie
references.title: Graph-based submodular selection for extractive summarization
references.venue: IEEE Workshop on Automatic Speech Recognition & Understanding,
references.authors: Cédric Malherbe Nicolas Vayatis
references.title: Global optimization of lipschitz functions
references.venue: In International Conference on Machine Learning,
references.authors: Yishay Mansour Mehryar Mohri Afshin Rostamizadeh
references.title: Domain adaptation: Learning bounds and algorithms
references.venue: In COLT,
references.authors: Andreas Maurer Massimiliano Pontil
references.title: Empirical bernstein bounds and sample variance penalization
references.venue: arXiv preprint arXiv:0907.3740,
references.authors: Mehryar Mohri Afshin Rostamizadeh Ameet Talwalkar
references.title: Foundations of machine learning
references.venue: MIT press,
references.authors: Saeid Motiian Marco Piccirilli Donald A Adjeroh Gianfranco Doretto
references.title: Unified deep supervised domain adaptation and generalization
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: George L Nemhauser Laurence A Wolsey Marshall L Fisher
references.title: An analysis of approximations for maximizing submodular set functions—i
references.venue: Mathematical programming,
references.authors: Yuval Netzer Tao Wang Adam Coates Alessandro Bissacco Bo Wu Andrew Y. Ng
references.title: Reading digits in natural images with unsupervised feature learning
references.venue: In NIPS Workshop on Deep Learning and Unsupervised Feature Learning
references.authors: James Newling François Fleuret
references.title: A sub-quadratic exact medoid algorithm
references.venue: In Artificial Intelligence and Statistics,
references.authors: Raymond T. Ng Jiawei Han
references.title: Clarans: A method for clustering objects for spatial data mining
references.venue: IEEE transactions on knowledge and data engineering,
references.authors: David Pardoe Peter Stone
references.title: Boosting for regression transfer
references.venue: In Proceedings of the 27th International Conference on Machine Learning (ICML),
references.authors: Hae-Sang Park Chi-Hyuck Jun
references.title: A simple and fast algorithm for k-medoids clustering
references.venue: Expert systems with applications,
references.authors: F. Pedregosa G. Varoquaux A. Gramfort V. Michel B. Thirion O. Grisel M. Blondel P. Prettenhofer R. Weiss V. Dubourg J. Vanderplas A. Passos D. Cournapeau M. Brucher M. Perrot E. Duchesnay
references.title: Scikit-learn: Machine learning in Python
references.venue: Journal of Machine Learning Research,
references.authors: Viraj Prabhu Arjun Chandrasekaran Kate Saenko Judy Hoffman
references.title: Active domain adaptation via clustering uncertainty-weighted embeddings
references.venue: arXiv preprint arXiv:2010.08666,
references.authors: Piyush Rai Avishek Saha Hal Daumé III Suresh Venkatasubramanian
references.title: Domain adaptation meets active learning
references.venue: In Proceedings of the NAACL HLT 2010 Workshop on Active Learning for Natural Language Processing,
references.authors: T. RayChaudhuri L.G.C. Hamey
references.title: Minimisation of data collection by active learning
references.venue: In Proceedings of ICNN’95 - International Conference on Neural Networks,
references.authors: Kate Saenko Brian Kulis Mario Fritz Trevor Darrell
references.title: Adapting visual category models to new domains
references.venue: In Proceedings of the 11th European Conference on Computer Vision: Part IV,
references.authors: Avishek Saha Piyush Rai Hal Daumé Suresh Venkatasubramanian Scott L DuVall
references.title: Active supervised domain adaptation
references.venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,
references.authors: Ozan Sener Silvio Savarese
references.title: Active learning for convolutional neural networks: A core-set approach
references.venue: In International Conference on Learning Representations,
references.authors: Burr Settles
references.title: Active learning literature survey
references.venue: University of Wisconsin, Madison, 52,
references.authors: Changjian Shui Fan Zhou Christian Gagné Boyu Wang
references.title: Deep active learning: Unified and principled method for query and training
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Chanop Silpa-Anan Richard Hartley
references.title: Optimised kd-trees for fast image descriptor matching
references.venue: IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Samarth Sinha Sayna Ebrahimi Trevor Darrell
references.title: Variational adversarial active learning
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: J. Su Y. Tsai K. Sohn B. Liu S. Maji M. Chandraker
references.title: Active adversarial domain adaptation
references.venue: IEEE Winter Conference on Applications of Computer Vision (WACV),
references.authors: Takeshi Teshima Issei Sato Masashi Sugiyama
references.title: Few-shot domain adaptation by causal mechanism transfer
references.venue: In International Conference on Machine Learning,
references.authors: Michal Valko Alexandra Carpentier Rémi Munos
references.title: Stochastic simultaneous optimistic optimization
references.venue: In International Conference on Machine Learning,
references.authors: Tom Viering Jesse Krijthe Marco Loog
references.title: Nuclear discrepancy for single-shot batch active learning
references.venue: Machine Learning,
references.authors: Zheng Wang Jieping Ye
references.title: Querying discriminative and representative samples for batch mode active learning
references.venue: ACM Trans. Knowl. Discov. Data,
references.authors: Kai Wei Yuzong Liu Katrin Kirchhoff Jeff Bilmes
references.title: Using document summarization techniques for speech data subset selection
references.venue: In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,
references.authors: Kai Wei Rishabh Iyer Jeff Bilmes
references.title: Submodularity in data subset selection and active learning
references.venue: International Conference on Machine Learning,
references.authors: Yuchen Zhang Tianle Liu Mingsheng Long Michael Jordan
references.title: Bridging theory and algorithm for domain adaptation
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: Yuchen Zhang Mingsheng Long Jianmin Wang Michael I Jordan
references.title: On localized discrepancy for domain adaptation
references.venue: arXiv preprint arXiv:2008.06242,
references.authors: Jingjing Zheng Zhuolin Jiang Rama Chellappa Jonathon P Phillips
references.title: Submodular attribute selection for action recognition in video
references.venue: Advances in Neural Information Processing Systems
sections.heading: 1 INTRODUCTION
sections.text: Machine learning models trained on a labeled data set from a source domain may fail to generalize on new target domains of interest (Saenko et al., 2010). This issue, which can be caused by domain shift, can be handled when no 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 (Motiian et al., 2017). Acquiring such new labels is often expensive (Settles, 2010) and one seeks to query as few labels as possible. This explains why strategies of optimal labels acquisition, referred as active learning (Cohn et al., 1994) seem very promising for domain adaptation (Su et al., 2020).
  Active learning is a challenging task and a 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., 2010; Bodó et al., 2011) or the minimization of target uncertainties (RayChaudhuri & Hamey, 1995; Gal et al., 2017) are considered, as well as combination of these heuristics (Wei et 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 on distribution matching aim at minimizing a distribution distance between the labeled set and the unlabeled one (Balcan et al., 2009; Wang & Ye, 2015; 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) or based on 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 2, we derive theoretical results by adopting a 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 a 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 at antoine.de-mathelin-de-papigny@michelin.com
  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 1). Inspired by this generalization error bound, we propose in Section 3 an accelerated K-medoids query algorithm which scales to large data set. In Section 4, 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.
sections.heading: 2 DISCREPANCY BASED ACTIVE LEARNING
sections.text: Setup and theory develop in this section mainly focus on regression tasks. Section 4.3 presents how the algorithm derived from the theoretical results can be extended to classification tasks.
sections.heading: 2.1 SETUP AND DEFINITIONS
sections.text: Given two subsets X ⊂ Rp and Y ⊂ Rq and d : X ×X → R+ a distance on X , we denote the source data set S = {x1, ..., xm} ∈ Xm and the target data set T = {x′1, ..., x′n} ∈ Xn. 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 × Y → R+ and a hypothesis space H of k-Lipschitz functions from X to Y . We denote by LD(h, h′) = Ex∼D[L(h(x), h′(x))] the average loss (or risk) over any distribution D on X between two hypotheses h, h′ ∈ H . We also define the expected Rademacher complexity of H for the distribution P as:
  Rn(H) = E {x′i}i∼P
  [ E
  {σi}i∼U [ sup h∈H 1 n n∑ i=1 σih(x ′ i) ]] ,
  with σi drawn according to U the uniform distribution on {−1, 1}. We consider a labeling function for each distribution: fQ : X → Y and fP : X → Y . For adaptation 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 are picked in one single batch of fixed budget of K > 0 queries. In this framework, an active learning 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 a batch of K queried target data denoted TK ⊂ 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 ∪ 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, fP ).
sections.heading: 2.2 LOCALIZED DISCREPANCY
sections.text: 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 et 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 et al., 2020) 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 ϵ ≥ 0. Let TK be a queried batch of size K, the empirical distributions of LK = S ∪TK and T are respectively denoted Q̂K and P̂ . Let H be a hypothesis space and L a loss function. The localized discrepancy is defined as:
  discHKϵ (Q̂K , P̂ ) = maxh,h′∈HKϵ |LQ̂K (h, h ′)− LP̂ (h, h ′)| , (1)
  with HKϵ = {h ∈ H; L(h(x), fQ(x)) ≤ ϵ ∀x ∈ LK}
  The localized space HKϵ includes hypotheses ”consistent” with fQ on the labeled data, i.e. hypotheses fitting the labeled data with an error below ϵ. The parameter ϵ drives the size of HKϵ . Obviously, ϵ needs to be high enough to ensure that HKϵ 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 > 0 be the number of queries and H a hypothesis space. Let P̂ and Q̂K be the empirical distributions of the respective sets T and LK = S ∪ TK of respective size n and m+K. We assume that L is a symmetric, µ-Lipschitz and bounded loss function verifying the triangular inequality. We denote by M the bound of L. Let ηH be the ideal maximal error on S ∪ T :
  ηH ∆ = min
  h∈H max x∈S∪T [L(h(x), fQ(x)) + L(h(x), fP (x))] (2)
  Then, for any ϵ ≥ ηH , any hypothesis h ∈ HKϵ and any δ > 0, the following generalization bound holds with at least probability 1-δ:
  LP (h, fP ) ≤ LQ̂K (h, fQ) + discHKϵ (Q̂K , P̂ ) + ηH + 2µRn(H) +M √ log( 1δ ) 2n  . (3) This bound share a similar form than the one derived in Cortes et al. (2019c) for the discrepancy. The ideal maximal error ηH characterizes the difficulty of the adaptation problem as well as the ability to learn the labeling functions with the considered hypothesis set H . If fP and fQ significantly differ on S ∪ T , ηH 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).
sections.heading: 2.3 MAIN RESULTS: GENERALIZATION BOUNDS FOR ACTIVE LEARNING
sections.text: Considering the previous bound (Proposition 1) it appears that a natural way of choosing the K queries in 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 HKϵ . Our main idea is then to further bound the localized discrepancy with a computable criterion: Theorem 1. Let K > 0 be the number of queries, H a hypothesis space of k-Lipschitz functions and ϵ ≥ ηH . Let LK = S ∪TK be the labeled set and T the target set drawn according to P . We assume that L is a symmetric, µ-Lipschitz and bounded loss function verifying the triangular inequality. We define M such that L(y, y′) ≤M for any y, y′ ∈ Y . For any hypothesis h ∈ HKϵ and any δ > 0, the following generalization bound holds with at least probability 1-δ:
  LP (h, fP ) ≤ LQ̂K (h, fQ) + 2kµ
  n ∑ x′∈T d(x′,LK) + 2ϵ+ ηH + 2µRn(H) +
  √ M2 log( 1δ )
  2n (4)
  With d(x′,LK) = minx∈LK d(x ′, x) and d(x′, x) the distance from x to x′.
  Visual insights to understand Theorem 1 are presented in Figure 1 : the main idea is to approximate the maximal hypotheses h, h′ ∈ HKϵ returning the localized discrepancy by the k-Lipschitz envelope of the labeling function fQ, consistent with fQ on the labeled points, i.e. at most ϵ close to fQ on these points. Indeed, for any target point x′ ∈ T , the gap between h, h′ on x′ : L(h′(x′), h(x′)) is upper bounded by twice the distance from x′ to its closest labeled point times the Lipschitz constants of L, h and h′ plus the error on the labeled point : L(h′(x′), h(x′)) ≤ 2kµ d(x′,LK) + 2ϵ. The generalization bound of Theorem 1 highlights the trade-off that exists between the Lipschitz constant k of the hypothesis space H and the parameters ηH and ϵ. To reduce the term 2ϵ + ηH in order to obtain tighter controls over the target risk, one needs to consider a more complex set of hypothesis and thus to increase the Lipschitz constant k. Then, to benefit from the theoretical guarantees of this bound, a careful choice of hypothesis set have to be made (cf Section 4.3).
  The important benefit of the derived bound is to bring out the bounding criterion ∑
  x′∈T d(x ′,LK)
  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.
sections.heading: 3 DISCREPANCY-BASED ALGORITHM
sections.text: Theorem 1 directly implies that selecting the K queries minimizing ∑
  x′∈T d(x ′,LK) leads to
  minimize an upper bound of the target risk. We can thus propose an algorithm dedicated to active learning which provides theoretical guarantees on the target risk.
  Seeking the K queries minimizing ∑
  x′∈T d(x ′,LK) corresponds to solve a K-medoids problem
  (Kaufmann & Rousseeuw, 1987). Notice however that it does not consist of a K-medoids performed directly on the target domain as the source data are already labeled and considered as medoids. The presented algorithm only differs in the initialization process, where the distance between each target and its nearest source neighbour needs to be computed.
  Several algorithms exist to solve or 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 of the greedy algorithm (the amount of decrease of the criterion by selecting K points) is at least a (1− 1/e)-approximation of the optimal gain (cf Appendix). It 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 as between targets. Precisely, the greedy K-medoids algorithm presents a complexity of O(p(nm+ n2) +Kn2) and a memory usage of O(nm + n2) 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 of the K-medoids greedy algorithm with better scalability (Algorithm 1). 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 (m+ pn) log(m)2) with T the number of trees.
  2) Medoids initialization using the greedy algorithm on a random target batch of B samples with complexity O((K + p)B2). 3) An iterative algorithm on the model of (Park & Jun, 2009), combining assignment of each target point to its closest medoid (O(Kpn)) and medoid update inside each cluster. 4) The medoid update for each cluster is done through an original Branch-and-Bound algorithm (Land & Doig, 2010) which estimates the criterion by iteration over mini-batch, target points for which criterion is bigger than a statistical threshold are left aside. Thus, the number of pairwise
  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 is O(n3/2K−1/2) (the proof is given in the supplementary material).
  The overall complexity is thenO(T (m+ pn) log(m)2 + (K + p)B2 +Kpn+ pn3/2K−1/2) which provides reasonable computational time for moderately large data set (n,m ∼ 105 and p ∼ 103). Empirical comparison of computational time is also provided in the supplementary material.
  Algorithm 1 Accelerated K-medoids 1: {d(x′,S)}x′∈T ← KDT-Forest-Nearest-Neighbour(S, T ) # Compute distances to source 2: TK = {x∗i }i=1..K ← Kmedois-Greedy(T , B,K, {d(x′,S)}x′∈T ) # Initialize medoids 3: Ci ← {x′ ∈ T | d(x′, x∗i ) = min
  j=1..K d(x′, x∗j ) ∧ d(x′,S)} # Assign targets to closest cluster
  4: while any medoid x∗i can be updated do 5: for i from 1 to K do 6: x∗i = argmin
  x′∈Ci ∑ x′′∈Ci d(x′, x′′)← Branch-and-Bound(Ci) # Update medoid
  7: end for 8: For all x′ ∈ T , compute d(x′, x∗i ) for all updated medoids and reassign x′ to the closest Ci 9: end while
sections.heading: 4 RELATED WORK AND DISCUSSION
sections.heading: 4.1 RELATED WORK
sections.text: 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 a minimal query budget. Several metrics are used to measure the gap between distributions as the Transductive Rademacher Complexity (Gu & Han, 2012), the MMD (Wang & Ye, 2015; Kim et al., 2016; Viering et al., 2019) the Disagreement Coefficient (Hanneke, 2007; Balcan et al., 2009; Beygelzimer et al., 2009; Cortes et al., 2019a;b; 2020), theH-divergence (Sinha et al., 2019; Gissin & Shalev-Shwartz, 2019; Su et al., 2020) or the Wasserstein distance (Shui et al., 2020). To the best of our knowledge, only one 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 for active learning. Many active learning methods use a K-medoids algorithm as an heuristic measure of representativeness (Lin et al., 2009; Gomes & Krause, 2010; Wei et al., 2013; Iyer & Bilmes, 2013; Zheng et al., 2014). The K-medoids is in general computed on a 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., 2011; Deng et al., 2018; Su et al., 2020). These works use in general the output of a 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 (Valko 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.
sections.heading: 4.2 COMPARISON WITH EXISTING GENERALIZATION BOUNDS FOR ACTIVE LEARNING
sections.text: Some previous works on active learning also propose theoretical bound on the target risk. In this section, we will compare them with our derived bound of equation (4) in order to relate our
  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 = fP = fQ, f ∈ H and ϵ = 0. In this case, our bound is written:
  LP (h, f) ≤ (2kµ/n) ∑ x′∈T d(x′,LK) + 2µRn(H) + √ M2 log(1/δ)/2n (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 a regression loss L and under the previous assumptions, it controls the target risk as follows:
  LP (h, f) ≤ 2kµmax x′∈T
  d(x′,LK) + 2µRn(H) +O (√ M2 log(1/δ)/2n )
  (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 use greedy selection approximation. Thus, in some cases, the queries from K-centers may lead to a 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., 2020). An adaptation of this bound for the proposed scenario with the aforementioned assumptions could be written as follows:
  LP (h, f) ≤ 2kµW1(Q̂K , P̂ ) + 2µRn(H) +O (√ M2 log(1/δ)/2n )
  Where W1(Q̂K , P̂ ) = argminγ∈Γ ∑ x∼Q̂K ∑ x′∼P̂ γxx′d(x, x ′) with Γ = {γ ∈ Rn×(m+K) ; γ1 = 1 n1 ; γ T 1 = 1m+K 1}.
  Thus, in observing that d(x, x′) ≥ d(x′,LK) for any x′ ∈ T and x ∈ LK we can show that our presented bound of equation (5) is tighter than the one above.
sections.heading: 4.3 DISCUSSION ABOUT THE ASSUMPTIONS AND LIMITATIONS
sections.text: One crucial point of the present work is the setting of the ϵ parameter of the hypothesis set HKϵ . In practice, the parameter ϵ is determined by the hypothesis set and the training algorithm that the learner considers. For instance, if the learner uses over-parameterized hypotheses overfitted on the labeled data set, the parameter ϵ will be small because for any h, h(x) ≃ fQ(x) on LK . This could leads to ϵ < ηH 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 ηH is hard to estimate, choosing larger ϵ (by regularizing the hypotheses) is safer, but will lead to larger bounds.
  To deal with this difficulty, we use, in our experiments, a set of neural networks H regularized through weight clipping. The value of the clipping parameter is directly linked to the Lipschitz constant of H . By selecting an adequate clipping parameter and network architecture, we ensure that H is complex enough to learn the task on the source domain but sufficiently regularized to avoid over-fitting (and thus avoid ϵ < ηH ). For this purpose, we select the architecture and the clipping parameter through validation on the source labeled data.
  Regularity assumptions on the loss function L are essentially verified by norms as the Lp which are common losses for regression problems. However, they are are not verified by most classification losses. In fact, classification loss as the cross-entropy is bounded between 0 and 1 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-medoids (K-medoids+W). This algorithm performs the K-medoids algorithm with a weighted criterion. To compute the weights, we consider the Best-vs-Second-Best (BVSB) 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 the source data set. The Weighted K-medoids optimization can be written as follows:
  min TK ∑ x′∈T bvsb(x′) min x∈S∪TK d(x, x′) (7)
sections.heading: 5 EXPERIMENTS
sections.text: We choose to compare the performances of our algorithm to classical active learning methods on regression and classification problems in a 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 1. We use the open source code of the corresponding authors for BADGE (Ash et al., 2019) and the implementations from ADAPT2 (de Mathelin et al., 2021) for the domain adaptation methods.
sections.heading: 5.1 COMPETITORS
sections.text: We compare the proposed approach with the following query methods : Random Sampling; Kmeans (Hu et al., 2010); K-centers (Sener & Savarese, 2018); Diversity (Jain & Grauman, 2016); QBC (RayChaudhuri & Hamey, 1995); BVSB (Joshi et al., 2009); AADA (Su et al., 2020) : 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 et 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, 2010) : Transfer learning regression method based on a reverse boosting principle; Adversarial training : unsupervised features transformation on the model of DANN (Ganin et al., 2016).
  To make a 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 to 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-parameters (epochs, batch sizes...) is performed using only source labeled data. We assume that the architecture and the resulting hyper-parameters will still be appropriate after adding the queried target data to the training set (see Section 4.3). Finally, for distance-based algorithm, we consider the L1 distance computed in the penultimate layer of a network pre-trained on sources. We use an ensemble of 10 models in QBC and the greedy version of K-centers.
sections.heading: 5.2 SUPERCONDUCTIVITY DATA SET
sections.text: As there is very few public data sets for domain adaptation with regression tasks (Teshima et 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. The task consists in predicting their critical temperature.
  Experimental setup: The data set is divided in four domains following (Pardoe & Stone, 2010) : low (l), middle-low (ml), middle-high (mh) and high (h) of around 4000 instances and 166 features. We use a learning rate of 0.001, a number of epochs of 100, a batch size of 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 1. We present the MAE evolution for the adaptation from mh to h in Figure 2.
  Results: We observe on Figure 2 that, for any K > 0, the K-medoids algorithm presents the lowest MAE on the target data for the three different training methods. In particular we observe a 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 1 where we observe that K-medoids presents the lowest MAE in 11 experiments over 12. We
  1https://github.com/antoinedemathelin/dbal 2https://github.com/adapt-python/adapt
  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 it takes into account the distance to source points and then queries less redundant information.
sections.heading: 5.3 OFFICE DATA SET
sections.text: The office data set (Saenko et al., 2010) consists in pictures of office items coming from different domains: amazon or webcam. The task is a multi-classification problem with 31 classes (chairs, printers, ...). The goal is to use data from the amazon domain where labels are easily available to learn a 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., 2016) pretrained on ImageNet. We vary K from 5 to 300, repeating each experiment 8 times. The learning rate is 0.001, the number of epochs 60 and the batch size 128.
  Results: Figure 3.A presents the results obtained. We observe that the K-medoids+W algorithm provides the best performances for almost any K and in particular for small values of K. We then present the visualization of the two first components of the PCA transform on Figure 4. We observe that the K-medoids+W 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 are less representative of the the target distribution.
sections.heading: 5.4 DIGITS DATA SET
sections.text: We consider the experiment proposed in (Ganin et al., 2016) where a synthetic digits data set: SYNTH is used to learn a classification task for a data set of real digits pictures: SVHN (Street-View House Number) (Netzer et al., 2011). Both data sets are composed of around 65k images of size 28× 28.
  Experimental setup: To handle the large number of data, we use the accelerated K-medoids algorithm (Algorithm 1) with T = 50 trees and a initial batch size of B = 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 a 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, a Balance Weighting training is performed with the source and target labeled data using the same optimization hyper-parameters than before. Experiments are conducted 8 times for K between 10 and 500.
  Results: Figure 3.B and 3.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+W provides improved results over other query strategies in both cases. This highlights the ability of the method to select informative target points in a variety of scenarios.
sections.heading: 6 CONCLUSION AND FUTURE WORK
sections.text: This work introduces a novel active learning approach based on a 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 to relevant features with respect to the task.
  REPRODUCIBILITY STATEMENT
  To help the reproducibility of the results presented in this work, the source code of the experiments is available at https://github.com/antoinedemathelin/dbal.
  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, notebooks are provided in the repository to enable a rapid access to the methods and the possibility to try for different hyper-parameters.
sections.heading: ACKNOWLEDGMENTS
sections.text: Part of this research was funded by the Manufacture Française des Pneumatiques Michelin and the Industrial Data Analytics and Machine Learning chair of Centre Borelli from ENS Paris Saclay.
sections.heading: A PROOF OF PROPOSITION 1
sections.text: Proposition 1. Let K > 0 be the number of queries and H a hypothesis space. Let P̂ and Q̂K be the empirical distributions of the respective sets T and LK = S ∪ TK of respective size n and m+K. We assume that L is a symmetric, µ-Lipschitz and bounded loss function verifying the triangular inequality. We denote by M the bound of L. Let ηH be the ideal maximal error on S ∪ T :
  ηH ∆ = min
  h∈H max x∈S∪T [L(h(x), fQ(x)) + L(h(x), fP (x))] (8)
  Then, for any ϵ ≥ ηH , any hypothesis h ∈ HKϵ and any δ > 0, the following generalization bound holds with at least probability 1-δ:
  LP (h, fP ) ≤ LQ̂K (h, fQ) + discHKϵ (Q̂K , P̂ ) + ηH + 2µRn(H) +M √ log( 1δ ) 2n  . (9) Proof. Let’s consider h ∈ H . According to (Mohri et al., 2018) we have for any δ > 0, with probability at least 1− δ:
  LP (h, fP ) ≤ LP̂ (h, fP ) + 2µRn(H) +M √ log( 1δ ) 2n . (10)
  Besides, we have for any h, h0 ∈ HKϵ :
  LP̂ (h, fP ) = LQ̂K (h, fQ) + LP̂ (h, fP )− LQ̂K (h, fQ) ≤ LQ̂K (h, fQ) + LP̂ (h, h0) + LP̂ (h0, fP )− LQ̂K (h, h0) + LQ̂K (h0, fQ) ≤ LQ̂K (h, fQ) + maxh,h′∈HKϵ |LP̂ (h, h ′)− LQ̂K (h, h ′)|+ LP̂ (h0, fP ) + LQ̂K (h0, fQ)
  (11)
  As the inequality is true for any h0 ∈ HKϵ , we have in particular:
  LP̂ (h, fP ) ≤ LQ̂K (h, fQ) + maxh,h′∈HKϵ |LP̂ (h, h ′)− LQ̂K (h, h ′)|+ min h0∈HKϵ
  ( LP̂ (h0, fP ) + LQ̂K (h0, fQ) ) (12)
  We notice that, for any h0 ∈ HKϵ :
  LP̂ (h0, fP ) + LQ̂K (h0, fQ) ≤ maxx∈S∪T [L(h0(x), fQ(x)) + L(h0(x), fP (x))] (13)
  From which we deduce that,
  min h0∈HKϵ
  ( LP̂ (h0, f) + LQ̂K (h0, f) ) ≤ ηHKϵ (14)
  Let’s now consider h∗ ∈ H , such that:
  h∗ = argmin h∈H max x∈S∪T [L(h(x), fQ(x)) + L(h(x), fP (x))] (15)
  By assumption we have ηH ≤ ϵ, and thus:
  max x∈S∪T
  [L(h∗(x), fQ(x)) + L(h ∗(x), fP (x))] ≤ ϵ (16)
  This implies that for any x ∈ S ∪ T :
  L(h∗(x), fQ(x)) ≤ ϵ (17)
  In particular, L(h∗(x), fQ(x)) ≤ ϵ for any x ∈ LK , which implies that h∗ is in HKϵ . We then deduce that:
  ηH = ηHKϵ (18)
  Thus we conclude that for any h ∈ HKϵ and any δ > 0, we have with probability at least 1− δ:
  LP (h, fP ) ≤ LQ̂K (h, fQ) + discHKϵ (Q̂K , P̂ ) + ηH + 2µRn(H) +M √ log( 1δ ) 2n  . (19)
sections.heading: B PROOF OF THEOREM 1
sections.text: Theorem 1. Let K > 0 be the number of queries, H a hypothesis space of k-Lipschitz functions and ϵ ≥ ηH . Let LK = S ∪ TK be the labeled set and T the target set drawn according to P . We assume that L is a symmetric, µ-Lipschitz and bounded loss function verifying the triangular inequality. We denote by M the bound of L. For any hypothesis h ∈ HKϵ and any δ > 0, the following generalization bound holds with at least probability 1-δ:
  LP (h, f) ≤ LQ̂K (h, fQ) + 2kµ
  n ∑ x′∈T d(x′,LK) + 2ϵ+ ηH + 2µRn(H) +
  √ M2 log( 1δ )
  2n (20)
  With d(x′,LK) = minx∈LK d(x ′, x)
  Proof. Let ϵ ≥ ηH and 0 ≤ K ≤ n. For all h, h′ ∈ HKϵ , for all x′ ∈ T and for all x ∈ LK we have:
  L(h(x′), h′(x′)) ≤ L(h(x′), h(x)) + L(h(x), h′(x)) + L(h′(x), h′(x′)) ≤ L(h(x′), h(x)) + L(h′(x), h′(x′)) + L(h(x), fQ(x)) + L(fQ(x), h′(x)) ≤ µ (|h(x)− h(x′)|+ |h′(x)− h′(x′)|) + 2ϵ ≤ 2kµ d(x′, x) + 2ϵ
  (21)
  The two first inequalities come from the triangular inequality, the others from the lipschitzness of h, h′ and definition of HKϵ .
  As the above inequality is true for any x ∈ LK , we have in particular for any x′ ∈ T :
  L(h(x′), h′(x′)) ≤ 2kµ min x∈LK d(x, x′) + 2ϵ
  = 2kµ d(x′,LK) + 2ϵ (22)
  Leading to:
  LP̂ (h(x ′), h′(x′)) ≤ 2kµ
  n ∑ x′∈T d(x′,LK) + 2ϵ (23)
  We then deduce the following, for all h, h′ ∈ HKϵ :
  discHKϵ (Q̂K , P̂ ) = maxh,h′∈HKϵ |LP̂ (h, h ′)− LQ̂K (h, h ′)|
  ≤ max [
  max h,h′∈HKϵ
  LP̂ (h, h ′), max h,h′∈HKϵ LQ̂K (h, h ′) ] ≤ max [ 2kµ
  n ∑ x′∈T d(x′,LK) + 2ϵ, 2ϵ
  ]
  ≤ 2kµ n ∑ x′∈T d(x′,LK) + 2ϵ
  (24)
  Finally, according to Proposition 1, we have for all h, h′ ∈ HKϵ :
  LP (h, f) ≤ LQ̂K (h, fQ) + 2kµ
  n ∑ x′∈T d(x′,LK) + 2ϵ+ ηH + 2µRn(H) +
  √ M2 log( 1δ )
  2n (25)
sections.heading: C APPROXIMATION ERROR BETWEEN PROPOSITION 1 AND THEOREM 1
sections.text: We present in this section the approximation error of the relaxation between the bounds of Proposition 1 and Theorem 1.
  We will show that, with the assumption of Theorem 1 and in the case L = L1, we have, for any labeled set LK :
  2k
  n ∑ x′∈T d(x′,LK) ≤ k k − kf discHKϵ (Q̂K , P̂ ) (26)
  With kf the Lipschitz constant of the source labeling function fQ. We assume that k > kf .
  For this purpose we will look for two hypotheses h, h′ ∈ HKϵ verifying:
  LP̂ (h, h ′) ≥ 2(k − kf )
  n
  ∑ x′∈T d(x′,LK) (27)
  Let’s define k′ = k − kf , and h, h′ : X → Y such that, for any x ∈ X :
  h(x) = fQ(x) + k ′ min x̃∈LK d(x, x̃) = fQ(x) + k ′d(x,LK)
  h′(x) = fQ(x)− k′ min x̃∈LK
  d(x, x̃) = fQ(x)− k′d(x,LK) (28)
  We will now prove that h, h′ are in HKϵ :
  Let’s consider x1, x2 ∈ X , we define:
  x̃1 = argmin x̃∈LK d(x̃, x1)
  x̃2 = argmin x̃∈LK
  d(x̃, x2) (29)
  Assuming without restriction that d(x1, x̃1) > d(x2, x̃2), we have:
  |h(x1)− h(x2)| ≤ k′ |d(x1,LK)− d(x2,LK)|+ kf d(x1, x2) ≤ k′ (d(x1, x̃1)− d(x2, x̃2)) + kf d(x1, x2) ≤ k′ (d(x1, x̃2)− d(x2, x̃2)) + kf d(x1, x2) ≤ k′ d(x1, x2) + kf d(x1, x2) ≤ k d(x1, x2)
  (30)
  Using the triangular inequality and the fact that d(x1, x̃1) ≤ d(x1, x̃2) by definition of x̃1. Using a similar development we can prove the k-Lipschitzness of h′.
  Let’s now consider x ∈ LK , we have
  L(h(x), fQ(x)) = L(fQ(x) + k ′d(x,LK), fQ(x))
  = L(fQ(x), fQ(x))
  = 0
  (31)
  In the same way L(h′(x), fQ(x)) = 0 and we have h, h′ ∈ HKϵ .
  Furthermore, we have:
  LP̂ (h, h ′) =
  1
  n ∑ x′∈T L(h(x′), h′(x′))
  = 1
  n ∑ x′∈T |h(x′)− h′(x′)|
  = 2(k − kf )
  n
  ∑ x′∈T d(x′,LK)
  (32)
  Thus,
  discHKϵ (Q̂K , P̂ ) ≥ |LP̂ (h, h ′)− 0| = 2(k − kf )
  n
  ∑ x′∈T d(x′,LK) (33)
  From which we conclude.
sections.heading: D COMPARISON WITH OTHER ACTIVE LEARNING BOUNDS (CF SECTION 4.2)
sections.text: In this section we assume that f = fP = fQ and f ∈ H with H a set of k-Lipschitz functions.
  D.1 K-CENTER BOUNDS
  Sener and Savarese (Sener & Savarese, 2018) propose the following generalization bounds for ϵ = 0 and h ∈ HKϵ :
  LP̂ (h, f) ≤ δ(λ l +MCλµ) +M √ log( 1δ ) 2n  (34) which leads to:
  LP (h, f) ≤ δ(λl +MCλµ) + 2µRn(H) + 2M √ log( 1δ ) 2n  (35) With δ = maxx′∈T d(x′,LK), C the class number and λµ the Lipschitz constant of a class-specific regression function. λl is the Lipschitz constant of the loss function l verifying l : (x, h) → l(x, f(x), h) = L(h(x), f(x)).
  If we consider a regression problem, we can drop the term corresponding to the class-specific function and we have:
  LP (h, f) ≤ δλl + 2µRn(H) +O √M2 log( 1δ ) 2n  (36) Let’s now consider h ∈ H and x, x′ ∈ X , we have for k-Lipschitz f :
  |l(x, f(x), h)− l(x′, f(x′), h)| = |L(h(x), f(x))− L(h(x′), f(x′))| ≤ |L(h(x), f(x))− L(h(x′), f(x))|+ |L(h(x′), f(x))− L(h(x′), f(x′))| ≤ L(h(x), h(x′)) + L(f(x), f(x′)) ≤ µ|h(x)− h(x′)|+ µ|f(x)− f(x′)| ≤ 2µk|x− x′|
  (37)
  The two first inequalities are obtained with triangular inequalities, then we use Lipschitz assumptions on h, f and L.
  Thus, we have λl = 2µk from which we deduce:
  LP (h, f) ≤ 2kµmax x′∈T d(x′,LK) + 2µRn(H) +O √M2 log( 1δ ) 2n  (38) D.2 WASSERSTEIN BOUNDS
  To adapt the bound from (Shui et al., 2020) Corollary 1 to our setting, we identify the distributions D̂ and Q̂ from Shui et al. (2020) with respectively the distributions P̂ and Q̂K . We then have the following generalization bound:
  LP (h, f) ≤ LQ̂K (h, f) + 2µkW1(Q̂K , P̂ ) + 2µRn(H) +O √M2 log( 1δ ) 2n  (39) Notice that the term corresponding to the labeling function ”decay property” in the bound of Shui et al. (2020) is null when considering a Lipschitz labeling function (f ∈ H). Thus for ϵ = 0 and for any h ∈ HKϵ , we have:
  LP (h, f) ≤ 2kµW1(Q̂K , P̂ ) + 2µRn(H) +O √M2 log( 1δ ) 2n  = 2kµ
  ∑ x′∈T ∑ x∈LK γ∗x′x d(x ′, x) + 2µRn(H) +O √M2 log( 1δ ) 2n  (40)
  With γ∗ = argminγ∈Γ ∑ x′∈T ∑ x∈LK γx′xd(x ′, x) and Γ = {γ ∈ Rn×(m+K) ; γ1 = 1n1 ; γ
  T 1 = 1
  m+K 1}.
  Thus, in observing that:∑ x′∈T ∑ x∈LK γx′xd(x ′, x) ≥ ∑ x′∈T ∑ x∈LK γx′x min x∈LK d(x′, x)
  ≥ ∑ x′∈T d(x′,LK) ∑ x∈LK γx′x
  ≥ 1 n ∑ x′∈T d(x′,LK)
  We deduce that our presented bound of Theorem 1 is also tighter than the one proposed in (Shui et al., 2020) in the case of ϵ = 0 and k-Lipschitz f and h.
sections.heading: E ALGORITHMS (CF SECTION 3)
sections.text: E.1 K-MEDOIDS
  Algorithm 2 K-Medoids Greedy 1: Input: T , B, K, S, {d(x′,S)}x′∈T ) 2: Output: TK = {xj}j≤K ⊂ T 3: T ← {x′s1 , ..., x ′ sB} with {x ′ s1 , ..., x ′ sB} picked randomly in T without replacement.
  4: Initialize query subset: T0 = {} 5: For all x′ ∈ T , d x′ = d(x′,S) = minx∈S d(x′, x) 6: For all x, x′ ∈ T compute d xx′ = d(x, x′) 7: for i from 1 to K do 8: xi ← argminx∈T ∑ x′∈T min ( d xx ′ , d x ′ )
  9: Si ← Si−1 ∪ {xi} 10: For all x′ ∈ T , update d x′ = min(d x′ , d xix′)) 11: end for
  Algorithm 3 Branch & Bound Medoid (B & B) 1: Input: Cluster C ∈ Rnc×p, previous medoid criterion C∗, batch size B 2: Output: New medoid x∗
  3: Initialize candidates C̃ = C 4: Initialize computed distance set Dx = {} for all x ∈ C̃. 5: Initialize criterion Cx = 0 and standard deviation σx = 0 for all x ∈ C̃. 6: Initialize threshold t = C∗ 7: for i from 1 to nc/B do 8: Ci = {xj ∈ C ; (B − 1)i ≤ j ≤ Bi} 9: for x ∈ C̃ do
  10: Dx ← Dx ∪ {d(x, x′) ; x′ ∈ Ci} 11: Cx ← 1Bi ∑ d∈Dx d
  12: σx ← √ 1 Bi ∑ d∈Dx(d− Cx) 2 13: end for 14: x∗ ← argminx∈C̃ Cx 15: t← min(t, Cx∗ + 2σx∗√Bi )
  16: C̃ ← { x ∈ C̃ ; Cx − 2σx√Bi < t } 17: end for 18: x∗ ← argminx∈C̃ 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− 1/e)-approximation of the optimal gain.
  Let TK 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 :
  gain(TK) = ∑ x′∈T d(x′,S)− ∑ x′∈T d(x′,S ∪ TK) (41)
  With d(x′,S) = minx∈S d(x′, x)
  We will prove now that the gain is monotone submodular.
  Let A ⊂ B ⊂ T and x ∈ T \B, We denote T A = {x′ ∈ T ; d(x′, x) < d(x′, A)} and T B = {x′ ∈ T ; d(x′, x) < d(x′, B)}. As A ⊂ B, we have d(x′, A) ≥ d(x′, B) for any x′ ∈ T . Thus,
  T B ⊂ T A (42)
  Besides, for any x′ ∈ T ,
  d(x′, A)− d(x′, x) ≥ d(x′, B)− d(x′, x) (43)
  We deduce then that,
  gain(A ∪ {x})− gain(A) = ∑
  x′∈T A d(x′, A)− d(x′, x)
  ≥ ∑
  x′∈T B d(x′, A)− d(x′, x)
  ≥ ∑
  x′∈T B d(x′, B)− d(x′, x)
  = gain(B ∪ {x})− gain(B)
  (44)
  Then, the gain is submodular.
  Besides, as A ⊂ B it appears clearly that,
  gain(A) ⊂ gain(B) (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 of the optimal gain.
  E.3 COMPLEXITY COMPUTATION
  In the following, a 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, at each root, at the median of a random feature until the leaf-sizes are∼ log(m). The median computation for each root with mr data is in O(mr log(mr)). Thus the overall complexity to build one tree is O( ∑M i=0 2 −im log(2−im)2i) = O(m log(m) ∑M
  i=0 1) with M ∼ log(m/ log(m)) which becomes O(m log(m)2). Then, each target is assigned to a leaf by performing O(log(m)) computations, inside the assigned leaf all distance computations are done in O(p log(m)). Thus an approximate nearest neighbour is given for all targets with a complexity O(T (m+ pn) log(m)2).
  2. Medoids Initialization: Using the greedy algorithm, O(pB2) distance computations are first done, then, for all targets, a sum over the target data is computed at each of the K steps. Thus the complexity is O((K + p)B2).
  3. Assignation to the Closest Medoid: The distance between all target and the medoids is computed in O(Kpn).
  4. Branch & Bound Medoid Computation B & B algorithm (Algorithm 3) takes as input one cluster C of nc unlabeled data from T . It also takes a batch size B and the previous cluster medoid criterion C∗ which is used as
  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.e we consider that C∗ = +∞. Besides, to use notations consistent with the common notations in statistics, we will denote the batch size B by n (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 ⊂ T with nc data. We consider the uniform norm as underlying distance d, defined for all xi, xj ∈ C as d(xi, xj) = max ( |x(1)i − x (1) j |, ..., |x (p) i − x (p) j | ) with xi = (x (1) i , ..., x (p) i ) ∈ Rp.
  Computing the complexity of the B & B algorithm for any distribution of the xi would be too difficult. We make here the simplifying assumption that the xi in C are uniformly distributed on the hyper-cube C of edge size 2 and centered on x∗ = (0, ..., 0) ∈ Rp We define for any i ∈ [|1, nc|] and any j ∈ [|1, nc|], the variables Zij = d(xi, xj). We also define Z∗j = d(x
  ∗, xj) for any j ∈ [|1, nc|]. We suppose that for any i ∈ [|1, nc|], Zi1, ..., Z i nc are iid and that for any j ∈ [|1, nc|] the Z i j are independents. We define, for any
  i ∈ [|1, nc|], the mean µi = E[Zi0] = 12p ∫ x∈C d(xi, x) and the variance σ 2 i = Var[Z i 0] =
  1 2p ∫ x∈C(d(xi, x)−µi)
  2. We consider a first batch of distance computations of size n < nC . We define for any i ∈ [|1, nc|] the empirical mean µ̂i = 1n ∑n j=1 Z i j and the empirical variance σ̂2i = 1 n−1 ∑n j=1(Z i j − µ̂i)2. We denote by µ∗ and σ∗ 2 the mean and variance of Z∗0 and µ̂ ∗ and σ̂∗ 2
  their respective empirical estimator. We first observe that µi and σi are finite for any i ∈ [|1, nc|] as the xi are uniformly distributed on the hyper-cube centered in x∗ ∈ C. We also notice that Zij ∈ [0, 2] for any i, j ∈ [|1, nc|]. Preliminary results: We make the assumption that p >> 1. We aim at giving bounds for any µi and σi. We admit the intuitive results that for any xi = (x (1) i , ..., x (p) i ) ∈ C and for any j ∈ [|1, nc|], µi ≥ µj→0i and σi ≥ σ j→0 i with µ j→0 i and σ j→0 i the mean and variance of the variable d(xj→0i , .) with x j→0 i = (x (1) i , ..., x (j−1) i , 0, x (j+1) i , ..., x (p) i ). We consider indeed that the more xi is close to the center of the hyper-cube smaller is µi and σi. Considering this fact, we have, for any i ∈ [|1, nc|]:
  µ∗ ≤ µi (46) σ∗ ≤ σi (47)
  Besides, for any 0 ≤ r ≤ 1 the sample density in the elementary surface between the balls centered on x∗ and of respective radius r + dr and r is prp−1dr. Thus, we can notice that Z∗0 follows a beta distribution of parameters α = p and β = 1, from which we deduce that:
  µ∗ = p
  p+ 1 (48)
  σ∗2 = p
  (p+ 1)2(p+ 2) (49)
  We further notice that for any 0 ≤ a ≤ 1 and for any i ∈ [|1, nc|] such that d(x∗, xi) = a we have µi ≥ µa with µa the criterion of the sample xa = (a, 0, ..., 0) ∈ Rp. To compute µa = 12p ∫ x∈C d(xa, x), we split the integral on three parts: d(xa, x) ≤ 1− a, 1− a ≤ d(xa, x) ≤ 1 and 1 ≤ d(xa, x) ≤ 1 + a:
  µa = ∫ 1−a r=0 prp−1dr + 1 2 ∫ 1 r=1−a ( prp−1 + (p− 1)(1− a)rp−2 ) dr + 1 2 ∫ 1+a 1 rdr
  = p p+ 1 (1− a)p+1 + 1 2
  [ p
  p+ 1 + (1− a)p− 1 p − (1− a)p+1
  ( p
  p+ 1 + p− 1 p
  )] + a
  2
  ( 1 + a
  2 ) ≃ 1− a
  2 +
  a
  2
  ( 1 + a
  2 ) ≃ 1 + a 2
  4 (50)
  Using the simplifying approximation pp+1 ≃ p−1 p ≃ 1 for p >> 1. Thus for any 0 ≤ a ≤ 1 and for any i ∈ [|1, nc|] such that d(x∗, xi) = a we have:
  µi ≥ 1 + a2
  4 (51)
  An upper bound of the σ2i is given by the variance σ 2 c of the variable d(xc, .) with xc = (1, ..., 1) which corresponds to one corner of the hyper-cube C:
  σ2c = 1
  2p ∫ 2 0 prp+1dr − ( 1 2p ∫ 2 0 prpdr )2
  = 4 p
  p+ 2 + 4
  ( p
  p+ 1 )2 = 4 p
  (p+ 1)2(p+ 2)
  = 4σ∗2
  (52)
  From which we deduce that for any i ∈ [|1, nc|]:
  σ∗ ≤ σi ≤ 2σ∗ (53)
  To simplify the calculations, we make the approximation σ̂i ≃ σi for any i ∈ [|1, nc|], which is relevant for sufficiently large n as E[Zi0 4 ] < +∞. Probability of rejecting all optimal medoid candidates: Let ϵ > 0 be an approximation factor of µ∗. The goal of the Branch & Bound algorithm is to identify one sample xi ∈ C such that µi ≤ µ∗(1 + ϵ) with less distance computations as possible. The process consists in removing all candidates xi such that µ̂i− 2σ̂i√n > µ̂i∗ + 2σ̂i∗√ n
  with µ̂i∗ the current minimal empirical mean. We aim now at computing the probability of rejecting all optimal medoid candidates xi verifying µi ≤ µ∗(1 + ϵ) during the B & B process. For this, we define Bϵ(µ∗) = {i ∈ [|1, nc|] ; µi ≤ µ∗(1 + ϵ)} the index set of optimal medoid candidates and Bcϵ(µ∗) = {i ∈ [|1, nc|] ; µi > µ∗(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 two following probabilities:
  P1 = P ({ ∃i ∈ Bcϵ(µ∗) ; µ̂i +
  4σ∗√ n ≤ µ∗(1 + ϵ/4)
  }) (54)
  P2 = P ({∃i ∈ Bϵ(µ∗) ; µ̂i ≤ µ∗(1 + ϵ/4)}) (55)
  We can observe that the probability of rejecting all optimal medoid candidates is upper bounded by: (1 − P2) + P2P1 considering the approximation σ̂i ≃ σi and the fact that σi ≥ σ∗ for any i ∈ [|1, nc|]. We now define, for i ∈ Bcϵ(µ∗):
  Pi = P ({ µ̂i +
  4σ∗√ n ≤ µ∗(1 + ϵ/4)
  }) (56)
  Leading to:
  Pi = P ({ µ̂i +
  4σ∗√ n − ϵµ ∗ 4 ≤ µ∗
  }) (57)
  On the other hand, according to the Bennett’s inequality from (Maurer & Pontil, 2009; Hoeffding, 1994) we have, for any i ∈ Bcϵ(µ∗) and for any δ > 0:
  P ( µ̂i/2 + √ σ2i log(1/δ)
  2n +
  log(1/δ)
  3n ≤ µi/2
  ) ≤ δ (58)
  Notice that we apply the inequality to the Zij/2. Then, considering the fact that σi ≤ 2σ∗ and that µi > µ∗(1 + ϵ) we have:
  P ( µ̂i + √ 2σ∗√ n √ log(1/δ) + 2 log(1/δ) 3n ≤ µ∗(1 + ϵ) ) ≤ δ (59)
  Leading to:
  P ( µ̂i + √ 2σ∗√ n √ log(1/δ)− ϵµ∗ + 2 log(1/δ) 3n ≤ µ∗ ) ≤ δ (60)
  Let’s consider δ > 0 such that the following equality holds: √ 2σ∗√ n √ log(1/δ)− ϵµ∗ + 2 log(1/δ) 3n = 4σ∗√ n − ϵµ ∗ 4 (61)
  Thus:
  u2 +Au = B (62)
  With:
  u = √ log(1/δ) (63)
  A = 3
  2
  √ 2nσ∗ (64)
  B = 3n
  2 ( 4σ∗√ n + 3ϵµ∗ 4 ) (65)
  (66)
  We then set:
  δ = exp ( − ( ∆−A
  2
  )2) (67)
  ∆ = √ A2 + 4B (68)
  We have for the δ defines above and for any i ∈ Bcϵ(µ∗): Pi ≤ δ (69)
  Thus, the probability P1 can be upper bounded as follows:
  P1 ≤ 1− (1− δ)nc (70) Considering the fact that |Bcϵ(µ∗)| < nc. 1− (1− δ)nc is the probability of getting at least one success for the binomial law of parameters (nc, δ). We are now looking for an upper bound of P2. We observe that, at least the index i such that xi = x
  ∗ is in Bϵ(µ∗). Besides, as x∗ is the center of the hyper-cube, Z∗j is in [0, 1] for any j ∈ [|1, nc|]. We can then apply the Bennett’s inequality to the Z∗j , and for any γ > 0 we have:
  P ( µ̂∗ ≤ µ∗ + √ 2σ∗2 log(1/δ)
  n +
  log(1/δ)
  3n
  ) ≥ 1− γ (71)
  We set:
  γ = exp −(√C2 + 4D − C 2 )2 (72) C = 3 √ 2nσ∗ (73)
  D = 3n ϵµ∗
  4 (74)
  We then have:
  P2 ≥ P ( µ̂∗ ≤ µ∗(1 + ϵ 4 ) ) ≥ 1− γ (75)
  Leading to:
  1− P2 ≤ γ (76)
  Finally the probability of rejecting all optimal candidates is upper bounded by 1 − (1 − δ)nc + γ. To give an order of magnitude of this probability, we consider the scenario where nc = 105, p = 100, n = √ nc and ϵ = 0.05. Then we have: δ ≃ 3.6 10−8 and γ ≃ 7.7 10−5, which leads to a probability of rejection around 3.6 10−3. Thus, in this case, there is at least a probability 0.995 that B & B returns a medoid candidate with a 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 xi kept at each batch. An upper bound of this number is given by the number of xi verifying µ̂i ≤ µ∗(1+ ϵ/4)+ 8σ ∗ √ n
  . We further assume that the previous upper bound can be approximated by the number of xi verifying µi ≤ µ∗(1 + ϵ/4) + 8σ ∗ √ n We have shown in the preliminary results that for any i ∈ [|1, nc|], µi ≥ 1 + a 2
  4 with a = d(xi, x
  ∗). Thus an upper bound of the number of candidates xi kept after the first batch is given by the number of xi in the ball of radius a with a verifying:
  a = 2 √ ϵ/4 +
  8σ∗√ n
  (77)
  Using the approximation µ∗ = pp+1 ≃ 1. Besides, as σ ∗ = O (1/p) we can suppose that for sufficiently large p and large n, 8σ ∗
  √ n ≤ 34ϵ (For instance with nc, n, p and ϵ considered
  previously, we have 8σ ∗
  √ n ≃ 0.005 and 34ϵ ≃ 0.03). Thus:
  a ≤ 2 √ ϵ (78)
  Finally the number of candidates kept after the first batch is in O ( nc ϵ p/2 )
  which is very small (for the values of nc, p and ϵ considered previously, we have nc ϵp/2 ≃ 10−60). If we consider a batch size of O (√ nc ) , the number of distance computations after the first batch
  is negligible behind O ( nc √ nc ) .
  We then conclude that the complexity of a medoid computation in one cluster is in O ( p nc √ nc )
  as each of the K cluster has approximately nc ≃ n/K samples (with n the sample size of T ), the overall complexity of B & B is in O ( p n3/2K−1/2 ) .
sections.heading: F EMPIRICAL COMPLEXITIES
sections.text: 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 on a (2.7GHz, 16G RAM) computer using Python 3.8. The scikit-learn (Pedregosa et al., 2011) implementation of the pairwise euclidean distance is used. No parallel computing is performed.
  The parameters are set to K = 100, T = 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 d. The results are reported on Figure 5. 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 5 that the K-medoids Greedy algorithm encounters computational burden for samples larger than 10k instances. For n = m = 60k, the K-centers algorithm encounters
  a similar issue due to 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 a factor of 5. We also notice that the accelerated K-medoids algorithm has similar complexity performance to K-medoids for n,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 an acceptable level. For n,m = 60k the complexities of the accelerated K-medoids and the K-centers + KD-Trees are almost similar but with a level of performance in favor of the accelerated K-medoids (see Section 5.4).
  We also present the evolution of the objective function of the different algorithm in function of the number of queries K for n = m = 60k (cf Figure 6).
  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 Kmedoids Accelerated.
sections.heading: G EXPERIMENTS
sections.text: G.1 SUPERCONDUCTIVITY
  Setup The UCI data set ”Superconductivity” (Hamidieh, 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 of features: some features correspond to the chemical element number’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 use the setup of (Pardoe & Stone, 2010) to 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 to this feature and split it in four parts: low (l), middle-low (ml), middle-high (mh), high (h). Each part defining a domain with around 4000 instances and 166 features. The considered feature is 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 is performed on features corresponding to the chemical element number’s. A visualization of the first components of the PCA as well as the output distribution is provided in Figure 7).
  Standard deviation Table 2 presents the standard deviation of the MAEs obtained on the 8 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 a distribution matching perspective, i.e. it produces a training set with a distribution close to the one of the testing set (cf Section 2). This can explain why the training is more stable with the training set provided by K-medoids.
  (high to low) analysis An interesting fact to notice in the results of the superconductivity experiments (for which a recap is given in Table 3) is 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.
  It first appears, in Figure 8, that this difference in performance for the low-to-high experiment compared to 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 two modes, one in the low and the other in the high temperature. Thus, the model trained with the low domain data will generalize better to 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 in the low domain that are queried (see Figure 9). It appears that K-medoids and Random query more of this type of data, as they are highly concentrated and relatively far from the sources (see Figure 10, 11).
  G.2 OFFICE
  G.3 DIGITS