Provable Adaptation across Multiway Domains via Representation Learning
Authors: Zhili Feng
Shaobo Han
Simon Shaolei Du
Venue: ICLR 2022 Poster (2022)
Keywords: Representation learning
tensor
statistical learning theory

Abstract: This paper studies zero-shot domain adaptation where each domain is indexed on a multi-dimensional array, and we only have data from a small subset of domains. Our goal is to produce predictors that perform well on \emph{unseen} domains. We propose a model which consists of a domain-invariant latent representation layer and a domain-specific linear prediction layer with a low-rank tensor structure. Theoretically, we present explicit sample complexity bounds to characterize the prediction error on unseen domains in terms of the number of domains with training data and the number of data per domain. To our knowledge, this is the first finite-sample guarantee for zero-shot domain adaptation. In addition, we provide experiments on two-way MNIST and four-way fiber sensing datasets to demonstrate the effectiveness of our proposed model.

Published as a conference paper at ICLR 2022
PROVABLE ADAPTATION ACROSS MULTIWAY DOMAINS VIA REPRESENTATION LEARNING
Zhili Feng
Shaobo Han
Carnegie Mellon University zhili f@andrew.weeemm cwt.reewwwmucccm cmw.cmm......m...oo .du
NEC Laboratories America, Inc. shaobo@nec-1e @abbbelbecaabss com
Simon S. Du
University of Washington ssduêcs. washington, edu
ABSTRACT
This paper studies zero-shot domain adaptation where each domain is indexed on a multi-dimensional array, and we only have data from a small subset of do- mains. Our goal is to produce predictors that perform well on wnseen domains. We propose model which consists of a domain-invariant latent representation layer and a domain-specific linear prediction layer with a low-rank tensor struc- ture. Theoretically, we present explicit sample complexity bounds to characterize the prediction error on unseen domains terms of the number of domains with training data and the number of data per domain. In addition, we provide experi- ments on a two-way MNIST, a four-way fiber sensing dataset, and also the GTOS dataset to demonstrate the effectiveness of our proposed model.
INTRODUCTION
In many applications, collected datasets cross- classifid by number of categorical factors such as a set of experimental or environmental conditions that are either controllable or known. These applications can be formalized being indexed on a multi-dimensional array. Domain-shifts often exist among data collected under different conditions, and to minimize the bias, one would like collect diverse data cover all conditions. However, due to high cost of data collection or insufficient resource in the field, it often impractical to cover all possible combinations of factors. In most cases, training data collection can only cover few limited, accessible scenarios, and the data from target domain may not be available during the training phase at all.
zero-shol domain adaptation (ZSDA) problem with each domain
One motivating example is the distributed fiber optical sensing (Rogers 1988) technique started to be used in smart city applications (Huang et al. 2019). Collecting fiber sensing data for machine learning is expensive and the characteristies of sensing data vary considerably across various het- crogeneous factors, such as weather-ground conditions, signal source types, and sensing distances. Although conducting experiments possible, it is difficult to conduct experiments to cover all possible combinations. Specifically, in order to account for the effects of multiple factors (e.g., soil type x distance sensor x weather), one has to visit multiple sites and set up the sensing equipment, and wait for the right time until the target type of data can be collected, and some combination of factors constraint of the physical world (e.g. testbed at 10km sensing distance with asphalt pavement sur- face). Besides, the digital pathology application, domain shift can be caused by different clinical centers, scanners, and tumor types (Fagerblom et al., 2021). ). It is impossible to cover every combi- nation in training (e.g., one center maybe specialized certain tumor class or own one particular type of scanners). Ideally, for these applications, one would want to train a model under subset of scenarios, and adapt it to new unseen scenarios without collecting new data.
cover small subset of combinations of different factors is
accessible due the
"Wok done intern NEC Labs America.

---

Published as a conference paper at ICLR 2022
Another motivating application design data augmentation with composition of operations. For instance, in image recognition applications, there are often multiple operations can be combined into augmented datasets, including blurring, translating, viewpoint, flipping, scaling, etc, and each with several levels or values to choose from. It may require huge amount of augmented data to cover all combinations of operations. Ideally, one only wants try small subset of all possible combinations. Previous works have shown that composing operations in careful ways outperforms randomly using data augmentation schemes (Ratner et al. 2017; Cubuk al. 2019).
In the general ZSDA formulation, each domain is associated with a task descriptor, which is used to generate predictor for the domain. This function that maps task descriptor to a predictor. i.e., a predictor generator, is trained on training domains where data is available (Yang & Hospedales) 2014). In our setting, we can view the categorical indices for each domain as a task descriptor and thus apply existing approaches. However, this ignores the inherent multíway structure that connects different domains. Furthermore, existing approaches lack theoretical guarantees, and thus it is unclear under what conditions, the learned predictor generator provably output accurate predictor on unseen domains. natural question is
Can we design a provably sample-efficient algorithm for zero-shot domain adaptation that exploits the multiway structure?
1.1 OUR CONTRIBUTIONS
In this paper, we answer this question affirmatively. Our contributions are summarized below.
we consider multilinear structure which naturally characterize the relatedness among differ- ent domains. Formally, we assume that there are totally = dd domains that form a d dimenssionl task tensor, where the predictor on domain t [D] is parameterized by w o 6- E W o where 6² : X' - I² is a common representation for tasks and we E TRP is a domain specific linear predictor. We only consider the case when p is small. Note the linear predictors, wi,.... wh E IR,, together form a form a d x d .... x xp-dimensional tensor,
M times which we denote as T. To enable domain adaptation, we further impose a low-rank multi-linear on the linear predictor T. The structure we impose on the model is that the slice along the last axis is always rank- with K < ddM That is, for all j E [p]. T., E TRdxdx--xx xd has rank K.
We provide finite- sample statistics analysis for this model. We show that if during training T E [D] source domains are observed, and in each observed domain n samples are collected, then the ((
expected excess risk across all D domains is of order
((TCW)) 1/4
+p
KdM²
1/2) T
where C(F) represents the complexity of function class F. The first term corresponds to the cost linear classifiers, and the second term corresponds to the cost of generalizing to unseen domains. In the case where n is large, we can simply ignore the first term, and conclude that T should scale with K Kd(pMM)2 This theoretically justifies our method can adapt to unseen domains with limited training domains.
of learning the common representation and
We test our proposed method on a two-way MNIST dataset and four-way fiber sensing datasets. The empirical results show our method matches the performance of general ZSDA algorithm by Yang & Hospedales (2014) which has lot more parameters than our method.
RELATED WORK
For theoretical results of multi-task learning, Baxter (2000) first derived a covering number bound for sample complexities. Later Maurer et al. (2016) gave a uniform convergence bound for multi- task representation learning. Their bound is of order O (V11mm of training samples in the target domain, so is not reflecting how their learning process benefits from seeing multiple domains. Recently, Du et al. (2020); Tripuraneni al. (2020) successfully derived results of type O O(V1/m + (1/(nT)), which satisfactorily explained how learning algo- rithm benefits from seeing abundant training data in many source domains, even if training data in target domain is scarce. This setting is often referred as transfer learning few-shot learning. A
v1/T), where is the number
2

---

Published as a conference paper at ICLR 2022
key difference between this setting and ours is that do not any training data from the target domain. Blitzer et al. (2009) also studied ZSDA, but they studied a different approach which relies on mueti-view learning and is restricted to linear models.
Many attempts to solving multi-task learning via low-rank matrices/tensors have been proposed Romera-Paredes et al. (2013) Signoretto et al. (2013); Wimalawarne et al. (2014), focusing on reg- ularizing shallow models. Wimalawarne et al. (2014) specifically discussed task imputation and
gave a sample complexity bound. However, their analysis assumed each training data uniformly sampled from all source domains, so it is incomparable to our result. Yang & Hospedales 2017);:
share parameters between neural architectures for multiple tasks and empirically verified that both multi-task learning and domain generalization can benefit from the low-rank structure. Some different but closely related settings include unsuper- vised domain adaptation and zero-shot learning, where the test labels are either unseen during the training phase or different from what the model has been trained with. This beyond the scope of this paper, as we only consider the case where all domains share same set of labels.
al. (2017) used low-rank tensor decomposition
The low-rank matrix completion problem has been thoroughly studied the past decade Srebro & Shraibman (2005); Srebro et al. (2004); Candès & Recht (2009); |Recht (201T). Despite the com- binatorial nature of rank, it has a nice convex relaxation, the trace norm, that can be optimized efficiently, in both noiseless and noisy settings Wainwright (201)). Although these quantities (trace norms, ranks, etc) are easy to calculate for matrices, most quantities associated with tensors are NP-hard compute, including the trace norm HHillar & Lim (2013). There are many efforts in the thcoretical computer science community to tackle tensor completion problems from the computa- tional complexity perspective Barak Moitra (2016); Liu & Moitra (2020). In this paper, we use the statistical properties of tensor completion despite their computational inefficiency. Hence our sample complexity bound does not contradict the seemingly worse bounds in the theory literature.
PRELIMINARY AND OVERVIEW
Notation. For D E Z, we let [D] = f1.2..... D}. We write || || to represent the & norm or Frobenius norm. Let (.-)) be the inner product on an inner product space. Throughout the paper,
we assume for simplicity in total there are D = d x d x ... d data domains. One can easily
M
generalize the results to the general case where D I dç. We use @ to denote the tensor product and @ the Hadamard product. We use T E [D] to denote the number of seen source domains, n to be the amount of sample in a single source domain. Since each E [D] also uniquely corresponds to multi-index in / [d|xM, if T _dxx-xxxpp is d dimension tensor composing of p- dimensional linear functionals, we also write Te, E RP to represent the classifier at multi-index 1, and we use t and I as indices interchangeably.
M
3.1 PROBLEM SETUP
During training, we have T source domains out of the D domains uniformly at random. For cach domain E [ have i.i.d data {(F1,5, st,i),=11 samples from the following probability (Tripu- raneni et al. k P. y) = P Puzoo (x., y) = P2 J y (y]w,, ø" (x)), where all domains share the common feature mapping o² (R' + R2) n & and common marginal distribution P.. Each domain has its specific classifier W, (R" R) n W. +b can be general function class and W composes of Lipschitz linear functionals. We denote this distribution as D,.
The key assumption is that D domain-specific classifiers form D x p rank-K tensor 'T in the following sense:
K
TA E [d] Ti. = w
a
(I)
for ai E R.P We remark that this does not mean T has rank K. Instead, this means for each j E [p), T. has rank K.
Let é R + R> be the loss function, L((wo)(<)),) v) = E. ((((((())))) v)] be the expected loss, [.,((w ()),)) = Ei_ l((w o (x:)) yr) be the empirical loss. When x and y clear
3

---

Published as a conference paper at ICLR 2022
from the context, write ((woo) denote [[(woo)(z), y). and similarly for i and L,- When the number of samples n is clear from the context, we write == Ln. We write Le Ep, [e( )) to emphasize the data is from D. Our goal is to minimize the average excess risk across all domains:
D ELEDD ED, [ (b o - (wf x²)
Our learning algorithm first outputs the empirical risk minimizer (ERM) the seen source domains:
1
ti, δ
arg min DE#. w W
((wr ()1,)))
(2)
nI
Naturally we put úh into d p tensor T, such that Te, W2z. Then do tensor completion for each E [p] separately:
T. arg min
Tea Te.s
rank-K T T
LE(T]
D., we make the Finally, test time, for target domain indexed by 1 E [D] and test data prediction I (w; (x), where úh = TT,-
Notion of Complexity We use Gaussian complexity and Rademacher complexity to measure the function class complexity.
Definition 3.1 (Gaussian and Rademacher complexity). Let F C
(J: RR) be vector-
valued function class, the empirical Gaussian and Rademacher complexity on n. points X = 1. Fnd 3 defined as:
G (FIx) E
sup
1 N
Σ VE(N)
Σ kE[y]
(Fxx E.
sup fEF
1 N
EE cnrfa(Z))
JEF
SEIN] kEll
where gsi are all standard Gaussian random variables, eki's 's are Rademacher random variables, and f& is the kth entry of f.
denote the expected Gaussian complexity (similarly for Rademacher complexity). To deal with the divergence among domains, we adopt the fol- lowing notions from Tripuraneni al. (2020): C,,(W maxzez Br (WW2), where Z (()())) o (Ix)) o 4, E X for all i [n]].
Let (F)
Ex 6
[ix)] (FFx))
To measure the complexity tensors, we use the notion of pseudo-dimension.
Definition 3.2 (Pseudo-dimension)) Let F X be real-valued function class. Let x. (I1...., 2mn) E X We say x is pseudo-shattered by F is there exists T (ri...., Tm) E R such that for all b (bı,..., bm) {+1)mm there exists f E such that sign(fo(x;) r.) b, of F defined as:
for all E [m]. The
(J) = max m E N Bay" s.t xx is pseudo-shattered by F
4 THEORETICAL RESULTS
In this section, derive the sample complexity bound for our DG setting. As high level overview, we first prove that on the T' seen source domains, with enough training data and sufficient regularity have iy being sufficient close to w the source domains. Then we show that
conditions, with a large enough T, even on an unseen domain t [D] [T] we can also approximate w, well by completing the low-rank tensor formed by learned ú, Finally, by certain regularity conditions the loss function, we can show the excess risk is also small.
We require the following regularity assumptions for theoretical development.
4

---

Published as a conference paper at ICLR 2022
Assumption 4.1. 1. The learning problem is realizable, that is, wi Wffor for all E [D] and
6" E Φ. WLOG assume that wt o o" is the unique minimizer of for all
2. ((())) .) is B-bounded, and E(.,y) y) is L-Lipschitz.
3. For all w E W, ||w|| & W.
4. sup, |1Ø(x)] & Dx, for any Φ Φ
5. For all t e [D], L, is X-strongly convex in wa for 6"
The first assumption is indeed general. Since we care about the excess risk, in realizable problems compare to the unique minimizer of L in Wo & instead of w/ oØ" The existence of unique minimizer is necessary, otherwise tensor completion can lead to arbitrary errors. Assumptions 2-4 common. Lastly, without strong convexity in the last assumption, one cannot derive the closeness of di to wł from the closeness of the excess risk on source domains.
4.1 LEARNING COMMON REPRESENTATION
this subsection, we discuss how learn the shared representation. The proof follows Tripuraneni et al.] (2020) with modifications to adopt our setting. First we introduce some definitions that defines the divergence among the source domains and target domains.
Definition 4.1. For a function class W, T functions W1...., Wr, and data (Ie, yt) De for any t E [ the task-average representation difference (TARD) between representation & and o' is defined as:
Σ inf E (f(w' (b)) - E(ww, o x))
T
w'EW tE[T]
Let w", O6" be the true functions. Define the uniform absolute representation difference (UARD) to be
dw(d':0) sup sup E (f(w, o Φ0) E(we o x))
tE(D] wew D.
For W, we say = wr is (v, c)-dieerse for representation o, if the following holds for all E t::
dw(6'; S dw...
The notion task task-average representation difference was introduced by Tripuranenn et al. (0020). In their setting, they bound the worse-case representation difference (WCRD) between two represen- tations Φ Φ E h which is defined as
sup inf weW W'EW (Pa))~Pwoo
[l(w' )') l(w Φ)),
using the task-average representation difference. One should note that WCRD changing the data distribution, while UARD takes expectation over the true distribution D,, We are saying that under the true distribution, the worst case difference between using & vs. ø' over both the choice of linear classifiers w and the domains, is not much larger than TARD. Intuitively, this says that our source domains and task domains are benign enough, such that the ERM o performs similarly to the true 6*
Although it seems that dw (d'; consider dw... (Ø'; )*)) and w oo* is assumed to be the minimizer. Hence, dy,,.- (Ø'; )²*) is always positive, and our notion of task diversity makes sense.
; ④) can be negative and dw is always positive, later we only
We cite the following theorem from Tripuraneni et al. 2020).
Theorem 4.1. Let à be the ERM eq.
2 Under assumption
4.1 with probability least 6,
we have
dw.w- (6, $ 4096T.
WDx
+ +log(nT) [W 6.r( + +o,00]]] (nT)²²
(6,
+ 8B
log(2/6)
n.T
5

---

Published as a conference paper at ICLR 2022
4.2 LEARNING DOMAIN SPECIFIC LINEAR LAYER AND TENSOR COMPLETION
Now we give results for learning the domain specific linear classification.
Theorem 4.2. Let ú, & the ERM in eq. 2 Let assumption 4.1 holds. With probability at least 1 - 8, we have
Exttyy 1100c uzz 12 1 00 (VV
1/2
(n2y) + log(n7) [W (Br( (. 8BV
log(2/62 n2
The proof of Theorem 4.2 starts with showing that L(w, x²) is close L(w; o Φ*), while normal ERM analysis only asserts L(ú, @) close to L(wf o 6²). Such assertion holds by the (u,e) divverse assumption. Intuitively, such diversity assumption makes somehow smooth: w; should be stable such that we perturb & to Φ², the loss function does not alter too much. Together with strong convexity, these conditions guarantee ú; is close to the true w on average.
learning landscape
After we learn ie for all t E [T], we find another ERM T by constructing p tensors T., for all i [p] separately as in eq. (3. We only observe the empirical tensor completion loss + Σ IT.. Tia during training. With large enough T, by a uniform convergence argument, we can show that Te.il can approximate + Ei [Tr - Tt, fairly accurately.
T Ei= [Te.
Lemma 4.1. Let XK be the class of rank- K tensor of shape dxM, its pseudo-dimension can be bounded by Pdim(Xx) S KdM2 log(8ed).
Pdim (Xx) is computed by treating tensors as polynomials and counting the connected components of these polynomials. Even though any X E Xxx has dM entries, its complexity only scales as poly (K d, M). This assures that we only need to see polynomially many source tasks to perform well in unseen domains. Using the pscudo-dimension, we have the following uniform convergence result.
Theorem 4.3. With probability at least 1 - 8,
Σ [E[D
Te
Tt.
Σ
Σ
Fe. Teal + PV
KdM log (Bed) + log(p/0)
+ Ö(n (111//4)
D
T
jE(M]
(4)
The last Onn-1/4) -1/4) term in eq. (4) comes from Theorem 4.2 This is the cost we pay for not knowing
the true T;: in each source domains we have infinity number of training samples, then statistically Theorem 4.2 recovers the true T In this case, we only need to observe T poly(p, K, M)
source domains.
4.3 MAIN THEOREM
We now ready to show main result. Theorem 4.4. Let assumption 4.7 holds and w- = {wi .... wi being (v, divveeree for represen-
tation o² With probability at least 1 - 35, the following holds:
LDxW T
E (D
[e(we M(x). l(wī a (x))
Σ
Σ
Wt. - Tr.)
KE[T]
jE(
1/4
KdM log (8ed) + log(p/8)
C(W)
C(+)
WD
T
nT
The first two terms correspond the cost of tensor completion and the last term corresponds to predicting with inaccurate 5. The term Eierry Σ ]eEpp] 0i. Tr.j can be exactly computed on the training dataset. Recall wi the learned by eq. (2) and म., is the estimated linear classifier after tensor completion. As increases, this difference becomes smaller úy becoming close w

---

Published as a conference paper at ICLR 2022
5 EXPERIMENTS
We empirically verify that our proposed model leads to better generalization performance than base- line model with vanilla representation learning on three datasets: variant of MNIST dataset, the ground terrain in outdoor scene (GTOS) dataset (Xue et al. 2017), and fiber sensing dataset. On all datasets, we use LeNet trained on all available training data as the baseline. According to et al. (2117] 2019). this is a simple yet strong baseline that outperforms most domain generalization methods. Our model is trained an end-to-end fashion. Instead of finding ERMs in eq. 2 and
perform tensor completion, we directly represent V0 = > O âikmt and output
K
to δ = arg min se ak.tm
Oktt (0)(z,,), )
(5)
n.
t=
k=
In this way, can fully exploit the computational convenience of auto-differenniation rather than dealing with the algorithmic difficulty of tensor completion. All models are trained using the cross entropy loss. Since theorem is uniform convergence bound by nature, the sample complexity will also apply to the end-to-end trained mode!"] To prevent overfitting, we stop training of all models on the two-way MNIST dataset as soon as the last 50 iterations have average loss less than 0.05, and the training of all models on GTOS and the four-way fiber sensing dataset is stopped once the last 100 iterations have average loss less than 0.05. Throughout the experiments, the Adam optimizer with default learning rate 10 is used except when explicitly stated otherwise. The sensitivity of the regularization parameter investigated on MNIST data and we set to 0.05 for all rest of the experiments. For MNIST dataset, the source and target domain data are augmented from MNIST training and test data respectively. For the fiber sensing dataset, the source and target domain data are collected in separate experimental rounds. The GTOS experiment results are postponed to the appendix. Across all results tables, mean accuracy is outside the parenthesis, standard deviation is inside the parenthesis.
5.1 TWO-WAY MNIST
A variant of MNIST is created by rotation and translation operations. We rotate all MNIST digits by [-30,- 0, 15, 30) degrees, and translate all MNIST by ((-3, (0, 3), (0, 0), (0,3), (3) pixels, leading to 5 x 5 domains.
For our proposed method, we use simplified low-rank structure on the last two layers of LeNet. Specifically. LeNet has the structure of conv 1 1-pooll fete-poooo---l------t-------e We impose the low-rank structure on both fc2 and fc3.
For task (i,j) E 5x 5, we use s; u2 u for prediction. This formulation is just a special case the general formulation in eq.
We create 11 linear classifiers for each layer, denote as si...., S5, vi..... Us.
[1] Indeed, let 01) [81, 82, 83, 84, 85, 1, 1, 1]. 02 [1, 1, 1. 1, 01, U2, U3, 04, v5). and u1 U, U, u, u. 1, 1, 1, 1, 1). where each Ws; 0c, u, TR? and or E R10 x RP.
0g
(i, E 5 x 5, its classifier we this can be formally written as > 0KK ak,s+jj which is the same form as eq. (1. This is done for both fc2 and fe3, and each layer has its own distinct set of weights.
Then for any task at
Similar idea has been previously proposed for domain generalization Yang & Hospedales] (201 ei al. (017). These previous works do not assume a tensor structure on the tasks. Instead, they put low-rank tensor structure on the classifiers themselves. This fundamentally distinguishes our settings from previous ones. As a result, during test phase they have to use the common classifier for different target domains, but we can incorporate more prior knowledge by using s; + Uy + u.
During training time, we collect training data from (i, entries for all E [5], and leave data in any other domains for test only. This one of the designs requires the minimal number of source domains, and we can still successfully train all unknown classifiers s, and u. Due to
'Some theorems require w., å being the ERM of eq. 2 In those cases, we can simply modify úi be the corresponding entries of the tensor 7 formed by âs.t... and substitute eq. 5 for eq. (2) This is justified since we assume the learning problem realizable.
7

---

Published as a conference paper at ICLR 2022
Table 1: Test accuracy with observed domains the diagonal. In each cell, from the 1st to 5th row: baseline, our domain-agnosti and domain-specific models (both with the special low-rank formulation) the general ZSDA model Yang & Hospedales 2014p, and the Fish algorithm (Shi et al. 2021 for domain generalization.
(-3, 0)
33)
(0.0)
(0.3)
(3.0)
0.958/0.007)
0.927(0.007)
0.735(0.017)
0.585/0.016)
0.950(0.007)
0.932(0.010)
0.769(0.024)
0.659(0.037)
0.965(0.004)
0.943)).009)
0.775(0.024)
0.64660.038)
(.967(0.0012)
0.93600.000)
0.76900.022)
(.671(0.021)
0.968(0.0033
0.932(0.004)
0.637(0.012) 0.744(0.018)
0.975(0.001)
0.974(0.002)
(.908(0.005)
0.79700.009)
0.978(0.003)
0.907(0.010) 0.973/0.004)
0.816/0.018)
-15
0.977(0.004)
0.975(0.003
(.910(0
0 (.839(00115)
0.976/0.005)
0.974(0.004)
0.913(0.012)
0.852(0.012)
0.978(0.002)
0.977(0.001)
0.912(0.007)
0.845(0.007)
0.925(0.012)
0.96910.004)
0.973(0.002)
0.935(0.007)
0.951 008)
0.966900.055
(0.00)))
(.947(0.007)
0.950(0.009)
0.92610.0005)
(.976(0.002)
0.952(0.005)
0.945(0.D11)
0.971 (464))
0.977(0.0011
0.952(0.004)
0.928(0.006)
(..01(0.002)
0.977(0.002)
0.950(0.003)
0.73M0.058)
0.861/0 (233)
(.074(0.0033
(975(0.003))
0.810(0.029)
0.863/0.013)
(.971().
(.92((.0022)
0.801(0.027)
0.866/0.013
0.978(0.003)
0.977(0.002)
0.804/0.019)
0.882(0.017)
0.978(0.001)
0.978/0.002)
0.75660.021)
(0.019
0.976/0.003)
0.980(0.002)
0,494(000559
0.919(0.D10) 0.6-990.027))
0.955(0.004)
0.576(0.048)
0.664/0.018)
0.917(0.021)
0.930(0.012)
30
0.573(0.045)
0.68 (0.02))
0.942(0.0088)
0.956(0.006)
0. 0.568/0.022
(.715(0.018)
0.938
0:947(0.016)
0.518(0.02-)
0.672(0.015)
0.928(0.007)
0.958(0.004)
the excess amount of learnable parameters, it is easy to overfit on our method. To reduce model complexity, regularize all learnable classifiers to be close to their mean. That is, on each low- rank layer, let = 17 EE U; + Ej 8j + u), we add the following regularizer to the loss function
us, = A Σ, |1u m1l + E, [|s; 1= ||u mll?)
We run the experiments 10 times and report the mean performances and standard deviations in Ta- 1 I Since this method uses the domain description information (i,j) during testing, we refer it as the domain-specific model. In addition, we also report the performance of using just the common classifier u in fc2 and fc3. This model uses no domain information during testing, and we call the domain- domain-agnostic agnostic model. The baseline model is LeNet trained with data pooled from all source domains together. Notice that each s; + 2j + V corresponds to a unique task descriptor qr, that serves the coefficients for the combination of the linear layers, so for the ZSDA model, we further trained another descriptor network that outputs ReLU(Wgg) 4) as the new coefficients. This is done for both the last two layers. Our method almost uniformly dominates the baseline in every domain, sometimes by a large margin, and almost matches the performance of the ZSDA model, with less pa- rameters. The domain-agnostic model achieves comparable performances to proposed method. This shows that with the low-rank tensor structure, aggnoiic models can also accommodate the domain shifts on this dataset. On most test domains, especially the ones that are "further away" from the training domains, our proposed algorithm consistently outperforms Fish (Shi et al. 202 one of the state of the art domain generalization algorithms. Such results are expected the Fish algorithm does not consider multi-way way structure into consideration.
Another interesting observation is that the performances of all models are better near the diagonal, and getting worse away from the diagonal. This may provide insight into how we should design experiments under fixed budget of data collection. conjecture that the performances on unseen target domains relate to the Manhattan distance of these domains to the seen source domains. Further discussion is deferred the appendix.
5.2 FOUR-WAY FIBER SENSING DATASET
The distributed optic fiber sensing technique turns underground cable of tens of kilometers into linear array of sensors, which could be used for traffic monitoring in smart city applications. In this paper, we aim build classifier for automatic vehicle counting and run-off-road event detection.
The objective is to classify whether the sensed vibration signal is purely ambient noise, or it contains vibration caused by vehicle either driving normally or crossing the rumbling stripes alongside the
8

---

Published as a conference paper at ICLR 2022
road. The sensing data takes the form of 2D spatio-tempore array that can be viewed an image each pixel represents the vibration intensity at a particular time and location along the cable. Vehicles driving the road, rumning-off seriing-off-roite off-road, and ambient noise all create different patterns, which makes convolutional neural networks a natural choice for a 3-class classification model.
In experimental design, consider several inftuencing factors representing the practical challenges faced after field deployment. These factors include weather-ground conditions (sunny-dry, rainy- wet), shoulder type (grass, concrete), sensing distance (0km, 10km, 15km), and vehicle type (van, sedan, truck), which produce combined effects on the data domain. In order to evaluate our ap- proach, we spent efforts on collecting data with all possible combinations of the levels in the afore- mentioned factors in a lab testbed, resulting to a multiway data indexed by a 2 x 3 x 3 X 2 tensor. Under each condition, we conduct The ambient noise data is collected when no vehicles are near the cable. The classes are balanced in both training and test data.
25 rounds for the run-off-road events and normal driving-
1.0
20
humber derate
35.3%
0.4
03,0%
0.7
Dusine
20
15.2%
Bark
2404
Coman spedi:
Gerera 2
somyyled dem
avergr vothiggn datn
saaay EDem grast
and pary eysten (r8tt
2016
Borme call
raly rate
6.0
0.65
0.70
575
6,45
6.66 6ts L.c
(a)
(b)
Figure I: Left: Average test accuracy vs. number of source domains. Right: Test accuracy, trained on 20 random observed domains.
We evaluate model performance against number of source domains (5, 10, 15, or 20, each with 10 simulation runs) and results are shown in Figure [a). The performance increases with number of source domains as expected. In particular, Figure [b) summarizes the test performance for models trained with 10 source domains and tested on the rest. In each run, the observed source domains randomly sampled. Among the 10 runs, Srann--edda-15km-
happens to be always selected as the source domain, thus the test result is not available for this domain.
We add two additional low-rank models the form of eq. (5) with K = 2 and 3 just in the last layer for comparison. Among the combination of factor levels, some scenarios more challenging than others. For example, sedan is the lightest vehicle among the three, which generates much weaker vibration than truck. Also the signal-to-noise ratio decays with increasing sensing distance. Results show that in most of the cases, our ZSDA models achieve improved performance over the baseline, and the margins over baseline are particularly large in several challenging scenarios.
CONCLUSION
In this work, we propose a particular domain adaptation framework where T out of = d total domains are observed during training. All domains are parameterized by common la- tent representation and their domain-specinf linear functionals, which form a -iM-dmmnnsional low-rank tensor. This multilinear structure allows us achieve an average excess risk of order 1/4
ō (TOW))O())
+p (P(KN)))
[dM=)) 1/2
In addition domain adaptation, our setting also sheds light on more efficient experiment designs and data augmentations. Algorithms developed under our framework are empirically verified on both benchmark and real-world datasets.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
SSD acknowledges support from NEC. SH would like to thank Yuheng Chen, Ming-Fang Huang, and Yangmin Ding from NEC Labs America for their help with the fiber sensing data collection.
REFERENCES
Boaz. Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy, In Conference on Learning Theory, pp. 417-445. PMLR, 2016.
Jonathan Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12: 149-198, 2000.
Irad Ben-Gal and Lev B Levitin. An application of information theory and error-correcting codes to fractional factorial experiments. Journal of Statistical Planning and Inference, 92(1-2):267-282, 2001.
John Blitzer, Dean P Foster, and Sham M Kakade. Zero-shot domain adaptation: A multi-view approach. Tech. Rep. TTI-TR-2009-,, 2009.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, (6)77177777, 2009.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. AutoAugment:
Learning augmentation strategies from data. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 113-123, 2019.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint 2tt2::200000944444 2020.
Freja Fagerblom, Karin Stacke, and Jesper Molin. Combatting out-of intoof-distribution errors using model-agnostic meta-lcarning for digital pathology. In Medical Imaging 2021: Digital Pathology, volume 11603, pp. 16600SS. International Society for Optics and Photonics, 2021.
Christopher J Hillar and Lek-Heng Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 6006):0063)))) 2013.
Ming-Fang Huang. Milad Salemi, Yuheng Chen, Jingnan Zhao, Tiejun J Xia, Glenn A Wellbrock, Yue-Kai Huang, Giovanni Milione, Ezra Ip. Philip Ji, et al. First field trial of distributed fiber optical sensing and high-speed communication over an operational telecom network. Journal of Lightwave Technology, 38(1):75-81, 2019.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales. Deeper, broader and artier domain generalization. In Proceedings of the IEEE International Conference on Computer Vision, pp- 5542-5550, 2017.
Yiying Li, Yongxin Yang. Wei Zhou, and Timothy Hospedales. Feature-critic networks for heteroge- neous domain generalization. In International Conference on Machine Learning, pp. 3915-3924. PMLR, 2019.
Allen Liu and Ankur Moitra. Tensor completion made practical. arXiv preprint arXiv:2006.03134 2020.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Michael D McKay, Richard J Beckman, and William Conover, A comparison of three methods for selecting values of input variables in the analysis of output from computer code. Technometries, 42(1):55-61, 2000.
Alexander Ratner, Henry R Ehrenberg, Zeshan Hussain, Jared Dunnmon, and Christopher Ré. Learning compose domain-specific transformations for data augmentation. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 2239-3249, 2017.
10

---

Published as a conference paper at ICLR 2022
Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
Augustus James Rogers. Distributed optical-fibre sensors for the measurement of pressure, strain and temperature. Journal of the Institution of Electronic and Radio Engineers, 58(5S):S113- S122, 1988.
Bernardino Romera-Paredess Hane Aung, Nadia Bianchi-Berthouue and Massimiliano Pontil. Mul- tilinear multitask learning. International Conference on Machine Learning, pp. PMLR, 2013.
Yuge Shi, Jeffrey Seely, Philip HS Torr, N Siddharth, Awni Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. arXiv preprint arXiv:2 2021.
Marco Signoretto, Lieven De Lathauwer, and Johan AK Suykens. Learning tensors in reproducing kernel Hilbert spaces with multilinear spectral penalties. arXiv preprint arXiv:1310.4977, 2013.
Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. International Conference on Computational Learning Theory, pp. 545-560. Springer, 2005.
Nathan Srebro, Noga Alon, and Tommi S Jaakkola. Generalization error bounds for collaborative prediction with low-rank matrices. In Advances in Neural Information Processing Systems, 2004.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The impor- tance of task diversity. arXiv preprint vrXiv:2006.16633 2020.
Martin Wainwright. High- Bigh--imensional Statistics: Non-asymptotic Viewpoint, volume 48. Cam- bridge University Press, 2019.
Kishan Wimalawarne, Masashi Sugiyama, and Ryota Tomioka. Multitask learning meets tensor fac- torization: task imputation via convex optimization. Advances in neural information processing 2014.
systems,
Jia Xue, Hang Zhang, Kristin Dana, and Ko Nishino. Differential angular imaging for material recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 764-773, 2017.
Yongxin Yang and Timothy Hospedales. Deep multi-task representation learning: A tensor factori- sation approach. In International Conference on Learning Representations, 2017.
Yongxin Yang and Timothy M Hospedales. A unified perspective multi-domain and multi-task learning. arXiv preprint arXiv: 2014.

---

Published as a conference paper at ICLR 2022
A PROOFS IN SECTION
Theorem 4.2. Let ú, & be the ERM in eq. 2 Let assumption 4. holds. With probability at least 1 6, we have
1/2
Eej 1/0c
wi 12-0 -0
(V3
WDr [x7y + log(nT)) [W (,r(() [w 8B
lon(2/6) ".
Proof. By standard decomposition, we have with probability at least 1 28
1
L(ú, o é) -Lwg o0))
T
(E[T]
1
Σ
[Eúú क) - ED, lwo o3')]
T
(E[T]
1
Σ
ED, [l(ir 3) nT
Σ
E((úr o @I(L.)) vi)
T
1E|21
1E|2] sE|n]
(((ū, (zI.)) v.)
Σ [((w; o (z)()))))
nT
nT
KE[T] KEin)
SELT KEjN
Σ
((ww xz) (11,))))) ED, (K(w o x*)]
nT
(E(T] vE(n)
<2 sup
Ed, [ll, o +)
1 nT
Σ
Σ
e((wr ()(,)))
T AE(T]
Wy EW, 0E4
TE sc[m]
log(1/8)
<4R (EWWST + + 4B
log(1/5)
<8LR о +)) + +B
nT
Use the fact that (H) < / (H) for any function class H. and the decomposition of Ruz (WVST o 4) introduced in Tripuraneni et al. 2020), we conclude that
T L(wr a () L(wg a x*))
1
WDx
log log(2/8)
< 4096L (nT)²
+ log(nTT) [ (x) (3,++,(11]]
+ +BB
nf
Meanwhile, by our assumption of uniform absolute representation difference and (v, cuttsk diver-
sity:
T
T
1
Σ
L((r - L(10, 06)) <
Σ
L(ü, o o00 L(u, o x) < dw(() < dw (/
T
2m1
which gives
Σ o00) owi T
1
Σ
L(w o o00) L(20 od) -
1 +
Σ
L(wr o x6) L( o 06"))
T
<
D/v+6
12

---

Published as a conference paper at ICLR 2022
where use d (0.0") Φ²) S ! from Theorem 4.1
By strong convexity, we conclude for any T E [D).vS1. 1:
1/2
2 V
20,
wi 112 3
(L(te, o Φ²) L(w d'))
T
T
(E|T]
TE(T]
1/2
WDxx (nTT)²
log(2/0)
4096L
log(nT)) [W (,T(2) + (M1)] +BB
+
Av
nTT
Now we proceed to show the results related to tensor completion. The main idea to treat a tensor polynomial, and count its connect components. This number restricts the complexity of the tensor.
Corollary A.1. The number of {=1.0) sign configurations of polynomials of degree at most d, over q variables, is at most (Sedr/q)² for q
Lemma 4.1. Let AK be the class of rank-K K tensor of shape dxM, its pseudo-dimension can be bounded by Pdim(XK) S KdM² (og().)).
Proof. Let KK, (sign(X T) E (=1,0)a** :x e Kx|/. It suffices to show that fr, M, K) (8ed) KdM2 A rank K d tensor be decomposed as:
M
X,
Σ II
Uk
k=1m=1
fort E xM Then one can treat X-T as d polynomials of degree at most M over the following
entries:
K
(x - T):
Σ II Un Tz.
a fixed arbitrary tensor, so there are in total KdM variables. Applying Corollary A.I yields the desired result.
Theorem 4.3. With probability at least 1 5,
1 Σ [E|D]
Σ
T..
Tr.
Σ tElr)
Fr.s Tea + +PV
KdM log (8ed) + log(p/0)
+ ((1t)))
T
Proof. The following equation holds with probability at least 1 6, and follows directly from uniform convergence bound using covering number and bounding covering number using pscudo- dimension. See Srebro & Shraibman (2005) for detail.
1 T T D
1
Σ
T.,
TT's
+
KdM log (8ed) - log
(6)
T
T
LE
LETT
Then by triangle inequality and equivalence of norms in finteeddimensional spaces
13

---

Published as a conference paper at ICLR 2022
Σ tE(D]
Tr. The
D Σ
Fi. Ted
D
(E jE(p]
KdM log (8ed) + log(p/6)
$ ΣΣ
Ti. Tis
+ +PV
T
[E[T] LE|p]
$ ΣΣ
Tei T + +PV
KdM log (8ed) log(p/6)
Σ Σ :E(T] TE(p)
Te.s - Tci
T
T
1E|T] tE(p)
KdM² log (Bed) + log(p/8)
$ Σ
Fij Ti. + PV
O Opp
T
[E|T) jElp
where the first step is from the fact that -1 |1- |la and union bounding eq. 6 p events. The
02p term follows from Theorem 4.2 and equivalence between norms. Note that p hence asymptotically our conclusion holds.
Theorem 4.4. Let assumption 4.1 holds and w² = {wi ...., w being (u, e)-dieerse for represen-
lation d² With probubility at least 35, the following holds:
LDx
E (E.Y)DD
[e(úe M(x), v) e(w] o o (x)x))))]
Σ
Σ
/t.j - Te.s
D
T
1/4
KdM log (Bed) + log(p/8)
C(W)
C(Φ)
LDxWpy
+ +
n1
n'.'
Proof.
[e( )(x). v) f(w; 6² (x).
(r.j)eD, D
D
1
E
[l(ur ((x). (úx o d" (z),
Σ
Ed, (0(ur o (x), v) aw, " (2(x))))
(I.y)/,,
B
Let dw.w- (a. d*) be as defined in definition 4.1 tation difference and (v, civveese, we upper bound A by dy...- (ő, o²) //)//cc. The second term can be bounded by lipschitzness,
By our assumption of uniform absolute represen-
B
Σ (E|D]
ED. LL oz))) wt о o' (x))
Σ (E(D)
Ep, [L]|0]
wi (x)
D
LDx
w ||-
D
AE(D)
Plug in approximation to dw w (6 in Theorem 4.1 and union bound, conclude the theorem.
D
Eiep))
|| w/ in Theorem 4.4
14

---

Published as a conference paper at ICLR 2022
Table 2: Mean test accuracy for method (both domain-specific and domain-agnostic) and base- line. Same settings as in Table but difference domains are observed.
TRANSLATION
(-3, 0)
(0, -3)
(0,0)
(0,3)
(3,0)
ROTATION
0.740(0.021)
0.932(0.009)
0.960(0.005)
(.604(0.025)
-30
(..67))
0.940(0.008)
0.958(0.007)
0.654(0.0444
0.796(0.022)
0.947(0.008)
0.965(0.003)
0.644(0.043)
0.971(0.003)
0.906(0.012)
0.976(0.002)
(0.29))
-15
0.977(0.003)
(.915(0.007)
0.978(0.002)
0. 0.860(0.021)
0.977(0.0033
0.914(0.007)
0.980(0.002)
0.866(0.019)
0.919(0.011)
(..04)
0,948(0.006 (0.61().007)
0.969(0.003)
0
0.953(0.006)
0.972(0.003)
0.952(0.006)
0.950(0.007)
0.975(0.003)
(.969(0.005)
0.955(0.006)
0.756(0.024)
0.956(0.005)
(0.61))
0.978(0.002)
15
0.844(0.020)
0.969(0.005)
0.844(0.024)
0.976(0.002)
0.813(0.019)
0.967(0.008)
0.853(0.025)
0.977(0.033)
0.554(0.021)
(.95
0,903)0.021)
0.656(0.025)
30
0.657(0.029)
0,956(0 005)
0,914(0.018)
0.632(0.027)
0.656(0.028)
0.966(0.005)
0.940(0.011)
0.691(0.030)
B MORE DISCUSSION TO SECTION 5
We mention in Section 5. that the test accuracy on unseen domain might relate to the Manhattan distance between the seen and unseen domains. Here is another experiment in the same setting as in section 5.1 but the chosen observed entries are [(0,0,, (1,3), (2,2), (3,1), (4.4)).
In both Table 2 and Table 1 every factor level has been observed exactly once. If the factors categorical nominal, then permuting rows 2 and row in Table to the same balanced design with Table D and the performance shall be similar. However, the factors (rotation, translation) considered here are not nominal, for example, there a ordinal relation between rotation -30 and rotation - 15. Hence, the above-mentioned permutation seems prohibitive. Consequently, makes sense to talk about Manhattan distances between observed and unobserved entries.
In Table D cell (4.0) is 4 units away from its closest observed cell in Manhattan distance (in the following we omit to mention the metric is Manhattan distance). but in Table (4,0) is 2 units away from the closest observed entry. One can see the accuracy that domain gets much better. However, the closest distance to the observed entry is not the only factor here. For example, (0.1) in Table [ outperforms (0,1) in Table 2 lot. Therefore, the average distance to the observed entries may also be a contributing factor.
an open question how to select the best subset of tensor entries to be observed, such that the overall performance in the unseen target domains can be optimized. This question may relate to the area of factorial experiment design, where many factors are involved and some have confounded interactions. One subject is to design minimal sets of experiments such that the effects of all factors can be studied. Our theory deals particularly with the case when the factor combinations are chosen uniformly at random, without assuming any particular tensor structure. With more prior knowledge, more efficient sampling algorithms can be designed. For instance, McKay et al. (2000) discussed how to use Latin hypercube sampling to achieve smaller sample complexity. There are also some works that connect the dots between error coding theory and factorial experiment design [Ben-Gal & Levitin (2001). There could be information theoretic understanding the relation between our setting of experiment design and Manhattan distance as well. This can be an interesting research direction and beyond the scope of our paper.
Fish Algorithm The Fish algorithm was proposed in Shi et al. (202] as a domain generalization method, which achieves state-of-the-an results the WILDS benchmarks. Its intuition is that the model should be regularized (implicitly) during training such that the gradient steps on different domains invariant, thus leading to invariant feature representation across different domain. Comparing to the Fish algorithm, our proposed algorithm consistently outperforms Fish on most test domains, especially the that are "further away" from the training domains. Such results
15

---

Published as a conference paper at ICLR 2022
expected as the Fish algorithm does not consider multi-way structure into consideration. See the results in t
Fish is used for the LeNet architecture. Its inner step is trained using Adam optimizer with step size 10 and the meta step uses a learning rate of 0.5. The number of meta steps is set to be 5. We use the same hyperparameters in the GTOS experiment as well. During training, the Fish algorithm does not converge well the batch size is too large. Hence we pick batch size 20. This is of the same magnitude as the batch size in [Sh al. (202T), but our proposed model and the ERM models exhibit better generalization when trained with larger batch size 200.
found out that
Hyperparamettr Sensitivity Model selection in domain adaptation is tricky in general, since no data from the target domains is seen. One benefit of using the special low-rank formulation is that has fewer number of tuning parameters than general low-rank formulations. In addition to tuning À in the regularizer S2y, the form in eq. (5) also requires to choose rank K. We evaluate the sensitivity of À on both the source and target domains. Observing data from (i, domains on the diagonal, we train on 5000 training data using E [0.005, 0.01, 0.03, 0.05, 0. 0.1,0.5, 1], and test on 1000 data from both (i, i) source domains for E [5) and (i,j) task domains for * j E [5]. Results show that
the test performances on both source domains and target domains are insensitive to A. The mean performances and standard deviations are reported in Table 3
Table 3:
Hyperparameter sensitivity.
Source Domain
Target Domain
0.005
0.963 (0.003)
0.822 (0.005)
0.01
0.964 (0.003)
0.821 (0.010)
0.03
0.962 (0.003)
0.824 (0.006)
0.05
0.963 (0.003)
0.818 (0.007)
0.1
0.959 (0.003)
0.823 (0.008)
0.5
0.961 (0.005)
0.810 (0.010)
0.962 (0.004)
0.811 (0.00T)
C THREE-WAY GROUND TERRAIN IN OUTDOOR SCENES DATASET
To train model invariant to domain shifts, one would either need to collect massive training data from many different domains such that the model able to generalize (implicitly) to unseen cases, or build mechanism allowing (explicitly) adaptation to new scenarios utilizing limited domain information. Our work belongs to the latter.
The proposed multi-way way domain setup represents combination of the environmental or experi- mental factors, which naturally arises in many real life applications and the levels of factors are pre-known. This setup is general enough for many tasks, especially those involving data collec- tion experiments that are costly and limited by physical constraints. To make the applicability of our method more compelling, we present results on the GTOS (Ground Terrain in Outdoor Scenes) dataset (Xue et al. 2017), which a large-scale real-world dataset that naturally fits into our frame- work.
The task of outdoor ground material recognition is strongly influenced by the weather and lighting conditions, as well as the surface viewpoints. The GTOS dataset consists of over 30, 000 images covering 40 classes (cement, asphalt, brick, etc.). The multi-way domain structure include: 4 differ- ent weather conditions (cloudy dry, cloudy wet, sunny morning and sunny afternoon). 3 illumination conditions with different exposure times, and 19 viewpoints from differential angular imaging. As result, each domain is indexed on a multidimensional array of size 4 x x 19. Experimental results in table show that method outperforms both the ERM and the Fish algorithm.
For our model, we use the same architecture as described in the beginning of section 5.] a simplified low-rank structure the last two layers of LeNet. Specifically, LeNet has the structure of convl- pooll-com 2oon22-poo22. and fc3. We create 27 linear classifiers for each layer, denote as 8;, Uj Uk h, for i (3]. J E [4),
We impose the low-rank structure on both fc2
16

---

Published as a conference paper at ICLR 2022
[19). For task k)) [3] [4] x [19], 8, + Uy + Uk h for prediction. The ERM model and Fish model both use LeNet.
Both our model and the ERM model are trained using Adam optimizers with learning rate 10-3 with batch size 200. The Fish model was trained with batch size 20, its inner step is trained with an Adam optimizer with learning rate 10-2 and the meta step has learning rate 0.5. We choose 5 for the meta steps N (this is the parameter that determines how many training domains the model sees every iteration. The original paper tested N 5, 10, 20 and found the performance insensitive to N).
During training, found that Fish tends the batch size from 200 to 20. For Fish to converge, we also need to mcrease the learning rate. One conjecture of this phenomenon is because the number of observed training domains is quite large, hence it is hard to match their gradients. As Shi et al. (2021) pointed out, Fish usually does not outperform ERM when the number of domains enormous. This is consistent with our observation.
converging with large batch size, hence reduce
Table 4: Experiments on GTOS
% of observed entries
ERM
Ours
Fish
0.602(0.059)
0.663(0.091)
0.565(0.022)
0.2
0.729(0.031)
0.794(0.058)
0.653(0.083)
0.3
0.792(0.013)
0.905(0.021)
0.731(0.032)
0.4
0.800(0.021)
0.913(0.013)
0.759(0.040)
0.5
0.884(0.037)
0.946(0.008)
0.851(0.025)
17


Reviews:
[{"review_id": "qb5mkalrDH3", "reviewer": "Reviewer_mkWr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written, with very few typos, and technically sound. Nonetheless, I think that some aspects should be further clarified. Specifically:\n\n(-) Despite the gains in computational efficiency, what are the disadvantages, if any, of replacing the optimization problem in eqs. (2)-(3) by the surrogate in eq. (5)? Is it just a constraint on the space of admissible solutions?\n\n(-) In the experiments with the MNIST dataset, the authors create linear classifiers on two network layers, namely fc2 and fc3. How are the predictions of the two layers combined to produce the final decision? Moreover, what would be the effect of building the classifiers only on top of the last layer (fc3)?\n\n(-) In the same experiment (MNIST), what is the value of $K$? More importantly, how was it chosen and what is the effect of varying it?\n\nMy only concerns about the paper are:\n\ni) The applicability of the method seems a bit limited. I don't see a very large class of practical applications where the domains can be represented by a vector of attributes and hence fit into the proposed framework.\n\nii) The experimental results are not totally convincing. The method should be compared with at least one SOTA algorithm for domain generalization, e.g. Matsuura and Harada (2020).\n\n\nRefs: \n\nMatsuura, Toshihiko, and Tatsuya Harada. \"Domain generalization using a mixture of multiple latent domains.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 07. 2020.", "summary_of_the_paper": "The paper addresses the problem of domain generalization in the setting where each domain is indexed on a multidimensional array. It assumes that only a limited number of domains is observed during training and presents a technique for learning a classifier with provable good generalization performance on the unseen domains. The method consists of learning a common latent feature representation for all domains and domain-specific linear functionals, which are obtained by imposing a low-rank constraint on the tensor built by aggregating the functionals of all domains. The authors present a thorough theoretical analysis of the algorithm, including an upper bound for the excess risk on the target domain.", "summary_of_the_review": "Although I have some doubts about the applicability of the method to practical applications, I don't see this as a reason for rejection. Moreover, the paper definitely has significant novelty and is technically sound. I would like to see an improved experimental section to increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ahgxMUntBTE", "reviewer": "Reviewer_b2ge", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "Positive aspects:\n- The error bounds presented appear correct, to the best of my knowledge.\n- The authors provide some empirical evidence of the benefits of their approach, on two different datasets. The results appear good, demonstrating the interest of their approach.\n- The paper is well written, clear.\n\nConcerns:\n- Concerning the empirical evaluation, I would note that conducting additional experiments on datasets more complex than MNIST-derived ones (and the sensing dataset) would be beneficial to show that the method works well in a more realistic setting. Is there another dataset that the authors could scale to, such as adapting the CelebA dataset to a similar task as the MNIST experiments?\n- Could the authors provide more details on how the different hyper-parameters were determined?", "summary_of_the_paper": "The paper considers the problem of zero-shot domain adaptation. The contributions are two-fold. The authors propose a novel domain adaptation technique and provide bounds on the prediction error, which they provide proofs for. In addition, they provide empirical validation of their proposed approach, on two sets of datasets: one derived from MNIST, the second corresponding to sensors.", "summary_of_the_review": "I have not found flaws in the proofs or reasoning of the paper, and find the theoretical contributions particularly interesting. While I feel the experimental part is less impressive, I feel that this paper deserves acceptance. As noted in my confidence score, I am not overconfident about this, and would recommend weighing my opinion accordingly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BNl9gpwqrt4", "reviewer": "Reviewer_5mcf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- In my opinion, it is a good contribution for zero shot domain adaptation analysis, it can have good potential future work on the theoretical side.\n- The authors support their analysis with small experiments and by showing the stability of their results. They obtain a bound on the polynomial scale with exponential input dimensions so it is satisfactory.\n\nWeaknesses:\n\n- The contributions are a little limited. The method is very similar with Tripuraneni et al. (2020) if I am not missing anything, but with a condition that not using any test tasks in the training. Also the authors define uniform absolute difference in order to keep distribution same with the true distribution. \n- The total number of source and target domains need to be known beforehand, so it might not be directly used for a new target domain.\n- The paper is not the first to do finite sample analysis in zero-shot domain, see [1]. You could rephrase your claim.\n- The paper was well written(there are a couple of typos especially in the equations - such as in theorem 4.2, 3rd line should be $=$, not $\\leq$.), however it made me go back and forth a lot(needs a bit organization). Its relation with previous work could be stated better, the analysis and method parts could be separated. Some of the definitions in section 4 can be carried to preliminary since they are borrowed from the previous work. \n\nQuestions:\n\n- How does the correlations between the labels/domains affect your bounds? How do you quantify the similarity between the domains other than through classifier parameters? \n- Did you test your algorithm on larger real data? You could try lower p and with not-very-different source and target domains. \n- The method adds sum of linear functionals to a neural network with a couple of weight norm constraints, so I would expect results other than 30 degree rotated MNIST(although there are convexity and linearity assumptions in the theoretical part). \n- In table 3, what did you choose as the value of K? How did you choose your experimental details, such as why 11 classes?\n\n[1] Blitzer, John, Dean P. Foster, and Sham M. Kakade. \"Zero-shot domain adaptation: A multi-view approach.\" Tech. Rep. TTI-TR-2009-1 (2009).", "summary_of_the_paper": "Short summary: \n\nThe authors propose a zero-shot domain adaptation method with the assumption of each domain having the same set of labels. They obtain finite sample complexity bounds that contain the number of samples(n) per class in the training, the number of seen(training) and unseen(test) tasks under regularity assumptions on the loss and mappings. They provide accuracy results for MNIST and MNIST with rotated digits. \n\nMethod: \n\nFirst, a common linear mapping is used to obtain a common representation for tasks. Then each domain-specific classifer(linear) combines at each index as a rank K tensor. A tensor completion is applied at each index that would give classifier parameters for unseen data as well, that allows them to predict without any data from the target domain. They assume same number of samples and same input dimensions for each domain (the latter can directly be extended to different dimensions). For the experiments, they use LeNet and directly predicted decomposed tensors rather than training and applying tensor completion.\n\nContributions: \n\nThe authors extend Tripuraneni et al. (2020) method and proofs from transfer learning to zero-shot case. They show a uniform convergence bound that has polynomial complexity with respect to the # tasks, # dimensions and rank. They derive excess risk on the order of n^-1/4. \n", "summary_of_the_review": "In general, I am a little bit concerned about the significancy of the paper's contributions. The method and theory part shows a lot of similarity with Tripuraneni et al. (2020). However, bringing it and the analysis to zero shot domain adaptation is valuable in my opinion. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ABzk57btCju", "reviewer": "Reviewer_Qy5s", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: While the theoretical results are interesting, the underlying assumptions are quite restrictive and will not hold for many computer vision tasks.\nWeaknesses; Results on MNIST and the fiber sensing dataset are vastly inadequate. There are more interesting datasets for evaluating domain generalization methods, such as WILDS. The WILDS leaderboard lists a few SOTA results.", "summary_of_the_paper": "This paper proposes a specific domain adaptation framework where a subset of all possible domains is are observed during training. Given sufficient training samples for the observed source domains, a common latent representation as well as a domain specific linear classifier is learned. Theoretical conditions under which the learned representations will be effective for unseen domains are provided. Experiments using two datasets are provided. ", "summary_of_the_review": "Unless I see results on more challenging datasets such as WILDS, I will remain unconvinced of the usefulness of this work. It is not just the number of source domains T that matter. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for your submission to ICLR.

This paper explores zero-shot adaptation from a theoretical perspective.  Three of the four reviewers are quite positive about the paper, particularly after the discussion phase.  One reviewer was more negative, citing a lack of compelling experiments and some possibly restrictive assumptions.

The authors responded to these concerns, as well as the concerns of the other reviewers.  One of the more positive reviewers increased their score from 6 to 8.  I did not hear from the negative reviewer, but my feeling is that I tend to agree with the authors that the focus of the paper is more on the theoretical side.  Moreover, the authors did add some additional results to the main paper, so I am of the opinion that the paper should indeed be accepted to the conference.

Even though this is paper is on the theoretical side, please do include as strong a set of empirical results as possible in the final version.  Also keep in mind the other suggestions from the reviewers when preparing the final manuscript.
Decision: Accept (Poster)