Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: This paper aimed to understand the self-supervised learning algorithm under a teacher-student network setting. The authors argued that the gradient are specified by a covariance operator, that can amplify extracting the intrinsic features that are invariant to the data augmentation.

I have several concerns on this paper, mainly on the over-simplified setting, unrealistic assumption, and inaccurate claim. Also, the presentation is weird.

The detailed comments:
1. I feel most of the theorem are just simple calculus. It’s inappropriate to claim such calculation results as theorem. At least one theorem should contain some information on the property of the terms of interest.
2. As far as I know, there’s no existing empirical work used the ell_2 loss on the feature as the dissimilarity, though when the features have norm 1 (which cannot simply hold in practice) there are some connections between the ell_2 loss and inner product. I personally would argue that, the authors should first make an empirical justification on this simplification, say such dissimilarity measure can empirically work. I don’t think this is a valid simplification. The authors may argue that methods like simCLR have normalization before computing pairwise similarity, but this will dramatically influence the gradient update. Maybe the remaining conclusion still holds, but at least the authors should include such part.
3. I would like to say that the assumption for Theorem 3, i.e. the gradient of the negative samples are identical, are too strong and unrealistic. Definitely this will not happen, even though the negative samples are from the same distribution, there should be some variance. I cannot accept such assumption. Even take H=1 is better than this assumption.
4. Beta is used without any introduction.
5. As the authors say, the covariance operator are changing over time, it’s hard to claim that this covariance operator let the parameter align with some specific direction that is good to learn a good representation. Take the NTK limit may be one possible way to get some more interested result, however, the authors haven’t done that.
6. And I would argue that, with only analysis on gradient, it’s rather hard to make some strong claim. There are several existing work on homogenous neural network that characterize the optimization and solution with e.g. separable data, which is much more convincing.
7. I feel the description starting from Section 4 on two groups of latent variables are so intuitive and also unrealistic. How can we identify such groups of latent variables and how can we make sure in practice we don’t perturb the class/sample-specific latent? On the other hand, what if we perturb the class/sample-specific latent? Imagine we have a Gaussian mixture of two isotropic components, if we augment the data with the isotropic Gaussian, can we make an informative projection onto low dimension with self-supervised learning? I think the current intuitive and unrealistic setting restricted the potential application in practice.
8. What’s the definition of bar{K}_l(z_0) as the input of this term should be x? What’s the form of the term after integrated out z^\prime? I feel there are so many ambiguities here and I’m afraid I cannot accept such claim.
9. I think the arguments in Section 4.1 need to be justified more formally, if this is a `theoretical’ paper. I wonder what does the author want to say in Section 4.1, the importance of non-linear activation? 
10. In Section 4.2, why constrained to 1 output? I would like to ask, as in the derivation in Section 3, there should be no straightforward barrier on considering this more general case?
11. In Theorem 4, is the A matrix fixed during the dynamics? I’m quite skeptical on that, as the w in the definition of u are changed over time, which can influence the indicator. Also, why we have the covariance is equal to zero? Is that the normal case? Also, there are so many ambiguities here, see 9, can the authors give all the formal description of the neural network we considered, the input data distribution, etc. in a clear way? To be honest, I cannot understand the proof of Theorem 4 as well, due to these ambiguities.
12. For the description in the last of Page 7, I totally get confused. What does the authors want to say on that? Even the parameter converge to some point, we cannot say during the optimization it keeps the indicator 1? Can the authors stop using such ambiguous description and give some formal description and claim?
13. What’s the meaning of considering such HLTM? Can it represent the general case of learning? I need to say the authors does not convince me that such setting is general and it’s necessary to consider the multi-layer network with such setting. I would like to say, it’s better first considering the fully-connect network rather than considering the network with local receptive field.
14. I would like to say the organization of Section 4.3 is really weird. Can the authors give a formal description in the neural network and generative model in Section 4.3, even in the appendix with simpler but clear model? I don’t even know the data generating process of x given z, thus does not the meaning of given a sample x how to resampling z^\prime. As the notation are only described in Table 1, I cannot get the meaning of each term in the theorem. Give some description on each of term with a formalized mathematical description on the generative model and network, please.
15. Also, I does not feel the theorem in Section 4.3 give some strong arguments. What we really care in the self-supervised learning is the quality of representation, the sample complexity, the convergence analysis, none of them have been addressed by the author formally. Instead, I feel Theorem 6 presented here is not of particular interest. Also, the discussion is quite intuitive.
16. What’s the sym subscript in Equation 10? Please introduce the notation before used it. Also, what’s the term deltaW_l^{BN} in Equation 12? Please be self-contained.
17. The observation of Theorem 7 can be interesting, however, in practice, what we really do during BN is the latter one, i.e. x - x.mean().detach()? And in fact, the mean we subtract in BN is a moving average statistics. I feel it can explain something, but not why BYOL works. The claim that such observation give an analysis of why BYOL work is not accurate. In the contrast, I think it even predict that BYOL will not work or at least need to be fixed.
18. Overall, what the authors have proposed are better understood as some intuition or observation, not some rigorous theory.

To sum up, I feel the presentation is weird. The settings are over-simplified and the authors even didn’t introduce the setting with formal description. The assumption can be too strong while some explanations are too intuitive. The authors want to argue several points, however, none of them are strong enough and can be claimed as 'theorem' (I feel they are only 'observations'). Meanwhile, I feel the authors include such different points in the main text with the expense of readability.

If this is an empirical paper introduced some observation on the self-supervised learning with detailed ablation study and some kinds of theoretical characterization, I’m happy to accept this paper. However, as I don’t feel the authors provide either strong theoretical results or detailed ablation study, meanwhile, the presentation is totally a disaster, I think this paper is not suitable for publishing right now.
review_title: The observations can be interesting, but they are not rigorous theoretical results, while the presentation is disastrous.

final_score: rating: 7: Good paper, accept
review_content: Strengths:
	This paper tried to analyze the “Black-box” of the contrastive learning by inspecting the weight update during contrastive learning. The analysis and conclusion seem promising.
	This paper made a theoretically analysis on BYOL and conducted a variety of ablation studies to study the impacts of BN layer and predictor in BYOL. And some interesting experimental results and conclusions are presented, which sheds light on the further explorations on self-supervised learning.
Weakness:
While I still have some questions:
	In [1], it has been proved that BYOL can work without BN in predictor, which seems contradictory the conclusion given in this paper. I recommend the author to compare with this conclusion.
	In Table 5, it seems that reinitializing the predictor will improve the performance a bit. I wonder if the improvements will gradually decrease or even vanish for longer training epochs.

[1] BYOL works even without batch statistics. 
review_title: This paper presented a novel theoretical framework to analyze some state-of-the-art self-supervised learning methods.  The authors proved that the weights are updated by a covariance operator that amplifies initial random selectivities that vary across data samples during training and explain how the good representations can be learned in this way. And the authors also analyze the reason why BYOL can work with no negative samples.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes a novel theoretical framework to understand self-supervised learning
methods that employ dual pairs of deep ReLU networks. The finding is interesting and novel. The experiments support the conclusion. However, there are several issues.

The paper should explain the motivation to choose simCLR for analysis.
The paper defines the covariance operator from contrast loss and the paper declare that the theory is suitable for deep ReLU networks with dual pairs. How to define the covariance operator for other kinds of loss function of deep ReLU networks with dual pairs, such as triplet loss.
The experiment setting should be listed. Such as the learning rate, the training time and the date augmentation used in the experiments. The paper also needs experiments about the magnitude of the covariance operator and the training time.
The paper analysis the activation gap and the weights of different layer for HLTM. The paper needs experiments about the activation gap grows over time and the weight of the top layer and lower layer change over time.

review_title: The paper proposes a theoretical framework to understand self-supervised learning methods that employ dual pairs of deep ReLU networks. The finding is interesting and novel. More experiments are needed.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary: This paper does theoretical analysis about self supervised learning (SSL), esp. those methods using contrastive learning. It zooms into one-layer and two-layer networks and proves contrastive learning can converge to weights corresponding to largest eigenvector of a covariance matrix. Experiments on synthetic and real datasets are consistent with theoretical conclusions.

Reasons for score: 
The covariance operator sheds light to the black-box learning process of contrastive learning. Approximating the data distribution with a hierarchical latent tree model is an interesting technique. This work may inspire practical tools to improve SSL. 

Issues:
1. My major concern is the analysis about BYOL. The authors of BYOL disagree with the conclusion in this paper that BatchNorm provides implicit contrastive objective for BYOL, in a newly released paper "BYOL works even without batch statistics". I'd ask the authors, does this invalidate your analysis about BYOL? Or does the GroupNorm + weight standardization also provide implicit contrastive objective, similar as BN? 
2. To what degree the validity of the theoretical analysis depends on the type of the loss? Say if I change the InfoNCE loss to some other loss, will that invalidate the whole analysis?
3. A typo in page 4: "we setup the following..." => "we set up the following..."


review_title: A very solid work

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper provided in-depth theoretical analysis of self-supervised learning, focusing on two network structures (SimCLR, BYOL). They proved that a covariance operator plays an important role in the SGD learning of self-supervised algorithms. Simulation experiments were provided to justify the theoretical findings. The paper is well written, with rigorous mathematical derivations.

Here are a few comments on the technical details:
1) In Theorem 3 there is an assumption that the derivative of L with respect to rk- is a constant. Is this a reasonable assumption in real situations? Can we see how this assumption is justified (or violated) in real data? 

2) Below equation (37) in the appendix, the above assumption becomes derivative of L with respect to rk-^2, and H is replaced with n in the constant. It seems that there is some discrepancy with the statement of Theorem 3, and some explanation may be helpful.

3) In the first paragraph of Section 4, it is stated that "all nuisance latents z' are integrated out in K(z_0)". This statement seems to be a little vague to me. More rigorous definitions and derivations may be needed here to support the claim.

4) A related follow-up question is, how would the augmentation distribution impact the analysis? What would be a good augmentation transform?
review_title: Interesting theoretical analysis of self-supervised learning

Meta-review: This paper presents new analysis for self-supervised learning. All reviewers are positive about some new perspectives of the analysis. However, some serious concerns have been raised about the rigorousness and the presentation clarity. The paper would be significantly improved, if the authors could address the concerns.
Decision: Reject