Provable Weak-to-Strong Generalization via Benign Overfitting

Rebuttal

We thank the reviewer for their feedback. We address their questions below. > Ideally, Theorem 3.3 should be standalone and at the very least, the variables in Theorem 3.3 like $\tau_{\mathsf{weak}}$, $p_{\mathsf{weak}}$ should be defined. - We agree that it is better to have theorem statements be more self-contained. Stating the theorem precisely requires using a decent amount of notation, and to reduce redundancy we have set up the data assumptions and notations explicitly in Theorem 3.2. For example, we have explicitly defined $\tau_{\mathsf{weak}}$ in line 419. - In the revision, we have amended the tags and wording in Theorem 3.3, especially around the two conditions in lines 421-423. It should hopefully be more intuitive what each condition is referring to. Also, we have reinforced the definitions of $\tau_{\mathsf{strong}}$ and $\tau_{\mathsf{weak}}$. > The notation and current presentation of the result doesn't really make it seem like this is a "simple, toy model", given how many free variables there are to keep track of. One possible fix is to give more intuition and less notation about the toy-model in the main text, and push the details into the Appendix. - We agree that there are many parameters floating around. However, we also believe that this bi-level covariance is essentially the simplest parameterization of low-rank data that can be tractably studied from a theoretical perspective. - In particular, these parameters can be interpreted as follows: $p$ specifies the ambient dimension $d$, $r$ specifies the dimension $s$ of the low-rank subspace, $q$ specifies the strength $a$ of the spike. A full specification of a low-rank data distribution needs to specify these three parameters. - We will try to include some more intuition about the main result in the revision, but we do think it is still important to have a fully precise statement in the main text. That way, a reader can know what is the exact statement being claimed without chance of ambiguity. > For example, I think it would be really helpful to have an informal, non-rigorous theorem summarizing the main result in the Main Contributions section. - In the main contributions, we have emphasized the informal statement of the main result. > why one should care about finding a "simple, concrete theoretical setting where we can provably exhibit different phases of weak-to-strong generalization?" - Weak-to-strong generalization is an interesting empirical phenomenon in ML models which might be important for scaling up post-training for foundation models. Human-labeled data is expensive to procure, but there is also no guarantee that using weakly-labeled data would scale well. Our theoretical results give provable guarantees for these kinds of training schemes in a toy setting. Moreover, because the setting is simple and theoretical, it is easier to trace down and explain exactly why the training strategy works. > what can I take away from this result? - One intuitive takeaway is that weak-to-strong generalization occurs based on how the strong model implicitly “knows” that certain latent directions in the weak model’s activations are more important than others. The weak model makes errors because its representations are low quality, but the key lies in the way its representations relate to the strong model's representations. Presumably, the reason the strong model's representations are better has to do with the way that it was pretrained as well as its own architecture. - Another takeaway regards our insights about multilabel vs multiclass training. In particular, we show that using multilabel weak supervision can do better than multiclass clean supervision! This suggests that in order to get effective weak supervision, whenever possible, one should use the logits / soft labels from the weak model to supervise the strong model. Because we can establish this rigorously in the classification-style setting here, it suggests that we should look for how to do a counterpart of this in the LLM setting (or more generically for generative models). Having access to a weak model for providing supervision opens up more possibilities than present with human-labeled data.

Rebuttal

We thank the reviewer for their positive review. Below, we address their questions. > What the the word "represent" mean in Desiredata 1.(ii). - Here we meant that the strong model can perfectly simulate the weak model. In other words, the strong model’s capabilities are a superset of those of the weak model. For the linear setting, this just means that the weak features are in the span of the strong features. > What is the significance of the bi-level-ensemble? - The bi-level ensemble is a minimal instantiation of a spiked covariance model that fully specifies all the aspects of the covariance of the data, i.e. a toy model for low-rank structure. You can also think of it as a parameterized linear manifold hypothesis. The bi-level ensemble has been studied in previous works as a way to state cleaner theoretical results for benign overfitting [1-4]. > What is $t$ in Theorem 3.1? - As mentioned in the response to Reviewer Ns5A, $t \in [0, s)$ controls the number of label classes in the multiclass problem: $k = n^t$, following Definition 2. We have updated the wording of the theorem to make this more explicit. > Is there a reason for choosing a halfspace for the ground truth? Does this analysis extend to other concepts. Is there a similar notion for regression (rather than classification)? - (Shifted) halfspaces are fundamental in the study of classification. For example, even complicated neural network architectures for multiclass / binary classification are predicated on halfspaces, since the last layer is usually a linear head. The analysis would not directly work beyond the linear setting, as we use the explicit analytic form of the minimum $\ell_2$-norm interpolator. - For regression, the same linear model that gives a halfspace can also be used as a regression model, if one doesn’t apply softmax. Our analysis should go through in this case: previous work [3] already developed the tools to tightly characterize the regression setting. [1] Wang, K., & Thrampoulidis, C. (2022). Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization. SIAM Journal on Mathematics of Data Science, 4(1), 260-284. [2] Wang, K., Muthukumar, V., & Thrampoulidis, C. (2021). Benign overfitting in multiclass classification: All roads lead to interpolation. Advances in Neural Information Processing Systems, 34, 24164-24179. [3] Muthukumar, V., Narang, A., Subramanian, V., Belkin, M., Hsu, D., & Sahai, A. (2021). Classification vs regression in overparameterized regimes: Does the loss function matter?. Journal of Machine Learning Research, 22(222), 1-69. [4] Wu, D., & Sahai, A. (2024). Precise asymptotic generalization for multiclass classification with overparameterized linear models. Advances in Neural Information Processing Systems, 36.

Rebuttal

We thank the reviewer for their comments and address their feedback below. > Most of the important details are pushed into appendix. The main body only contains one useful theorem which identifies a certain condition where condition 1) of weak to strong generalization holds. Setting for condition 2) and multi class settings are merely mentioned as claims. - Condition 2) is essentially Desiderata 2.ii, which is not a core part of the weak-to-strong generalization phenomenon. We mention this merely as a claim because, it essentially just reduces to checking the conditions from Theorem 3.1, i.e. that $\tau_{\mathsf{strong}} < 0$. We have updated Remark 3.4 to make this more explicit. - Regarding the multilabel/multiclass setting (Theorem 3.5), as stated in the text, it requires some additional setup, so due to space constraints we could not elaborate much further on it formally. We will add some comments to convey the intuition of the proof and how it reduces to the binary classification analysis. > The main body also does not provide proof sketch or provide insights into the proof of the theorem. - In the revision, we have moved the proof sketch back into the main text. The brief idea is that, we can analyze the SNR of the true direction $v_*$ when the model is trained on labels generated by another direction $w$. We can use this high level strategy to analyze the generalization of the weak model, as well as the generalization of the weak-to-strong model. > Reduce the introduction - it currently spans 2 pages. - We have condensed the introduction, while still attempting to be fair and thorough with our literature review. > Figure 1 is useless - We have removed Figure 1. > The section on data model was not particularly needed. Page 5 and 6 can be compressed into 1 or 2 paragraphs. - We believe that since the weak-to-strong generalization setup is slightly nonstandard, it can be a little confusing if readers are unfamiliar with the concept. Also, since the result crucially relies on the data assumptions, it was worth being more thorough with the assumptions (perhaps at the risk of being slightly verbose). We have attempted to slightly trim down on the more redundant parts, but think that compressing much more would hamper the paper’s readability. > Include some experiments in main body. - We have moved some of the MNI experiments from the appendix back into the main text in Figure 2.

Rebuttal

We thank the reviewer for their feedback. Below, we address their comments. > The main setup is quite confusing to me. The paper first states that "$f_{\mathsf{weak}} \in \mathbb{R}^d$" is the object we learn. Normally, the model is a function, not a vector, so this was not immediately clear. It is defined later in line 347 how we learn $f$, which is quite far from where it was introduced (line 184). It would be better to define that we train $f$ by MNI earlier. - We apologize for the confusion with the notation. We have uploaded an updated version where we clarify this, including clarifying how $f$ is trained by MNI earlier. Our goal with the discussion around Line 184 was to encapsulate many different w2s training schemes, but we agree it is helpful to keep a concrete algorithm in mind. > In line 201, it says, "As a consequence of our main results in Section 3, we will show that the above desiderata are achievable in a simple toy model; see Theorem 3.3 for a formal statement." However, Theorem 3.3 only considers desiderata 1.2 and 2.1, not the entirety of the desiderata. - The two equations in Lines 421-422 contain the conditions for the additional Desiderata being satisfied. In the revision, we have stated more explicitly that Desiderata 1.i-1.iii are all satisfied, and changed the tags to make it more intuitive. In addition, Remark 3.4 discusses Desiderata 2.i and 2.ii. We felt it would be distracting to focus on the bonus desiderata too much, so we moved it to the Remark. We updated the writing near Line 201 to reference Remark 3.4 regarding the bonus desiderata. > What is $t$ in Equation (3) of Theorem 3.1? - $t \in [0, s)$ controls the number of label classes in the multiclass problem: $k = n^t$, following Definition 2. We have updated the wording of the theorem to make this more explicit. > The notation $u,p,q,r$ used is not very intuitive, and it makes the result difficult to interpret. Is there a simpler way to rephrase the result? - We apologize for the confusion. The reason we chose this type of notation is that prior work in this area has used similar conventions (see, e.g., [1-4]). We thought it might be easier to work in log space (where conditions are additive) as opposed to multiplicative, but we can try to add a couple sentences to rephrase things. [1] Wang, K., & Thrampoulidis, C. (2022). Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization. SIAM Journal on Mathematics of Data Science, 4(1), 260-284. [2] Wang, K., Muthukumar, V., & Thrampoulidis, C. (2021). Benign overfitting in multiclass classification: All roads lead to interpolation. Advances in Neural Information Processing Systems, 34, 24164-24179. [3] Muthukumar, V., Narang, A., Subramanian, V., Belkin, M., Hsu, D., & Sahai, A. (2021). Classification vs regression in overparameterized regimes: Does the loss function matter?. Journal of Machine Learning Research, 22(222), 1-69. [4] Wu, D., & Sahai, A. (2024). Precise asymptotic generalization for multiclass classification with overparameterized linear models. Advances in Neural Information Processing Systems, 36.