Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the InfoNCE loss widely used in contrastive learning from the view of Lovasz theta function. In particular, regardless the positive-pair term of InfoNCE, minimizing InfoNCE corresponds to solving the Lovasz theta function. Inspired by this, the authors relax the constraint of Lovasz theta function beyond orthonormality, and revise the InfoNCE accordingly. Experiments show that the proposed weighted InfoNCE achieves an improvement of 1% in the supervised case and up to 4% in the unsupervised case.
strength_and_weaknesses: Strength:
- The view of Lovasz theta problem is interesting.
- The proposed loss achieves significant improvement on empirical performance.

Weaknesses:
- This paper can only deal with the negative-sample part of InfoNCE and ignores the positive-pair part. The quality of a representation should be affected by these two factors together and these two factors are not independent. 

- The relaxation (7) of the original problem (2) is not intuitive. Why do the authors explain the upper bound of  $u_i^T u_j$ as a similarity? Is the minimum similarity equal to zero? In the unsupervised case where CLIP is applied, the similarities could be [-1,1]? In summary, the authors should explain more about how to interpret the weight $w_{ij}$ in the weighted Lovasz theta problem as a similarity.

- I carefully read the proof in the appendix. I find that (12) should include another constraint that $k>1$. Otherwise, (11) and (12) are not equivalent. Also, (15) should include the constraint that $t<0$. For example, (15) always has a feasible solution of $t=1$ while (11) may not have any feasible solution (e.g., $E$ is empty and $d<N$). Similarly, (31) also needs $t<0$. But this is weird: Since $w_{ij}>0$, the upper bound of $v_i^Tv_j$ becomes the weighted average of $1$ and a negative value $t$.

clarity,_quality,_novelty_and_reproducibility: - Clarity: This paper is well-written and easy to follow.
- Quality: The proof may not be rigorous. The formal version of the main theorem should not be hidden in the appendix.
- Novelty: The novelty is limited since it only considers the negative sample part of InfoNCE. However, the alignment of positive samples may be more important for contrastive learning, since several methods such as byol/simsiam only consider the alignment and can achieve good performance. At least, the author should discuss the importance of the negative sample part.
summary_of_the_review: Overall, the idea is interesting and novel. The empirical performance is impressive. However, this is an unready paper. A number of issues need to be closed, especially the rigorousness of the theory part and how to interpret the weight $w_{ij}$ as a similarity. This paper needs to be further polished before acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors established a connection between contrastive learning and the Lovasz theta problem. They show that with certain assumption the original loss function corresponds to Lovasz theta with an empty similarity graph. Then, by considering Lovasz theta on weighted graphs, they designed a new loss function that incoporates prior knowledge of similarity between examples. Experiements are performed to show that their method can be used to improve both unsupervised and supervised contrastive learning. 
strength_and_weaknesses: Strength:
1. The paper provides a new view of contrastive learning by showing its connection to the Lovasz theta problem, which may help further the understanding of contrastive learning.
2. The proposed loss can be used to boost contrastive learning with any prior knowledge on similarity between examples. 
3. The proposed method can be seen as a new way of using information from pretrained models and transfering the useful knowledge in them to new relevant tasks in the context of contrastive learning. It is more flexible than finetuning since it does not require the model architecture to be the same as the pretrained one. 

Weakness:
1. Theorem 4.1 only shows that the negative pair part in the loss is equivalent to Lovasz theta. The positive pair part is nullified by the assumption of the single positive case. This makes the result less informative considering that the positive part can play an important role. For example, [1] has shown that it encourages alignment between positive pairs and has certain interaction with the negative pair part which corresponds to uniformity. 
2. It is unclear what the quality of representations given by CLIP is. I think most likely it would not be very high, but it is still important to clarify since otherwise there is always a possibility that the CLIP representations are already good enough and it is trivial to beat the baseline by aligning the similarity output by the model with the good-enough representations'. 
3. More clarification is needed on the confusion matrix used in experiments. The authors said it is given by a model pretrained using supcon. But what is the setup for the pretraining and how long has the model been trained? what's the linear evaluation accuracy on its representations? Without knowing the answers to the above questions, it is hard to judge if the corresponding experimental results are meaningful. 

[1] Wang, Tongzhou, and Phillip Isola. "Understanding contrastive representation learning through alignment and uniformity on the hypersphere." International Conference on Machine Learning. PMLR, 2020.
clarity,_quality,_novelty_and_reproducibility: Clarity:
1. Based on the equivalence to Lovasz theta, I wonder if more can be said about the learned representations, e.g., the geometry of learned representations and even their effect on generalization in downstream task.
2. Clarification on the quality of CLIP representations and confusion matrix is needed.

Novelty:
1. The main insights of the connection between contrastive learning and Lovasz theta, and leveraging the connection to derive a generalized version of loss are novel and can be important to the field. The idea of incoporating prior knowledge of similarity into contrastive learning is also novel. 

Seems the proposed loss function explicitly encourages non-uniform pair-wise similarity. It would also be interesting to see if this can help address some other problems in supervised contrastive learning, e.g., class-collapse.
summary_of_the_review: The contribution of the paper is two fold (1) it showed the connection between contrastive learning and Lovasz theta, which is a novel viewpoint of contrastive learning (2) and subsequently proposed a loss function that incoporates prior knowledge of similarity. However, the connection to Lovasz theta doesn't yet provide much insights into properties of the learned representations, since there is no further discussion about this in the paper. This may limit its theoretical contribution. Some details are missing in the experiment section. Also, I wonder if one should also expect that adaptively adding similarity information obtaind from the representations given by the current model every certain epochs during training can also improve the performance (i.e., training -> updating similarity matrix using current representations -> training -> updating -> training ...)
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper establishes a connection between the Lovasz theta function and contrastive learning. Specifically, with InfoNCE - a type of contrastive loss function used for self-supervised learning. They define a novel loss function - Lovasz theta contrastive loss based on a weighted graph representation of the similarities between examples.. 
The loss function is evaluated with various ways of quantifying sample similarity. The method outperforms existing model SimCLR in both supervised and unsupervised contrastive learning. Previous works introduce the notion of using graph representation with edge weights equal to the probability that two samples correspond to views of the same sample. Current work uses that representation to perform contrastive learning. Under certain choices for model dimensionality and batch size, the paper shows an equivalence between minimizing InfoNCE loss and the Delsarte formulation of the Lovasz theta problem.
This equivalence is shown in both supervised and unsupervised cases. The equivalence is used to incorporate degree-of-similarity information into contrastive learning. So this method is a generalization of regular contrastive learning. In unsupervised cases, the method outperforms regular SimCLR pretraining on CIFAR100. In the supervised case, the method outperforms simple cross entropy loss and supervised contrastive learning on CIFAR100 and ImageNet-100. The method can be used with any similarity measure to create a problem specific contrastive loss.
As a proof of improvement, the work plots the effect of blending regular contrastive learning with the degree-of-similarity aware method they created. A parameter λ = 0 (regular SupCon) to λ = 1 (their method) is used to blend the effect of setting the class similarity matrix as C’ = λC + (1 − λ)I. It shows an overall improvement in performance as λ increases.
The work links the field of contrastive learning to classic graph theory and semi-definite programming. By doing this, it tries to provide a direction to understand the underpinnings of contrastive learning. 

strength_and_weaknesses: The paper introduces a new loss function and provides proof that the minimization of certain terms in the proposed loss function is a relaxation of the weighted Lovasz theta function. To do this, they start with a very widely-used contrastive loss function - InfoNCE. They prove that minimizing InfoNCE is the same as minimizing a certain formulation of the Lovasz theta function. This provides a strong basis for the theory of contrastive learning. Additionally it provides a way to include similarity metrics into contrastive methods.

However, the results showed minor improvements in performance from SimCLR. It is also prudent to compare the method with other SoTA self-supervised learning methods that learn fine-grained granular features like MUlti-Granular Self-supervised learning (Mugs). We advise the authors to do this as it will help measure the effect of using similarity metrics in this particular loss formulation on performance. 

clarity,_quality,_novelty_and_reproducibility: The work is presented clearly with necessary introduction of current work and explanation on how it builds upon the same. The contribution is novel and original as it bridges a previously unexplored bridge between contrastive learning and graph theoretical approaches and semi-definite programming. The paper provides all analytical proofs stated. It also provides code and selection of hyperparameters to help with reproducibility. However, the paper does not refer to any previous runs / logbooks of trails. This will provide a way for readers to understand the way the problem was approached.
summary_of_the_review: The paper provides an contribution of bridging the field of contrastive learning with Lovasz theta functions and graph theory. We think it will pave the way for incorporating more similarity metrics into contrastive learning methods. The paper provides excellent explanations of contrastive learning functions therefore it is valuable for a wide audience.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work points out an interesting connection between Lovasz theta function and contrastive learning. More concretely, the negative term in the InfoNCE loss corresponds to the Lovasz theta problem, with zero weights. From this connection, the authors are able to extend the InfoNCE loss to a broader class and the experiments show some improvement over SimCLR.

--post rebuttal--

Thanks to the authors for the rebuttal. After the revision, the paper looks better. However, the main contribution seems less novel to me. The connection Theorem 4.1 is somehow known in contrastive learning, for example, Theorem 5 (revised version) in https://sslneurips21.github.io/files/CameraReady/f-MICL-NeurIPS-workshop.pdf (the exact form is slightly different but it can extend to the current paper). I think the main novelty is the extension to different similarity weights, but the comparison with baseline algorithms is limited (only MoCo, SimCLR and SupCon). More SSL baselines are needed, e.g., SimSiam, BYOL, SwAV, etc. Also, the similarity term $w_{ij}$ needs to be discussed more. 

For the fair comparison part, I don't understand the author's comment. Why can't we use CLIP as a pre-trained model for SimCLR? In this way, both Lovasz and SimCLR would have the same prior knowledge.

In summary, despite being interesting, I think this paper does not have enough contribution to be accepted, and I disagree with Reviewer 4DeW that it should be given the highest score of ICLR.
strength_and_weaknesses: Strengths:
1) The connection between the negative term of InfoNCE and Lovasz theta problem from graph theory is novel. The generalized version also makes sense, since the weight $w_{ij}$ represents the similarity between samples $i$ and $j$.
2) The authors test the Lovasz generalization to both supervised and unsupervised cases, and show that the linear fine-tuning accuracy can be improved over SimCLR and SupCon.
3) The supplementary code is attached for reproducibility.
4) The similarity function can be defined from existing feature encoders such as CLIP. This is a highlight of the current work.

Weaknesses:
There are indeed some places where this draft can be improved. 
1) Minor issues of writing/typos: some informal abbreviations: "doesn't", "s.t."(eq. (3)), "don't", "aren't"; parenthesis in Theorem 3.1
2) The connection part could be written more clearly. Some insights from the appendix can be summarized in the main text. For example, the Jensen's inequality of the negative term leads to a constrained optimization problem w.r.t. the inner products, and thus the Lovasz theta problem. 
3) The 2nd assumption in Sec 4.1 doesn't seem necessary. One can just say that the negative term relates to the Lovasz theta problem.
4) The comparison between SimCLR and the proposed method is a bit unfair: the Lovasz theta method uses CLIP as some prior knowledge, but this is not used in SimCLR. Also, only SimCLR and SupCon are compared while there are many competitive contrastive learning methods such as MoCo (v1, v2, v3) and SimCLRv2.
5) The theoretical analysis is not strong enough. Although the paper finds equivalence and extension of InfoNCE, it doesn't show any theory of convergence or generalization property.

clarity,_quality,_novelty_and_reproducibility: Clarity: see above.
Quality: the paper is reasonably well written with supporting experiments
Novelty: the connection to Lovasz theta problem is novel
Reproducibility: the authors attach code for reproducibility check
summary_of_the_review: In summary, my recommendation of the paper is mixed: on the one side, the connection with Lovasz theta problem is defintely interesting and opens up a new approach for finding similarity function; on the other side, this connection is not well explained in the main paper and more empirical comparison is needed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper shows that minimizing the InfoNCE loss widely used for contrastive learning corresponds to solving the Lovasz theta function. Empirically, the authors show that the proposed weighted InfoNCE achieves an improvement of 1% in the supervised case and up to 4% in the unsupervised case.

A meeting was held to discuss the paper in detail. The reviewers and I agree that the theoretical formulation is indeed very interesting and novel. 

However, the first concern is that the formulation does not capture the effect of the positive pairs which is shown to be crucial for the performance of CL. Besides, empirically, the paper shows that the proposed method outperforms SimCLR and SupCon. But, as I mentioned in my comment to the authors, from the current experiments it is not clear if the performance boost is due to the help of the supervision from CLIP or is due to the contrastive loss proposed by the authors. For a fair comparison, the authors may compare performance of different contrastive methods while incorporating the same similarity information from CLIP in a naive way (e.g. by weighting the negative pairs by some function of their similarity), with their proposed formulation. This will confirm the effectiveness of the proposed formulation and will significantly strengthen the paper.

Therefore, while the paper has a great potential, it may not be ready to be published in its current format.

justification_for_why_not_higher_score: Explained in part 1.
Decision: Reject