Self-Supervised Learning with the Matching Gap

[Evaluation] The evaluation section could have been more comprehensive. For example, when strong data augmentations are involved (Table 1), only several SSL baselines are included, e.g. MoCo-v3, DINO. The settings shown in Table 1 are also not consistent, e.g. different number of epochs, which makes it difficult to interpret the results, e.g. could the proposed method match DINO’s performance when trained for the same number of epochs? Also, it would be beneficial to include architectures beyond ViT-B(L)/16, e.g. ViT-S, CNN, etc.

■ In presenting (and evaluating) MG, our focus was not to reach SOTA performance, but to suggest a simple alternative to contrastive SSL losses that can naturally avoid collapse. We do show that a “lean” implementation of the MG loss leads to comparable results to SOTA. Instead of chasing SOTA, we used our compute budget to explore MG’s performance over diverse settings (decreasing amount of augmentations, removing momentum encoder and predictor heads, or other experiments in section A.3 “Additional ablation studies”, results over smaller datasets (CIFAR-10, CIFAR-100, and SVHN) using ResNet-50 as backbone). We found that MG is consistently near or at the top, despite being much simpler conceptually than most approaches. Following your (and other reviewers’ comments), we are now running additional experiments, to study impact of #epochs.

[Performance] With strong augmentations, the proposed method shows no benefit compared to SOTA methods. The method outperforms several SSL approaches with weaker augmentations. However, at least from the application perspective, it is unclear to the reviewer what are the advantages of using only weak augmentations, especially when the training epochs are the same.

■ As mentioned in our introduction, increasing the variety/strength of augmentations can be seen as a way to mitigate the tendency of contrastive losses to force instances of the same image to collapse in representation space. However, as nicely presented by Assran et al. 2023 the reliance on hand-crafted data augmentations is limiting and may introduce unwanted biases. With that, we find that attaining good performance with a smaller number of epochs, and a smaller set of augmentations, is a worthy direction. Besides, this can be also useful in settings (e.g. biomedical data) where the number of “natural” augmentations is more limited than in vision tasks (and where even testing the hypotheses that many augmentations are needed, or not, is harder).

[Claim] Some of the claims are not well-justified. For example, i) compared to CL that may “collapse representations for very different images”, the proposed method learns diverse representations for different views of the same image; ii) stronger data augmentations could help mitigate the representation collapsing problem. In order to justify the claims, the authors may measure/compare the mean distance of different views of the same image, or different samples of the same classes, across different models (i.e. the proposed method and baselines) and settings (i.e. strong/weak augmentations).

■ We thank the reviewer for this suggestion. We are now evaluating statistical properties of the representation space of MG and alternative approaches, under different augmentations of the same image. We will update the response once we have results, and hope to include it in a revised manuscript version within the rebuttal period.

[Overall] the paper studies an interesting topic, the proposed method is also technically sound. However, he reviewer has concerns about the evaluation, performance and some of the claims in the paper. At this moment, the reviewer rates the paper as marginally below the acceptance threshold.

■ We hope that our response to the points presented above helped lift some of your concerns, and will be happy to answer any additional questions.

The reviewer expects apples-to-apples experiments and justifications about claims, as in the reviewer’s humble opinion, these are also expected by the ICLR audience, that the readers can interpret the results without speculation and get convinced by the claims. Eventually, the aim is to make it easier for the readers to learn the potential advantages of this work.

Given the pre-rebuttal results presented in Table 1, it is unclear to the reviewer if MG could match DINO when trained in the same number of epochs (i.e. 400). The rebuttal clarifies that MG's performance peaks at 300 epochs, making it less effective than DINO. Therefore, the readers may learn little about the advantages of MG in Table 1. Similarly, the reader may also learn little in Table 2 as the performance gaps, either positive or negative, are marginal. In Table 3, the reader may speculate that, with weak augmentations, how does MG perform compared to the baselines presented in Tables 1 and 2, as they are not included in Table 3. The paper also lacks convincing evidence for other claimed benefits of MG, like sample diversity (strongly indicated in the abstract) and simplicity,

The reviewer agrees with the authors that SOTA is not mandatory for ICLR and appreciates the authors’ exploration of an alternative, potentially “simpler” loss that may yield more “diverse representations”. However, the reviewer cannot find solid justifications for such advantages in the current revision.

The authors are encouraged to further showcase other potential benefits of MG that can be easier to evaluate, e.g. memory usage, etc.

IOT vs MG. I Wonder if it improves the training speed/convergence or reduces the memory consumption?

■ Our MG approach will be at least twice as fast when it comes to computing the loss and its gradient, since only requires a forward pass. It will also be more memory efficient if one chooses to unroll the Sinkhorn solutions, or even faster if one chooses to differentiate implicitly the OT solution (see e.g. Luise et al. 2018), which requires solving a $n\times n$ linear system.

That being said, in the large-scale setting that we have used — notice that IOT (Shi et al. 2023) was never evaluated on ImageNet — the overhead of running a ViT-B architecture far dominates the costs of running Sinkhorn when using a small batch size of 128, a fairly large entropic regularization ($\epsilon$). The loss computation, whether MG or IOT, is negligible. The speedup of MG vs. IOT did not, therefore, play an important factor in the overall compute cost. As we mention in the conclusion, this tradeoff will change when using simpler feature architectures, larger batch sizes, or, as mentioned in the conclusion, considering other OT approaches that cannot be differentiated (e.g. low-rank solvers).

Unfair comparisons. The implementation of the experiments largely followed the setting of Dino, which used two global crops and ten local crops by default. However, some of the baseline methods, e.g., MoCov3 and I-JEPA, used only two global crops, making it unfair to directly compare the performance with MG loss on the default setting. Even under the potentially unfair comparison, the performance of MG loss is only comparable and sometimes even inferior to the contrastive loss.

■ In presenting MG our goal was not to suggest a combination of tricks that could reach SOTA performance, but rather to provide a conceptually simple alternative to contrastive SSL losses, with the hope that, when applied in “naively”, its performance will be consistently comparable or better than far more complex approaches that use several tricks. We believe we have delivered in that sense.

Following this objective, we have used our computation budget to explore a variety of settings that showcase the robustness of MG, the simplifications it allows for, as well as its shortcomings.

We indeed relied on reported performances for baseline methods in the most comparable setting (e.g. matching backbone architecture). Here, it is important to note that while indeed the number of crops provides an advantage for MG in a majority of cases MG is evaluated over a significantly lower number of epochs.

At last, specifically concerning the comparison to I-JEPA, Assran et al. (2023) present the new setting, Image-based Joint-Embedding Predictive Architecture, in which the construction is by definition different: for each image, given a context block, predict the representations of various target blocks, where $M$ (typically setting $M=4$) non-overlapping targets are chosen. Hence, it is not straightforward to define an exact fair comparison between these settings.

Some notations are used without first introduced, e.g., $c$ in Introduction and $t$ in Sec. 3.

■ $c(\cdot,\cdot)$ is simply a cost, this was defined at the beginning of Section 2.2, we now mention it earlier in the intro when first introduced. The function $t(\cdot,\cdot)$ was defined in Equation 3 (using the $:=$ symbol). We have now split it to make it more visible and clear.

Overall, I think the proposed loss is interesting, and I like the presentation of this paper. However, the evaluation part still has significant room for improvement.

■ We thank you for highlighting these positive aspects of our paper. We thank you for your several comments and suggestions. We hope that you can appreciate that we have decided to focus our compute budget on various ablations, rather than aiming for a SOTA performance in a specific setting. Ultimately, we believe the picture we provide, where the contribution of MG is better outlined, isolated, and ablated, paints a more convincing picture.

The proposed method is an extension of the paper "Understanding and generalizing contrastive learning from the inverse optimal transport perspective”.

■ We respectfully disagree. While it is true that both our (MG) and (Shi et al. 2023) methods use optimal transport to define a SSL loss, our method cannot be characterized as an extension of (Shi et al. 2023). A single level optimization problem cannot be described as an extension of a bilevel problem.

We make this distinction clear several times in the paper, going as far as citing and differentiating us from (Shi et al. 2023) 14 times. In the introduction, we chose carefully our words, writing “draw inspiration from (Shi et al. 2023)” (i.e. not “extend”). We credit (Shi et al. 2023) with an entire paragraph to introduce their approach (“Inspiration : …” in p.5), insisting on the bilevel optimization approach taken by (Shi et al. 2023). We then clearly lay out the differences in section “Our Contribution” which is single Level.

Instead, MG can be better described as an extension of infoNCE, blending the negative sampling idea of (Robinson et al. 2020) with the gap perspective outlined in Monge Gap (Uscidda and Cuturi 2023). We will

The novelty of this paper is rather limited. This article only uses a previously proposed technique to improve the computational complexity of inverse OT-based contrast loss in the optimization process.

■ We respectfully disagree, our method was not proposed previously, and our goal is not to improve the computational complexity of inverse OT. Improving inverse OT would require carrying out a more efficient differentiation of $\rm{argmins}$ solutions (using e.g. unrolling or the implicit function theorem). Instead, our method bypasses those challenges entirely thanks to a different formulation, resulting in a much simpler optimization.

Hard to follow. There are many mathematical symbols and proper nouns that lack explanation. For example, what is t in eq. 6 and 7, what is bistochastic matrices, and what are the difference between matching cost, measuring agreement, matching gap, and optimality gap?

■ We regret that the reviewer found the paper hard to follow. The function $t$ is defined in Equation 3 ($:=$), in the revised manuscript we have made this definition more apparent; The definition of bistochastic matrices is provided in Section 2.2, $\mathcal{B}_n$, and is a standard concept (see. E.g. https://en.wikipedia.org/wiki/Bistochastic_matrix); The “matching cost” is defined in Equation 3; “Measuring agreement” is used in a sentence to describe the IOT loss (“Inspiration: Measuring Agreement using Inverse OT.”). This refers directly to a sentence above, “In such cases, OT can be used as a way to quantify whether locations (xi, yi) are in agreement with the diagonal pairing”; The matching gap is the name of the method we introduce; The optimality gap, or “gap to optimality” is a common concept in optimization, quantifying to what extent a solution is not optimal. We use this reference to highlight that the matching gap is simply the objective value of $J_n$ vs. the best possible objective value, as in Equation 7.

The organization of Section Introduction is superfluous. I cannot find the relationship between the first two paragraphs and the last paragraph.

■ We wrote the 3 paragraphs of the introduction to highlight the following blocks: context: the first paragraph provides context, introducing the importance of SSL with a contrastive view. problem: the second paragraph highlights that SSL has weaknesses due to feature collapse, which have been identified by previous works as arising from the promotion of invariance by contrastive losses such as InfoNCE solution: the third paragraph details our contribution to solve the problem above, the matching gap.

In the revised manuscript, we give these paragraphs an explicit title to clarify further the structure above.

Dear reviewer,

We would like to address your response above. Despite our rebuttal and attempt at clarifying your concerns we are afraid there are some misunderstandings we turn to clarify.

Comment: 1. About novelty: 1) the authors have not explained why the bi-level problem is necessary and effective; 2) improving the computational complexity of inverse OT have been addressed many time in the OT field. Apply this in contrastive learning is not innovative at all.

■ 1) As we present it in the text “Our Contribution: Single Level Optimization with the Matching Gap” and attempted to explain in our previous rebuttal response, MG avoids a bi-level problem, hence it is unclear why we should clarify that a bi-level approach should be necessary or effective. Our message is the opposite, bi-level is not needed. If there was a mistake in your wording above, and your point was the opposite of what you wrote (you expect us to explain why bi-level is not necessary nor effective), then we refer you to our answer to reviewer tJTN for a discussion of this aspect.

■ 2) We are not improving the complexity of Inverse OT in our paper, nor extending inverse OT. We are only using OT (forward computation, no backward) for SSL. MG is a direct approach that avoids bi-level and inverse notions completely. This is presented in the paper, with a dedicated section “Our Contribution: Single Level Optimization with the Matching Gap” as well as following discussion. In addition, in the rebuttal we have described this in our responses above to your questions,

• ”The proposed method is an extension of the paper "Understanding and generalizing contrastive learning from the inverse optimal transport perspective.”

• “The novelty of this paper is rather limited. This article only uses a previously proposed technique to improve the computational complexity of inverse OT-based contrast loss in the optimization process.”

2. The authors claims that the aim of this paper is to explore the robustness, the shortcomings, and the ability of the MG. However, regarding the performance gain reported in this paper, I think this paper is overclaimed.

■ We would appreciate it if the reviewer could point out examples that we have overclaimed in that respect to allow us to tone down and/or relate to concrete claims.

3. The quality of the first draft was particularly low, containing many errors and ambiguities, and falling far short of acceptable standards. And in the rebuttal phase, the authors are not well interpreted and modified.

■ We were keen to see that other reviewers acknowledged the quality of writing and presentation. We do realize the work contained typos, however we find the above remark harsh and unjustified. Unjustified, because a score of 1 should be only used for trivially wrong or plagiarized papers.

We are very grateful for your encouraging comments, constructive review, and really great suggestions!

We wanted to start our rebuttal to your review with a few numbers that we were able to compile in the last week or so.

I think that this new form of loss would be better justified if there would be empirical evidence that supports the intuitions (in addition to the standard benchmarking and ablations). It would perhaps be interesting to see how the embeddings of an augmented batch behave, in comparison to standard NCE, or some statistics of that kind.

We agree, and we have been working on such a presentation.

2] The formulation is restricted to the 2-view setting. While this is simple, it would be interesting to know whether there are effective generalizations to multi-view settings.

This is indeed a very interesting avenue for further research.

3] There is no specification or discussion regarding batch size, which has an important role in contrastive learning. Supposedly, the compact computation and 2-view setup could allow for larger batch sizes. It would be interesting to see how performance scales with batch-size.

Thanks for this great suggestion. As can be seen in our general response above, we have investigated this aspect. We reproduce these results below for convenience. Using MG in a setting strictly identical to that reported in Table 1 (300 epochs over ImageNet), we obtain the following accuracies

As can be seen in these results, performance is fairly stable across $n$ sizes, and maybe suggest that for larger $n$, one might need to readjust $\varepsilon$ values. We are still running results for even smaller sizes (e.g. 16, 24) and will report them.

4] Several minor inaccuracies (which don't affect the analysis or correctness): (i) Bistochastic should be non-negative (ii) Should be <P,logP> in Equation 3 (without the -1) (iii) Last row of the loss equation is wrong, resulting in a matrix rather than a value: should probably be \eps<P,logP> instead of \eps\logP.

Many thanks for spotting these typos:

• (i) yes, we have added the "+"
• (ii) this "-1" is a convention that is adopted, for instance, in the computational OT book (e.g. https://arxiv.org/pdf/1803.00567.pdf Eq. 4.1, p.57). This helps rewrite the dual more elegantly, and also plays a role for unbalanced formulations, where the generalized KL is used.
• (iii) apologies for this ugly typo, now corrected.

Did you ablate on number of epochs, within the budget, to see if the dimnishing returns behavior is comparable to other methods?

Yes, we have ran this experiment, as reported above. As mentioned in the general remark, the performance did not improve markedly when going from 300 to 600, when keeping all other hyperparameters unchanged ($76.5$)

Due to the approach that does not require positives to converge to the same point - Perhaps there is actually room for more aggressive augmentation, that can exploit a richer extension of the training data?

This is a good remark. However, as we debate in the paper, we took the opposite direction, and did instead try to get rid of aggressive augmentations, to simplify the overall pipeline (see e.g. Table 3). Our intuition is that agressive augmentations are a form of regularization that is needed with InfoNCE.

As I know, DINOv2 and SwAV also use the optimal transport algorithm to solve contrastive learning. But I can not find the discussion about such methods in related work. I would like to find the discussion about the difference between Matching Gap and SwAV/DINO

■ Thanks for pointing this out. We agree that it is worth adding a discussion on this, which we did in the updated pdf, paragraph “Related works” in Section 3. To develop: optimal transport does indeed plays a role in SwAV (Caron et al. 2020) and DINOv2 (Oquab et al. 2023), where optimal transport, and more specifically the Sinkhorn algorithm, is used as a differentiable proxy to obtain a balanced $k$-means clustering of representations (i.e. each cluster must capture a similar amount of mass). Note that in DINO (Caron et al. 2021), Sinkhorn was replaced with Softmax (similar to a single Sinkhorn iteration), but was later reintroduced in DINOv2, following Ruan et al. (2022). Importantly, in both SwAV and DINOv2, OT is used as a low-level clustering routing, only indirectly involved in the final loss, which is a more standard KL-based quantity, on a discretization using those clusters. With that, because OT is used at an intermediate step, this requires, as in Inverse OT (Shi et al. 2023), differentiating the Sinkhorn iterations.

As for experiments. In Table 1, the performance of the Matching Gap is not as good as DINO, which is a strong baseline proposed 1 year before.

■ We agree that DINO (Caron et al. 2021) is indeed a strong baseline that builds upon SwAV (Caron et al. 2020), incorporating various tricks and a significant compute budget for hyperparameter optimization. In contrast to DINO, MG only proposes a novel loss function, and we show that only that loss can lead to several simplifications in architecture/training procedure, as shown in the various experiments we conducted. For instance, in contrast to Table 7 “Important component for self-supervised ViT pretraining.” in (Caron et al. 2021), which presents the importance of all components for training in DINO (with a complete failure in the absence of momentum encoder, row 2), our ablations show that MG is overall very robust, and able to work in various settings.

The author only conducts downstream experiments on transfer classification. Many self-supervised learning methods evaluate the downstream detection(COOC, VOC) and segmentation(COCO, aed20k) performance. I think the simple downstream classification task is not enough.

■ We thank the reviewer for making these suggestions. We are now conducting these evaluations and hope to include them in an updated version within the rebuttal period.

As mentioned above, we have been running a few experiments following reviewers' requests.

We can now report the following numbers, in response to questions raised by Reviewer iFzB.

• Impact of batch size on performance of the MG model, using ViT-B/16, in a setting strictly identical to that reported in Table 1 (300 epochs over ImageNet). Keep in mind that, due to parallelization across 32 GPUs, the total batch size for each gradient update is therefore 32 x $n$ (e.g. 6144 images when $n=192$) images.

As can be seen in these results, performance is fairly stable across $n$ sizes, and maybe suggest that for larger $n$, one might need to readjust $\varepsilon$ values. We are still running results for even smaller sizes (e.g. 16, 24) and will report them.

• Total Epochs: using the same hyperparameters, after 600 epochs, with batch size $n=128$, we can now report a performance of $76.5$, to be compared to $76.7$ reported after 300 epochs in Table 1.