Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper propose to sample effective hard negative samples in contrastive learning, conditioned on given anchor point. Authors proved that their new objective is a more biased lower bound than InfoNCE, but with less variance. Experiments on several datasets as well as transferring datasets show some promising results.

Pros:
- Conditional negative sampling in contrastive learning is currently less studied, and this paper starts on this direction.
- The relative improvement of the new objective function upon multiple popular contrastive learning methods have been verified.
- The strategy in final realization is easy to implemented (though this realization is not very closely coherent to their theoretical analysis). In the analysis, they specify expectation value c as bound, while in experiments, the tuning of w_l can be tricky and a bit hacky.
- The implementation can be simple, which I appreicaite.

Cons:
- The written is not very good. Specifically, I found the usage of p and q in section 3 is a bit hard to follow. Specifically, I did not follow the sentence, "The remaining probability mass assigned by p to elements outside S_B is renormalized to sum to one...", do you mean conditional p or marginal p, or else? Overall, the section 3 is not well clarified for me
- While the experimental explicitly remove "two closed" samples, this part is completely missing in the theoretical analysis. E.g., the authors did not discuss the cases that the c threshold in Theorem 3.1 is too high such that set B only contains positive samples.
- The authors do not prove, in experience, that whether such improvement still holds on more solid baselines with larger networks and recent contrastive learning tricks. E.g., how would MoCoRing works with MoCo v2 baseline with 800 epochs training of R-50 model on ImageNet?
- Specifically for MoCo which maintains a FIFO queue, I am not convinced that the improvement mainly comes from hard negatives. It might because it mainly comes from removing "too close" negatives which are false negatives. I am imagine the case that, if we have labels to remove all false negatives in MoCo for each anchor, then all remaining negatives are true negatives. Then, does it still help to remove easy negatives to certain extent, or it's better to keep all true negatives you have in the queue? This would be some interesting experiments to see.
- The results on MS COCO is way off. I do not believe that switching from R-50 to R-18 will lead such a significant drop in AP, e.g. AP of bounding box drops from ~38 to ~10. 

Overall, I have a mixed feeling over this paper, and would appreciate authors response. 

======= updated ======
The authors response partially addressed my concerns and I would raise the rating to 6.
review_title: Interesting direction, presentation and experiments need to be enhanced

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

Inspired by the effectiveness of hard negative mining in deep metric learning, this papers focuses on the problem of negative mining in unsupervised learning under the contrastive setting. One of the problems in this scenario is that naively selecting difficult negatives may yield an objective that no longer bounds mutual information, which is the basis for many contrastive objectives such as the Noise Contrastive Estimator. To address this problem, this paper formally defines a family of conditional distributions where negatives can be drawn from (negatives are chosen conditional on the current instance), while maintaining a lower bound on the NCE and on mutual information, resulting in a new estimator dubbed Conditional NCE. It also shows that, even though it’s a looser bound than NCE, it also has lower variance, which may lead to better local optima. Finally, within this family of conditional distributions, the paper proposes the Ring model, which takes inspiration from semi-hard negative mining approaches, and that can be applied to state-of-the-art contrastive algorithms in order to sample harder negatives, resulting in better representations.


# Pros

The paper tackles a typically disregarded problem in contrastive learning: hard negative mining. It shows the importance of selecting difficult negatives to obtain stronger unsupervised representations.

The method and contributions are very well motivated and introduced. The paper is also very well written, and includes a thorough review of the background needed in order to understand the proposed approach.

The strongest contribution of the paper is the definition of this family of conditional distributions, the CNCE, and the proof that it remains a lower bound on NCE, preserving the relation of contrastive learning to mutual information. Not less important is the proof that even though CNCE is a lower bound on NCE, it has however lower variance, leading to better local optima.

The Ring model results in a simple method that can be applied to any contrastive algorithm resulting in a better representation that outperforms existing approaches by a significant margin. This is shown in a thorough and extensive experimental analysis, which includes several benchmarks, transfer tasks, and ablation studies to validate the different components of the proposed approach.


# Cons

A minor comment is that the Ring model takes a lot of inspiration from other works in deep metric learning, which might limit its novelty. The concept of semi-hard negative mining is well-know in the field of deep metric learning and has been studied in numerous papers that have proposed more sophisticated approaches. I understand however that this wasn’t the main focus of the paper, being mainly paving the road to the exploration of negative sampling in contrastive learning.


# Recommendation

My overall recommendation is accept. The paper not only tackles a very important and typically disregarded problem in contrastive learning, but does it in a way that opens up the door to future research on this topic. It is also interesting to see hard negative mining from the mutual information point of view, making sure that by adding these conditional distributions the contrastive objective still remains a lower bound.

review_title: A good paper that tackles a very important problem in unsupervised learning

final_score: rating: 5: Marginally below acceptance threshold
review_content: 

Briefing:

This is an interesting paper that discusses the negative sample mining in visual representation learning. The authors discuss the theory and method to conditionally select the negative samples based on the dot product of representations in noise constructive estimation (NCE). Their theory shows that the NCE with negative examples sampling from a conditional distribution q is lower bounded with mutual information, and the object has higher bias and lower variance. The authors also provide the method to construct the conditional distribution by picking a ring surface where the dot product of representations is bounded within percentiles of data.

#######################################################

Pros:


The topic of this paper is popular and interesting. The negative sample mining strategy in unsupervised representation learning is well discussed and found effective in recent research.

The experiments show the effectiveness of their method compared with the original NCE methods.

#######################################################

Cons:


This paper's writing quality is limited, and this makes some points that are not easy to understand.

Why introduce many such details about IR and MoCo? It seems they are not heavily related to the contribution of this paper.

The paper limits the exploration of NCE to image representation learning with transform functions. This is not clear in the introduction section and may make readers confused about the contribution and purpose of the introduction. Can this theory and strategy be extended to other representation problems? 

The claim of Borel sets A in theory 3.1 is not clear enough. How would you actually define the A2 to Ak? The proof of 3.1 is also unclear, and the notations here are in a mess.

The motivation to choose the way to construct q is still unclear. Why chose the dot product as the condition to build q? What's the connection between the "ring discrimination" and theory 3.1? It seems the sample selection strategy is not well supported by the theory the authors claim.

#######################################################

Please address and clarify the cons above in the rebuttal period.

review_title: 1947 Initial review

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper adopts semi-hard negative mining, a sampling strategy widely used for metric learning, for contrastive self-supervised learning. Specifically, the paper chooses the negative samples in the range of $[w_l, w_u]$ percentiles (close, but not too close) in terms of the normalized feature distance. As the initial representation is not informative, the paper anneals down the percentile range. This sampling strategy improves the contrastive learning methods (IR, CMC, MoCO).

The paper has some good points:
- Applying semi-hard negative mining for contrastive learning is reasonable.
- Discussion on the property of the proposed estimator, CNCE.
- Empirically validate the proposed method improves the contrastive learning methods.

However, the paper needs more improvements for both method and presentation.


**Concerns in method**

A. Choice of the hyperparameters $[w_l,w_u]$.

Choosing "close, but not too close" samples is ambiguous and may depend on datasets, networks, and training methods. Is there some principle to choose hyperparameters? I checked both the main text and appendix but could not find how the paper selected the hyperparameters for experiments.

B. Cost of the negative mining

Searching negative samples for each update is quite expensive. How much the training time increased compared to the vanilla contrastive learning methods? Providing the training trend curve of the vanilla model and negative mining (using the clock time as an x-axis) would be insightful. It would also be great to discuss how to reduce the cost, e.g., use approximated nearest neighborhood search.

C. Negative mining for the *batch* setting?

For a single sample of $x_i$, it is easy to find the semi-hard negative samples. However, how to construct the batch $\{x_i\}$ such that each sample is effective negatives for the other samples? The batch should contain diverse samples; it would be interesting to consider the determinantal point process or submodular optimization formulation.


**Concerns in presentation**

There are lots of imprecise or undefined terms, unclear or unkind expressions, and typos. Here are some examples:
- Eq. (1) assumes to use $k$ negative samples ($i \notin \{1,...,k\}$ for a positive sample $i$), but Theorem 3.1 assumes to use $k-1$ negative samples
- The definition of the CNCE estimator comes after the property of it (Theorem 3.1)
- The definition of $S_B$ comes after the property of it. Also, it would be kinder to say "Assume $p(S_B) > 0$ for $S_B = \sim$" to "Assume that the set of random variables $S_B := \sim$ has a non-zero probability, i.e., $p(S_B) > 0$"
- "For Borel $A$" $\to$ "For a Borel set $A$"
- "Figure 1:" $\to$ "Figure 1: Visual illustration of ring discrimination"
- In Algorithm 1, do tx1 and tx2 receives the same input $x$?
- The evaluation metric "Transfer Acc." is not defined. Also, the term can be confused with "transferring features". Why not use the standard terminology "linear evaluation"?
- In Table 1, "three" image domains $\to$ "four" image domains


**Other comments**

Tons of similar techniques are concurrently proposed. It would be informative to discuss the relation with those works.
- Contrastive Learning with Hard Negative Samples
- Are all negatives created equal in contrastive instance discrimination?
- Self-supervised representation learning via adaptive hard-positive mining
- What Should Not Be Contrastive in Contrastive Learning
- Contrastive Learning with Stronger Augmentations

Is the sentence "A better representation would contain more "object-centric" information, thereby achieving a higher classification score." has some logical/empirical supports? Does "good" representation (in terms of downstream task performance) have some relation (in both directions) with the "object-centric" representation?
review_title: Reasonable direction, but needs more improvements

Meta-review: This paper addresses the problem of how best to sample hard negatives during contrastive learning, a topic of importance for the recently resurgent field of metric learning / contrastive loss-based unsupervised representation learning. Backed by theoretical results for a new low-variance version of the NCE, the paper proposes an easy-to-implement "Ring" method for selecting negatives that are at just the right level of difficulty, neither too hard nor too easy.

Happily, this is a paper that has improved significantly through the interactive peer review of a dedicated set of reviewers combined with prompt responses from the authors. Perhaps the result that tipped this paper over the line in my assessment: the new experimental results now show significant gains from applying the "Ring" approach for hard negative sampling to near-state-of-the-art implementations of the MoCo-v2 approach, which is among the leading unsupervised visual feature learning approaches. 
Decision: Accept (Poster)