The balancing principle for parameter choice in distance-regularized domain adaptation
Year: 2021

Abstract:
We address the unsolved algorithm design problem of choosing a justified regularization parameter in unsupervised domain adaptation. This problem is intriguing as no labels are available in the target domain. Our approach starts with the observation that the widely-used method of minimizing the source error, penalized by a distance measure between source and target feature representations, shares characteristics with regularized ill-posed inverse problems. Regularization parameters in inverse problems are optimally chosen by the fundamental principle of balancing approximation and sampling errors. We use this principle to balance learning errors and domain distance in a target error bound. As a result, we obtain a theoretically justified rule for the choice of the regularization parameter. In contrast to the state of the art, our approach allows source and target distributions with disjoint supports. An empirical comparative study on benchmark datasets underpins the performance of our approach.

heading: 1 Introduction
text: Domain adaptation uses the knowledge in a source domain to improve the performance of an algorithm on a related target domain [1]. In particular, domain adaptation tackles domain shifts in machine learning applications: Medical diagnostic systems should be adapted to new physical human variations; Industrial quality inspection systems should be accurate for new products; Self-driving cars should be able to adapt to new geographical environments and weather conditions. In this work, we focus on unsupervised domain adaptation where labels are only available in the source domain.
There are mainly two types of approaches for unsupervised domain adaptation: importance weighting [2, 3, 4, 5, 6, 7] and feature representation learning [8, 9, 10, 11, 12, 13]. In this work, we focus on feature representation learning which goes beyond classical importance weighting by allowing a target distribution with support outside of the source distribution. The core idea behind feature representation learning approaches is to map the data into a new feature space where the source and target
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
data representations appear similar, and where enough information is preserved for prediction [14]. The similarity is often realized by regularization using distance measures between source and target representations [15, 16, 17, 18, 19, 20, 21]. However, the performance of such methods crucially depends on the choice of the regularization parameter which penalizes the distance. The problem we investigate in this work is to choose this parameter, which is sophisticated without any target labels.
While remarkable theoretical results have been achieved which quantify the generalization ability of domain adaptation models [8, 22, 19, 20, 21], the choice of the regularization parameter which is crucial for finding such models has not systematically been addressed. Even though some parameter choice strategies exist, they are either purely heuristically driven or very limited by their assumptions [23]. Typical approaches are fixing the regularization parameters [12], minimizing the source error [16], balancing the source error and a distance [17], multiplying a fixed weighting parameter (e.g. 1 in [16]) by a heuristic schedule value that increases during training, or, (importance) weighting the input samples by the ratio between target and source density [3, 24, 23]. One common problem shared among all these approaches is that they all can fail if the density ratio is unbounded. Such unbounded density ratio is typical for many of the high dimensional problems considered in machine learning [19], e.g. see Figure 1. Besides the aforementioned issues, the lack of principled strategies for parameter choice causes misinterpretations in the ranking of domain adaptation methods which are traditionally compared by performance, while often relying on different parameter choice strategies.
In this work, we propose a principled method for choosing distance-penalizing parameters of feature representation learning approaches for unsupervised domain adaptation. Our approach starts with the observation that the distance-regularization setting of domain adaptation shares characteristics with regularized ill-posed inverse problems (see Table 1). In inverse problems, the regularization parameter can be optimally chosen by the fundamental balancing principle which optimizes an approximation-sample (bias-variance) trade-off [26, 27, 28]. We apply this principle for balancing domain distance and learning errors of target error bounds. In particular, we approach the problem of non-computable terms in the target error bound by a new algorithmic criterion for approximating the value of balance. We call our method the Balancing Principle for Domain Adaptation (BPDA).
The BPDA is general in the sense that it can be applied based on different target error bounds, e.g. on [8, 22, 19, 20, 21]. To the best of our knowledge, the BPDA is the first principled method for parameter choice in unsupervised domain adaptation that allows an unbounded ratio between target and source density. We provide a bound on the generalization error of the best model corresponding to the parameter chosen by the BPDA. Finally, we empirically investigate the behavior of the BPDA based on two target error bounds, different domain adaptation methods and benchmark datasets. Our
results show that the BPDA outperforms or is on par with the state of the art on the problem of choosing the regularization parameter, on several domain adaptation methods; applied on different datasets.

heading: 2 Summary of results
text: Notation Let X ⊂ Rn be an input space and Y be a discrete label space. Following the classical setting of unsupervised domain adaptation [25], we consider two datasets: A source dataset (x,y) = ((x1, lS(x1)), . . . , (xs, lS(xs))) ∈ (X × Y)s with inputs x1, . . . , xs independently drawn according to some source distribution (Borel probability measure) pS on X and labeled according to some labeling function1 lS : X → Y , and, an unlabeled target dataset x′ = (x′1, . . . , x′t) ∈ X t with elements independently drawn according to some target distribution pT on X . Throughout this work, we focus on loss functions L : Y ×Y → [0,∞) which satisfy L(y, y) = 0. For example consider the 0-1 loss L(y1, y2) := 1[y1 ̸= y2], where 1[P ] is 1 iff the predicate P is true and 0 otherwise, and the quadratic loss function L(y1, y2) := |y1 − y2|2. We denote the source error by εS(f) = εS(f, lS) with cross-error defined as εS(f, g) := Ex∼pS [L(f(x), g(x))] and its empirical sample estimate by ε̂S(f) = ε̂S(f, lS) with ε̂S(f, g) := ∑s i=1 L(f(xi), g(xi)). We denote the analogously defined target error by εT (f), target cross-error by εT (f, g) and its empirical sample estimate by ε̂T (f) with empirical cross-error ε̂T (f, g). Throughout this work, we focus on target cross-errors εT (f, g) which satisfy the triangle inequality.
Learning setup In this work, we focus on feature representation learning algorithms for domain adaptation. These approaches aim at finding two learning models: A representation mapping ϕ ∈ Φ ⊂ {ϕ : X → R} into some representation space R ⊂ Rm and a classifier g ∈ G ⊂ {g : R → Y}. Loosely speaking, the aim is to find a mapping ϕ under which the source representations ϕ(x) := (ϕ(x1), . . . , ϕ(xs)) and the target representations ϕ(x′) := (ϕ(x′1), . . . , ϕ(x ′ t)) appear similar, and, at the same time, enough information is preserved for prediction [14] by g(x). A common approach to realize this aim is to solve the following objective function [19]
min g∈G,ϕ∈Φ
ε̂S(g ◦ ϕ) + α · d(ϕ(x), ϕ(x′)) (1)
where d is a distance measure between source and target representations and α ∈ [0,∞) is a parameter2. Good choices for d in Eq. (1) have been identified to be the Wasserstein distance [29, 30], the Maximum Mean Discrepancy [31, 32], moment distances [17, 33, 18, 34, 35, 36], adversarially learned distances [16, 37] and other measures of divergence [38, 39, 19, 20].
Problem For some α ∈ [0,∞), let gα ◦ ϕα denote the minimizer of Eq. (1). Given an increasing sequence of parameters α1, . . . , αw ∈ [0,∞) with α1 = 0, the problem studied in this work is to choose the parameter α in the sequence α1, . . . , αw with the lowest target error εT (gα ◦ ϕα).
Approach Our approach consists in minimizing a target error bound which satisfies the form εT (gα ◦ ϕα) ≤ D(α) + E(α) (2)
where D(α) gives a notion of domain distance (cf. [25]) by quantifying a distance between source and target data representations and E(α) comprises different learning errors. We assume that E(α) is bounded by some constant B > 0. The general form in Eq. (2) is satisfied by many error bounds [8, 22, 20, 21, 34] which all can be taken as a basis for our approach (more detailed examples are provided in Section 3 and Section 4). One problem that complicates the minimization of these error bounds is that all of them contain terms that are not computable due to the lack of target data. That is, E(α) cannot be directly estimated. The BPDA overcomes this problem by a new criterion for estimating the value of balance between the normalized terms E(α) and D(α). The BPDA is detailed in Algorithm 1.
Properties of Algorithm 1 The BPDA has the following striking properties.
• The BPDA is a general procedure which can be instantiated by any error bound of the form in Eq. (2). See Section 4 and Section 5 for its application based on two different target error bounds [25, 20].
1For simplicity, we use labeling functions instead of the more general concept of conditional distributions. 2For simplicity we omit further regularization of ϕ and g.
• In contrast to state-of-the-art methods, the BPDA does not assume a target labeling function lT that is equal to the source labeling function lS (covariate-shift assumption) and it does not assume that the ratio between target and source density is bounded (sample selection bias assumption). See the supplementary material for a discussion of covariate-shift violations.
• The learning model gαBP ◦ ϕαBP identified by the BPDA satisfies a generalization bound, see Section 4. If the learning errors term E(α) is non-decreasing, then the target error of gαBP ◦ ϕαBP is only a constant factor away from the minimum minα∈[0,∞) D(α) + E(α) of the instantiation bound in Eq. (2).
Algorithm 1: Balancing principle for domain adaptation (BPDA) Input :Increasing sequence of parameters α1, . . . , αw ∈ [0,∞) with α1 = 0 and minimizers f1 := gα1 ◦ ϕα1 , . . . , fw := gαw ◦ ϕαw of Eq. (1). Output :Parameter αBP solving the problem above. Initialization :S = {} for i = 1, . . . , w do
Compute empirical cross-error ε̂T (fi, fj) and domain distance D(αj) for all j = 1, . . . , i− 1. if ε̂T (fi, fj) ≤ D(αj) ( 2 + 2BD(0) ) for all j = 1, . . . , i− 1 then
S := S ∪ {αi} end
end return :αBP := maxS
Besides the properties above, the BPDA outperforms or is on par with the state of the art, on the problem of choosing the regularization parameter, on several domain adaptation methods; applied on different datasets, see Section 5.
Related work Approaches which follow Eq. (1) are sometimes interpreted as learning domaininvariant representation. Note that the minimization of d(ϕ(x), ϕ(x′)) in Eq. (1) to achieve ϕ(x) = ϕ(x′) differs from the conception as regularization [40, 41]. In fact, minimization of the distance means unjustified over-penalization which might lead to deteriorated performance [19]. Interestingly, our interpretation as regularization problem opens up a powerful toolbox of mathematical techniques. Our approach takes up the technique of balancing stability and approximation in regularized illposed inverse problems. The balancing principle has its origins in [26] devoted to nonparametric regression estimation and has been introduced in the context of ill-posed problems [27] and in supervised learning with kernels [42]. Following this line of research, we propose to apply the mathematical techniques underlying the balancing principle in the context of domain adaptation. The most related principled parameter choice methods in the context of unsupervised domain adaptation are importance-weighted cross-validation [3] and its extensions [24, 23]. In contrast to these methods, our method is not restricted by the assumption of a bounded ratio between target and source density. One empirically driven method which is related to ours is [17, 43] which aims at balancing the source error and a distance between source and target data representations. However, this method is not theoretically justified as it ignores the minimal combined error of a classifier on representations as defined in [8]. Nevertheless, if the minimal combined error is negligibly small, our results provide a theoretical explanation of the principles underlying the success of [17, 43]. Our method relies on bounds on the target error such as e.g. [8, 22, 19, 20, 21, 34].

heading: 3 Preliminaries
text: Sampling error bound Throughout this work, we generically denote an upper bound on the sampling error by ηt,G,δ ∈ [0,∞), which is assumed to hold true with probability at least 1− δ:
|εT (f, g)− ε̂T (f, g)| ≤ ηt,G,δ (3)
The bound ηt,G,δ depends on the sample size t, the function class G and the constant δ, and, it is assumed to satisfy ηt,G,δ → 0 for t → ∞.
Two accompanying target error bounds In the seminal works [8, 25] binary classification Y := {0, 1} with 0-1 loss is considered and it is shown that the following bound holds for all symmetric function classes G (g ∈ G =⇒ 1 − g ∈ G), ϕ ∈ Φ, g ∈ G and datasets of equal size s = t with probability at least 1− δ:
εT (g ◦ ϕ) ≤ εS(g ◦ ϕ) + λG(ϕ) + d̂G△G(ϕ(x), ϕ(x′)) + ηt,G,δ (4) where
d̂G△G(x,x ′) := 2 ( 1− min
f,f ′∈G
[ 1
s s∑ i=1 1[f(xi) = f ′(xi)] + 1 s s∑ i=1 1[f(x′i) ̸= f ′(x′i)]
]) (5)
is the empirical G△G-divergence [44, 25] and λG(ϕ) := inff∈G(εS(f ◦ ϕ) + εT (f ◦ ϕ)) is the minimum possible combined error determined by the application of G. Using Eq. (3), the source error can be further upper bounded by the empirical source error. However, the term λG(ϕ) cannot be estimated based on given datasets as it depends on the unknown labeling function lT .
In [20], the bound in Eq. (4) is generalized to multiple classes Y := {1, . . . , k} and scoring functions H ⊂ {h : R → Rk}, where the output on each dimension indicates the confidence of prediction. For some h ∈ H, let us denote by gh : R → Y, x 7→ argmaxi∈{1,...,k} h(i)(ϕ(x)) with h(i)(z) being the i-th component of h(z). Let further εT denote the target error based on 0-1 loss. Then, with probability at least 1− δ
εT (gh ◦ ϕ) ≤ ε(ρ)S (h ◦ ϕ) + λH(ϕ) + d̂ (ρ) h,H(ϕ(x), ϕ(x ′)) + ηs+t,H,δ (6)
where ε(ρ)S (h) := ∫ X Λρ◦ρh(x, lS) dpS(x) with ρh(x, lS) := 1/2(h
(lS(x))(x)−maxy ̸=lS(x) h(y)(x)) and Λρ(x) being 1− x/ρ if 0 ≤ x < ρ, 0 if ρ ≤ x and 1 otherwise. Further, the target terms T, pT , lT are defined analogously to S, pS , lS , respectively; the combined error is defined by λH(ϕ) := infh∈H(ε (ρ) S (h ◦ ϕ) + ε (ρ) T (h)), and the empirical margin disparity discrepancy (MDD) is given by
d̂ (ρ) h,H(x ′,x) := max h′∈H
[ 1
s s∑ i=1 Λρ ◦ ρh′(xi, gh)− 1 t t∑ i=1 Λρ ◦ ρh′(x′i, gh)
] (7)
Similarly to Eq. (4), the source error can be further estimated by an empirical error and the combined error λH(ϕ) cannot be estimated based on given data.
Balancing principle for regularized inverse problems Let H and K be two Hilbert spaces and V : H → K be a linear operator. Then, the linear inverse problem associated to a given datum g ∈ K is to find some function f satisfying V f = g, see e.g. [45, 46, 40, 41] and references therein. In general, the above problem is ill-posed, i.e. a solution does either not exist, is not unique or does not depend continuously on g. Existence and uniqueness can be approached by using the the following minimizer as approximation of f
fH ∈ argmin f∈H ∥V f − g∥2K
However, especially in the case of a noisy operator V̂ and noisy data ĝ, continuous dependency on data becomes an important issue which can be restored using Tikhonov regularization [45]
fα ∈ argmin f∈H ∥V̂ f − ĝ∥2K + α ∥f∥ 2 H (8)
In many cases, probabilistic bounds on the error can be proven
∥fα − fH∥H ≤ S(α) +A(α) (9)
where S(α) is called sampling error made by considering noisy approximations V̂ and ĝ of V and g, respectively, and, A(α) is called approximation error originating from adding the regularizer ∥f∥2H. Commonly, S(α) decreases while A(α) increases with increasing α. We refer to [42] for detailed examples. The fact that S(α) decreases and A(α) increases motivates the so-called balancing principle which aims at computing α∗ such that S(α∗) = A(α∗) [26, 27, 42, 41, 28]. As a result, the balancing principle provides a procedure for approximating α∗ without having access to the values of A(α). The balancing principle obtains optimal error rates in many settings [47, 48, 49, 42, 41, 28].

heading: 4 Balancing principle for domain adaptation
text: In the following, we present the mathematical foundations of Algorithm 1 in two steps. In a first step, in Subsection 4.1, we state our assumptions and detail our idea of choosing the value of balance between terms in a target error bound. In a second step, in Subsection 4.2, we propose an algorithmic criterion, the balancing principle estimate for approximating the theoretical choice of the balancing value without target labels. Based on this criterion, we explain why we expect Algorithm 1 to be accurate.

heading: 4.1 Balancing terms in a target error bound
text: Assumptions In the following, let gα ◦ ϕα be a minimizer of Eq. (1) and assume that a target error bound holds which is of the form given by Eq. (2). Our approach is based on the plausible assumptions (a) that the function α 7→ E(α) is continuous and bounded by some constant B > 0, and (b) that the function α 7→ D(α) is continuous, non-increasing and non-degenerate, i.e. D(0) > 0. We further make the technical assumption (c) that limα→∞ D(α)/D(0) < supα∈[0,∞) E(α)/B. Note that (c) is satisfied in most standard cases, where D(α) → 0 for α, t → ∞. For example consider the two accompanying target error bounds in Section 3 as discussed at the end of this section.
Bridging regularized inverse problems and domain adaptation Under the assumptions above, our domain adaptation learning setup in Section 2 shares characteristics with the setting of regularized inverse problems as described in Section 3. Indeed, the Tikhonov regularizer ∥f∥2H in Eq. (8) is similarly applied as the distance-regularizer d(ϕ(x), ϕ(x′)) in Eq. (1). In addition, error bounds for inverse problems as given by Eq. (9) show a similar form as target error bounds following Eq. (2). The sampling error S(α) in Eq. (9) decreases similarly to the domain distance in Eq. (2) and the approximation error A(α) in Eq. (9) cannot be estimated similarly to the learning errors E(α) in Eq. (2). However, in the domain adaptation setting, the term E(α) does not necessarily increase. We approach this issue by considering the least non-decreasing majorant of E(α). Definition 1 (Least non-decreasing majorant [50]). The least non-decreasing majorant of E(α) is given by E(α) := supβ∈[0,α] E(β).
Further upper bounding Eq. (2) by
εT (gα ◦ ϕα) ≤ D(α) + E(α) ≤ D(α) + E(α) (10) results in a form which satisfies all properties needed to apply the balancing principle, see Table 1.
Balancing value for domain adaptation Having identified the shared characteristics between regularized inverse problems and domain adaptation, we now apply the techniques underlying the balancing principle to domain adaptation. We define the balancing value α∗ as achieving
D(α∗)
D(0) =
E(α∗)
B (11)
The normalizing factor 1/D(0) on the left-hand side of Eq. (11) and the factor 1/B ensure that the two curves D(α)/D(0) and E(α)/B intersect. In particular, the existence of α∗ follows from the
assumptions (a)–(c) above. See Figure 2 for an illustration. Algorithm 1 approximates α∗. If E(α) is non-decreasing and the bound in Eq. (10) holds with equality, then the rate of the target error εT (gα∗ ◦ ϕα∗) is optimal, i.e. εT (gα∗ ◦ ϕα∗) is only a constant factor away from the optimum infα∈[0,∞) εT (gα ◦ ϕα). See the supplementary material for a proof. This optimality property is shared with related regularization settings [47, 48, 49, 42, 28].
Two accompanying target error bounds Let us now discuss the reasoning above based on the two error bounds described in Section 3. First, recall the target error bound of [25] in Eq. (4). If we take D(α) := d̂G△G(ϕα(x), ϕα(x′)) + ηt,G,δ and E(α) := εS(gα ◦ ϕα) + λG(ϕα), it is natural to assume D(α) to decrease with α, especially for adversarial approaches which penalize the empirical G△G-divergence d̂G△G(ϕ(x), ϕ(x′)), see [16]. It also holds that E(α) ≤ 3 for all α ∈ [0,∞). For the balancing value to exist for large sample size t, we need to verify that D(α)/D(0) → 0 for t, α → ∞. However, this is satisfied for most function classes Φ, since it can be assumed that the constant function ϕ : x 7→ c ∈ R which achieves d̂G△G(ϕ(x), ϕ(x′)) = 0 is contained in Φ. That is, d̂G△G(ϕ(x), ϕ(x ′)) = 0 can be achieved for α → ∞ and consequently D(α)/D(0) → 0 for t, α → ∞.
Consider now the bound in Eq. (6). By using D(α) := d̂(ρ)h,H(ϕα(x), ϕα(x ′)) + ηs+t,H,δ, E(α) := ε (ρ) S (h ◦ ϕ) + λH(ϕ) and B = 3, all assumptions above are naturally satisfied similarly to the target error bound in Eq. (4) and the balancing value exists. In Section 5, we empirically investigate the performance of our method based on our two accompanying target error bounds. However, let us first show how we can overcome the problem of the non-computable term E(α).

heading: 4.2 Approximation of balancing value
text: Unfortunately, E(α) in Eq. (1) usually contains information about the target labeling function lT and α∗ can therefore not be calculated directly.
Balancing principle estimate We propose the following criterion for estimating α∗ which is realized by the BPDA in Algorithm 1. Definition 2 (Balancing principle estimate). Let α1, . . . , αw, w ∈ N with α1 = 0 be an increasing sequence of values in [0,∞) and denote by fi := gαi ◦ϕαi . Then, the balancing principle estimate is
αBP := max { αi ∣∣∣∣∀j ∈ {1, . . . , i− 1} : ε̂T (fi, fj) ≤ D(αj)(2 + 2BD(0) ) + ηt,G,δ } (12)
The balancing principle estimate in Definition 2 is based on checking an upper bound on the empirical cross-error ε̂T (fi, fj) between two models fi, fj resulting from two different values αi, αj of the
regularization parameter, respectively. The empirical cross-error does not contain information about the unknown target labels lT (x′1), . . . , lT (x ′ t) and can be computed based on available data. The main reason why we expect the balancing principle estimate αBP to be near to the balancing value in Eq. (11) can be explained as follows. Lemma 1. Let δ ∈ (0, 1), α, β ∈ [0,∞) and denote by fα := gα ◦ ϕα. If 0 ≤ α ≤ β ≤ α∗ then the following holds with probability at least 1− δ:
ε̂T (fα, fβ) ≤ D(α) ( 2 + 2B
D(0)
) + ηt,G,δ (13)
Lemma 1 (see the supplementary material for its proof) shows that the inequality in Eq. (12) is satisfied if αj ≤ αi ≤ α∗. This implies that αi > α∗ if the criterion is violated for some αj ≤ αi. Consequently, the maximum αBP as defined in Eq. (12) from an increasing sequence α1, . . . , αw which violates Eq. (13) for some j ∈ {1, . . . , i− 1} can be assumed to be near to α∗.
Generalization guarantee The model gαBP ◦ ϕαBP obtained by the BPDA in Algorithm 1 satisfies the following generalization guarantee. Theorem 1. Let δ ∈ (0, 1) and α1, . . . , αw ∈ [0,∞), α1 = 0 be an increasing sequence such that
D(αl) ≤ q ·D(αl+1) (14)
for all l ∈ {1, . . . , w − 1} and some q > 1. Then, with probability at least 1− δ εT (gαBP ◦ ϕαBP) ≤ D(α∗) ( 3 + 3B
D(0)
) q + ηt,G,δ (15)
Theorem 1 shows that the target error of the model gαBP ◦ ϕαBP identified by the BPDA has the same error rate as D(α∗) for t → ∞. Moreover, if the optimum infα∈[0,∞) D(α)+E(α) is achieved, then the error rate is optimal in the sense that εT (gαBP ◦ ϕαBP) is only a constant factor worse than the minimum infα∈[0,∞) D(α)+E(α). The constant factor is given by (3 + 3B/D(0)) qmax {D(0)/B, 1}. That is, the bound is larger for steeper D between two consecutive values for α (q is larger), and, it is larger for larger D(0)/B. The constant can be derived by bounding D(α∗) in Eq. (15) as detailed in the supplementary material. If E(α) is increasing and the instantiation bound in Eq. (2) is tight, i.e. it holds with equality, then the error εT (gαBP ◦ ϕαBP) is only a constant factor worse than the optimal error infα∈[0,∞) εT (gα ◦ ϕα). It is well known that appropriate assumptions as given above are needed for successful domain adaptation [52, 19]. However, in practice, target error bounds are often not tight and optimality cannot be guaranteed. In the following section, we therefore investigate the performance of our method on benchmark datasets based on our two accompanying target error bounds.

heading: 5 Empirical evaluations
text: We empirically investigate the performance of our approach based on two target error bounds, two parameter selection methods, three datasets and different domain adaptation methods3.

heading: 5.1 Setup
text: Given a domain adaptation algorithm that follows Eq. (1), the goal is to identify the regularization parameter α from the sequence 0, 10−6, 10−5, . . . , 103, 104 which leads to the smallest target error of the model learned by the algorithm.
Datasets We rely on one academic example which we call Transformed Moons. Transformed Moons shows a density ratio that is unbounded in large regions, see Figure 1. We also use the Amazon Reviews dataset [53]. This dataset contains text reviews from four domains: books (B), DVDs (D), electronics (E), and kitchen appliances (K). Reviews are encoded in 5000 dimensional feature vectors of bag-of-words unigrams and bigrams with binary labels: label 0 if the product is ranked by 1 to 3
3The source-code can be found at https://github.com/Xpitfire/bpda
stars, and label 1 if the product is ranked by 4 or 5 stars. From the four categories we obtain twelve domain adaptation tasks where each category serves once as source domain and once as target domain. We use the same data splits as previous works [54, 55, 16]. Thus, we have 2000 labeled source examples and 2000 unlabeled target examples for training, and between 3000 and 6000 examples for testing. Our third dataset is the DomainNet–2019 dataset consisting of six different domains, each having 345 classes, and an average count of 288 images per class, i.e. around 0.6 million images [56]. However, our focus is not on large-scale domain adaptation, but rather on ranking model selection methods; hence, we propose a reduced version of the DomainNet–2019 dataset. In particular, we reduce the number of classes to five. We call our new dataset MiniDomainNet. See the supplementary material for the dataset statistics.
Balancing principle for domain adaptation We apply the BPDA in Algorithm 1 based on the two accompanying target error bounds described in Section 3. On the two-class datasets Transformed Moons and Amazon Reviews, we apply the BPDA based on Eq. (4). We set the domain distance D(α) := d̂G△G(ϕα(x), ϕα(x
′)) + ηt,G,δ and approximate its value by a classifier as proposed in [16, Subsection 3.2]. In our experiments on the multi-class dataset MiniDomainNet, we apply the BPDA based on Eq. (6). We define D(α) := d̂(ρ)h,H(ϕα(x), ϕα(x
′)) + ηs+t,H,δ and approximate its value as proposed in [20, Subsection 4.2]. In both variants of the BPDA, one for each bound, we follow the argument of [25, Subsection 7.2] to have enough unlabeled data to evaluate the bounds without considering the finite sample error term ηt,G,δ. We repeat each domain adaptation model training several times. The if-statement in the BPDA in Algorithm 1 is considered violated, if there is a violation of the statement for at least one of the repetitions. For a fair comparison, the evaluations of IWV and DEV are also based on all repetitions. More precisely, for IWV and DEV, we choose the parameter with the lowest average importance weighted risk and lowest average DEV-risk, respectively, where the average is computed over all repetitions.
Parameter choice baselines We compare our parameter choice approach to four baselines. The first baseline is training on source data only (SO). The second baseline is the best target error (TB) and it serves as a lower bound for the error. The third baseline is importance weighted validation [3] (IWV). We follow [23] and use held-out validation, i.e. we hold out a part of the training data as validation set, and we compute the importance weights based on this validation set. We also follow [57] and [23, Subsection 4.3] to estimate the importance weight by a classifier trained to separate source from target data. The classifier is tuned separately for each task and dataset such that its validation misclassification error is at most 0.05. For MiniDomainNet, we compute the importance weight based on the features of the pre-trained ResNet-18 [58]. The fourth baseline is deep embedded validation [23] (DEV) which solves the unbounded variance issue in IWV. Following [23], DEV is applied on the features of the neural networks.
Domain adaptation methods In our experiments, we use three domain adaptation techniques. Domain-adversarial neural networks [16] (DANN), Maximum Mean Discrepancy [59, 15] (MMD) and Central Moment Discrepancy [18] (CMD). The details of all neural network architectures used, as well as the training strategy and hyperparameters are provided in the supplementary material.
Assumptions To evaluate the compliance of the assumptions in Subsection 4.1 for the algorithms CMD and MMD, we estimate E, the domain distance D and the least non-decreasing majorant E on the Transformed Moons dataset. In particular, the term E is computed using the (in unsupervised domain adaptation unknown) target labels for training a classifier to minimize the minimum possible combined error in Eq. (4). We repeat the evaluations 10 times for different initializations of the domain adaptation model weights.

heading: 5.2 Results
text: Assumptions The terms E and D for MMD on Transformed Moons are shown in Figure 2 and, for CMD, in the supplementary material. The following observation (a)–(d) can be made: (a) E is bounded, the mean curves of D(α) tend to be non-increasing and the technical assumption D(α)/D(0) < supα∈[0,∞) E(α)/B is satisfied for α ≥ 103. That is, the mean curves tend to follow the assumptions listed in Section 4.1. (b) The mean curves E and E tend to be similar. (c) The average parameters chosen by the balancing principle (see αBP in Figure 2) are the maximum values for
which the mean curves of E(α)/B are smaller than the mean curves of D(α)/D(0). That is, the BPDA described in Algorithm 1 tends to perform as expected. (d) There is a moderate trend towards a violation of the monotonicity assumption for D for CMD (see the supplementary material for the figure). However, the BPDA is (on average) robust w.r.t. this violation as it picks nearly the optimal value (see Table 2).
Comparative study Average values of our empirical evaluations on Transformed Moons and Amazon Review are summarized in Table 2. For the full tables on Transformed Moons, Amazon Reviews and MiniDomainNet, see the supplementary material. Although making no assumptions on the ratio between target and source density, the BPDA outperforms related parameter choice methods (IWV, DEV) on almost all tasks on Transformed Moons and Amazon Reviews, and, obtains competitive results on MiniDomainNet.

heading: 6 Conclusion and future work
text: One widely-used technique for unsupervised domain adaptation is to map the data into a new feature space where the source and target data representations appear similar, and where enough information is preserved for prediction [14]. The similarity is often realized by minimizing the source error weighted by a distance measure between source and target representations. One common interpretation of this approach is to learn domain-invariant representations. However, there is a subtle difference between distance-regularization by penalizing the error minimization with a distance as above, and distance-minimization which results in domain-invariant representations. The latter can even lead to deteriorated performance [19]. In contrast, the interpretation as regularization problem opens up a powerful toolbox of mathematical techniques. We take up the technique of balancing stability and approximation in the regularization of ill-posed inverse problems, to tackle the problem of choosing the crucial regularization parameter in distance-regularized domain adaptation. Our approach overcomes the lack of target labels, it satisfies a generalization guarantee, and is (to the best of our knowledge) the first theoretically justified method that allows source and target distributions with disjoint supports. Finally, our approach outperforms or is on par, with the state of the art on the problem of choosing the regularization parameter, on several domain adaptation methods; applied on different datasets.
Broader impact
Many fields, such as manufacturing, personalized medicine or analytical chemistry, have to handle problems of domain shift together with issues of data limitations. These areas can profit from our research, as it provides a principled way of choosing a justified regularization parameter of unsupervised domain adaptation algorithms. Our method provides a high level of trust by applying mathematical techniques with guarantees originally developed in the area of ill-posed inverse problems. However, in domain adaptation in general, one critical point is the bias stored in the source data (e.g. past product, previous patient data, previous spectroscope), since knowledge in this data is used to improve the learning on the unlabeled target data (e.g. new product, new patient data, new spectroscope). If such a bias is present in one of the source domains, the predictions in new target domains might always suffer from this bias. We therefore suggest to not only look at new data in new target domains but more importantly consider dataset bias in already collected labeled source data.
Acknowledgments and Disclosure of Funding
We thank Markus Holzleitner for careful proofreading. We thank the anonymous reviewers for a constructive discussion which formed the basis for the supplementary material’s section about limitations, risks and future developments. The research reported in this paper has been funded by the Federal Ministry for Climate Action, Environment, Energy, Mobility, Innovation and Technology (BMK), the Federal Ministry for Digital and Economic Affairs (BMDW), and the Province of Upper Austria in the frame of the COMET–Competence Centers for Excellent Technologies Programme and the COMET Module S3AI managed by the Austrian Research Promotion Agency FFG. The LIT AI Lab is financed by the Federal State of Upper Austria. We further acknowledge the partial support of the FFG project AutoQual-I. The ELLIS Unit Linz, the LIT AI Lab and the Institute for Machine Learning, are supported by the Federal State Upper Austria. IARAI is supported by Here Technologies. We thank the projects AI-MOTION (LIT-2018-6-YOU-212), DeepToxGen (LIT-2017-3-YOU-003), AI-SNN (LIT-2018-6-YOU-214), DeepFlood (LIT-2019-8-YOU-213), Medical Cognitive Computing Center (MC3), INCONTROL-RL (FFG-881064), PRIMAL (FFG-873979), DL for GranularFlow (FFG871302), AIRI FG 9-N (FWF-36284, FWF-36235), ELISE (H2020-ICT-2019-3 ID: 951847), AIDD (MSCA-ITN-2020 ID: 956832). We thank Janssen Pharmaceutica (MaDeSMart, HBC.2018.2287), Audi.JKU Deep Learning Center, TGW LOGISTICS GROUP GMBH, Silicon Austria Labs (SAL), FILL Gesellschaft mbH, Anyline GmbH, Google, ZF Friedrichshafen AG, Robert Bosch GmbH, UCB Biopharma SRL, Merck Healthcare KGaA, Verbund AG, TÜV Austria, and the NVIDIA Corporation. This material is based upon work supported by the Google Cloud Research Credits program with the award GCP19980904.

Review summaries:
This paper introduces a new error bound for the target domain motivated from Tikhonov-regularized inverse problem. This adoption gives an optimal selection scheme for the error bound of target domain based on distance-regularized domain adaptation, which is a theoretical principle for most domain adaptation methods. The proposed method is evaluated on the three benchmarks on domain adaptation.

The paper proposes the  balancing principle to tackle hyper-parameter selection in unsupervised domain adaptation without requiring target labelled data. By viewing the target error bound as the combination of "  learning errors"  and the distance between source and target domains, the paper designs an algorithm that balances both terms to estimate the regularization parameter.  Generalization guarantee  of the corresponding selected  model is provided. Empirical  evaluations on a simulation dataset and two classical domain adaptation datasets highlight the performances achieved by the proposed method over existing approaches.

This paper studies the problem of choosing a justified regularization parameter for unsupervised domain adaptation. The authors make a link between ill-posed inverse problems and approaches based on a weighted combination of the source error and a distance between source and target feature representations. They propose a framework based on balancing approximations and sampling errors to obtain a target error bound that takes into account a balance between learning errors domain distance. This leads to develop a founded rule for the choice of the regularization parameter which can be applied with source and target distributions with disjoint supports.  A bound on the target risk is provided.  An experimental evaluation of the approach is provided using the Moons toy dataset and the Amazon reviews and DomainNet–2019 benchmark.

In this paper, the authors study the hyperparameter selection problem in the context of unsupervised domain adaptation. While hyperparameter selection is not trivial at all due to the absence of the labeled data in the target domain, the authors employ the balancing principle to draw a connection between unsupervised domain adaptation and ill-posed inverse problems. The proposed method is based on balancing the discrepancy term and the error term, and the joint minimizer is chosen as a good hyperparameter. Notably, this method does not require any assumptions such as covariate shift and support matching as supposed in the existing researches.