Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper theoretically analyse how self-supervised pretraining can achieve better performance than full supervised training in a synthetic setting, with fixed data, a fixed architecture, and a fixed self-supervised training scheme. More precisely, it looks at how, when a precise data generating process is assumed and a precise architecture is used, combining a form of self-supervised learning with supervised learning achieves zero test loss, while supervised learning achieves a non zero test loss.

strength_and_weaknesses: **Strengths:**
- The paper is reasonably well-written.
- Most of the hypothesis are clearly presented and the derivations look reasonable (even though I did not go through the full derivations in appendix).
- While the data and architecture setups are synthetic, the paper analyses the full gradient descent dynamic.

**Weaknesses:**
- Starting from the title, the claims made by the paper are very strong compared to the restrictive setting presented. This paper does not answer the question asked in the title: 'How does self-supervised learning work?'. It only shows that, in a restrictive (and somehow convoluted, more on that below) setting, one can design a self-supervised learning method, which has only few similarities with existing competitive self-supervised methods, that succeeds in learning more efficiently than a supervised counterpart. I think the title, abstract, and conclusion should be significantly reworked to reflect the restrictions imposed on the setup.
- The setting presented is very restrictive, and some of the restrictions/design choices diverge quite significantly with usual practical use cases. Without some proper motivations and explanations, it's hard to understand how generalizable the theoretical results provided by the paper are. Some examples of such restrictions/departure from practice:
  - The paper uses a ReLU^3 activation. Most common activation function are linear when pre-activations grow big, and either saturate or decrease linearily when preactivations get low. How crucial is the use of this specific activation function?
  - The generation process of the data is extremely simple, far from any practical setup.
  - SSL methods often rely on 1 pretext task to build a representation, then learn a linear predictor on top of the representation. Here, the paper relies on K pretext tasks to build K features, then aggregate the features linearly. Can we relate this setting to the usual SSL setting?
  - The architecture that is used is very ad-hoc, with features operating directly on the two separated parts of the data, and with only the input layer being trainable for the pretraining phase. The results obtained might be extremely dependent on this ad-hoc architecture. Would adding trainable features on the second layer break the analysis? Would removing the hard split in both data and architecture break the analysis?
  While I fully understand that studying setups closer to practically reasonable setups is much harder and might render the analysis intractable, I still believe that the current analysis does not support the claims made.
- While the paper aims to tackle self-supervised learning, the goal that is used to train the self-supervised model is a mix of pretext goal and supervised goal. This kind of mixing is usually considered semi-supervised more than self-supervised. Framing the paper in the context of semi-supervised learning might be a better fit.
- There are a couple of hard coded numerical values in condition 4.1. that could probably be replaced by constants bounded by some less ad-hoc thresholds. My personal view would be that this would make the analysis more readable and general, but that is mostly a minor point.

----
Post rebuttal comments:
I thank the authors for the efforts they put in the rebuttal. Many of my comments have been addressed and I am therefore raising my rating from 3 to 5. I think all the changes made are net positives. The reason I am not raising my rating further is that I still have my doubts on the practical insights that can be drawn from this analysis, which I already mentioned in my initial review.

A couple of additional remarks/questions:
- You mentioned in the rebuttal that working with K = 1 would recover a more standard SSL setup. If I am understanding things properly, the case K = 1 means that you are learning a single feature (the logits of a single pseudo-label predictor), then probing on this single feature (and thus learning a single weight a_0). I would still not consider this to be a standard SSL setup, where you would rather remove the final layer of your self-supervised network (here the untrained second layer), and replace it with a linear probe, working on the actual 'self-supervised' features. Am I misunderstanding something?
- I thank the authors for mentioning the fact that the analysis also worked with n_l = 0 which is something I missed in my first read. I would argue in favor of adding an additional comment mentionning that the case n_l = 0 corresponds to usual self-supervised training, whille n_l > 0 corresponds to a semi-supervised training regime (which only adds some generality to the paper).

clarity,_quality,_novelty_and_reproducibility: The paper is reasonably clear and well-written. The theoretical result is most probably novel, and the experiments most probably reproducible. While the paper is clear, I also believe that it generalizes too broadly its contributions, making claims about self-supervised learning in general, when the results presented are specialized to one specific data generation process, one specific architecture and one specific pretraining method (which I would consider a semi-supervised learning method rather than a self-supervised learning method).
summary_of_the_review: The paper at hand provides a clear and probably correct theoretical analysis of a synthetic self(/semi)-supervised learning setup. Based on this analysis, the paper makes broad claims about self-supervised learning. I believe those claims are too broad, and should be properly tamed down to account for the narrowness of the setting considered.
Aside from this claim problem, I am not sure the theoretical results presented here can translate into practical insights, given how far the setup considered is from practical setups of interests.

Given those points, I don't recommend accepting the paper for now, but I am willing to discuss my current rating with both authors and other reviewers.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper theoretically studies optimization and generalization of self-supervised learning with pseudo labelers setting. The pseudo label and true label are correlated. It considers linear data setting (signal/noise ratio = $O(d^{0.01})$) and two-layer neural networks with ReLU^3 activation function. Comparing two settings (a) train networks on constant labeled data and $O(d)$ pseudo-labeled data (b) train on constant labeled data only, the setting (a) will have $o(1)$ test loss while setting (b) will have $\Theta(1)$ test loss. The proof idea is to manipulate the gradient and try to give a bound on the signal growth rate and noise growth rate. 
strength_and_weaknesses: Strength:
1. In my understanding, the key idea is that pseudo labels with a positive correlation with true labels can provide more gradient projection on the effective directions. When the pseudo-label data number is much larger than the true-label data, there is a generalization gap between settings (a) and (b). The main results in Section 4 are non-trivial. 
2. The paper has clear motivation and good writing. The proof sketch section is comprehensive and insightful. 

Weakness:

My major concern is how to generate pseudo-labels in Condition 4.1. Based on my rough calculation, it needs $\Theta(d)$ true labeled data to train a non-trivial teacher such that test accuracy can be larger than ½ with a constant margin with high probability (correct me if I am wrong). Then, here is an unfair comparison for setting (b) which only use constant true labels. If both setting (a) and (b) has $\Theta(d)$ true labeled data, I think the guaranteed generalization gap may be small or even may vanish. Let me know how to fix it or I may misunderstand here. 

Here are other concerns:
1. The paper considers linear data and it is acceptable. However, it is worth considering non-linear data settings such as XOR or low-degree polynomial in [1,2,3]. 
2. It seems the paper is considering neural networks (NN) rather than convolutional neural networks (CNN). 
3. I understand the authors need ReLU^3 in the proof so that the gradient has a better formulation and property. However, it is a good try to consider the ReLU activation function by using some feature purification tricks (Allen-Zhu & Li (2020a)). 
4. How large is $K$ in Section 3.4? Is it necessary to have a $K$ here rather than using $K=1$?

[1] Shi, Zhenmei, Junyi Wei, and Yingyu Liang. "A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features." International Conference on Learning Representations. 2021.

[2] Frei, Spencer, Niladri S. Chatterji, and Peter L. Bartlett. "Random feature amplification: Feature learning and generalization in neural networks." arXiv preprint arXiv:2202.07626 (2022).

[3] Damian, Alexandru, Jason Lee, and Mahdi Soltanolkotabi. "Neural networks can learn representations with gradient descent." Conference on Learning Theory. PMLR, 2022.

clarity,_quality,_novelty_and_reproducibility: Clarity: The paper has good clarification and motivation. 

Quality: I checked the most proof in the appendix. They look good to me. 

Novelty: The paper has novelty in studying representation learning in self-supervised learning. 

Reproducibility: I believe the experiments part can be reproduced. 

summary_of_the_review: The paper is well-writing and has a non-trivial conclusion. However, I have a major concern about unfair comparison in settings (a) and (b). I may accept the paper if the author can fix my concern, otherwise, I tend to reject it.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This is a theoretical paper that aims to prove the benefits of pretext-based self-supervised pretraining before supervised probing. To do so they consider a toy data generative process where the inputs are a concatenation of label-dependent features  (a linear function of the label) and some random features (Gaussian noise such that noise strength is larger signal). They then prove that an overparametrized 2-layer CNN that was pretrained will achieve near-zero downstream test error if the pretraining set is large, while a fully supervised model cannot if the number of labeled data because it will memorize the noise.

strength_and_weaknesses: **UPDATE**: I’m updating my score 5->6 given that the authors addressed some of my initial concerns. The main remaining issues with this theoretical paper is that there are no actionable insights and that the considered setting is far from practice.
- - -

Strength:
- **theory is non-trivial** 
- **proof sketch is clear and useful**
- **good review of related work**

Weakness
- (addressed in rebuttal) **Some lack of clarity in SSL nomenclature** multiple times when reading the paper the authors used terms that indicate that one setting was considered when actually it was not. For example:
    - linear probing vs fine-tuning. You often say that the model is "fine-tuned on small amount of labeled data", which suggests that you are finetuning all the weights of your model (eg abstract or figure 2). In other places, you seem to suggest that you only train a linear probe but freeze the pretrained model (eg end of section 3.1). From section 3.2 it seems that you indeed only train a linear probe with weights $a_k$
    - you use the term "pretext task" which in SSL typically means some task that is not directly related to the downstream task (eg predicting frames in a video, predicting the rotation of an image, predicting the order after a jigsaw transformation ...). Yet the paper is really about pseudo labeling in the sense that the pseudo labels are noisy labels of the downstream tasks
   - The model seems to be a 2 layer neural network instead of a CNN? Or is that a CNN with stride $d$?
- (addressed in rebuttal) **Not about self-supervised learning** as I just mentioned the paper is about pretraining to fit pseudo labels that are noisy versions of the downstream labels. This is not about self-supervised learning but semi-supervised learning (the pseudolabeler has to first be trained with some labels). To be clear there is nothing wrong with studying pseudo-labeling in semi-supervised learning but I think that the paper (especially the title) is misleading because of that.
- **toy assumptions** the setting is very toy (2-layer CNN, toy data generating process, uncommon SSL setting ...). That being said I do think that the high-level idea might generalize to more realistic settings.
- (addressed in rebuttal) **title and abstract are too grandiose** the title and abstract make it seem that the authors do much more than they actually prove. Authors need to be clear how constraint and limited the considered setting is.

**Question**
- **Is it really about representation learning?** the title and abstract seem to put much emphasis on "a representation learning perspective" but wouldn't a supervised learning model that is jointly trained on the pseudo labels and the real labels have the same performance gains? (with proper scheduling of the ratio of pseudo and actual labels"
clarity,_quality,_novelty_and_reproducibility: **Clarity** the paper has some clarity issues due to some choices of names (fine-tuning / self-supervised learning / CNN ...) as discussed above. The rest is clear.

**Novelty**: the main theorem seems novel

**Quality**: I have not checked the proofs in details, but the sketch proof and end results seems reasonable.
summary_of_the_review: Assuming that the authors modify (or explain why not) their use of the terms "fine-tuning" and "self-supervised learning" I think that it could be of interest to some theoretical researchers. I am nevertheless not sure whether ICLR is the right venue to reach such researchers.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper provides theoretical understanding to certain self-supervised learning approaches based on pre-training and fine-tuning.
The reviewers all appreciated the impressive theoretical results and clarity of the paper.
The reviewers also agreed the paper's insights may not have immediate practical relevance. 
justification_for_why_not_higher_score: Without clear practical actionable insights, the paper as presented might not be relevant to the wider ML community.
justification_for_why_not_lower_score: The theoretical results are impressive and the paper appears worthy of publication.
Decision: Accept: poster