Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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.

Discussing 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?

Minor comments:
- 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.
- I believe epsilon in Eq 2 needs a quantifier such as "there exists epsilon and f* such that...".
- What does stylized mean in the abstract?
- 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.
- [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.

[1] Stojanov, Petar, et al. "Domain adaptation with invariant representation learning: What transformations to learn?." Advances in Neural Information Processing Systems (2021)
clarity,_quality,_novelty_and_reproducibility: See previous section
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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. 

The 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).

minor:
- Paper would benefit from a careful read as there are several typos here and there
- r_i not defined end of page 4. Why is wlog to assume i\in[2]
- Should it be f^* in (3)?
clarity,_quality,_novelty_and_reproducibility: The results per se appear original to the best of my knowledge (proofs use rather standard ideas but nevertheless appear to be non-trivial). In terms of clarity, the paper would potentially benefit from better structuring. Despite some attempts of the authors to provide interpretations of the results more effort in this directions seems to be needed to make the contribution less "dry".
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.


---------------------------------------------------
**** Raised score 5-->6. See response to authors
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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). 
strength_and_weaknesses: Strengths.
1. Theoretical understanding of distribution shift is much needed, with the closest related work from 2010. Any progress toward better understanding is welcome. 
2. Writing is mostly clear, assumptions are clearly stated and claims are argued well. 

Weakness/questions.
1. 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. 
2. I expected some empirical validation of their claims with either continuous or discrete inputs. 
3. 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. 

Minor comments.
1. Around eq (8), (9), r is swapped with k.
2. Section 3.3 talks about f1, f2 without introducing them. 
3. “considered theorem 5” -> “considered in …”
4. Page 5: sparest cut -> sparsest cut.

clarity,_quality,_novelty_and_reproducibility: The paper rates highly on each of clarity, quality and novelty. I only found minor typos in the writing. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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: 
"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?"
This 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.
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.

My 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. 

First, 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.

Second, 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.
clarity,_quality,_novelty_and_reproducibility: The work is largely clear, well-written, and easy to follow. The results build off existing work but generalize it to a new and novel setting that is very relevant to the field. 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper poses an interesting problem to study: How do non-linear models extrapolate to new distributions. The author provide a precise definition for extrapolation to new distributions: Given a function class, they measure the ratio between the expected disagreement between any two functions in the class computed over the target distribution vs the expected disagreement computed over the source distribution. And the supremum over all the pairs of functions is used as a measure of extrapolation. 

I have read the paper carefully myself, and discussed this with the reviewers. Overall, the problem formulation of the paper is very interesting, however the reviewers were not entirely convinced about some of the assumption (e.g. the additive function model analyzed or the Gaussianity) as well as whether/not there is a concrete message from the upper bounds (Thms 2-5) that non-linear models extrapolate better. I a revised version of the paper, the authors should clarify how useful these bounds are (it may be the case that they are too loose to be useful). Moreover, there is no comparison to lower bounds so tightness was also not clear to the reviewers.

Overall, the reviewers (and myself) see some good ideas in the work, but we recommend that the authors continue working on the results to achieve more concrete messages. These points were all mentioned in the reviews, and the authors took an extensive effort to respond (and agreed with the points). The paper is really on the border. As the AC, I would like to accept this paper because the paper provides new ideas and a problem formulation and the results should be discussed at the conference. 


justification_for_why_not_higher_score: The paper is a borderline paper.
justification_for_why_not_lower_score: See above
Decision: Accept: poster