Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper suggests a simple denoising technique for existing semi-supervised learning methods (with surrogate objectives). The proposed objective is shown to have less variance in some cases, and is now consistent when $n->\infty$.
strengths_and_weaknesses: **Strengths:**
- The debiasing technique is simple and easy to implement, which can be added to existing SSL methods without much effort.
- The authors provide solid theoretical contributions regarding the variance of the proposed objective and the consistency of its minimizer.

**Weaknesses**
- Some missing parts on the theory side. I am more interested in the reduced variance of the proposed objective. The authors showed that at $\lambda_{opt}$, the objective has less variance than the standard complete case. However, this $\lambda_{opt}$ value is often unknown or hard to estimate in practice due to $\rho_{L,H}$, so the theorem is less meaningful. I wonder if we can find out the range of $\lambda$ in which we have reduced/increased variance. For example, if the range for reduced variance is small, the method would be less robust (too sensitive to the choice of $\lambda$), thus becoming less meaningful.

- The experiments section is weak. Why don't the authors verify the proposed debiasing term with all three well-known pseudo label, entropy minimization, and consistency-based methods for all experiments (MNIST, MeMNIST, CIFAR)? I imagine these experiments are not too computationally expensive.

questions: - The first point in my weaknesses section regarding the theory part.

- If the authors can provide a more complete empirical evaluation of the debiasing term with the most common existing SSL methods (pseudo label, entropy minimization, and consistency-based) to show the benefit of the proposed technique.
limitations: The authors claim in the checklist that they have discussed the limitations of the work in Section 5, but no limitations are mentioned there.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper focuses on semi-supervised learning and tries to give theoretical guarantee about the safeness of semi-supervised learning methods. Specifically, the authors propose a dibiasing approach, and combine it with the deep SSL methods. Theoretical ananysis about the generalization are discussed.
strengths_and_weaknesses: Strengths:

1) This paper focuses on safe semi-supervised learning problems. This is an important problem for SSL methods, and it is a good attempt to give a theoretical analysis of semi-supervised learning methods.

Weakness

1) The paper's presentation is very poor and very hard to follow. The figures and tables need to be reorganized.

2) The paper gives a new definition of safe SSL: "a SSL algorithm is safe if it has theoretical guarantees that are similar or stronger to the complete case baseline". How to judge whether the theory is stronger?  The "safe" is related to the performance, i.e., the performance is guaranteed not to be reduced compared with the baseline supervised learning method.

3)  The theoretical result does not give a guarantee that the performance will always be better than the supervised learning method. So it does not consist with the author's claim.
questions: 1) Why is the proposal guaranteed to be safe? It seems that the results cannot guarantee that the proposal will always be better than the simple supervised learning method.
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes to debias the training objective for semi-supervised learning (SSL) methods. The paper suggests a simple modification to the training objective, which de-biases it, by reducing the certainty on labelled datapoints, and considering the whole objective as an optimization of the complete case with a constraint on the two sets of labelled and unlabelled datapoints to satisfy the same property on the SSL loss $H$ on average. Then, the authors proceed to prove statistical learning results on the debiased SSL method, and empirically demonstrate the usefulness of the approach.
strengths_and_weaknesses: Strengths: 

1) The idea of the paper is clear and sound. The bound on the variance of the DeSSL risk estimate and the generalization bound are useful. They give us generalization insights about SSL, and the benefit from the correlation between $L$ and $H$.

2) The experiments demonstrate that the intuition about the usefulness of debiasing benefits standard SSL benchmarks. I like the toy task example as well.

3) Overall, the paper is clearly written. The proofs seem correct to me, although I have not been able to check every single detail.

Weaknesses: 

1) It would be interesting to test your debiasing on a larger task, such as ImageNet. For example, how does debiasing work for PAWS (https://arxiv.org/abs/2104.13963)? 

2) I think the paper should discuss the role of the debiasing, and the role of the reducing of the confidence on the labeled datapoints. I think the latter is important for the success of the method, and the theory as well. However, just by looking at the main paper, this doesn't stand out. 

For example, we can achieve debiasing by splitting the unlabelled dataset in two parts and using the red term on one part and the blue term on the other (using the color convention from Equation 5 in the main text). Doing, this, we will make the estimate unbiased, but we will not learn good representations (I think), because we have two conflicting objectives on the unlabelled dataset. Having the blue term on the labelled dataset is very important, I think, but it does not stand out in the paper right now. I think the blue term helps with calibration, as the ECE experiments show in the Appendix. Please, discuss this more. 
questions: What will happen if we replace the labeled data points used for debiasing the objective with unlabeled datapoints? I assume that the approach would fail, because the two objectives on the unlabelled datapoints will be competing with each other.

Minor: 

Line 35: "notion safe semi-supervised learning" <- "notion of safe semi-supervised learning". There are other typos. Please, proofread carefully.

Figure 2: in the caption, it should be "top" and "bottom" instead of "left" and "right". Likewise for Figure 3.

You have missed to put some notations in the equation environment within the appendix, please proofread carefully.

limitations: I think the paper does not yield any major limitations. However, I don't see a dedicated section about limitations in the main text. I suggest the author spend some time thinking about it.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose a method of removing the bias in semi-supervised learning: debiased SSL (DeSSL). The paper provides generalization error bounds for the proposed methods based on the missing completely at random (MCAR) assumption. The authors also demonstrate the implementation of the debiased component and evaluate debiased versions of different existing SSL methods, such as the Pseudo-label method and Fixmatch, and show that debiasing can compete with classic deep SSL techniques in various settings by providing better calibrated models.
strengths_and_weaknesses: The paper has good clarity on the theory presented and has generally sound approaches and good results. The literature review is comprehensive and leads to the proposed method naturally. Technical results are not particularly complex but flow naturally and results are intuitive.

There are several aspects of the paper that can be strengthened:

The key to the proof of the consistency is the assumption that the true parameter optimizes the proposed "debiased" objective under the true distribution. A natural question is  when such an assumption is viable, and when it is not. For example, would there be situations when the true parameter approximately optimizes the objective without adjusting for bias using the labeled data?

The theory in the paper is built on the assumption of missing completely at random (MCAR), which is often considered in practice a strong condition and sometimes not realistic. Therefore it would be helpful to evaluate how much the results rely on this assumption and provide some intuition on how MCAR is used in the theory.

In problems emphasizing the overall prediction error, it could be argued that the bias-variance trade-off can be more important than the bias itself. This paper partially addresses this issue by finding the optimal $\lambda$ in minimizing the variance of the objective function. The resulting format of the minimal variance is intuitive. An alternative and more direct calculation is to find the $\lambda$ that leads to the smallest asymptotic variance of the $\hat{\theta}$, which should be easy to obtain from the $M$-estimator results.

The experiments section is comprehensive. In evaluate the influence of $\lambda$, it would be helpful to visually mark the estimated optimal $\lambda$ and examine whether it actually achieves better performance.

Minor issues:
Some definitions are missing which may prevent the reader from following the technical results:
eq (1) $n_l$
eq (2) $n_u$
eq (4) several items are not defined
questions: Since the focus of the proposed method is to reduce bias, is there a way to directly evaluate the bias reduction in addition to the results reported in the experiments?


limitations: yes
review_title: null

Meta-review: metareview: This paper provides an interesting generalized perspective on SSL techniques and proposes a debiasing technique that can be viewed as decreasing the variance of the risk estimate. The authors argue that this leads to estimators that are better than the purely supervised estimator under a rather weak assumption called MCAR - which assumes that the probability of a missing label is independent of covariate and label. 

Although the exposition and perspective are interesting, this paper is borderline for the following two main reasons:

1. A few reviewers were not convinced of the theoretical result that is supposed to show that unlabeled data strictly helps - indeed, whereas usual variance reduction techniques (e.g for optimization schemes such as SGD etc.) lead to a strict gain in terms of convergence rate, there is no clear asymptotic/high probability statement that indicates statistical gain of the corresponding estimator (which is what we really care about - not the risk estimate). The dependence of lambda_opt on theta (which changes every iteration) does not help in providing such a statement. Since this is the primary contribution of the paper, I would suggest the authors follow through with the analysis to show a gain for the actual estimator compared to the "complete case" (only using supervised data). 

On that note, the authors claimed in their rebuttal that they have added an asymptotic variance analysis in Appendix I, which indeed would have made a very valuable point - however, I could only find a copy-pasted version of Theorem 3.1. in Appendix I? Similarly, Appendix F does not seem to include the comparison between debasing using labeled and unlabeled data but instead contains the proof of Theorem 3.2. Perhaps the wrong revision was uploaded, but unfortunately, given the current version, this point is not adequately addressed.

2. If the experimental results were more extensive and conclusive, then the current theorem could have perhaps been alright as a mainly methodological contribution. However, as the authors note, extensive experiments require a lot of compute power - however, given the lack of the ultimate theorem, the methodology becomes the primary contribution and would thus require more experimental evidence as the reviewers asked for.
  
Addressing one of the above points would push the paper above the acceptance threshold which we hope the authors can pursue in their next submission. 
confidence: Certain
Decision: Reject