Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: In this paper, the authors mainly study how to sample good/informative negative examples for contrastive learning. The key challenge is the unsupervision in contrastive methods.  They propose a new unsupervised method to select the hard-negative samples with user control. The experimental results on three modalities (images, graph and sentences) show the effectiveness of their method. 

Strength.
This paper is well written and easy to follow. 
This work mainly focuses on how to sample informative negative examples in contrastive learning. Targeting at this problem, they propose a new hard negative sampling with theoretical analysis. 
The authors also do lots of comparisons on multiple modalities dataset to indicate the effectiveness of their method. Besides, they also do interesting ablation studies, in Section 6, for example, to investigate the effect of the more harder samples and debiasing. 

Weakness. 
This is an interesting and important problem. I have noticed that, there is another paper released on ArXiv to deal with this similar problem at the same time. (Hard Negative Mixing for Contrastive Learning). It is unfair for the authors to do experimental comparison, while I might suggest that if possible the authors might just do an analysis comparison without any experimental results.

Visualization. If possible, the authors might give more visualization examples, such as t-SNE or some numerical values to show the distances between anchor and the sampled hard samples with different hardness on the batch on three modalities, including images, graph and sentences. For example, just like the Figure 1, the authors might show some sampled negative sentences by typical method and their method. For the proposed hardness, maybe they could show some sampled sentences with different hardness, as an additional visualization. Besides, if possible, they could also show some similar figures like Figure 5.

review_title: Contrastive Learning with Hard Negative Samples

final_score: rating: 6: Marginally above acceptance threshold
review_content: Update:

The revisions are good. The paper is very easy to follow and most of the story is pretty clear. Theory sections are clearer as well. So I'll improve my score as the authors followed through with both mine and other reviewer's comments. There's one hitch: Pr1, the one having to do with the labels, is not well substantiated in the paper, though it gets first-class treatment in Fig 1 as well as being one of 2 main principles guiding this method. Some of this is carried over from the de-biasing work, but I have concerns that there's essentially a trade-off between hardness and label distribution depending on beta. Unfortunately, this paper does no empirical analysis on the labels in q, and I worry that readers may be mislead that something close to Fig 1 might happen in practice.

====

This paper essentially extends / iterates on [1], using a different proposal distribution for the infoNCE loss. In this case, it's a type of exponential distribution with a weighting hyperparameter beta which allows the model to concentrate the distribution of negative samples around those which have high score. As they are building off of [1], they also get the debiasing effect from that work.

This is a fine idea and it seems validated by the experiments. My first comment is there's a few missing works. 1) [2] also showed that using different proposal distributions for the infoNCE loss to increase the hardness of the contrastive task. In that case, they cover several types of distributions. 2) More or less I disagree that contrastive learning need be unsupervised. There are existing works (e.g., [3] called CMDIM) that use labels to generate a mixture distribution of positive samples that come from the same instance as well as from other instances of the same class. They also omit same class from negative samples. Really, contrastive learning should be able to leverage any information available to generate similar tasks for the model to solve. This could be thought of as a hybrid between contrastive and metric learning, but I see no reason to complicate the naming of things.

Other remarks:
* Much of the intro regards contrastive learning, augmentation, and mutual information. As such, proper credit needs to be given to [4].
* The use of the word "label" on the last paragraph second page is a little confusing as the context here is unsupervised learning. Could you clarify what you mean here? (same as first full paragraph 3rd page)
* Q is a constant brought in from [1], it would be nice to know what this means in this paper and why it's introduced without having to read that one work.
* page 4 "rejection sampling... could be slow". Are there any experiments to support this? Rejection sampling would be easy to implement, so I'm not sure I'm comfortable with discounting it so easily here.
* You are making a lot of empirical estimations of things, particularly of the partition functions. I feel like bias / variance analysis is necessary here.
* Page 5 you introduce the debiasing idea, which could be made clearer in this work.
* The explanation at the end of 4.1 is very confusing to me or not clear. Could you explain more clearly why q_beta represents a tractable approximation for large beta?
* Page 5 "representation generalizable": generalizable to what? Downstream tasks, test distribution? I'm not sure what follows with the ball packing relates to generalization.
* Figure 2: why were those betas chosen?
* 6.1: this would be a great place to mention CMDIM [2]
* For the annealing experiments, wouldn't it make more sense to anneal beta up (progressively harder) than down?

One last remark is the paper borderlines iterative from [1]: there are some interesting new things, but not nearly as much analysis or comparisons to other proposal distributions to make this a significant contribution. Including some of the baselines from [2] might help as well as more bias / variance analysis of the empirical estimators used here would help.

[1] Chuang, Ching-Yao, et al. "Debiased contrastive learning." arXiv preprint arXiv:2007.00224 (2020).
[2] Wu, Mike, et al. "On Mutual Information in Contrastive Learning for Visual Representations." arXiv preprint arXiv:2005.13149 (2020).
[3] Sylvain, Tristan, Linda Petrini, and Devon Hjelm. "Locality and compositionality in zero-shot learning." arXiv preprint arXiv:1912.12179 (2019).
[4] Bachman, Philip, R. Devon Hjelm, and William Buchwalter. "Learning representations by maximizing mutual information across views." Advances in Neural Information Processing Systems. 2019.
review_title: Review of "Contrastive Learning with Hard Negative Samples"

final_score: rating: 7: Good paper, accept
review_content: The paper proposes a novel noise contrastive estimation (NCE) objective that incorporates hard-negative samples without similarity supervision, e.g., assuming unsupervised learning. To this end, it modifies the denominator of the original NCE by (a) re-weighting the negative samples based on the euclidean distance from the anchor point, and (b) considering a de-biasing of the effect of positive samples (that should be near to the anchor). Experimental results show that the proposed objective outperforms the pure SimCLR and its de-biased-only variants in many but not all cases in image, graph and text domains. 

Overall, I found the paper is well-written, with a clearly-motivated method. I also liked their theoretical analysis on the method. Experimental results can be a weakness of the paper for some readers in several aspects: e.g., lack of large-scale experiments, and the mixed results on comparing the method with the "debiased" baselines. Nevertheless, I think it is ok considering that the paper instead has provided an extensive evaluation over multiple modalities.

- Section 5.1: There could be a more justification on why the proposed method works not better than "Debiased" on CIFAR-10. I thought Section 6.1 would handle this, but apparently it seems not.
- Figure 4: Why the results on CIFAR-10 are not presented? It would be nice to give more information for the readers on why the method works less effectively on that dataset.
- It was a bit confusing for me to follow Eq. 3 or 4 before I noticed that q is conditioned on x. Although the paper mention that x will be omitted in the context (p2), I think there could be some place to remind this for better clarity.
- The paper could further provide a practical guide on how to choose tau^+.
review_title: Official Blind Review #1

final_score: rating: 7: Good paper, accept
review_content: Summary:

This paper investigated how to sample informative/hard negative examples for self-supervised contrastive learning without label information. To tackle this challenge, this paper proposed an efficient tunable sampling distribution to select negative samples that are similar to the query when the true label or similarity information is not accessible. Positive-unlabeled learning is used to address the challenge of no label, while the importance sampling technique is used for efficient sampling.

My main concerns are (1) how to distinguish hard negative examples and same-class samples as Fig.1 depicts, (2) how to sample $v$ in Eq.(4) to estimate the expectation.
 
Pros: 

\+ This paper is the first to propose a hard negative sampling for unsupervised contrastive representation learning.

\+ This paper provides a theoretical analysis of the proposed method that can tightly cluster similar inputs while departing the clusters from each other.

\+ The proposed method can be easily implemented with few additional lines of code.

\+ Experiments are conducted on several datasets (STL10, CIFAR100, CIFAR10). The proposed method works well even with a small number of negative samples.

\+ This paper has a high writing quality. The paper is clearly written and well organized. The motivation, challenges, and contributions are clearly stated.

\+ This paper shows plenty of visualized results to intuitively and detailedly show how the proposed method works.

Cons:

\- The experiments are conducted only on small datasets. Experiments on larger datasets, including Imagenet-1k and Imagenet-100 are not provided, especially the latter. The most related work, debiased [1], has conducted experiments on Imagenet-100.

 
Questions: 

It is not clear to me how to distinguish hard negative samples and same-class samples. Taking Figure 1 for example, how to distinguish 'oak' from other types of trees without labels?

In Sec. 3.1, $\beta$ is used to meet Principle 2. Since $\beta $ is like the temperature in softmax for scaling and does not change the order/rank of $f(x)^Tf(x^-)$, it is not clear how using $\beta$ satisfies Principle 2.

As shown in Eq.(4), estimating $E_{v\sim q_{\beta}^+}$ requires sampling $v$ from $q_{\beta}^+$. Are there any comments or ablations on the number of samples like Fig. 4(c) in [1]?

The paper focuses on hard negative samples mining with a relatively small number of negative samples (i.e., less than 512). Since memory-bank/queue-based methods like MoCo [2] has a relatively large number of negative samples (i.e., 65536), is it possible to improve the performance of MoCo, or reduce the number of negative samples?

References:

[1] Ching-Yao Chuang, Joshua Robinson, Lin Yen-Chen, Antonio Torralba, and Stefanie Jegelka. De- biased Contrastive Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[2] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9729–9738, 2020.










*******************************************

Final decision: 

I would keep my score unchanged. 

As for Principle 1, the authors said that upholding Principle 1 is impossible with no supervision, and they proposed to uphold Principle 1 approximately. This is acceptable to me as they build on ideas from positive-unlabeled learning.

This paper is clearly written and well organized. Both empirical and theoretical analysis is provided. The feedback addressed my concerns well.
review_title: Good Submission

Meta-review: This paper proposes a contrastive learning framework that leverages hard negative samples for self-supervised training. The proposed framework is theoretically analyzed and its efficacy is examined on several datasets/problems. A group of expert reviewers reviewed the paper and provided positive ratings for this paper. I agree with the reviewers and I recommend accepting this submission. 

One of the main discussion points among the reviewers was to what degree Pr1 is "approximately" satisfied in the proposed framework. There are several approximations in this paper that are not fully analyzed.  Some of these approximations could be examined assuming that labeled data is available during training. For example, $p_x^+$ is approximated using a set of semantics-preserving transformations. In practice, the distribution induced by augmenting $x$ is very different than the distribution that samples from the instances in the class of $x$. The effect of this approximation could be easily examined by sampling from true class labels. Additionally, it would be very helpful to visualize how $q$ samples from the negative instances and how much it follows Pr1.

I would like to ask the authors to add a small limitations section to the final camera-ready version that lists all the assumptions and approximations made in this paper. Please provide a high-level analysis on how such assumptions could be validated or such approximations could be measured if labeled data or additional information was provided. This discussion is extremely important for future practitioners to understand the basic assumptions that may not hold in reality and it will enable them to improve upon this work. 

Decision: Accept (Poster)