Contrastive Learning with Hard Negative Samples
Authors: Joshua David Robinson
Ching-Yao Chuang
Suvrit Sra
Stefanie Jegelka
Venue: ICLR 2021 Poster (2021)
Keywords: contrastive learning
unsupervised representation learning
hard negative sampling

Abstract: We consider the question: how can you sample good negative examples for contrastive learning? We argue that, as with metric learning, learning contrastive representations benefits from hard negative samples (i.e., points that are difficult to distinguish from an anchor point). The key challenge toward using hard negatives is that contrastive methods must remain unsupervised, making it infeasible to adopt existing negative sampling strategies that use label information. In response, we develop a new class of unsupervised methods for selecting hard negative samples where the user can control the amount of hardness. A limiting case of this sampling results in a representation that tightly clusters each class, and pushes different classes as far apart as possible. The proposed method improves downstream performance across multiple modalities, requires only few additional lines of code to implement, and introduces no computational overhead.


Published as a conference paper at ICLR 2021
CONTRASTIVE LEARNING WITH HARD NEGATIVE SAMPLES
Joshua Robinson, Ching-Yao Chuang, Suvrit Sra, Stefanie Jegelka Massachusetts Institute of Technology Cambridge, MA, USA (joshrob, cychuang, suvrit, stef je) @mit.edile
ABSTRACT
How can you sample good negative examples for contrastive learning? We argue that, with metric learning, contrastive learning of representations benefits from hard negative samples (i.c., points that are difficult to distinguish from an anchor point). The key challenge toward using hard negatives is that contrastive methods must remain unsupervised, making it infeasible to adopt existing negative sampling strategies that true similarity information. In response, family of unsupervised sampling methods for selecting hard negative samples where the user can control the hardness. A limiting case of this sampling results a representation that tightly clusters each class, and pushes different classes as far apart as possible. The proposed method improves downstream performance across multiple modalities, requires only few additional lines of code to implement, and introduces no computational overhead.
develop new
INTRODUCTION
Owing to their empirical success, contrastive learning methods (Chopra et al., 2005; Hadsell et al., 2006) have become one of the most popular self-supervised approaches for learning representations (Oord et al., 2018; Tian et al., 2019; Chen et al., 2020a). In computer vision, unsupervised con- trastive learning methods have even outperformed supervised pre-training for object detection and segmentation tasks (Misra & Maaten, 2020; He et al., 2020).
Contrastive learning relies on two key ingredients: notions of similar (positive) (I,x*) and dissimilar (negative) (x, x pairs of data points. The training objective, typically noise-contrastive estimation (Gutmann & Hyvärinen, 2010), guides the learned representation f to map positive pairs nearby locations, and negative pairs farther apart; other objectives have also been considered (Chen et al., 2020a). The success of the associated methods depends on the design of informative of the positive and negative pairs, which cannot exploit true similarity information since there is no supervision.
Much research effort has addressed sampling strategies for positive pairs, and has been a key driver of recent progress in multi-view and contrastive learning (Blum & Mitchell, 1998; Xu et al., 2013; Bachman et al., 2019; Chen et al., 2020a: Tian al.. 2020). For image data, positive sampling strategies often apply transformations that preserve semantic content, e.g., jittering random cropping. separating color channels, etc. (Chen et al., 2020a;e; Tian al., 2019). Such transformations have also been effective in learning control policies from raw pixel data (Srinivas et al., 2020). Positive sampling techniques have also been proposed for sentence, audio, and video data (Logeswaran & Lee, 2018; Oord et al., 2018; Purushwalkam & Gupta, 2020; Sermanet et al., 2018).
Surprisingly, the choice of negative pairs has drawn much less attention contrastive learning. Often, given an "anchor" point x, "negative" x is simply sampled uniformly from the training data, independent of how informative it may be for the Iearned representation. In supervised and metric learning settings, "hard" (true negative) examples its mistakes more quickly (Schroff et al., 2015; Song et al., 2016). For representation learning, informative negative examples are intuitively those pairs that mapped nearby but should be far apart. This idea is successfully applied in metric learning, where true pairs of dissimilar points are available, as opposed to unsupervised contrastive learning.
help guide learning method correct
Code available at: https:// /ttp:://gttttba/e com/ http://sssrr//// joos////////////////

---

Published as a conference paper at ICLR 2021
With this motivation, we address the challenge of selecting informative negatives for contrastive representation learning. In response, we propose a solution that builds a tunable sampling distribution that prefers negative pairs whose representations are currently very similar. This solution faces two challenges: (1) we do not have access to any true similarity or dissimilarity information; (2) we need an efficient sampling strategy for this tunable distribution. We overcome (1) by building on ideas from positive-unlabeled learning (Elkan & Noto, 2008; Du Plessis et al., 2014), and (2) by designing an efficient, easy to implement importance sampling technique that incurs no computational overhead.
Our theoretical analysis shows that, as a function of the tuning parameter, the optimal representations for our new method place similar inputs in tight clusters, whilst spacing the clusters as far apart as possible. Empirically, our hard negative sampling strategy improves the downstream task performance for image, graph and text data, supporting that indeed, our negative examples are more informative.
Contributions. In summary, we make the following contributions:
1. We propose a simple distribution over hard negative pairs for contrastive representation learning, and derive a practical importance sampling strategy with zero computational overhead that takes into account the lack of true dissimilarity information;
2. We theoretically analyze the hard negatives objective and optimal representations, showing that they capture desirable generalization properties;
3. We empirically observe that the proposed sampling method improves the downstream task performance on image, graph and text data.
Before moving onto the problem formulation and our results, we summarize related work below.
1.1 RELATED WORK
Contrastive Representation Learning. Various frameworks for contrastive learning of visual representations have been proposed, including SimCLR (Chen et al., 2020a;b), which uses augmented views of other items minibatch as negative samples, and MoCo (He et al., 2020; Chen et al., 2020c), which uses momentum updated memory bank of old negative representations to enable the use of very large batches of negative samples. Most contrastive methods are unsupervised, however there exist some that use label information (Sylvain et al., 2020; Khosla et al., 2020). Many works study the role of positive pairs, and, c.g., propose to apply large perturbations for images Chen et al. (2020a;c), or argue to minimize the mutual information within positive pairs, apart from relevant information for the ultimate prediction task (Tian et al., 2020). Beyond visual data, contrastive methods have been developed for sentence embeddings (Logeswaran & Lee, 2018), sequential data (Oord et al., 2018; Hénaff et al., 2020), graph (Sun et al., 2020; Hassani & Khasahmadi, 2020; Li et al., 2019) and node representation learning (Velickovic et al., 2019), and learning representations from raw images for off- offlcolicy control (Srinivas et al., 2020). The role of negative pairs hase been much less studied. Chuang et al. (2020) propose a method for "debiasing". i.e., correcting for the fact that not all negative pairs may be true negatives. It does so by taking the viewpoint of -ntttiee--nlaeeddd learning, and exploits a decomposition of the true negative distribution. Kalantidis et al. (2020) consider applying Mixup (Zhang et al., 2018) to generate hard negatives in latent space, and Jin et al. (2018) exploit the specific temporal structure of video to generate negatives for object detection.
Negative Mining in Deep Metric Learning, As opposed to the contrastive representation learning literature, selection strategies for negative samples have been thoroughly studied in (deep) metric learning (Schroff et al., 2015; Song et al., 2016; Harwood et al., 2017; Wu et al., 2017: Ge, 2018; Suh et al., 2019). Most of these works observe that it is helpful to use negative samples that are difficult for the current embedding to discriminate. Schroff al. (2015) qualify this, observing that some examples are simply too hard, and propose selecting "semi-hard" negative samples. The well known importance of negative samples metric learning, where (partial) true dissimilarity information is available, raises the question of negative samples in contrastive learning, the subject of this paper.
2 CONTRASTIVE LEARNING SETUP
We begin with the setup and the idea of contrastive representation learning. We wish to learn an embedding f X - gd_1 /t that maps an observation x to a point on a hypersphere gd 1/t in Rd of radius 1/t, where is the "temperature" scaling hyperparameter.
Following the setup of Arora et al. (2019), we assume an underlying set of discrete latent classes that represent semantic content, that similar pairs (x,2*)) have the same latent class. Denoting
2

---

Published as a conference paper at ICLR 2021
Embedding Space:
Anchor:
Negative Batch:
Sample Negatives
Uniformly from
44 04
Dataset (typical method)
Oak
Mountain
Willow
Violets
Oak
Sample Hard Negutives (our method)
44
0
A
Oak
Sycamore
Willow
Maple
Sequoia
Figure I: Schematic illustration of negative sampling methods for the example of classifying species of tree. Top row: uniformly samples negative examples (red rings); mostly focuses very different data points from the anchor (yellow triangle), and may even sample examples from the same class (triangles, vs. circles). Bottom row: Hard negative sampling prefers examples that (incorrectly) close to the anchor.
the distribution over latent classes by p(c) for E C. we define the joint distribution e c) = p(z]c)p(c) whose marginal p(x:) we refer to simply p. and assume supp(p) = X. For simplicity, we assume p(c) = r* uniform, and let r = r be the probability of another class. Since the class-prior - is unknown in practice, must either be treated as hyperparameter, or estimated (Christoffel et al., 2016; Jain et al., 2016).
Let h X' be the true underlying hypothesis that assigns class labels inputs. We write x to denote the lahel equivalence relation h(x) = (xx).. We denote by p. (x') p<='l((x') = hxx)). ), the distribution over points with same label æ, and by Pr (z') = p(x') ((x') + h(x)). the distribution over points with labels different from æ. We drop the subscript æ when the context is clear. Following the usual convention, we overload '~J' and also write p to denote point sampled from p.
For each data point p, the noise-contrastive estimation (NCE) objective (Gutmann & Hyvärinen, 2010) for learning the representation f uses a positive example x with the same label as x, and negative examples (x, J with (supposedly) different labels, h(xT) * h(x), sampled from
eat) s(x))
soup, x trpp {nr V.N 1
log ef(a) + EM (aa)
The weighting parameter Q is introduced for the purpose of analysis. When is finite we take Q = N, yielding the usual form of the contrastive objective. The negative sample distribution is frequently chosen to be the marginal distribution p. or, in practice, an empirical approximation (Tian et al., 2019; Chen al., 2020a;c; He et al., 2020; Chen et al., 2020c; Oord et al., 2018; Hénaff et al., 2020). In this paper we ask: is there a better way to choose q?
HARD NEGATIVE SAMPLING
In this section describe approach for hard negative sampling. We begin by asking what makes a good negative sample? To answer this question we adopt the following two guiding principles:
Principle 1. should only sample "true negatives" x. whose labels differ from that of the anchor x.
Principle 2. The most useful negative samples are ones that the embedding currently believes to be similar the anchor.
In short, negative samples that have different label from the anchor, but that embedded nearby are likely to be most useful and provide significant gradient information during training. In metric learning there is access true negative pairs, automatically fulfilling the first principle.
In unsupervised contrastive learning there no supervision, so upholding Principle is impossible to do exactly. In this paper we propose method that upholds Principle 1 approximately, and simultancously combines this idea with the key additional conceptual ingredient of "hardness" (encapsulated in Principle 2). The level of "hardness" in method can be smoothly adjusted,
3

---

Published as a conference paper at ICLR 2021
allowing the user to select the hardness that best trades-off between improved learning signal from hard negatives, and the harm due to the correction of false negatives being only approximate. This important since the hardest points those closest the anchor, and expected to have a high propensity to have the same label. Therefore the damage from the approximation not removing all false negatives becomes larger for harder samples, creating the trade-off. As special case our our method, when the hardness level is tuned fully down, we obtain the method proposed in (Chuang al., 2020) that only upholds Principle 1 (approximately) but not Principle 2. Finally, beyond Principles and 2, we wish to design an efficient sampling method that does not add additional computational overhead during training.
3.1 PROPOSED HARD SAMPLING METHOО
Our first goal is to design a distribution q on that is allowed to depend on the embedding f and the anchor z. From q we sample a batch of negatives {., ) according to the principles noted above. We propose sampling negatives from the distribution d3 defined as
43 (x == ga(2 [h(x)) + Ih(x)))
where ga(x ) x xe @f(x) f(xT), p((x)) )
for 3 2 O. Note that Ug and qa both depend on æ, but suppress the dependance from the notation. Mises-Fisher distribution with mean direction
The exponential term qs an unnormalized (x) and "concentration parameter" 33 (Mardia & Jupp, 2000). There two key components to 93 corresponding to each principle: 1) conditioning on the event (h(x) & h(*))) which guarantees that (x, correspond to different latent classes (Principle 1); 2) the concentration parameter term controls the degree by which qa up-weights points x that have large inner product (similarity) to the anchor (Principle 2). Since f lies on the surface of hypersphere of radius 1/t, have
Il. - f(x')| = 2/t² 2f(x) f(x') so preferring points with large inner product is equivalent preferring points with small squared Euclidean distance.
Although we have designed 43 to have all of the desired components, it is not clear how to sample efficiently from it. To work towards a practical method, note that we can rewrite this distribution by adopting PU-learning viewpoint (Elkan & Noto, 2008; Du Plessis et al., 2014; Chuang et al., 2020).
That is, by conditioning on the event {h(x) = h(==)} }} we can split ga(x") as
qa(0: = 9 (x-) - (x
where o (x-) go(r (h(x) = h(xx)())
x ((() f(x ). >.p
-pt((r (x-). Rearranging equation 2 yields a
formula 97 (x-) = two distributions that are tractable since we have samples from p and can approximate samples from transformations, as is typical contrastive learning methods (see Appendix E for extra discussion of practical implications of this approximation).
- 93 (x-)) ))/r /T- for the negative sampling distribution 93 in terms of
p+ using set of semantics-preserviie
possible to generate samples from ds and approximately from 03 using rejection sampling and data augmentations to generate positives. However, rejection sampling involves an algorithmic complication since the procedure for sampling batches must be modified. To avoid this, we instead take an importance sampling approach. To obtain this, first note that fixing the number Q and taking the limit N ou in the objective (1) yields.
(())) f(x
L(f.g) = E pop x xtop?
log fa ) QE, (eB--glefftnn (ef
The original objective (1) can be viewed as finite negative sample approximation to L(f.g) (note implicitly L(f. 9) depends on Q). Inserting q 93 and using the rearrangement of equation (2) obtain the following hardness-biased objective:
((x) s(at)
E pop x ttpp
log ef(x) f(x)) + Q
(4)
-- (E, was (x)) f(x 3] T engg
Ie (((l))
This objective suggests that we need only to approximate expectations Ez- je jef()) and Eungz (ed( ((v)] over qa and o (rather than explicily sampling). This can be achieved using
4

---

Published as a conference paper at ICLR 2021
classical Monte-Carlo importance sampling techniques using samples from p and p as follows:
Bg rua (e [e=))
[e = Fe-~~p
(x)) ((xT) /ga/pl = T rpp (((++))(()))) ((=)) /Zp]:
E Buwgz (e f(o) = Ex- le (x) f(0) /3/ /5/p11 = Euppt le ((++))(())) (6) /2z).
where ZB. Zzz are the partition functions of da and q3 respectively. The right hand terms readily admit empirical approximations by replacing p and pt with p(x)) Σi= 8 x, (I) and ş (z)
Σ 82- respectivelyy (6w. denotes the Dirac delta function centered w). The only unknowns left are the partition functions, Z Eg-=plee (e f(z and Z E (e f(x which themselves are expectations over and pt and therefore admit empirical estimates,
N
M
1 N
0f(2) H(77)
2
e Bfw)) S(a))
=
M
1=1
is important to emphasize the simplicity of the implementation of our proposed approach. Since we propose reweight the objective instead of modifying the sampling procedure, only two extra lines of code are needed to implement our approach, with no additional computational overhead. PyTorch-style pseudocode for the objective is given in Fig. 13 in Appendix D.
4
ANALYSIS OF HARD NEGATIVE SAMPLING
4.1 HARD SAMPLING INTERPOLATES BETWEEN MARGINAL AND WORST-CASE NEGATIVES
Intuitively, the concentration parameter 3 in our proposed negative sample distribution q3 controls the level of "hardness" of the negative samples. As discussed earlier, the debiasing method of Chuang al. (2020) can be recovered as special case: taking 3 case amounts to correcting for the fact that some samples in a negative batch sampled from will have the same label the anchor. But what interpretation does large 3 admit? Specifically, what does the distribution 93 converge to in the limit 3 + oc, if anything? We show that in the limit 93 approximates an inner solution to the following zero-sum two player game.
obtain the distribution % This
{xx) f(x))
inl sup ((J.g) =E s>p xt xtapt
log eflx) [(=)) + QB.--gggah (QB--agle(a)
(5)
I qell
where II fq x( supp (g(:x, S fo' X a' x), Vr E X) is the set of distributions with support that is disjoint from points with the same class as x (without loss of generality we assume {x' X : x' x x) is non-empty). Since q =( x. f) depends can be thought of as a family of distributions. The formal statement is as follows.
and f it
Proposition 3. Let L (f) sup L(f.q). Then for any > 0 and f X + 3d-1 /t observe the convergence L(J. 93 L (f) as B + co.
Proof. See Appendix A.1.
To develop a better intuitive understanding of the worst case negative distribution objective L (f) sup,en C(f, q), we note that the supremum can be characterized analytically. Indeed,
sup C(S,g) -E pap f(xt) + sup E w<p log Losfedto (et f(+t) + +E. lgle~lglle le (x)) f(x {(-) gEtt ztapt
gell
x =t=pt
--E x<p
f(x) f(x xtapt
x<p log (( s(xt) + +Q + sup Eg- - (ool" [|]))] qETl
xtmpp
The supremum over q can be pushed inside the expectation since q is a family of distribution indexed by æ, reducing the problem to maximizing E,, ~gle (ef(") ](="), which is solved by any q whose
support is subset of arg sup,, =z (x)) f(z if the supremum is attained. However, computing such points involves maximizing a neural network. Instead of taking this challenging route, using qg defines lower bound by placing higher probability on x for which f(x)² f(x-) ) is large. This (c))
lower bound becomes tight - co (Proposition 3).
5

---

Published as a conference paper at ICLR 2021
4.2 OPTIMAL EMBEDDINGS ON THE HYPERSPHERE FOR WORST- CASE NEGATIVE SAMPLES
What desirable properties does an optimal contrastive embedding (global minimizer of L) possess that make the representation generalizable? To study this question, we first analyze the distribution of an optimal embedding f* on the hypersphere when negatives are sampled from the adversarial worst-case distribution. We consider a different limiting viewpoint of objective (1) as the number of negative samples N + co. Following the formulation of Wang & Isola (2020) we take Q = N in (I), and subtract log N. This changes neither the set of minimizers, nor the geometry of the loss surface. Taking the number of negative samples N + 0o yields the limiting objective,
5(2))) f(xt) S(x+)
Lox (J. =E gmp logg Eg Ee-~glesta) ((=)))
(6)
2x rup
Theorem 4. Suppose the downstream task is classification (i.e. C is finite), and let Lic (f) = sup oo (f.9) q). The infimum inf measurable Lo0 (f) is attained, and any f achieving the global minimum is such that (x) (*(x almost surely. Furthermore, letting Ve (x)x for any
such that h(z)- = c (so Ve is well defined up to set of x of measure zero), f is characterized as being any solution to the following ball- packipa problem,
Σp(e) GEC
min lIve 1 Verl?? d'sc
max [v.
1/t)
Proof. See Appendix A.2.
Interpretation: The first component of the result is that -x= almost surely for an optimal f" That is, an optimal embedding f" must be invariant across pairs of similar inputs x, The second component is characterizing solutions via the classical geometrical Ball-Packing Problem of Tammes (1930) (Eq. 7) that has only been solved exactly for uniform p. for specific of C and typically for Sa (Schütte & Van der Waerden, 1951; Musin & Tarasov, 2015; Tammes, 1930). When the distribution over classes is uniform this problem is solved by a set of [C] points on the hypersphere such that the average squared-22 distance from a point the nearest other point is as large as possible. In other words, suppose we wish to place (CI number of balls! on g so that they do not intersect. Then solutions to Tammes' Problem (7) expresses (twice) the largest possible average squared radius that the balls can have. So, we have ball-packing problem where instead of trying to pack as many balls as possible of a fixed size, we aim to pack a fixed number of balls (one for each class) to have as big radii possible. Non-uniform, p adds importance weights each fixed ball. In summary, solutions of the problem miny L (f) are a maximum margin clustering.
This understanding of global minimizers of (f) supgen (f. can further developed into a better understanding of generalization on downstream tasks. The next result shows that representations that achieve small excess risk the objective 4% still separate clusters well in the sense that a simple 1-nearest neighbor classifier achieves low classification error.
Theorem 5. Suppose p is uniform C and f is such that (f) inf measarable (f) S
with ε S 1. Let {v²- E /d-1/t) be a solution to Problem 7, and define the constant & = mine,e- mine,,e-effe-11 llv: -== O. Then there exists a set of vectors {vo E gd-1/OJoee such that the 1-nearest neighbor classifier h(x) arg minsec ffx)) - vell (ties broken arbitrarity) achieves misclassification risk,
& P (e,(h(z)+ # (c) (G2 22-2|C (1 + 1/2)
Proof. See Appendix A.3.
In particular, P(((()) fc) (e) as E - 0, and in the limit e - we recover the invariance claim of Theorem 4 as special case. The result can be generalized to arbitrary P by replacing [C] in the bound by 1/ min, p(c). The result also implies that it is possible to build simple classifiers for tasks that involve only a subset of classes from C, or classes that are union of classes from C. The constant ç = min V v > a purely geometrical property of spheres, and describes the minimum separation distance between a set of points that solves the Tammes' ball-packing problem.
Foor manifold M C TRd, we say C c M is hall if it is connected, and there exists Fuclidean ball B {a Rd ||]||| S R} for which C = M.B.

---

Published as a conference paper at ICLR 2021
5 EMPIRICAL RESULTS
Next, we evaluate our hard negative sampling method empirically, and apply it as a modification to state-of-the of-tthe-rt art contrastive methods image, graph, and text data. For all experiments 3 is treated as a hyper- parameter (see ablations in Fig. for more understanding of how to pick 9). Values for M and 7+ must also be determined. We fix M for all experiments, since taking M > 1 would increase the number of inputs for the forward-backward pass. Lemma 11 in the appendix gives a theoretical justífication for the choice of M 1. Choosing the class-prior 7- can be done in two ways: estimating it from data (Christoffel et al., 2016: Jain et al., 2016), or treating it as hyper-parameter. The first option requires the possession of labeled data before contrastive training.
5.1 IMAGE REPRESENTATION
We begin by testing the hard sampling method on vision tasks using the STL10, CIFARI00 and CIFARIO data. We use SimCLR (Chen et al., 2020a) the baseline method, and all models are trained for 400 epochs. The results in Fig. 2 show consistent improvement over SimCLR p) and the particular case of our method with / 0 proposed in (Chuang al., 2020) (called debiasing) on STL10 and CIFARIOR 100. For N = 510 negative examples per data point we observe absolute improvements of 3% and 7.3% over SimCLR on CIFAR 100 and STLIO respectively, and absolute improvements over the best debiased baseline of 1.9% and 3.2%. On tinylmageNet (Tab. 1) we observe an absolute improvement of 3.6% over SimCLR, while on CIFARIO there is a slight improvement for smaller N. which disappears at larger N. See Appendix C.I results using MoCo-v2 for large negative batch size, and Appendix D.I for full setup details.
Top-1 Accurscy
40
Trp-1 Accurwy
Trg-I Accuray
90.0
87.5
Dehinel
Deince
(5-,7
35.0
Ditene
Debiaeed 150
Détane ( -6:0
Detined .039
Hant 05. ..0
[l 026)
82.5
05, a00
Hand (1-1,
Hand -040
Bard (1 1.
60
$0.0
254
510
510
Negutive Sample N (STL10)
Negative Sample Size (CIFARIO))
Negative Sample Size (CIFARIO)
Figure 2: Classification accuracy on downstream tasks. Embeddings trained using hard, debiased, and standard (3 = O = 0) versions of SimCLR, and evaluated using linear readout accuracy.
5.2 GRAPH REPRESENTATIONS
Second, we consider hard negative sampling in the context of learning graph representations. We use the state-of-the- art InfoGraph method introduced by Sun et al. (2020) as the baseline, which is suitable for downstream graph-level classification. The objective is of slightly different form from the NCE loss. Because of this we use generalization of the formulation presented in Section (See Appendix B for details). In doing so, we illustrate that it is easy to adapt our hard sampling method to other contrastive frameworks.
SimCLR
Debiased
Hard (3 1)
53.4%
53.7%
57.0%
Table 1: Top-1 linear readout on tinylm- ageNet. Class prior is set to - = 0.01.
Fig. 3 shows the results of fine-tuning the fixed, learned embedding for a range of different values of 3. Hard sampling does as well as InfoGraph in all cases, and better in 6 out of 8 cases. For ENZYMES and REDDIT, hard negative samples improve the accuracy by 3. 3.2% and 2.4%, respectively, for DD and PTC by 1 - 2%, and for IMDB-B and MUTAG by at least 0.5%. Usually, multiple different choices of B 0 were competitive with the InfoGraph baseline: 17 out of the 24 values of B > O tried (across all 8 datasets) achieve accuracy as high or better than InfoGraph (3 = 0).
SVM (Boser al., 1992; Cortes & Vapnik, 1995) on
5.3 SENTENCE REPRESENTATIONS
Third, we test hard negative sampling on learning representations of sentences using the quick- thoughts (QT) vectors framework introduced by Logeswaran & Lee (2018), which uses adjacent sentences (before/after) as positive samples. Embeddings are trained using the unlabeled BookCorpus dataset (Kiros et al., 2015), and evaluated following the protocol of Logeswaran & Lee (2018) on six downstream tasks. The results are reported in Table 2. Hard sampling outperforms equals the QT
7

---

Published as a conference paper at ICLR 2021
Info Graph (B 0)
Hard (3
Hard 2)
Hard 10)
DD
PTC
REDDIT-B
Accuracy
72.5%
72.8%
72.2%
73.8%
55.3% 57.1% 56.2% 56.9% AU
81.0%
83.4%
80, 10.0%
74.3%
74.2% 74.1% 74.5%
ENZYMES
IMDR-B
IMDB-MM
50.4%
51.2%
51 44%
53.6%
66. 8%
86.4%
87.3%
87.3%
72.2%
72.6%
72.6%
72.8%
49.6%
49.2%
49.4%
49.6%
Average Accuracy
Figure 3: Classification accuracy downstream tasks. We compare graph representations four classification tasks. Accuracies are obtained by fine-tuning an SVM readout function, and are the average of 10 runs, each using 10-fold cross validation. Results in bold indicate best performer.
baseline in 5 out of 6 cases, the debiased baseline (Chuang et al., 2020) in 4 out of 6, and both in out of cases. Setting 7 > 0 led to numerical issues in optimization for hard sampling.
Objective
MR
CR
SUBJ
MPQA
TREC
MSRP
(Acc)
(F1)
QT (6 7+ 0) Debiased (r+ = 0.01)
76.8
81.3
86.6
93.4
89.8
73.6
81.8
76.2
82.9
86,9
93.7
89.1
74.7
82.7
Hard (B 1, 0)
77.1
82.5
87.0
92.9
89.2
73.9
82.2
Hard (8 2, 7 = 0)
77.4
83.6
86.8
93.4
88.7
73.5
82.0
Table 2: Classification accuracy downstream tasks. Sentence representations learned using quick-thoughts (QT) vectors on the BookCorpus dataset and evaluated on six classification tasks. Evaluation binary classification tasks (MR, CR, SUBJ, MPQA) uses 10-fold cross validation.
A CLOSER LOOK AT HARD SAMPLING
6.1 ARE HARDER SAMPLES NECESSARILY BETTER?
By setting 3 to large values, one can focus on only the hardest samples in a training batch. But is this desirable? Fig. 4 (left, middle) shows that for vision problems, taking larger 3 does not necessarily lead to better representations. In contrast, when one uses true positive pairs during training (green curve,
label information for positive but negative pairs), the downstream performance monotonically increases with / until convergence (Fig. 4. middle). Interestingly, this achieved without using label information for the negative pairs. This observation suggests an explanation for why bigger 3 hurts performance in practice. Debiasing (conditioning on the event (M(x) * h(x=)) )}) using the true p* corrects for sampling x with the same label as æ. However, since in practice we approximate p* using set of data transformations, we can only partially correct. This is harmful for large 3 since this regime strongly prefers x for which f(x is close to f(x:), many of whom will have the same label
if not corrected for. We note also that by annealing / (gradually decreasing to throughout training, see Appendix D. for details) possible to be more robust the choice of initial B, with marginal impact downstream accuracy compared to the best fixed value of (3.
6.2 DOES AVOIDING FALSE NEGATIVES IMPROVE HARD SAMPLING?
Our proposed hard negative sampling method conditions on the event {h(x) * [(xT)} in order to avoid false negatives (termed "debiasing" (Chuang et al., 2020)). But does this help? To test this, train four embeddings: hard sampling with and without debiasing, and uniform sampling (8 0) with and without debiasinn. The results in Fig. 4 (right) show that hard sampling with debiasing obtains the highest linear readout accuracy on STL10, only using hard sampling or only debiasing yields (in this case) similar accuracy. All improve over the SimCLR baseline.
8

---

Published as a conference paper at ICLR 2021
Debiased
Debiased
Top: 1 Accurary
Top: 1 Accuracy
66-
Handd Sampling
0.05 annesicd) True positives
87.44 %
84.41 %
04-
62-
SInCLR 05-0.r=00
0.1
Not Hard Samp ling
84.26 %
80.15 %
80
0.0
1.0
2.0
6.0
0.0
6.5
2.
B (STL10)
B (CIFARI0O)
Figure 4: Left: the effect of varying concentration parameter / on linear readout accuracy. Middle: linear readout accuracy as concentration parameter varyies, the case of contrastive learning (fully unsupervised), using true positive samples (uses label information), and an annealing method that improves robustness to the choice of 3 (see Appendix D. for details). Right: STL10 linear readout accuracy for hard sampling with and without debiasing, and non-hard sampling (B 0) with and without debiasing. Best results come from using both simultancously.
Frequency Frequency
H D (Ours)
& mot D
not H & not (SimCLR)
Posilive Pairs
Negulive Pairs
65
18 k
05
La
0. LG 60
0. Similrrty
Similarity
Simiartty
Simiarity
Similarity
Similarity
Figure 5: Histograms of cosine similarity of pairs points with the same label (top) and different labels (bottom) for embeddings trained on STL10 with four different objectives. H-Hard Sampling, D-Debissing. Histograms overlaid pairwise to allow for convenient comparison.
Fig. 5 compares the histograms of cosine similarities of positive and negative pairs for the four learned representations. The representation trained with hard negatives and debiasing assigns much lower similarity score to a pair of negative samples than other methods. On the other hand, the SimCLR baseline assigns higher cosine similarity scores to pairs of positive samples. However, to discriminate positive and negative pairs, key property is the amount of overlap of positive and negative histograms. Our hard sampling method achieves less overlap than SimCLR, by better trading off higher dissimilarity of negative pairs with less similarity positive pairs. Similar tradeoffss are observed for the debiased objective, and hard sampling without debiasing.
6.3 How DO HARD NEGATIVES AFFECT OPTIMIZATION?
Fig. 11 (in Appendix C due space constraints) shows the performance on STL10 and CIFAR100 of SimCLR versus using hard negatives throughout training. We use weighted k-nearest neighbors with A: = 200 as the classifier and evaluate each model once every five epochs. Hard sampling with 3 = leads to much faster training: STL10 hard sampling takes only 60 epochs reach the same performance as SimCLR does in 400 epochs. On CIFAR 100 hard sampling takes only 125 epochs to reach the same performance SimCLR does in 400 epochs. We speculate that the speedup is, in part, due to hard negatives providing non-negligible gradient information during training.
7 CONCLUSION
We argue for the value of hard negatives in unsupervised contrastive representation learning, and introduce simple hard negative sampling method. Our work connects two major lines of work: contrastive learning, and negative mining in metric learning. Doing so requires overcoming an apparent roadblock: negative mining in metric learning uses pairwise similarity information core component, while contrastive learning is unsupervised. Our method enjoys several nice aspects: having desirable theoretical properties, very simple implementation that requires modifying only couple of lines of code, not changing anything about the data sampling pipeline, introducing zero extra computational overhead, and handling false negatives in principled way.

---

Published as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. theoretical analysis of contrastive unsupervised representation learning. In Int. Conference on Machine Learning (ICML). pp. 5628-5637, 2019.
Philip Bachman, Devon Hjelm, and William Buchwalter.
Learning representations by maximizing mutual information across views. In Advances in Neural Information Processing Systems (NeurIPS), pp. 15535-15545, 2019.
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Proceed- ings of the eleventh annual conference Computational learning theory, pp- 92-100, 1998.
Bernhard Boser, Isabelle Guyon, and Vladimir N Vapnik. training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory, pp. 152, 1992.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Int. Conference on Machine Learning (ICML), pp. 10709-10719, 2020a.
Ting Chen, Simon Korbblihh, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self-supervised models are strong semi-supervised learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020b.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv:2003.04297, 2020c.
Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning a similarity metric discriminatively, with application to face verification. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), volume 1, pp. 539-546, 2005.
Marthinus Christoffel, Gang Niu, and Masashi Sugiyama. Class-prior estimation for learning from positive and unlabeled data. In Asian Conference on Machine Learning, pp. 221-236, 2016.
Ching Yao Chuang, Joshua Robinson, Lin Yen-Chen, Antonio Torralba, and Stefanie Jegelka. De- biased Contrastive Learning. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Corinna Cortes and Vladimir Vapnik. Support- Vector Networks. Machine learning, 20(3):273-297, 1995.
Bill Dolan, Chris Quirk, and Chris Brockett. Unsupervised construction of large paraphrase corpora: Exploiting massively parallel news sources. In Proceedings of the 20th international conference Computational Linguistics, pp. 350. Association for Computational Linguistics, 2004.
Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In Advances in Neural Information Processing Systems (NeurIPS), pp. 703-711, 2014.
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 213-220, 2008.
Weifeng Ge. Deep metric learning with hierarchical triplet loss. In Europ. Conference on Computer Vision (ECCV), pp. 269-285, 2018
Michael Gutmann and Aapo Hyvärinen. Noise-Contrastive Estimation: A new estimation principle for unnormalized statistical models. In Proc. Int. Conference on Artificial Intelligence and Statistics (AISTATS), pp. 297-304, 2010.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning invariant mapping. In JEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1735- 1742, 2006.
10

---

Published as a conference paper at ICLR 2021
Ben Harwood, Vijay Kumar BG, Gustavo Cameiro, lan Reid, and Tom Drummond. Smart mining for deep metric learning. In Int. Conference on Computer Vision (ICCV), pp. 2821-2829 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. Int. Conference on Machine Learning (ICML), pp. 3451-3461, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016.
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.
Olivier 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. In Int. 2020.
Conference on Machine Learning (ICML), pp.
Minqing Hu and Bing Liu. Mining and summarizing customer reviews. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 168-177, 2004.
Shantanu Jain, Martha White, and Predrag Radivojac. Estimating the class prior and posterior from noisy positives and unlabeled data. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2693-2701, 2016.
YouYoung Jin, Aruni RoyChowdhur,, Huaizu Jiang, Ashish Singh, Aditya Prasad, Deep Chakraborty, and Erik Learned-Mllerr Unsupervised hard example mining from videos for improved object detection. In Europ. Conference Computer Vision (ECCV), pp. 307-324, 2018.
Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus. Hard negative mixing for contrastive learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. arXiv:2004. 11362, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Int. Conf. on Learning Representations (ICLR), 2015.
Ryan Kiros, Yukun Zhu, Russ R Salakhutdinov, Richard Zemel, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. (NeurIPS), pp. 3294-3302, 2015.
Vectors. In Advances in Neural Information Processing Systems
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity graph structured objects. Int. Conference on Machine Learning (ICML), pp. 3835-3845, 2019.
Lajanugen Logeswaran and Honglak Lee. tions. In Int. Conf. on Learning Representations (ICLR), 2018.
An efficient framework for learning sentence representa-
K. V. Mardia and Jupp. Directional Statistics. John Wiley and Sons Ltd., second edition, 2000.
Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invariant representations. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 6707-6717, 2020.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. Graph Representation Learning and Beyond, ICML. Workshop, 2020.
Oleg R Musin and Alexey S Tarasov, The tammes problem for n= 14. Experimental Mathematics, 24 466-466488. 2015.
11

---

Published as a conference paper at ICLR 2021
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-GAN: Training generative neural samplers using variational divergence minimization, In Advances in Neural Information Processing Systems (NeurlPS), pp. 271-279, 2016.
Aaron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. /807.00007.031 0374488.......... 2018.
Bo Pang and Lillian Lee. A sentimental education: Sentiment analysis using subjectivity summa- rization based minimum cuts. In Proceedings of the 42nd annual meeting on Association for Computational Linguistics, pp. 271. Association for Computational Linguistics, 2004.
Bo Pang and Lillian Lee. Seeing stars: Exploiting class relationships for sentiment categorization with respect rating scales. In Proceedings of the 43rd annual meeting association for computational linguistics, pp. 115-124, Association for Computational Linguistics, 2005.
Senthil Purushwalkam and Abhinav Gupta. Demystifying contrastive self-supervised learning: Invariances, augmentations and dataset biases. arXiv:2007.13916 2020.
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 815-823, 2015.
K Schütte and BL Van der Waerden. Auf welcher kugel haben 6, 7, 8 oder 9 punkte mit mindestabstand eins platz? Mathematische Annalen, (23(1):96-224, 1951.
Pierre Sermanet, Corey Lynch, Yevgen Chebotar, Jasmine Hsu, Eric Jang, Stefan Schaal, Sergey Levine, and Google Brain. Tomme-cntrasstive networks: Self-supervised learning from video. In 2018 IEEE International Conference on Robotics and Automation (ICRA); pp. 1134-1141, 2018.
Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. Deep metric learning via lifted structured feature embedding. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4004-4012, 2016.
Aravind Srinivas, Michael Laskin, and Pieter Abbeel. CURL: Contrastive unsupervised repre- sentations for reinforcement learning. In Ini. Conference on Machine Learning (ICML), pp. 10360-10371, 2020.
Yumin Suh, Bohyung Han, Wonsik Kim, and Kyoung Mu Lee. Stochastic class-based hard example mining for deep metric learning, In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 7251-7259, 2019.
Fan-You Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. InfoGraph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. Int. Conf. on Learning Representations (ICLR), 2020.
Tristan Sylvain, Linda Petrini, and Devon Hjelm. Locality and compositionality in zero-shot learning. In Int. Conf. on Learning Representations (ICLR), 2020.
Pieter Merkus Lambertus Tammes. On the origin of number and arrangement of the places of exit on the surface of pollen-grains. Recueil des travaux botaniques néerlandais, 27(1): 1930.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive Multiview Coding. In Europ. Confer- ence on Computer Vision (ECCV), pp. 770-786, 2019.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? arXiv:2005. 10243, 2020.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. In Int. Conf. on Learning Representations (ICLR), 2019.
Ellen M Voorhees and Donna Harman. Overview of trec 2002. 2002.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In Int. Conference on Machine Learning (ICML), pp. 9574-9584, 2020.
12

---

Published as a conference paper at ICLR 2021
Janyce Wiebe, Theresa Wilson, and Claire Cardie. Annotating expressions of opinions and emotions in language. Language resources and evaluation, 39(2-3):165-216 2005.
Chao-Yuan Wu, R Manmatha, Alexander Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In Int. Conference on Computer Vision (ICCV), pp. 2840-2848, 2017.
Chang Xu, Dacheng Tao, and Chao Xu. A survey on multi-view learning- arXiv: 2013.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Int. Conf. Learning Representations (ICLR), 2019.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In Int. Conf. on Learning Representations (ICLR), 2018.
13

---

Published as a conference paper at ICLR 2021
A ANALYSIS OF HARD SAMPLING
A. HARD SAMPLING INTERPOLATES BETWEEN MARGINAL AND WORST- NEGATIVES
We begin by proving Proposition 3. Recall that the proposition stated the following.
Proposition 6. Let (J) sup C(J.g) q). Then for any i > 0 and measurable f X - S4-1/1 we observe the convergence [(f. 9g - (f) as + co.
Proof. Consider the following essential supremum,
M(x)
sup
m 2 {()) a.s. for xt up }. [xx) sup(m m0mm
EX::
The second inequality holds since supp(p) X. We may rewrite
(w)) f(+
s(=t)
(') E pmpp x xtrpp
log
ef(xr) f(+t) + Qe 7
f(x)) f(at)
((f.9g) = mmp up
log f(x+) + QB g-p ~ag (c((a)(aa)))
The difference between these two terms can be bounded as follows,
(f( ((x)) + QeM(s) + log ed(w)) + QE, maz [eseeoo) S(-O]
ef(a) f(+t)
(C(()) - -(f
E amp
log
x up!
+QE -Eg (es(a)" (1))))))))
log Llog(edto (ef(o)) s(+t) + QoM(
EE xmp
log
upp
1/1
((x)) f(x + +QE QE woj [ed(s) 1(= y ed(a)) s(x)) Qe
aap xt xtapp
Q+1
e/tQQ
Exup By Ba (er(ar) f(0 [( - M(x
Q +
S 1/t EEMPB Ma2 - e(0))" ((x)) s(x
where for the second inequality have used the fact that lies on the hypersphere of radius 1/t to restrict the domain of the logarithm to values greater than (Q ( 1)e- Because of this the logarithm is Lipschitz with parameter (Q + 1). Using again the fact that f lies on the hypersphere know that fx) f(--)) S 1/t² and hence have the following inequality,
Expp E
E 13
_ (an) ) s c/l/1B
M(0)
Eenp B ((===)(())T(()
Let us consider the inner expectation FT((x) = bounded, (x( is uniformly bounded in x. Therefore, in order to show the convergence L(J, 93 + (f) as 3 + co, it suffices by the dominated convergence theorem to show that Eạ(x) + 0 pointwise as + oo for arbitrary fixed x E X.
Note that since f is
From now on we denote M = (x) for brevity, and consider a fixed x E X. From the definition of 45 it is clear that 03 < p- That is, since 43 = c. p for some (non-constant) e, it is absolutely continuous with respect p So M(x) 2 [(x)][(>>)
[(xT) almost surely for x. 93 and
14

---

Published as a conference paper at ICLR 2021
may therefore drop the absolute value signs from our expectation. Define the following event g: = for f(x) f(z))2 2 M =} where & is refers to "good" event. Define its complement
B = Ge where B is for "bad". For a fixed X' and >> 0 consider,
Eạ(x) = E2 : M(x) - -(())
P Pn (9e) E ~4g |M<()) ((()" f(x f(x
[(x) |9
+ +P 29~ (Ba) E ~gp
[xx
x-
$ ~u (Ge) E ++ 2PP ~~~ (Ba)
S E 2P x ~ (Bz).
We need control P. Pa-~aj (B&). Expanding.
(Af(x) .p (x
P ~ (B&) / 1 (0)
Zg dx
xx
s(0))p )p (- (x- )dz is the partition function of 43 where ZB ex 1(0
We may bound this
expression by,
/ 1 { MM cB(M-c) .p (p(x0)
@8(M-c)
dr
S(x [1
1
M M (x )dd
Zg
Zg
3(M
c)
Px-~p-1 (Bs)
7B
((M
ZB
Note that
73 / 3s()) s()T) 'p (s5)da 2 (
(f(x)= 2 ee22).
By the definition of M = ((x) the probability Pe = P. P2--D f(x)) 2 - - > 0, and we may therefore bound,
((M
P ~ (Be) = (
= e -Be22/
as oc.
We may therefore take 3 to be sufficiently big so to make I. mag (Be) s and therefore Eg (x) < 3s. In other words, Ex(x) -
+ 0 as B + xc.
A.2 OPTIMAL EMBEDDINGS ON THE HYPERSPHERE FOR WORST- CASE NEGATIVE SAMPLES
In order to study properties of global optima of the contrastive objective using the adversarial worst case hard sampling distribution recall that we have the following limiting objective,
F(x) s(ot)
Loe (J.9) = E xop xt
log EE
(8)
(efl f(x o]
maga
We may separate the logarithm a quotient into the sum of two terms plus a constant,
Loo (f,4) Latign (f) Lunar 1/1²
15

---

Published as a conference paper at ICLR 2021
where (fliga(f) Ez.z+ (x) /12+)11//2 and Cfmr(ff.) Ez log Eg- gg ef(a) ( f(z Here we have used the fact that f lies on the boundary of the hypersphere radius 1 1/t, which gives us the following equivalence between inner products and squared Fuclidean norm,
2/t² - 2f(x) f(x 1 + -
f(x)) (9)
Taking supremum to obtain (f) = supgen Lo (f, we find that the second expression simplifies to,
(f) = sup Luiit (f. = Exup log sup ( f(x") Expp sup f(x) mx
T f(x))
NEfT
x 4x
Using Eqn. (9), this can be re-expressed as,
Egpp sup f(x) mx
f(x -Exop inf [1[(x) fa=>)|1 /2 1/p.
(10)
The forthcoming theorem exactly characterizes the global optima of miny C:c (f)
Theorem 7. Suppose the downstream task is classification (iee. C finite), and let E (f) supyen L (f.9). The infimum inf measurable (f) is attained, and any f achieving the global minimum is such that f (x) f (xx
almost surely. Furthermore, letting Ve (x) for any
such that h(x) = c (so Ve is well defined up to a set of x of measure zero), f is characterized as being any solution the following ball-packing problem,
max
Ed(c)
p(c) min lIve vorl
(II)
(v (V.E8a-1/0b) 1/DJEEC CEC
c'Fc
Proof. Any minimizer of Latign()) (f') has the property that f(x) f(x)) almost surely. So, in order to prove the first claim, it suffices show that there exist functions f arg inf, (fme(f) for which f(x) = f(x+) almost surely. This is because, at that point, we have shown that arg min, Latign (f) and arg min, Limit() intersect, and therefore any solution of (J) Latign (f) + f (J) must lie this intersection.
To this end, suppose that f E arg min, (J) but that f(x) * f(x+) with non-zero probability. We shall show that we can construct a new embedding such that f(x) = f fx*)) almost surely, and Lini < (f). Due to Eqn. (10) this last condition is equivalent to showing,
Exep inf [f(x)) - f(x f(x Eenp inf 11((x) - 21 x- uz
(12)
x
Fix c C, and let xe E arg max, (())= inf, ax [ff(z) f(x The maximum is guaranteed to be attained,
explain now. Indeed know the maximum is attained some point in the closure 0(x h(x) = c) U fz h(x) c). Since X' compact and connected, any point c) such that inf l [(= 0 since F must belong to fa l(x)) = e') for some other c'. Such an I cannot be a solution unless all points in
0fx h(x) c} (x h(x)
(o h(x) = c) also achieve 0, in which case we can simply take x, to be point in the interior of {z: h(z) = c).
Now, define f(x) f(x) for any x such that h(x) = and f(x) f(x) otherwise. Let us first aim to show that Eqn. (12) holds for this f. Let us begin expand the left hand side of Eqn. (12),
16

---

Published as a conference paper at ICLR 2021
Ex-p inf (1(()) - [11
= Bemp (6) inf llf(x) f(x 1|?
= =p(c)Bespptlc) inf [lf(x) - }11
+ + - (ec)) B(mp))))) x o0x
inf llf(x) - f(x }1?
=c(c)Berr(ied inf [1(()) f )11
x mix
(1 Be inf f(xx))
x wax
= p(c) inf llf(zz) - f(x )11
a0 (1
inf [1((z) f(x
(13)
h(x h(x-)##
By construction, the first term can be lower bounded by infz ma. (1f( - f( > Ex-e(-le) ==f (ff [(=))|2 for any such that h(xx) = To lower bound the sec- ond term, consider any fixed è o e and x ~ pl-lé) (so h(x) = é). Define the following two subsets of the input space
A= ((=))) è for x' E (= f(x)(()))))))) + for x E X..
Since by construction the range of f is subset of the range of f, we know that A A. Combining this with the fact that f(z) = fxx whenever h(x) = * e we see,
inf h(w )#8
inf 1f(x)) - f(x=)112 (1f(z)) - h(x )#E
inf [lf(x)) - -ull2
ue
inf [1/(x)) -ul2
inf [[f(z) - f(x )]1
Using these two lower bounds we may conclude that Eqn. (13) can be lower bounded by,
p(c)Eaep((e) inf M(x") 1ec
llf(x) f(x )1 + (1 -
Exmp(())
inf M(= }
[lf(x)) - f1
which equals Egep inf=-wa [ - fx 21? We have therefore proved Eqn. (12). To summarize the current progress; given an embedding f we have constructed new embedding f that attains lower Lunar loss and which is constant x such that f is constant on {z h(x)) = c}. Enumerating (cI, ). we may repeatedly apply the same argument to construct sequence of embeddings fi, fe. fe..... .. ffc! such that f; is constant on each of the following sets {z hhx)) cy for j S i. The final embedding in the sequence f fíc is such that ( f is minimizer. This embedding is constant each of {x h(x)) = =c² for 1, CC.. In other words, fx) = f= (x**) almost surely. We have proved the first claim.
L (f) and therefore
Obtaining the second claim is matter of manipulating C: (f*). Indeed, we know that Cz (f*) Limi 1/t² and defining v. = f (x) f(xx) for each e E C, this expression minimized and only if f attains,
17

---

Published as a conference paper at ICLR 2021
max
h(a Exup inf [1((x) f(x [[1 max BowpBeeptte inf (f) - f(x I|(
f
max
p(c)
inf [z) f(x )1( h(a))
max (v.E50-1 1//50-
Σ p(c) min CFc
||ve verl1
where the final equality inserts f as an optimal f and reparameterizes the maximum to be over the set of vectors {v- E 8d-1//Joocc
A.3 DOWNSTREAM GENERALIZATION
Theorem 8. Suppose is uniform C and f is such that ( inf measurable Lix (f) S 8 with E S Let {v² E 3d-1/() be solution to Problem 7, and define & min -ette- -v-l--l1 O. Then there exists set of vectors {ve E Sd-1/t]oes such that the following I-nearest neighhor classifier,
Mx)= = 2 where == arg min f(x) vell
(ties broken arbitrarily)
BEC
achieves misclassifccation risk,
85
+() #c) (52 [ (1 1/2)
Proof. To begin, using the definition of h we know that for any E.
P2,c((aa))))> = PP.c (1((x)) vell s min [1[(x) - vo-11 #c
Px, (1[(x)) -voll s 6, and 85 min [1{(z) vo-1)
#c
1 Px.c (l](()) -vel vel > 6) Pao min [[(() ve- <))
So to prove the result, our goal is now bound these two probabilities. To do so, we use the bound on the excess risk. Indeed, combining the fact 4 (f) - inf, mensurable 2- (x S with the notational
rearrangements before Theorem 7 we observe that E, E, flf(=))()))))))))){()) - f(x f( < 2s.
We have,
Ext 28 Ex,x+ - Pew
For fixed c, ct let Te E arg min minl sh(w )=e} E. 1nmp(1o)]((a f( where we extend the minimum to be over the closure, compact set, to guarantee it is attained. Then we have
2: > Be Eapn [l)((())))))))))(()) s(x Be-pee))()) - v.ll2 -v.l
where we have now defined v. = f (xx) for each e E C. Note in particular that v, lies on the surface of the hypersphere gt. This enables obtain the follow bound using Markov's inequality,
18

---

Published as a conference paper at ICLR 2021
Pz. (l)(C)) - voll >6) PPa (15(x)) vell2 > 82)
Baral Ba,al((s)) vell
8²
2s
8²
so it remains still to bound Pa.e (el
[ -xx)-v-
< 8).
Defining g
ming.e repee Ie Vo-ll. we have the following fact (proven later).
Fact (see lemma 9): E'2 5 (1+
Using this fact we are able to get control over the tail probability as follows,
Pa,c min - vo- <
< Pz,c
(I]((x) vzl > 5¹ -6)
([](()) - voll > & - V - (1
< Pz.
(l((x) - voll > (v 2/0 21 - 5)2
= Pa.
2
(V - 2|/2 (1 1/t)e1/2 - -8)2
where this inequality holds for for any 0 5 - - 2/c| (1 + 1/1)51/2.
Gathering together our tail probability bounds we find that (h(x) c) 2 1
2g
g
200-20000-/////2--0 for any 0 8 V 2/c| (1 + 1/t)e2/2, That is,
P (2,0(h(z) xc) 2x
(V - 2/C| (1 1/t)= - 8)2
Since this holds for any 5 < / 2 (1 + 1/1)e1/2,
2
2s
P (1(zz) #c)
min
0565 / 201=
82
(1 + 1/t)= 8)2
Elementary calculus shows that the minimum is attained 8 v/2 201120( Plugging this in yields the final bound,
2
8
P(h(x) # +c) S (E2 - 2|c| +1+1)))
Lemma 9, Consider the same setting as introduced in Theorem 5. In particular define
g' = min IIve 0,0 sefo
ve-ll. Il:
g
min 0.0 cote
IV2 - vā-
where (v² sd- /t/e/ is a solution to Problem 7, and (ve o0t11/t/EC is defined via ve f(xc) with De E arg min [ Ex-pt f[x) - f(zt)|| for each E C. Then we have,
5' 2 / 2|C| (1 + 1/t)el/2
19

---

Published as a conference paper at ICLR 2021
Proof. Define,
X= min live vo-1l? c tc
X min c ic #c
|v v2_
X and X are random due the randomness of We can split up the following expectation by conditioning on the event {X & } and complement,
- - X = P(X
& XX - -X.
(14)
Using (f) (f)) measurable Foo (f) < 8 and the notational re- writiing of the objective 2% introduced before Theorem 7, we observe the following fact, whose proof we give in separate lemma after the conclusion of this proof.
Fact (see lemma 10): EX* 2 1/1+1 E < EX
This fact implies in particular TE[X - X* and E X X < 2(1 1/t/e.. Inserting both inequalities into Eqn. 14 we find that E - X - 2(1 + 1/t)ve. In other words, since is uniform.
min lIve va-1l²
min llv: v=-11² S 2 + 1//0VE.
C
se- #
c-se-tc #C
EEC
From which we say that for any E C.
min IVo - v= -=11/= 2|1 (1]]((++110)) 111)/E.
min llve -
1ic-va-li vo-112
c
So sell Ve - vo-1l
mminl-o= - v2 11 22|C|| (1+ 1/t)
V - [1 1/2)=2/2.
Since this holds for any c E C we conclude that
E' e - 2 1/t)
Lemma 10. Consider the same setting as introduced in Theorem 5. Define also,
min I|ve vo-113
X min Ivē v2 c0
e =c #0
#c
where v. fxx) with arg min have,
E Ba) [f(x) f(x for each C. We
(z+th(=t)= m
- + 1/t) EX EX.
Proof. By Theorem 7 we know there is an f attaining the minimum inf meusurable C (f) and that this f attains Canggn (f*) = O, and also minimizes the uniformity term Cimit taking the value (5a) Boop max.-:e- #c v ve_ Because of this find
Cimit < (I) (()()))) + (Caligo - (a)) + Limie < (c (f) (- + (fm
< + ((")
+ Eeop
max v. v--.
sc #c
20

---

Published as a conference paper at ICLR 2021
Since would like to bound Bexp max, to ph Ve Ve- in terms of Boup max, ie de Vc V this observation means that is suffices bound Bexp maxe- se Ve Ve- in terms of ()nit()) To this end, note that for fixed e, and & such that h(x) = c we have,
sup {vo [(=))+++++++0
vo)
sup 42
xx
sup ve T f(x -1 - -velltt
x *
max Vo f(x) -11 11)((x) vell /6
a E(Felece
max T Ve- -1f((2) - vell /t
#c
where the inequality follows since {weJOEC is subset of the closure of {x x d x). Taking expectations over c, x.
(fnit Ex sup f(x) f(x=)
2 Eeep max Ve Ve- - Eo,ell(((s)) voll /t
2 Eeep max Ve Ve- - V /Bsalls(as [(x) - vell?/1 e fc
2 Beep max Ve Ve- - Ve/t.
So since S VE, have found that
Bewp max Ve #c
S + Beup max ve
VoVVz vo <1 1/t)VE +
Eeup max vo V
c #0
Of course also have,
Eeup max vo T V= =(ini((()) & Boxp
max Ve #0
V
10 #0
since the embedding (xx = va whenever h(x)) e also a feasible solution. Combining these two inequalities with the simple identity x x = 1/t² ||x - 2 /2 for all length 1/t vectors x, y, we find,
1/2² - Beep max |lv -v: v= 11 1/12 11//2 - -eep max live- - 1o-22112 /2 e-se- #c
c- 4c
$ 1/t² - Eeup
max |lv2 v 1/2/2+ + (1+ 1/t) #
Subtracting 1/t2 and multiplying by -2 yields the result.
B GRAPH REPRESENTATION LEARNING
We describe in detail the hard sampling method for graphs whose results are reported in Section 5.2. Before getting that point, in the interests of completeness on the InfoGraph method of Sun et al. (2020). For further information see the original paper (Sun al., 2020).
some required background details
21

---

Published as a conference paper at ICLR 2021
B.1 BACKGROUND ON GRAPH REPRESENTATIONS
We observe set of graphs G = [G3 GJ sampled according to a distribution over an ambient graph space G. Each node u in graph is assumed to have features h/ living in some Euclidean space. We consider a K K-layer graph neural network, whose k-th layer iteratively computes updated embeddings for each node v E G' in the following way.
((
4/ = COMBINE(A) I( AGGREGATE
: :
Eurr)
where COMBINE (k) and (GGREGATE(*) are parameterized learnable functions and (u)) denotes the set of neighboring nodes of The K embeddings for node collected together to obtain single final summary embedding for u. As recommended by Xu et al. (2019) we use concatenation, h" h"(G) = CONCAT ((h! k== to obtain an embedding in F Finally, the node representations are combined together into length d graph level embedding using readout function,
HG)) READOUT ((h")ue))
which is typically taken to be simple permutation invariant function such the mean. The InfoGraph method aims to maximize the mutual information between the graph level embedding (G) and patch-level embeddings h ("")) using the following objective,
max E EG
(N"(G);:(GG) Σ DEG
G
In practice the population distribution p replaced by its empirical counterpart, and the mutual information / replaced by variational approximation Ir. In line with Sun et al. (2020) we use the Sensen-Shannov mutual information estimator as formulated by Nowozin et al. (2016). It is defined using a neural network discriminator T' I2dd + IR as,
It (I)( = Ea-p ( -Bic,))> (MM)),
where sp(2) = l)g(1+e=) denotes the softplus function. The finial objective is the joint maximization over h and T,
max E B 0,8
Σ IT (IT()))
WEG
B.2 HARD NEGATIVE SAMPLING FOR LEARNING GRAPH REPRESENTATIONS
order to derive a simple modification of the NCE hard sampling technique that appropriate for use with InfoGraph, we first provide mildly generalized view of hard sampling. Recall that the NCE contrastive objective can be decomposed into two constituent pieces,
((f.g) = (flign()) + Lunie (f.
where is in fact family of distributions qx ; the anchor æ. Lalign performs the role of "aligning" positive pairs (embedding near to one-another), while Lunit repels negative pairs. The hard sampling framework aims to solve,
that is indexed by the possible values of
22

---

Published as a conference paper at ICLR 2021
inf sup L(J.g) q).
In the case NCE loss we take,
Latign(J (J) = -R amp f(x)" f(xt),
x xtrpp
Luiit (f: 9)) = E amp log { (e s(at) ) + QE )
at stmpt
View this view, we easily adapt to the InfoGraph framework, taking
Caliga (h,, 1) = - -BG
Σ
(h")),
G
WEG
Cunit T.q) -B
Σ uEG
sp (G) H(G))
Denote by & the distribution over nodes u E R defined by first sampling G ~ then sampling uniformly over all nodes of G. Then these two terms can be simplified
falign (h,, T) = -Euppsp( (- ((G)),
Conit (h, T. = -Bx (G"(G),
At this point it becomes clear that, just with NCE, distribution q² arg arg.ax, [(f. q) in the InfoGraph framework if it is supported on arg ea sp(T (G), Although this is still hard to compute exactly, it can be approximated by,
Lh (C') x exp (BT) p(')).
C ADDITIONAL EXPERIMENTS
C.I HARD NEGATIVES WITH LARGE BATCH SIZES
The vision experiments the main body of the paper are all based off the SimCLR framework (Chen et al., 2020a). They use relatively small batch size (up 512). In order to test whether hard negatives sampling method can help when the negative batch size is very large, also periments using MoCo-v2 with standard negative memory bank size N 65536 (He et al., 2020; Chen et al., 2020c). We adopt the official MoCo- v2 2 Embeddings are trained for 200 epochs, with batch size 128. Figure 6 summarizes the re- sults. We find that hard negative sampling can still improve the generalization of embeddings trained on CIFAR 10: MoCo-v2 attains linear readout accu- racy of 88.08 %, and MoCo-v2 with hard negatives (3 0.2, + 0) attains 88.47%.
Top-1 Accuracy
88.4
88.3
88.2
0
McCo-v2 ($ 0,
r'
88.1
0.0
0.0
0.1
0.2
0.5
B (CIFAR10)
Figure 6: Hard negative sampling using MoCo- v2 framework. Results show that hard negative samples can still be useful when the negative memory bank is very large (in this case N 65536).
C.2 ABLATIONS
hhtpps: thub. com/ http///cccoooeeerrcc/.ccooooo
23

---

Published as a conference paper at ICLR 2021
To study the affect of varying the concentration parameter 3 on the learned embeddings Figure 9 plots cosine similarity histograms of pairs of sim- ilar and dissimilar points. The results show that for 3 moving from 0 through 0.5 to 2 causes both
Top-1 Accuracy
92
O
SimCLR (p =0 -0 =0)
T, - 0.1
91
the positive and negative similarities to gradually skew left. In terms of downstream classification, an important property is the relative difference in sim- ilarity between positive and negative pairs. In this
90
89
case 3 = 0.5 find the best balance (since it achieves highest downstream accuracy). When /3 is taken very large (3 = 6), we see change in conditions. Both positive and negative pairs are assigned higher similarities in general. Visually it seems that the positive and negative histograms for = overlap lot more than for smaller values, which helps ex- plain why the linear readout accuracy is lower for 6.
0.0
6.0
B (CIFAR10)
Figure 7: The effect of varying concentration parameter on linear readout accuracy for CI- FARIO. (Complements the left and middle plot from Figure 4.)
Figure 12 gives real examples of hard vs. uniformly sampled negatives. Given an anchor æ (a monkey) and trained embedding f (trained STL10 using standard SimCLR for 400 epochs), we sample a batch of 128 images. The top row shows the ten negatives x that have the largest inner product (()) f( while the bottom row is random sample from from the same batch. Negatives with the largest inner product with the anchor correspond to the items in the batch are the most important terms in the objective since they are given the highest weighting by 9g- Figure 12 shows that "real" hard negatives are conceptually similar to the idea as proposed in Figure 1: hard negatives are semantically similar to the anchor, possessing various similarities, including color (browns and greens), texture (fur), and objects (animals vs machinery).
B O, acc-67.73%%
B 0.S, acc-69.61%
B 2, 2c6-67.68%
f 6, acc-65.54%
Pairs
Posilive
Frequeacy
Es Similarity
0.5 Cosiaa Sinilurity
Similurity
Sinilariyy
Simduriky
Similurity
Figure 8: Histograms of cosine similarity of pairs of points with different label (bottom) and same label (top) for embeddings trained on CIFARIO0 100 with different values of B. Histograms overlaid pairwise to allow for easy comparison.
H not D
not H &
not not (SimCLR)
Frequency Frequency
Posiiive Pairs
Negativo Pairs
0.
03
1:
5.5
1.0
6.
0.0
0.5
1.0
0.0
0. 2.0
0.0
0.5
1.0 Simlartty
Similanty
Similartt
Similarity
Similarity
Similanty"
Figure 9: Histograms of cosine similarity of pairs points with the same label (top) and different labels (bottom) for embeddings trained on CIFAR 100 with four different objectives. H-Hard Sampling, D-Debiasing. Histograms overlaid pairwise to allow for convenient comparison.
24

---

Published as a conference paper at ICLR 2021
(SimCLR)
5.0
Posilive Pairs
Frequensy
Negalive Pairs
50
53
10
03 Sunilarily
1.
0.0
0.3
1.0
U.5 Similanity
1.5
3.3
1.0
2.0
Similrrity
Similarity
Simbarity
Similarity
Figure 10: Histograms of cosine similarity of pairs of points with the same label (top) and different labels (bottom) for embeddings trained on CIFAR10 10 with four different objectives. H-Hard Sampling, D-Debiasing. Histograms overlaid pairwise to allow for convenient comparison.
Readout Accuracy
60
Readout Accuracy
80
50
70
40
60
30
SimCLR
Hard (B 1.0, =0.05)
50
Hard (B 1.0, r =0.1)
20
Hard ($ 0.5., r' =0.55)
0.5,
Hard 0.=0.5.+ r* =0.1)
50
100 150 200 250 300 350 400 Epochs (CIFAR100)
50 100 150 200 250 300 350 400
Epochs (STL10)
Figure 11: Hard sampling takes much fewer epochs to reach the same accuracy SimCLR does in 400 epochs; for STL10 with 3 = it takes only 60 epochs, and on CIFAR 100 it takes 125 epochs (also with B = 1).
D EXPERIMENTAL DETAILS
Figure 13 shows Tyrrhs-sty pseudocode for standard objective, the debiased objective, and hard sampling objective. The proposed hard-sample loss is very simple to implement, requiring only two extra lines code compared to the standard objective.
D.1 VISUAL REPRESENTATIONS
We implement SimCLR in PyTorch. We use ResNet-50 (He et al., 2016) as the backbone with embedding dimension 2048 (the representation used for linear readout), and projection head into the lower 128-dimensional space (the embedding used in the contrastive objective). We use the Adam optimizer (Kingma & Ba, 2015) with learning rate 0.001 and weight decay 10-6 6 Code available at https: /i thub. com/ joshrrl///// 1/HHCL. Since we adopt the SimCLR framework, the number of negative samples N = 2(batch size 1). Since we always take the batch size to be a power of (16, 32, 64, 128, 256) the negative batch sizes are 30, 62, 126, 254, 510 respectively. Unless otherwise stated, all models trained for 400 epochs.
Annealing Method: We detail the annealing method whose results are given in Figure 4. The idea is to reduce the concentration parameter down to zero as training progresses. Specifically, suppose we have e number of total training epochs. We also specify number of "changes" concentration parameter we shall make. We initialize the concentration parameter 31 = B (where this 3 is the number reported Figure 4), then once every e/L epochs we reduce 3 by B/e. In other words, if we are currently on B, then 8:41 3 - 3/e,, and we switch from B; to 8i4 in epoch number i e/f. The idea of this method is to select particularly difficult negative samples early on order to obtain useful gradient information early on, but later (once the embedding is already quite good) we reduce the "hardness" level so as to reduce the harmful effect of only approximately correcting for false negatives (negatives with the same labels the anchor).
the
25

---

Published as a conference paper at ICLR 2021
Anehor
Hard negatives
Uniform negatives
Figure 12: Qualitative comparison of hard negatives and uniformly sampled negatives for embedding trained on STLI0 for 400 epochs using SimCLR. Top row: selecting the 10 images with highest inner product with anchor in latent space from a batch of 128 inputs. Bottom row: a set of random samples from the same batch. Hard negatives are semantically much more similar the anchor than uniformly sampled negatives- hard negatives possess many similar characteristics to the anchor, including texture, colors, animals vs machinery.
pos
exp Inner products for positive example exp inner products for negative examples
neg
nunber of negative examples
temperature scaling
tau_plus: class probability
beta
concentration ion parameter
#Original objective
standard_ loss -log (pos.sum / (pos. sur () neg.sum ())
10
#Debiased objective
12 Neg
(-N+tau (~Nittaa__luusposs neg) ssum() / (1-tau_plus) e** (-1/t))
debiased_ loss -log (pos sum / (pos. Neg))
15 #Bard sampling objective (Ours)
16 reweight - (beta-neg) neg. megg
17 Neg = max ( (-Natau plus*pos + reweight saum () / (1 plus), e*x (xx/-1/t)
18 loss -log {
() sum Neg))
Figure 13: Pseudocode for our proposed new hard sample objective, well the original NCE contrastive objective, and debiased contrastive objective. each case we take the number positive samples be M = 1. The implementation of our hard sampling method only requires two additional lines of code compared to the standard objective.
We also found the annealing in the opposite direction ("down") achieved similar performance.
Bias- varianceee of empirical estimates in hard-negative objective: Recall the final hard negative
samples objective we derive is,
e(a) f(x))
E gop a Nupp
log ef()) + - - (Eo-~ae (e (((()T((T)) - Bunng (eng ((0)))
(15)
This objective admits practical counterpart by using empirical approximations to Ey-~ggle [e](()" and E (e In practice (e.g. N 510) to approximate the first expectation, and only M - samples to approximate the second. Clearly both cases the resulting estimator unbiased. Further, since the first expectation is approximated using many samples, and the integrand is bounded, the resulting estimator is well concentrated (e.g. apply Hoeffding's inequality out-of-the-box) But what about second expec- only sample, however it turns out that the
fairly large number of samples
tation? This might seem uncontrolled since random variable = (x)) f(e) where p and ~ q3 has variance that is bounded by Latign
Lemma 11. Consider the random variable X (x)) f(o) where x ~ p and v ~ z Then Var(X) O (Lalign ())-
26

---

Published as a conference paper at ICLR 2021
Recall that Latign Ex,.+ f((=))ffx+((])] is termed alignment, and Wang & Isola (2020)
show that the contrastive objective jointly optimize alignment and uniformity. Lemma 11 therefore shows that as training evolves, the variance of the X = < f(w) where ~ p and ~ qá is bounded by a term that we expect to see becoming small, suggesting that using single sample (M 1) to approximate this expectation is not unreasonable. We cannot, however, say more than this since we have no guarantee that Lalign (f) goes to zero.
Proof. Fix an and recall that we are considering 4 (-) o3 (+))). First let X' be an i...d copy of X, and note that, conditioning H we have 2Va((X(>) Var (ar(X(ar) Var Var(X x)) s B[(X - [=) Bounding this difference,
- s(00)) 2
B - x1) = Berwino
((v) (1x) [(o))]))))
BuN
3 e c/11"B UADiNag (II1(())l11 (11)+)))1(((000110111
e1/t"
[1((t) - f(6')l12
12 u
S Burt'
[[(()) - s(w))11))
where the first inequality follows since f lies on the sphere of radius 1/t, the second inequality by Cauchy-Schwee the third again since f lies on the sphere of radius 1/t, and the fourth since q3 is absolutely continuous with respect to p+ with bounded ratio.
h(x). rather than itself, taking expectations over x ~ is equivalent to taking expectations over c ~ p. Further, p(c)p(tlc)p((''c) = p(u)p(u'(c) = p(u)p: (u'). So Be-pEr, fu) f(r')| Ex, [If(=) f(x=)))(x+(]])) [I+ 2L where
Since pt (x+) ((x*)((())) only depends
p and x p Thus obtain the lemma.
pos neg
exp Inner products for positive examples exp inner products for negative examples
number of negative examples
temperature scaling
tau_plus: class probability beta
concentration parameter
#C1 Iclipping negatives trick before computinng inng rewe reweighting
reweight 2*neg / max neg.max .abs (),
().bb ()
10 reweight (beta-reweight)
reweight mean ()
Neg max (-N*tau_pe) ctwtauuppuusxpos
reweight negg) .sum / (1-tau_olus), (-1/t1
hard loss -log pos. sum. ()
(pos. sum () Neg))
Figure 14: In cases where the learned embedding is not normalized to lie on hypersphere we found that clipping the negatives to live in fixed range (in this case [-2, stabilizes optimization.
D.2 GRAPH REPRESENTATIONS
All datasets we benchmark on can be downloaded at www. www. www.graphhearninggg Dataset repository of graph classification problems (Morris et al., 2020). Information basic statistics of the datasets is included in Tables 3 and 4. For fair comparison to the original In- foGraph method, adopt the official code, which be found at https:/ /ttp:://gii httpgbttthh..o//gg thub. com/
from the TU-
27

---

Published as a conference paper at ICLR 2021
We modify only the qan wosssssssss..................... py script, adding in pro- posed hard sampling via reweighting. For simplicity we trained all models using the same set of hyperparameters: used the GIN architecture (Xu et al., 2019) with K layers and embedding dimension d = 32. Each model is trained for 200 epochs with batch size 128 using the Adam opti- mizer (Kingma & Ba, 2015). with learning rate 0.001, and weight decay of 10-6. Each embedding is evaluated using the average accuracy 10-fold cross-validatio using an SVM as the classifier (in line with the approach taken by Morris al. (2020)). Each experiment is repeated from scratch 10 times, and the distribution of results from these 10 runs is plotted in Figure 3.
Sanyun--uunInffGGee
Since the graph embeddings are not constrained to lie on a hypersphere, for batch we clip all the inner products to live in the interval [- 2] while computing the reweighting, as illustrated in Figure 14. We found this to be important for stabilizing optimization.
Dataset
DD
PTC
REDDIT-B
PROTEINS
No. graphs
1178
344
2000
1113
No. classes
2
2
2
2
Avg. nodes
284.32
14.29
429.63
39.06
Avg. Edges
715.66
14.69
497.75
72.82
Table 3: Basic statistics for graph datasets.
Dataset
ENZYMES
MUTAG
IMDB-B
IMDB-M
No. graphs
600
188
1000
1500
No. classes
2
Avg. nodes
32,63
17.93
19.77
13.00
Avg. Edges
62.14
19.79
96.53
65.94
Table 4: Basic statistics for graph datasets.
D.3 SENTENCE REPRESENTATIONS
We adopt the official quick-thoughts vectors experimental settings, which can be found at https: / //gi thub. com/ jannggn/S22 We keep all hyperparameters at the default values and change only the s2v-model. saleee.py.. py script. Since the official BookCorpus dataset Kiros et al. (2015) is not available, we use unofficial version obtained using the following repository: https: : //g//t/t thub. com hon/soskek / bookcorrpppooooooooooooooooooooo
Since the sentence embeddings are also not constrained to lie on a the same clipping trick as for the graph embeddings, illustrated in Figure 14.
hypersphere,
After training on the BookCorpus dataset, we evaluate the embeddings on six different classification tasks: paraphrase identification (MSRP) (Dolan al., 2004), question type classification (TREC) (Voorhees & Harman, 2002), opinion polarity (MPQA) (Wiebe et al., 2005), subjectivity classification (SUBJ) (Pang & Lee, 2004), product reviews (CR) (Hu & Liu, 2004), and sentiment of movie reviews (MR) (Pang & Lee, 2005).
E FURTHER DISCUSSION
Comparison with Kalantidis et al. (2020): Kalantidis et al. (2020) also consider ways to sample negatives, and propose a mixing strategy for hard negatives, called MoCHi. The main points of difference are: 1) MoCHi considers the benefit of hard negatives, but does not consider the possibility of false negatives (Principle 1), which we found to be valuable. 2) MoCHi introduces three extra hyperparameters, while our method introduces only (8, 7*. If we discard Principle I (i.e. ++) then only 3 requires tuning. 3) our method introduces zero computational overhead by utilizing within-batch reweighting, whereas MoCHi involves small amount of extra computation.
main sources of approximation in the hard negative sampling algorithm we propose to use in practice. First, our hard negatives objective requires computing expectation over p (x+), the distributions on points with the same = class label as
Linitations of proposed method. There
28

---

Published as a conference paper at ICLR 2021
Due to lack of supervision, propose using samples generated using data augmentation, which we find works well in practice, but deviates from the original formulation and framework. We find this approximation has important implications for practitioners, since we observe that when using oracle access to P the downstream performance improves monotonically the concentration parameter / increases (see Fig. 4, middle), while when using the practical approximation, large values of 3 start to hurt performance, thereby requiring that be tuned (values in the range (0.5, 2) tend to work well in general). Second, estimate the expectation E 8o-0, [e/(x] [(v)] using just a single (importance weighted) sample. This is
not able sample exactly from p To circumnavigate this,
done in the interests of efficiency since using M samples significantly increases the effective batch size (this is the more costly multi-view setting), increasing memory and runtime costs. We anticipate that using M > would improve performance further, in exchange for this extra price, but leave experimentation to future work. That said, our analysis finds that the variance of the variable ( f(0) with of is controlled by the alignment objective, as shown in Lemma 1 11, which suggests that in later stage training the variance of the single-sampl estimator may be reasonably small.
29


Reviews:
[{"review_id": "ueMtuZgIiKB", "reviewer": "AnonReviewer2", "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": "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. \n\nStrength.\nThis paper is well written and easy to follow. \nThis 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. \nThe 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. \n\nWeakness. \nThis 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.\n\nVisualization. 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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hMs2EDs8oj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "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. \n\nOverall, 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.\n\n- 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.\n- 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.\n- 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.\n- The paper could further provide a practical guide on how to choose tau^+.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LHA7j68nHef", "reviewer": "AnonReviewer4", "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\nThis 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.\n\nMy 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.\n \nPros: \n\n\\+ This paper is the first to propose a hard negative sampling for unsupervised contrastive representation learning.\n\n\\+ This paper provides a theoretical analysis of the proposed method that can tightly cluster similar inputs while departing the clusters from each other.\n\n\\+ The proposed method can be easily implemented with few additional lines of code.\n\n\\+ Experiments are conducted on several datasets (STL10, CIFAR100, CIFAR10). The proposed method works well even with a small number of negative samples.\n\n\\+ This paper has a high writing quality. The paper is clearly written and well organized. The motivation, challenges, and contributions are clearly stated.\n\n\\+ This paper shows plenty of visualized results to intuitively and detailedly show how the proposed method works.\n\nCons:\n\n\\- 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.\n\n \nQuestions: \n\nIt 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?\n\nIn 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.\n\nAs 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]?\n\nThe 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?\n\nReferences:\n\n[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.\n[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.\n\n\n\n\n\n\n\n\n\n\n*******************************************\n\nFinal decision: \n\nI would keep my score unchanged. \n\nAs 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.\n\nThis paper is clearly written and well organized. Both empirical and theoretical analysis is provided. The feedback addressed my concerns well.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5NXH8O4f6wP", "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": "Update:\n\nThe 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.\n\n====\n\nThis 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.\n\nThis 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.\n\nOther remarks:\n* Much of the intro regards contrastive learning, augmentation, and mutual information. As such, proper credit needs to be given to [4].\n* 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)\n* 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.\n* 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.\n* You are making a lot of empirical estimations of things, particularly of the partition functions. I feel like bias / variance analysis is necessary here.\n* Page 5 you introduce the debiasing idea, which could be made clearer in this work.\n* 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?\n* Page 5 \"representation generalizable\": generalizable to what? Downstream tasks, test distribution? I'm not sure what follows with the ball packing relates to generalization.\n* Figure 2: why were those betas chosen?\n* 6.1: this would be a great place to mention CMDIM [2]\n* For the annealing experiments, wouldn't it make more sense to anneal beta up (progressively harder) than down?\n\nOne 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.\n\n[1] Chuang, Ching-Yao, et al. \"Debiased contrastive learning.\" arXiv preprint arXiv:2007.00224 (2020).\n[2] Wu, Mike, et al. \"On Mutual Information in Contrastive Learning for Visual Representations.\" arXiv preprint arXiv:2005.13149 (2020).\n[3] Sylvain, Tristan, Linda Petrini, and Devon Hjelm. \"Locality and compositionality in zero-shot learning.\" arXiv preprint arXiv:1912.12179 (2019).\n[4] Bachman, Philip, R. Devon Hjelm, and William Buchwalter. \"Learning representations by maximizing mutual information across views.\" Advances in Neural Information Processing Systems. 2019.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)