Victor Bouvier
email: vbouvier@sidetrade.com

Philippe Very
email: philippe.very@lend-rxtech.com

Clément Chastagnol
email: clement.chastagnol@alan.eu

Myriam Tami

Céline Hudelot

Stochastic Adversarial Gradient Embedding for Active Domain Adaptation

come   L'archive ouverte pluridisciplinaire

Introduction

When provided with a large amount of labelled data, deep neural networks have dramatically improved the state-ofthe-art for both vision [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and language tasks [START_REF] Vaswani | Attention is all you need[END_REF]). However, deploying machine learning models for real-world applications requires to generalize on data which may slightly differ with the training data [START_REF] Amodei | Concrete problems in AI safety[END_REF][START_REF] Marcus | The Next Decade in AI: Four Steps Towards Robust Artificial Intelligence[END_REF]. Quite surprisingly, deep models do not meet this requirement and often show a weak ability to generalize out of the training distribution [START_REF] Beery | Recognition in terra incognita[END_REF][START_REF] Geva | Are We Modeling the Task or the Annotator? An Investigation of Annotator Bias in Natural Language Understanding Datasets[END_REF][START_REF] Arjovsky | Invariant Risk Minimization[END_REF].

Deep nets can learn data transferable representations to new tasks or new domains if some labelled data from the new distribution are available [START_REF] Oquab | Learning and transferring mid-level image representations using convolutional neural networks[END_REF][START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF]. Acquiring a sufficient amount of labeled Preprint.

data is laborious, and large scale annotation is often costprohibitive. Unlabelled data are much more convenient to obtain. This observation has motivated the field of Unsupervised Domain Adaptation [START_REF] Pan | A survey on transfer learning[END_REF][START_REF] Quionero-Candela | Dataset shift in machine learning[END_REF] for bridging the gap between a labelled source domain and an unlabelled target domain.

Learning domain Invariant Representations has led to significant progress towards learning domain transferable representations with deep neural networks [START_REF] Ganin | Unsupervised Domain Adaptation by Backpropagation[END_REF][START_REF] Long | Learning transferable features with deep adaptation networks[END_REF][START_REF] Long | Conditional adversarial domain adaptation[END_REF]. By fooling a discriminator trained to separate the source from the target domain, the feature extractor removes domain-specific information in representations [START_REF] Ganin | Unsupervised Domain Adaptation by Backpropagation[END_REF]. Therefore, a classifier trained from those representations with source labelled data is expected to perform reasonably well in the target domain [START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF], 2010).

However, those methods perform significantly worse than their fully supervised counterparts. Practical applications often offer the possibility of annotating a fixed budget of target data; a paradigm referred to as Active Learning (AL). Despite its great practical interest, there are, to our knowledge, only a few previous works which address the problem of Active Domain Adaptation (ADA) [START_REF] Chattopadhyay | Joint transfer and batch-mode active learning[END_REF][START_REF] Rai | Domain adaptation meets active learning[END_REF][START_REF] Saha | Active supervised domain adaptation[END_REF][START_REF] Su | Active adversarial domain adaptation[END_REF]. In particular, the work of Su et al., proposed recently, is the first that brings active learning to domain adversarial learning.

Our insight is to reserve the annotation budget for the data that will have the most impact on the representations' transferability. Promoting class-level domain invariance [START_REF] Long | Conditional adversarial domain adaptation[END_REF][START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF]) makes it possible to assess this impact precisely. Indeed, class-level invariance consists of using predicted target labels for soft-class conditioning in the domain adversarial loss. Involving an oracle, which provides the ground-truth, enables to change the contribution of a target sample from soft to hard-class conditioning. Therefore, we measure the impact of annotation by estimating the variation of the domain adversarial loss gradient (see Fig. 1). Thus, in this paper,

• We present Stochastic Adversarial Gradient Embedding (SAGE), an embedding of target samples suited for active learning of domain invariant representations. This embedding is obtained by measuring the variation, before and after annotation, of the domain adversarial loss gradient. (• vs ) where source samples are blue and target samples are orange. Before annotation, the class-level alignment is not satisfactory leading to a potential negative transfer (poorly aligned target samples tagged as 1, 2 and 3). We estimate which sample should be annotated as a priority by measuring the variation, before and after annotation, of the gradient of the representations' transferability. We observe the highest variation is obtained for target sample 3, which is sent to an oracle. The oracle annotation returns class , validating the suspicion of negative transfer. This leads to an update of the decision boundary which pushes 1, 2 and 3 into class , resulting of a better class-level alignment of representations. SAGE has the following properties: 1. It takes into account the uncertainty on a target sample label by considering the gradient as a stochastic vector. Since annotation removes uncertainty, it allows us to estimate its expected variation due to the annotation. 2. The higher the gradient variation norm, the more significant is the impact of annotation on the transferability of representations. • We follow [START_REF] Ash | Deep batch active learning by diverse, uncertain gradient lower bounds[END_REF] for increasing sampling diversity by promoting target samples for which SAGE span on diverse directions using the k-means++ initialization [START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF] The rest of the paper is organized as follows. First, we provide a brief overview of Domain Adversarial Learning for UDA. Importantly, we expose a soft-class conditioning adversarial loss, which reflects the transferability error of domain invariant representations [START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF]. Second, we motivate the use of Active Learning for enhancing their transferability. Third, we present the details of Stochastic Adversarial Gradient Embedding. Finally, we conduct an empirical investigation on several benchmarks.

Background

Notations. Let us consider three random variables; X the input data, Z the representations and Y the labels, defined on spaces X , Z ⊂ R d where d is the dimension of the representation, and Y, respectively. We note realizations with lower cases, x, z and y, respectively. Those random variables may be sampled from two and different distributions: the source distribution p S (X, Z, Y ) i.e., data where the model is trained and the target distribution p T (X, Z, Y ) i.e., data where the model is evaluated. Labels are one-hot encoded i.e., y ∈ [0, 1] c with i y i = 1 where c is the number of classes. We use the index notation S and T to differentiate source and target quantities. We define the hypothesis class H as a subset of functions from X to Y which is the composition of a representation class Φ (mappings from X to Z) and a classifier class F (mappings from Z to Y) i.e., h := f ϕ := f • ϕ ∈ H where f ∈ F and ϕ ∈ Φ. For D ∈ {S, T } and an hypothesis h ∈ H, we introduce the risk in domain D, ε D (h) := E D [ (h(X), Y )] where is the L 2 loss (y, y ) = ||yy || 2 and h(x) i is the probability of x to belong to class i. We note the source domain data (x S i , y S i ) 1≤i≤n S and the target domain data (x T i ) 1≤i≤n T .

Domain Adversarial Learning. The seminal works from [START_REF] Ganin | Unsupervised Domain Adaptation by Backpropagation[END_REF][START_REF] Ganin | Domain-adversarial training of neural networks[END_REF][START_REF] Long | Learning transferable features with deep adaptation networks[END_REF], and their theoretical ground [START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF], 2010), have led to a wide variety of methods based on domain invariant representations [START_REF] Long | Unsupervised domain adaptation with residual transfer networks[END_REF][START_REF] Long | Deep transfer learning with joint adaptation networks[END_REF][START_REF] Long | Conditional adversarial domain adaptation[END_REF][START_REF] Liu | Transferable Adversarial Training: A General Approach to Adapting Deep Classifiers[END_REF]Chen et al. 2019a;[START_REF] Combes | Domain Adaptation with Conditional Distribution Matching and Generalized Label Shift[END_REF]. A representation ϕ and a classifier f are learned by achieving a trade-off between source classification error and domain invariance of representations by fooling a discriminator trained to separate the source from the target domain:

L(ϕ, f ) := L c (ϕ, f ) -λ • inf d∈D L inv (ϕ, d) (1)
where

L c (ϕ, f ) := E x,y∼p S [-y • log(f ϕ(x))]
is the cross-entropy loss in the source domain, L inv (ϕ, d) := log(d(ϕ(x))] is the adersarial loss and D is the set of discriminators i.e. mapping from Z to [0, 1]. In practice, inf d∈D is approximated using a Gradient Reversal Layer [START_REF] Ganin | Unsupervised Domain Adaptation by Backpropagation[END_REF].

E x∼p S [log(1-d(ϕ(x)))]+E x∼p T [
Transferability loss for class-level invariance. Promoting class-level domain invariance improves transferability of representations [START_REF] Long | Conditional adversarial domain adaptation[END_REF]. Recently, Bouvier et al. introduce the transferability loss, noted L tsf , which performs class-conditioning in the adversarial loss by computing a scalar product between labels y and a class-level discriminator d defined as a mapping from Z to [0, 1] c . Since labels are not available in the target domain at train time, predicted labels ŷ := f ϕ(x) are used. This approach is referred to as soft-class conditioning:

L(ϕ, f ) := L c (ϕ, f ) -λ • inf d∈D L tsf (ϕ, ŷ, d) (2)
where

L tsf (ϕ, ŷ, d) := E (y,x)∼p S [y • log(1 -d(ϕ(x)))] + E (ŷ,x)∼p T [ŷ • log(d(ϕ(x))
] is the transferability loss and D is the the set of class-level discriminators i.e. mappings from Z to [0, 1] c . In this work, we explore the role of active annotation of a small subset of the target domain in order to improve the transferability of representations.

Theoretical Analysis

Naive active classifier. We consider A ⊂ X a measurable subset of X with probability b := p T (X ∈ A). The subset A is given to an oracle which provides the ground-truth: y ∼ Oracle(x) where x ∈ A. In concrete terms, b reflects our annotation budget. Given a hypothesis h ∈ H, we introduce a naive classifier h A that returns the predicted label h(x) if

x is not annotated and the Oracle annotation if x is in the subset A. Thus,

h A (x) = Oracle(x) if x ∈ A, h(x) otherwise. ( 3
)
To measure the quality of the active set A, we introduce the notion of purity. In particular, we are interested in the amount of information coming from the Oracle. The purity is thus defined as π := p T (h(X) = Oracle(X)| X ∈ A) and reflects our capacity to identify misclassified target samples. With this notion, we observe the naive classifier improves the target error:

ε T (h A ) ≤ ε T (h) -bπ (4)
The higher the budget of annotation b and the higher the purity π, the lower the target error of the naive classifier.

The naive classifier as a Transferability Inductive Bias.

We now show how the target error of the naive classifier ε T (h A ) is related to the source error of a classifier trained on source labelled data ε S (h), the annotation budget b, the purity of the annotated subset π, and the transferability of representations τ . We build on the work of Bouvier et al. by interpreting the naive classifier as an inductive bias. More precisely, the naive classifier's target error is bounded as follows (see supplemental material for the proof):

ε T (h A ) ≤ 1 bπ -1 (ε S (h) + 8τ + η) (5)
where

τ := sup f∈F {E x∼p T [h A (x) • f(ϕ(x))] -E x,y∼p S [y • f(ϕ(x))]} is the transferability error, F is the set of continuous functions from Z to [-1, 1] C and η := inf f∈F ε T (fϕ).
It is important to note that the transferability loss L tsf (ϕ, ŷA , d) is a domain adversarial proxy of the transferability error τ where ŷA = h A (x) [START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF]. Interestingly, target labels are only involved in π and η where the latter is an incompressible error that we assume to be small. The target error of the active classifier is a decreasing function of both the purity and the annotation budget and an increasing function of the transferability error.

Proposed Method

We first expose our motivations to embed target samples using the gradient of the transferability loss. Indeed, this quantity allows to assess the impact of annotation on representations transferability. Second, we define the Stochastic Adversarial Gradient Embedding (SAGE), an embedding where the norm quantifies this impact efficiently. Third, we increase the diversity of sampling in this space, as described in [START_REF] Ash | Deep batch active learning by diverse, uncertain gradient lower bounds[END_REF]. Finally, we detail the procedure for the active learning of domain invariant representations.

Motivations

As shown in the theoretical section, the budget b, the purity π and the transferability of representations τ are levers to improve the naive classifier target error. The budget b must be considered as a cost constraint and not as a parameter to be optimized. The purity of π is not tractable since it involves labels in the target domain. Therefore, we focus our efforts on understanding the role of active annotation in improving transferability error τ . Given a target sample x ∼ p T (X) with representation z := ϕ(x) ∈ R d , we expose the effect of annotating the sample x on the gradient descent update of Eq. (2). To conduct the analysis, we introduce the adversarial gradient g x of sample x as the gradient of the discriminator loss with respect to the representation z:

g x := - ∂ log(d(z)) ∂z ∈ R c×d , where d(z) ∈ [0, 1] c (6)
Following the expression of the transferability loss L tsf , the contribution of a sample x to the gradient update (Eq. ( 2)), before and after its annotation, is:

θ ← θ -α ∂z ∂θ • (ŷ • g x ) Before annotation -→ θ ← θ -α ∂z ∂θ • (y • g x ) After annotation y∼Oracle(x)
where ∂z/∂θ is the jacobian of the representations with respect to the deep network parameters θ i.e., z := ϕ θ (x), ŷ := gϕ θ (x) is the current label estimation and α is some scaling parameter. Before the annotation, the gradient vector can be written as a weighted sum of g x i.e., ŷ • g x ∈ R d , reflecting the class probability of x. Annotating the sample x has the effect of setting, once and for all, a direction in R c of the gradient (y • g x ). Based on this observation, we can measure the annotation procedure's ability to learn more transferable representation by its tendency to change the path of the gradient descent i.e., how y • g x may differ with ŷ • g x .

ŷ • g x 2 R d g 1 x g 2 x g2 x g1 x = 0 = 2g 1 x (a) Positive orth. projection ŷ • g x 2 R d G r a d i e n t p a t h ŷ = (p 1 , p 2 ) g 1 x g 2 x |g 1 x • gx| ||gx|| 2 gx |g 2 x • gx| ||gx|| 2 gx g2 x g1 x p p 1 g1 x p p 2 g 2 x (b) SAGE ŷ • g x 2 R d g 1 x g 2 x g 3 x ŷ = (0.25, 0.25, 0.5) (c) Poor local minimum
(x) = ( √ p 1 g1 x , √ p 2 g2 x ). Here g2 x ⊥ g 2 x since ŷ • g x and g 2 x have a similar direction while |g 1 x • g x | ≥ |g 1 x • g x | since g 1
x as a component in the opposite direction of ŷ • g x . (c) Illustration of a case where the transferability loss is close to a local minimum (ŷ • g x ≈ 0), but the stochastic gradients (g y x for y ∈ {1, 2, 3}) have a high norm. Here, the annotation chooses one of the gradients resulting in a strong update of the model.

Positive orthogonal projection

The adversarial gradient g x := ∂ log(d(z))/∂z ∈ R c×d embodies the uncertainty on the true labels in the first dimension R c . In the rest of the paper, we now consider g x as a stochastic vector of R d with realizations lying in a discrete support G x := {g 1

x , ..., g c x } where g i x = (∂ log(d(z))/∂z) i . When provided the label through an oracle i.e., y ∼ Oracle(x), we obtain g y x ∈ G x , a realization of g x . Before annotation, the direction of the gradient is the mean of g x where G x is provided with a probability measure given by the classifier h(x) i.e., p(g x = gi

x ) = h(x) i :

E h [g x ] := E y∼h(x) [g y x ] ∈ R d (7
) Therefore, the tendency to modify the direction of the gradient is reflected by a high discrepancy between E h [g x ] and g y

x for y ∼ Oracle(x). To quantify this discrepancy, we consider variations in both direction and magnitude: • Direction: A simple way to learn a new model by gradient descent is to find samples which modify the gradient's direction drastically. • Magnitude: The higher the norm of the gradient, the stronger the update of the model. To find a good trade-off between direction and magnitude, we remove the mean direction of the gradient E h [g x ] to g x by computing a positive orthogonal projection:

gx := g x -λE h [g x ] (8) where λ := |g x • E h [g x ]|/||E h [g x ]|| 2 . Note that we use |g x • E h [g x ]|, rather than g x • E h [g x ]
for the standard orthogonal projection, hence its name of positive orthogonal projection.

On the one hand, if the annotation provides a gradient with the same direction as the expected gradient i.e., the annotation reinforces the prediction, gx is null. On the other hand, if the annotation provides a gradient with an opposite direction to the expected gradient i.e., the annotation contradicts the prediction, the norm of gx increases. Therefore, target samples x for which we expect the highest impact on the transferability, are those with the highest norm of gx . An illustration is provided in Fig. 2(a). Since gx is random, we need additional tools to define a norm operator properly on it, leading to our core contribution.

Stochastic Adversarial Gradient Embedding

A simple way to define the norm of gx would be to consider ||g x || h := (E y∼h(x) ||g y

x || 2 ) 1/2 i.e., the expected norm of gx . This leads to a "distance" defined as follows

(E y1∼h(x1),y2∼h(x2) ||g y1 x1 -g y2 x2 || 2 ) 1/2
. However, it is straightforward to observe such a "distance" between gx and itself is not null if h(x) is not a one-hot vector; not making it, in fact, a proper distance.

To address this issue, we suggest to embed, through a mapping named Stochastic Adversarial Gradient Embedding (SAGE), the coupling (h, g) in a vectorial space by considering the following tensorial product:

SAGE(x) := ( h(x) 1 g1 x , ..., h(x) c gc x ) ∈ R c×d (9)
Importantly, the choice of using √ h is motivated by the observation that ||SAGE(x)|| = ||g x || h leading to a proper distance between x 1 and x 2 :

∆ h (x 1 , x 2 ) := ||SAGE(x 1 ) -SAGE(x 2 )|| (10)
Crucially, both the norm and the distance computed on SAGE do not involve the target labels, making it relevant in the UDA setting where target labels are unknown. An illustration of SAGE is provided in Fig. 2(b).

Increasing Diversity of SAGE

As aforementioned, the higher the norm of ||SAGE(x)||, the greater the expected impact of annotating sample x on the transferability of representations. A naive strategy of annotation would be simply to rank target samples by their SAGE norm (||SAGE(x)||). However, this strategy ignores the crucial problem of diversity when running active annotation [START_REF] Settles | Active learning literature survey[END_REF]. Embedding target samples offers the opportunity to increase sampling diversity by selecting samples with high expected norms and various directions [START_REF] Ash | Deep batch active learning by diverse, uncertain gradient lower bounds[END_REF]). The k-means++ initialization is known to select diverse and high norm vectors. Roughly speaking, the algorithm starts by selecting the vectors v with the highest norm and the second, v , such that vv has the highest norm, and so on. The procedure is detailed in Algorithm 1.

Algorithm 1 diverse SAGE((x T i ) 1≤i≤n T , f, ϕ, d, b) Input: Target samples (x T i ) 1≤i≤n T , classifier f , representa- tion ϕ, discriminator d, budget b: 1: A ← [ arg max 1≤i≤n T ||g x T i || h ] 2: while len(A) < b do 3: A.append arg max 1≤i≤nt min a∈A ∆ f ϕ (x T i , x T a ) 4: end while 5: Return A

Training procedure

The training procedure is described in Algorithm 2. First, we train the model by UDA [START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF]. Second, for a given number of iterations, we select by SAGE b samples to send to the Oracle. Then, we perform two steps: an inductive step and a transfer step. The former updates the current classifier, for learning an active classifier, by incorporating the knowledge provided by annotated samples. The latter updates the representations for achieving class-level invariance where the predictions of the active classifier are used in the target domain. This procedure is repeated for the r annotation rounds. In the following, we note h a ∈ H an active classifier i.e., a classifier that takes into account annotations provided by the Oracle (e.g., the naive classifier).

Transfer step. Based on our theoretical analysis, the representations transferability is improved when h a is introduced into the transferability loss:

L tsf (ϕ, h a , d) := E (y,x)∼p S [y • log(1 -d(ϕ(x)))] + E x∼p T [h a (x) • log(d(ϕ(x))] (11)
The active classifier is involved in the target domain to compute the transferability loss. Therefore, we introduce the Transfer step which consists in the following stochastic gradient descent update:

transfer(f, ϕ, h a ) :=(f, g) -α∇ (f,g) {L c (ϕ, f ) -λ • inf d∈D L tsf (ϕ, h a , d)} (12)
where inf d∈D is in practice gradient reversal layer [START_REF] Ganin | Unsupervised Domain Adaptation by Backpropagation[END_REF], α is scaling parameter, λ varies smoothly from 0 to 1 during training as described in [START_REF] Long | Conditional adversarial domain adaptation[END_REF]) and losses are computed on batches of samples.

Inductive step. We now focus our attention on the design of the active classifier h a , referred to as the Inductive step, as described in [START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF]. Our theoretical analysis from Eq. ( 5) holds for the naive classifier (it outputs the oracle annotation if the target sample is annotated and the current prediction otherwise). However, given two samples x 1 and x 2 close in the representation space i.e., z 1 ≈ z 2 , such that x 1 is annotated, y 1 ∼ Oracle(x 1 ), one can assume that the probability of observing y 1 = Oracle(y 2 ) is high. However, the design of the naive classifier does not reflect this inductive bias since h A (x 2 ) = h(x 2 ) (see Fig. 3). A.append(diverse SAGE((

x T i ) 1≤i≤n T , f, ϕ, d, b
)) # Annotate target samples selected by diverse SAGE.

4:

for n it iterations do 5: h a ← inductive(f ϕ, A) # Inductive step: annotations are incorporated in the active classifier.

6:

(f, ϕ) ← transfer(f, ϕ, h a ) # Transfer step: representation and classifier update for aligning with the feedback of the active classifier.

7:

end for 8: end for Therefore, we suggest to train an active classifier based on the annotation provided by the Oracle to spread the information in the representation space neighborhood of x 1 . We propose to use a simple loss that incorporates both the error in the source domain and the error in target annotated samples as follows:

h a := arg min h∈H γL c (h) + (1 -γ)L A (h) (13)
where

L A (h) = E x∈A [-Oracle(x) • log(h(x))
] and γ ∈ (0, 1) is a trade-off parameter. On the one hand, when the annotated samples have high importance to learn h a i.e., γ tends to 0, we are exposed to a high risk of high variance of such classifier since |A| n S . On the other hand, when the source samples have a high importance to learn h a i.e., γ tends to 1, knowledge provided by the annotation is poorly learned by the active classifier. Therefore, calibrating properly γ is a challenging problem. We overcome this issue by smoothly updating the classifier h as follows: The design of inductive aims not to forget knowledge acquired in the source domain while integrating the knowledge provided by the annotation of the target samples.

inductive(h, A) := h -α∇ h L A (h) (14)

Experiments

Datasets. We evaluate our approach on Office-31 [START_REF] Saenko | Adapting visual category models to new domains[END_REF]) and VisDA-2017 [START_REF] Peng | Visda: The visual domain adaptation challenge[END_REF]). Office-31 contains 4,652 images classified in 31 categories across three domains: Amazon (A), Webcam (W), and DSLR (D). We explore tasks A → W, W → A, A → D and D → A.

We do not report results for tasks D → W and W → D since these tasks have already nearly perfect results in UDA [START_REF] Long | Conditional adversarial domain adaptation[END_REF]. For VisDA, we explore Synthetic: 3D models with different lightning conditions and different angles; Real: real-world images. We explore the Synthetic → Real task. The standard protocol in UDA uses the same target samples during train and test phases. In the context of active learning, this induces an undesirable effect where sample annotation mechanically increases the accuracy; at train time, the model has access to input and label of annotated samples which are also present at test time. We suggest instead to split the target domain into a train target domain (samples used for adaptation and pool of data used for annotation) and test target domain (samples used for evaluating the model) with a ratio of 1/2. Therefore, samples from the test target domain have never been seen at train time.

Setup. For classification, we use the same hyperparameters than [START_REF] Long | Conditional adversarial domain adaptation[END_REF]) and adopt ResNet-50 [START_REF] He | Deep residual learning for image recognition[END_REF]) as a base network pre-trained on ImageNet dataset [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]). Our code is based on official implementations of Bouvier et al. derived from [START_REF] Long | Conditional adversarial domain adaptation[END_REF]. For all experiments, we have fixed r = 10 rounds of annotations. For Office31, we have fixed a budget of b = 2% of annotation of the train target domain i.e., 20% of the train target domain is annotated at the end of the 10 rounds. For VisDA, we have explored two budgets: b = 10 or 100 samples. We report average results obtained with 6 random experiments. We perform 10k iterations of SGD for the UDA pre-training while, between each annotation round, we perform 5k iterations of SGD. One experiment lasts about ∼12 hours on a single NVIDIA V100 GPU with 32GB memory. The full implementation is provided in the supplemental material. Results. We report the results of experiments in Fig. 4. Approximately 110 days of GPU time are necessary for reproducing the results. First, active annotation brings substantial improvements to UDA for both datasets. This validates the effort and the focus that should be put on active domain adaptation in our opinion. For the six tasks, SAGE outperforms the baselines (AADA in particular) with a comfortable margin. More precisely, the saturation regime for AADA for A→W, D→A and VisDA tasks is significantly below than the saturation regime of SAGE. Even when provided with free annotation rounds, AADA++ is less accurate than SAGE, except for task W→A, demonstrating the significant improvement made by SAGE. In addition, we observe that AADA is unstable when only few data are an-notated (VisDA(b = 10)), while SAGE remains robust in this regime. Finally, uncertainty-based sampling (Entropy) performed better than diverse-based sampling (Random) for the Office31 dataset, while the contrary is observed for the VisDA dataset. Interestingly, SAGE performs better than both Entropy and Random, showing that SAGE takes the best of both worlds (uncertainty vs diversity).

Ablation study. We conduct an ablation study to compare the inductive step described in Eq. ( 14) with a step based on Eq. ( 13) (Balance with γ = 0.5) or based on Eq. (3) (Naive). We report results for tasks A→W, W→A and both tasks of VisDA(b = 100). We observe that both Balance and Inductive improve significantly performances compared to the Naive classifier, demonstrating the importance of the inductive step. For both tasks A→W and W→A, Inductive is slightly better than Balance, confirming our belief that smooth updating the classifier (as described in Eq. ( 14)) improves performances. Interestingly, Inductive performed better than Balance when few data are annotated (e.g., VisDA with b = 10, VisDA with b = 100 for rounds lower than 3), while the contrary was observed when more data is annotated. This findings tend to show that Inductive is more adapted in the low annotation regime. All things considered, the difference between Balance and Inductive remains small compared to the improvement provided by SAGE compared to AADA. Nevertheless, the inductive step remains an important step in SAGE and deserves a deeper understanding. More ablation is provided in the Appendix. We demonstrate the effectiveness of k-means++ [START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF]

Related works

Transferability of Invariant Representations. Recent works warn that domain invariance may deteriorate transferability of invariant representations [START_REF] Johansson | Support and Invertibility in Domain-Invariant Representations[END_REF][START_REF] Zhao | On Learning Invariant Representations for Domain Adaptation[END_REF]. Prior works enhance their transferability with multi-linear conditioning of representations with predictions [START_REF] Long | Conditional adversarial domain adaptation[END_REF], by introducing weights [START_REF] Cao | Partial adversarial domain adaptation[END_REF][START_REF] Bouvier | Hidden Covariate Shift: A Minimal Assumption For Domain Adaptation[END_REF][START_REF] You | Universal domain adaptation[END_REF][START_REF] Zhang | Importance weighted adversarial nets for partial domain adaptation[END_REF][START_REF] Combes | Domain Adaptation with Conditional Distribution Matching and Generalized Label Shift[END_REF], by penalizing high singular value of representations batch [START_REF] Chen | Transferability vs. discriminability: Batch spectral penalization for adversarial domain adaptation[END_REF], by hallucinating consistent target samples for bridging the domain gap [START_REF] Liu | Transferable Adversarial Training: A General Approach to Adapting Deep Classifiers[END_REF] or by enforcing target consistency through augmentations which conserve the semantic of the input [START_REF] Ouali | Target Consistency for Domain Adaptation: when Robustness meets Transferability[END_REF]).

Active Learning. There is an extensive literature on Active Learning [START_REF] Settles | Active learning literature survey[END_REF]) that can be divided into two schools; uncertainty and diversity. The first aims to annotate samples for which the model has uncertain prediction e.g., samples are selected according to their entropy [START_REF] Wang | A new active labeling method for deep learning[END_REF] or prediction margin [START_REF] Roth | Margin-based active learning for structured output spaces[END_REF], with some theoretical guarantees [START_REF] Hanneke | Theory of disagreement-based active learning[END_REF][START_REF] Balcan | Agnostic active learning[END_REF]. The second focuses on annotating a representative sample of the data distribution e.g., the Core-Set approach (Sener and Savarese 2017) selects samples that geometrically cover the distribution. Several approaches also propose a trade-off between uncertainty and diversity, e.g., [START_REF] Hsu | Active learning by learning[END_REF] that is formulated as

Conclusion

We have introduced SAGE, an efficient method for active adversarial domain adaptation. SAGE is an embedding suitable for identifying target samples that are likely to improve representations' transferability when annotated. It relies on three core components; a stochastic embedding of the gradient of the transferability loss, a k-means++ initialization which guarantees that each annotation round annotates a diverse set of target samples, and a two-step learning procedure that incorporates efficiently active target samples when learning invariant representations. Through various experiments, we have demonstrated the effectiveness of SAGE for improving the transferability of representations and its capacity to take the best of uncertainty and diversity sampling.

Proof of the theoretical analysis

The naive classifier's target error is bounded as follows:

ε T (h A ) ≤ 1 bπ -1 (ε S (h) + 8τ + η) (15)
where τ := sup f∈F {E x∼p T [h A (x) • f(ϕ(x))] -E x,y∼p S [y • f(ϕ(x))]} is the transferability error, F is the set of continuous functions from Z to [-1, 1] C and η := inf f∈F ε T (fϕ).

Proof. First, we observe that :

ε T (h A ) ≤ βε T (h) (16)
with β = 1 -bπ ε T (h) . Then;

ρ := β 1 -β = ε T (h) bπ -1 ≤ 1 bπ -1 (17)
We apply Bound 4 from [START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF] where the inductive classifier is the active classifer h A . Then we bound the invariance error using the transferability error (Proposition 3, item 1 from [START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF]) to obtain 6τ +2τ = 8τ , leading to the announced result.

Figure 1 :

 1 Figure1: Illustration of the effect of annotation of a target sample selected by SAGE (best viewed in colors). Binary classification problem (• vs ) where source samples are blue and target samples are orange. Before annotation, the class-level alignment is not satisfactory leading to a potential negative transfer (poorly aligned target samples tagged as 1, 2 and 3). We estimate which sample should be annotated as a priority by measuring the variation, before and after annotation, of the gradient of the representations' transferability. We observe the highest variation is obtained for target sample 3, which is sent to an oracle. The oracle annotation returns class , validating the suspicion of negative transfer. This leads to an update of the decision boundary which pushes 1, 2 and 3 into class , resulting of a better class-level alignment of representations.

Figure 2 :

 2 Figure 2: (a) The positive orthogonal projection cancels the gradient when the annotation agrees with the prediction. It doubles its norm when the annotation disagrees with the prediction. (b) Visualisation of SAGE(x) = ( √ p 1 g1 x , √ p 2 g2 x ). Here g2 x ⊥ g 2

Figure 3 :

 3 Figure 3: Illustration of the decision boundary update when varying the inductive design of the active classifier. Sample 2 is sent to an Oracle providing annotation when the current classifier h predicts •. Based on this annotation, one can strongly that 1 is a . Here, the naive classifier predicts • for 1. Both 1 and 2 are close to the balance classifier's decision boundary due to a • source sample 3 resulting in an uncertain predictions, thus a poor class-conditioning in the transferability loss. Our inductive step allows to obtain confident predictions for both 1 and 2. The active classifier misclassifies 3 enforcing the model to learn a better-suited representation for 3, improving the representation alignment. Algorithm 2 Training procedure Input: Target samples (x T i ) 1≤i≤n T , annotation budget b, annotation rounds r, iterations n it : 1: f, ϕ ← UDA pretraining, A ← [ ]. 2: for r rounds of annotations do 3:

  Figure 4: SAGE outperforms the baselines for the six tasks. Annotation of target samples improves the transferability of domain invariant representations drastically. If uncertainty-based selection (Entropy) performs better than diversity-based selection (Random) for the Office31 dataset, the opposite is observed for the VisDA dataset. For both datasets, SAGE performs better than both uncertainty and diversity-based selections, demonstrating its capacity to take the best of the two worlds.

  Baselines. AADA[START_REF] Su | Active adversarial domain adaptation[END_REF] is the closest algorithm to SAGE and the most interesting to compare. AADA learns domain invariant representations by fooling a domain discriminator d trained to output 1 for source data and 0 for target data[START_REF] Ganin | Unsupervised Domain Adaptation by Backpropagation[END_REF] and scores target samples x; s(x) := H(ŷ)w(z) where H(ŷ) is the entropy of predictions ŷ and w(z) = (1d(z))/d(z). H(ŷ) brings information about uncertainty while w(z) brings diversity to the score. We have reproduced the implementation of AADA. SAGE starts active learning with a serious advantage to AADA as the pre-training procedures differ significantly. In order to get a fairer comparison with SAGE, we have therefore chosen to report a modified version of AADA that we call AADA++. AADA++ is free of charge as long as the performance is below the UDA baseline[START_REF] Bouvier | Robust Domain Adaptation: Representations, Weights and Inductive Bias[END_REF]) (UDA). In our view, this should essentially eliminate AADA's structural disadvantage. In practical terms, we translate AADA to the left of the graph (Annotation round, Target accuracy) until accuracy at request 0 is higher than UDA, explaining why annotation rounds of AADA++ do not reach 10. We also report Entropy (uncertainty-based sampling which selects samples with the highest entropy) and Random (diversitybased sampling which selects samples randomly). For both Entropy and Random baselines, the training procedure of Algorithm 2 is followed, except for line 3 where SAGE is replaced by entropy sampling[START_REF] Wang | A new active labeling method for deep learning[END_REF] or random sampling.

Figure 5 :

 5 Figure 5: Both Inductive and Balance improve the active learning compared with the Naive classifier. Inductive seems to provide better guarantees compared with the Balance classifier when only few data are annotated. This remark opens the way to interesting future work in ADA.

  in SAGE. Additionally to report SAGE (SAGE with k-means++), we also reports results of Active Domain Adaptation when target samples are selected with respect to their SAGE norm (||SAGE||), thus not taking in account directions of gradients. Results are presented in Fig.6for tasks A→W, W→A and both tasks of VisDA(b = 10 and 100).

  Figure 6: For the four tasks selected for the ablation study, the k-means++ initialization brings substantial improvments especially for tasks W→A and VisDA for b = 10 and 100.

  a bandit problem. Recently, Ash et al. introduced BADGE, a gradient embedding, which, like SAGE, takes the best of uncertainty and diversity. Our work is inspired by BADGE and adapts the core ideas in the context of learning domain invariant representations.Active Domain Adaptation. Despite its great practical interest, only a few previous works address the problem of Active Domain Adaptation.[START_REF] Chattopadhyay | Joint transfer and batch-mode active learning[END_REF] annotates target samples by importance sampling while ALDA[START_REF] Rai | Domain adaptation meets active learning[END_REF][START_REF] Saha | Active supervised domain adaptation[END_REF] annotates samples with high discrepancy with source samples based on the prediction of a domain discriminator. However, those strategies do not fit modern adaptation with deep nets. To our knowledge, AADA[START_REF] Su | Active adversarial domain adaptation[END_REF] is the only prior work that learns actively domain invariant representations and achieves the state-of-the-art for Active Domain Adaptation. Thus, AADA is the most relevant work to compare with SAGE.

Acknowledgements

Victor Bouvier is funded by Sidetrade and ANRT (France) through a CIFRE collaboration with CentraleSupélec. This work was performed using HPC resources from the "Mésocentre" computing center of CentraleSupélec and École Normale Supérieure Paris-Saclay supported by CNRS and Région Île-de-France (http://mesocentre. centralesupelec.fr/). We thank the contributors of (Walt, Colbert, and Varoquaux 2011) and (Buitinck et al. 2013) that were used for k-means++ initialization, (Hunter 2007) for figures rendering and (Paszke et al. 2019) that was used as Deep Learning framework.