Theoretical Analysis of Weak-to-Strong Generalization

For example, can the bound predict the result in [Burns et al 2023] that weak-to-strong generalization doesn't work well on the reward modeling task?

Great question! Our analysis is limited to classification for now, since we essentially assume that the class-conditional sets $\mathcal{X}_i$ have some neighborhood structure that is respected by the hypothesis class of the strong model. This type of assumption makes the most sense when $\mathcal{X}_i$ has some consistent semantic meaning. In the reward modeling case, the labels (chosen/rejected) are not semantically meaningful in the same way, so different structural assumptions are likely required. While our bounds don't explain the lack of weak-to-strong generalization in reward modeling, we are encouraged that they seem to plausibly capture these effects in classification problems. We will add reward modeling / ranking losses as an interesting direction for future work!

Which of the assumptions specifically captures the intuitive notion that the strong student should not be able to fit the mistakes of the weak model too well?

[Related question from Reviewer 3HaP] What happens in the case of self-training when the function class of strong and weak models are the same?

If the strong model class can exactly fit the weak model, the expansion assumption is not satisfied, as we now show.

Suppose we have a weak model $\tilde{y} \in \mathcal{F}$ and aim to fit a strong model $f \in \mathcal{F}$. In this case we can have $f = \tilde{y}$ (i.e., the strong model exactly fits the weak model), so suppose that is the case. The class of sets we need to expand for pseudolabel correction is $\mathcal{M}’ = \\{R(g) \cap S_i^{good} \setminus \text{mistakes}(g) : g \in \mathcal{F}\\}.$

Since $f = \tilde{y}$, $S_i^{good} \setminus \text{mistakes}(f) = S_i^{good}$. Now consider a pair $(x,x')$ with $x\in S_i^{good}$, $x' \in \mathcal{N}(x)\cap S_i^{bad}$. Since $x$ and $x'$ are both in $S_i$, $y(x) = y(x')$. Then we have $f(x) = \tilde{y}(x) = y(x) = y(x') \ne \tilde{y}(x') = f(x')$, so $f(x) \ne f(x')$. Thus $x$ is not in $R(f)$. Since $x$ was an arbitrary point in $S_i^{good}$, this shows $R(f) \cap S_i^{good} = \emptyset$, so $\mathcal{M}’$ contains $\emptyset$. In this case, expansion requires: $0 = P(\mathcal{N}(\emptyset) | S_i^{bad}) > c P(\emptyset | S_i^{good}) = 0,$ which is not possible.

Working out this example hopefully gives more intuition for the expansion assumption, and we will include it as an example in the paper. Thanks for the question!

Is it possible to provide a final result conditioned on the entire covered set?

Yes, we just left it out for space and because getting a combined bound with a simple functional form requires more definitions (max/min of the weak label errors $\alpha_i$, the minimum expansion parameter across all the $S_i$'s, etc). Given these definitions, the combined bound essentially follows from averaging the bounds on each $S_i$. Similarly, we can give a combined coverage expansion bound conditioned on the entire uncovered set $T$ instead of the individual covered sets $T_i$. These two combined bounds can also be averaged together to get a final combined bound on the unconditioned error $err(f,y)$. We will include combined bounds in the Appendix.

It is not clear from the bounds how the size of covered sets (pseudolabel coverage) affects the results

Thanks, this is a great point. We had a discussion on the role of coverage and had to cut it for space since it affects our bounds in a somewhat subtle way. The most direct way in which coverage enters the bounds would be in a combined error bound that uses $err(f,y) = err(f,y|S) P(coverage) + err(f,y | T) (1-P(coverage))$ and then applies the combined-source and combined-target bounds discussed in our reply to your previous question to $err(f,y|S)$ and $err(f,y|T)$, respectively. However, this doesn’t capture the full story.

The “coverage rate” $P(S)$ also enters the picture implicitly in the $S$–$T$ expansion parameter. For a fixed neighborhood $\mathcal{N}$ (e.g., all points with similar embedding), it will be qualitatively easier to have expansion from $T_i$ to $S_i$ when $S_i$ is larger, since (informally) for each uncovered point in $T_i$, there are more possible covered neighbors in $S_i$. But increasing the coverage by including more points in $S_i$ might also affect the weak label accuracy parameters $\alpha_i$, which also affect the bounds.

In practice, there is not a clear tradeoff between coverage and performance, as explored recently in, e.g., [37], so it qualitatively makes sense that our bounds do not prescribe a functional dependence of the error on the amount of coverage and instead allow that dependence to enter through data-dependent parameters (expansion $c$ and weak error rate conditioned on coverage $\alpha_i$). We hope this at least partially answers your question and we will include a more detailed discussion of the role of coverage in the final draft.

[How do the bounds depend on] the complexity of the strong model's function class?

Great question! Following related work on expansion-based bounds (e.g., [23]), our error bounds are expressed as relationships between population quantities (e.g., expansion, population error on the weak/ground-truth labels). There is no statistical estimation aspect, which is where the complexity of the strong model's function class directly enters the picture. We focus on population quantities because relating the population error on the weak and ground-truth labels is the key problem-specific component. Once these quantities are related, the sample complexity aspect is more standard and can be dealt with by applying existing generalization bounds. We discuss this topic in more detail in Appendix B.5.

The strong model hypothesis class can also enter the bounds indirectly via the expansion parameter, since the amount of expansion depends on that class. A richer class for the strong model may decrease the amount of expansion. For example, if the strong model class is rich enough to exactly fit the weak labels, there is zero expansion, as worked out in our response to Reviewer cokD. At the same time, the error of the strong model on the weak labels appears as a term in the bounds ($err(f,\tilde{y} | S_i)$), and a richer class might decrease this term. So these two terms capture a potential tradeoff—a stronger hypothesis class may decrease the expansion, but it may also decrease the error on the weak labels. Whether this makes the bounds tighter or looser depends on the sizes of these decreases. As with the coverage $P(S)$, our bounds do not prescribe a functional form for this dependence and instead allow it to enter via data-dependent parameters. This should make the bounds flexible enough to capture seemingly conflicting empirical results, where sometimes a stronger hypothesis class works better and sometimes a weaker one works better, as seen for example in the WRENCH weak supervision benchmarks [73].

We will highlight this implicit dependence in Section 4. An interesting direction for future work is to see whether these tradeoffs can reveal how to pick a strong model hypothesis class for a given weak labeler, or pick a weak labeler for a given strong model hypothesis class. Thanks for the insightful question.

It would be useful to have a discussion and instantiation to some specific settings like in [1] to understand the results better.

We wanted to include an instantiation of the results for special cases in the main text, but were limited by space. Appendix C.1 has a worked example under the distributional assumptions of co-training (where each data point consists of two conditionally independent views). We can mention this as a simple example where the expansion assumptions are satisfied with good values for $c$. There are other distributional assumptions that lead to good expansion, such as the Gaussian Mixture Model style distributions studied in Oymak and Cihad Gulcu---Wei et al. [69, Example 3.4] showed that GMMs satisfy their expansion assumption, which is very related to ours. We will extend our existing discussion of Oymak and Cihad Gulcu in Appendix A to comment on its relationship to our assumptions.

What happens in the case of self-training when the function class of strong and weak models are the same?

Please see our response to Reviewer cokD! We will include this in the paper as a worked example of a case where expansion does not hold.

Adding comparisons with recent concurrent works ([1, 2, 3]) would be beneficial.

Thanks for pointing these out! First, we just want to note that all 3 of these works appeared on arXiv after the NeurIPS submission deadline, so we were not aware of them at the time of submission.

Broadly, [1] and [2] are similar to our paper in that they make some structural assumptions under which weak-to-strong generalization can provably occur. [1] uses a framing of weak supervision as transfer learning to give pseudolabel correction results when the data is distributed according to a Gaussian Mixture Model, whereas we do not make specific distributional assumptions and also focus on coverage expansion in addition to pseudolabel correction. As discussed in our response to Reviewer 3HaP, Gaussian Mixture Models can be shown to satisfy notions of expansion. [2] is the most similar to our paper, but focuses on pseudolabel correction for regression problems, whereas our work tries to explain both coverage expansion and pseudolabel correction for classification problems—both phenomena are important in weak supervision settings that we are interested in. Additionally, the underlying assumptions and conceptual ideas are very different. In our work, we use structural notions of expansion to explain these two phenomena, and our bounds directly generalize existing results from other literature (co-training, self-training), and extend this theory to more general settings. In [2] they assume convexity of the hypothesis space for fine-tuning, and show that projections onto this space can explain pseudolabel correction effects. We feel these two explanations are very different but potentially complementary, and it would be very interesting future work to develop a common framework that incorporates both. [3] considers a qualitatively very different setting, showing that when the training data consists of a mixture of data generated by different experts, a strong student model can be better than the best single expert that generated the data. Their results are more related to classical work on crowdsourcing, where by observing generations from many experts the learner can outperform the best single expert. Our paper and [1] and [2] consider the case where there is a single weak teacher model (which itself may be an ensemble of many models, but this is not exposed to the learner).

Including simpler or synthetic experiments could enhance the paper. The (c, q) expansion property in a practical setting is not intuitively straightforward.

Thanks for the suggestion! Per our responses to the other reviewers, we will include a worked example that shows (c,q)-expansion does not hold when the strong model can exactly fit the weak model’s errors. Subject to space limitations, we can also include a version of the content in Appendix C.1, which gives a very straightforward setting (“conditionally independent views”) where the expansion assumptions hold. These examples should give more intuition for how the assumption works.