Venue: NeurIPS 2022 Conference

Reviews:

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: Characterizing the desirable properties for representations learned via self-supervised learning objectives,  presents open theoretical and empirical questions, particularly in the context of downstream classification tasks. The authors propose a framework to study popular contrastive and non-contrastive learning algorithms as invariant-SSL (iSSL). Under some technical assumptions, they present certain properties of population-optimal and sample-optimal feature encoders (c.f. Eq 2, Sec 3) for evaluation with linear probes. Building on these characteristics, the paper presents practical design primitives to learn encoders with such properties. In particular, with approximations to a log-loss training objective, and different estimators to approximate the true loss, the framework recovers popular SSL objectives (SimCLR, Dino). Finally, these estimators are evaluated via experiments on the Tiny Imagenet dataset, where ISSL motivated modifications translate to ~3% improvement in both regimes of pretraining. Notably, Distillation ISSL is a simplified training algorithm which recovers representations which are competitive to, and often better than strong baselines (SwAV).
strengths_and_weaknesses: Strengths:
+ The paper presents a novel framework (ISSL) to study the paradigm of contrastive learning, SSL pretraining objectives. Notably, the authors study invariance to data-augmentation with downstream classification tasks and use ISSL to find simplifications to popular SSL algorithms (e.g. SimCLR with asymmetric projection head, Distillation SSL as an alternative to SwAV).
+ The authors perform extensive ablations on TinyImagenet dataset and compare to strong baselines to establish the efficacy of insights from there proposed framework. The simplifed learning objectives could further encourage research into more fine-grained questions about these training algorithms (such as learning dynamics, sample efficiency etc).


Weaknesses:
- Beyond evaluation on linear probing, the authors are encouraged to present visualizations, discussion on emergent structure in representations learned with their proposed algorithm as compared to prior work. 
- Certain assumptions in the framework are too restrictive or unrealistic (such as label being either invariant to class of augmentations, or not i.e. binary effects of the data-augmentations). 
questions: A couple of questions for the authors:
1. How well do the estimators approximate the desired quantities (e.g. DISSL approximates $M(x)$) ? For instance, are there controlled experiments with toy datasets to demonstrate the effectiveness of the auxillary losses?
limitations: The authors are encouraged to consider relaxing some of the strict assumptions, namely:
1. Coarse-grained effects of data-augmentation operators (the operators are often smooth, low-variance). 
2. While the authors demonstrate that stronger data-augmentations improve in-distribution generalization, I think it also important to consider out-of-distribution generalization (i.e. performance on different tasks).
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper tends to figure out crucial properties of self-supervised learning (SSL) methods, which promote good performance on downstream tasks. To reach this target, the authors propose a unifying conceptual ISSL framework. In particular, their primary contributions contain: i) increasing the dimensionality of presentation and using asymmetric projection heads; ii) presenting a new non-contrastive ISSL objective; iii) applying non-linear probes.
strengths_and_weaknesses: The motivation is clear, and I appreciate the heavy theoretical and empirical efforts.

However, my main doubts/concerns regarding the paper are the following:

- This paper is hard to follow because of the lack of organization. I strongly recommend that the paper needs significant improvement in writing.
- The novelty of the mentioned contributions is limited:
1. Increasing the dimensionality of presentation. The effect of dimensionality has been thoroughly discussed in previous literature [1,2]. Are there any different insights in your experiments? If yes, please elaborate the difference between this paper and [1,2].
2. Using asymmetric projection heads. In [3,4,5], they have theoretically and empirically discussed the impact of asymmetric projection heads.
3. Novel non-contrastive ISSL objective. To my knowledge, DINO[6] may first introduce "self-distillation" into self-supervised learning. The authors mention DINO in line 210, yet I did not find any analysis on comparison between DINO and DISSL. Can the authors discuss the difference between DINO and the proposed DISSL?
4. Non-linear probes. Although non-linear probes improve downstream tasks, they cannot serve as a property of SSL representation. Thus, this result can hardly support your original motivation.
5. Coarser augmentation. InfoMin [7] has thoroughly analyzed the effect of augmentations or view selections. Besides, they claimed that "we should reduce the mutual information (MI) between views while keeping task-relevant information intact.", which is nearly the same as your proposed "stronger label-preserving augmentations".
- In Table 3, a lack of comparisons with state-of-the-art methods mentioned in the "related work" section, including BYOL[3], DINO[7], MoCo[8], Simsiam[9].
- Inconsistent hyper-parameters between main paper and supplementary material. For instance, "3072 batch size" in Table 3 and "a total batch-size of 2560" in line 1034.

Minor:

- The experimental setting on TinyImageNet is not standard. I kindly suggest that you could follow some previous work [10,11,12] if the computation resources are constrained.
- Some informal theorems and algorithms. Take Algorithm 1 (line 237) for example, the inputs are required to be clearly described.

[1] T. Chen, et al., "A Simple Framework for Contrastive Learning of Visual Representations", ICML 2020.

[2] J. Zbontar, et al., "Barlow Twins: Self-Supervised Learning via Redundancy Reduction", CVPR 2022.

[3] J. Grill, et al., "Bootstrap your own latent: A new approach to self-supervised Learning", NeurIPS 2020.

[4] Y. Tian, et al., "Understanding Self-supervised Learning Dynamics without Contrastive Pairs", ICML 2021.

[5] X. Wang, et al., "On the Importance of Asymmetry for Siamese Representation Learning", CVPR 2022.

[6] M. Caron, et al., "Emerging Properties in Self-Supervised Vision Transformers", ICCV 2021.

[7] Y. Tian, et al., "What Makes for Good Views for Contrastive Learning?", NeurIPS 2020.

[8] K. He, et al., "Momentum Contrast for Unsupervised Visual Representation Learning", CVPR 2020.

[9] X. Chen, et al., "Exploring Simple Siamese Representation Learning", CVPR 2021.

[10] Y. Tian, et al., "Contrastive Multiview Coding", NeurIPS 2021.

[11] Y. Kalantidis, et al., "Hard Negative Mixing for Contrastive Learning", NeurIPS 2020.

[12] C. Chuang, et al., "Debiased Contrastive Learning", NeurIPS 2020.
questions: - Are there any different insights in your experiments? If yes, please elaborate the difference between this paper and [1,2].
- Can the authors discuss the difference between DINO and the proposed DISSL?
limitations: Yes, the authors have addressed the societal impact of their work.
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: In this work, the authors characterize properties that representations learned in self-supervised way should ideally satisfy. They prove necessary and sufficient conditions such that for any task invariant to given data augmentations, the probes (e.g., linear or MLP) trained on such representation attain perfect accuracy. Based on these requirements the authors propose a unifying framework for improving existing SSL methods and deriving new ones. In contrastive learning regime, they propose asymmetric projection heads and in non-contrastive learning regime, they derive novel objective. 

In the evaluation, the authors focus on the implications of the proposed framework using the TinyImageNet and ImageNet data sets. It consists of experiments and results 
(i)   about the use of the proposed objectives to ensure sample optimal encoders in ideal settings, 
(ii)  regarding the finding by the theoretical result (Theorem 1), 
(iii) related to the use of coarser label-preserving augmentations (Proposition 2) and 
(iv) for training with the smallest ISSL log loss to ensure optimality (Proposition 3). 

The results show that the proposed self-supervised algorithms lead to improvements in performance with respect to the baselines on the used datasets for different ResNet neural network architectures.
strengths_and_weaknesses: Originality: The authors present a framework in an attempt to characters self-supervised learning and describe the problem grounded on invariant self-supervised learning and idealized representations. The authors formalized the notion of invariant self-supervised learning using an equivalence relation between original data and it's augmented version that should partitions the inputs X into  equivalent classes. Further they define optimal encoders at least theoretically, stating/defining population optimal and sample optimal cases that can produce ideal representations in terms of classification with minimum error (minimum empirical risk).

They give result about the required dimensionality of the population optimal encoders (at the output) by which the representations are linearly predictable. They argue that ERMs encoders that correctly predict one example in an equivalence class, also correctly predict all the others. They prove that such invariance of population optimal encoders is necessary and sufficient for sample optimality.

They also derive simple objectives that learn optimal encoders in ideal settings (infinite data, perfect optimizers, universal function approximators). In addition, they try to explain why previously proposed invariant self-supervised learning methods work, and comment how they might be improved in practice for contrastive invariant self-supervised learning and distillation invariant self-supervised learning.

Quality: The quality seems good. It is interesting how the authors state the problem formulation and relate it to empirical risk minimization in order to characterize the ideal representations (under ideal scenario) as well as how the authors relate to existing work and to practical considerations. 

In the evaluation, the authors focus on experiments that are towards verifying the postulated theory. On the TinyImageNet data set they show large gaps of improvement of recondition accuracy compared to the used baselines. On the ImageNet data set they are somewhat on pair (with small improvement) compared to some of the state-of-the-art methods.

Clarity: The paper attempts to outlay an unified theory. Overall, the paper is well organized and the writing is good. The readers have to keep track of the many characteristics, propositions, derivations, etc, sometimes pushes the paper a bit on the heavy side, which might suggest that the content in this work needs more space. Maybe a table of content about the most important concepts could help.

The authors take on practical considerations for contrastive invariant self-supervised learning and distillation invariant self-supervised learning. Maybe focusing only on one of these two (or putting one in the appendix) might have made the paper lighter and the authors could have had more space to do more experiments as well as overall make the paper a more easy of a read. On the other hand, there are also a lot of additional details that the authors leave for the appendix

Significance: Unsupervised and self-surprised learning might be very important aspect towards the long-lasting goal of human-capable machine learning and artificial intelligence in practice. Theoretical foundation in this direction are of particular interest for understanding and improving existing works, and designing novel algorithms that could brings us closer to this goal.
questions: Could the authors comment more about how close the proposed theoretical foundation is to the practical cases?
Have the authors evaluated the proposed approach on other datasets (common in computer vision or other public ones)?

limitations: The authors address the limitations of the paper exposition in Section 7 Discussion and Outlook. Regarding the potential negative societal impact might be nice that the authors comment/discuss about the theoretical connections/aspect of their framework related to learning of possible biases/"short cuts" that might be undesirable as well as misused.
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: In this work, the authors characterize the properties of an ideal set of representations for self-supervised learning. Namely, they use the notion of equivalence classes with respect to some transformation, and show that under certain assumptions, it is possible to characterize a sample optimal encoder for the desired equivalence classes. Using intuition from this characterization, they formulate a variant of self-supervised loss which can learn these optimal encoders under ideal conditions. The authors also evaluate practical objectives based on this loss, and show their competitiveness against other similar techniques from the literature.
strengths_and_weaknesses: This is a solid work overall, with several strong points:

- First of all, the topic of this work (self-supervised learning) is of great interest to the NeurIPS community. The authors analyze in great detail this paper’s related work, and properly demonstrate how it is positioned with relation to previous works in the literature. The paper is also very cleanly written overall. As a minor comment, although I understand that the authors moved the related work to the appendix due to space limitations, I believe that at least a short version of its should appear in the main paper.

- Secondly, the theoretical foundation of this work is solid. While the idealized encoders are defined using ideas which exist as a notion in the literature (for example, the fact that we want our encoders to be invariant to augmentations and predictive of the latent classes, which are conditions set in Theorem 1), this work provides a careful formalization of these ideas. Moreover, with Propositions 2 and 3 the authors provide an expression for the expected risk of those encoders and a loss that when minimized recovers these optimal encoders. Even though these theorems are only applicable under idealized assumptions, they still provide a good theoretical characterization of the idealized representations.

- Moreover, the link between the theoretical formulation of the ISSL loss and the practical versions defined in the paper is clear and well-motivated. The authors accurately assess that the main problem in the formulation of the ISSL loss is the lack of knowledge regarding the underlying classes and take measures to rectify this in the practical versions of the loss. I also appreciate the discussion on how each of the two formulations proposed by the authors (CISSL and DISSL) relate to contrastive and non-contrastive technique in the literature, respectively. In my opinion, this provides a good foundation of the proposed techniques, in relation to existing literature. The experimental evaluation of the two proposed methods also demonstrates that they are competitive and in most cases outperform the previous techniques, despite their simplicity.

- Finally, the authors extensively prove their theoretical statements and expand upon connections to the related work in the appendix. The added experiments in the appendix also go beyond standard performance evaluation based on accuracy, and examine various effects such as the augmentations used and the dimensionality of the representations. This is very useful in order to fully understand the proposed method.

A few weaknesses I can identify are the following:

- At the beginning of Section 4, the introduction of the loss function is somewhat abrupt, and while Proposition 3 demonstrates the link of the loss to the optimal encoders discussed above, I believe that including a proof sketch for the proposition or intuition on why it holds would help the connection with the previous parts of the paper. In a similar vein, I believe expanding upon Figure 4 would be useful, because currently it seems to be somewhat disconnected from the rest of the paper.

- A key limitation in the idealized setting is that it holds only in if the dimension of the representation is at least the number of equivalence classes minus 1. Combined with the assumption that the encoder is invariant to the equivalence class, this geometrically implies that there exists one point for each class in the representation space, and they can be shattered by halfspaces (which can be easily done if the points are general enough and they are at most 1 plus the representation dimension). Lemma 13 in the appendix expands upon this, but I believe it should also be pointed out in the main paper, because it may seem as an oversimplification otherwise.

- I believe that Section 5 should be shortened and included in the Section 4. This would allow parts of the appendix (namely, related work and some proof sketches) to be included in the main paper without harming the experimental section (since non-linear probes are only a small part of the main paper).

Overall, this is a strong and clearly written work. The above flaws I pointed out are minor, and I believe that the main issues I have can be addressed in the author response.

Minor comments:
- In Section 3, consider explicitly highlight the fact that equivalence classes are different from downstream classes, to avoid confusion.
- Line 43, $\mathcal{T}$ is not defined.
- Line 224: missing "and"
- Appendix H.2 seems to be missing.

questions: I would like to know whether the authors have performed any experiments regarding transferability of the learned representations for their methods. This is an experiment commonly seen in the literature of this topic, and it would be good if the authors could include it in the paper.

As mentioned above, I would also suggest the authors to include parts of the related work and proof sketches in the main paper, to help with reader understanding.
limitations: The authors have adequately adressed the limitations of their work (namely, the idealized setting of their theory and the lack of constraints on the encoders and tasks considered), both briefly in the main paper and extensively in the appendix. Moreover, I don't believe there is any negative societal impact arising from this work. As such, I believe the authors have addressed these topics sufficiently.
review_title: null

Meta-review: metareview: Decision: Accept

This paper provides a theoretical analysis on the invariance properties of representation learned by self-supervised learning, and derived an algorithmic framework from the theory which includes approaches similar to existing SSL methods. Empirical results demonstrate the competitiveness of the proposed approach.

Reviewers found the proposed approach simple but effective, and the related work and limitations are discussed. Initially there are concerns regarding novelty & comparisons to previous work, which are largely addressed in author feedback & revision. 

After reviewer-AC discussions, it is concluded that we should accept this paper. In revision for camera ready, I'd suggest the authors to follow what they promised in their summary feedback, and improve the clarity of the presentation, especially on section 4 as suggested by one of the reviewers. The additional results provided by the authors in feedback period should also be added.
confidence: Certain
Decision: Accept