Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: In general, it is not clear, at least theoretically, how, and when unsupervised data helps to generalization of nonlinear methods. In the literature there are important and elegant works exists that analyses the impact of usage of unlabelled data during training, however, (if I am not mistaken) all these analyses have been done for linear models. Authors analyse and shed some light to several aspects of using unlabelled data during training. They formalize their analyses based on expansion assumption. I think it can be restated as the similarity between members of the same classes is bounded by below. Intuitively such an assumption is quite reasonable. The authors use the term input consistency for defining a broad set of methods e.g. transformations of the image should be similar to each other, and they also couple their analysis using the expansion assumption with input consistency. In their view input consistency brings a local stability/generalization and expansion property brings global stability/generalization. This is again quite reasonable way of thinking because intuitively just forcing an input point to be close to transformed version of itself sounds a weak property for a good generalization performance. The authors supply quite a bit of theoretical novel material to support their intuition and analysis. 
Furthermore, they present some supportive experiments albeit not an extensive one. 

Strong and weak points:
a)	Strong points: Please see above.
b)	The paper is quite dense, and the reader needs to be familiar with learning theory concepts. I wonder if authors would have focused on only one aspect of the problem which they are dealing. In the current version semi-supervised learning methods, unsupervised domain adaptation and unsupervised learning are covered. Every of them is a field by itself. I understand the desire of a unified and generic framework however I can imagine that there is a risk of diluting the message.
c)	Another understandably weak point is the experiments. I personally think that conducting an experimental study in the scope of this quite challenging however it will be nice see expansion property on a real dataset.
Recommendation:
Overall, I would like this paper to get published because (if I am not mistaken) paper develops an initial understanding extremely important field e.g. self-training/self-supervised learning. 

Supporting arguments:
a)	I found the assumptions paper quite intuitive and necessary. Authors also supply population level guarantees for unsupervised learning. Moreover, they extend their work finite-sample guarantees by using margin concept and Lipschitz continuity. They extend their work to domain adaptation and semi-supervised learning. The novel material in the paper is extensive.


Questions:
a)	As I mentioned before I would like to expansion property on some real-world datasets. For example, can authors present some evidence of expansion property for a chosen deep neural network on a dataset (or multiple datasets) and quantify the expansion property based on some metric.  
Improvement Suggestions:
a)	The paper is quite dense, and the reader needs to be familiar with learning theory concepts. I would recommend authors to decrease density of the paper and may be move some parts to the supplementary material.

Although I am quite positive about paper, I would like to see the discussion and comments. I am open to change my review to any direction if some new evidence/discussion/published work supplied.




review_title: Strong theoretical insights for a class of important but hard problems

final_score: rating: 7: Good paper, accept
review_content: This work provides a unified framework to analyze the self-training, semi-supervised algorithms. The key assumptions are 1) the “expansion” assumption which characterizes the low-probability data subset must expand to a neighborhood with large probability; and 2) the neighborhoods of samples from different classes have small overlap.  Then the authors established the upper bound of the prediction error on the population when minimizing the self-training and input-consistency based loss on the population. They also extend their results to a finite-sample setting and semi-supervised setting as well.  

merits
1) In the theoretical aspect, the established results can explain the success of self-training training and is of high quality. 

2) Moreover, this work is well written and easy to follow. 

Questions
1) Though this work provides good theoretical results, it seems that the results do not bring any practical insights to further improve the analyzed algorithms. E.g. the population-based loss in Eq. (3.4) is not used in practice, since the loss is on expectation and is relatively complex. Actually, when the network is large, then sampling data to estimate E_p[1(G(x)=y)] and R_B(G) is of the high cost. 

2) About the assumption that neighborhoods of samples from different classes have a small overlap, it also may be restrictive. For example, in imagenet, there are many images that contain several objects actually. This means that the overlap between samples from different classes may be not small. 

3) Finally, the key expansion constant c is not investigated on the toy and real datasets. What is the magnitude of c? this is very important since the upper bound will be large if (c/(c-1)) is hugh.

review_title: Comments 

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: **Summary:**
This paper provides a theoretical analysis of self-training for semi-supervised learning, unsupervised domain adaptation, and unsupervised learning. The authors propose a novel assumption that they dub _expansion_ to effect this analysis. The expansion assumption requires that the neighborhood of small sets have a class conditional distribution that is large. Under this assumption, the authors show population results for an algorithm that performs self-training under the objective that enforces input consistency. 
They also provide finite sample guarantees based on off-the-shelf generalization bounds for unsupervised learning. 

**+ves**
+ The expansion property seems neat, and seems like a natural quantity for making progress in understanding self-training theoretically 
+ The authors also provide support for this empirically in Section D. 
+ The paper is very well written. In particular, the summary of the theoretical results in the main paper is very well done. I also appreciated the proof intuition for Theorem 4.3's proof

**Concerns/Comments:**
- I think it would be helpful for the reader to have a brief proof sketch of the theorems immediately after the statement. The results are already summarized (well!) informally in the introduction. 
- It is unclear to me how realistic Assumption 4.1 is. 

**Questions for the Authors:**
- Can you expand on the optimization objective of (4.1)? How may one implement this in practice? Or, how is this analogous to what is being done in practice? 
- Can you comment on the realism of Assumption 4.1? Is it possible to verify this on toy examples as you have done with the assumptions in Section 3? 
- Can you comment on obtaining a finite sample version of Theorem 4.3? 

review_title: A strong submission that provides theory for self-training

final_score: rating: 7: Good paper, accept
review_content: Summary of the paper: The paper gives a theoretical justification of self-training. It proposes a new notion of "expansion" - the amount of data distribution in the neighbor of an example. Here the neighbor means adding perturbations to the example, or augmentations of the example. When the label distribution satisfies nice expansion properties and that classes are properly separated according to the neighbors, the paper proves distributional guarantees of self-training. Combining with generalization bounds of DNNs, the paper also derives finite sample bounds for DNNs. The paper also verifies the expansion assumption via experiments using a GAN.

Review: Overall, the paper is written nicely and gives a novel perspective on self-training. Several questions:
	1) It is a bit strange that semi-supervised learning requires a stronger assumption on expansion than unsupervised learning. Is it possible to use the unsupervised method and then somehow align it with the semi-supervised labels?
	2) The assumptions depends heavily on $\mathcal{B}$ - if $\mathcal{B}$ is too large than we have inconsistency, if it is too small than we lose expansion. How will the results change if $\mathcal{B}$ is of other forms (e.g., coming from a model)?

I feel that the paper gives an interesting notion to consider for self-training and the statements are rigorous. I would recommend acceptance.
review_title: Nice paper

Meta-review: The paper looks into theoretical analysis of self-training beyond the existing linear case and considers deep networks under additional assumption on data. namely: expansion and minimal overlap in the neighborhood of examples in different classes. The results shed some light on self-training algorithms that use input consistency regularizers.
Although the assumptions are very hard to check for all input distributions, the authors make an attempt by considering output of BigGAN generator. In summary, the paper is a great first step in understanding self-training for deep networks.

The paper is overall clearly written. please add the explanation of  Assumption 4.1 as requested by Reviewer 4.

Pros: - given the extensive use of self-training the paper is of great importance to the community
-extending the analysis of self-training to deep networks
-the paper is clearly written and easy to follow

cons: -the assumptions are very hard to validate on all datasets

Decision: Accept (Oral)