Conditional Negative Sampling for Contrastive Learning of Visual Representations
Authors: Mike Wu
Milan Mosse
Chengxu Zhuang
Daniel Yamins
Noah Goodman
Venue: ICLR 2021 Poster (2021)
Keywords: contrastive learning
hard negative mining
mutual information
lower bound
detection
segmentation
MoCo

Abstract: Recent methods for learning unsupervised visual representations, dubbed contrastive learning, optimize the noise-contrastive estimation (NCE) bound on mutual information between two transformations of an image. NCE typically uses randomly sampled negative examples to normalize the objective, but this may often include many uninformative examples either because they are too easy or too hard to discriminate. Taking inspiration from  metric learning, we show that choosing semi-hard negatives can yield stronger contrastive representations. To do this, we introduce a family of mutual information estimators that sample negatives conditionally -- in a "ring" around each positive. We prove that these estimators remain lower-bounds of mutual information, with higher bias but lower variance than NCE. Experimentally, we find our approach, applied on top of existing models (IR, CMC, and MoCo) improves accuracy by 2-5% absolute points in each case, measured by linear evaluation on four standard image benchmarks. Moreover, we find continued benefits when transferring features to a variety of new image distributions from the Meta-Dataset collection and to a variety of downstream tasks such as object detection, instance segmentation, and key-point detection.

Published as a conference paper at ICLR 2021
CONDITIONAL NEGATIVE SAMPLING FOR CON- TRASTIVE LEARNING OF VISUAL REPRESENTATIONS
Mike Wu', Milan Mosse Chengxu Zhuang², Daniel Yamins 1.2 Noah Goodman'
Department of Computer Science', Psychology?, and Philosophy Stanford University
(wumike, chengxuz, mmossel9, yamins, ngoodman) (anadmaan@sttaafod...
ABSTRACT
Recent methods for learning unsupervised visual representations, dubbed con- trastive learning, optimize the noise-contrastive estimation (NCE) bound on mu- tual information between two transformations of image. NCE typically uses randomly sampled negative examples to normalize the objective, but this may often include many uninformative examples either because they are too easy too hard to discriminate. Taking inspiration from metric learning, we show that choosing semi-hare negatives can yield stronger contrastive representations. To do this, we introduce a family of mutual information estimators that sample negatives conditionally in a "ring" around each positive. We prove that these estimators remain lower-bounds of mutual information, with higher bias but lower variance than NCE. Experimentally. we find our approach, applied on top of existing mod- els (IR, CMC, and MoCo) improves accuracy by 2-5% absolute points in each case, measured by linear evaluation on four standard image benchmarks. More- over, we find continued benefits when transferring features to a variety of new im- age distributions from the Meta-Datase collection and to a variety of downstream tasks such object detection, instance segmentation, and key-point detection.
INTRODUCTION
Supervised learning has given rise to human-level performance in several visual tasks (Russakovsky al. 2015 He et al. 2017). relying heavily on large image datasets paired with semantic anno- tations. These annotations vary in difficulty and cost, spanning from simple class labels to more granular descriptions like bounding boxes and key-points. As it is impractical to scale high quality annotations, this reliance supervision poses barrier to widespread adoption. While supervised pretraining is still the dominant approach in computer vision, recent studies using unsupervised "contrastive" objectives, have achieved remarkable results in the last two years, closing the gap to
supervised baselines (Wu et al.) 2018 Oord et al. 2018 Hjelm et al. 2018 Zhuang et al. 2019
Hénaff et al. 2019 Misra & Maaten 2020 He et al. 2019 Chen al. 2020a
Grill al. 2020
Many contrastive algorithms are estimators of mutual information (Oord et al. 2018 Hjelm et al. 2018 Bachman et al. 2019), capturing the intuition that good low-dimensional "representation" is one that linearizes the useful information embedded within a high-dimensional data point. In vision, these estimators maximize the similarity of encodings for two augmentations of the same image. This is trivial (e.g. assign all image pairs maximum similarity) unless the similarity function normalized. This typically done by comparing an image to "negative examples", which model must assign low similarity to. We hypothesize that how we choose these negatives greatly impacts the representation quality. With harder negatives, the encoder is encouraged to capture more granular information that may improve performance downstream tasks. While research in contrastive learning has explored architectures, augmentations, and pretext tasks, there has been little attention given to the negative sampling procedure. Meanwhile, there is rich body of work in deep metric learning showing semi-hard hard negative mining to improve the efficacy of triplet losses. Inspired by this, we hope to bring harder negative sampling to modern contrastive learning.
Naively choosing difficult negatives may yield an objective that no longer bounds mutual informa- tion, removing theoretical connection that is core contrastive learning and has been shown to

---

Published as a conference paper at ICLR 2021
be important for downstream performance (Tian et al. 2020 In this paper, present esti- mator of mutual information based on the popular sampling negatives from conditional distributions. We summarize our contributions below:
estimator (NCE) that supports
1. We prove our Conditional-NCE (CNCE) objective to lower bound mutual information. Further, we show that although CNCE is looser bound than NCE, has lower variance. This motivates its value for representation learning.
2. We use CNCE to generalize contrastive algorithms that utilize a memory structure like IR, CMC, and MoCo sample semi-hard negatives in just few lines of code and minimal compute overhead.
3. We find that the naive strategy of sampling hard negatives throughout training can be detri- mental. We then show that slowly introducing harder negatives yields good performance.
4. On four image classification benchmarks, we find improvements of 2-5% absolute points. We also find consistent improvements (1) when transferring features new image datasets and (2) in object detection, instance segmentation, and key-point detection.
2
BACKGROUND
We focus on exemplar-ber based contrastive objectives, where examples are compared to one another learn a representation. Many of these objectives (Hjelm et al. 2018 Wu et al. 2018 Bachman Tian et al., 2019; Chen et al., 2020a) are equivalent to NCE (Oord et al.) 0018 Poole
et al.
2019:
al.
2019p. a popular lower bound on the mutual information, denoted by Z, between two random
variables.
This connection is well-known and stated in several works (Chen al. 2020a
Tschannen
ct al.
2019
Tian et al.) 2020 Wu et al. 2020). To review, recall:
efo(2..3))
I(X;Y) INCE (X;))
E E E2.sroppa.ss Eurepple)
log
k+11 EjE(CLAA) elllrss))
where y are realizations of two random variables, X and Y, and fo X + is similarity function. We call y1.k = (y1.... negative examples, being other realizations of Y.
Suppose the two random variables in Eq. are both transformations of common random variable X. Let T family of transformations where each member is a composition of cropping, color jittering, gaussian blurring, among others (Wu et al. 2018,) Bachman et al. 2019 Chen et al. 2020a) We call a transformed input f(x)) a "view" of x. Let p(t) denote distribution over T, common choice being uniform. Next, introduce Ln-normalized representation. Suppose we have a dataset D {x,)²= n values for X sampled from distribution p(x). Then, the contrastive objective for the i-th example is:
encoder ge X + S that maps example
ego(t(r)))) so(t)))))))
[(xx) Eu Mnanp(() Bun log
JE((i " (o(L)
where is a temperature. The equivalence of Eq. to NCE is immediate given fe (z, y) =
ge(2)" ge(y)/T. Maximizing Eq. 2 chooses embedding that pulls two views the same example together while pushing two views of distinct examples apart. A drawback to this framework is that the number of negatives l must be large to faithfully approximate the true partition. In practice, is limited by memory. Recent innovations have focused on tackling this challenge:
Instance Discrimination (w et 2018), or IR, introduces memory bank of entries to cache embeddings of each example throughout training. Since every epoch we observe each example once, the memory bank will save the embedding of the view of the i-th example observed last epoch in its th entry. Representations stored in the memory bank are removed from the automatic differentiation tape, but in return, we can choose a large & by querying M. A follow up work, Contrastive Multiview Coding (Tian et al. 2019), CMC, decomposes image into two color modalities. Then, CMC sums two IR losses where the memory banks for each modality are swapped.
Momentum Contrast (He et al. 2019). MoCo, observed that the representations stored in the memory bank grow stale, since possibly thousands of optimization steps pass before updating an entry again. So, MoCo makes two important changes. First, it replaces the memory bank with
2

---

Published as a conference paper at ICLR 2021
first-in first-out (FIFO) queue of size k. During each minibatch, representations are cached into the queue while the most stale ones are removed. Second, MoCo introduces a second (momentum) encoder gg. copy of go. The primary encoder go is used to embed one view of z; whereas the momentum encoder is used to embed the other. Again, gradients are not propagated to 96-
In this work, we focus contrastive algorithms that utilize memory structure that we repurpose we briefly discuss generalizations to in Sec. 9 to efficiently sample hard negatives from. In Sec. / contrastive algorithms that do not use memory structure.
CONDITIONAL NOISE CONTRASTIVE ESTIMATION
In NCE, the negative examples are sampled i..d. from the marginal distribution, p(y). Indeed, the existing proof that NCE lower bounds mutual information (Poole al. 2019) assumes this to be true. However, choosing negatives in this manner may not be the best choice for learning a good representation. For instance, prior work in metric learning has shown the effectiveness of semi- hard negative mining in optimizing triplet losses (Wu et al. 2017 Yuan et al, 2017| Schroof et al.) 2013 We similarly wish to exploit choosing semi-hard negatives in NCE conditional on the current example but to do so in a manner that preserves the lower bound on mutual information.
In presenting the theory, we assume two random variables X and Y. deriving a general bound; we will return to the contrastive learning setting in Sec. + To begin, in Eq. [] suppose we sample negatives from a distribution q(ylæ)) conditional on a value x ~ p(z)) rather than the marginal p(y), which is independent of X. Ideally, we would like to freely choose ((v(=r) to be any distribution but not all choices preserve a bound on mutual information This does not, however, imply that we can only sample negatives from pvy) (Poole et al. 2019 Oord et al. 2018). One of our contributions to formally define a family of conditional distributions Q such that for any ((y(z)) E Q, drawing negative examples from q defines an estimator that lower bounds IY:;Y). We call this new bound the Conditional Noise Contrastive Estimator, or CNCE. We first prove CNCE to be a bound:
Theorem 3.1. (The Conditional NCE bound) Define d-dimensional random variables X and Y by a joint distribution p(z, y) and let Y1, ..., Y& be i.i.d. copies of Y with the marginal distribution ply). Fix any function f: (X,Y) - R, any realization of X, and let Ey-ools) (ed ((()))))) the expected exponentiated similarity. Pick a set C R strictly lower-bounded by c. Assume the pulled back set Sn ( E B} has non-zero probability (i.e. p(SB) 0). For A,...., Ag in the Borel o-algebra over Rd, define A = Ai x x Au and let
(( ................................ Y2) E AA = 2) II p(A,1SB)
Joo (amw)
Ler IIwcce(x (X:Y) Ex Ey - a (nll))))
Then ICNCE I INCE-
# Σイ E (ln
Proof. To show ICNCE S INCE, we show [log] Σ j=1 ((..s)))) log Σj= (...)))) To see this, apply Jensen's to the left-hand side of log E,1 j=1 (w..s))) < log -j=1 e (wwws) which holds yj E Sp for j 1..... k, and then take the expectation E, of both sides. The last inequality holds by monoticity of log, linearity of expectation, and the fact that Ep Ep(es(a)))) < ex(.)))
Theorem Intuition. For intuition, although using arbitrary negative distributions in NCE does not bound mutual information, we have found a restricted class of distributions @ where every member q(ylz) "subsets the support" of the distribution p(y). That is, given some fixed value æ, we have defined (yylz)) to constrain the support of p(y) to a set SB whose members are "close" to æ as measured by the similarity function f. For every element y E Sg, the distribution g(y(zr) wants to assign to it the same probability as p(y). However, as 4(y|2)) is not defined outside of Sp. we must renormalize it sum to one (hence p(A)(SB) p(A;nSe) Intuitively, 43)(2)) cannot change p(y) too much: it must redistribute mass proportionally. The primary distinction then, the smaller
r(Sz)
We provide counterexample in Sec. A.1
3

---

Published as a conference paper at ICLR 2021
Awo
- Uhu
(a) IR, CMC, MoCo
(b) Ring
(c) Annealed Ring
Figure 1: Visual illustration of Ring Discrimination. Black: view of example 24; gray; second view of 2;; red: negative samples; gray area: distribution q(a)t(z,)). In subfigure (c), the negative samples annealed to be closer to t(2;) through training. In other words, the support of q shrinks.
support of ((y) ar), which forces samples from it to be harder for f to distinguish from T. Thm. 3.1 shows that substituting ((v(>)) for p(y) NCE still bounds mutual information.
Theorem Example 3.1. We give concrete example for the choice B that will be used in Sec. For any realization æ, suppose we define two similarity thresholds wi, Wy, E R where c < we < Wu- Then, choose B [wy, W.... In this case, the set SB, which defines the support of the distribution q(ylz) contains values of y that are not "too-close" to x but not "too-far". In contrastive learning, might pick these similarity thresholds vary the difficulty of negative samples.
Interestingly, Thm. 3.1 states that CNCE looser than NCE, which raises the question: when is a looser bound useful? In reply, show that while CNCE is more biased estimator than NCE, in return it has lower variance. Intuitively, because ((y(>) is the result of restricting p(y) to a smaller support, samples from ((y|z)) have less opportunity deviate, hence lower variance. Formally:
Theorem 3.2. (Bias and Variance Tradeoff) Pick any x, y ~ p(xx y). Fix the distribution
( (x)
as stated in Theorem 3.1 Define a new random variable 7yy:ss) log E ( Teraas
repre-
senting the normalized similarity. By Theorem 3.1 the expressions Ep(r)a) [Z] and E Edonala [Z] estimators for ((X;)), Suppose that the set SB is chosen to ensure oar [Z] S Varganalla)) [7,, where i(A) = P(Al complement of SB). That is, we assume the variance of the normalized similarity when using Yi:k E SB is smaller than when using yi:k & SB. Then Biasp(gn.s)) (Z) S (iass(onale) (Z) and Varp(naa) Z Var
The proof can be found in Sec. A.2 Thm. 3.2 provides one answer to our question of looseness. In stochastic optimization, lower variance objective may lead better local optima. For representa- tion learning, using CNCE to sample more difficult negatives may (1) encourage the representation to distinguish fine-grained features useful in transfer tasks, and (2) provide less noisy gradients.
4 RING DISCRIMINATION
We have shown CNCE be a new bound on the mutual information that uses hard negative samples. Now we wish to apply CNCE to contrastive learning where the two random variables are again transformations of a single variable X. In this setting, for a fixed x; ~ p(r), the CNCE distribution is written as ((x:) (x:)) for some transform E 'T. Samples from x ~ ((ar)((x))) will be such that the exponentiated distance, exp(ge (t(x:))) (t' is at least a minimum value c. As in Example 3.1. we will choose B wur w... closed interval in R defined by two thresholds.
Picking thresholds. We pick the thresholds conditioned on the i-th example in the dataset, hence each example has different set B. We first describe how to pick the upper threshold wa. Given the i-example 24, we pick a number u E [o, 100) representing an upper "percentile". We consider each example in the dataset to be in the support Sg if and only if the (exponentiated) distance between the embedding of I; and x. or exp(go((aa)))) 20'gg go (l((x))), is below the w-th percentile for all D. Call this maximum distance whe In other words, we construct (( such that we ignore examples from the dataset whose embedding dot producted with the embedding of æ; is above wi. (Note that 100 recovers NCE.) For a small enough choice of u, the upper similarity threshold wa will be greater than e (defined in Thm. [.] as the expected distance with respect to p(x)), and the samples from (x=))(x=)) will be harder negatives discriminate from T;-
4

---

Published as a conference paper at ICLR 2021
In picking the lower threshold wy, one could choose it to be 0, so B [0, w.). However, picking the closest examples to t(r;) as its negative examples may be inappropriate, as these examples might be better suited as positive views rather than negatives Zhuang et al. 2019 Xie et al. 2020). As an extreme case, if the same image is included in the dataset twice, we would not like to select it negative example for itself. Furthermore, choosing negatives "too close" to the current in- stance may result in representations that pick up on fine-grain details only, ignoring larger semantic concepts. This suggests removing examples from g(=))((;)) we consider "too close" to Z;. To do this, we pick lower percentile 0 S l < u. For each example I E D, we say it is in SB if exp(ge (t (z+))) go (=))) below We and also if is above the ε-th percentile of all distances with respect to D. Call this minimum distance wR. Fig. visualizes this whole procedure.
Step two pencemilles.
Step Compute distanees.
Step distances.
Step 4: Compute threhsolds.
Step & Define distribution q.
Duyte a aftiels gleltyi
X Suy
Xg
X
Xg
Xa
dist 1-m My
401
X1
p(x)
SB
100
Wi=distix.:x11
1-th
u-th
Sg
Figure 2: Defining the CNCE distribution (x:))(x;)). By choosing lower and upper percentile & and u, we implicitly define similarity thresholds we and wh, to construct a support of valid negative examples, SB. which in turn, defines the distribution ((x)((x;)))
Ring Discrimination. Having defined we and Who we have a practical method of choosing B, and thus Sn to define ((x))(z)) for i-th example. Intuitively, we construct a con- ditional distribution for negative examples that are (1) not too easy since their representations are fairly similar to that of x; and (2) not too hard since we remove the "closest" instances to x; from SB. We call this algorithm Ring Discrimination, or Ring, inspired by the shape of negative set (see Fig.
Algorithm 1: MoCoRing
* 8.9. 2.9- g.k: encoder networks temperature
uz ring upper percentile
# 1: ring lower pereentile
(xl-aug(x) # random augmestation (x2-aig(x)
embl-norm[g q(Tx]))
emb2-noem g g-k((x22)) )). ()tach()
dps-sum(txl (x1--x2)/ à dot product
Ring can be easily added to popular contrastive algorithms. For IR and CMC, this amounts to simply sampling entries in the memory bank that fall within the L-th to u-th percentile of all distances to the current example view (in representation space). Similarly, for MoCo, we sample from a subset of the queue (chosen to be in the ê-th to u-th percentile), preserving the FIFO ordering. In our experiments, we refer to these as IRing, CM- CRing, MoCoRing, respectively. Alg. [ shows PyTorch-like pseudocode for MoCoRing. One of the strengths of this ap- proach is the simplicity: the algorithm requires only few lines of code on top of existing implementations.
from clasest
farthest neg
all,dps=sort
Siqueee T/1)
t find indices of thresholds ix [queeen(quese)) ix_a-o-len (quee)
ring.dpszall.oo dps [ [i.ix.l:xx.u]
# nonparametric softmax
joss--dps+loguums dpp)
lass. b)ckward
(tep(g_9 params)
t meea updates
k. g.k. params m.r..k.paramse)
(I-m)+ 2.4- params
enquene (queue eemb2):
# threshold updates
aw (W.R)
Annealing Policy. Naively using hard negatives can collapse to a poor representation, especially if we choose the upper thresh- old, Wus to be very small early in training. At the start of training, the encoder go is randomly initialized and cannot guarantee that elements in the E-th to u-th percentile are properly calibrated: the representations are near random, choosing negatives that are close embedding distance may detrimentally exclude those examples that are "actually" close. This could lock in poor local min- ima. To avoid this, we propose to use an annealing policy that reduces Wa (and thus the size of the support 5g) throughout training. Early in training choose wn, to be large. Over many epochs, we slowly decrease Wa closer to wi, thereby selecting more difficult negatives. We explored several annealing policies and found linear schedule be well-performing and simple (see Sec. G In our experiments, annealing is shown to be crucial: being too aggressive with negatives early in training produced representations that performed poorly on downstream tasks.
5 EXPERIMENTS
We explore our method applied to IR, CMC, and MoCo in four commonly used visual datasets. As in prior work (Wu et al. 2018 Zhuang al. 2019 He al. 2019 Misra & Maaten 2020 Hénaff
5

---

Published as a conference paper at ICLR 2021
et al.
2019 Kolesnikov et al. 2019 Donahue & Simonyan 2019: Bachman et al. 2019 Tian al. 2019 Chen et al. 2020a), we evaluate each method by linear classification on frozen embeddings. That is, we optimize contrastive objective pretraining dataset to learn representation; then, using& a transfer dataset, we fit logistic regression on representations only. A better representation would contain more "object-centric" information, thereby achieving higher classification score.
Training Details. We pick the upper percentile u = 10 and the lower percentile & = 1 although we anneal starting from 100. We resize input images to be 256 by 256 pixels, and normalize them us- ing dataset mean and standard deviation. The temperature T is set to 0.07. We use a composition of a 224 by 224-pixel random crop, random color jittering, random horizontal flip, and random grayscale conversion as our augmentation family T. We use a ResNet- 18 encoder with a output dimension of 128. For CMC, we use two ResNet- 18 encoders, doubling the number of parameters. For linear classification, we treat the pre-pool output (size 512 x 7 X 7) after the last convolutional layer as the input to the logistic regression. Note that this setup is equivalent to using a linear projection head (Chen et al. 2020a bb. In pretraining, we use SGD with learning rate 0.03, momentum 0.9 and weight decay le-4 for 300 epochs and batch size 256 (128 for CMC). We drop the learning rate twice by factor of 10 epochs 200 and 250. In transfer, we use SGD with learning rate 0.01, momentum 0.9, and no weight decay for 100 epochs without dropping learning rate. These hyper- parameters were taken from Wu et al. (2018) and used in all of Table [ for consistent comparison. We found normalizing hyperparameters to be important for a fair comparison as many competing algorithms use different hyperparameters. For a ofate-of-the-art comparison, see Table
Model
Lincar Evaluntion
Madel
Lincar Ecalurzion
Model
Lineu Evaluation
Model
Linear Evaluation
IR
$1.2
IK
60.4
IK
61.4
IK
43.2
IRing
83,9 (+2.7)
IRing
62.3(++.9)
IRing
64.3 (+2.9)
IRing
48.4 (+5.2)
CMC*
85.6
CMC
56.0
CMC
63.8
CMC*
48.2
CMCRing
87.6 (+2.0)
CMCRing
56.0
CMCRingg
66.4 (+2.6)
CMCRing
50.4 (+2.2)
MoCo
$3.1
MaCo
59,1
MoCo
63.8
MoCo
52.8
McCoRing
86.1 (+3.0)
MoCoRing
61.5 (+2.4)
MoCoRing
65.2 (+1.4)
McCoRing
54.6 (+1.8)
83,9
LA
(a) CIFARIO
(b) CIFARI00
(c) STL10
(d) ImageNet
Table I: Comparison of contrastive algorithms on four image domains. Superscript (*) indicates models that use twice as many parameters as others e.g. CMC has "L." and "ab" encoders.
The results for CIFARIO. CIFARI00, STL10, and ImageNet are in Table I Overall, IR, CMC, and MoCo all benefit from using more difficult negatives as shown by 2-5% absolute points of improvement across the four datasets. While we find different contrastive objectives to perform best in each dataset, the improvements from Ring are consistent: the Ring variant outperforms the base for every model and every dataset. We also include as a baseline Local Aggregation, or LA Zhuang et al. 2019), a popular contrastive algorithm (see Sec. H that implicitly uses hard negatives without annealing. We find our methods to outperform LA by up to 4% absolute.
Ablations: Annealing and Upper Boundary. Having found good performance with Ring Discrimination, we want to assess the importance of the individual components that comprise Ring. We focus on the annealing policy and the exclusion of very close negatives from SB. Coneretely, we measure the transfer accuracy of (1) IRing without annealing and (2) IRing with an lower per- centile é = O, thereby excluding no close negatives. That is, SB contains all examples in the dataset with representation similarity less than the wn (a "ball" instead of a "ring"). Table 2 compares these ablations to IR and full IRing on CIFARI0 10 and ImageNet classification transfer. We observe that both ablations result in worse transfer accuracy, with proper annealing being especially important to prevent convergence to bad minima. We also find even with e = O, IRing outperforms IR, suggesting both remov- ing negatives that are "too close" and "too far" contribute to the improved representation quality.
Model
Linear Eval.
IR IRing
$1.2
83.9
IRing (No Anneal)
$1.4
TRing (f 0)
(a) CIFAR10
Model
Linear
43.2
IRing
IRing (No Anncal)
41.3
[Ring (6 = D1
47.3
(b) ImageNet
Table 2: Lesioning the effects of annealing and choice of l.
Transferring Features. Thus far we have only evaluated the learned representations on unseen examples from the training distribution. As the goal of unsu-

---

Published as a conference paper at ICLR 2021
pervised learning is to capture general representations, on new, unseen distributions. To gauge this, we use the same linear classification paradigm on a suite of image datasets from the "Meta Dataset" collection (Triantafillou et al. 2019 that have been used before in contrastive literature (Chen et al. 2020a). All representations were trained on CIFAR 10. For each transfer dataset, compute mean and variance from a training split normalize input images, which we found important for generalization to new visual domains.
also interested in their performance
Model
Aircraft
CUBirds
DTD
Fungi
MNIST
FushionMNIST
TrafiiSign
VOGRoower
MSCOCO
40,9
17.9
39.2
91.7
97.1
52.4
IKing
40.5 (40.3)
17.9 (-0.0)
39.5 (40.3)
3.4 (40.7)
97.8 (40.9)
91.6 (+1..)
98.8 (-1.7)
68.5 (40.4)
52.5 (40.3)
MoCo
41.5
18.0
39.7
3.1
96.9
90.9
91.3
64,5
52.0
MaClRiing
41.5(-0.1)
(9.5(-0.2)
(40.5)
(41.00
(+0.4)
99.3
(44.6)
(40.6)
15.8
97.5
91.5
94.6
67.1
51,4
CMCKing
40.8 (+0.7)
16.8 (-1.0)
40.6 (+2.3)
4.2 (-0.1)
91.9 (+0.4)
92.1 (+1.0)
91.1 (+2.5)
08L1 (+2.0)
52.1 (+0.7)
LA
41.3
17.8
39.0
2.3
97.2
92.3
98.2
66.9
$2.3
Table 3: Transferring CIFARIO embeddings to various image distributions.
We find in Table that the Ring models are competitive with the non-Ring analogues, with increases in transfer accuracies of 0.5 to 2% absolute. Most notable are the TrafficSign and VGGFlower datasets in which Ring models surpass others by a larger margin. We also observe that IRing largely outperforms LA. This suggests the features learned with more difficult negatives are not only useful for the training distribution but may also be transferrable to many visual datasets.
More Downstream Tasks. Object classification is popular transfer task, but we want our learned representations to capture holistic knowledge about the contents of an image. We must thus evaluate performance on transfer tasks such as detection and segmentation that require different kinds of visual information. We study four additional downstream tasks: object detection on COCO (in et al. 2014) and Pascal VOC (Everingham et al. 2010), instance segmentation on COCO, and keypoint detection COCO. In all cases, we employ embeddings trained on ImageNet with ResNet- 18 encoder. We base these experiments after those found in He et al. 2019) with the same hyperparameterrs. However, use smaller backbone (ResNet-1 18 versus ResNet- and we freeze its parameters instead of finetuning them. We adapt code from Detectron2 (Wu et al. 2019.
Objectt Dotection
CUCO: Inst. Segmentiiion
COCO: Keypaint Detection
Objjcct Detection
Arch.
R-CNN, R, FPN, Ix scholole
R-CNN, R FPN
Faster R-CNN, R CC4
Model
Apib
APib
Aprak
Ap
Appa
ApAo
AP
AP
Aphs
Apho
APIS
IR
8.6
19.0
6.6
8.5
17.4
7.4
34.6
63.0
32.9
5.5
14.5
3,3
TRing
10.9
22,9
8.7
11.0
20.9
9.6
37.2
66.1
35.7
7.6
20.3
4.4
MoCo
14.3
37.6
66.5
McCoking
20.5
22,9
10.8
38.7
67.7
22.1
LA
10.2
22.0
8.1
10.0
20.3
9.0
36.3
65.3
35.1
7.6
20.0
4.3
Table 4: Evaluation of ImageNet repressenttnssss using four visual transfer tasks.
We find IRing outperforms IR by around 2.3 points in COCO object detection, 2.5 points in COCO Instance Segmentation, 2.6 points in COCO keypoint detection, and 2.1 points in VOC object de- tection. Similarly, MoCoRing finds consistent improvements of 1-3 points over MoCo on the four tasks. Future work can investigate orthogonal directions of using larger encoders (e.g. ResNet-50) and finetuning ResNet parameters for these individual tasks.
6 RELATED WORK
Several of the ideas in Ring Discrimination relate existing work. Below, we explore these con- nections, and at the same time, place our work in a fast-paced and growing field.
Hard negative mining. While it has not been deeply explored in modern contrastive learning, negative mining has a rich line of research in the metric learning community. Deep metric learning utilizes triplet objectives of the form Lusplt a distance function (c.g. L2 distance), x4 and x are positive and negative example, respectively, relative to Fj, the current instance, and R.+ is margin. In this context, several approaches pick
(2:.) (e (x_)) d[go((())) (2t),, ()==))))(==)++=)))))))))))) + where d is
7

---

Published as a conference paper at ICLR 2021
semi-hard negatives: Schroff al. (2015) treats the furthest (in L2 distance) example in the same minibatch as 24 as its negative, whereas Oh Song et al. (016) weight each example in the mini- batch by its distance to (o()),, thereby being continuous version of |Schroff et al. (015). More sophisticated negative sampling strategies developed over time. In Wu et al. (017). the authors pick negatives from a fixed normal distribution that is shown approximate L2 normalized embeddings in high dimensions. The authors show that weighting by this distribution samples more diverse neg- atives. Similarly, HDC (Yuan et al., 2017) simulataneously optimizes a triplet loss using many levels of "hardness" in negatives, again improving the diversity. Although triplet objectives paved the way for modern NCE- objectives, the focus on negative mining has largely been overlooked. Ring Discrimination, being inspired by the deep metric learning literature, reminds that negative sampling still an effective way of learning stronger representations in the new NCE framework. As such, an important contribution was to do so while retaining the theoretical properties of NCE, namely in relation to mutual information. This, to the best of our knowledge, is novel as negative mining in metric learning literature was not characterized in terms of information theory.
That being said, there are some cases of negative mining in contrastive literature. In CPC (Oord et al. 2018), the authors explore using negatives from the same speaker versus from mixed speakers in audio applications, the former of which can be interpreted as being more difficult. A recent paper, InterCLR (Xie et al.) 2020), also finds that using "semi-hard negatives" is beneficial to contrastive learning whereas negatives that are too difficult or too easy produce worse representations. Where InterCLR uses a margin-basee based approach to sample negatives, we explore wider family of negative distributions and show analysis that annealing offers simple and easy solution to choosing between easy and hard negatives. Further, as InterCLR's negative sampling procedure CNCE, we provide theory grounding these approaches in information theory. Finally, a separate line of work in contrastive learning explores using neighboring examples (in embedding space) as "positive" views of the instance (Zhuang et al. 2019, Xie et al. 2020, Asano et al., 2019: Caron et al. 2020 Li et al. 2020p. That is, finding a set {5,) such that we consider 4; = (x;;) for the current instance 2,, While this does not deal with negatives explicitly, it shares similarities to approach by employing other examples in the contrastive objective to learn better representations. In the Appendix, we discuss how one of these algorithms, LA (Zhuang et al. 2019p, implicitly uses hard negatives and expand the Ring family with ideas inspired by it.
special case of
Contrastive learning. We focused primarily comparing Ring Discrimination three recent and highly performing contrastive algorithms, but the field contains much more. The basic idea of learning representations be invariant under a family of transformations is old one, having been explored with self-organizing maps (Becker & Hinton 1992) and dimensionality reduction (Hadsell al. 2006). Before IR, the idea of instance discrimination was studied (Dosovitskiy et al., 2014 Wang & Gupta 2015) among many pretext objectives such as position prediction (Doersch et al.
2015). color prediction (Zhang et al. 2016), multi-task objectives (Doersch Zisserman 2017);
rotation prediction (Gidaris et al. 2018 Chen et al. 2019p, and many other "pretext" objectives (Pathak et al. 2017). As we have mentioned, one of the primary challenges to instance discrimi- nation making such large softmax objective tractable. Moving from parametric (Dosovitskiy) 2014) to a nonparametric softmax reduced issues with vanishing gradients, shifting the chal- lenge to efficient negative sampling. The memory bank approach (Wu et al. 2018) is simple and memory-efficient solution, quickly being adopted by the research community (Zhuagg et al. 2019
et al.
Tian al. 2019 He et al. 2019 Chen al., 2020b Misra & Maaten 2020 With enough compu-
tational resources, is now also possible to reuse examples in a large minibatch and negatives of one another YEe al.) 2019 Ji al. 2019 Chen et al., 2020a). In our work, we focus on hard negative mining in the context of a memory bank or queue due to its computational efficiency. However, the same principles should be applicable to batch-based methods (e.g. SimCLR): assuming large enough batch size, for each example, we only use a subset of the minibatch as negatives as in Ring. Finally, more recent work (Grill al. 2020) removes negatives altogether, which is speculated to implicitly use negative samples via batch normalization (loffe & Szegedy 2015); we leave a more thorough understanding of negatives in this setting to future work.
DISCUSSION
Computational cost of Ring. To measure the cost of CNCE, we compare the cost an epoch of training MoCo/IR versus MoCoRing/IRing on four image datasets. Table 5a reports the average
8

---

Published as a conference paper at ICLR 2021
Model
CIFARLO (sec.)
ImageNet (min.)
Dataset
Arch.
MoCo-12
MoCCoiing-22
IR TRing
136.0 4
43.9 =
CIFARIO
ResNee- 18
90.1
91,9
(+1.8
141.1 5..10)
51.0 (1.28)
CIFARIO
ReaNer-50
92.4
94.1
(+1.6)
MoCo
318.4 1: 16
61.1 #
CIFARI00
ResNet-18
65.1
67.3
(+2.2)
Mod'oRing
383.4 + 12.220
64,9
(1.1)
STL10
ResNee 18
76.7
(+1.9)
(a) Average Epoch Cost
(b) Comparison with SOTA
Transee Task
McCo
MoCoRing
LibriSpeech Spk. ID (Panavctvv al. 2013
93.5
96.6
(+1.1)
Ditaset
SimCLR
SimCLRing
AudioMNIST ( B83
87.4
91.3
(43.9)
CIFARIO
53.9
89.3
(-0.4)
Google
Fluest Oitjects
Actions
pooee e am A011
41.9
36.3
41.4
36.8
44.1
(+2.2)
(62.9)
(+0.3)
CIFAR100
STL10
63.5
71.2
72.1
(+0.9)
(+0,)
Fluent Locations
Lugnniie 6 31 AUD
60.9
63.9
(43.0)
(d) SimCI Ring Extension
(c) Speech Extension
Table 5: Generalizations of Ring to a new modality (a) and batch-based algorithm (b).
cost over 200 epochs. We observe that Ring models cost no more than 1.5 times the cost of standard contrastive algorithms, amounting to difference of 3 to minutes in ImageNet and 10 to 60 seconds in three other datasets per epoch. In the context of deep learning, we do not find the cost increases to be substantial. In particular, since (1) the memory structure in IR and MoCo allow us store and reuse embeddings and (2) gradients are not propagated through the memory structure, the additional compute of Ring amounts to one matrix multiplication, which is cheap modern hardware. We
used a single Titan X GPU with 8 CPU workers, and Py PyTocc Lightning (Falcon et al. 2019).
Comparison with the state-of-the-art. Unlike the experiments in Sec. we now choose the op- timal hyperparameters for MoCo-v2 (Chen et al. 20206) separately for CIFARIO, CIFARIO0, and STL10. Table D compares MoCo-v2 and its CNCE equivalent, MoCoRing v2 using linear evalua- tion. We observe comparable improvements as found in Table even with optimal hyperparameters. Notably, the gains generalize to ResNet-50 encoders. Refer to Sec. for hyperparameter choices.
Generalization to other modalities. Thus far, we have focused on visual representation learning, although the same ideas apply to other domains. To exemplify the generality of CNCE, we apply MoCoRing to learning speech representations. Table D reports linear evaluation on six transfer datasets, ranging from predicting speaker identity to speech recognition to intent prediction. We find significant gains of 1 to 4 percent over 4 datasets and 6 transfer tasks with an average of 2.2 absolute percentage points. See Sec. E for experimental details.
Batch-based negative sampling. In Ring, assumed to have memory structure that stores embeddings, which led to an efficient procedure of mining semi-hard negatives. However, an- other flavor of contrastive algorithms removes the memory structure entirely, using the examples in the minibatch as negatives of one another. Here, we motivate a possible extension of Ring to SimCLR, and leave more careful study to future work. In SimCLR, we are given mini- batch M of examples. To sample hard negatives, as before, pick and u as lower and upper percentiles. For every example x; in the minibatch, only consider the subset of the minibatch {z S M, cxp(9o(t(z:)) go (z()) in the b-th and u-th percentiles in M) as negative exam- ples for z; This can be efficiently implemented as matrix operation using an element-wise mask. Thus, we ignore gradient signal for examples too far or too close to z; in representation. As before, we anneal u from 100 to 10 and set = 1. Table 55 report consistent but moderate gains over SimCLR, showing promise but room for improvement future research.
8 CONCLUDING REMARKS
To conclude, we presented family of mutual information estimators that approximate the partition function using samples from a class conditional distributions. We proved several theoretical statements about this family, showing bound on mutual information and tradeoff between bias and variance. Then, we applied these estimators as objectives in contrastive representation learning. In doing so, found that our representations outperform existing approaches consistently across spectrum of contrastive objectives, data distributions, and transfer tasks. Overall, we hope our work to encourage more exploration of negative sampling in the recent growth of contrastive learning.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
This research was supported by the Office of Naval Research grant ONR MURI N00014-16-1-2007 MW is supported by the Stanford Interdisciplinary Graduate Fellowship as the Karr Family Fellow.
REFERENCES
Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultaneous 2019.
clustering and representation learning, arXiv preprint
Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. In Advances in Neural Information Processing Systems, pp- 15535-15545, 2019.
Sören Becker, Marcel Ackermann, Sebastian Lapuschkin, Klaus-Robert Müller, and Wojciech Samek. Interpreting and explaining deep neural networks for classification of audio signals. arXiv preprint (eXivv:807.034111 2018.
Suzanna Becker and Geoffrey E Hinton. Self-organizing neural network that discovers surfaces in random-dot stereograms. Nature, 355(6356):661-163, 1992.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. arXiv preprint arXiv:2006.0988 09882, 2020.
Ting Chen, Xiaohua Zhai, Marvin Ritter, Mario Lucic, and Neil Houlsby. Self-supervised gans via auxiliary rotation loss. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 12154-12163, 2019.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint arXi::2002.05709 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint rrXiv:2003.04297 2020b.
Carl Doersch and Andrew Zisserman. Multi-task self-supervised visual learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2051-2060, 2017.
Carl Doersch, Abhinav Gupta, and Alexei Efros. Unsupervised visual representation learning by context prediction. In Proceedings of the IEEE International Conference on Computer Vision, pp- 1422-1430, 1430, 2015.
Jeff Donahue and Karen Simonyan. Large scale adversarial representation learning. In Advances in Neural Information Processing Systems, pp. 10542-10552 2019.
Alexey Dosovitskiy, Jost Tobias Springenberg, Martin Riedmiller, and Thomas Brox. Discrimina- tive unsupervised feature learning with convolutional neural networks. In Advances in neural information processing systems, pp. 766-774, 2014.
Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The paseal visual object classes (voc) challenge. International journal of computer vision, 88(2): 303-338, 2010.
WEA Falcon et al. Pytorch lightning. GitHub. Note: https://github. con/villiamFalcoo/yytorr lightning Cited by, 3, 2019.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv: 1eo:: 2018
Lean-Bastion Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. arXiv preprint arXiv:2006.0r1 07733, 2020.
10

---

Published as a conference paper at ICLR 2021
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recogni- tion (CVPR 06), volume 2, pp. 1735-1742. IEEE, 2006.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE international conference on computer vision, pp. 2961-2969, 2017.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for 2019.
unsupervised visual representation learning. arXiv preprint
Olivier J Hénaff, Aravind Srinivas, Jeffrey De Fauw, Ali Razavi, Carl Doersch, SM Eslami, and
Aaron van den Oord. Data-efficient image recognition with contrastive predictive coding. arXiv 2019.
preprint
R Devon Hjelm, Alex Fedorov, Samuel Savoie-Marchilee Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 1808. 06670, 2018.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint urXiv:1502.03106 2015.
Xu Ji, João F Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 9865-9874, 2019.
Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self-supervised visual represen- tation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recog- nition, pp. 1920-1929, 2019..
Junnan Li, Pan Zhou, Caiming Xiong, Richard Socher, and Steven CH Hoi. Prototypical contrastive learning of unsupervised representations. arXiv preprint arXiv:2005.04900 2020.
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pictro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pp. 740-755. Springer, 2014.
Loren Lugosch, Mirco Ravanelli, Patrick Ignoto, Vikrant Singh Tomar, and Yoshua Bengio. Speech model pre-training for end-to-end spoken language understanding. arXiv preprint 19X1v:1904.03670. 2019.
Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invariant representa- tions. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 6707-6717, 2020.
Hyun Oh Song. Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4004-4012, 2016.
Aaron van den Oord, Yazhe Li. and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint / 2018.
Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an asr corpus based on public domain audio books. In 2015 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pp. 5206-5210. IEEE, 2015.
Deepak Pathak, Ross Girshick, Piotr Dollár, Trevor Darrell, and Bharath Hariharan. Learning fea- tures by watching objects move. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2701-2710, 2017.
Ben Poole, Sherjil Ozair, Aaron van den Oord, Alexander Alemi, and George Tucker. On varia- tional bounds of mutual information. arXiv preprint 195.09290. 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3)2111255 2015.
11

---

Published as a conference paper at ICLR 2021
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings ofe IEEE conference on computer vision and pattern recognition, pp. 2015.
Alex Tamkin, Mike Wu, and Noah Goodman. Viewmaker networks: Learning views for unsuper- vised representation learning, arXiv preprint arXiv:2010.07432 2020.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. arXiv: 05849, 2019.
Contrastive multiview coding, arXiv preprint
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning. arXiv preprint arXiv:2005./0224 2020.
Eleni Triantafillou, Tyler Zhu, Vincent Dumoulin, Pascal Lamblin, Utku Evei, Kelvin Xu, Ross
Goroshin, Carles Gelada, Kevin Swersky, Pierre-Antoine Manzagol, et al. Meta-dataset: A dataset of datasets for learning learn from few examples. arXiv preprint arXiv: 030096 2019.
Michael Tschannen, Josip Djolonga, Paul Rubenstein, Sylvain Gelly, and Mario Lucie. On mutual information maximization for representation learning. arXiv preprint arXiv: 1907. 13625, 2019.
Xiaolong Wang and Abhinav Gupta. Unsupervised learning of visual representations using videos. In Proceedings of the IEEE international conference on computer vision, pp. 2094-229220 2015.
Pete Warden. Speech commands: A dataset for limited-vocabulary speech recognition. arXiv preprint 1xXiv1180.0032000 2018.
Chao-Yuaa Yuan Wu, Manmatha, Alexander Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2840-2848, 2017.
Mike Wu, Chengxu Zhuang, Milan Mosse, Daniel Yamins, and Noah Goodman. On mutual in- formation in contrastive learning for visual representations. arXiv preprint arXiv:2005.13 2020.
Yuxin Wu, Alexander Kirillov. Francisco Massa, Wan- Lo, and Ross Girshick. Detectron2. 2019.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 3733-3742, 2018.
Jiahao Xie, Xiaohang Zhan, Ziwei Liu, Yew Soon Ong, and Chen Change Loy. Delving into inter- image invariance for unsupervised visual representations, arXiv preprint arXiv: 11002, 2020.
Mang Ye, Xu Zhang, Pong C Yuen, and Shih-Fu Chang. Unsupervised embedding learning via invariant and spreading instance feature. In Proceedings of the IEEE Conference computer vision and pattern recognition, pp. 0210-6219 2019.
Yuhui Yuan, Kuiyuan Yang, and Chao Zhang. Hard-aware deeply cascaded embedding. In Proceed- ings of the IEEE international conference computer vision, pp. 814-823, 2017.
Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In European confer- ence on computer vision, pp. 649-666. Springer, 2016.
Chengxu Zhuang, Alex Lin Zhai, and Daniel Yamins. Local aggregation for unsupervised learning of visual embeddings. In Proceedings of the IEEE International Conference Computer Vision, pp. 6002-6012, 2019.
12


Reviews:
[{"review_id": "mznPX1ss1Cp", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nThe paper has some good points:\n- Applying semi-hard negative mining for contrastive learning is reasonable.\n- Discussion on the property of the proposed estimator, CNCE.\n- Empirically validate the proposed method improves the contrastive learning methods.\n\nHowever, the paper needs more improvements for both method and presentation.\n\n\n**Concerns in method**\n\nA. Choice of the hyperparameters $[w_l,w_u]$.\n\nChoosing \"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.\n\nB. Cost of the negative mining\n\nSearching 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.\n\nC. Negative mining for the *batch* setting?\n\nFor 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.\n\n\n**Concerns in presentation**\n\nThere are lots of imprecise or undefined terms, unclear or unkind expressions, and typos. Here are some examples:\n- 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\n- The definition of the CNCE estimator comes after the property of it (Theorem 3.1)\n- 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$\"\n- \"For Borel $A$\" $\\to$ \"For a Borel set $A$\"\n- \"Figure 1:\" $\\to$ \"Figure 1: Visual illustration of ring discrimination\"\n- In Algorithm 1, do tx1 and tx2 receives the same input $x$?\n- 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\"?\n- In Table 1, \"three\" image domains $\\to$ \"four\" image domains\n\n\n**Other comments**\n\nTons of similar techniques are concurrently proposed. It would be informative to discuss the relation with those works.\n- Contrastive Learning with Hard Negative Samples\n- Are all negatives created equal in contrastive instance discrimination?\n- Self-supervised representation learning via adaptive hard-positive mining\n- What Should Not Be Contrastive in Contrastive Learning\n- Contrastive Learning with Stronger Augmentations\n\nIs 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?", "extra_scores": {}, "extra_text": {}}, {"review_id": "k7SdmUQuKOw", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nBriefing:\n\nThis 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.\n\n#######################################################\n\nPros:\n\n\nThe 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.\n\nThe experiments show the effectiveness of their method compared with the original NCE methods.\n\n#######################################################\n\nCons:\n\n\nThis paper's writing quality is limited, and this makes some points that are not easy to understand.\n\nWhy introduce many such details about IR and MoCo? It seems they are not heavily related to the contribution of this paper.\n\nThe 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? \n\nThe 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.\n\nThe 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.\n\n#######################################################\n\nPlease address and clarify the cons above in the rebuttal period.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "TjKkfur3d9n", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nInspired 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.\n\n\n# Pros\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\n\n# Cons\n\nA 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.\n\n\n# Recommendation\n\nMy 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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "O39kBpFN7wz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nPros:\n- Conditional negative sampling in contrastive learning is currently less studied, and this paper starts on this direction.\n- The relative improvement of the new objective function upon multiple popular contrastive learning methods have been verified.\n- 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.\n- The implementation can be simple, which I appreicaite.\n\nCons:\n- 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\n- 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.\n- 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?\n- 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.\n- 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. \n\nOverall, I have a mixed feeling over this paper, and would appreciate authors response. \n\n======= updated ======\nThe authors response partially addressed my concerns and I would raise the rating to 6.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)