Can semi-supervised learning use all the data effectively? A lower bound perspective

Summary

this paper investigates whether improvements in the rates of sample complexities are possible for semi-supervised learning compared with supervised learning and unsupervised learning (up to a change in sign) for the specific case of a classification problem where each class is a symmetrical Gaussian. it is found that no improvement in the rate can be made, but it is possible to improve the constants.

Strengths

1 I think it is a very relevant question to investigate whether SSL can improve performance in theory over sup and unsup, and this can have a great impact 2 I like the deep theoretical analysis where minimax upper and lower bounds are derived 3 the theory is complemented by some experiments to validate the theoretical findings

Weaknesses

4 the work misses a very relevant recent survey concerning this question in general: Mey, A., & Loog, M. (2019). Improvability through semi-supervised learning: A survey of theoretical results. arXiv preprint arXiv:1908.09574.

Questions

5 for Algorithm 3, how does it make sense that $t$ is an input? should this not be learned also? similarly, I see the same problem with Theorem 6. This would imply the algorithm has knowledge of the distribution? Or is there a universal (distribution independent) t? 6 Similarly, in the experiments, these parameters seem to be tuned on a holdout labeled set. Why is that appropiate?

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

none

Summary

The paper presents a detailed analysis of semi-supervised learning (SSL) algorithms. Specifically, the authors establish lower bounds for 2-Gaussian mixture model distributions, revealing that no SSL algorithm can improve the sample complexities of optimal supervised or unsupervised learning. However, SSL can improve their error rates by a constant factor. The authors propose an algorithm that achieves lower error than both supervised and unsupervised learning, and conduct experiments on synthetic and real-world data.

Strengths

- The paper investigates the learning capacity of SSL algorithms and theoretically establishes a lower bound, which is an inherently interesting and meaningful endeavor. - The paper is well-organized and easy to comprehend. The authors provide a clear overview of the problem and their proposed solution.

Weaknesses

- Some details about the method and theory part should be further elaborated on, see Questions below.

Questions

- The paper only considers Gaussian mixture distributions. Could more complex distributions be considered in future work to accommodate more real-world problems? - The paper only considers the worst-case scenario. Is it possible to consider milder cases? For instance, could a data-dependent bound that relates to problem difficulty be derived? - The statement on line 103 seems to be erroneous: when using the UL algorithm, why can't labeled data be considered as unlabeled data, so that UL can use $n_l + n_u$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- As mentioned in the Questions section, the authors should provide further clarification on the method and theory parts.

Summary

This paper analyzes the effect of SSL methods to improve the error bound. The results suggest that SSL cannot improve over the statistical rates of both SL and UL at the same time, but it is possible to improve the errors by a constant factor. Simple experiments on synthetic and small-scale real-world data validate the theoretical findings.

Strengths

- This paper studies an interesting and important problem: whether semi-supervised learning can effectively use all the data. - A detailed theoretical study is provided on the 2-GMM distribution, which sheds light on this problem. Modification: - Though simple, the proposed SSL switching algorithm is interesting and insightful.

Weaknesses

- The theoretical analysis is based on GMM, which introduces a strong assumption about the data distribution. This limits the scope of application of the theoretical analysis. - The proposed SSL switching algorithm introduces an extra hyperparameter s/t, and it seems that the algorithm is sensitive to the choice of the hyperparameter. Though it can be chosen by holdout labeled validation set, labeled data are relatively rare in the SSL setting. Is it possible to estimate the value of the hyperparameters?

Questions

Please address the concerns in the weaknesses part.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The main limitation of this paper is that the analyses mainly focus on GMMs, which limits the scope of application.

Summary

The paper provides a tight lower bound for semi-supervised learning for the 2GMM model. It compares the minimax rate with supervised and unsupervised learning. The authors also provide supporting experiments on real-world and synthetic datasets."

Strengths

1. The paper is very well-written. The authors have effectively communicated their ideas, making it easy for readers to follow and understand the research. 2. The results presented in the paper go beyond existing prior work (when s > 0). 3. The authors have conducted experiments to support their theoretical analysis. This empirical validation strengthens the credibility of their findings and enhances the practical relevance of the proposed approach.

Weaknesses

The paper relies on strong assumptions regarding the 2GMM and linear model. This might limit the generalizability of the proposed method to other scenarios or data distributions.

Questions

1. Line 65: There seems to be a typographical error in the notation "A(D_l, D_l)." Please clarify this notation. 2. Line 121: I assume that 'u' represents a function mapping the number of labeled data points to the corresponding number of unlabeled data points. Can you please confirm this understanding?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors have adequately addressed the limitations.