First Steps Toward Understanding the Extrapolation of Nonlinear Models to Unseen Domains
Authors: Kefan Dong
Tengyu Ma
Venue: ICLR 2023 poster (2023)
Keywords: extrapolation of nonlinear models
theory
structured domain shift
gaussian kernel

Abstract: Real-world machine learning applications often involve deploying neural networks to domains that are not seen in the training time. Hence, we need to understand the extrapolation of \textit{nonlinear} models---under what conditions on the distributions and function class, models can be guaranteed to extrapolate to new test distributions. The question is very challenging because even two-layer neural networks cannot be guaranteed to extrapolate outside the support of the training distribution without further assumptions on the domain shift. This paper makes some initial steps towards analyzing the extrapolation of nonlinear models for structured domain shift. We primarily consider settings where the \textit{marginal} distribution of each coordinate of the data (or subset of coordinates) do not shift significantly across the training and test distributions, but the joint distribution may have a much bigger shift. We prove that the family of nonlinear models of the form $f(x)=\sum f_i(x_i)$, where $f_i$ is an \emph{arbitrary} function on the subset of features $x_i$, can extrapolate to unseen distributions, if the covariance of the features is well-conditioned. To the best of our knowledge, this is the first result that goes beyond linear models and the bounded density ratio assumption, even though the assumptions on the distribution shift and function class are stylized.

Published as a conference paper at ICLR 2023
FIRST STEPS TOWARD UNDERSTANDING THE EXTRAP- OLATION OF NONLINEAR MODELS TO UNSEEN Do- MAINS
Kefan Dong Stanford University Sttandonn@stanfooooee
Tengyu Ma Stanford University t tengyuma@stanfordd.
ABSTRACT
Real-world machine learning applications often involve deploying neural networks to domains that are not seen in the training time. Hence, we need to understand the extrapolation of nonlinear models what conditions on the distributions and function class, models can be guaranteed to extrapolate to new test distributions. The question very challenging because even two-layer neural networks cannot be guaranteed to extrapolate outside the support of the training distribution without further assumptions on the domain shift. This paper makes some initial steps towards analyzing the extrapolation of nonlinear models for structured domain shift. We primarily consider settings where the marginal distribution of each coordinate of the data (or subset of coordinates) do not shift significantly across the training and test distributions, but the joint distribution may have a much bigger shift. We prove that the family of nonlinear models of the form f(x) Σ (1()), where fi is an arbitrary function on the subset of features 2;, can extrapolate to unseen distributions, if the covariance of the features is well-conditioned. To the best of our knowledge, this is the first result that goes beyond linear models and the bounded density ratio assumption, even though the assumptions on the distribution shift and function class are stylized.
INTRODUCTION
In real-world applications, machine learning models often deployed domains that are not in the training time. For example, we may train machine learning models for medical diagnosis on data from hospitals in Europe and then deploy them to hospitals in Asia.
Thus, we need to understand the extrapolation of models to new test distributions - how the model trained on one distribution behaves on another unseen distribution. This extrapolation of neural networks is central to various robustness questions such as domain generalization (Gulrajani & Ganin
Lopez-Paz (0200;; Ganin al. (2016); Peters et al. (2016) and references therein) and adversarial
robustness GGoodfellw et al. 2014 Kurakin et al. 2018), and also plays a critical role in nonlinear bandits and reinforcement learning where the distribution is constantly changing during training
(Dong et al. 2021 Agarwal et al. 2019 Lattimore & Szepesvári 2020 Sutton & Barto 2018).
This paper focuses on the following mathematical abstraction of this extrapolation question:
Under what conditions on the source distribution P, target distribution Q, and function class F do we have that any functions J.g E F thut agree on P are also guaranteed agree on Q?
Here measure the agreement of two functions on P by the & distance between f and under distribution P. that is, |I gll A Ez~r((f<x) ) The function be thought of as the learned model, g as the ground-truth function, and thus || gllp as the error on the source distribution P.
This question is well-understood for linear function class F. Essentially, if the covariance of Q can be bounded from above by the covariance of P (in any direction). then the error Q is guaranteed

---

Published as a conference paper at ICLR 2023
to be bounded by the error on P. We refer the reader to Lei et al. (2021): Mousavi Kalan et al. (2020) and references therein for more recent advances along this line.
By contrast, theoretical results for extrapolation of nonlinear models is rather limited. Classical results have long settled the case where P and Q have bounded density ratios (Ben-Davie & Urner 2014 (Sugiyama et al. 2007). Bounded density ratio implies that the support of Q must be subset of the support of P. and thus arguably these results do not capture the extrapolation behavior of models outside the training domain.
Without the bounded density ratio assumption, there was limited prior positive result for characterizing the extrapolation power of neural networks. [Ben-David al. (2010) show that the model can extrapolate when the HAAH-distance between training and test distribution is small. However, it remains unclear for what distributions and function class, the H-A--distance can be bounded In general, the question is challenging partly because of the existence of such strong impossibility result. As soon as the support of Q is not contained in the support of P (and they satisfy some non-degeneracy condition), it turns out that even two-layer neural networks cannot extrapolate- there are two-layer neural networks f and y that agree on P perfectly but behave very differently on Q (See Proposition 5 for a formal statement.)
The impossibility result suggests that any positive results on the extrapolation of nonlinear models require more finengrained structures the relationship between P and Q (which are common in Sractice/Koh et al. (202T): Sagawa et al. (202)) as well as the function class F. The structure in the domain shift between P and Q may also need to be compatible with the assumption the function class F. This paper makes some first steps towards proving certain family of nonlinear models can extrapolate to new test domain with structured shift.
We consider a setting where the joint distribution of the data can does not have much overlap across P and Q (and thus bounded density ratio assumption does not hold), whereas the marginal distributions for each coordinate of the data does overlap. Such a scenario may practically happen when the features (coordinates of the data) exhibit different correlations on the source and target distribution. For example, consider the task of predicting the probability of a lightning storm from basic meteorological information such as precipitation, temperature, etc. We learn models from some cities on the west coast of United States and deploy them to the east coast. In this case, the joint test distribution of the features may not necessarily have much overlap with the training distribution- correlation between precipitation and temperature could be vastly different across regions, e.g., the rainy season coincides with the winter's low temperature on the west coast, but not so much on the cast coast. However, the individual feature's 's marginal distribution is much more likely to overlap between the source and target-the the possible ranges of temperature on east and west coasts are similar.
Concretely, we assume that the features x E + have Gaussian distributions and can be divided into two subsets I1 E R and 22 E R such that each set of feature 2; (i E {1,22) has the same marginal distributions on P and Q. Moreover, we assume that 2 and 22 not exactly correlated on P-the covariance of features x on distribution P has strictly positive minimum eigenvalue.
As argued before, restricted assumptions on the function class F are still necessary (for almost any P and Q without the bounded density ratio property). Here, we assume that F consists of all functions of the form f(x) = fi (æ1) + f2(22) for arbitrary functions fi R + E and f2 : R + R. The function class F does not contain all two-layer neural networks (so that the impossibility result does not apply), but still consists of a rich set of functions where each subset of features independently contribute to the prediction with arbitrary nonlinear transformations. We show that under these assumptions, if any two models approximately agree on P, they must also approximately agree on Q - -formally speaking, vʃ.g E F, || - allQ S I|s - d|l (Theorem
We also prove a variant of the result above where we divide features vector x E Id into d coordinate, denoted by
(I1..... xz2) where 2; RR The function class consists of all combinations of nonlinear transformations of rı's, that is, F = { fe(xx)) Assuming coordinates of x are pairwise Gaussian and a non-degenerate covariance matrix, the nonlinear model E F can extrapolate to any distribution Q that has the same marginals as P (Theorem 3
In fact, the -isdttittncce likely cannot be bounded when the function class contains two-layer neural networks, and the supports of the training and test distributions do not overlap -when there exists function that distinguish the source and target domain, the HAH divergence will be large.
2

---

Published as a conference paper at ICLR 2023
training distributions
test distribution
P1
Pz
P3
12
2 3
5
6
2
5
6
1
2
4
5
6
2
3
3
5
5
6
6
marginal coverage
clusterable
marginal coverage non clusterable
(a)
(b)
(c)
(d)
Figure 1: Visualization of three different training distributions P1, Ps, P's and test distribution Q. where the orange color blocks marks the support. (a) and (b): distributions PI, P2 that do not satisfy conditions and cannot extrapolate. (c): distribution P3 that satisfies our conditions even though the support of P3 is sparse. (d): the test distribution.
These results can be viewed as first steps for analyzing extrapolation beyond linear models. Compared the works Lei et al. (202T) on linear models, assumptions the covariance of P are quali- tatively similar. We additionally require /' and Q have overlapping marginal distributions because it is even necessary for the extrapolation of one-dimensional functions on single coordinate. Our results work for more expressive family of nonlinear functions, that is, F (Ei (x::), than the linear functions.
We also present a result on the case where 2 's are discrete variables, which demonstrates the key intuition and also may be of its own interest. Suppose we have two discrete random variable 2 and I2. In this case, the joint distribution of P and Q can be both presented by a matrix (as visualized in Figure and the marginal distributions are the column and row sums of this joint probability matrix. We prove that extrapolation occurs when (1) the support of the marginals of Q is covered by P, and cannot find subset of rows and columns such the support of P in these rows and columns lies within their intersections.
(2) the density matrix of P is non-clusterable-
In Figure 1 visualize a few interesting cases. First, distributions Pl. P2 visualized in Figures la and 1b, respectively, do not satisfy our conditions. Fundamentally, there are two models that agree on the support of distribution P1 (or P2), but still differ much on the non-support. In contrast, our result predict that models trained on distribution Ps in Figure Ic can extrapolate to the distribution Q in Figure 1d, despite that the support of P3 is sparse and their support have very little overlap.
We also note that the failure of Pi and Pg demonstrate the non- con-triviality of our results. The overlapping marginal assumption by itself does not guarantees extrapolation, and condition (2), or analogously the minimal eigenvalue condition for the Gaussian cases, is critical for extrapolation.
Our proof technique for the theorems above is generally viewing ||A]] as Ky(h,, h) for some kernel Kp F x F + R. Here ht is shorthand for the error function - y. Note that the kernel takes in two functions F as inputs and captures relationship between the functions. Hence, the extrapolation of F (i.c., proving | < ||hlpp for all h F) reduces to the relationship of the kernels (i.c., whether K2 (h, h) S Kp(h, h) for all h E F), which is then governed by properties of the eigenspaces of kernel Kr, Kq. Thanks to the special structure of our model class F = E (zz)) we can analytically relate the eigenspace of the kernels Kp, Kq to more explicitly and interpretable property of the data distribution of P and Q
PROBLEM SETUP
We use P. and Q to denote the source and target distribution over the space of features X' X x x Mr, respectively. We measure the extrapolation of a model class F R from P to Q
3

---

Published as a conference paper at ICLR 2023
by the F-restricted error ratio, F-RER as shorthand
Bol(f(x) - 9(x))
T(. & sup figEJ
(1)
Bp((f(x) 9(x)
When F) is small, if two models f.g E F approximately agree on P (meaning that Ep[[f(z) - ((x)) | small), they must approximately agree on Q because Eol(f(x) - 9( g(
T ((P:Q,
The F-restricted error ratio monotonically increases we enlarge the model class F, and eventually, r, F)) becomes the density ratio between Q and P if the model F contains all functions with bounded output. To go beyond the bounded density ratio assumption, in this paper we focus on the
structured model class F {Σ i= [(x,,) Ep (xx)) < bo, Vi [k]] where Si X R is an arbitrary function. Since FF is closed under addition, we can simplify Eq. ① to T(P, P,P,C, Q,F)=
[o]f(=)* For simplicity, we omit the dependency on P. Q, F when the context clear. SuPJeF Ep(
If the model class F includes the ground-trute labeling function, T(P, Q. upperbounds the ratio between the error on distribution Q and the error on distribution P (formally stated in Proposition [ which provides the robustness guarantee of the trained model. This is because when g corresponds to the ground-truth label, (r(((()) - ( becomes the l error of model f.
Proposition 1. Let T be the F-RER defined in Eq. T For any distribution P, Q and model class F, there exists a model f in F that represent the true labeling y X - R on both P and Q:
E B4(p=o)(u(0)- ((x))) ser.
(2)
then we have
VFEF, Eglly(>) f(x)) s (8r + 4)E 47Mp[(y(z)) f()))
(3)
Proof of this proposition is deferred to Appendix A.1
Relationship to the HAH--isstanc. Compared with the /iAA-disttnnce (Ben David et al. 2010):
dHAm (P, Q) 2sup f.gEF (Pr=)l((x)) + g(x)] - Prz- * g())]l
(4)
differences (1) we consider lg loss instead of classification loss, and (2) focuses the ratio of losses whereas dHAH focuses on the absolute difference. As we will see later, these differences bring the mathematical simplicity to prove concrete conditions for model extrapolation.
Additional notations. Let I [E] be the indicator function that equals if the condition is true, and For vector x Rd we use [z], to denote its i-th coordinate. Similarly, [M] denotes the (i,j)-th element of a matrix M. We use M to represent the element-wise n-th power of the matrix M (i.c., [Mo]],
0 otherwise. For an integer n, let [n] be the set {1, 2.... .n..
([M],,)")) Let Ia Radd be the identity matrix, 1 E Idd the all-1 vector and 6s,d the i-th base vector. We omit the subscript d when the context is clear. For a square matrix Raxd we use diag(P) gdxd to denote the matrix generated by masking out all non non-diagonal terms of P. For list Ti, ,d, diag((Ø1, ... aa)) Rdxdd be the diagonal matrix whose diagonal terms are 0i, ... .d.
Jd, let
For symmetric matrix M E Rdxd Jet Å (M) S A2(M) < ... < (M( be its eigenvalues in ascending order, and Amax (M), Amin Am), (M) the maximum and minimum eigenvalue, respectively. Similarly, we use (M), ... mmin(d dz) da) (M) to denote the singular values of M E Rdixds
3 MAIN RESULTS
In this section, we present our main results. Section 3.1 discusses the case where the features have discrete values. In Section 3.2 and 3.3 we extend our analysis to two other settings with real-valued features.
For simplicity, we set 0/0 0.
4

---

Published as a conference paper at ICLR 2023
3.1 FEATURES WITH DISCRETE VALUES
For better exposition, we discuss the case that x = (21, 222) here and defer the discussion of the general case to Appendix A.5 We assume that vi takes the value in (1, ... :ri) for E [2]. Hence, the density of distribution P can be written in a matrix with dimension v1 x T2-
We measure the (approximate) clusterablity by cigenvalues of the Laplacian matrix of bipartite graph associated with the density matrix P E IR X which is known to capture the clustering structure of the graph (Chung] 1996 Alon 1986). Let Gp be weighted bipartite graph whose adjacency matrix equals the density matrix P E R concretely, U = {u1, Mry } and V = {oi,-.. Ur,] 22 = j). To define the signless Laplacian of Gp, let di Rn and d2 E IR"2 be the row and column sums of the weight matrix P (in other words, degree of the vertices), and Dj diag(d1) E RR.x. D2 = diag(d2) E * the diagonal matrices induced by d1, d2, respectively. The signless Laplacian Kp and normalized signless Laplacian Kp are:
are the sets of vertices, and the weight between ug fy is P(z1
Kp = (
D2 p)).
Kp diag(Kp) 1/2 pdiag(Kp) (Kp) 11/11
(5)
Compared with the standard Laplacian matrix, the non non-diagonal terms in the signless Laplacian Kp are positive and equal to the absolute value of corresponding terms in the standard Laplacian matrix. In the following theorem, we bound the F-RER from above by the eigenvalues of Kp and the density ratio of the marginal distributions of Q.
Theorem 2. For any distributions P. Q over discrete random variables æ1, 22, and the model class F (f(( + fz(x2)} where fs : X, - R is an arbitrary function, the F-RER can be bounded above:
Q(x: =
TP,Q. < (RP(
max
(6)
P(z. = t)
Compared with prior works that assumes a bounded density ratio on the entire distribution (e.g., Ben-David Umer 2) (Sugiyama et al. (2007), we only require a bounded density ratio of the marginal distributions. In other words, the model class f(x) = fi (x1) ) + f2(22) can extrapolate to distributions with a larger support (see Figure Tp). In contrast, for an unstructured model (i.e., fx) is an arbitrary function of the entire input 2)), the model can behave arbitrarily on data points outside the support of P.
Qualitatively, Theorem 2 proves sufficient conditions under which the structured model class can
extrapolate to unseen distributions (as visualized in Figure -- In particulary, Theorem 2 iipplis
that for non-trivial extrapolation, that is, T(P, Q, F) < co, we need (a) (2x,e()] (i.e., the support of the marginals of Q is covered by P), and (b) A2 (kp) > 0. To interpret condition (b), note that Cheeger's 's inequality implies that A2(Kr) > 0 if and only if the bipartite graph Gp connected (Chung 1996: Alon 1986 that is, there does not exist non-empty strict subsets of vertices U' U.V' V V. such that P(æ1 E U',22 22 of V')
P(z,=t) < co
Q
0 and P(x1 & UU, V') O. Equivalent, we cannot shuffle the rows and columns of to form a block diagonal matrix where each block is strict sub-matri of P. In other words, the density matrix P is non-clusterable as discussed in Section I
Proof sketch of Theorem 2 In the following we present proof sketch of Theorem 2 We start with a high-level proof strategy and then instantiate the proof on the setting of Theorem
Suppose we find set of (not necessarily orthogonal) basis (bi, bb,) where by X R. such that any model f E F can be represented as a linear combination of basis, that is, f E neb. Since the model family F is closed under subtraction, have
1 /
sup Eg E (x))
T(P.Q,F) = sup SEF
sup VERT
VERT Ep (E (x)
[o (x)
'Cheeger's inequality measures the clustering structure of a graph by the eigenvalues of its standard Laplacian However, the signless Laplacian and standard I. Laplacian have the same eigenvalues for hipartite graphs Cvetkowić al. 2007); Grone et al. (990..
5

---

Published as a conference paper at ICLR 2023
If we define the kernel matrices [Kr],] (=)(b(=));; and [Kqli, (x)bg(2)bb(()) (we use the same notation for the kernel matrix and signless Laplacian because later we will show that the kemelss Kp p, Kg equal to the signless Laplacian of the bipartite graphs Gp, Go with specific choice of the basis bz). it follows that
Ene= way vny Bol(()))))) sup w KQu
sup HER*
(8)
Σij=1 vuy (r((()((())) vER* v Kpv
Hence, upper bounding 7
reduces to bounding the eigenvalues of kernel matrices Kp, Kq-
Since the model has the structure f(x) fi + f2(22), we can construct the basis {be Fi=1 explicitly. For any i E [2], E [ril. with little abuse of notation, let (x,( = I[ [z; = t] We can verify that the set hept),e))) is indeed a complete set of basis. As a result, the kernel matrices Kp can be computed directly using its definition:
( P(x, = =,,, = s),
when i + j. P(xx = [s when i = j.
=
which is exactly the Laplacian matrix defined in Eq. (
To prove Eq. (6), need upperbound the eigenvalues of Ko. Since the eigenvalues of the normalized signless Laplacian Kę is universally upper bounded by 2 for every distribution Q, first write Kp, Kę in terms of Kp, Kę. Formally, let Dp diag(K (P) and Do diag(Ko) and we have
T KQU
T T 1/2u Q KoD DD D DP? Amin(Kp)
S Amar (Ko)
1/2 2112
sup VER V KN "E e
sup
sup VER |
(10)
However, this naive bound is vacuous because for any P we have Amin (Kp) = O. In fact, Kp and Ko share the eigenvalue and the corresponding eigenvector u E Britta with [u]: = (-1)llesn) Therefore we can restrict to the subspace orthogonal to the direction u, and then Amin ( becomes
(P) in Eq. (T).. Finally, by basic algebra we also have Amax (Kq)= S 2 and suPweR [D 3 <
m (er))) Q(a=())
P(z==t) which complete the proof sketch. The full proof of Theorem 2 is deferred to
Appendix A.3
3.2 FEATURES WITH REAL VALUEE
In this section we extend our analysis to the case where I1, D2, are real-valued random variables. Recall that our model has the structure f(x) = Di=1 fi(1;) where fi is arbitrary one-dimensional function.
When d 2, we view this setting direct extension of the setting in Section 3.1 where each Iy's 's has infinite number of possible values (instead of finite number), and thus the Laplacian "matrix" becomes infnite-dimensiona Nonetheless, we still bound the F-RER from above, stated in the following theorem.
Theorem 3. For any distributions P. Q over variables z = (z,,... ,Za) with matching marginals, assume that (1)) has the distribution of a two-dimensional Gaussian random variable for every i.j E [d]. Let 3 = ( .x)) be the normalized input where à; (x; Ep zero mean and unit variance for every i [d), and Ep Er T the covariance matrix of ā. Then
1/22 has
T(P.Q.F) Amin (Ep)
(11)
For better exposition, first focus the where every I; has zero mean and unit variance, hence ह x and Ep Ep [xxxx" Compared with linear models, Theorem 3 proves that the structured nonlinear model class f(r) = E(=1(((;)) f((z;) can extrapolate with similar conditions- for linear models Fuieaar - {tr U E Rd] we have
| 212
Eg xr 1 < Amin(Pp) Amin (Ep)
T(P, Q, Flinee))
sup wERd
sup
1 T x 2
vERd O Ep xx lo

---

Published as a conference paper at ICLR 2023
which equals to the RHS of Eq. 111 up to factors that does not depend on the covariance Ep, Eq.
We emphasize that we only assume the marginals on every pair of features 24, zj is Gaussian, which does not imply the Gaussianity of the joint distribution of æ. In fact, there exists non-Gaussian distribution that satisfies our assumption.
Proof sketch of Theorem 3 On high level, treat the features 's discrete random variables, and follow the same proof strategy as in Theorem For better exposition, we first assume that x; has zero mean and unit variance for every E [d], hence Ep = Ep _ Ep(xxT] T].
First consider simplified case when d = 2. Because 21, 22 continuous, the normalized
1
A)
signless Laplacian Kp is infinite dimensional, and has the form Kp
(A
I
where A
is an infinite dimensional "matrix" indexed by real numbers 21, 22 E with values [A] [A]ar.2 =
P(2,, and I is the identity "matrix". Recall the proof of Theorem gives
Q(===t)
max E P(a:=1)
(12)
By the assumption that P.Q have matching marginals, we get maXie P(a;=t) = As result, only need to lowerbound the second smallest eigenvalue of Kp. To this end, first write A in its singular value decomposition form A UAVT, where UUT = I,VV = / and A = diag((an (n20) with oo
Q(a,zt)
0 2 Then we get
Kp
AT
1
A
1
U 0 0
(
V
I A
A
I
U
VT).
(13)
1)
Since the matrix Kp A
consists of four diagonal sub-matrices, we can shuffle the rows
A
{ }
and columns of Kp to form block-diagonal matrix with blocks
On
0,1,,, As
On
1
2 0, the smallest and second smallest eigenvalues of Kp are - dg and 1 - 01. respectively, meaning that px) = >2((K (p) = 1-01 By the assumption that (æ1, x22) follows from Gaussian distribution, the "matrix" is Gaussian kernel, whose eigenvalues and eigenfunctions can be computed analytically- Theorem 11 proves that 0 = | [2] if 111,, 22 have zero mean and unit variance. Consequently, X2(
result, the eigenvalues of Kp are 1 oo, 1 + 01, Because = op 2 01
01
|E [2]22]]
Amin((Ep)
Now we briefly discuss the case when d = 3, and the most general cases (i.e., > 3) are proved similarly. When d = 3, the normalized kernel will have the following form
A
B
Kp =
A BT
C
(14)
T
CT
By the assumption that .1, 42 are zero mean and unit variance with joint Gaussian distribution, matri- = P(zz, x1)/ P(x))) = [Al Similarly, matrices B, C are symmetric. In addition, Theorem II shows that the eigenfunc- tions of the Gaussian kernel is independent of the value Ey[x,,,). Hence, the matrices A, B,C C shares the same eigenspace and can be diagonalized simultaneously:
ces A symmetric because [A]] [A]p,.s = P(11, x2)/ /P(zi) /
1
A
B
U
A
AB
0
0
Kr
A
T
1
C
=
0
1
A
I
Ac
0
TT
0
(15)
B
T
CT
I
A
n
AT
I
0
0
UT)
By reshuffling the columns and rows, the eigenvalues of Kp are the union of the eigenvalues of following matrices
{ (K(") m- S
(Gnla))
1
(n(A)
on(C)
on((B)
(16)
(n((B (C)
1
0,1,2,
7

---

Published as a conference paper at ICLR 2023
Theorem implies that (A) ((Ep),2)",,,n ([Ep]1,)) and oC(C) (EPl223)". Then, this theorem follows directly by noticing Amiu (I)
Consequently we get ( Dnn
(mpp(Ep) for n 2 (Lemma 13
Finally, the general case where I2 has arbitrary mean and variance can be reduced to the case where 24 has zero mean and unit variance (Lemma 8). The full proof of Theorem [1 is deferred to Appendix A.66 A.6
3.3 TWo FEATURES WITH MULTI-DIMENSIONA GAUSSIAN DISTRIBUTION
Now extend Theorem to the case where Iι E Rd E R2 are two subset of features with dimensions d1, d2 > 1, respectively, and the input x = (Z1, 22) has Gaussian distribution. Recall that the model class is F {f1 (æ1) + f2(22) Bplf( still upper bound the F-RER by the eigenvalues the covariance matrix Ep, which is stated in the following theorem.
co, Vi [2]]. In this case, we can
Theorem 4. For any distributions P, Q over variables x = (x1, where I E Rd, 22 Rdd let Ep = Eplex J. If (I1,42) has Gaussian distribution both P and Q with zero mean and matching marginals, and Ep [x = I, Eppee [x22]] = I, then
2
7 T(,.Q.F) Amnin (Ep)
(17)
We defer the proof of Theorem 4 Appendix A.7
Compared with Theorem 3 where the features 1, ad are one-dimensional, our condition for the
covariance is almost the same: Amia (Ep) > O. However, the model class considered Theorem 4 is
more powerful because captures nonlinear interactions between features within the same subset. compromise, the assumption on the marginals of P and Q is stronger because Theorem requiiress matching marginals on each subset of the features, whereas Theorem only requires matching marginals each individual feature.
Remarks. Our current techniques can only handle the case when the input divided into k subsets. This is because for k 2 3 must diagonalize multiple multi-dimensional Gaussian kernels simultaneously using the same set eigenfunctions, as required the proof of Theorem However, these multi- multi-dimmenional Gaussian kernels do not share the same eigenfunctions because the rotation matrix U, depends on the covariance Ep(z,a) ]. Hence, the proof strategy for Theorem fails for the case 2 3.
LOWER BOUNDS
In this section, we prove lower bound as motivation to consider structured distributions shifts. The following proposition shows that the worst case, models learned on cannot extrapolate to Q when the support of distribution Q is not contained in the support of P.
Proposition Let the model class F be the family of two-layer neural networks with ReLU acti- vation: F = {Σx a;ReLU(w; x + b,) w; E Rd 0s b E B Suppose for simplicity that all the imputs have unit norm (i.e., ||0||| = 1). If Q has non-zero probability mass on the set of points well-separated from the support of P in the sense that
Be > 0, Q(1=: ||x||2 1, dist(z, supp(P)) 2 e}) 0,
(18)
we can construct a model f E F such that || 0 but |lf can be arbitrarily large.
A complete proof of this proposition is deferred to Appendix A.8 On high level, prove this proposition by construct a two-layer neural network 9, that represents a bump function around any given input grt-1 As result, when t is point in supp(Q)) supp(P), the model gi (z) will have zero l norm on P but have a positive &g norm on Q. This construction inspired by Dong al. 2021 Theorem 5.1).
8

---

Published as a conference paper at ICLR 2023
5
RELATED WORKS
The most related work is Ben-David et al. (2010), where they use the H. H-d--distance to measure the maximum discrepancy of two models f,9 F any distributions P. Q. However, it remains open question to determine when Hidd-distance is small for concrete nonlinear model classes and distributions. On the technical side, the quantity t is an analog of the Hidd-distaece for regression problems, and we provide concrete examples where is upper bounded even if the distributions P, Q have significantly different support.
Another closely related settings are domain adaptation (Ganin & Lempitskyl 2015 Ghifary et al. 2016 Ganin et al., 2016) and domain generalization (Gulrajani & Lopez-Paz [2020] Peters al. 2016). where the algorithms actively improve the extrapolation of learned model either by using
unlabeled data from the test domain (Sun & Saenko 2016 Li et al. 2020a Zhang et al. 2019). or
learn an invariant model across different domains (Arjovsky et al. 20199] et al. 2016 Gulrajani
Lopez-Pazz 2020). There are also algorithms that learn features whose distributions on the source and target domain have small discrepancy measured by the maximum mean discrepancy (Donahue
ct al. 2014 Long al. 2015), or the Wasserstein distances (Shen et al., 2018 Courty et al. 2017). In comparionn, this paper studies whether model trained on distribution (without any implicit bias and unlabeled data from test domain) extrapolates to new distributions. There are also prior works that theoretically analyze algorithms that use additional (unlabeled) data from the test distribution, such as self- seff-training (Wei et al.] [2020] Chen et al.) 2020). contrastive learning (Shen et al. 2022
HaoChen al. 2022). label propagation (Cai et 2021 etc.
CONCLUSIONS
In this paper, we propose to study domain shifts between P and Q with the structure that each feature's 's marginal distribution has good overlap between source and target domain but the joint distribution of the features may have a much bigger shift. As first step toward understanding the extrapolation of nonlinear models, we prove sufficient conditions for the model f(x) ->* f(. to extrapolate where fi is an arbitrary function of a single feature.
Even though the assumptions on the shift and function class stylized, to the best of our knowledge, this is the first analysis of how nonlinear models extrapolate when source and target distribution do not have shared support in concrete settings. There still remain many interesting open questions. which we leave as future works:
(a) Our current proof can only deal with restricted nonlinear model family of the special form (xx) = Σ fi(x;). Can we extend to more general model class? (b) In this paper, we focus on regression tasks with &2 loss for mathematical simplicity, whereas majority of the prior works focus the classification problems. Do similar results also hold for classification problem?
ACKNOWLEDGMENT
The authors would like thank Yuanhao Wang, Yuhao Zhou, Hong Liu, Ananya Kumar, Jason D. Lee, and Kendrick Shen for helpful discussions. The authors would also like to thank the support from NSF CIF 2212263.
REFERENCES
Alekh Agarwal, Nan Jiang, and Sham M Kakade. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96 1986.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:190..0289) 2019.
Sara Beery, Arushi Agarwal, Elijah Cole, and Vighnesh Birodkar. The iwildcam 2021 competition dataset. arXiv preprint arXiv:2105.034// 2021.

---

Published as a conference paper at ICLR 2023
Shai Ben-David and Ruth Umer. Domain adaptation can quantity compensate for quality? Annals of Mathematics and Artificial Intelligence, 70(3):185-200 2014.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fermando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, (9(1-2)1151-113 2010.
Tianle Cai, Ruiqi Gao, Jason Lee, and Qi Lei. A theory of label propagation for subpopulation shift. In International Conference on Machine Learning, pp. 1170-1182. PMLR, 2021.
Enrico Celeghini, Manuel Gadella, and Mariano A del Olmo. Hermite functions and fourier series. Symmerry, 13(5):853, 2021.
Yining Chen, Colin Wei, Ananya Kumar, and Tengyu Ma. Self-training avoids using spurious features under domain shift. arXiv preprint arXiv:2006. 10032, 2020.
Fan RK Chung. Laplacians of graphs and cheeger's inequalities. Combinatorics, Paul Erdos is Eighty, 2(157-172) 1996.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamoniy. Joint distribution optimal transportation for domain adaptation. Advances in Neural Information Processing Systems, 30, 2017.
Dragoš Cvetković, Peter Rowlinson, and Slobodan K Simić. Signless laplacians of finite graphs. Linear Algebra and its upplications, 423(1):155-171, 2007.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In International Conference on Machine Learning (ICML), volume 32, pp. 647-655, 2014.
Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. arXiv preprint arXiv:2102.04168, 2021.
Gregory E Fasshauer. Positive definite kernels: past, present and future. Dolomites Research Notes on Approximation, 4:21-63, 2011.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference machine learning, pp. 1180-1189, PMLR, 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarre training of neural networks. The journal of machine learning research, 17(1):2096-2033 2016.
Muhammad Ghifary, W Bastiaan Kleijn, Mengjie Zhang, David Balduzzi, and Wen Li. Deep reconstuationnclaasffcttiin networks for unsupervised domain adaptation. In European conference on computer vision, pp. 597-613. Springer, 2016.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnsssing adversarial examples. arXiv preprint 14Xivv:4422.633 2014.
Robert Grone, Russell Merris, and VS_ Sunder. The laplacian spectrum of a graph. SIAM Journal on matrix analysis and applications, 11(2):218-22 1990.
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. arXiv preprint arXiw:2007.01434. 2020.
Jeff HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations, arXiv preprint arXiv:2204.0264. 2022.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsub- ramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao. Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton A. Earnshaw, Imran S. Haque, Sara Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine. Chelsea Finn, and Percy Liang. WILDS: A benchmark wi-the-wild distribution shifts. In International Conference on Machine Learning (ICML), 2021.
10

---

Published as a conference paper at ICLR 2023
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. In International Conference on Machine Learning (ICML), 2020.
Alexey Kurakin, Ian J Goodfellow, and Samy Bengio. Adversarial examples in the physical world.
In Artificial intelligence safety and security, pp. 99-112. Chapman and Hall/CRC, 2018.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Qi Lei, Wei Hu, and Jason Lee. Near-optimal linear regression under distribution shift. In Interna- tional Conference on Machine Learning, pp. 6164-6174. PMLR, 2021.
Jingjing Li, Erpeng Chen, Zhengming Ding, Lei Zhu, Ke Lu, and Heng Tao Shen. Maximum density divergence for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 43(11) (3(11))3918 1--1888--,,,,99 2020a.
Mengxue Li, Yi-Ming Zhai, You-Wei Luo, Peng-Fei Ge, and Chuan-Xian Ren. Enhanced transport distance for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13936-13944, 2020b.
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. In International conference on machine learning, pp. 97-105, 2015.
Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi. Minimax lower bounds for transfer learning with linear and one-hidden layer neural networks. Advances in Neural Information Processing Systems, 33:1959-1969, 2020.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical Sociery. Series B (Statistical Methodology), 78:947-1012, 2016.
Alexander D Poularikas. Handbook of formulas and tables for signal processing. CRC press, 2018.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning (ICML), volume 139, pp.
2021.
Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Kendrick Shen Sang Michael Xie, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Sara Beery Henrik Marklund, Etienne David, lan Stavness, Wei Guo, Jure Leskovec, Tatsunori Hashimoto Kate Saenko, Sergey Levine, Chelsea Finn, and Percy Liang. Extending the wilds benchmark for unsupervised adaptation. In International Conference on Learning Representations, 2022.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Kendrick Shen, Robbie M Jones, Ananya Kumar, Sang Michael Xie, Jeff 7. HaoChen, Tengyu Ma, and Percy Liang. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. In International Conference on Machine Learning, pp. 19847-19878. PMLR, 2022.
Masashi Sugiyama, Matthias Krauledat, and Klaus-Robert MÅäller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, (M555)985-11055 2007.
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In European conference on computer vision, pp. 443-450. Springer, 2016.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data, 2020. URL htttp:://ppenreeeee net forum? rC8 6kaH

---

Published as a conference paper at ICLR 2023
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael I Jordan. Bridging theory and algorithm for domain adaptation. arXiv preprint arXiv:1904.05801, pp. 7404-7413, 2019.
Huaiyu Zhu, Christopher KI Williams, Richard Rohwer, and Michal Morciniec. Gaussian regression and optimal finite dimensional linear models. 1997.
12


Reviews:
[{"review_id": "ujT9C3oT7Vg", "reviewer": "Reviewer_JEBk", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies extrapolation of models from source to target distribution. Unlike prior work that made restrictive assumptions about the distribution shift, this work considers any shift with shared marginals but arbitrary shifts in the joint. However, as a compromise, they only study a class of functions that are the sum of nonlinear functions on each coordinate (the last theorem relaxes the class of models to some extent though). ", "summary_of_the_review": "The paper makes a good effort toward developing theoretical bounds for extrapolation from a source to a target distribution for a specific class of models. The theoretical results are interesting but their relevance and impact value is left to the reader. The paper can improve by commenting on tightness of its result, discussing broader impact, and with engaging commentary in connection to known empirical results. Without such, it is difficult to assess the significance of its claims.", "strength_and_weaknesses": "Strengths.\n1. Theoretical understanding of distribution shift is much needed, with the closest related work from 2010. Any progress toward better understanding is welcome. \n2. Writing is mostly clear, assumptions are clearly stated and claims are argued well. \n\nWeakness/questions.\n1. I found the writing a bit dry because it does not anchor itself with interesting empirical findings that the theory can explain. They do not also have any section that explains how the theoretical results are of practical consequence. \n2. I expected some empirical validation of their claims with either continuous or discrete inputs. \n3. I find the considered class of functions (which are the sum of functions on each dimension) too restrictive. Does the bound on extrapolation measure $\\tau$ depend on d because of the assumed class of models? How does the upper bound change with a more general class of models? For the continuous case, when does the bound on $\\tau$ lead to a non-trivial bound? The paper can gain from some commentary around the developed theoretical claims, such as how tight the bounds are, what is the worst and best case shift, etc. \n\nMinor comments.\n1. Around eq (8), (9), r is swapped with k.\n2. Section 3.3 talks about f1, f2 without introducing them. \n3. “considered theorem 5” -> “considered in …”\n4. Page 5: sparest cut -> sparsest cut.\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "f0Qj1WMdjjM", "reviewer": "Reviewer_CdV3", "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": "", "summary_of_the_paper": "The paper studies domain shift between distributions whose marginals have good overlap by analyzing the maximum of the ratio between the two distributions of the corresponding squared-distances between any two models. They bound this ratio for a model class that includes models additive over individual features and some additional gaussianity assumptions.", "summary_of_the_review": "See above. I have not read the appendix due to review time constraints. At this point my feeling is that the paper is somewhat below the acceptance threshold. While the results could be of some interest, some more effort appears that is needed to justify the assumptions and draw concrete conclusions that are useful before the theory itself.\n\n\n---------------------------------------------------\n**** Raised score 5-->6. See response to authors ", "strength_and_weaknesses": "This work has some potentially interesting ideas, but overall the studied setting is limited making it questionable how informative or insightful the results really are. \n\nThe lower bound (Prop. 6), although not surprising, is helpful to the story as it motivates the idea of imposing structural assumptions between P and Q. Yet, the specific structural assumption assumed (identical marginals) is rather strong and at least it should be motivated. Besides that, the Gaussianity assumption also appears limiting in that setting. Even more concerning, there is no explicit discussion on how informative the bounds are (eg Thm 4 and 5). The result of Thm 4 is compared to the linear case but the comparison reads loose: (i) In (14) we have d/\\lambda_min compared to 1/\\lambda_min for linear models; why is \"d\" treated as a \"constant\" here? (ii) the bound in the linear case depends both on Q and P. (eg this is also the case in Thm, 3).\n\nminor:\n- Paper would benefit from a careful read as there are several typos here and there\n- r_i not defined end of page 4. Why is wlog to assume i\\in[2]\n- Should it be f^* in (3)?", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cDiA4yUQJQ", "reviewer": "Reviewer_fhp8", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposes domain generalization results for squared error that apply to cases where the support of the target distribution exceeds the support of the source distribution. There data model is nonlinear but the function has to be nearly realizable with a certain hypothesis class. ", "summary_of_the_review": "The approach taken in this paper is vastly different from previous domain adaptation works I've read and I lack the background to carefully evaluate correctness. I did my best to verify the math in the main paper but it's likely that I've missed some errors. The assumption on the data is restrictive but the paper is clear about it. I'm leaning towards acceptance.", "strength_and_weaknesses": "The most important addition to this paper would be a synthetic experiment where the data satisfies the assumption. This would both make it clearer how easy it is to construct such data and how tight the bounds are.\n\nDiscussing the impossibility results in previous work where disjoint support leads to unbounded divergence will also help with the motivation. Do Ben David et al already provide examples of this situation?\n\nMinor comments:\n- In Eq 1 tau is defined as a function of three variable and then, in the text below it, the variables are dropped. This change in notation should be clarified.\n- I believe epsilon in Eq 2 needs a quantifier such as \"there exists epsilon and f* such that...\".\n- What does stylized mean in the abstract?\n- The title of the paper is a bit misleading. Ben David et al's result already applies to nonlinear models. The submission is providing results for certain classes of nonlinear models and data where the previous results would not apply and so is not \"a first step\" for the general case of nonlinear models.\n- [1] also discusses issues with domain adaptation models and its relationship to support overlap. The discussion in [1] as far as I know is different from the submission but perhaps the authors can see some connections. There is no need to include this paper in related work if the authors do not find it relevant.\n\n[1] Stojanov, Petar, et al. \"Domain adaptation with invariant representation learning: What transformations to learn?.\" Advances in Neural Information Processing Systems (2021)", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "Jo9JhwZx7n", "reviewer": "Reviewer_1mvE", "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": "", "summary_of_the_paper": "This paper addresses the problem of understanding how models generalize to new domains from a theoretical perspective. Specifically, they seek to answer the core question: \n\"Under what conditions on the source distribution P , target distribution Q, and function class F do we have that any functions f, g ∈ F that agree on P are also guaranteed to agree on Q?\"\nThis paper extends existing results on this problem to a broad class of nonlinear functions, without requiring the assumption that the support of Q lies within the support of P. They show a number of related results for different types of data (discrete, continuous gaussian-distributed) relying on the assumptions that a) the support of the *marginals* of Q lie within the support of the marginals of P, and b) the covariance-matrix is non-degenerate, then the function class $F={\\sum_i f_i(x_i)}$ along with P and Q satisfy the above property.", "summary_of_the_review": "This paper tackles a very interesting theoretical question and attempts to provide answers in a setting that is a) of direct practical interest and b) has not yet been satisfactorily resolved in the literature. It is well-written and high-quality, but the specific assumptions made about the form of the data may be overly restrictive and limit its usefulness. For now I would consider this paper borderline, but I hope that the authors or other reviewers might be able to provide more context on how limiting those assumptions really are. From an empirical perspective they seem quite severe, but from the perspective of learning theory it may still be a significant result, and as such I may update my score pending further discussion.", "strength_and_weaknesses": "The paper addresses a central and important question in the theory of generalization, and extends new results to a broad class of nonlinear functions without making assumptions about the support that fail in the context of domain generalization. Their arguments are rigorous and well-presented, and make a convincing case for why this result is powerful and novel. Their argument convincingly shows how the ability to extrapolate to new domains (for the class of functions they consider) is tied to the conditions of non-degenerate covariance and overlapping marginal support.\n\nMy primary hesitation with the paper is in the assumptions made about the data. My understanding is that the results shown in this paper hold for three settings: 1) when x takes on discrete values, 2) when $x=(x_1,...,x_d)$ such that each pair $(x_i, x_j)$ is pairwise gaussian distributed, and 3) when x can be divided into two subsets $x_1,x_2$ and $(x_1,x_2)$ is gaussian distributed. \n\nFirst, the results in the discrete setting are proved only for the 2-dimensional setting as far as I can tell. In the paper, it is stated that \"Theorem 2 can be easily extend to the case when k > 2. We choose to present the current version because of simplicity, and because the kernel matrix KP coincides with the Laplacian of a bipartite graph when k = 2, which provides further insights and better intuitions.\" I think the extension to higher dimensional x should at least be shown in the appendices.\n\nSecond, the assumptions on the data in real-valued settings seem quite restrictive. I am not an expert on learning theory, so it is possible these assumptions are more standard than I assume, but the first set of assumptions (e.g. each pair of features is pairwise gaussian distributed) seems unlikely to be true in general cases, and the note in the latter case (where features are partitioned into subsets) that \"we want to handle the general version where the inputs are divided into multiple subsets, but due to technical reasons we can only use our proof techniques to two subsets\" also seems like a significant constraint. Perhaps the authors could give some motivation for whether there is a reason to expect either of these assumptions about the form of the data to hold in cases that are of particular practical or theoretical interest.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster