Venue: NeurIPS 2022 Conference

Reviews:

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: This paper studies how the prediction head in non-contrastive learning avoids trivial collapsed solutions (full collapse or dimension collapse). The empirical observations made in the paper are: (1) initializing the prediction head to identity matrix and training only the off-diagonal entries can lead to competitive performance, (2) the off-diagonal entries display a rise and fall behavior. The paper then provides theory for a simple setting to explain this phenomenon. It analyzes the dynamics of a two-layer non-linear convolutional style  neural network for a setting where data contains a strong (higher weight) and a weak feature (lower weight). Here the following can be shown: (1) without a prediction head the network will demonstrate dimensional collapse, even with batch norm (BN), (2) with a trainable prediction head + BN.+ stop-gradient can avoid such a collapse. The analysis identifies two effects that help with this, (1) substitution effect where once the stronger feature is learned in a neuron, the prediction head helps decrease the learning speed of the strong feature in other neurons and (2) acceleration effect where the strong features, via the prediction head, can further accelerate the learning of weaker features in the substituted neurons. These two steps also benefit from BN and stop-gradient.
strengths_and_weaknesses: **Strengths**
- Studies a relevant problem of understanding why non-contrastive methods do not collapse and makes concrete progress towards it. To my knowledge this is the first paper that studies this for a non-linear neural network. I believe this paper would help subsequent work on non-contrastive methods.
- The use of linear predictor + identity init + trainable off-diagonal entries is new and interesting. The empirical findings about rising and falling off-diagonals and theoretical results capturing this behavior seem non-trivial.
- The paper is well written and mostly easy to follow

**Weaknesses**

The main “weakness” in my opinion is lack of discussions about certain aspects:

- Role of non-linearity: Analyzing non-linear models is key to opening up the deep learning black-box. That said, the paper currently lacks a discussion about whether and why non-linearity is crucial for the example being studies. In particular, what would happen with a linear model in this case? Will there be dimension collapse? Will substitution and acceleration kind of phenomena not happen? Including a discussion about this could be insightful either way.
- Proof sketch: The discussion about the various phases in Section 5 is much appreciated, as it also helps understand the role of various components like trainable predictor, BN and stop-gradient. However I felt that the paper could benefit from from some more details in the proof sketch, especially to describe the substitution and acceleration effects. In particular, it might help to spell out (in terms of gradient computations say) what happens in phase III when there is no normalization and/or stop-grad.

Given these (relatively minor) concerns I am currently assigning a score of weak accept. I was unable to read the proofs in the appendix and so the above discussion will also help with increasing confidence in the results. I would be happy to raise the score if the above points are addressed in the author response, because I believe that the overall contribution of the paper is positive.
questions: - Is there a way to check for substitution + acceleration in real networks? For instance, noticing that some features are trained faster and others.
- What is the distribution of $z_p$ in Definition 3.1?
- L173: Figure 3 is missing or wrongly referenced? Figure 3 in the appendix is just a simple framework.
- L205: [84] is cited twice
- OPT is undefined
- L241: will creates -> will create
- L51: “no well-established statistical framework” [50] connects non-contrastive methods like SimSiam with a identity covariance constraint to non-linear CCA. Although not the case where there are collapsed solutions
limitations: Some limitations discussed, The contributions being theoretical, there is no immediate negative societal impact.
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 explore why BYOL-style self-supervised learners do not collapse to trivial solutions from a theoretical perspective, focusing on the prediction head component of the architecture. They use a simplified setting with a strong feature and a weak feature that compete. They define various phases of training and describe what their theoretical results suggest should happen in those phases. Some empirical results are presented to support this. 
strengths_and_weaknesses: Strengths: 
- The authors consider an important problem in a way that is simplified but feels justified. 
- Simple steps are provided to qualitatively understand what the theory reveals about the training process. 
- The previously-introduced dimensional collapse problem and reasons behind it are made conceptually clear in this work. 
- I like the organization of the paper and the intuition provided at different steps. 

Weaknesses: 
- I found the acceleration effect section relatively harder to follow. 
- The writing could use some revision. A review with an eye for grammar in particular would be helpful. 
- The strong/weak feature assumption could be better motivated.
questions: What limitations does using the strong/weak feature setup introduce?
Could you elaborate more on how batch normalization interacts with the stop-gradient to contribute to the acceleration effect?
As someone outside of deep learning theory, I would like to know more about how the assumptions posed here differ from those in other works, as well as some justification of these difference.
limitations: See questions. I am mostly interested in the limitations posed by the assumptions utilized in this work.
review_title: null

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 aims to theoretically analyze why non-contrastive self-supervised learning methods (e.g., BYOL and SimSiam) can avoid trivial solutions even without negative pairs. To this end, the authors assume a simple setting: (i) data contains only two feature vectors, (ii) the backbone encoder architecture is a single-layer CNN with a non-linear activation, and (iii) the prediction head architecture is a linear layer. Under these assumptions, this paper proves that the trainable prediction head can learn CNN to avoid trivial solutions. Furthermore, this paper provides experimental results that support the theoretical results under more standard (i.e., real-world) settings.

strengths_and_weaknesses: I think the main **strength** of this paper is the theoretical analysis of non-contrastive SSL methods. I agree that why the methods are working is less studied, so such a theoretical study is important in the field of SSL. Furthermore, the empirical observations with linear prediction heads support the validity of the theoretical assumptions well.

My main concern with this paper is the presentation quality. In general, it is hard to understand statements and their intuitions. First of all, Definition 3.1 is hard to understand:
- There is no Figure 3 about Definition 3.1 (e.g., see L173 and L213).
- Confused notations: $\mathcal{S}(X)$ and $S(X)$ (e.g., see L170, L172, L180).
- Does all $X$ in $\mathcal{D}$ share the same feature vectors $\{v_\ell\}_{\ell\in[2]}$? If so, Definition 3.1 seems to assume that the data distribution $\mathcal{D}$ has only two data points (with some noises). Is this reasonable?
- I think the constraint in L171, i.e., "all feature patches have the same direction of $v_\ell$", is also too strong.
- In L171, it would be better to use $z_p(X)=z_{p'}(X)\in\{\pm\alpha_\ell\}$ rather than $\{0,\pm\alpha_\ell\}$ because for any $p\in\mathcal{S}$, $z_p\neq 0$ by definition.
- You should describe what is $\xi_p$ first. Until p5, it is hard to know whether $\xi_p$ is a random variable, a constant vector, or something else.

And, what are the intuitions of theorems in Sections 4 and 5? I can understand what the theorems state, but it is hard to know how they can be derived. For example, how does borrowing the features in $f_1$ by increasing $E_{2,1}$ minimize the distance between $F_2$ and $G_2$? I feel that the authors should allow more space for explanations about the substitution and acceleration effects since they are key components of this paper. I also feel it would be better to provide empirical results based on the theoretical setup described in Section 3 to understand the changes in Phase I ~ IV.

To sum up, I think this paper's contributions are meaningful, but the presentation is unsatisfactory, and some results are still hard to understand. Hence, I vote for borderline rejection now, but I'm willing to increase my score after a strong rebuttal.

questions: **Q1.** Why $|E_{2,1}|$ is increasing in Phase II?

At the ends of Phase I and II (Lemma C.4 and D.8, resp.), $B=(B_{ij})=(w_i^\top v_j)$ does not change with $B_{1,1}=\Theta(1)$ and $B_{ij}=\Theta(1/\sqrt{d})$ for $(i,j)\neq(1,1)$, but $E_{2,1}$ increases from $\tilde{O}(\eta_E / \eta d)$ to $\Theta(\sqrt{\eta_E / \eta})$. It means that $F_2$ chagnes but $G_2$ does not in Phase II. This does not make sense because our objective (3.3) minimizes the distance between $F$ and $G$.

Also, the intuition of the substitution effect (L276-L279) is also hard to understand. Why does borrowing the features in $f_1$ minimize the distance between $F_2$ and $G_2$?

---

**Q2.** After Phase II, what is $w_2$?

This question is closely related to Q1. If Lemma 5.2 holds, then $F_2\approx E_{2,1} f_1$. Due to the objective (3.3), $G_2=f_2 \approx F_2$ anytime. It means that $w_2$ should be aligned with $w_1$ which is also aligned with $v_1$ by Lemma 5.1. Namely, $w_2\approx v_1$ at the end of Phase II. Is it right? If so, why does $w_2$ change from $v_1$ to $v_2$ in Phase III? I think $w_2$ will remain as $v_1$ after Phase II.

---

**Q3.** Why use Batch Normalization (BN) instead of l2 normalization?

BN is an unnecessary component in non-contrastive SSL methods, as shown in [68]. Also, BYOL and SimSiam apply l2 normalization without BN at their output layers. However, $\tilde{F}$ and $\tilde{G}$ defined in L198-200 use BN, and the objective (3.3) does not use l2 normalization. This gap may undermine this paper's motivation.

limitations: This paper does not address the limitations and potential negative societal impact.

**Limitations.** This paper uses strong assumptions on data distribution (i.e., only two feature vectors) and network architectures (i.e., 1-layer CNNs). Also, this paper does not focus on l2 normalization, but it is widely utilized in various SSL methods.

**Negative societal impact.** This paper is a theory paper. I think there is no negative impact.
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 provides original theorems to explain the convergence of self-supervised learning methods based on positive views only (i.e., BYOL-like). Under reasonable assumptions, the authors demonstrate that the predictor module prevents the appearance of dimensional collapse. Interestingly, the authors could mathematically and empirically highlight different training regimes. They also introduce the concept of weak vs. strong features to intuit the learning dynamics. 

DISCLAIMER: I have not checked the Appendix yet, for they are 40 pages long. I *may* have additional comments during the discussion as the Appendix requires quite some extra time to parse. Therefore, this review did not check the mathematical details. Besides, I cannot put high positive/negative scores for intellectual ethic reasons.

strengths_and_weaknesses: This paper is impressive for multiple reasons. 
First, the theoretical contribution is partially resolving a recent open problem in self-supervised learning: why non-contrastive methods such as BYOL or SimSiam do not collapse while they have trivial poor minima. Furthermore, the authors even describe learning dynamics, which is quite remarkable and even unique to my knowledge. 
Second, the authors did a fantastic job explaining their theoretical results, making it extraordinarily accessible for most self-supervised learning practitioners. The structure with a formal definition, the lemme, and the intuition combine rigor and pedagogy. 
Third, the authors complete their theoretical insights with experiments. While less impressive and may still be completed, they perfectly complete the papers.
Overall, this paper and [1] now provide the basics to understand the impressive and surprising results of non-contrastive methods 

The main paper's weakness also results from its strength: the level of granularity of the learning dynamics may be too precise and, therefore, more open to debate. For instance, the time complexity may overlap between the lemma (if I am not mistaken, they rely on different parameters). Therefore, the authors may have wanted to make the story a bit too much compelling: while they describe it as an iterative process, the training stage phenomenon may occur jointly. 

[1] Tian, Yuandong, Xinlei Chen, and Surya Ganguli. "Understanding self-supervised learning dynamics without contrastive pairs." International Conference on Machine Learning. PMLR, 2021.  
questions: I have many questions listed below:

A) It is a recurrent complaint about the description of BYOL-like methods: BYOL does not optimize a loss nor have a global minimum. It is a dynamic system (or a game) that has equilibria; as mentioned in the original paper, similar to GAN, BYOL has no optimum too (because of the stop gradient). As far as I could tell from the proof, the authors work at the gradient level, i.e., training updates, and not loss minimization, so the proof still holds. I would thus recommend that the authors replace the mention of loss with gradient updates or equilibria (depending on the context); especially l49 and 248.

B) As mentioned by the authors in Section 1.1., this paper does not study the convergence from an eigenvalue perspective. However, the concept of weak/strong features could be related to high/low eigenvalues. Do you have any intuition about it? From an empirical perspective, I would try to plot the eigenvalues (linear layer only), and see whether they may relate to the training phase you mention.

C) I may be missing something... but I do not understand how dotted lines may match the magnitude of non-dotted lines in Figure 2. Indeed, I would expect $E^t - (E^t)^T$ to be around zero (or around 1). I do understand that the off-diagonal is non-symmetric, but it here means that there exist a few leading values where the transpose is null (which sounds weird). Can you explain to me why the difference is so tight?

D)  In corollary 4.2, the authors demonstrate that dimensional collapses are avoided. However, do the authors have a similar results that show that without the predictor, the dimensional collapse will happen with high probability? Here, I am afraid of a potential confirmation bias.

E) In the footnote, 1 page 7, the authors mentioned that the same proof might be feasible with $\eta_E = \eta$. On a personal note, I do not think that it is possible in the BYOL setting. Indeed, BYOL requires the predictor to be close to optimal. Therefore, $\eta_E$ must be smaller than $\eta$, cf Appendix I.1 of the original BYOL paper. Note that this remark may be wrong in the SimSiam setting because of the inner optimization loop. Would it be possible to discuss this point and potentially update the paper to link it to the optimal predictor observation? 

F) In the paper, the authors explored different normalizations, showing that a non-trainable BN may be enough to avoid the collapse (even if it only returns mediocre results). It is indeed quite interesting and pushes further the limit of non-negative SSL methods. Differently in Appendix F.6 - Figure 7 of BYOL, the authors also noticed that the predictor works without normalization if and only if it is combined with weight decay. In such a case, BYOL diverged, but it is then stabilized because of the WD. In the absence of WD, the representation just diverged to infinity. More generally, the encoder WD is one of the most crucial parameters in BYOL. From your analysis, can you explain/extend this empirical (and reproducible) phenomenon?

G) It is quite an open remark. One of the strengths of a hypothesis is to be able to be predictive and thus... be contradicted. If you had infinite resources, what would be the experiment you would do (and the observation that you would get) that could refute your paper? Please, note that I am not trying to trap you here but to understand the limit cases better.

Remarks:
  - When mentioning BN, I would recommend mentioning that you are using non-trainable BN, and only the centering/normalizing components
 - The size/depth of the predictor may have a bigger/smaller impact given the task difficulty. Therefore, I am not surprised that you empirically observed little difference between method accuracy in Figure 1. Differently, did you gather some intuition regarding the predictor of inner/outer dimensions during your work? (i.e., some quantities that may depend on $|z|$ or generalization requirement)?  
 - While the mathematical notation is very well explained, it may take time to apprehend them for some people. The authors mentioned that they give an illustration in Figure 3 (Appendix). Yet, the figure barely ground the notation, and it is simply the classic non-negative SSL pipeline. I would strongly recommend that the authors create a new large figure to illustrate all the mathematical variables. In other words, the paper impact could be even more significant if they use sketches to explain the results.
 - Please add all your training hyperparameters in the Appendix for your experiments.


Nit:
  - non-contrastive methods may be too much of an approximation for BYOL-like methods. Indeed, pretext task methods would fall under this umbrella. Yet, I do not have a better naming, and BYOL-like is awkward too.
 - Put the OPT definition in the main paper instead of the footnote. I looked for it for a few minutes!
 - sigma is used both for activations and std; please use another notation for activation
 - In equation 2.1, I would add j != i in the sum of the negative 

In summary, I am quite positive about the paper. Even though I still have many questions, most of them only deal with opening directions. 
limitations: n/a
review_title: null

Meta-review: metareview: This paper proposed a theoretical explanation to the open question of why BYOL-style (non-contrastive) self-supervised learning does not collapse to trivial solutions. This paper could be an important contribution to better understanding this widely observed but poorly understood phenomenon. Although there are still some issues raised by the reviewers that are not addressed during the rebuttal, it is generally agreed that the contribution of this paper still overweigh the issues. Therefore, I decide to accept this paper, but urge the authors to fully address the reviewers' comments in the final revision (e.g. missing Fig.3, clarification of Def. 3.1, etc.).
confidence: Certain
Decision: Accept