Benign Overfitting in Out-of-Distribution Generalization of Linear Models

Thank the reviewer for your positive response and valuable suggestions. The following is our response to your comments and suggestions.

Q1: The result for PCR is more like “Shoot The Arrow, Then Draw The Target.”

A1: We want to clarify that, considering the scenario where “the true signal primarily lies in the major directions” is necessary, and PCR appears to be a natural algorithm under this scenario. As we discussed at the beginning of Sec 4.2, the signal in the minor directions is nearly lost since the eigenvalues of $\\Sigma_S$ in those directions are so small. In other words, learning the true signal from the minor directions is essentially impossible. Therefore assuming the true signal primarily lies in the major directions is necessary (actually in prior work of benign overfitting [Tsigler & Bartlett 2023], this is also implicitly assumed, as you can see there is a term regarding $\\beta^{\\star}\_{-k}$ in the upper bound). As long as the true signal primarily lies in the major directions, it is natural to consider PCR. We want to further clarify that we assume \\beta^\\star_{-k}=0 in Theorem 5 just for presentation clarity. We mentioned in Remark 5 that Lemma 31 provides the generic results without assuming $\\beta^{\\star}_{-k}=0$. One can see that in this case there will be a term in the upper bound regarding $\beta^{\*}\_{-k}$ as in ridge regression.

Q2: Can authors elaborate more on the main obstacle for the lower bound in general case?

A2: The proof techniques in prior work [Tsigler & Bartlett 2023] for the lower bound for in-distribution case crucially rely on the fact that they can express the variance term as a function of many independent subGaussian vectors, while this relies on the source and target covariance share the same eigenvectors (i.e., they are simultaneously diagonalizable). Here we do not assume such a strong assumption, therefore establishing a matching lower bound is much more difficult.

Q3: The fast rate in PCR is not adaptive.

A3: PCR is not adaptive due to its nature of applying principal component analysis. We need to choose a $k$ prior to applying PCR. There are some heuristics when choosing $k$: from our upper bound, we can see that we need to choose a $k$ such that $\lambda_k-\lambda_{k+1}$ is large. And we also want $\lambda_k$ not to be too small, since we want $tr(\mathcal{T})$ to be small. Such a $k$ can be obtained by drawing a “scree plot” which plots the eigenvalues of the sample covariance matrix in a descending order, and picking the “elbow” points. Also we want to clarify that, there is not a “correct” $k$. Our bound applies to any $k$. How to find a good $k$ (for example, using the “scree plot”) for the algorithm is another interesting direction.

Q4: I would like to know if there is any special case that ridge regression can attain fast rate in large shifts.

A4: For large shifts in minor directions, where the overall magnitude of $\Sigma_{T, -k}$ is large, we believe that in general ridge regression can not attain a fast rate. Intuitively when $\Sigma_{S, -k}$ has small eigenvalues, ridge regression will induce large variances on these directions, and this will cause a large excess risk when the overall magnitude of $\Sigma_{T, -k}$ is large.

Thank the reviewer for your positive feedback and valuable comments and suggestions. The following is our response to your comments.

Q1: Numerical experiments.

A1: We thank the reviewer for suggesting the consolidation of theory with simulations. We have included two simulation experiments in Appendix A. The first experiment takes the benign overfitting setup proposed in the paper, involving small shifts in the minor directions. It confirms the $\mathcal O(1/n)$ rate for ridge regression. Data is generated from a multivariate normal distribution, with target covariance matrices randomly generated. We validate the influence of two factors $\\|\\mathcal T\\|$, $\\mathrm{tr}[U]/\\mathrm{tr}[V]$, identified in the paper as measures of covariate shifts in major and minor directions, respectively. The experiment results show that, for each combination of $\\|\\mathcal T\\|$ and $\\mathrm{tr}[U]/\\mathrm{tr}[V]$, the excess risk of ridge regression decays at nearly 1/n. For a fixed sample size, the excess risk increases with larger values of $\\|\\mathcal T\\|$ or $\\mathrm{tr}[U]/\\mathrm{tr}[V]$.

The second experiment compares ridge regression with Principal Component Regression (PCR) under large shifts in the minor directions. The setup follows the instance in Theorem 4, where the excess risk of ridge regression is lower bounded by $\mathcal O(1/ \sqrt n)$, while PCR achieves an excess risk of $\mathcal O(1/n)$. This result is confirmed by the experiment, where the excess risk of PCR is compared against ridge regression with various regularization strengths: $\lambda = 0, n^{0.5}, n^{0.75}, n$. The findings show that the excess risk of ridge decays optimally at the rate of $n^{-0.48}$ for $\lambda = n^{0.75}$, consistent with the $\mathcal O(1/ \sqrt n)$ lower bound in Theorem 4. The optimal regularization in the experiment also aligns with that derived in the theoretical proof. In contrast, PCR achieves a superior decay rate of $n^{-0.99}$.

Q2: While it is very clear the discussion about previous results and how the current result generalise the old ones I feel that the assumptions for the original contributions are hidden in the appendix.

A2: We want to emphasize that we have included all assumptions in the main text and do not hide our assumptions in the appendix. Here, we would like to clarify our main assumptions again. In ridge regression, actually our assumptions are the same as the prior in-distribution results [Tsigler & Bartlett 2023]. All the assumptions are listed in the setup section and in the beginning of Section 3. We would also like to point out that our upper bound for ridge regression does not require assumptions that go beyond prior works. It is one of our core contributions that we generalize the in-distribution benign overfitting results without introducing additional assumptions. This stands in contrast to related work in section 1.1 which poses strong assumptions on target distributions. As for the PCR results in section 4, we use the same setup in section 2, and Assumption 1 [Tsigler & Bartlett 2023] in section 3 is no longer required. Actually we assume $\beta^{\*}_{-k}=0$ in Theorem 5 just for presentation clarity. We mentioned in Remark 5 that Lemma 31 provides the generic results without assuming $\\beta^{*}\_{-k}=0$. Regarding the gap between major and minor directions, it is not an assumption because our result holds regardless of this gap. Following the theorem, we discuss the impact of this gap on our bound. We thank the reviewer for suggestions to further improve clarity of assumptions. We modified our presentation in the beginning of section 4 to include the above statements.

Q3: Are the conditions considered in Section 3.1 the most general ones for which the rate of the excess risk is slow?

A3: We believe that the conditions in Sec 3.1 are general for Theorem 2 to hold. Regarding the slow rate for ridge regression, we further need the overall magnitude of the minor components on target to be small.

I sincerely thank the authors for the time to produce the numerical simulations. I believe that they give a more visual backing to the results.

I also better understand the results and the different assumptions used for the various results of the paper. I want to thank the authors for their clarity and patience.

I have thus decided to increase my score.

Thank the reviewer for your positive feedback and valuable comments and suggestions. Regarding your concerns and suggestions, we write our response as the following:

Q1: What are the main challenges in proving a matching lower bound for OOD similar to the in-distribution case? Also what is the technical contribution of this work?

A1: The proof techniques in prior work [Tsigler & Bartlett 2023] for both the upper bound and lower bound crucially rely on the source and target distribution are the same. To be specific, in proving the lower bound for the in-distribution case, they can express the variance term as a function of many independent subGaussian vectors, while this relies on the condition that the source and target covariance share the same eigenvectors (i.e., they are simultaneously diagonalizable). In our work, we do not assume such a strong assumption. Therefore, establishing a matching lower bound is much more difficult. Also, regarding the technical contribution, when establishing the upper bound, we found that if naively applying previous techniques, the derived upper bound is loose. As an example, by previous techniques, the variance of the first $k$ components will scale as $\frac{tr(\Sigma_S \Sigma_T^{-1})}{n\mu_k(\Sigma_S \Sigma_T^{-1})}$. This quantity depends on $\Sigma_S \Sigma_T^{-1}$ which is extremely loose because it indicates smaller target covariance causes larger excess risk in some cases. In fact, it is inconsistent with previous art [Ge et al. 2024] demonstrating that $\Sigma_S^{-1} \Sigma_T$ captures the covariate shift in under-parameterized linear regression. To deal with this issue, we establish a new technique for deriving a tight bound which reflects our intuition.

Q2: The fact that the analysis of OOD boils down only to the alignments of the covariance of the source and target distribution is closely to the square loss and linear estimator. How much should we expect this to transfer to other tasks, such as linear classification for instance?

A2: We can extend the current results beyond the linear model by considering kernel ridge regression. In practice, nonlinear estimators can be well approximated by RKHS. As long as a proper kernel is chosen, the kernel ridge regression becomes the linear regression on the transformed feature space. In fact, our results also hold for infinite-dimensional linear regression. Therefore, our bound can also be applied to kernel ridge regression. As for classification problems, it remains unknown whether “benign overfitting” might happen. This can be an interesting future direction.

Q3: Misleading sentence in L39-42 and typo in L11

A3: Thank you very much for pointing out an improper sentence and a typo in our writing. The typo is addressed. And we modify the sentence in L39-42, mentioning that LLM can be viewed as over-parameterized during the fine-tuning stage.

I thank the authors for their rebuttal, which addressed my questions. I am keeping my positive evaluation.

Thank the reviewer for your positive feedback and valuable suggestions and questions. The following is our response to your questions.

Q1: Numerical experiments.

A1: We thank the reviewer for suggesting the consolidation of theory with simulations. We have included two simulation experiments in Appendix A. The first experiment takes the benign overfitting setup proposed in the paper, involving small shifts in the minor directions. It confirms the $\mathcal O(1/n)$ rate for ridge regression. Data is generated from a multivariate normal distribution, with target covariance matrices randomly generated. We validate the influence of two factors $\\|\mathcal T\\|$, $\\mathrm{tr}[U]/ \\mathrm{tr}[V]$, identified in the paper as measures of covariate shifts in major and minor directions, respectively. The experiment results show that, for each combination of $\\|\\mathcal T\\|$ and $\\mathrm{tr}[U]/\\mathrm{tr}[V]$, the excess risk of ridge regression decays at nearly 1/n. For a fixed sample size, the excess risk increases with larger values of $\\|\\mathcal T\\|$ or $\\mathrm{tr}[U]/\\mathrm{tr}[V]$.

The second experiment compares ridge regression with Principal Component Regression (PCR) under large shifts in the minor directions. The setup follows the instance in Theorem 4, where the excess risk of ridge regression is lower bounded by $\mathcal O(1/ \sqrt n)$, while PCR achieves an excess risk of $\mathcal O(1/n)$. This result is confirmed by the experiment, where the excess risk of PCR is compared against ridge regression with various regularization strengths: $\lambda = 0, n^{0.5}, n^{0.75}, n$. The findings show that the excess risk of ridge decays optimally at the rate of $n^{-0.48}$ for $\lambda = n^{0.75}$, consistent with the $\mathcal O(1/ \sqrt n)$ lower bound in Theorem 4. The optimal regularization in the experiment also aligns with that derived in the theoretical proof. In contrast, PCR achieves a superior decay rate of $n^{-0.99}$.

Q2: Does the result in PCR require the number of relevant components k to be known in advance? What is the effect if the number is misspecified?

A2: Our theory does not require k to be known in advance, because our upper bound holds for any $k$ as long as the assumptions are satisfied (Lemma 31 provides the generic result where we do not require $\\beta^{\\star}\_{-k} = 0$), though when applying PCR, a specific $k$ needs to be chosen. The effect of $k$ is discussed in Sec. 4.2, where we show that PCR works well when the eigengap $\lambda_k - \lambda_{k+1}$ is large and $\beta^{*}_{-k}$ is small.