Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied the problem of measuring the data heterogeneity, i.e., the distributional diversity inside the data. It provided a novel data heterogeneity notion named predictive heterogeneity to explore how it affects the prediction of machine learning models. The crucial idea was to define the environment-conditional predictive V-information, which enabled the empirical estimation from finite samples. Its efficacy was then verified in various prediction tasks.
strength_and_weaknesses: Strengths
(1) It introduces a predictive heterogeneity to define the data heterogeneity quantitatively.
(2) It theoretically analyzes how predictive heterogeneity works in homogenous and heterogeneous settings, and studies its empirical estimate with PAC bounds.
(3) The experiments demonstrate the effectiveness of the proposed Information Maximization algorithm in various prediction tasks.

Weaknesses
(1) One major concern is the tightness of the predictive heterogeneity in Theorem 2. The first term Var[r]/E[r^2] involves both the variance of r and the expectation of r^2. It is unclear how the E[r^2] affects the approximation tightness.
(2) In the introduction, it mentioned the data heterogeneity in the graph data. Could the proposed predictive heterogeneity be applied to learn the data heterogeneity of graph data? If so, how is the node interdependence reflected in the predictive heterogeneity?
(3) It mentioned that "Large H(P) indicates that the correlation between X and Y is enhanced by E" in Section 3.1. What is H(P) here? Why does it indicate the correlation between X and Y?
(4) How is the regularize U_V(W, Y_N) defined in the objective function of IM?
(5) Theorem 4 shows the connection between the optimization of Eq. (15) and the empirical predictive heterogeneity. Would this result consider the approximation of Eq. (20-21)?
(6) Appendix B showed that the proposed method is not sensitive to the choices of K. But K might be much smaller than the real number of sub-populations. In this case, the model performance might be improved by increasing the value of K.
(7) In Table 1, it is unclear why EIL (Creager et al., 2021) fails to predict the simulated data.

###########
Update: The authors have addressed most of my concerns, and thus I would like to improve the score accordingly.
clarity,_quality,_novelty_and_reproducibility: This paper clearly presents the crucial idea of measuring data heterogeneity using predictive heterogeneity. However, some technical details are not well explained.
summary_of_the_review: The overall idea of this paper is interesting. It theoretically and empirically shows the quality of predictive heterogeneity in measuring data heterogeneity. I would like to improve my score if my concerns can be solved well.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work defines predictive heterogeneity to quantify the heterogeneity in the data which influences the predictive performance. It proposes an algorithm which quantifies the mentioned heterogeneity and use that in examples to show how it can be helpful in understanding the subtleties of the data.
strength_and_weaknesses: The paper seems interesting and timely. Its implications are general and the experiments show its usefulness in providing insights as well as OOD generalization.
clarity,_quality,_novelty_and_reproducibility: I find the paper fast-paced. The authors seem to be trying to compactly include information which may get overwhelming to a person not familiar with the literature. Moreover, the paper concerns itself with definitions and intricacies from the get-go which is expected from a mathematically rigorous paper but on the other hand fails to provide the overarching flow. In other words, it loses the forest for the trees. 
summary_of_the_review: This work is significant and it has very good applicability.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors analyzed the problem of identifying differing prediction mechanisms amongst different sub-populations that are likely to differ. They provided theoretical outlining of the mechanism and proposed a novel algorithm to explore the differences. The provided empirical analysis of the explore differences and provided discussions around the usefulness of extracted insights
strength_and_weaknesses: There are several strong aspects of the paper as follows

- The authors proposed a formal definition of predictive heterogeneity by starting from the first principles of probablity and using concepts from information theory. This allows the authors to immediately connect certain strong theoretical results for the proposed definition
- The theoretical analysis around linear cases is interesting. While not being the most real-world scenario, this analysis allows readers to gain an intuitive association with the properties of the methods and deliberate on its applicability
- The empirical exploration around the yield datasets is motivating. Similarly the other empirical evaluations lends substance to the otherwise theoretical paper

The paper could still be improved upon certain manner
- The presentation of the paper could be improved upon. While the background around information theory is useful, more intuitions around the theoretical propositions could improve the readability of the paper
- While acknowledging that the paper is theoretical, the empirical results do not sufficiently motivate the "correctness" of the method. The OOD experiments are interesting, however, It may be useful to devise some sort of quantitative/qualitative measure of extracted sub-groups from the 3 example tasks. There is a huge body of literature around sub-group discovery that can provide pointers for this (e.g using a synthetic dataset)
- The applicability of the algorithm is also not well discussed. There are many sub-group discovery methods. Are there situations where other methods are more applicable? Can you provide more details on the computational complexity 
clarity,_quality,_novelty_and_reproducibility: The proposed method is novel and at the same time well motivated from existing literature. The presentation by itself is ok but could be improved upon. For improved reproducibility, distributing their code in open source may be beneficial 
summary_of_the_review: Overall the paper is well motivated, has strong theoretical under-pinnings, and backed by some level of empirical evidence. While the empirical part of the paper may be improved upon, the proposed method could be an interesting contribution, especially when considering the problems of algorithmic bias and model selection. 
Apart from the aforementioned aspects, below are a few other aspects that the authors may consider

- Provide a glossary of symbols used for the theoretical descriptions. Define symbols before using them (e.g. Section 2, Notations the probability triplet is not described)
- Provide more details around the complexity of the proposed optimization. As the authors have noted, MI is notoriously intractable - providing more details on the final complexity would be useful for consideration of the algorithm to a wide range of problems
- Considering expanding the discussions around the benefits to quantifying/debiasing w.r.t algorithmic fairness of models

Edit: The authors have addressed a number of concerns regarding validity in their response
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies criteria and methods for finding data heterogeneities that affect building predictive models. The authors define a predictive homogeneity criterion and present an algorithm to find predictive heterogeneity in data. The authors further show predictive heterogeneity criterion can provide insights for subpopulation in agriculture, sociology and object recognition applications and its benefits for OOD generalisation.
strength_and_weaknesses: S1: The paper is well written and easy to follow.

S2: The theoretical analysis is substantial and looks sound. 

S3: The experimental case studies are from different areas.


W1: The predictive heterogeneity criterion is interesting, but is incremental to the previous work (Xu et al.). In Definition 5, $\Epsilon$ is unknown, and the authors' solutions for finding $\Epsilon$  are in linear settings with independent noise. These assumptions will restrict the empirical impact of the work.  Also, since $\Epsilon$ is unknown, setting a $k$ is challenging and the authors have not discussed how to set a $k$. 

W2: The empirical impact of the proposed method has not been shown to be significant. In three experimental demonstrations in subpopulation division, the number of k is 2 (the minimum possible number in heterogeneity discovery). Finding data heterogeneity is not a new topic and many works have been done. For example, in cancer subtype discovery in bioinformatics, many sophisticated methods have been proposed to deal with complex data types for many subgroups. The paper lacks discussions and comparisons with this type of work.

====

The authors' detailed explanations and follow-up experiments clarify my doubts. 
clarity,_quality,_novelty_and_reproducibility: Clarity: Good. The paper is well organised, and easy to follow.
Quality: I have not spotted a flaw.
Novelty: moderate. The empirical impact is low.
Reproducibility: Most details are provided for reproducibility.

summary_of_the_review: It is a technically sound paper with a modest empirical impact paper. I am not excited by the idea or the experimental results.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper defines a new notion of data heterogeneity and shows how it can be estimated from finite data. The authors provide theoretical analysis and empirical results showing the usefulness of their proposed notion.  

All reviewers believe the paper should be accepted. The topic is interesting and the technique could be useful in many applications. The authors have resolved a number of reviewers' concerns during the discussion phase. 
justification_for_why_not_higher_score: It is unclear how significant of an impact the work would have in practice. The reviewers believe the work is solid, but not groundbreaking. 
justification_for_why_not_lower_score: All reviewers believe the paper should be accepted. The topic is interesting and the technique could be useful in many applications. Most reviewer concerns have been addressed in the authors' response.
Decision: Accept: poster