Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In self-supervised learning (SSL), a representation is learned and it is usually one multi-dimensional vector. This paper proposes an effective representation using multiple sparsified embeddings (SEM) inspired by over-complete representation. It is obtained by projecting the SSL embedding into multiple smaller dimensional vectors each through a softmax operation. The sparsity of the smaller vectors can be controlled via the temperature parameter in the softmax function. The author gives theoretical analysis on the benefit of using SEM and also conducts extensive empirical experiments. The results show the superiority of the proposed method. 
strength_and_weaknesses: Strength: 

Clarity and quality of writing. Extensive experiments.
The paper is well written with a pretty clear introduction of background and related work. I also like how the author draws inspirations from the over-complete representation literature to motivate the proposed method. The experimental results show both quality improvement (with reasonable computation increase) and interpretability improvement.

Originality. The work seems pretty novel to me. 
Practical application: Being aware of the increased memory usage from SEM, the author also studies how to efficiently reduce memory usage at inference time. 

Though the findings in the proposed work is largely based on prior work in SSL, the SEM idea is pretty interesting and effective (observation from the empirical results).

Weakness:
Questions to the author(s):

1. Regarding Figure 5 (a), or effects of increasing $L$. Have you investigated when the improvement of accuracy starts to diminish if we further increases $L$ (e.g, increase $L$ to 20K, 50K)?  A larger number of basic vectors could be very helpful in defining finer granularities in some applications.

2. Could we increase the embedding dimension in BYOL to achieve the similar quality improvement as achieved by SEM?

3. Is the BYOL metric in Figure 1 a strong baseline? This is not something I am familiar with. Please clarify.

4. After SSL embedding is obtained, one usage of the SSL embedding is to perform clustering to obtain needed level of granularity and interpretability. Let's say we cluster the embeddings into 5K groups. And also on the other hand, we have the SEM embedding (when L= 5K), what would be the pros and cons of the two approaches ?

I will be willing to increase my score once the questions above are well clarified/explained.
clarity,_quality,_novelty_and_reproducibility: See clarity/quality/novelty above.
Reproducibility:
The author includes very extensive descriptions of their experiment setup in the appendix and provides code in the supplemental maternal. I believe it will be sufficient to reproduce their work.

Minor comment:
Appendix D.1: the last line at page 24, "the $ of parameters" should probably be change to "the # of parameters".


summary_of_the_review: The author proposes a simple yet effective component to build more interpretable and more effective representation. The experiments are solid and extensively demonstrate the effectiveness of the method. There, I think it is a good paper - "accept".
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper suggests using simplicial embedding (SEM) -- instead of the standard R^d embedding -- as the feature for self-supervised learning and downstream classification. Specifically, given $L*V$-dim feature, SEM applies softmax operation for each $V$-dim subvector and concatenates the sparsified vectors. The paper claims the superiority of SEM theoretically and empirically. First, the paper provides a new generalization bound where the complexity measure $\varphi$ is determined by the type of final representation. Here, the paper claims that the complexity measure of SEM is strictly smaller than the one of standard R^d embedding. Second, the paper demonstrates that SEM improves the classification performance of various self-supervised learning methods.
strength_and_weaknesses: **Strength**

This paper makes a good attempt to validate their claims, providing a theory and empirical evidence. For example, the paper provides an ablation study on the size of $L$ and $V$, a comparison with hard discretization, and an analysis of semantic coherence. The overall presentation was well-written and supported by proper evidence.

---

**Weakness**

While the paper suggests an interesting alternative to designing an embedding, my biggest concern is whether future research would really use this technique. Here are some reasons why its practicality is not convincing yet.

* **Weak baselines.** The paper shows an improvement over underfitted BYOL trained for 200 epoch (IN acc.: 70.6) instead of standard 800 epoch (IN acc.: 74.3). Since many methods converge faster but saturates eventually (or even collapse later), the paper should provide the results at 800 epoch. Also, this repo (https://github.com/HobbitLong/SupContrast) shows that SimCLR trained on CIFAR-100 shows acc. of 70.7, although they use ResNet-50, which is 5% higher than this paper. Thus, the overall baseline results are undervalued, and the gain of this method can be exaggerated. Providing the results in the SOTA setup would make the benefit of SEM more convincing.

* **CIFAR-10 results.**
The paper only demonstrates the CIFAR-100 results instead of more standard CIFAR-10. I suspect that SEM is less effective for CIFAR-10. Still, it would be informative if the paper provided CIFAR-10 results in Appendix. How can we explain this if SEM is less effective for few-class classification? Discussion for coarse vs. fine-grained classification would be informative.

* **Heavy computation.**
As the paper mentions, SEM needs an additional layer to expand the embedding overcomplete, which requires many parameters, memory, and computation. Although Table 17 in Appendix suggests an efficient version, it still uses 2~3x of parameters. Due to this, the actual baseline should be BYOL with some additional nonlinear layers instead of the vanilla BYOL.
I appreciate that the paper shows that naively adding the overcomplete layer to BYOL does not work, as shown in Figure 3. However, I think a better way to sell this method is to emphasize the scaling part -- instead of adding an overcomplete layer (which may be arguable for a fair comparison) -- achieving SOTA using very-wide models would be more impactful. For example, current self-supervised learning (SSL) methods achieve SOTA on models like ResNet-50 x4. If the paper claims that prior work does not scale for larger models such as ResNet-50 x16 but SEM can, it could be a game changer.

* **Why self-supervised learning (SSL)?**
While the paper targets SSL, the idea of SEM could also be applied to supervised learning. Why the paper's scope should be SSL? Would SEM be more effective for SSL than supervised learning?

* **Comparison with a mixture of experts (MoE).**
Conceptually, SEM may be thought of as a simple instantiation of MoE [1] or MCL [2] where each $V$-dim subvector is routing the specialized feature for each class. The bipartite in Figure 6 shows the learned features are indeed specialized to some classes. Here, the MoE technique is popularly used to train large-scale models. Since one major benefit of SEM is robust training on larger overcomplete features, it may discuss the relation to MoE and may show superiority over them.

[1] Fedus et al. A Review of Sparse Expert Models in Deep Learning. arXiv 2022.\
[2] Guzmán-rivera et al. Multiple Choice Learning: Learning to Produce Multiple Structured Outputs. NeurIPS 2012.

Typo:
- Gubel -> Gumbel in the caption of Table 2.
clarity,_quality,_novelty_and_reproducibility: Clarity: Good.\
Quality: Good.\
Novelty: Good.\
Reproducibility: Good. It clearly states the base codebase and provides code in the supplementary.
summary_of_the_review: Overall, I think the paper has a clear contribution. However, I'm on the borderline since empirical evidence is not convincing enough. I'm willing to raise my score if my concerns are addressed:
- ImageNet results comparing with BYOL in 800 epoch
- CIFAR-10 results and explanation of why SEM is more effective for many-class classification
- Results on wide models such as ResNet-50 x16 instead of adding overcomplete layer
- Discussion on why SEM should be used for SSL - why not supervised learning?
- Comparison with MoE methods - would SEM be a better way to scale large models?
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes to apply a  subcomponent-wise softmax to SSL representations (z -> partition -> softmax -> concatenate -> new z), dubbed SEM. They empirically show that this simple transformation combined with a large increase in the dimensionality of the representation yields significant improvements in standard SSL benchmarks (in and out of distribution). They also try to explain the gains by providing generalization bounds of the downstream predictors.
strength_and_weaknesses: **Updated during rebuttal** the authors removed some strong claims and results showing that the gains are due to the proposed method rather than only increasing dimensionality of the representation. I thus update my score 5->8 .

-------

**Strengths**
- **Paper is well written** the paper is generally easy to understand and enjoyable to read.
- **Simplicity and generality** the main strength of the transformation is that it is simple and widely applicable. 
- **Significant empirical gains** the empirical results show uniformly significant gains across settings. Assuming that the baseline is indeed meaningful (see below), the results clearly indicate that the proposed method would be useful. 

**Weaknesses**
- **Is the theory meaningful?** my main issue with the theory is that it might be meaningless and unrelated to SEM[^1]. Specifically, it seems that using the arguments of your theoretical section one would conclude that any transformation that shrinks the support of Z would be better. For example, let $f_{\mathrm{new}}(z)=g(z/2)$ be a function that is defined like for SEM but the transformation is halving rather than SEM (other transformations like relu also works). Then if I followed your definitions you would essentially[^2] have $\psi_{f_{new}} - \psi_{f_{base}} \leq 2V - 4V = -2V < 0 $. Using the rest of your arguments you would thus conclude that "halving representation provably leads to better performance".  You can further use a parameter $t$ instead of $2$ to say $\psi_{f_{new}} \to 0$ as $\frac{1}{t} \to 0$. For the theorem to be meaningful for SEM it should give rise to the same conclusion for any transformation just because it shrinks the support. Am I missing something?
- (addressed in rebuttal) **Are gains only due to increasing dimensionality of the representations?** my main issue with the experimental results is that it is unclear to me whether the gains are only due to the increasing dimensionality of the representation rather than to the use of SEM. In particular, I think that your experiments and previous work show that: SEM+high dim helps, SEM only does not help, and high dim only helps. It is thus currently unclear what is the gain of SEM. More specifically: 
    - **Previous papers show similar gains by only increasing dimensionality** [1] argues theoretically + shows empirically that increasing dimensionality of representations helps downstream performance. There figure 7c shows a monotonic improvement in embedding size similar to BYOL+SEM in your figure 3. The line of work on dimensionality collapse, eg, [2], also suggests that higher effective dimensionality of the representation should improve performance regardless of SEM.
    - **Inadequate baseline** As just mentioned [1] finds a significant monotonic improvement when increasing dimensionality without SEM while your baseline doesn't. I think that the problem is that the baseline you are using does not actually increase the effective dimensionality of the representation. Indeed, your embedding layer is linear (linear layer + BN) and as a result, it cannot increase the dimensionality of the span of the representations (ie you are only increasing the ambient space but not the real/effective dimensionality). To bypass this issue [1] increases the dimensionality before the avg pooling layer (see Appx F1). Another standard way of increasing the dimensionality of representations of resnets which can lead to significant gains is to change the pooling layer (eg see [this code](https://github.com/facebookresearch/vissl/blob/main/configs/config/benchmark/linear_image_classification/imagenet1k/eval_resnet_8gpu_transfer_in1k_linear.yaml#L65) ). For this reason, the current figure 3 does not adequately support the hypothesis that SEM is what drives the performance up.
    - **SEM without increasing dimensionality seems to show no gains** BYOL + SEM without increasing dimension in Figure 3 seems to perform similarly to standard BYOL (table 17), thus suggesting that SEM without increasing dimensionality does not help.
 - (addressed in rebuttal) **Some over overclaiming**
    -  in the abstract, you say "we formally prove that the SEM representation leads to better generalization than normalized". This is a strong claim, which I do not think is supported given that you only show one upper bound is smaller than the other (without a discussion about their tightness). To support such a statement you could for example provide a lower bound on the generalization gap of $f_{\mathrm{base}}$ and show that it is larger than the upper bound of $f_{\mathrm{ERM}}$
    - section 4.2 you say "Figure 5 [...] allowing us to confirm two predictions made in Section 3.2: the expected generalization [...]". Your experiments do not actually test the generalization gap of the probe (as suggested by your theory) but the general test performance. One potential explanation (which would be my guess) is that the training performance of the linear probe is actually what drives the performance up (due to the increase of dimensionality) rather than the shrinking of the generalization gap. I think that showing the generalization gap is needed if you want to make any claims about the relation between your theory and experiments. Another way of testing your claims would be consider the standard "semi-supervised" setting where the downstream probe uses only 1% of ImageNet. My guess is that your representation will perform worst there (due to the high dimensionality) while your theory would suggest that it actually performs better due to the sparsity.

[^1] Note that I haven't read all appendices in detail. If the argument breaks please refer me to the exact line and I will look at it.

[^2] I removed $\delta$ for conciseness but the argument still holds with those.

[1] [Improving Self-Supervised Learning by Characterizing Idealized Representations](https://arxiv.org/abs/2209.06235)

[2] [On Feature Decorrelation in Self-Supervised Learning](https://arxiv.org/abs/2105.00470)
clarity,_quality,_novelty_and_reproducibility: **Clarity**: The paper is generally clear, easy to understand and enjoyable to read. My only concern in this respect is that the theoretical section is not understandable using only the main paper. Indeed one of the components of the theorem ($\psi$) is not even defined in main paper. I think that all terms in the main results should be defined in the main paper.

**Quality**: as discussed in the weakness the theory does not seem meaningful and the main claim of the paper (usefulness of SEM) is not appropriately supported. 

**Novelty** the proposed method is novel

**Repredocuability** hyperparameters and code is provided.
summary_of_the_review: The paper is enjoyable to read and could be impactful if the author's main claim (usefulness of SEM) holds. My main issue with the current version is that I have doubts about: (1) whether the theory is meaningful; (2) whether the gains are due to SEM rather than increasing the dimension of the representation.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Examines the utility of including a large number of parallel softmax operations, also called simplicial embedding (SEM), within a SSL method.  Includes theory showing improvements in generalization error bounds from using SEM, as well as extensive experimental evaluations showing benefits to classification, transfer learning, robustness to input corruption, as well as demonstrating interpretability of the SEM features (clustering by class).  The experiments also give insight on how to choose the number of simplices and the dimensionality of the simplex, as well as the temperature parameter.
strength_and_weaknesses: Strengths

+ Simple idea with interesting connections to sparse coding (in neuroscience)
+ Goes beyond looking at performance and also shows improved interpretability.
+ Includes a theoretical analysis.
+ Provides useful guidance on setting hyperparameters.
+ Evaluations show benefits in several problems: classification (without and without corruption) and transfer learning.


Weaknesses

- Why are some of the competing methods doing so poorly?  Is the poor performance of BYOB+Gumbel on CIFAR-100 really due to SEM being a better method, or perhaps the Gumbel approach was not implemented as well as possible? [after rebuttal: addressed]
- It would be nice to how changing the architecture affects results. [after rebuttal: addressed]
- A minor weakness, but the use of softmax is so commonplace that it doesn't even seem to warrant a mention in related work.
- The practical utility of the theoretical result is unclear.
- As reviewer E9n7 and 4CQ8 noted, the baselines could be improved.  BYOL should be trained until convergence, and increasing the number of nonlinear layers or increasing the size of the network to match BYOL+SEM would be more convincing. [after rebuttal: addressed]

clarity,_quality,_novelty_and_reproducibility: Quality

This paper is really solid with regards to explaining the method and examining all the details of how to use it.  The experiments show benefits in many supervised learning tasks, but may need to use stronger baselines.  The theory is interesting but may not be practical.


Clarity

The paper is clearly written.


Originality

SEM is conceptually similar to previous approaches, but somehow performs much better than them.
summary_of_the_review: This paper puts a lot of thought into presenting and analyzing a potentially high-impact addition to semi-supervised learning techniques.  The author's rebuttal addressed many concerns about the fairness of the comparisons and overclaiming. The impact of the technique (around 1-2 percent accuracy) would be interesting to a general audience but perhaps not at spotlight level.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This is a very nicely written paper that introduces a simple procedure, with theoretical motivation, that leads to real empirical improvement on self-supervised learning of features. Reviewers were unanimous in their high scores, with multiple reviewers raising scores after a detailed and thorough rebuttal from the authors which included additional empirical results. There's some uncertainty still around how meaningful the theory is, but reviewers are happy to leave further investigation of this to future work.
justification_for_why_not_higher_score: While it's a strong paper, the overall gains are modest, and the method is can be explained quite concisely. While a short talk would be nice, I don't think there is a need for a longer one.
justification_for_why_not_lower_score: I think the paper would have broad interest in the community, and there are open questions around scaling and theory which maybe others would be able to follow up on. So, I believe a spotlight could be fruitful.
Decision: Accept: notable-top-25%