Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the performance of one-pass SGD when pre-trained on a large linear regression source task and fine-tuned on a smaller linear regression target task with a mild degree of covariate shift. In this setting, O(N^2) data points from the source data are as effective as O(N) data points from the target task. The study is mostly theoretical based on a bias-variance decomposition where the bias term is due to limited iterations of the single-pass algorithm and the variance term is due to noise. An experiment verifies the results on a synthetic problem.
strengths_and_weaknesses: The paper is well written and well organized. The proofs are in the appendix which was not checked but the arguments in the main paper are intuitive and convincing. The choice of algorithm and the domain shift make the findings less surprising as I will elaborate below, but the theoretical characterization in the paper may pave to way for more interesting results. Altogether I am voting for acceptance but I strongly recommend highlighting the following limitations in the introduction.

1. All the results are on a quite benign form of covariate shift where the model reaches the same solution on both the source and the target task. Even if no data point is available from the target task, the model can reach zero error by training on the first task. This is where the power of pretraining largely comes from. The question is then how much training on the source task can slow down the optimization or hurt generalization compared to training on the target task.

2. The studied algorithm is one-pass SGD. Optimization and generalization of this algorithm are connected together in a way that the insights from this paper may not extend to the more commonly used multi-pass SGD. The number of data points in one-pass SGD determines the number of iterations and how far the parameters can move towards the optimal solution. The limitation of pretraining appears to largely come from the fact that reducing the loss on the target task requires more iterations if training is on the source task instead of the target task. In single-pass SGD, since the number of iterations is equal to the number of data points, more iterations means more data points. Multi-pass SGD with limited data points can make up for this slow convergence with more epochs even if the number of data points is limited. I am not sure then if these findings on one-pass SGD about the number of required data points extend to multi-pass SGD. I suggest clarifying in the intro and abstract that this is a study of the performance of one-pass SGD under covariate shift and using applications of one-pass SGD in ML to highlight the significance.

Minor comments:

(i) Line 241 states that a bounded signal-to-noise ratio is of statistical interest. Is the ratio bounded from above here? And could you provide citations for the claim about statistical interest?

Typos:
- Line 262: regarding
- Line 273: Supervised
-----------------------------
Update: The revision addressed my second comment and so I increased the score to 7. As for the first comment, although this assumption limits the applicability of the current result, I think analyzing the behavior of single-pass SGD under this assumption is still valuable.

Note on clarity: Covariate shift has a rather standard definition in machine learning: The two tasks have the same conditional distribution p(y|x) but different marginal distribution p(x). See "key assumption 1" in [1] for example. As the reviewer df3S explained, if there is a chance of model misspecification, the assumption that the two tasks share the same optimal parameters does not follow from this definition. (An elaborate discussion is provided in [2].) Currently, the submission is including the assumption of shared optimal parameters in the definition of covariate shift. Even if some previous papers have defined covariate shift in this way, doing this would confuse a majority of readers who expect the standard definition of covariate shift. I strongly recommend separating this assumption from the definition of covariate shift and editing the corresponding statements in the paper to help with readability. One example is the sentence "For covariate shift problem, pretraining with infinite many source data can learn the true model" in line 230 in the revision.

[1] Huang, Jiayuan, et al. "Correcting sample selection bias by unlabeled data." NeurIPS, 2006

[2] Shimodaira, Hidetoshi. "Improving predictive inference under covariate shift by weighting the log-likelihood function." Journal of statistical planning and inference, 2000
questions: See weaknesses section
limitations: See weaknesses section
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents a theoretical study of the generalization performance of the pretraining-finetuning method with linear regression setting under covariate shift. Especially, this paper derives the upper and lower bounds for the generalization achieved by the pretraining-finetuning method. With the bounds, this paper characterizes the power of the pretraining, the pretraining-finetuning method, and the limitation of the pretraining compared to supervised learning.
strengths_and_weaknesses: This paper is interesting and well-written. I think that this is a good paper that should be accepted. One minor concern is how standard Assumption1 is. If the assumption is standard or applies to any common distributions under covariate shift, it would be better to state it with some examples. 

It would be better to summarize the bounds by showing a detailed comparison between only pretraining, pretraining-finetuning, and finetuning.
questions: In line 263, "middle" eigenvalues subspace of H falls into the top eigenvalues subspace of G. Can you explain in more detail?
limitations: The paper seems fine to me in this regard.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper investigates a transfer learning approach with pretraining on the source data and finetuning based on the target data and establishes sharp instance-dependent excess risk upper and lower bounds for this approach. 
strengths_and_weaknesses: ### Originality

The paper's idea is very novel. To the best of my knowledge, the theoretical analysis of the transfer learning paradigm remains unclear.

### Quality

The technical part of the paper seems correct as far as I can see.

### Clarity 

The paper is well-written. 

### Significance

The question studied in the paper is significant. Understanding the power and limitation of pretraining-finetuning for linear regression under covariate shift is meaningful. 

questions: The regression problem is very old. What is the factual applications of the theoretical analysis?
limitations: The limitations of the presented analysis could be discussed in more detail.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper investiage the covariate shift problem in a linear regression task. They assume there exits a w* that can simutanously achieves the optimal in both training and testing (target) domain.  They show a model trained on the training domain (with O(N^2) samples) can match the one trained on the target domain (with N samples). Also, they also show the benefits of finetuning on the target domain with limited data. From the technical side, they provide a sharpened upper bound (by a logarithmic factor)  and matched lower bound . 
strengths_and_weaknesses: Strength:
    1) the paper is well motivated and clearly written.
    2) I didn't check the proof, but the results seem correct to me.
    3) the bounds are sharp and complete.

Major Weakness:
    1) From my perspective, it is strong to assume a w* that is optimal for both domains (or the optimal set of the two domains overlap). This assumption is crucial for the main results such that a model trained with sufficient data in the training domain matches the performance of the one trained on target domain. Given the vast empirical results on the domain adaptation and generalization, there is no evidence that such w* exists or minimizing the training domain loss can lead to testing domain performance gain. I suggest the authors  the provide more supports for the this assumption.  I will change my rate after the rebuttal phase depending on the authors response to this concern. 
     
Minor Weakness:
    1) the notation is dense and the main thereom 3.1 is hard to follow, I suggest the authors to reformulate the results for better readability. 
    2) I think (if I am not wrong) the techniques used in this paper is not novel. It is an application of existing methods on the M+N setting.

### Post Rebuttal Comment

After the discussion with the authors, I thinks this paper makes an unreasonable assumption on the training and testing domains share the same optimal $w^*$ in a linear case.  **Though the conditional distribution can be the same in training and testing domain,  the optimal $w$ can still be different due to model misspecification (which is commonly the case in linear models).** In other words, if there is model misspecification, the optimal $w^*$ for the source domain is not optimal for the target domain. By assuming model misspecification, we mean the residual of $y-x^\top w^*$ is not independent of $x$. So let assume $\mathbb{E}_{\mathbb{P}(y|x)}(y-x^\top w^*)=g(x)$, where $g(x)$ is the non-linear part that can't be explained by a linear model. 

Denote the source domain with $s$ and target domain with $t$. Because $w^*$ is optimal for the source domain, then we have $\mathbb{E}_s [x (y-x^\top w^*)]=\mathbb{E}_s [x g(x)] = 0$. However, because $P_s(x) \neq P_t(x)$ and further $\mathbb{E}_t [x g(x)] \neq \mathbb{E}_s [x g(x)] $, we have $\mathbb{E}_t [x (y-x^\top w^*) ] = \mathbb{E}_t [x g(x)] \neq 0$.

In conclusion, the $w^*$ optimal for source domain is **NOT** optimal for the target domain due to model misspecification and the shift of $P(X)$.

If one assumes $w^*$ is simutanously optimal for both domains, then we must assume $E_s [x g(x)] = E_t [x g(x)]$ even when $P_s(X) \neq P_t(X)$, which is a prohibitively strong assumption that I have not seen in the existing literature. I think it only holds in rare cases. 

Due to this concern that the results of the paper only hold in well specified linear cases, I heavily doubt whether the implication is true for the real applications. I changed score from 6 to 4. I highly suggest the authors to consider different optimal $w^*$ for training and testing domains.

### Post Rebuttal Comment 2

I have read the literature [1]. And it indeed assume the same optimal $w^*$ for both training and testing domains. Though I don't like this assumption and it has problems with model misspecification under distributional shift, my claim "a prohibitively strong assumption that I have not seen in the existing literature" is inaccurate. I raise the score from 4 to 5. 

[1] Near-Optimal Linear Regression under Distribution Shift
questions: See Weakness.
limitations: See Weakness.
review_title: null

Meta-review: metareview: After the rebuttal, the majority of the reviewers were convinced that the paper is novel and interesting and it should be accepted. In preparing the camera-ready, I suggest to the authors to take into account the reviewers' comments to better explain the used assumptions to the readers and avoid potential misunderstandings.
confidence: Less certain
Decision: Accept