Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: ### Summary of the contribution
The paper addresses the issue of combining datasets from different sources, and taking into account the fact that they do not share the same precision. 
It aims at predicting the performance of an algorithm trained on those data, through a simple formula taking into account the size of the data, and its composition through the mixture weights of the distribution from which it comes.
As the formula also depends on the estimator trained and the quality of data, it is trained to be estimated fully.

### Strengths
The paper and the topic are both interesting. The maths look correct, although I have not checked it all.

### Weaknesses and concerns
The paper lacks clarity in general.
1. Context
The context of mixed-source data is not very clear: 
	- from Section 2, it appears to be applicable e.g. for datasets coming from different sensors, but predicting the same output, while the experiment section makes use of very different datasets, not even predicting the same target; 
I encouraged the authors to provide specific examples in Introduction or Section 2 for clarity. The experiments seem to be related to multitask learning, as mentioned shortly for one application but looks to be true also for others;
it could also possibly be related to domain adaptation. In both cases, the experiments should include comparison to state-of-the-art approaches in those learning problems.
	- It is also not clear how the different sources are mixed together: does the proportion $q$ apply to the number of observations in each source? 
	- Moreover, there is mention in the Introduction of the goal of optimal data collection policy. 
How can the proposed work be used in practice for that goal, since we do not know in advance what is the quality of each dataset, or how well does an estimator perform?
2. Main goal of the work 
The title and most of the work is a bit misleading, as it mentions predicting the performances of an estimator, while in fact it predicts its excess loss, that is, how close an estimator is from the best possible estimator (oracle) in the model; 
while this is a good approach to improve the fitting of an estimator (and its parameters) inside a family, it does not give any clue as its actual performance. 
It is also not clear what the learning problem at the beginning of Section 3 does, and how it is used in practice.
3. Related work
Appart from the learning problems mentioned before, here are possible issues with related work
	- Active learning does not qualify as related work, as it is usually concerned with the labelization of unlabeled samples in a single source dataset when labelling is expensive. 
If there exist work on that domain that is specific to the problem of combining data from different sources, please provide a more specific reference.
	- There exist however other works for the issue of performance evaluation through a learning problem, e.g. "Per Instance Algorithm Configuration of CMA-ES with Limited Budget" by Belkhir et al (2017);
 it should be interesting to compare to the proposed work.
4. Experiments
The experiments show the following issues:
	- As the proposed formula estimates the excess loss and not the performance itself, there should also be a comparison of the actual performances obtained both in the full training set and on the test set.
	- Amazon sentiment: 
		- regression is applied on the sentiment prediction, which is a classification task
		- the estimator considered is ridge regression, which does not fit Proposition 3.1 setting and no comments are made as to how the penalty would impact (or not) the theoretical properties of the work
		- $C(q)$ contains 4 terms, while it said that there are 3 data sources in training

### Minor comments:
Proposition 3.2 is not written in the same format as the others, and makes it hard to see the link with n (or log n). Please re-write it or explain where the n component is.

### Overall evaluation: 
The paper is interesting and tackles an important problem. However, it lacks clarity in many aspects.

=====POST-REBUTTAL COMMENTS======== 

I thank the authors for answering my questions. Their answers did clarify some aspects, such as the ratio of mixed sources, the optimal data collection, and the relation of the proposed work to active learning and multitask. However, the answer provided on my comment about the distinction between excess loss and absolute loss is not sufficient. I believe this is an important point, and calls for a major revision, not just a promise to clarify the point throughout the paper. The same comment applies to the experiment when comparing methods on the basis of computing the excess loss and not showing the absolute loss, which is the actual measure of quality of an estimator.
review_title: Interesting paper, but lacks clarity

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper, the authors proposed a model to predict the model performance given the sample size n and the composition of the source of the data, q. They argued that the excess test loss should be separable in n and q.  The paper is interesting and well presented. I have no difficulty following the authors arguments. The proposal could be useful for some practitioners. 

However, I am not convinced that log(L(n, q)) should be separable in n and q in general. The authors did show in some special cases in Figure 1 and Sections 3.1~3.3 that n and q are separable, but a more general theory is lacking. The baselines in the experiments are all relatively weak. In fact, comparing the results between Datasize and Rational, it seems plausible to me that Rational achieves good performance simply due to the added flexibility in the q term, rather than modeling the n and q relationship correctly. A more suitable baseline would be to use a DNN model on [n, q], without separating n and q, and if Rational achieves on par performance with DNN on Train, that suggests to me that the functional form of Rational is probably correct.

On page 2, the authors wrote "The performance of this classifier is evaluated on a test distribution which may differ from the
training distribution by a covariate shift (i.e., p(y|x) = p_test(y|x))." Is there a typo here? Do the authors want to write "p(y|x) = p_test(y|x) but P(x) \neq p_test(x)"?

On page 3, what is the expectation taken over in L(n, q)?

On page 3, I can only see 3 colors in Figure 1 (a), yet there are 5 lines in the legend.

On page 4, in the formulation of C(q), lambda appears in the denominator. How to initialize lambda such that sum(lambda q) is not too small, leading to exploding C(q)? Is there any constraint on alpha to guarantee the sublinear relationship established in Hestness et al. (2017)? Is there any constraint on lambda's? How many lambda's should we use? It seems that based on the propositions, there should optimally be dk lambdas. This seems like a large number.

On page 7, in Table 1, do we extrapolate only with respect to n? If so, it would be great to also present a study with extrapolation on q.
review_title: Good paper, but I am not convinced that L(n, q) is separable in n and q.

final_score: rating: 7: Good paper, accept
review_content: This paper casts generalization under covariate shift as a prediction problem. Concretely, given a model trained on $n$ samples from a mixture of $K$ distributions, can we predict the excess risk of the model on data drawn from a different mixture? 
Motivated by recent empirical work, the paper posits a simple functional form for the model: log-linear dependence on dataset size and an additive offset given by a \emph{rational} function of the mixture coefficients. The author's demonstrate theoretically that this form arises naturally for linear regression, M-estimation, and a non-parametric binning estimator. Empirically, they show fitting this model to data gives better predictive performance than methods based on dataset size or using linear functional forms.

Pros:
- This paper addresses a question of great interest to much of the ML community: generalization under distribution shift.
- The approach taken here, i.e. using theory to posit "scaling laws" or models whose parameters are fit to then fit to empirical data is an interesting alternative to reasoning about performance under distribution shift from first principles alone.
- The quantitative predictions from the models presented here may be of interest to people using active learning to gather new data to improve model performance. 
- The paper and proofs read well and don't appear to have correctness issues. (I did not carefully verify Proposition 3.2 due to time). 
- In the experiments presented, the rational function model gives fairly accurate predictions, and certainly better predictions than methods based on dataset size alone.

Cons:
- My main complaints with this paper is the lack of limited baselines and the limited scope of the experimental results.
- Baselines: The dataset size and linear baselines are good starting points, but the the experiments not include any non-linear baselines. This makes it difficult to determine whether the rational function model is really fundamental or necessary. Would, e.g., a generic function approximator perform just as well?
- Experimental scope: Scaling laws like the ones presented in this paper are useful and interesting in so far as they capture some "universal" phenomenon. 
-- In each of the settings considered, the experiments focus on one model, e.g. pretrained BERT for question answering. How general is this method beyond the models considered? Does the rational model give predictive power on each task across a diverse set of models, or is there something particular about the ones presented?
-- All of the experiments take place with text data. Does a similar result hold, e.g., for CNNs trained with natural images?

Overall, I very much enjoyed reading this paper, and it offers several avenues for further inquiry. I vote to accept.

==============

Update after rebuttal:
Thanks to the authors for their response. I enjoyed this paper, and I'm keeping my score unchanged. In terms of multiple datasets/diverse models, I appreciate the various models/dataset/baselines currently included as a proof of concept. However, I'd be very interested in a more systematic study with significantly more models and datasets to understand better precisely when excess error as function of data composition and size can be reliably extrapolated and the extent to which the trends observed are "universal."
review_title: Interesting and important question; experimental weaknesses

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work studies the problem of predicting model performance with more training data when the data are collected from different sources. The predictor is a function of the number training examples, and the ratio of examples from each source. The predictor needs to be built from a small number of training examples the observed model performance, and applied to larger numbers of training example without actually training the model. The predictor can be used to decide a good data collection policy which is expected to have best model performance. The proposed solution is a simple parametric form of the predictor, which is log-linear in the log of # training examples, and log-rational in the source distribution vector. The solution is motivated by recent literature about the same task for single source. The correctness of the solution is proved for several cases: linear regression, M-estimator and nonparametric binning. The performance of the predictor is then evaluated for a number of real-world tasks: linear regression for Amazon book rating, semantic parsing, machine translation and multitask question answering. The performance is measured by r2 score between the actual performance and predicted performance. The proposed predictor has a clear advantage over the baseline of using a linear predictor.

Pros:

1. The work is built on top of recent studies with single source and the extension to multi source is timely. 
2. The discovered relation between the expected model performance and the number of training examples from multiple sources is neat and interesting. 
3. The proposed rational function of the distribution vector is justified for a few cases theoretically.
4. The empirical evaluation uses diverse real tasks, covering different loss functions, including the ones where the assumptions in the theoretical analysis are not satisfied. And the proposed solution has a reasonably robust performance and is much better than the baseline. The behavior of the predictor across the tasks meets expectation.

Cons:
1. " Following earlier observations by Hestness et al. (2017), we expect a log-linear relationship
between L(n, q) and log(n) for any fixed q," It will be good to specify the condition of the loss function required by the reference.
2. The experiment applies prediction to 2-6$\times$ of the training examples used for fitting the predictor at max. It will be useful to study the case when this gap is larger, to understand the power or limitation of the proposed predictor. 
3. The distribution vector is randomly sampled in both training and testing. It will be useful to test the case where the distribution vector is sampled differently, to further evaluate the extrapolation ability.
4. Combining 2 and 3, it will be very useful to test the limit of the proposed approach and know the minimal required observations for the predictor to work well.
5. Page 8: typo BLUE. 

===================
Update after discussion: The difference between excess loss and absolute loss is an issue I overlooked. After discussing with other reviewers, I realized a new question: how to compute the excess loss L(n, q) without knowing the the best possible estimator (oracle) in the class? This is a key step in the proposed algorithm when fitting the predictor. The paper has not explained it. As of now I do not think that is possible, except if strong assumptions are made, such as the oracle has 0 loss. In the experiments, if the authors use the estimator trained with full data as the oracle to compute the excess loss, that would invalidate the practical usability of the approach because the goal was to predict the performance without having full data to begin with.
review_title: A neat result in theory; Practical use is in question due to the unclarity of how to compute excess loss without knowing the oracle

Meta-review: This paper studies the following broad question: How can we predict model performance when the data comes from different sources? The reviewers agreed that the direction studied is very interesting. While the results presented in this work are promising, several reviewers pointed out some weaknesses in the paper, including a confusion between absolute loss and excess loss, and the limited scope of the experiments. Overall, this paper does not appear to be ready for publication in its current form. In my personal opinion, if the concerns raised by the reviewers are appropriately addressed, this work could be publishable in a high quality venue.
Decision: Reject