Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper aims to theoretically explain and investigate the benefit of reconstruction-based self-supervised learning. This paper studies a specific problem with two input features and one downstream label and shows how the specific connection between them can guarantee successful self-supervised learning.  In particular, this paper quantifies how the approximation independence between two input features can be extracted to solve the downstream tasks. Results show that self-supervised learning can successfully learn the ground-truth with much smaller labeled sample complexity.

main_review: I have to say I am not familiar with self-supervised learning and its theory. From a general point of view, the theory established in this paper is rigorous and makes sense to me. The assumptions, theorems, claims are clearly presented.  

However, my main concern is regarding the clarity of the paper. For example, from the proof sketch of Lemma 3.1, it is not clear why the matrix A has rank $k=|Y|$? Why sometimes the authors use the $\arg\min$ notation to denote $f^*$ and $\psi^*$, and sometimes they are written using the expectation notations.

There are a bunch of notations used in the paper (e.g., $b_0$, $\beta$, $\alpha$, $k$, $m$, $\rho$, etc). It would be better to summarize them somewhere. Besides, I am wondering whether the authors can briefly elaborate on which of them are typically large (e.g., $\omega(1)$) and which of them are typically small (i.e., $o(1)$).

Lastly, does the conditional independence really hold in practice, or how small is their correlation? The authors should add more content to justify this (experimental justification could be better). 

=========================

Thanks for the authors' response. I agree the paper presentation can be improved after fixing the problems I mentioned. I would like to keep my evaluation marginally acceptance.
limitations_and_societal_impact: This paper has no potential negative societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper suggests a theoretical model to capture
why reconstruction-based self-supervised learning leads to good representations, and improved downstream performance.
The suggested model is that the pretext task "factors through" the supervised labels, i.e. that X_1 -- Y -- X_2 is Markov, where X_1-->X_2 is the pretext task, and X_1 --> Y is the supervised task.
In such a setting, it is shown that the optimal pretext function has certain good properties: it linearly separates the supervised task, and
is "low rank", so can be used for efficient downstream learning.
main_review: ## Strengths
- The main realization of this paper is interesting: it gives a setting
where learning an "auxiliary" task is actually linearly-related to the task of interest (without assuming any linear structure in the tasks themselves). This is the statement of Lemma 3.1, which I consider to be the main conceptual contribution of this paper.
Lemma 3.1 is technically straightforward, but the statement is interesting.

- The problem studied is important: we do not have much theoretical understanding of why SSL methods work in practice.

## Weaknesses

- The primary weakness of this paper is that the statistical (Markov) assumption is extremely strong (even in its "approximate" formulation),
and does not clearly connect to any situations in practice.
There are no experiments that support the assumptions, and the intuitions presented are not convincing. That is, although the claimed motivation
of this paper is to study "What conceptual connection between pretext and downstream tasks ensures good representations?", the results in the paper do not clearly shed light on this question in realistic settings.
In particular, I do not think Assumption 4.1 will hold in practice, for reasonable values of $m$. More importantly, I do not think it captures the spirit of many pretext tasks: there could be very high mutual information between X_1 and X_2 in practice, even when conditioned on the supervised label (Y). This is especially the case when the supervised task is much "easier" than the pretext task.

- I do not believe the technical contributions are strong enough to stand alone, without appropriate motivation from practice.
Most of the technical results are essentially corollaries of
Lemma 3.1, expanded in straightforward ways.
I do not think these results contribute significantly
to the mathematical theory of learning (and they do not develop any new technical tools, as far as I am aware).

- The empirical section is lacking. It would have been nice to see some attempts to empirically justify the theoretical assumptions made in this work. For example, by trying to approximately estimate the conditional independence in realistic settings.
However, the experiments on real data do not attempt to probe the validity of the assumptions.
limitations_and_societal_impact: Societal impacts N/A.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: - The paper theoretically analyzes self-supervision under some simplifying assumptions. They begin with a conditional independent setting, where X1 is conditionally independent of X2 given Y.
- The high-level idea is to first pre-train a model that predicts X2 from X1. This can be done on unlabeled data. Then they can fit a model on top of representations learned by this model, to predict Y.
1. Ground truth self-supervision: They show that if we learn E[X2 | X1], the ground truth self-supervision function, then under mild invertibility conditions, E[Y | X] is a linear function of E[X2 | X1]. Further, E[X2 | X1]'s effective dimension is the same as Y, so this linear function can be fit using very few examples. In contrast, the function from X1 or X2 to Y can be very complicated / non-linear and require many examples to fit.
2. Linear self-supervision: They then examine what happens if we fit a linear function (on feature space) to predict X2 from X1. This can learn a useful lower dimensional embedding, and then we train a linear classifier to predict Y on top of this. They show this is more sample efficient than just training a linear classifier from X1 to Y.
3. Relaxing conditional independence: They quantitatively examine how this degrades when we don't exactly have conditional independence. Their bounds will still be good if things are "almost" conditionally independent.

main_review: After rebuttal: added comments below

---------------------------------------------------------------------------------------

Strengths
- I think this is a strong paper. Result (1), that E[Y | X1] is a linear function of E[X2 | X1] under conditional independence, is already conceptually quite intriguing to me. It's easy to prove if someone told you the result was true and asked you to prove it, but it is nice and surprising. In fact, I mentioned the result to a couple people who are really good at ML theory and work in related areas, and they didn't believe the result at first - they figured it could be true for Gaussians under conditional independence, but not in general (for discrete Y).
- I think results (2) and (3) make the paper even stronger, because they handle situations where we don't have exact conditional independence, or if we learn a linear model (even when the ground truth model is much more complicated).

Weaknesses
- Please label all equations for easy reference, both in the main paper and appendix
- The quality of writing in the Appendices should be substantially improved. To be clear, I'm not saying anything is wrong. I sampled some proofs and read them carefully, and they do appear to be correct, but they're very hard to follow.
- Focusing on the proof of Theorem B.3. In line 693, in the first step, I believe it should be <= -2<N, psi(X1) W* - psi(X1) \hat{W}>
- I'm not sure what P_{\psi(X_1)} is, what are we projecting to? And why does that not change N?
- In the last line of the equation array in line 697, you have an extra k in the denominator, it's not clear why that disappears?
- In the first line to the second line of the equation array in line 697, how does a matrix vector product (which is a vector) transform into a scalar (frobenius norm)?
- Unfortunately, it's hard for me to verify the results from Section 3.2 onwards, especially for Section 4. I did some basic sanity checks to see that they seem reasonable, and sampled some parts of the Appendix, and it looks likely correct overall.
- Part of why the proof are hard to verify is because the results are somewhat complicated (which isn't a bad thing!). But the other more important issue is that there aren't substantial proof intuitions given in the main paper, and the proofs in the appendix don't seem to be written very well (for example, a large number of typos just between line 693 and 697). I only sampled a small proportion of proofs, so it's possible that I happened to sample the bad examples.
- I'd personally err on the side of having fewer results, that are very clearly explained and proved, and that the reader can fully understand.

I think it's worth comparing this framework much more carefully with co-training. Both co-training and self-supervision are essentially semi-supervised learning methods, and co-training also assumes conditional independence. How would the bounds compare between the two? The initial co-training paper assumed conditional independence, and later versions assume weaker properties such as expansion [1], inspired from spectral graph theory.

I think it's worth noting that k often increases exponentially. E.g. if Z represents r 'semantic' features (like color, rotation, etc), each of which can take on one of s values, then k = s^r. Could be interesting for future work to avoid this blowup.

Other comments
- Why do we need to apply PCA in remark 4.1? E.g. in theorem 3.2, we didn't need PCA, because the complexity depends on the trace of some matrix so automatically improves if the data lies in a lower dimensional subspace.

Minor comments:
- Remark 3.2 uses m, which is defined later in assumption 4.1
- Claim A.3 has typos, it says it's a concentration result for sub-Gaussians, but assumes the data is Gaussian. Also unclear what Sigma_X is if it's sub-Gaussian?
- I think Theorem 3.2 should use n_2 instead of n in the theorem statement.
- Line 274 appears to change the definition of excess risk - maybe use a different terminology?
- In theorem 4.2, is assumption 3.2 actually not needed for universal feature maps?
- In theorem 4.2, do you really need both a lower bound on n1 *and* an upper bound on the error of the pretext tasks, \epsilon_pre^2?

[1] Co-Training and Expansion: Towards Bridging Theory and Practice. Maria-Florina Balcan. Avrim Blum. Ke Yang.

limitations_and_societal_impact: Looks fine.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies whether reconstruction-based pretext task can provide representations helpful for downstream tasks, which is a question of good interests in the community.

The authors give an affirmative answer that when (approximate) conditional independence holds, reconstruction as a pretext task provides representations such that 1) an additional linear layer is sufficient to ensure small approximation error on classification, and that 2) helps to reduce the sample complexity of the classification task from complexity of the function class (without pretraining) to linear in data dimension.

These theoretical results are empirically verified on synthetic, vision (inpainting), and NLP (sentiment classification) tasks.
main_review: **Significance and novelty of the contribution**: To the best of my knowledge, this paper is the first to provide a statistical connection on reconstruction-based self-supervised methods and downstream tasks. The setup and (approximate) conditional independence assumption is reasonable; for example, several recent works on multi-view redundancy adopt similar assumptions. 
 - It's much appreciated that the theoretical results are verified by multiple experiments. However, it would be better if the authors could comment more on the practical implications of the assumptions required for theory.

**Relation to prior work**: This paper is clearly situated in relation to prior work. The discussions on comparison to prior work (esp multi-view) are sufficiently detailed which is appreciated.

**Clarity & writing**: This paper is well structured and easy to follow. Some minor notes:
- Typo: Thm 3.2: $n$ should be $n_2$.
- Line 235: $d_2 < km$: $m$ hasn't been introduced yet.
- Line 239: on the RHS of $\psi^*$, $x_1$ should be $\phi_1(x_1)$ (otherwise $\psi^*$ is linear in $x_1$).
- Typo: line 321: remove the first word "this".

====== 
Post-rebuttal update: I thank the authors for their responses and keep my score of recommending an accept.
limitations_and_societal_impact: Future directions pointed out by the authors include 1) analyze the effect of fine-tuning to bring down the approximation error terms; and 2) study other possible conditions under which pretext tasks are helpful for downstream learning, since CI is sufficient but likely not necessary.

Societal impact is not applicable since this work is theoretical.
review_title: null

Meta-review: Three of four reviewers generally agree to recommend this paper for acceptance, and I agree with the strengths that they highlight, especially as reviewer Y1dq summarizes them.

Reviewer hGAR, who recommends rejection, makes a valid point as well: the experimental section and the discussion of assumptions leaves room for improvement. I encourage the authors to take the committee's suggestions about these parts into consideration when revising the draft.

For instance, two reviewers would have liked to see an empirical signal for whether the conditional independence assumption holds in a real data setting (not simulation). Even if the authors choose not to do this, it is natural to ask and it is lacking from the experiments, and so it is ultimately a limitation. It's best to be clear about whether the experiments are meant to closely verify theory (including its assumptions), or whether they are meant only to show that the analysis is at least not at odds with empirical observations. The latter seems to better describe this paper's experiments, but it is a weaker point than the former, and discussing limitations ultimately helps with clarity.

I will add that there are other ways to support an assumption than by experiment. One is to identify example mathematical constructions that satisfy them (e.g. topic models, HMMs). Another is to point to similar assumptions made in related prior work. The paper does the latter reasonably well. If it is easy enough to do, perhaps the authors can make use of an example construction or two as well.

Overall I second Y1dq's remarks in discussion that this is a field with little theoretical analysis, and that what constitutes a reasonable abstraction and assumption is not yet clear. Making assumptions for progress is fine, especially if similar ones have been make in related work. The validation and discussion of assumptions in this paper could be improved as hGAR emphasizes, but overall the support from the remaining reviewers leads me to recommend acceptance.

Decision: Accept (Poster)