The balancing principle for parameter choice in distance-regularized domain adaptation
Authors: Werner Zellinger
Natalia Shepeleva
Marius-Constantin Dinu
Hamid Eghbal-zadeh
Hoan Duc Nguyen
Bernhard Nessler
Sergei Pereverzyev
Bernhard A. Moser
Venue: NeurIPS 2021 Poster (2021)
Keywords: domain shift
unsupervised domain adaptation
model selection
regularization
inverse problem

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.

The balancing principle for parameter choice in distance-regularizze domain adaptation
Werner Zellinger 1.
Natalia Shepeleva'
Marius-Constantin Dinu
Hamid Eghbal-zadeh 4.3
Duc Hoan Nguyen
Bernhard Nessler
Sergei Pereverzyer
Bernhard A. Moser
Software Competence Center Hagenberg GmbH
Institute for Machine Learning, Johannes Kepler University Linz
*Dynatrace Research
Institute of Computational Perception, Johannes Kepler University Linz
'LIT AI Lab, Johannes Kepler University Linz
Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences werner wnw.zzllllnggrrrcchh.oo
Abstract
We address the unsolved algorithm design problem of choosing justified regular- ization parameter in unsupervised domain adaptation. This problem is intriguing no labels available in the target domain. Our approach starts with the obser- vation that the widely-use used method of minimizing the source error, penalized by a distance measure between source and target feature representations, shares charac- teristics with regularized ill-posed inverse problems. Regularization parameters in inverse problems optimally chosen by the fundamental principle of balancing approximation and sampling errors. We use this principle to balance learning errors and domain distance 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.
target error bound. As a result, we obtain theoretically
Introduction
Domain adaptation uses the knowledge in source domain to improve the performance of an algorithm related target domain [1]. In particular, domain adaptation tackles domain shifts in machine learning applications: Medical diagnostic systems should 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, focus unsupervised domain adaptation where labels only available in the source domain.
There are mainly two types of approaches for unsupervised domain adaptation: importance weight- ing 2
12 13]. In this work, we focus on feature representation learning which goes beyond classical importance weighting by allowing target distribution with support outside of the source distribution. The core idea behind feature repre- sentation learning approaches is to map the data into new feature space where the source and target
3
4
5
6
7 and feature representation learning [ 9 10
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

0.4
App
satisfied. sounce dasn
000100 dass
target
30"d 10"1 10"
repolartzation parameter
Figure 1: Unsupervised domain adaptation on Transformed Moons. Left: Target data (black dots) partially outside of the support of the source data (blue +, orange x). The common assumption of bounded density ratio is violated in large regions. In contrast, all our assumptions
Our method identifies the best parameter of a domain adaptation algorithm [16] (green solid) which improves training source data only (red dashed). Right: Regularization parameter (x-axis) which penalizes a distance (25] (purple) leading to models with different source error (blue) and target error (black). Importance weighted validation
(IWV) shows the smallest error (red) for models without domain adaptation (arwv = 0). In contrast, our approach identifies the optimal parameter (OBP- 1).
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 [1S 16
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.
77 18
While remarkable theoretical results have been achieved which quantify the generalization ability of domain adaptation models 88 [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 assump- tions 23). Typical approaches are fixing the regularization parameters [12], minimizing the source
error [16]. balancing the source eтror and a distance [17], multiplying fixed weighting parameter (e.g. (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] 22 23 One common problem shared among all these approaches is that they all can fail if the density ratio unbounded. Such unbounded density ratio is typical for many of the high dimensional problems considered in machine learning [9 c.g. see Figure 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 principled method for choosing distance distance-penalizingg parameters of feature representation learning approaches for unsupervised domain adaptation. Our approach starts with the observation that the destance-regularizatio setting of domain adaptation shares characteristics with regularized ill-posed inverse problems (see Table D]. In inverse problems, the regularization parameter can be optimally chosen by the fundamental bulancing principle which optimizes an approximation-sanne sample (bias-variance) trade-off [26] 28). We apply this principle for balancing domain distance and learning errors of target error bounds. In particular,
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 g 22 19 21]. To the best of our knowledge, the BPDA is the first principled method for parameter choice 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.
2 Summary of results
Notation Let X' C I be an input space and y be discrete label space. Following the classical setting of unsupervised domain adaptation (25), we consider two datasets: A source dataset (x, = ((x1, ((e..s((21))..... (z,, 49 (xx))) E (X' x 3" with inputs ......,. F. independently drawn according to some source distribution (Borel probability measure) ps on and labeled according to some labeling Sunction (ss X + y and, an unlabeled largel dataset x' (x',,..,,.7)) Ia) E X with elements independently drawn according to some target distribution pr on X. Throughout this work, we focus on loss functions L y 3 - [0, oo) which satisfy [y,, y) = 0. For example consider the 0-1 loss L(y1, 3/2 := [yv * y2l. where [P]] is iff the predicate P is true and 0 otherwise, and the quadratic loss function L(y1. = 1y1 y2l? 2 We denote the source error by Es(f) Es(f, (ff,s)) Is) with cross-error defined as Es(f. == E Eawps (L(f()),
and its empirical sample estimate by Es(f) (s(f, Is) with Eg (f. = (x.)) ((:)). We denote the analogously defined target error by Ex (f), target cross-error by (f. and its empirical sample estimate by (f) with empirical cross-error (f. Throughout this work, we focus on target cross-errors Ey .) 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: representation mapping é E & C {ó: : X' + RJ into some representation space R C 1 and classifier g E G C {g R + }}. Loosely speaking, the aim is to find a mapping & under which the source representations ((x) :=
(ó(x1)...., (xx,)) and the target representations o(x') := (Φ(=1),... .(x))) appear similar, and, at the same time, enough information is preserved for prediction [14] by g(z). A common approach
to realize this aim is to solve the following objective function [19
min NEG.0E
Eo Φ) + d()(x),)(x'))
where is a distance measure between source and target representations and a E [0, oc) is a paramete D Good choices for d in Eq. (T) have been identified to be the Wasserstein distance
29 30),
the Maximum Mean Discrepancy [1 32 moment distances [17
33
18
34 35 36), adversarially
learned distances [16 37 and other measures of divergence [3 39 19
20
For some a E oo), let Ja da denote the minimizer of Eq. I Given an increasing sequence of parameters 0i,...,, O'w E [0, oo) with 0i O, the problem studied in this work is to choose the parameter a in the sequence a1,..., Ohe with the lowest target error (g(g. o Φa).
Problem
Approach Our approach consists in minimizing target error bound which satisfies the form
(y o @a) S D(a) + E(ax)
25 by quantifying a distance between source and target data representations and E(a) comprises different learning errors. We assume that E(a: bounded by some constant B > 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, F(aa) cannot be directly estimated. The BPDA overcomes this problem by new criterion for estimating the value of balance between the normalized terms E(a) and D(a). The BPDA is detailed in Algorithm I
where D(a)) gives notion of domain distance (cf.
Properties of Algorithm
1
The BPDA has the following striking properties.
* The BPDA is general procedure which can be instantiated by any error bound of the form in Eq. (2). See Section 4 and Section for its application based on two different target error bounds 12 20).
1 For simplicity, we use laheling functions instead of the more general concept of conditional distributions. For simplicity omit further regularization of and g.
3

---

In contrast to state-of-thh-ar methods, the BPDA does not assume target labeling function IT that is equal to the source labeling function is (covariate-shiff assumption) and does 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 SaBr POBP identified by the BPDA satisfies a generalization bound, see Section 4 If the learning errors term E(a) is non-decreasing, then the target error of gopp o Oopp 18 only a constant factor away from the minimum minaef0,os) D(a) + E(a) of the instantiation bound in Eq. (2)
Algorithm 1: Balancing principle for domain adaptation (BPDA)
Input
Increasing sequence of parameters .i,.... aw E [0, 00) with 01 0 and minimizers f1 == 9a. .a...... fw == Ja... o oa. of Eq.
Output Initialization::
:Parameter ogp solving the problem above.
for i 1, ................................ do
Compute empirical cross-error fj) and domain distance D(a;) for all
== ;=1......-- if (T. ff) S D(as) (2+ D(o)) for all ,...., i then S: Su {a;}
2B
end end return
tOpp max S
Besides the properties above, the BPDA outperforms or is on par with 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. IT are sometimes interpreted as learning domain- invariant representation. Note that the minimization of d d(@(x). 6(x')) in Eq. (I to achieve o(x) ø(x') differs from the conception as regularization 440 means unjustified weer-ennalization 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 ill- posed inverse problems. The balancing principle has origins regression estimation and has been introduced in the context of ill-posed problems (27] and in supervised learning with kernels [42). Following this line 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 the context of unsupervised domain adaptation importance weighttd cross-valides valiidtioo (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 [ 43 which aims at balancing the source error and a distance between source and target data representations. However, this method is not theoretically justified ignores the minimal combined error of a classifier
In fact, minimization of the distance
(66 devoted to nonparametric
representations as defined in []. Nevertheless, 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. 22
19
20
21 34).
3 Preliminaries
Sampling error bound Throughout this work, we generically denote an upper bound on the sampling error by Te, [0, oo), which is assumed to hold true with probability at least
(f((f (r( S nt..55
(3)
The bound g/,.g.8 depends on the sample size i, the function class G and the constant o, and, is assumed to satisfy T). 0 for co.

---

Two accompanying target error bounds In the seminal works 8 25 binary classification y := {0, 13 with 0-1 loss is considered and it is shown that the following bound holds for all symmetric function classes G (g E G probability least 1 ò:
= 1 - g G). Φ E 4, E 9 and datasets of equal size 8 = t with
()(god) S Seslg x) + Am( + (xxo(((x), + 11.65.5
(4)
where
E 1[(((E) 1 r(2)))
xx) =
min f.f'eG
Σ
= -
(5)
the empirical GLG -iv-riieegeence
and Ag(Ø) inf yeg o Ø) + ef o o)) 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 17.
In (20). the bound in Eq. is generalized multiple classes (1,..., }}} and scoring functions H C (h: R + ]. where the output on each dimension indicates the confidence of prediction. For some h H. let denote by 9h R V, arg ( h (o(z)) with (2) being the i-th component of h(2). Let further er denote the target error based on 0-1 loss. Then, with probability at least 1
(gh o Φ) S 2 (h o 6) + (x( - d (o(x), 6(x)) + 7s4.,
-
(6)
where ((p) (h) == fx op (s) dz) with pa (z, (s) == 1/2(h Sarth,, and (z) being 1 s/p if < x < 0f x and 1 otherwise. Further, the target terms T. pr, br
(a
(x))
defined analogously to S,ps, ls. respectively; the combined error is defined by (x(Ø)
infnen(Es (ho + c/ (h)), and the empirical margin disparity discrepancy (MDD) is given by
Jot (x'))
Σ Ap ph (2;, gh) - 1 Σ Ap ph (T',
max KEN
i=1
Similarly to Eq. 44) the source error can be further estimated by an empirical error and the combined error (x( cannot be estimated based on given data.
Balancing principle for regularized inverse problems Let H and I. be two Hilbert spaces and V: H >> K. be linear operator. Then, the linear inverse problem associated
given datum g E IC is to find some function f satisfying ff 9. see e.g. [45] 46 40 [1] and references therein. In general, the above problem is ill 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
fN E arg min [VV - -lll
JEN.
However, especially in the of noisy operator V. and noisy data continuous dependency data becomes an important issue which can be restored using Tikhonov regularization 455
fa E arg min [ FEH
Olk + Il
(8)
In many cases, probabilistic bounds on the error can be proven
llfa - full & S(a) + A(a)
(9)
where S(a:) is called sampling error made by considering noisy approximations V and g of V and respectively, and, A(a) is called approximation error originating from adding the regularizer Il Commonly, S(a.) decreases while A(a) increases with increasing We refer to (2) for
detailed examples. The fact that ((a) decreases and A(a) increases motivates the so-called bulancing principle which aims at computing a" such that S(a*) = A(a*) [26 27 42 41 28) As result, the
balaneing principle provides a procedure for approximating a" without having access to the values of
A(a). The balancing principle obtains optimal error rates in many settings 47 48 49 42 28
5

---

Balancing principle for domain adaptation
In the following. present the mathematical foundations of Algorithm in two steps. In first step, in Subsection 4.1] we state our assumptions and detail our idea of choosing the value of balance between terms in target error bound. In second step, Subsection 4.2 we propose 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 | to be accurate.
4.1 Balancing terms in a target error bound
Assumptions In the following, let Ja Oa be minimizer of Eq. I and assume that target error bound holds which is the form given by Eq. ( Our approach is based on the plausible
assumptions (a) that the function + E(a) is continuous and bounded by some constant B > 0, and (b) that the function a + D(a) is continuous, non-increasing and non-degenerate, i.e. D(0) > 0. We further make the technical assumption (c) that lim D(al/DO) ((o) supae(0,,s) E(a)/B. B. Note that (c) is satisfied in most standard cases, where D(a) for a, f - oc. For example consider the two accompanying target error bounds in Section as discussed at the end of this section.
Bridging regularized inverse problems and domain adaptation Under the assumptions above, shares characteristics with the setting of regularized inverse problems as described in Section Indeed, the Tikhonov regularizer If in Eq. (8) is similarly applied as the distance-regularrizerd
our domain adaptation learning setup in Section 2
(( dx((x). Φ(x') in Eq. (.. In addition, error bounds for inverse problems as given by Eq. (9) show similar form as target error bounds following Eq. (2)
The sampling error S(a) in Eq. 99 decreases similarly the domain distance in Eq. 2 and the
approximation error A(a) in Eq. (9) cannot be estimated similarly to the learning errors E(a) in
Eq. (2). However, in the domain adaptation setting, the term E(a) does not necessarily increase. We approach this issue by considering the least non-decreusing majorant of E(a).
Definition (Least non-decreasing majorant [50)). The least non-decreasing majorant of E(a) is given by ((a) == [u (3))
Further upper bounding Eq. by
(g da) S D(a) + E(a) & D(a) + E(a)
(10)
results in form which satisfies all properties needed to apply the balancing principle, see Table
[
Table I: Correspondences between regularized inverse problems and domain adaptation which allow apply the balancing principle. See Section 3 for details on the inverse problem setting.
Tikhonov inverse problem
Distance- domain adaptation
Ja arg f - Olk + 1151 /EH
Ia o O. E arg min Es o 6) + a d((((x)) o(x'))
gE9
fullx S S(a) + A(a)
Eg o Qa) < D(a) + E(a)
decreasing sampling error S(a)
decreasing domain distance ((a)
increasing approximation error A(a) A(a) not estimable
bounded learning errors E(a)
E(a) not estimable
balance A(a*) S(a*)
balance D(a") F(o²)
D(0) B
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 a achieving
D(a*)
E(a*)
(11)
D(0)
B
The normalizing factor 1/D(U) the left-hand side of Eq. (11) and the factor 1/B ensure that the two curves D(a)/D(O) and B(a//B intersect. In particular, the existence of a follows from the

---

D(a)
D(0)
Forul
08
E(a)
0.7
B
0.8
E a
04
B
03
62
OHp
a²
repubrustion paramadar
Figure 2: Left: The BPDA in Algorithm overcomes the problem of the unknown learning errors term E(a) by approximating a" which balances P(o)/D(0) (green) and the least non-decreasing majorant B(e)/B (red dashed) of E(a//B (red). Right: Average and standard deviation over 10 repetitions of estimated learning errors E and the domain distance D of the accompanying target error bound Eq. (4) for the models computed by Eq. ! with the Maximum Mean Discrepancy [5I]
as distance. The BPDA chooses the value app 10 near the estimated balancing value.
assumptions (c) above. See Figure 2 for an illustration. Algorithm approximates a". If E(a) is non-decreasing and the bound in Eq. 10) holds with equality, then the rate of the target error (r(sa- Φar) is optimal, i.e. (g(ga- ) ) is only a constant factor away from the optimum a0)) (go, &a). See the supplementary material for proof. This optimality property is shared with related regularization settings
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
take (a)) == dg (x), (x(x)) + n.g.55 and E(a) := (s( o oa) + (g( it is natural to
assume (a) to decrease with a, especially for adversarial approaches which penalize the empirical GAG- -iv-divereence وووو (ø(x), (xx)), see [16]. also holds that E(a) < for all E oo). For the balancing value to exist for large sample size t, we need to verify that D(a)/D(o) + 0 for 1, a - xo. However, this satisfied for most function classes 4 since can be assumed that constant function Φ x + c which achieves dg (o(x), d(x') = 0 is contained in Q. That is, dang( (x)),, ((x))) 0 can be achieved for - co and consequently D(a)/D(O) - 0 for 1, co.
Consider now the bound in Eq. (6). By using D(a) == The (0. da (x)) + 7,+,,,,6 E(a)
(()) (h o ②) + Ax (Φ) 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 [ we empirically investigate the performance our method based on our two accompanying target error bounds. However, us first show how we can overcome the problem of the non-computable term F((a))
4.2 Approximation of balancing value
Unfortunately, E(a) in Eq. ( usually contains information about the target labeling function ly and a" can therefore not be calculated directly.
Balancing principle estimate We propose the following criterion for estimating a" which is realized by the BPDA in Algorithm[]
Definition 2 (Balancing principle estimate). Let a1...... . Owo w E N with a₁ be an increasing sequence of values in [0, oo) and denote by f. = Ia, o Da.. Then, the balancing principle estimate is
2B ::: (f..)) D(ay) (2 D(0) - m1..55
QBP = max
03 Vje fI.
(12)
The balancing principle estimate in Definition is based on checking an upper bound on the empirical cross-error (ft, fz) between two models ft. f, resulting from two different values ag ag of the
7

---

regularization parameter, respectively. The empirical stoss-erroi does not contain information about the unknown target labels (z(2),. ...i).....p. .,f((( and can be computed based on available data. The main reason why we expect the balancing principle estimate OBP to be near to the balancing value in Eq. (11 can be explained as follows.
Lemma 1. Let ó E (0, 1), a, 3 E [0, oo) and denote by Sa = Da. 1f0 S S S a² then the following holds with probability at least - 6:
2B D(0) + 11,9.5
Ef( fo) = D(a) 2
(13)
Lemma D (see the supplementary material for its proof) shows that the inequality in Eq. 12 is
satisfied if aj S a; 1 a" This implies that a; > a² if the criterion is violated for some aj S dq.-
Consequently, the maximum onp as defined in Eq. [12 from an increasing sequence , Oan
which violates Eq. 113 for some j E {l,..., } can be assumed to be near to a².
Generalization guarantee The model Japp Dagr obtained by the BPDA in Algorithm 1 [attssiiiss the following generalization guarantee.
Theorem 1. Let E (0,1) and a1.-.., Oww [0, 00), 01 = be an increasing sequence such that D(an)= S q D(a++1)
(14)
for all 1 E (1...... 1} and some q 1. Then, with probability at least -
3B
ST (yoar )oar) S D(a") 3++ D(0)
q + 73.9.88
(15)
Theorem [ shows that the target error of the model goup o &apr identified by the BPDA has the same error rate as D(a") for - oc. Moreover, if the optimum inl en] D(x)) + F((a) achieved, then the error rate is optimal in the sense that Fr @GBP) is only constant factor worse than the minimum g]o.c (ax) + (ax). The constant factor is given by (3 + //B/D()) q qmxx {D(0/B, s, 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. B. The constant can be derived by bounding ( Eq. (15) detailed in the supplementary material. If E(a) is increasing and the instantiation bound in Eq. (2) is tight, i.c. it holds with equality, then the error ET (gour Mapp) ) is only a constant factor worse than the optimal error inf (0) (g (.).
well known that appropriate assumptions as given above are needed for successful domain adaptation (52 However, in practice, target error bounds are often not tight and optimality cannot be guaranteed. In the following section, therefore investigate the performance of our method on benchmark datasets based on our two accompanying target error bounds.
5
Empirical evaluations
We empirically investigate the performance of our approach based on two target error bounds, two parameter selection methods, three datasets and different domain adaptation methods
5.1 Setup
Given a domain adaptation algorithm that follows Eq. (I) the goal is identify the regularization parameter a from the sequence 0, 10-6, 10 10-5,10-5 ...., 10x, 10a 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 unbounded in large regions, see Figure 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- ooods unigrams and bigrams with binary labels: label ( if the product is ranked by 1 to 3
'The source-code be found https:tp//// httpp::/ggtthb..... htwp::hhub...oootttttittti

---

stars, and label 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-200 having 345 classes, and an average count of 288 images per class, i.c. 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 MiniDomainNer. See the supplementary material for the dataset statistics.
dataset consisting of six different domains, each
Balancing principle for domain adaptation We apply the BPDA in Algorithm based on the two accompanying target error bounds described in Section On the two-class datasets Transformed Moons and Amazon Reviews, we apply the BPDA based Eq. 44) We set the domain distance D(a) := عدوه (Ø (x), dn (x')) + 77,,g& & and approximate its value by 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(a)= ( (xx(xx) (x))) + 1,,66,7 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 GI.G.8. We repeat each domain adaptation model training several times. The if-statement in the BPDA in Algorithm [ is considered violated, if there is a violation of the statement for 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 importance weighted validation Bl (IWV). We follow 23 and use held-out validation, i.e. we hold out 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 classifier trained to separate source from target data. The classifier tuned separately for each task and dataset such that its validation misclassification error is at most 0.05. For MiniDomminnNe we compute the importance weight based on the features of the pre-trained 18 (58). The fourth baseline is deep embedded
validation [23] (DEV) which solves the unbounded variance issue in IWV. Following 23] DEV is applicd on the features of the neural networks.
Domain adaptation methods In our experiments, we use three domain adaptation techniques. Domain-adveersariil neural networks (16) (DANN), Maximum Mean Discrepancy [59] [5] (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 F,, the domain distance 1) and the least non-decreasing majorant F. on the Transformed Moons dataset. In particular, the term E is computed using the (in unsupervised domain adaptation unknown) target labels for training 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.
5.2 Results
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 ((a) tend to be non-increasing and the technical assumption D(al/ < s0)) B(a)/n B is satisfied for a 2 10 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 aBp in Figure 2 are the maximum values for

---

which the mean curves of B(a)/B B are smaller than the mean curves of D(a)/Doo) That is, the BPDA described in Algorithm 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 picks nearly the optimal value (see 2).
Comparative study Average values of our empirical evaluations on Transformed Moons and Amazon Review are summarized in T For the full tables on Transformed Moons, Amazon Reviews and MoniDomainNNt, 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.
Table 2: Average target misclassification error with best values in bold. See the supplementary material for the full results for all datasets and domain adaptation tasks.
Transformed Moons
Amazon Reviews
Method
SO
IWV
DEV
BPDA
TB
SO
IWV
DEV
BPDA
TB
MMD
0.21
0.20
0.34
0.16
0.16
0.27
0.25
0.25
0.22
0.21
DANN
0.18
0.18
0.17
0.12
0.12
0.28
0.28
0.32
0.27
0.24
CMD
0.21
0.20
0.19
0.19
0.18
0.28
0.24
0.25
0.21
0.21
Avg.
0.20
0.19
0.23
0.16
0.15
0.28
0.26
0.27
0.23
0.22
6 Conclusion and future work
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 weighted by distance measure between source and target representations. One common interpretation this approach is to learn domain- invariant representations. However, there is a subtle difference between cetrunce-regularizatin by penalizing the error minimization with distance as above, and distance-minimizanee minimization which results in nomain-invarian representations. The latter can even lead to deteriorated performance [19]. In contrast, the interpretation 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, tackle the problem of choosing the crucial regularization parameter in distance-regullarized 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 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 manufacturing, personalized medicine analytical chemistry, have to handle problems domain shift together with issues of data limitations. These areas can profit from our re- search, 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 iol-posed inverse problems. However, in domain adaptation in general, one critical point is the bias stored in the source data (c.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 bias is present in of the source domains, the predictions in 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.
10

---

Acknowledgments and Disclosure of Funding
We thank Markus Holzleitner for careful proofreading. We thank the anonymous reviewers for a con- structive 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 the frame of the COMET-Competents 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-) 111-2008---YOU-22111 YOU-2122, DeepToxXeo (LIT-2017-3-YOU--0033 AI-SNN (LIT-2018-6 -OUUU221)4, DeepFlood (LIT-2019-8) ---0011---------1-111 YOU-213), Medical Cognitive Computing Center (MC3), INCONTROL-RA. (FFG-88 1064), PRIMAL (FFG-873979), DL for GranularFlow (FFG- 871302), AIRI FG 9-N (FWF-36284, FWF-36235), ELISE (H2020-ICT-2019-3 ID: 951 AIDD (MSCA-ITN 2020 ID: 956832). We thank Janssen Pharmaceutica (MaDeSMart, HBBC.011.22877 Audi.JKU Deep Learning Center, TGW LOGISTICS GROUP GMBH, Silicon Austria Labs (SAL), FILLL Gesellschaft mbH Anyline GmbH, Google, ZF Friedrichshafen AG, Robert Bosch GmbH, UCB Biopharma SRI., 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.
Centers for Excellent Technologies Programme and the COMET
References
[1] Sinno J Pan and Qiang Yang. A survey transfer learning. IEEE Transactions Knowledge and Data Engineeringn, 13110):33451335 2010.
[2] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelihood function. Journal of Statistical Planning and Inference, 90(2):227-244, 2000.
[3] Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul V Buenau, and Motoaki Kawan- abe. Direct importance estimation with model selection and its application to covariate shift adaptation. In Advances in Neural Information Processing Systems, pages 1433-1440, 2008.
[4] Jiayuan Huang, Arthur Gretton, Karsten M Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. In Advances in Neural Information Pro- cessing Systems, pages 601-608, 2007.
[5] Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in Neural Information Processing Systems, pages 442-450, 2010.
[6] Corinna Cortes, Mehryar Mohri, and Andrés M Medina. Adaptation based generalized discrepancy. Journal of Machine Learning Research, 20(1):1-30, 2019.
[7] ER Gizewski, L Mayer, BA Moser, DH Nguyen, Pereverzyev Jr, SV Pereverzyev. N Shepeleva, and W Zellinger. On regularization of unsupervised domain adaptation in RKHS. RICAM- Reports, 2021.
[8] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in Neural Information Processing Systems, pages 137-144, 2007.
[9] Hal Daumé III. Frustratingly easy domain adaptation. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 256-263, 2007.
[10] Sinno Pan, Ivor W Tsang, James T Kwok, and Qiang Yang. Domain adaptation via transfer component analysis. IEEE Transactions on Neural Networks, 22(2):199-210 2011.
[11] Boqing Gong, Kristen Grauman, and Fei Sha. Connecting the dots with landmarks: Discrimina- tively learning domain-invariant features for unsupervised domain adaptation. In Proceedings of the International Conference Machine Learning, pages 222-230, 2013.
11

---

[12] Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell. Deep domain confusion: Maximizing for domain invariance. arXiv preprint arXiv:141.33474, 2014.
[13] Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. In Proceedings of the International Conference on Machine Learning, pages 2839-2848, 2016.
[14] Joaquin Shionero-Candelas Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset Shift in Machine Learning. The MIT Press, 2009.
[15] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. In Proceedings of the International Conference Machine Learning, pages 97-105, 2015.
[16) Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarin training of neural networks. Journal of Machine Learning Research, 17(Jan):1-35, 2016.
[17] Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In Proceedings of the European Conference Computer Vision, pages 443-450 2016.
[18] Werner Zellinger, Thomas Grubinger, Edwin Lughofer, Thomas Natschläger, and Susanne Saminger-Plasn Paaaing Central moment discrepancy (emd) for domain-invarian representation learn- ing. International Conference on Learning Representations, 2017.
[19] Fredrik D Johansson, David Sontag, and Rajesh Ranganath. Support and invertibility in domain-invariant representations. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 527-536, 2019.
[20] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In Proceedings of the International Conference Machine Learning, pages 7404-441 7413, 2019.
[21] Victor Bouvier, Philippe Very, Clément Chastagnol, Myriam Tami, and Céline Hudelot. Robust domain adaptation: Representations, weights and inductive bias. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2020.
[22] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. Proceedings of the Annual Conference on Learning Theory, 2009.
[23] Kaichao You, Ximei Wang, Mingsheng Long, and Michael Jordan. Towards accurate model se- lection in deep unsupervised domain adaptation. In Proceedings of the International Conference on Machine Learning, pages 71 7124-7133, 2019.
[24] Wouter M Kouw, Jesse H Krijthe, and Marco Loog. Robust sypportance-weighte cross- validation under sample selection bias. In IEEE International Workshop on Machine Learning for Signal Processing, pages 1-6. IEEE, 2019.
[25] Shai Ben-Davie John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine Learning. 79(1-2):151-175, 2010.
[26] OV Lepskii. On a problem of adaptive estimation in gaussian white noise. Theory of Probability & Its Applications, 35(3):454 1991.
[27] Alexander Goldenshluger and Sergei V Pereverzev. Adaptive estimation of linear functionals in hilbert scales from indirect white noise observations. Probubility Theory and Related Fields, 11((2)169911)) 2000.
[28] Shuai Lu, Peter Mathé, and Sergei V Pereverzev. Balancing principle in supervised learning for general regularization scheme. Applied and Computational Harmonic Analysis, 48(1):123-148, 2020.
12

---

[29] Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamoniy. Optimal transport for domain adaptation. IEEE' Transactions on Pattern Analysis and Machine Intelligence.
2017.
[30] Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In Proceedings of the International Conference on Machine Learning, pages 3076-3085, 2017.
[31] Mahsa Baktashmotlagh, Mehrtash T Harandi, Brian C Lovell, and Mathieu Salzmann. Un- supervised domain adaptation by domain invariant projection. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, pages 769-776, 2013.
[32] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I Jordan. Unsupervised domain adaptation with residual transfer networks. In Advances in Neural Information Processing Systems, pages 136-144, 2016.
[33] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge a local nash equilibrium. In Advances in Neural Information Processing Systems, pages 6629-6640, 2017.
[34] Werner Zellinger, Bernhard A Moser, and Susanne Saminger- Platz.. On generalization in comennt-based domain adaptation. Annals of Mathematics and Artificial Intelligence, 89)):333 369, 2021.
[35] Werner Zellinger, Bernhard A. Moser, Thomas Grubinger, Edwin Lughofer, Thomas Natschläger, and Susanne Saminger-Platz. Robust unsupervised domain adaptation for neural networks via moment alignment. Information Sciences, 483:174-198 191, May 2019.
[36] Werner Zellinger and Bernhard A Moser. On the truncated Hausdorff moment problem under Sobolev regularity conditions. Applied Mathematics and Computation, 400:126057, 2021.
[37] Eric Tzeng. Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. Proceedings the pages 7167-7176. 2017.
the IEEE Conference on Computer Vision and Puttern Recognition,
[38] Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. Proceedings of the International Conference on Machine Learning, pages 10-18, 2013.
[39] Fuzhen Zhuang, Xiaohu Cheng, Ping Luo, Sinno Jialin Pan, and Qing He.. Supervised represen- tation learning: Transfer learning with deep autoencoders. Proceedings of the International Joint Conference on Artificial Intelligence, pages 41 4119-4125 2015.
[40] Heinz W Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science& Business Media, 1996.
[41] Shuai Lu and Sergei V Pereverzev. Regularization theory for ill-posed problems: selected topics, volume 58. Walter de Gruyter, 2013.
[42] Ernesto De Vito, Sergei V Pereverzyev, and Lorenzo Rosasco. Adaptive kernel methods using the balancing principle. Foundations of Computational Mathematics, 10(4):455-47, 2010.
[43] Ramin Nikzad-Langerode Werner Zellinger, Susanne Saminger-Platze and Bernhard A Moser. Domain adaptation for regression under beer-lambert's law. Knowledge-Bass Based Systems, 210: 210:106447, 2020.
[44] Daniel Kifer, Shai Ben-David, and Johannes Gehrke Detecting change in data streams. In Proceedings of the Thirtieth International Conference on Very Large Data Volume 30, pages 180-191. VLDB Endowment, 2004.
[45] Andrei Nikolaevich Tikhonov. On the solution of ill-posed problems and the method of regularization. In Doklady Akademii Nauk, volume 151, pages 501-504, 1963.
[46] CW Groetsch. The theory of tikhonov regularization for fredholm equations. Boston Pitman Publication, 1984.
13

---

[47] Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco. On regularization algorithms in learning theory. Journal of complexity, 23(1):52-72, 2007.
[48] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
[49] Steve Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their approximations. Constructive approximation, 26(2):153-172, 2007.
[50] Gord Sinnamon. Transferring monotonicity in weighted norm inequalities. Collectanea Mathematica, pages 181-216, 2003.
[51] Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(3):723-773, 2012.
[52] Shai Ben-David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 129-136, 2010.
[53] John Blitzer, Ryan McDonald, and Fernando Pereira. Domain adaptation with structural correspondence learning. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 120-128, 2006.
[54] Minmin Chen, Zhixiang Xu, Kilian Weinberger, and Fei Sha. Marginalized denoising au- toencoders for domain adaptation. Proceedings of the International Conference on Machine Learning, pages 767-774, 2012.
[55]
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair auto encoder. International Conference on Learning Representations, 2016.
[56] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE International Conference on Computer Vision, pages 1406-1415, 2019.
[57] Steffen Bickel, Michael Brückner, and Tobias Scheffer. Diseriminative learning for differing training and test distributions. In Proceedings of the International Conference Machine Learning, pages 81-88, 2007.
[58] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[59] Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex J Smola. kernel method for the wwo-sample-proble Advances in Neural Information Processing Systems, pages 513-520, 2006.
14


Reviews:
[{"review_id": "yuD3uFd-wTI", "reviewer": "Reviewer_mWtP", "summary": "In this paper, the authors study the hyperparameter selection problem in the context of unsupervised domain adaptation.\nWhile 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.\nThe proposed method is based on balancing the discrepancy term and the error term, and the joint minimizer is chosen as a good hyperparameter.\nNotably, this method does not require any assumptions such as covariate shift and support matching as supposed in the existing researches.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the problem studied in this paper is pretty interesting.\nHyperparameter selection is one of the central obstacles when unsupervised domain adaptation (UDA) is applied in real-world scenarios.\nWhile this problem itself has been actively studied as a matter of course, the proposed approach sheds new light on the estimation methodology to deal with \"inaccessible\" in the common domain adaptation bounds---the joint error minimizer.\nThis obstacle was mitigated by the balancing principle estimate (Definition 2), and in particular, by means of Lemma 1.\nIn my opinion, this is a pretty interesting theoretical result in the UDA context.\n\nI'm overall positive about this paper, but let me put a few remarks that could help the authors to improve the paper.\n\n**Clarity issue**:\nI would like to see the following points improved.\n- The definitions of the discrepancy and error terms $D(\\alpha), E(\\alpha)$ is ambiguous as of Section 2, which may lead to some potential misunderstanding. For example, \"... cannot be estimated similarly to the learning errors $E(\\alpha)$\" (l.187), but I thought the error term only depends on the source domain, which turned out to be false at l.203 and I understood that $E(\\alpha)$ contains the joint error $\\lambda_\\mathcal{G}$ as well.\n- Why do we put the balancing condition as in Eq. (11), not $D(\\alpha^*) = E(\\alpha^*)$ as in the case of inverse problems?\n- (l.136) \"Using Eq. (3), the source error can be further upper bounded by the empirical source error\": This is not clear because Eq. (3) is a concentration bound for the target domain. Do you assume the similar bound for the source domain, too?\n\n**About the domain adaptation bound**:\nIn Eq. (4), the common domain adaptation is shown.\nAs far as I understand (please let me know if the following is wrong), the DA bound based on $\\mathcal{G}$-divergence is not correct, although it is presented in [7].\nIndeed, the proof of Theorem 1 in [7] upper bounds $\\mathcal{H}\\Delta\\mathcal{H}$-divergence by $\\mathcal{H}$-divergence, which does not hold in general.\nTo make it precise, we need to bound by $\\mathcal{G}\\Delta\\mathcal{G}$-divergence as done in Theorem 2 in [27].\n\n----\nA few minor comments.\n- (l.127) \"the sampling error by $\\eta_{t,\\mathcal{G},\\delta}$\" instead of \"the sampling error by $\\eta_{z,\\mathcal{G},\\delta}$\"?\n- (Eq.(6)) the argument in $\\varepsilon_S^{(\\rho)}$ should be $g_h \\circ \\phi$?\n- (l.232) The numbering of Lemma is not aligned between the main text and the supplementary material. Could you align or mention it at least?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately mentioned potential social impacts in the concluding section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "three hours"}, "extra_text": {}}, {"review_id": "HdbdIks4xM", "reviewer": "Reviewer_VzZx", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Overall, the paper is well written. In particular, the rationale behind the proposed method is justified. Empirical evaluations support these intuitions and show how they contribute Unsupervised Domain  adaptation (UDA).\n- Specifically, the paper tackles the challenging task of model selection in UDA without having access to labelled data from target domain. As such, the addressed problem is of interest for practitioners. To achieve the hyper-parameter  selection in UDA, the paper adapts to DA the balancing principle, a framework used in ill-posed inverse problems.\n- The main pursued idea is to estimate the regularization parameter such that the domain-gap distance is balanced with the learning errors occurring in the target error upper-bound. As not all terms in the learning errors are computable, a surrogate is used to attain the balancing. It  consists in computing the cross-errors over $f_i, f_j, j=1,  \\cdots, i-1$ on target data and in ensuring that  the cross-errors are lower than a specified bound depending solely on the domain distance. As a model $f_i$ is related to a hyper-parameter $\\alpha_i$  (the $\\alpha_i$s  are set increasingly), the best hyper-parameter is the maximal of such $\\alpha_i$s. Interestingly the procedure is agnostic to the  theoretical target error bound. As a concept  of proof, the paper investigates the use of two existing target error bounds to illustrate the benefit of the approach. Finally the rationale behind the proposed approach is supported by a generalization guarantee.\n- The paper  claims that the proposed method, BPDA, may account for label shift (lines  99-102). However  this assertion is not investigated in the experimental evaluations  or supported by a theoretical  analysis. Note that in UDA,  there exists target bound that  handles the label shift (see [a]). Is this kind of bound more suitable to BPDA to deal with generalized shift? \n- The considered target error in Equation (4) is  based on the 0-1 loss that offers the nice triangle inequality property (used to establish Theorem 1). However,  in practice when training the pursued model $f$  one rather relies on surrogate function of the 0-1 loss. How this fact impacts the consistency of estimated hyper-parameter? In the same vein does the  margin loss, used in the the target bound (6), satisfy the properties stated lines 66-68?\n-  $D(\\alpha)$ is assumed  to  be non-increasing. In  practice when training the UDA model in a deep learning setting,  the assumption may not hold true. Is this  detrimental for the proposed UDA model selection?\n- The paper should discuss the tightness of the bound (15).\n- In the empirical evaluations on the Transformed Moons, it might be interesting to compute and plot $E(\\alpha)$, $D(\\alpha)$ to  illustrate the ability of  BPDA to retrieve the correct  regime of the  hyper-parameter.\n-  Reported results in Table 2  suggest that BPDA is  effective over existing approaches. However, Table 3 related to the more challenging multi-class classification tends  to mitigate that  effectiveness. In  fact,  Table 3 does not show the significance of BPDA as its standard deviations are higher than for the competitors. At best, BPDA is on par with those methods. Can the authors elaborate more  on this? Notice that instead of comparing the methods using the average of the averaged classification errors, the ranking of the methods will be  more significant.\n- The performances of BPDA (as for the competitors)  tend to  vary according to the  used domain distance. Is a setting more suitable for BPDA that can be recommended to practitioners? \n- Minor comments\n* To  ease readability,  I would suggest  to expand earlier in the paper the terms $E(\\alpha)$ and DA(\\alpha)$ related to UDA.\n* Line 127: the upper bound on the sampling error should read $\\eta_{t, \\mathcal{G}, \\delta}$\n* Lines 146-147:  it is  not clear why the second term in $\\lambda_{\\mathcal{H}}$ expression does not depend on $\\phi$, the representation mapping\n* Equation (7): the representation mapping function $\\phi$ is  missing in  the expression of $\\hat{d}$.\n* To  help the reader, I would propose to specify the terms $A(\\alpha)$ and  $S(\\alpha)$ (at least in the supplementary material) when presenting the balancing principle for regularized inverse problems.\n* Line 210: note that $\\phi$ is not a scalar-valued function. \n\n[a] Domain Adaptation with Conditional Distribution Matching and Generalized Label Shift, Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, Geoffrey J. Gordon. Neurips 2020\n\nAfter feedback\n--------------------\nI thank the authors for providing detailed responses to the raised points. I highly appreciate their endeavour to clarify most concerns, especially the thighness of the target bound,  the practical instanciation of the bound or the discussion on the potential limitations of the approach when dealing with label shift. The sole weakness I may point out (ans this was mentioned in the paper)  is that the approach seems not overcome existing methods on more challenging DA datasets. Nevertheless the proposed method is theoretically grounded which is a good point to be mentioned. I increase my score to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper  adequately metions the broader impact of the tackled unsupervised domain adaptation . Especially the issue related  to the fact existing bias (including societal bias) in source domain data may be lifted to the target domain after adaptation is discussed.  ", "review_text": "", "extra_scores": {"ethical_concerns": "The  paper does not raise  any ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "DkAcq6gLoFp", "reviewer": "Reviewer_DYjR", "summary": "This paper studies the problem of choosing a justified regularization parameter for unsupervised domain adaptation.\nThe 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.\nThey 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.\nThis 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. \nA bound on the target risk is provided. \nAn experimental evaluation of the approach is provided using the Moons toy dataset and the Amazon reviews and DomainNet–2019 benchmark.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n---------------\nThis paper studies the tuning of a particular hyperparameter in the context of unsupervised domain adaptation. An important strong point is the procedure is founded theoretically which is not often the case of existing methods.\n\nQuality\n-----------\nThe proposed method is justified theoretically and argumented.\n\nThe experimental evaluation is sound but limited in some points: other baselines and a study on how far the assumptions are verified could be added.\n \nI would have also appreciated a thorough discussion on the target risk bounds that can be obtained from Thm1 for different divergence measures, both from theoretical and practical sides. One can wonder if the bound will not be large in some cases to match the required constraints?\n\n\nClarity\n---------\nThe paper is clear and easy to read. The contribution is well presented.\n\n\nSignificance\n-----------------\nThe problem studied is of importance in the context of domain adaptation problems. \nThe method has the advantage to be simple which makes it rather accessible in practice while being justified in practice.\nThis is the first (or at least among the first) for which the theoretical justification helds for  distributions without disjoint support.\nThe results are rathe good.\n\nHowever the method is specialized for only one hyperparameter while many domain adaptation algorithms optimized losses with multiple objective and hyperparameters. So the contribution has a strong limitation from this point.\nAnother one is probably the computation cost that requires quadratic pairwise computation on the parameter range.\nAbout the theoretical guarantee, one the one hand this is strong point to have such a guarantee, but the bound can be loose at some point. In representation spaces where the two distributions are close, the bounds seems to be infinite, which is not what one would expect here.\nExperimental evaluation can be improved in some points\n\n\n\n\nComments\n---------------------\n\n-In order to assess the quality of the result, I would be interested in having more discussions about the bound provided in Thm 1. \nIt could be interesting to try to instantiate the bound in theory and in practice to make it more concrete and maybe to better compare it to other bounds.\n\nOne thing that puzzles me is that when considering a representation space $\\phi$ such that the source and target distribution are naturally close, then the divergence will be naturally small and thus D(0), which makes the bound very loose and possibly infinite if the two distributions are the same.\nMaybe refining the bound with restrictions on $\\phi$ could be a direction for trying to have a better consistency.\n\n-About the assumptions (paragraph started line 174): The authors have justified that they can be reasonable in theory, but I wonder what happens in practice. It could be interesting to check in the experiments to which the assumptions are verified and if the worst results can be identified as results obtained when the assumptions are not (fully) satisfied.\n\n-In the results, and in particular in those related in the supplementary material, it seems that the proposed method has on average a higher variance than other methods. Can the authors provide some explanations for explaining this behavior. Is it a consequence of a generalization bound not that tight?\nWhile the method is simple, it may then be more difficult to use it in practice?\n\n-I am wondering if the authors could discuss more the computational cost of the method that requires to compute pairwise comparisons between candidate hypothesis/models. This seems costly and one can wonder if the benefits worth the computational time cost. In particular when a user is looking for a precise tuning, the cost is prohibitive and this is confirmed in the reported experiments in supplementary material (DANN on the MiniDomainNet benchmark)\nMaybe can we imagine some stochastic methods to accelerate the computation of the criterion?\n\n-About distribution with disjoint supports, the result is good but in the experimental setup other baselines adapted to disjoint supports could be considered, (e.g. the TrCV method below).\n\nOther (heuristic) validation methods that can be discussed in the related work and used as other baselines in the experiments based a notion of \"reverse validation\":   \n *Erheng Zhong, Wei Fan, Qiang Yang, Olivier Verscheure, Jiangtao Ren: Cross Validation Framework to Choose amongst Models and Datasets for Transfer Learning. ECML/PKDD 2010   \n *Lorenzo Bruzzone, Mattia Marconcini: Domain Adaptation Problems: A DASVM Classification Technique and a Circular Validation Strategy. IEEE Trans. Pattern Anal. Mach. Intell. 32(5): 770-787 (2010)   \n\nAnother direction can also be to consider heterogeneous domain adaptation, but here specific domain distances must be considered, as well as benchmarks dedicated to these tasks.\n\n-In the experiments, I did not understand well how the baseline TB corresponding to the best target error is computed?\nIt is the best target error found among the $\\alpha$ values selected or is it a bound obtained when learning for labeled target data?\nIn both cases, this is clearly a lower bound for the error.\nIn the first case, one can notice from the results in Appendix, that sometimes the method is close to this bound and sometimes not. In the second situation does this mean the assumption that D(\\alpha) is non-increasing is false in practice.\nIn the second case, it is strange to be sometimes very close to the TB results.\nCan the authors precise this point.\n\n-In terms of writing, I agree that the inverse problem setting should be cited and discussed, but I think that the discussion on it can be reduced since at the end the two problems considered are rather different.\n   \n-A minor remark, but line.109, the notation $\\phi(x)=\\phi(x')$  is maybe badly chosen\n\n\n-------   \nAfter Rebuttal\n-------   \nThe authors did a strong work to answer the points mentioned in the review. I appreciated the answers. I increase my score to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work is methodological and fundamental, so there is no direct negative societal impact.\nThe authors propose a broader impact discussion at the end of the paper.\n\nHowever, in my opinion, the paper did not discuss properly the limitations of the work. The authors mention that this is discussed in Section 4.2 but as far as I can see, the only point is mentioning that the bound may not be tight and optimality cannot be guaranteed, but no precise limitations are discussed.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "31aXN5Uajxo", "reviewer": "Reviewer_9iYu", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My concerns are solved by the author. I'm keeping my rating 7 and increasing my confidence from 3 to 4.\n\n==========================================================================================\n\n### Originality\n\nThe introduced formulation gives an alternative optimal target error bound for unsupervised domain adaptation. Inspired by the Tikhonov-regularized inverse problem, the authors explore similarities between two problems and leads to solutions for the domain adaptation.\n\n### Quality\n\nI'm not familiar with the Tikhonov-regularized inverse problem, the other parts of the paper seem to be good and written in a good manner. But, work on the limitation of the domain adaptation is missing. I will discuss it in the limitation section below.\n\n### Clarity\n\nThe paper is well-structured and easy to follow. Section 2 to 4 gives clever structure to understand the statement. \n\n### Significance\n\nThe work introduces a novel scheme to select the optimal regularization parameter for target-error bound for domain adaptation, while there exist many works on domain adaptation giving good practices. The experiment is relatively weak, but it is of acceptable quality. My concern as a practitioner for domain adaptation is this work does not talk about the regularization weight of domain adversarial network (DANN), which is epoch-based scheduling value not a fixed value. I will discuss in the limitation section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "### related works\n\nCould discuss the your method with the work [R1]? In line 99~102, it seems that covariate shift problem assumption is adopted the other papers. case. Could you refer to papers that take this as an assumption for the method? As I know it is not the case for most of the works. The work [R1] indicates covariate shift is the main problem of domain adaptation solver that relies on minimizing the distance between source and target domains. \n\n### DANN and regularization scheduling\n\nIt is common to use domain adaptation parameter $\\lambda$ is initialized at $0$ and gradually increased to 1 using the scheduling policy.\n$\\lambda_p = \\frac{2}{1 + exp ( -\\gamma \\cdot p )} -1$\n\n[R1] On Learning Invariant Representation for Domain Adaptation, ICML 19", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission proposes the balancing principle to tackle hyper-parameter selection in unsupervised domain adaptation, with an error bound for the target domain.  The reviewers were unanimous that the paper was above the acceptance threshold for NeurIPS.  In the post rebuttal discussion, it was pointed out that the method is supported by theoretical analysis, and although it is not likely that this current paper will be the final word on model selection for domain adaptation, that it provides a concrete step forward in a topic that has a lack of theoretical analysis.  As such, it is of interest to the NeurIPS community and may foster additional research and analysis on the topic.
Decision: Accept (Poster)