Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: __post-rebuttal__
The responses have been persuasive enough. I am raising my score, with an expectation that the authors will make additional textual revisions based on their responses to make it clear in the abstract and introduction that (1) authors only consider the "reconstruction-based" SSL, instead of SSL in general, and (2) address the discrepancy between the practice and the proposed framework. (I thought asking questions could make the authors revise the manuscript, but unfortunately that did not happen.)

__summary of the paper__
The paper provides a mathematical framework to theoretically understand and quantify the benefit of self-supervision on the downstream tasks. The considered pipeline (which seems to be based on Arora et al. (2019)) is as follows. $X_1$ is the input variable, $X_2$ is the "target" random variable, and $Y$ is the label for the downstream task. Then, the learner solves two problems sequentially: (1) _pretext task:_ The learner looks for a representation $\psi: \mathcal{X}_1 \to \mathcal{X}_2$ such that $\psi(X_1) \approx X_2$. (2) _downstream task:_: The learner looks for a matrix $W$ such that $W^\top \psi(X_1) \approx Y$. Based on this framework, the paper gives performance guarantees on the downstream task under various assumptions, e.g. unbounded sample for the pretext task or Gaussianity. The key underlying mechanism is what authors call the _approximate conditional independence._

__Strengths__
(1) The theoretical analyses appearing in the paper are concrete.
(2) The manuscript overall is very easy to understand and comprehensive.

__Weakness__
The biggest concern that I have is that the provided framework does not seem to incorporate most existing self-supervised learning paradigms. Although it is somewhat explicitly stated already in the paper that the discussion is confined to the **"reconstruction-based self-supervised learning"** instead of any self-supervised learning task, I still am not really sure if the provided framework covers those pretext tasks. Actually, the paper exemplifies the task of "inpainting" (Pathak et al. 2016) to motivate the theoretical framework. Here, $X_2$ is the cropped part of an image, $X_1$ is the remaining part, and $Y$ is the corresponding label. I am happy with how the framework handles the pretext task, but not with how it handles the downstream task. According to the framework, the learner aims to predict the label from the "remainder of a cropped image," instead of the full image. While one can always imagine such an algorithm, I am not sure if this is what is typically done in self-supervision algorithms. The same may hold for image colorization tasks (which also motivates the framework). Actually, it seems to me that such discrepancy takes place because the paper did not want to step away too far from Arora et al. (2019), which is actually quite similar in spirit except that Arora et al. (2019) did not spell out "approximate conditional independence."

Also, I am not sure if the framework is extendable enough to take care of other (perhaps more popular and well-performing) categories of self-supervision, such as rotation/jigsaw-based methods. If not, I think many statements and expressions appearing in the paper should be significantly down-toned, including the title of the paper.

__nitpicks__
(1) Although not absolutely mandatory, discussing the relationship to Bansal et al. (2020) may help the future readers.
(2) In section 2, right before the paragraph **(Partial) covariance matrix,** the sentence "We also note that $\mathbb{E}[Y|X] = \min_{f}\mathbb{E}[\|Y-f(X)\|^2]$ is the best predictor of $Y$ given $X$" does not make too much sense. Perhaps the authors meant argmin?
(3) Is $X$ the random variable, or can it be a vector as well?
(4) In section 2.2., I am not sure why the authors use the Frobenius norm in the definition of  $\psi$. Shouldn't it be simply $\ell_2$ norm, as $X_2$ seems to be a vector? Or are the authors already assuming a data matrix?


[Bansal et al. 2020] For self-supervised learning, Rationality implies generalization, provably, arXiv 2020.
review_title: Is the framework really about self-supervision?

final_score: rating: 6: Marginally above acceptance threshold
review_content: The estimation error refers to the distance between the best function in some function class H, and the optimal estimator computed based on the given data. The definition at the end of page 3 may have some typos since f^* is the universal optimal predictor.
Lemma 3.5 seems trivial since \psi comes from the universal function class; it is not surprised to get the zero approximation error.
Some CI results may inspire this utilized ACI; however, the provided generalization bound seems more general with a weaker assumption.
Overall, it is a good sunmision and offers much insight for SSL from the theoretical perspective.
review_title: This is a good submission that provides some theoretical understanding of the reconstruction-based SSL.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a mechanism based on approximate conditional independence (ACI) to explain why solving pretext tasks created from known information can learn representations that provably reduce downstream sample complexity, as a sufficient condition. In specific, they measure the downstream performance using the approximation error and estimation error, and establish their initial results under a strict condition -- conditional independence (CI) and linear function space in Section 3, then extend it to ACI and arbitrary function space in Section 4, resulting in the main contribution Theorem 4.2 that clearly quantifies the generalization error. The theorem is also verified in Section 5 using simulations on NLP tasks. 

One concern is that, in terms of the theory for self-supervised learning, I am not sure how big is the proposed theorem contributes to the community, as there are works such as Tosh et al. (2020b) in contrastive learning also provide theoretical guarantees using assumptions similar to CI. So I would rather hear more comments from other reviewers.

Another point is that the authors spent around four pages to illustrate their results with lemmas and theorems, which is good. But for the benefit of a broader audience, I would suggest to include more intuitions and discussions at the beginning, include some proof steps and ideas only with limited but key lemmas and theorems, and move the rest of them into the appendix. For example, Section 3.1 is on jointly Gaussian variables and 3.2 is on general random variables, they are indeed different, but results are pretty same and kind of overlap with each other. I would suggest shrink them but add more discussions and intuitions for the audience. 

Overall, from my own point of view, the paper is clearly written and well-motivated. It addresses an important question that perfectly fits into the ICLR topics: what connection between pretext and downstream tasks ensures good representations? 


------
Update after rebuttal

Thanks for the author's response. Combing the author's response (though the authors didn't upload new versions to address my comments -- include more intuitions and discussions) and other reviewer's comments and discussions. I suggested this paper being marginally above the acceptance threshold.


review_title: Interesting topic and useful findings

final_score: rating: 6: Marginally above acceptance threshold
review_content: 

  *  Summary of the paper.
  The paper shows theoretical results to support the claim that (approximate) conditional independence is a good way to quantify the link between the downstream task and the pretext task in self-supervised learning. Doing so, the authors prove theoretical results showing that indeed self-supervised learning decrease the estimation error in a classification task when the downstream task and the pretext task are linked through conditional independence or the weaker approximate conditional independence showing that approximate conditional independence is a good quantification of the link that the downstream task and the pretext task must have in order for the self-supervised learning to be efficient. The authors also provide numerical illustrations.
 
  * Strong points: theoretical guarantees in SSL (there are not a lot of those) while using approximate conditional independence which is more realistic than conditional independence.  The paper has some experiments that support its claim. The paper takes a gradual approach, first with jointly Gaussian variables and then with general (sub-Gaussian) random variables which helps the comprehension because at least in the Gaussian case, things are not so hard.
   
  * Weak points: Use of mean squared error for a classification task which negates most of the practical aspect of this paper. Not enough details in the proofs. The bounds are not optimal. The experiments are not reproducible and the presentation of those experiments is somewhat lacking. Overall problems with experiments.
    
  * Recommendation.
    I vote to accept because this is one of the rare theoretical guarantees for SSL, the approximate conditional independence is very interesting as a way to quantify the link between downstream and pretext task and this gives more understanding on how to choose a pretext task in practice when doing SSL.


  *  Questions:
    * Why did you use MSE ? Why not Cross entropy for instance ?
    * $Tr(\Sigma_{YY})$ in Theorem 3.3 is of order k for instance in the case where $\Sigma_{YY}$ is the identity matrix, the bound is $O(k^2)$ not $O(k)$, is it not? (contradiction with what you say in the text).


  * Additional feedback.
    * Please provide the minimax bound (i.e. optimal bound) in the "not self-supervised" context for us to compare with your bounds for self-supervised, below Theorem 3.3 you say that we gain from $O(d1)$ to $O(k)$ but you don't provide the bound that explain this $O(d1)$.
    * Please include the results of the simulation study in the main text. In my opinion, a simulation study must firstly show that your method works as intended, a sanity check of sorts. You simulation study does not do this because we don't see the results of this study right away, it is hidden at the end of the appendix.
    * Be careful, Theorem A.6 is only true for sub-Gaussian, please include this in the theorem, this is important in my opinion. 
    * Theorem A.6 can be improved, for now it is of order $\sqrt{\frac{Tr(\Sigma)}{n}}(1+t)$ but it can be made of order 
$\sqrt{\frac{Tr(\Sigma)}{n}}+\sqrt{\frac{||\Sigma||_{op}t}{n}}.$
  
        The difference can be important when the dimension is large (for instance if Sigma is the identity matrix in $R^d$, $Tr(\Sigma)= d$, $||\Sigma||_{op}=1$). To obtain this for sub-Gaussian vectors, one can for instance use the article "A tail inequality for suprema of unbounded empirical processes with applications to Markov chains" by R. Adamczak. This is important because the dimension is important for your conclusion.
    * Lemma A.7 is not true for any delta, please state in the lemma for which delta it is true (delta is at most $ke^{-n}$ if I am not wrong)
    * Generally, when reading the proofs I would have appreciated if you included more details. The "therefore" in the proof of theorem 3.3 was not clear right away for me, there are numerous lines where you do a lot of manipulations that the reader has to guess to obtain the good results and this makes it very hard for us to check the results you claim.
    * In the proof of Lemma C.2, please provide a reference for "Davis kahan", for those that are not familiar with this result.
    * Typo: beginning of the first sentence of A1.
    
    
    




review_title: Review of "Predicting What You Already Know Helps: Provable Self-Supervised Learning".

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper attempts to understand why self-supervised learning works in the following sense: will the sample complexity for a downstream task be decreased (compared to the standard supervised learning without pretraining) if it is pre-trained according to some related auxiliary task? The relation between tasks is formulated as the approximate conditional independence of the dependent variables. The main theoretical results show that the sample complexity (compared to supervised learning) can be decreased under Assumption 3.5, 4.1, and 4.2. 

Clarity: 

Generally, this paper is well organized. I have some comments to improve clarity. 

i) I'm not quite sure about the motivation of the conditional independence assumption in the introduction. In the colorization example used in the introduction, an algorithm with a general hypothesis (not CNNs) does not necessarily know the semantics of the images (even implicitly) to predict the background-color. It can focus on the cross channel information at the image border to make predictions and ignore the image semantics. Such a self-supervised learning method works (i.e., extracts semantic features) may simply because of the inductive bias introduced by the hypothesis (i.e., CNNs). Therefore, I can hardly say that the pretext tasks work because the "only" way is to implicitly infer Y first given the conditional independence assumption.

ii) It may be better to explain more about the assumptions and conclusions (lemmas and thms) considering both the theory and practice in self-supervised learning. 

For instance, about theorem 4.2, the paper only mentions that the bound is independent of the complexity of the feature extractor. Why can you achieve this? I guess it is because of the two-stage training and a strong assumption on the feature extractor. Any technical contributions to achieve this should be highlighted? Do the results of traditional supervised learning rely on a similar assumption? Besides, around theorem 4.2, I didn't see a sample complexity comparison to supervised learning. Maybe it is well known, but this is the main claim of the paper. 

Further, I wonder how good the sample complexity is, compared to the results in some related areas like transfer learning and semi-supervised learning (not just supervised learning). Self-supervised learning has outperformed other methods in transfer learning and semi-supervised learning and it would be better to at least discuss more.

Correctness:

I'm not an expert in machine learning theory. I read the main text carefully and I understood the setups, assumptions, and main results. I quickly checked the proof in the appendix and didn't find flaws. I'm aware that I may underestimate the theoretical contribution of the paper since I'm not familiar with the related work. Welcome any feedback on this during rebuttal and discussion.

As for empirical validation, considering that the main result is Theorem 4.2 and the main "baseline" is supervised learning, it would be better to directly compare the sample complexities of supervised learning and self-supervised learning in experiments.

Generality: 

One major concern is that the conditional independence assumption (even the approximate one) can be violated in practice. For instance, recently, the instance discrimination pretext has been extensively studied in self-supervised learning and achieved SOTA results in many benchmarks  (e.g., in MoCo and many recent papers). In that case, the random variable X2 is the index of the image (or the input generally). Since we can shuffle the index, it seems that we cannot say X2 (index) and X1 (image) are (approximately) conditionally independent conditioned on Y(label). Also, the paper mentions that some concurrent work does not apply to recontrsuction SSL in the related work. I think, in this case,  X1 = X2, and the conditional independence assumption does not hold as well. In such cases, does the analysis in this paper still apply? The generality of the analysis should be discussed somewhere in the paper because i) the title seems to cover all self-supervised learning methods and ii) the main difference of the paper from several recent papers is the generality as claimed in the related work.

Another issue is that the paper discusses two hypotheses H1 and H_u and also mentions that H_u includes deep neural networks. However, as far as I know, only infinitely wide or deep neural networks are in H_u.  In practice, self-supervised learning often uses networks with finite depth and width. Does the analysis in this paper apply in this case? If so, please also add detailed discussion and some validation experiments in such models. Otherwise, please clarify this since it can be misleading.

Related work: 

Compared to the existing work, the main contribution of the paper is to generalize the conditional independence based analysis via weakening the assumption. We may need to pay attention to that some concurrent work mentioned in this paper obtain similar results (with less generality as claimed in the related work but also see my comments in Generality).

Overall, I think the theory of self-supervised learning is very important and I should not blame the authors too much since it is an early work on this topic. However, I hope the authors to address the above issues to improve paper quality. I give a rating of 6 currently but it is very borderline in my opinion.
review_title: An interesting paper with some issues on clarify and generality

Meta-review: This paper proposes a mathematical framework to theoretically understand and quantify the benefit of self-supervision on the downstream tasks. The theoretical analyses in this paper are concrete and the authors conducted experiments to support their claims. However, the current version still has the following weaknesses.  

- This paper would benefit from incorporating the reviewers' comments (which was complained by multiple reviewers) and the authors' responses if any.
- The authors need to make it clear in the abstract and introduction that (1) this paper only considers the *reconstruction-based* SSL, instead of the general SSL, and (2) addresses the discrepancy between the practice and the proposed framework.  
- In the post-rebuttal phase, Reviewer 2 pointed out "Lemma 3 seems much more meaningful after the clarifications. I also notice that R5 concerned about the discrepancy in downstream task setup and may doubt the mathematical framework in this paper. In fact, I agree with R5. There is indeed a gap between the proposed mathematical model and the practical SSL algorithms. There is still some work need the authors to complete, i.e., $\mathbb{E}[Y|X_1]\approx \mathbb{E}[Y|X_1,X_2]$."
Decision: Reject