Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers a popular approach to semi-supervised learning based on iterative pseudo-labeling the unlabelled data and refining the model parameters thereafter. The paper is supported theoretically for the case of the Gaussian mixture model establishing a generalization error bound based on the KL divergence between the pseudo-labeled and true data distributions. The paper is also supported empirically for binary classification examples coming from CIFAR10 and MNIST datasets

main_review: Dear Authors, 

Please find my review below. Sorry for submitting it late. 

The reviewer likes the approach proposed in this paper; however, I would like to express several concerns regarding the theoretical power and limitations of the result. My main concern is about the results' impact and there how do they advance the state-of-the-art.  Please, find below some of the most crucial ones: 
1. Theoretical bounds are based on the KL divergence between the pseudo-labeled and true distributions, which is hard to measure/estimate unless the additional information is specified. Any computable upper bound?
2. The loss function used for the generalization error computation is designed in such a way that even for a high misclassification rate on later stages the loss function would converge. (See Eq.~ 5 for the details)
3. No lower bound is provided. Any bound known from the literature?
4. Figure 1: the upper bound on the generalization error, which should be in between 0 and 1, is about 14 at convergence. Why is it so? A small number of objects? A similar concern regarding Figure 6. 
5. When one is talking about the generalization error, one derives the bound for a class of functions rather than for a single function. However, in the paper 

Overall, I believe the paper is interesting, but it can not be accepted as is unless the authors' resolve these comments. 
summary_of_the_review: The results are interesting; however, it is not clear to me how one can extend the results beyond the Gaussian mixture model considered in the paper. Furthermore, it is not clear how to get efficiently computable bounds from the statements of Theorems 1-3. The bounds are needed for model complexity penalization. Also, the following questions are needed to be addressed: 

- Theoretical bounds are based on the KL divergence between the pseudo-labeled and true distributions, which is hard to measure/estimate unless the additional information is specified. Any computable upper bound?
- The loss function used for the generalization error computation is designed in such a way that even for a high misclassification rate on later stages the loss function would converge. (See Eq.~ 5 for the details). Could you advocate using this bound?
- No lower bound is provided. Any bound known from the literature?
- Figure 1: the upper bound on the generalization error, which should be in between 0 and 1, is about 14 at convergence. Why is it so? A small number of objects? A similar concern regarding Figure 6.
- When one is talking about the generalization error, one derives the bound for a class of functions rather than for a single function. However, in the paper
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers one common semi-supervised learning algorithm, pseudo labeling, and studies this problem from theoretical point of view. Specifically, it derives an information theoretic upper bound on generalization error in each iterative update of pseudo labeling. They separate the bound into two main parts: one depends on the mutual information between the data samples and model parameters, and the other depends on the KL distance between the underlying data distribution and pseudo labeled samples from previous iteration. Their main conclusion is that as the number of labeled and unlabeled samples grows, the first term vanishes, but the second term does not necessarily vanish. 

In the rest of the paper, the authors rely on the simple example of binary Gaussian Mixture Model to give a more understandable and sensible calculation of the their upper bound. Namely, they calculate the KL distance and mutual information terms in the main theorem and study the behavior of generalization error for this model. The conclusion they made is that the iterative pseudo labeling can decrease the generalization error for only the first few iterations and after than has no effect on reducing the generalization error. 
main_review: Strength: The conclusions and observations about generalization error is made in the regime where n -> infinity and m->infinity and m >>n. The analysis seems sound and credible. I did not check the proof in the appendix, but the results and overall proof sketch in the main paper seems reasonable.
Weakness: While the result is sound and theoretically valuable, it is not surprising at all in the regime studied (m and n large). The paper starts with the motivation that labeled data is limited, and pseudo labeling is shown to be helpful, but studying the regime where we have growing number of labeled samples does not completely intersect with that motivation. Also, the authors mention that after a few iterations, the accuracy might improve, but the generalization error does not, and I think it is worth elaborating on this point to see where this improvement is coming from.

Weakness: In the last section, the authors show with experiments on MNST and CIFAR datasets that the generalization error only decreases for a few iterations of pseudo labeling and then saturates. However, this observation is not very obvious to me by just looking at figures. Based on Figures 7, 8, and 9, there is a sharp reduction in generalization error after only one iteration, but after that, it is not necessarily decreasing. The overall trend of vanishing generalization error until a saturation limit is acceptable based on the plots, but drawing conclusions that for the first iterations we have significant reduction and then the reduction vanishes is not quite clear to me. For example, in figure 9, we have reduction in generalization error for the first iteration, then we have a jump in the generalization error followed by another sharp decline. It would be helpful if authors could explain these ups and downs in the plots. 

Weakness: Also, the first iteration used a neural network that is well trained and converged to a good solution, then we use this well-trained network to predict labels for a subset of data, and fine-tune the network using the newly-labeled data. This is no surprise to me that more than a few rounds of fine-tuning will not improve the generalization error.

Strength: The paper is overall very well written and well-organized with the exception of section 4 where the authors could have done a better job of further dividing the section into multiple subsections.

Minor comments:

- In the informal statement of Theorem 1, it is better to mention that this bound is for pseudo labeling algorithm and not any SSL algorithm. 
- In Equation 6, I could not find what f_{\theta_{k}} is.
- For section 4, it would be better to subdivide it into a few subsections. It was not smooth to follow the whole section. 
summary_of_the_review: The analysis of the paper seems interesting and correct. It is novel to look at the generalization error at each iterative update. However, I do have concerns about the significance of the work. It is not clear to me and it was not made clear by the authors how we can make use of this analysis and conclusions to train better models for example.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of semi-supervised learning where pseudo-labeling is used to iteratively assign labels for unlabelled data batches to enlarge the labelled dataset for subsequent re-training of the classification model. The paper first adapts the recent results of Bu et al (2020) and Wu et al (2020) to this set-up and provides a general information-theoretic upper bound for the generalization error of such a learning algorithm. The paper then specializes its set-up to a binary classification problem with Gaussian class conditionals and presents its corresponding generalization bound. Additional experiments are performed on the more practical datasets with deep neural network classifiers. 
main_review: **Strength**

The paper presents a new general algorithm-dependent generalization bound for semi-supervised learning with iterative pseudo-labelling (Theorem 1) and an application of the bound to binary classification with Gaussian class conditionals (Theorem 2).  

**Weakness**

Although the work is interesting and has some merit, to this reviewer, the theoretical results (Theorems 1 and 2) are quite far from the setting in the real world in which deep neural nets are used as the classifier and the training is done via SGD. Specifically

* Theorem 2 considers only a toy problem setting. In fact this setting is very well studied in Castelli and Cover (1996) ("The Relative Value of Labeled and Unlabeled Samples in Pattern Recognition with an Unknown Mixing Parameter") albeit not considering an iterative pseudo-labeling approach. Compared with Castelli and Cover (1996), the current paper does not seem to offer deeper insight or stronger results. -- Agreeably it may not be fair to compare the two papers, since the considered learning algorithms are different. But I invite the authors to study this classical paper on semi-supervised learning, which is missed in the reference list of this paper.  

* Theorem 1 does have the potential for analyzing SGD-alike learning algorithms on deep neural nets. But the authors did not pursue further along this direction, while only studying such more practical settings via experiments. 

The experimental results related to deep neural networks appear distant from the theoretical development. To this reviewer, they are inadequate to validate or support the theoretical development. 

summary_of_the_review: The paper presents new generalization bounds for semi-supervised learning under iterative pseudo-labeling. But the results are distant from settings of practical interest.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a generalization error bound for iterative semi-supervised learning (SSL) algorithms using information-theoretic principles (see Theorem 1). To provide more intuitions, the authors first work with a simple model, i.e., the binary Gaussian mixture model (bGMM). It is shown in bGMM that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates. The theoretical results on the simple model are corroborated by experiments on MNIST and CIFAR datasets, where similar phenomena are observed, i.e., the generalization error improves after several pseudo-labelling iterations, but saturates afterwards.
main_review: I have a question regarding to the SSL algorithm considered in the paper, splitting of the unlabeled dataset into \tau disjoint part is something unnatural to me. I understand that making \hat{S}_{u,k}  independent would simplify the analysis, but can you give more discussion on such a formulation compared to using the entire unlabeled dataset and update the pseudo-label in each iteration? Can we interpret it as a bias-variance trade-off, as more samples would reduce variance, but the low quality of the pseudo-label would increase the bias? 

The organization of section 4 can be improved by using subsections and subtitles, which emphasize the main take-away message of each discussion and remark in words. There are so many new notations introduced in this section, and they are not well-explained, especially the G_\sigma and F_\sigma function. If we only care about the monotonicity of these functions, then a lot of technical details can be moved to the appendix, so that the discussion of related works can be incorporated in the main body of the paper.

I feel like the experimental result is not very informative, as it only shows that similar generalization behavior (decrease and then saturate) can be observed in practice. However, such a phenomenon is expected, and something more useful would be how to use such bounds to predict the performance of SSL algorithm and further improve it. Maybe the authors could provide more discussion on the “cat” and “dog” result and talk about the influence of the label noise in real dataset.  

summary_of_the_review: This paper provides a novel information-theoretic generalization bound for semi-supervised learning, which involves both disintegrated mutual information (characterizing the input output sensitivity) and the disintegrated KL-divergence (distribution mismatch for pseudo-label) conditioned on the previous outputs. To my knowledge, the bGMM results are quite novel and interesting.
review_title: null

Meta-review: This paper studies the generalization error of semi-supervised learning, where the algorithm gradually pseudo-labels the data throughout the learning process. Theoretically, an upper bound on the generalization error is shown to decompose into a term that vanishes with successive labeling and another that does not, leading to a plateau in performance. This is studied analytically for a mixture of two Gaussians. Experimentally, similar behavior is also observed to occur in more realistic scenarios. What reviewers struggled with is to understand what part of the results are, to some extent, obvious, and what offer deeper insight. What is obvious: even if a Bayes classifier were available for pseudo-labeling, feature overlap means that there is a plateau of noise beyond which labeling cannot improve. What is not obvious: is it even worth pseudo-labeling, or could we make things worse? The merit of the paper is in elucidating the latter. There are several concerns that remain, however, even after discussions. First, there is whether the insight is substantial or not. Here, some comparison and contrast with existing literature suggests otherwise. Second, there is whether the experimentally observed behavior is an instance of the phenomenon described by theory. Here, better structured experiments are needed to tie in with the theory. Overall, although the paper presents compelling insight, it is not yet ready to disseminate. It needs a stronger argument for its added theoretical contribution and clearer experiments to support that the presented theory is indeed behind the empirical behavior of these iterative algorithms.
Decision: Reject