Theoretical Analysis of Weak-to-Strong Generalization

Summary

The paper provides a theoretical analysis of weak-to-strong generalization, a phenomenon where strong models can learn from weak supervisors and outperform them [[Burns et al 2023](https://arxiv.org/abs/2312.09390)]. The authors make precise assumptions about the nature of the strong student model family and the weak supervisor mistakes. Specifically, (1) near any datapoint (where neighborhoods are defined according to the strong student model class) that is incorrectly labeled by the weak supervisor, there should be many correctly labeled datapoints and (2) datapoints that are unlabeled (i.e. in the test set) also have a correct number of correctly and incorrectly labeled datapoints in the neighborhood. The authors make these ideas mathematically precise, and derive generalization bounds for empirical risk minimization for the strong student model. Importantly these bounds describe two phenomena: (1) pseudolabel correction, i.e. correcting for the mistakes of the weak supervisor and (2) coverage expansion, i.e. generalization to unlabeled datapoints. Finally, the authors provide a way of statistically testing their assumptions empirically, and show that they are applicable in one setting: sentiment analysis with a bag-of-words supervisor.

Strengths

S1: The theoretical approach used by the authors makes sense intuitively. The authors often provide an informal intuition for the definitions and results that they derive. S2: The derived generalization bounds are to the best of my understanding novel and non-trivial. The authors provide detailed comparisons to existing generalization bounds for weak supervision. S3: The authors provide a rigorous statistical method, as well as a heuristic for testing their assumptions in practice. S4: The authors evaluate their assumptions and bounds in a simple empirical setting.

Weaknesses

W1: While the core of the paper makes sense intuitively, the paper becomes more mathematically dense and hard to follow towards the end. W2: It is not obvious to me that the paper provides a novel empirical insight. As authors admit in the limitations section, they do not provide a new training method with improved weak-to-strong generalization or generally make practical recommendations. However, the paper makes a valuable contribution in formally describing conditions under which we can provably get weak-to-strong generalization. W3: The empirical evaluation is limited, and only covers one simple case. It would be very interesting to apply the bound to several settings, with varying weak-to-strong generalization. For example, can the bound predict the result in [[Burns et al 2023](https://arxiv.org/abs/2312.09390)] that weak-to-strong generalization doesn't work well on the reward modeling task? Does the bound provide an intuition for why that would be the case?

Questions

Q1. See questions in W3. Q2. 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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitations are adequately discussed.

Summary

The paper provides a theoretical explanation for weak-to-strong generalization. A weak model produces pseudolabels that can have errors and may not cover the entire input space. The paper argues current weak supervision theory fails to explain how and when the strong model can correct the psuedolabels (pseudolabel correction) and expand the coverage of pseudolabels (coverage expansion). The authors derive a new bound based on the expansion properties of the data distribution and the hypothesis class of the strong model. Their bound suggests that generalization occurs when the strong model is unable to fit the mistakes of the weak model without incurring additional errors. They provide experiments to show the expansion properties are verifiable in practice.

Strengths

1. The paper shows the gaps in the existing theory of learning from weak labels ( potentially erroneous labels available for part of the input space). In programmatic weak supervision (PWS) the focus has been on aggregating several weak labeling sources and showing that learning with aggregated labels is as good as learning from clean labels when the weak labeling sources satisfy certain conditions. The paper shows shortcomings of the previous results on PWS – failing to explain pseudolabel correction and coverage expansion. 2. It provides upper bounds on the expected error of the learned strong model on the part of the space that is covered by the psueodlabels and the part that is not covered. The first bounds suggests the error decreases in the covered part implying pseudolabel correction. A non-trivial error bound is provided on the error of the strong model in the uncovered set by utilizing the expansion property i.e. many points in the uncovered set have many correctly pseudo-labeled points. 3. The authors also provide a theoretical result suggesting that the expansion property is statistically checkable with finite samples but is computationally hard. They provide a heuristic approximation to verify the property in practice.

Weaknesses

1. It is not clear from the bounds how the size of covered sets (pseudolabel coverage) affects the results and why are the results in terms of subsets of the covered set. Is it possible to provide a final result conditioned on the entire covered set? 2. The improvements in terms of coverage and error correction are not immediately clear. For instance, the following paper [1] explains the improvement in coverage with self-training in a specific setting. It would be useful to have a discussion and instantiation to some specific settings like in [1] to understand the results better. [1] https://arxiv.org/abs/2006.11006

Questions

1. How do the bounds depend on the size of the covered points and by how much does the coverage improve? 2. Where does the complexity of the strong model's function class come into play, how do the bounds depend on it? What happens in the case of self-training when the function class of strong and weak models are the same.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes.

Summary

This paper proposes a theoretical framework to interpret the weak-to-strong generalization phenomenon. It shows that strong student models trained on noisy labels from weak teacher models can outperform the weak teacher models, correcting their errors and generalizing well to examples where the weak teacher models are not confident or abstain. The paper demonstrates that existing bounds for learning from noisy labels do not explain this phenomenon and derives new bounds based on assumptions about the strong model’s robustness in its neighborhood and its expansion property. An empirical study validates the generalization bound in a practical setting.

Strengths

- Weak-to-strong generalization has gained renewed attention despite being well-known in weak supervision. However, there has been no theoretical analysis of why a model trained with noisy labels can be more accurate than the labels themselves. This paper’s contribution is crucial as it provides a theoretical framework for this problem. - The theory explains under what conditions weak-to-strong generalization can occur, which has practical implications. - The paper is technically solid, with reasonable assumptions for derivation. Sections 4.2 and 5 add to its practicality. - The writing is clear and the main ideas are easy to follow.

Weaknesses

- The experiment is limited to only one setting, though it is already mentioned in the limitations section. This is a minor concern since the paper is primarily theoretical.

Questions

- Adding comparisons with recent concurrent works ([1, 2, 3]) would be beneficial. I am curious about the authors' views on these papers and whether there are any conflicting points in theory or if the conclusions are well-aligned. - Including simpler or synthetic experiments could enhance the paper. The (c, q) expansion property in a practical setting is not intuitively straightforward. [1] Somerstep, Seamus, et al. "A statistical framework for weak-to-strong generalization." *arXiv preprint arXiv:2405.16236* (2024). [2] Charikar, Moses, Chirag Pabbaraju, and Kirankumar Shiragur. "Quantifying the Gain in Weak-to-Strong Generalization." *arXiv preprint arXiv:2405.15116* (2024). [3] Zhang, Edwin, et al. "Transcendence: Generative Models Can Outperform The Experts That Train Them." *arXiv preprint arXiv:2406.11741* (2024).

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

Authors adequately addressed the limitations in Conclusion.