Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
Authors: Vicente Balmaseda
Bokun Wang
Ching-Long Lin
Tianbao Yang
Venue: ICML 2025 poster (2025)
Keywords: False Negative Discovery
Contrastive Learning
Self-supervised Learning
Machine learning
Primary area: general_machine_learning->representation_learning
TL;DR: We propose an optimization-based algorithm to identify global false negatives by automatically learning a dataset-wide threshold on the fly for each anchor data

Abstract: In self-supervised contrastive learning, negative pairs are typically constructed using an anchor image and a sample drawn from the entire dataset, excluding the anchor. However, this approach can result in the creation of negative pairs with similar semantics, referred to as "false negatives", leading to their embeddings being falsely pushed apart. To address this issue, we introduce *GloFND*, an optimization-based approach that automatically learns on the fly the threshold for each anchor data to *identify* its false negatives during training. In contrast to previous methods for false negative discovery, our approach *globally* detects false negatives across the entire dataset rather than locally within the mini-batch. Moreover, its per-iteration computation cost remains independent of the dataset size. Experimental results on image and image-text data demonstrate the effectiveness of the proposed method. Our implementation is available at https://github.com/vibalcam/GloFND.

Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
Vicente Balmaseda' Bokun Wang'
Ching-Long Lin
Tianbao Yang'
Abstract
Anchor
False negatives
Anchor
False negatives
In self--uperviied contrastive learning, negative pairs are typically constructed using an anchor image and a sample drawn from the entire dataset, excluding the anchor. However, this approach can result in the creation of negative pairs with similar semantics, referred to as "false negatives", leading to their embeddings being falsely pushed apart. To address this issue, we introduce GLoFND, an approach that automatically learns on the fly the threshold for each anchor data to identify its false negatives during train- ing. In contrast to previous methods for false negative discovery, our approach globally detects false negatives across the entire dataset rather than locally within the mini-batch. Moreover, its per- iteration computation cost remains independent of the dataset size. Experimental results on im- age and image-text data demonstrate the effective- ness of the proposed method. Our implementa- tion is available at "https:/ /ttg://gtttttbb com/ Sabalcam/GloFyy
Figure 1: Examples of false negative images seen during training on ImageNet. The left column is the anchor image and the rest are observed false negative samples.
optimization-base
ability across diverse downstream tasks.
Notably, many self-supervised learning approaches center around contrastive learning. Contrastive learning operates on straightforward principle: it seeks to bring together the embeddings of positive (similar) pairs while simultaneously pushing apart those of negative (dissimilar) pairs. This prin- ciple is combined with well-chosen data augmentations to improve the model's invariance non-semantic variations.
In the absence of reliable labels to determine whether pair of data is positive or negative, many methods resort to instance discrimination. To this end, positive pairs are de- fined as distinct augmented views of the anchor data, while negative pairs are generated by sampling from the whole dataset excluding the anchor data, irrespective of their se- mantics (Chen et al., 2020a; Yuan et al., 2022). However, negative pairs produced through this method lack reliabil- ity. Specifically, augmented views from images sharing similar semantic meanings are incorrectly deemed negative, leading to their embeddings being pushed apart. This inad- vertently encourages the model to discard crucial semantic information. We term these undesirable negative pairs as false negatives (FN). Figure illustrates examples of false negatives encountered during training on ImageNet, where the anchor images are different from their negative samples yet semantically similar.
1. Introduction
Representation learning is a fundamental problem in ma- chine learning that aims learn good representation of the data for downstream tasks. Conventional supervised ap- proaches rely on large quantities of high-quality labeled data, which is hard to collect. Recently, self-supervised learning has achieved promising performance for image represen- tation learning (Chen et al., 2020a; Grill et al., 2020). Its success extends to bimodal learning (Radford et al., 2021) and semi-supervised learning (Chen et al., 2020b). These methods exploit unlabeled data to acquire general- purpose representations that exhibit robust performance and transfer-
The presence of false negatives detrimentally impacts the representations learned through contrastive learning (Saun- shi al., 2019). with this effect becoming more pro- nounced in large-scale datasets featuring numerous semantic concepts (Chen et al., 2022). For instance, during Sog- CLR (Yuan et al., 2022) pretraining on ImageNet100 (100 classes), approximately 1% of all negative pairs are false
'Department of Computer Science and Engineering, Texas A&M University, College Station, USA F, Correspondence to: Vicente Balmaseda <vibaleam @tamu.edu>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
data points from the entire dataset on the fly, with top-a % being the set above the (1 ---uuntille (a E [o, 1). The GLOFND algorithm alternates between two key steps: i) Updating the per-anchor thresholds by SGD to solve a con- vex optimization problem of finding a threshold that can filter out the top-a% % of a set of scores. ii) Updating the parameters of the encoder network by using a stochastic gradient estimator of the modified contrastive loss that takes care of the false negatives identified via the learned thresh- olds (e.g., excluding them).
(a) SogCIR
(b) GLoFNN (Ours)
Figure 2: ImageNet100 00 features (t-SNE projected) learned
GLoFND can be integrated with various CL techniques with minimal computational overhead. It effectively idee- tifies false negatives for each sample, offering flexibility in how these are addressed. We demonstrate the empirical success of our method in unimodal, bimodal, and semi- supervised contrastive learning several CL techniques without using a large batch size. Figure 2(a) and 2(b) quali- tatively showcases that identifying and removing false nega- tives using GLOFND achieves better separation between the learned representations of different classes. One example of this observation that clusters close to the periphery appear more tightly packed and distinct.
by SogCLR (Yuan et al., 2022) and GL.NFD (this work).
negatives. This translates to around 20,000 false negatives per batch with a batch size of 1024, and about 325 with a batch size of 128. The presence of such false negatives dur- ing training can significantly degrade the quality of learned representations: linear classifier trained on top of such representations achieves up to 10% lower accuracy in semi-supervised setting compared to representations learned without the false negatives.
Given an approach to identify false negatives, we can take corrective actions such as filtering them from the training set (i.e., false negative elimination) or incorporating them as additional positive pairs (i.e., false negative attraction) (Huynh et al., 2022). However, confidently identifying the potential false negatives in the absence of labels poses challenging problem. The desire to eliminate false negatives is motivated by the goal of improving representation learn- ing, yet the identification of these instances may necessitate some level of semantic knowledge to determine whether two pairs are indeed negative. Looking at Figure 1, we can observe some of the false negatives are not straightforward to identify, especially after data augmentation.
2. Related Work
Self-supervied learning (SSL). SSL has garnered substan- tial attention for its capacity to generate general-purpose representations from unlabeled data, facilitating scalability to large-scale datasets (Gui et al., 2023). SSL learns data encoder network by leveraging intrinsic relationships within the data. The encoder network is then used to learn predic- tive models in downstream tasks through transfer learning, Noteworthy applications span computer vision (Kolesnikov et al., 2019), natural language processing (Lan et al., 2019), and healthcare (Sowrirajan et al., 2021), among others.
Previous works addressing this problem fall into two cat- egories: local (batch-wise) and global (dataset-wise) ap- proaches. Local methods (Zheng et al., 2021; Huynh et al., 2022) identify false negatives for an anchor by assessing its similarities or adjacency to other data within the same mini-batch. However, the most similar adjacent item to the anchor in the mini-batch may not necessarily be se- mantically similar to the anchor in the entire data space, particularly when the mini-batch size is small. The global approach IEND (Chen et al., 2022) aims to discover false negatives for each anchor the whole dataset. However, their method involves clustering the entire dataset at spe- cific epochs, which could be computationally expensive for large-scale datasets.
Early efforts in SSL formulated pretext tasks to enable mod- els learn representations from unlabeled data. Examples include predicting the relative offset between two patches within the same image (Doersch et al., 2016), solving jigsaw puzzles (Noroozi & Favaro, 2017), colorizing grayscale im- ages (Zhang et al., 2016), and unsupervised deep clustering (Caron et al., 2019). However, these methods necessitate carefully crafted pretext tasks, which may not always apply to diverse domains, leading to a lack of generality.
Contrastive learning (CL). CL has emerged prevalent paradigm in SSL, primarily grounded in instance discrimi- nation (Wu et al., 2018; Zhao et al., 2021). This approach employs contrastive losses, compelling the model to bring the embedding vectors of positive pairs closer while simul- taneously pushing those of negative pairs apart. In essence, it promotes the learning of representations with high similar- ity among positive pairs and low similarity among negative
This paper addresses existing limitations in false negative detection by introducing a novel algorithm, named Global False Negative Discovery (GLoFND), which learns global and dynamic thresholds for each anchor in the dataset. This enables the selection of the top-a% most similar negative
2

---

Discovering Global False Negatives On the Fly for Self-superviee Contrastive Learning
pairs. Positive pairs can be easily generated from differ- ent views of the same image. However, generating quality negative pairs is more challenging. MoCo (He et al., 2020) addresses this through (i) a momentum encoder network that generates representations of images for contrast with the anchor, and (ii) a long queue to provide a large number of negative samples. SimCLR (Chen et al., 2020a) instead uses a large batch size and data augmentations. generating negative pairs with augmented views of images other than the anchor image. However, its performance degrades a lot as the batch size decreases. To address this issue, Yuan et al. (2022) propose a stochastic algorithm called SogCLR that does not rely on large batch size. Ge et al. (2024) gener- ates negatives that preserve superftuous instead of semantic features. Shah et al. (2022) introduced a max-margin crite- rion inspired by support vector machines (SVMs). While these methods have shown promising results, they overlook the semantic relationship when generating negative pairs. Despite two images being semantically similar, their aug- mented views are treated as negative pairs, a phenomenon referred to as "false negatives". The false negatives result in the loss of crucial semantic information, consequently impacting representation learning (Saunshi et al., 2019).
beddings for the entire dataset and subsequently applying k-means clustering- Hence, there remains need for global (dataset-wise) false-negative discovery approach that is agnostic to batch size and scalable for large-scale datasets.
3. CL with Global False Negative Identification
Let D = {xi..... x denote dataset of size n, and let ' be a collection of data augmentation operators. (.). represents an encoder network parametrized by w E Rd.
The global contrastive objective (Yuan et al., 2022) LGCL (w) contrasts each x; E 'D with negative data S (A(x) AA E P, Vx E Di{x;)) } in the whole dataset. Let 2; = E ( (A(x:)). 2 Ew (A'(x)) denote the embed- dings and sim(..-) the cosine similarity. Then,
fGCL = EX,ED,,,,EE (ONWEE/(((::))) [e(w; A, A')
(I)
exp(sim(a, 21/7)
f(w;x,, A'A = -7 log Exeo, exp(sim Bx
While GLOFND is not restricted to any CL technique, the following sections present how GLoFND can be integrated with the global contrastive loss. GLoFND's application to other CL techniques can be done in a similar manner and we empirically show its effectiveness in Section 4. Since GLoFND's 's focus is on detecting false negatives, it does not restrict what actions to take with the detected false negatives. This paper will consider the straightforward approach of filtering them from the loss, leaving how to make the best use of false negatives for future work.
Semantic-aware CL. Recently, several studies have en- hanced www.ediiiinatinn-baaaee
CL by leveraging the underlying semantics. Qiu et al. (2023) introduce the iSog- CLR algorithm that Iearns individualized temperatures for each sample depending on the frequency of its semantics to increase the tolerance of false negatives. In contrast, GLoFND tackles the more challenging task of detecting each sample's 's false negatives, thus providing more freee- dom on how to deal with them. Supervised CL (SupCon) (Khosla et al., 2021) has demonstrated that employing the CL objective with labels to define positive and negative pairs (i.e., avoiding false negatives) can be more effective than the conventional supervised cross-entrppy loss. Weakly supervised CL (WCL) (Zheng et al., 2021) constructs an undirected graph based on auxiliary embeddings of mini- batch data, whose connected components are used to define weak labels for the SupCon. Huynh et al. (2022) adopt a different approach called FNC, addressing false negatives for each anchor by selecting the top l similar samples in the batch. The limitation of the last two works is that the top similar negative samples in the batch may not be reliable false negatives when the mini- size is small.
3.1. Learning Dynamic Per-Anchor Thresholds
The challenge in the false negative discovery problem ap- pears akin to a thicken-and-egee dilemma: the reliable iden- tification of false negatives demands good representations, yet achieving quality representation learning necessitates de- tecting and dealing with false negatives. Thus, our approach starts with a sufficiently pre-trained encoder network E (this can be done with warm-up stage using existing CL methods) and further refines it by systematically and dynam- ically eliminating the identified false negatives. Moreover, we assume that the top a% most similar negative data share similar semantics with the anchor data hased on their current representations, where a is a hyper- parameter to be tuned that allows adapting to different settings. We will identify as false negatives of the anchor x, the negative data with similarity scores above the (1 qquantieee (a [0, 1)).
Instead of detecting false negatives within the mini-batch, Chen et al. (2022) introduce an incremental dataset-wide beattering-based approach. At specific epochs, embeddings are computed for all samples in the dataset, followed by clustering using k-means. Pairs of samples within the same cluster are designated false negatives. Nevertheless, this approach entails high computational costs, particularly for large-scale datasets, due to the necessity of computing em-
The hyperparameter a allows GL.OFN to adapt to different definitions of false negatives, which are inherently depen- dent on the desired level of granularity. For example, in a dataset like ImageNet, consider two classification settings: (1) a maars--griined task of classifying between cars and
3

---

Discovering Global False Negatives On the Fly for Self-superviee Contrastive Learning
animals, and (2) fine-grained task of classifying dog breeds. Two images of dog from different breeds might be con- sidered false negative in the coarse-grained case (1), but not in the fine-graine one (2). Consequently, the optimal percentage of false negatives, controlled by o, varies with the chosen granularity. By adjusting a, GLOFND can flex- ibly align with different levels of semantic resolution, i.e., granularity, Its value can be set based on prior knowledge (e.g., expected rate of false negatives or desired granularity of learned representations) or tuned like other hyperparame- ters, such as the temperature in contrastive learning.
since the minimization of LGCL (w; involves the solution
X to lower level problem in (2). However, the problem in (3) is more challenging that most bilevel problems in the lit- erature (Ghadimi & Wang, 2018; Ji et al., 2021) because the lower-level problem in (2) is non-smooth and non-strongly convex while the upper-level function LaCL (w,, A) is non- differentiable to X. To tackle this challenge, we just ignore the hypergradient of À in terms of w. which has been used in model-agnostic meta-learning (Finn et al., 2017).
3.2. GLOFND for Unimodal CL
Previous work (Huynh et al., 2022) either selects the top- k most similar negatives or sets a threshold on similarity scores. However, the former involves the expensive com- putation and ranking of cosine similarities across the entire dataset, while the latter presents challenges due to the need for manually crafted scheduling of the threshold for each anchor. Moreover, both approaches are problematic as simi- larity scores change when we update the parameters of the encoding network.
We propose an efficient algorithm called GLOFND for dy- namically discovering and eliminating the false negatives in contrastive learning. GLOFND can be combined with pre- vious contrastive learning algorithms, e.g. SogCLR (Yuan et al., 2022). In each iteration, SogCLR + GLOFND first randomly samples a batch of data B C DD and data augmen- tations A, A'. Then, it alternatively executes two steps: (i) updating the thresholds X B: (ii) removing the iden- tified false negatives from the loss function and updating the parameters of the encoding network. Notably, step (i), GL.FND 's computation of A is independent of the specific contrastive loss used, as it relies solely on the em- bedding similarity of negative pairs. The contrastive loss only influences how the filtered false negatives are handled during training.
Instead, we choose an optimization-basse approach to au- tomatically learn the per-anchor threshold X; to select the top a% most similar negative data for the i-th anchor. To achieve this, we cast the problem of finding the (1 - a)- quantile of all similarity scores between x; and all other samples, i.e., R. = {sim( (x;), (x)) x E S as the following optimization problem (Ogryczak & Tamir, 2003):
1.2.1. UPDATING THE THRESHOLLD À
A; = arg min va 1E(-1,1]
+
1 R
(r-v)- PER.
Σ
(2)
First, the threshold X; can be updated by caleulating the stochastic subgradient of (2) and employing the regular SGD update. Given the predetermined sampled negative data of x; in the mini-batch, i.e., B,- = (A(x), A'(x) x E . we can compute an stochastic estimator Vx, of the subgradient of (2) w.r.t. x;- Then, we update those X that correspond to those sampled anchors x; E B while keeping others unchanged, i.e.,
Then, we will have a set of threshold (AiiE The fol- lowing lemma shows that the solution A; to (2) can be used to select the top-a% % most similar negative data.
B {x+}] C ST.
Lemma 3.1. Let k- ST The solution >; to (2) is either the k-th largest value or between k-th and (k + 1)-th largest value in the set R.,
We modify the contrastive loss in (1) to eliminate the false negatives. yielding the following optimization problem:
Σ X
U(sim(z. Ex)x)) > X1)
A
= a
B
1 Σ E... (ew, x;)], n XEED
min Locr, (w,)) A)
(3)
1|
AA - 00
x; E B, x; $ B,
A₂ x-
(4)
((w, ); = =ssim 2i, 2 + log(1 (g( (w, >s; x;, 37)),
Adi
g(w, A; 1 S
Σ
exp(sim(z,, Ew (x))/T),
where I(() is the indicator function, 1111,1| denotes the projection onto the interval [-1, 1] due to that are similarity scores are in [-1, 1J. and 0 is the learning rate of X; In this way, we keep track of a threshold A for detecting global false negatives across the whole dataset for each anchor X; E D. while ensuring that computation remains mini- batch-wise.
where 8,- = fx x E S, sim(zi, Em (x)) < ) is obtained by removing the false negatives (identified via the threshold X,) in the negative dataset S, for anchor x,.
Note that minw LGCL(W (w, X) can be viewed as a stochas- tic bilevel optimization problem (Ghadimi & Wang, 2018)
4

---

Discovering Global False Negatives On the Fly for Self-supervise Contrastive Learning
3.2.2. UPDATING ENCODER NETWORK Ew
CLIP (Radford et al., 2021). This can be achieved by learn- ing a threshold for each instance for modalities and following the same general procedure as for unimodal CL. In this section, we provide brief overview of GLoFND's extension to bimodal CL..
For each anchor x, E B, we eliminate the false neg- atives identified through the threshold X; from its neg- ative data batch B,-, resulting in B
{x , E (x)) S ).). Following the SogCLR algo- rithm (Yuan et al., 2022), we use moving average estimator of g(w, A; X,, S for each anchor x, E D to alleviate the requirement of a large batch size. For each XG, we maintain scalar u, to estimate g(w, Xe X,, S, as
E
Let D = {(x1, pairs, and denote the encoder network by E, for images and the encoder network by ËT for text parametrized by For each (x,, (x),tt) E D, the negative dataset for each anchor image is ST {t V(x, E D (x;, 43 while the negative dataset for each anchor text t; is ST.: = {x V(x, t) E {x, (. Let ž,,5 be the representation of the i-th anchor image x; and Zr, be the representation of the i-th anchor text t;, and Ar, AT, E [-1,1] their respective associated thresholds defined through (2). Then, the problem is formulated as:
bn)} be a set of image-text
(1 (1-7)u: + 10( X; B x, B, Uii
ut
(5)
x; $ B,
O(w do Xi, BT)
Σ xEB,
exp(sim (zi, Ew (w((x)) (x))/))
B
where y [0, is the parameter and g( (w,, X;x;; X, B, is an stochastic estimator g(w, A5 x,, ). Finally, we can update w by computing a stochastic estimator of the gradi- ent of LOCI,Ww X) in (3) w.r.t. the parameters of encoding network w as:
min (X:tt))D
Σ
E(e(w, XI, X;; t:)
l(w, A1,5, Ar, x;, t.) - -2sm (Z,,i, 2r,i)
+ + logl Togl S7,50 (w, A1,5 Xi, S7,1)
-wwsim(z 2/) + TV TVw](w, X;;
w
B
U4
+ log S7, (w, AT.i t, ST,;)
X;EB
gi (w. A1,8 ST,)
Σ exp(sim(ZI,, (r (t))/)/
The whole algorithm, incorporating GLOFND to address the false negative issue in SogCLR through filtering, is outlined in Algorithm 1. Noteworthy differences compared to the vanilla SogCLR algorithm are highlighted in blue. Note that GLOFND adds little overhead, since it just requires basic matrix computations and runs in O(B)), which is relatively negligible compared to the cosine similarity and forward/backward computations.
|S
tEST.
gr(W,Ar,; Ar, ti, (,
(x)) 2r,)
ST xEST.
where Sy = [t| S,, ET())) S Ar,3) and
ST, (x x ST. (erimimxm)x)e))) 2T,;) S AT,i).
Algorithm 1 SogCLR + GLOFND
Then, casily extend the GLOFND the bimodal setting similarly as in the unimodal setting. We refer readers to the Appendix B for more details.
1: Initialize: w E R.,, initialize u E IR" and À E I
2: for for(= 1ol. do
Draw batch of B samples tations A, A', and construct B, {A(x), A'(x)
D and data augmen-
4. Experiments
x E B [xx,)} for each x, E B
In this section, we evaluate GLOFND in unimodal, semi- supervised unimodal, and bimodal scenarios. It is not focus to leverage multiple techniques for achieving state- of-the-art art performance, but to showcase GLOFND's im- provements in identifying false negatives across different settings while being scalable to large-scale datasets (with negligible overhead) and compatible with small batch sizes. Additionally, we perform an ablation study analyze the effect of the different components of GLoFND. We report the score average and standard deviation in parenthesis over 3 runs with different random seeds.
4: for x; E B do
5: Update A; according to (4)
6: Construct B,- by excluding the false negatives
identified via A and compute ((w;
7: Update uis, according to (5)
8: end for
9: Compute the gradient estimator V
10: Update w by the momentum or Adam method
11:
end for
3.3. Extension to Bimodal CL
The unimodal experiments are run on a single NVIDIA A30 with 24GB memory size, while the bimodal experiments make use of multi-node setup with nodes, each with
Our approach GLOFND can be extended to resolve the global false negative discovery in bimodal CL., e.g.,
5

---

Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
Table I: Linear evaluation results in unimodal semi-supervised scenario. We train the linear classifiers with different percentages of randomly sampled labeled training data and present their top-1 accuracies (%) on the validation set. We include the overall average and, in parentheses, its improvement WRT SogCIR baseline. We also report the average of recall, precision, and fl-score of the identified false negatives over the final epoch of pretraining.
Top-1 Accuracy
False Negatives Identification
Method
100.0%
10.0%
1.0%
0.1%
Average
Precision
Recall
F1-Score
SogCLR
76.55 (0.09)
72.24 (0.14)
62.92 (0.34)
34.94 (0.60)
61.66
+ FNC
77.12 (0.14)
72.89 (0.25)
64.29 (0.34)
36.11 (0.70)
62.60 (+0.94)
27.57 (0.03)
53.67 (0.27)
36.42 (0.07)
GL.OFND
77.59 (0.03)
73.36 (0.15)
65.09 (0.49)
37.38 (0.97)
63.36 (+1.70)
48.40 (0.65)
58.81 (0.60)
53.10 (0.31)
Table 2: Unimodal transfer learning results. We report the overall average and its improvement WRT SogCLR baseline.
Method
CIFARIO
CIFAR100
Food101
Caltech101
Cars
DTD
Pets
Flowers
Average
SogCLR
82.46 (0.36)
60.2 (0.22)
59.66 (0.2)
77.73 (0.17)
25.99 (0.64)
57.80 (0.30)
60.63 (0.34)
76.91 (0.33)
62.67
FNC
82.77 (0.36)
60.96 (0.31)
59.82 (0.14)
78.34 (0.92)
26.28 (0.50)
58.60 (0.29)
61.67 (0.66)
78.77 (0.51)
63.40 (+0.73)
GLOFND
82.81 (0.23)
61.94 (0.24)
59.87 (0.16)
79.18 (0.52)
27.88 (0.44)
58.97 (0.96)
63.91 (0.22)
79.89 (0.09)
64.31 (+1.64)
NVIDIA A100 GPUs with 40GB each.
epochs. For FNC, we set a 0.01 and tune the start- ing epoch in {10, 30, 50, 90, 110, 130), choosing the value that achieves the best semi- superviee average perfor- mance. More details on hyperparameters can be found in Appendix D.I.
For unimodal and semi-supervised experiments, we use Sog- CLR (Yuan et al., 2022) and compare with FNC (Huynh et al., 2022). FNC computes the top is for negative data within a mini-batch by utilizing a support set. The support set includes additional views for each image, and the sim- ilarity scores are averaged across these views. For a fair comparison, we set k = afD) and use a support set of size 1. For bimodal experiments, we compare GLOFND with SogCLR and FastCLIP (Wei et al., 2024).
Evaluation. We evaluate our model in three ways: false negative identification, semi-supervised linear evaluation, and transfer learning. First, given that GLOFND's main objective is false negative identification, we assess its effec- tiveness to correctly detect false negatives. To construct the ground truth, we compare the labels of each sample pair, if both samples have the same label they are considered a false negative. We report precision, recall, and F1-scores for the final epoch of pretraining. Second, we evaluate GLoFND's s ability to achieve better representations through linear evalu- ation. That is, we freeze the weights of the encoder at the last iteration of pretraining, remove its projection head, and train a linear classifier on top of the encoder's output. We follow a supervised learning setup, where we use different fractions of labeled training data during linear evaluation, i.e., we train on random subsets of 100% (full dataset), 10%, 1% and 0.1 % of the training data. We report each top-1 accuracy the validation set and average the performance across percentages obtaining the overall semi-supervised score. Lastly, we evaluate the transfer learning performance of the learned representations. We train an fz-regularized logistic regression classifier on features extracted from the frozen pretrained network after removing the projector head, For each method, we report linear evaluation and transfer learning results for the model that achieves the highest semi- supervised average performance.
4.1. Unimodal and Semi-supervised Experiments
Dataset. We run our experiments on ImageNet100 (Wu et al., 2019), a subset of ImageNet with 100 randomly se- lected classes (about 128k images), and report scores on its official validation split. Additionally, we examine the trans- fer learning performance on Food-101 (Bossard et al., 2014), CIFAR-10 and CIFAR-100 (Krizhevsky, 2009), Stanford Cars (Krause et al., 2013), Describable Textures Dataset (DTD) (Cimpoi et al., 2014), Oxford-IIIT Pets (Parkhi et al., 2012), Caltech- 101 (Li et al., 2022), and Oxford 102 Flow- ers (Nilsback& & Zisserman, 2008).
Experiment Setup. Following previous work (Yuan et al., 2022), we pretrain ResNet-50 (He et al., 2015) with a 2- layer 128 x 128 projection head on top of the backbone encoder. We pretrain for 200 epochs with batch size of 128 and the same set of augmentations as in SogCLR. We use LARS optimizer (You et al., 2017) with square root learning rate scaling (0.075 x (irl(Baachiize) and co- sine decay schedule without restart. For SogCLR, we set the temperature (7) to 0.1 and 7 = 0.9. We start using GLOFND when we reach 70 epochs. We use a 0.01, initialize X; 1, and learn it with Adam with learning rate of 0.05 (8, = 0.9, B2 0.98) during the remaining
Results. We report false negative identification perfor- mance and top-1 accuracies by linear evaluation in Table 1. GLOFND achieves significant improvements in false nega- tive identification over FNC, with a 20.83% and 5.14% in-
6

---

Discovering Global False Negatives On the Fly for Self-supervied Contrastive Learning
Table 3: Results in bimodal zero-shot downstream tasks. Datacomp provides the average across 38 tasks, Retrieval averages the performance on image-text retrieval datasets, and IN & Variants averages ImageNet datasets.
Asprex A' Ulomm
of predicted
1.0.0
0.8
0.66
- 0.4
8 0.2
GaRdD
8 0.0
a-0.01
Method
Datacomp
Retrieval
IN & Variants
0.2
0.3
0.4
0.5
0.6
20.0 76.0 120.0 170.0
Epoch
SogCLR (Wei al., 2024)
24.87 (0.13)
29.28 (0.30)
18.86 (0.09)
(a) Threshold distributions
(b) % of predicted FN
+ FNC.
24.55 (0.20)
29.69 (0.19)
18.69 (0.62)
+ GLOEND
25.37 (0.16)
29.92 (0.35)
19.44 (0.16)
Figure 3: Analysis of learned X for GLOFND with a
II (Wei et al,, 2024)
24.76 (0.26)
30.36 (0.18)
19.08 (0.16)
0.01. (a) Kernel density estimation of the distributions of GLOFND's ' X, the approximated optimal X and 20 ran- domly sampled FNC thresholds. (b) Average percentage of negative pairs predicted to be false negatives during training (i.e., 1 | 1/155)) l).
+ FNC
24.63 (0.72)
28.87 (0,93)
18.51 (0.19)
GLOEND
25.37 (0.13)
30.22 (0.32)
19.38 (0.15)
crease in mean precision and recall, leading to an Fl-score of 53.10% which is 16.68% higher than FNC. Observe that simply removing the false negatives identified by FNC or GLOFND improves both the semi-supervised and trans- fer learning performance of SogCLR, GLOFND achieves greater improvements in both scenarios, achieving 1.04%- 2.44% improvement in the semi-supervised scenario and an average 1.64% improvement in transfer learning, while increasing the per-epoch computation by only 2% (from 427 s to 435 s). More details can be found in Appendix D.3. Note these improvements are achieved by simply removing the false negatives identified by GLoFND from the loss,
445 77.5
73.5
mill
77.0
73.0
1 76.5
72.5
72.0
76.0
Single GloFND
Single GloFND
Method
Method
(a) 100% labeled
(b) 10% labeled
Top-1 Acc. (%)
Top-1 Acc. (9))
38
while a more careful treatment can potentially improve the performance even further.
mil
64
63
4.2. Bimodal Experiments
None Single A FNC GloFND
None Single A FNC GloFND Mechod
Method
Datasets. For bimodal learning, we use the Conceptual Cap- tions 3M (CC3M) (Sharma et al., 2018) dataset. We evaluate the performance by leveraging the Datacomp Benchmark (Gadre et al., 2023), which includes 38 zero-shot down- stream tasks. We report the average performance, named Datacomp. For each scenario, we select the model with the best Datacomp average and also report its average perfor- mance on two subsets of the tasks: zero-shot image classifi- cation ImageNet-II Ik (Russakovsky et al., 2015) and Im- ageNet distribution shift datasets (Wang et al., 2019; Recht et al., 2019; Hendrycks et al., 202 b:a; Barbu et al., 2019) (IN & Variants), and zero-shot cross-modee image-text re- trieval on Flickr30K (Plummer et al., 2017), MSCOCO (Lin ct al., 2015), and WinoGAViL (Bitton et al., 2022).
(c) 1% labeled
(d) 0.1% labeled
Figure 4: Linear evaluation (top-1 accuracy %) on Ima- geNet100 for SogCLR without FN identification, with FNC (lop 1%), with single learned threshold (a 0.1), and GLOFND (a 0.01).
Results, We present the bimodal results in Table 3. Despite using a larger batch compared to the unimodal case, the bimodal scenario proves more challenging for FNC, which generally underperforms compared the baseline models. In contrast, GL.OFN enhances both SogCLR and Fast- CLIP across most metrics. Notably, improves the overall Datacomp score for both models. These results highlight the benefit of integrating false negative detection into bi- modal contrastive losses, demonstrating that GLoFND is an effective approach for this task.
Experiment Setup. Following previous work (Wei al., 2024), use a 12-layer transformer (Vaswani et al., 2017) as the text encoder, and ResNet50 as the vision encoder. All experiments are conducted in a multi-node setting with 2 nodes, each with two A100 40GB GPUs. We pretrain for 37 epochs with a global batch size of 1024. For SogCLR, we start using FNC/GLOFND after 15 epochs, setting a = 5e - 4, while for FastCLIP we start after 20 epochs with le 3. For both losses, we initialize X and use Adam updates with learning rate of 0.05. More details hyperparameters can be found in Appendix D.2.
4.3. Ablation Study
Verification of Algorithm Design. We empirically validate three aspects of GLoFND's design: (i) the necessity to have global threshold (as opposed to natch-wise), (ii) the necessity have different X; for each anchor x; E D. and (iii) the quality of the learned X threshold. We will cover (ii) and (iii) in this section and (i) in the next section.
7

---

Discovering Global False Negatives On the Fly for Self-supervied Contrastive Learning
(ii) Do we need a different threshold for each anchor?
Precision (%)
100
GloFND FNC
60
We first examine the distribution of A, learned by GLOFND after pretraining. Rather than being concentrated around a single value, we expect it to span range, indicating that different anchors adopt different thresholds when comput- ing their top (1 - a) quuantile. Figure 3(a) illustrates this distribution for ImageNet100 (red line). As expected, X varies within the range [0.1, 0.6), highlighting the necessity of per-anchor threshold.
80
Recail (%)
60
U4 5
40
GloFND
20
30
80 100 120 140 160 180 260 Epoch
100 120 140 160 180 200 Epoch
(a) Precision
(b) Recall
63.5
50
To empirically validate this, we compare GL.OFN,, which assigns a distinct A; per anchor, against a variant that uses a single A for all anchors, referred to as "SSiggle X." Figure 4 reports the semi-supervised performance on ImageNer100, demonstrating that GLOFND with per-anchor X consis- tently outperforms the single-threshold variant.
45- A
wvg. Top Acc
63.0
9 35-
40
62.5
CloFND FNC
GloFND
62.0
25-
30
FNC
66.55
None
80 100 120 140 160 180 200
10
30 50
70
90 110
Epoch
Starting Epoch
(c) F1-Score
(d)
(ii) How good are the learned X thresholds?
Figure 5: FNC and GL.FND comparison. (a): False nega- tive prediction performance scores for ImageNet 10 using the labels as ground truth. We report the per-epoch mean pre- cision, recall, and fl-score for SogCLR + FNC and SogCLR + GLOFND (a = 0.01). (b): Starting epoch comparison on linear evaluation performance.
We train SogCLR on ImageNet100 and apply GLOFND (a = 0.01) with SGD updates starting at epoch 20. We monitor the percentage of negative pairs predicted to be false negatives, computed as Ss I/S, I. throughout training. We initialize A = 1 (indicating no false negatives) and expect the percentage to converge to the target a. As shown in Figure 3(b), GL.OFD successfully reaches and maintains the desired a after a few epochs.
potential benefits of GLoFND may be limited due to insuf- ficient training time. To assess the necessity and impact of this "wait" period, we evaluate GLoFND's semi-supervised performance on ImageNet100 as we vary the start epoch in {10, 30, 50, 70, 90, 110], keeping the total number of train- ing epochs fixed 200. The linear evaluation results, pre- sented in Figure 5(d), show that GLOFND's 's performance improves as the wait time increases, peaking at 70 epochs. Beyond this point, performance begins to decline. FNC shows a similar trend, with its performance degrading when applied after 110 epochs.
Next, we evaluate the error of the learned A relative to its optimal value. Since computing the exact optimal X; is in- tractable, requiring similarity calculations for every anchor against all other samples under different augmentations, we approximate it instead. We freeze the network and estimate the optimal threshold X by randomly selecting 100,000 samples per anchor. Empirically, GLOFND approximates the desired threshold significantly better than FNC with a batch size of 128, achieving a Mean Absolute Error (MAE) of 0.1 and a Root Mean Squared Error (RMSE) of 0.13 (A₃ [-1, I)) whereas FNC obtains MAE and RMSE of 0.21 and 0.28, respectively. This means GLOFND has less than half the error of FNC. Qualitatively, Figure 3(a) com- pares the distribution of the Icarned Xx the approximated Ay. and the thresholds used by FNC. Since FNC computes thresholds at the mini- batch level, we sample 20 random batches per anchor and plot their respective distributions. The results show that GLOFND learns a A, distribution that more closely aligns with the desired threshold than FNC.
Computational Efficiency. When using GloFND with a contrastive method based on embedding similarity (e.g.. SimCLR, SogCLR, and CLIP), pairwise similarities are already computed as part of the loss function. Thus, the only additional computations required are: (1) updating the X values for the mini-bated samples, which involves a simple gradient computation (Equation 4), and (2) filter- ing the false negatives, which can be done through simple matrix operations. Both operations involve basic matrix computations and run in linear time with respect to the number of pairs in a batch (O(B2), where B is the batch size). The computational overhead of GLOFND is mini- mal compared to the cost of cosine similarity computation and forvard/backpropagatio Our experiments on Ima- g0 with batch size of 128 show that GLOFND introduces only a 2% increase in per-epoch training time for SogCLR (435.19 for SogCLR GLOFND vs. 426.67 for SogCLR). This overhead is comparable to that of the batch-wise method FNC (434.06 s).
Impact of Starting Epoch. GL.OND requires a sufficiently pre-trained network to ensure that the similarity between embeddings reflects semantic similarity. This is achieved by applying GLOEND after a certain number of training epochs. However, the optimal start time involves trf If GLOFND is applied too early, the embedding space may not be well-formed leading to incorrect classification of pairs as false negatives. Conversely, if applied too late, the
8

---

Discovering Global False Negatives On the Fly for Self-superviee Contrastive Learning
4.4. Comparison with Mini-batch Top-k Method
Anchor
False negatives GloFND
False negatives FNC
In this section, we assess the necessity of a global threshold by comparing GLOFND's 's global thresholds to FNC, which computes threshold for each mini-batch
Semi-supervised Linear Evaluation. We present the semi- supervised linear evaluation performance for different per- centages of labeled training data in Figure 4. Both GLOFND and FNC outperform not addressing false negatives, high- lighting the importance of handling them. Furthermore, G1.OFND consistently outperforms FNC across all settings, with improvements ranging from 0.47% to 1.27%. This demonstrates the advantage of using a global threshold, as opposed to a threshold specific to each mini-batch.
Figure 6: Examples of false negatives identified for Ima- geNet100 by GLOFND and FNC. The left column shows the anchor images, while the middle and right columns present the false negatives identified by GLoFND and FNC respectively.
Quality of Found False Negatives. We analyze the quality of the false negatives identified by GLOFND and FNC. In Section 4.3 (iii), discussed how GL.NND matches more closely the optimal wiiaset-wwiee threshold than FNC, with half the approximation error. Here, we examine how this improved threshold aligmment affects the quality of the false negatives identified. To do so, we calculate the per-epoch mean precision, recall, and FI-score for each method, using the class labels as ground truth (i.e., a pair is considered false negative if both samples share the same label). As training progresses and the embedding space improves, we expect these metrics to increase, reflecting better alignment between embedding and semantic similarity. Furthermore, for GLOFND, we expect an increase in recall as A; reaches the desired quantile, capturing more false negatives. This should lead to a decrease in precision due to early repre- sentations not being sufficiently pretrained. After some oscillation, GLOFND should follow steady upward trend.
occurs in the first and last rows, where GLoFND identifies more false negatives than FNC.
5. Conclusions
In this work, we have addressed the problem of identifying global false negatives in self-supervised contrastive learn- ing through optimization- approach. We propose identifying as false negatives for given anchor those nega- tive samples whose similarity exceeds the desired quantile across the entire dataset. We then introduce GLOFND,, an optimization- based method that automatically learns a threshold for each anchor, enabling the identification of its false negatives on the fly. Experimental results demon- strate that GLoFND improves existing contrastive learn- ing methods, both for unimodal and bimodal tasks, with minimal computational overhead. An open question is whether Gr.OFND could be extended to non-CI. methods and whether the parameter a could be individualized.
The results are presented in Figure 5. We observe that GLoFND behaves as expected, with the oscillations dimin- ishing and becoming minimal around epoch 120. Regard- less, GLOFND shows a 14.89% average improvement in F1-score, surpassing FNC for all but 4 epochs (indicated by the red area in Figure 5). Moreover, after epoch 120, GLoFND consistently maintains mean F1-score between 14.64% and 18.05% higher than FNC. This underscores GLoFND's 's superiority in identifying false negatives.
Limitations. Since the focus of this paper is on false neg- ative detection for contrastive learning, address false negatives through filtering. While this straightforward ap- proach has proven effective in our settings, future work could explore more advanced methods that may further en- hance downstream performance. Additionally, the benefits of GLOFND and similar false-negative techniques on down- stream tasks depend on the proportion of false negatives in the pretraining dataset and how false negatives are defined within the downstream task.
This is quantitatively illustrated in Figure 6, which shows examples of false negatives identified in a mini-batch by GLOFND and FNC. While the number of false negatives identified by FNC remains constant across mini-batches, GLOFND's 'sssi dynamic threshold allows this number to vary, adapting to each mini-batch more effectively. For instance, in the second and third rows, FNC's s fixed top-k approach results in the selection of negative samples that are not sufficiently similar, leading to errors. contrast, GLoFND not constrained to fixed number and instead selects only the most similar samples according A₁. The opposite
A Acknowledgments
VB, BW and TY were partially supported by National Sci- ence Foundation Award #2306572 and #2147253, National Institutes of Health Award #R01HL1681 1661166.6111116611666111111111 CL was par- tially supported by National Institutes of Health Award #R01HL168116.
9

---

Discovering Global False Negatives On the Fly for Self-supervise Contrastive Learning
Impact Statement
Finn, C., Abbeel, P., and Levine, S. Model-agnostie meta- learning for fast adaptation of deep networks. CoRR, abs/1703.03400, 2017. URL abs 0t///170..04440
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Gadre, S. Y., Ilharco, G., Fang, A., Hayase, J., Smyrnis, G., Nguyen, T., Marten, R., Wortsman, M., Ghosh, D., Zhang. J., Orgad, E., Entezari, R., Daras, G.. Pratt, S.. Ramanujan, V., Bitton, Y., Marathe, K., Mussmann, S., Vencu, R., Cherti, M., Krishna, R., Koh, W., Saukh, O., Ratner, A., Song, S., Hajishirzi, H., Farhadi, A., Beau- mont, R., Oh, S., Dimakis, A., Jitsev, J., Carmon, Y., Shankar, V., and Schmidt, L. DataComp: In search of the next generation of multimodal datasets. arXiv preprint arXiv:2304. 14108, (arXiv:2304. (ete2300441118)) October 2023, doi: 10.448550/axXiv.334444 14108.
References
Barbu, A., Mayo, D., Alverio, J., Luo, W., Wang, C., Gut- freund, D., Tenenbaum, J., and Katz, B. ObjectNet: A large-scale bias- controlld dataset for pushing the limits of object recognition models. In Wallach, H., Larochelle, H., Beygelzimer, A., dAlché-BBii (Alché-Buc, F., Fox, E., and Garnet,, Advances in Neural Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019.
R. (eds.), Advances
Bitton, Y., Cuettn, N., Yosef, R., Elovici, Y., Bansal, M., Stanovsky, G., and Schwartz, R. Winogavil: gamified association benchmark to challenge ssion-and-language models. In Proceedings of the 36th International Confer- ence Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781 18817110 171 1888
Ge, S., Mishra, S., Wang. H., Li, C.-L., and Jacobs, D. Robust contrastive learning using negative samples with diminished semantics. In Proceedings of the 35th Inter- national Conference on Neural Information Processing Systems, Nips '21, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 978- 1-7138-45399-33
Ghadimi, and Wang, M. Approximation methods for bilevel programming. arXiv preprint arXiv:180..02246, 2018.
Bossard, L.,, Guillaumin, M., and Van Gool, L. Food-101 mining discriminative components with random forests. In European Conference on Computer Vision, 2014.
Grill, J.-B., Strub, F, Altché, F., Tallec, C., Richemond, P. H., Buchatskaya, E., Doersch, C., Pires, B. A., Guo, Z. D., Azar, M. G., Piot, B., Kavukcuoglu, K., Munos, R., and Valko, M. Bootstrap your own latent: A new approach to self-supervised Learning, September 2020. URL http: http://aaxwv..ora//////aao/a 2006. 077.300..77.....
Caron, M., Bojanowski, P., Joulin, A., and Douze, M. Deep Clustering for Unsupervised Learning of Visual Features, March 2019. URL http::/ /ttt::///axiv.oot abs/ abs/1807. 05520.
Chen, T., Korbllith, S., Norouzi, M., and Hinton, G. A Simple Framework for Contrastive Learning of Visual Representations, June 2020a. URL http:://axti brg/abs/2000 05709.
Gui, J., Chen, T., Zhang, Cao, Q. Sun, 7., Luo, H., and Tao, D. A Survey on Self-supervised Learning: Algo- rithms, Applications, and Future Trends, September 2023. URL http: wwwpaawwwww..wwaaoao./oo/ 2231 05712.
Chen, T., Korbblith, S., Swersky, K., Norouzi, M., and Hinton, G. Big Self-Supervised Models are Strong Semi- Supervised Leamerr, October 2020b. URL http:// arxiv. org/ httg//bs/200000
He, K., Zhang, X., Ren, S., and Sun, Deep Residual Learning for Image Recognition, December 2015.
He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R. Momen- tum Contrast for Unsupervised Visual Representation Learning, March 2020. URL http:://tttxi...t/ abs
Chen, T.-S., Hung, W.-C., Tseng, H.-Y., Chien, S.-Y., and Yang, M.-H. Incremental False Negative Detec- tion for Contrastive Learning, March 2022. URL http: //arxiv. org/ abs/ /alo. 03719.
Hendrycks, D., Basart, S., Mu, N., Kadavath, S., Wang, F,, Dorundo, E., Desai, R., Zhu, T., Parajuli, S., Guo, M., Song, D., Steinhardt, J., and Gilmer, J. The many faces of robustness: A critical analysis of out-of-distributis generalization, 2021a. URL https: htt///axvvvv///// org/ abs/2006.162411
Cimpoi, M., Maji, S., Kokkinos, I., Mohamed, S., and Vedaldi, A. Describing textures in the wild. In Proceed- ings of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2014.
Doersch, C., Gupta, A., and Efros, A. A. Unsupervised Vi- sual Representation Learning by Context Prediction, Jan- uary 2016. URL http:// /tt////axivi.//. www.wiiwww/aaaa.a....o.. wttpd/..ogg/bb///0o00// a155. 05192.
Hendrycks, D., Zhao, K., Basart, S., Steinhardt, J., and Song, D. Natural adversarial examples, 2021b. URL
https://arxiv.orgg httts:///aaii..or//a/////////
10

---

Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
Huynh, T., Kornblith, S., Walter, M. R., Maire, M., and Khademi, M. Boosting Contrastive Self-Supervised Learning with False Negative Cancellation, January 2022. URL http: / arxiv.
Parkhi, O. M., Vedaldi, A., Zisserman, A., and Jawahar, C. V. Cats and dogs. In IEEE Conference on Computer Vision and Pattern Recognition, 2012.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury. J., Chanan, G., Killeen, T., Lin, Z.,, Gimelshein, N., Antiga, L., Desmaison, A., Köpf, A., Yang, E., Vito,, Z., Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. PyTorch: an imperative style, high-performance deep learning library. Curran Associates Inc., Red Hook, NY, USA, 2019.
Ji, K., Yang, J., and Liang. Y. Bilevel optimization: Con- vergence analysis and enhanced design. In International conference on machine learning, pp. 4882 4892. PMLR, 2021.
Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. Supervised Contrastive Learning, March 2021. URL http://arxix org/ abs/ 22040.0.000 11362.
Plummer, B. A., Wang. L., Cervantes, C. M., Caicedo, J. C., Hockenmaier, J., and Lazebnik, S. Flickr30k Entities: Collecting Region-to- thrres Correspondences for Richer Songe-to-Sentend Models. International Journal of Computer Vision, 123(1):74-93, May 2017. ISSN 1573-
Kolesnikov, A., Zhai, X., and Beyer, L. Revisiting self- supervised visual representation learning. In Proceedings of the IEEF/CVE conference on computer vision and pattern recognition, pp. 1920-1929, 2019.
1405. doi: 10. 1007/s1 163--01---6----. URL https: / //doi. 10..//g1.0... 0ttp../rg11..10071111111111 111.:0..00001111111 01 096507.65771 7.
Krause, J., Deng, J., Stark, M., and Fei-Fei, L. Collect- ing large-scale dataset of fine-grained cars. In Second Workshop on Fine-Grained Visual Categorization, 2013.
Qiu, Z.-H., Hu, Q., Zhong, Y., Zhang, L., and Yang, T. Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence, Febru- ary 2023. URL http:://raee org/ abs/2202. 12183.
Krizhevsky, A. Learning Multiple Layers of Features from Tiny Images. 2009.
Lan, Z., Chen, M., Goodman, S., Gimpel, K., Sharma, P., and Soricut, R. Albert: lite bert for self-supervised learning of language representations. arXiv preprint 19%.: 2019.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., and Sutskever, I. Learning Transferable Vi- sual Models From Natural Language Supervision, Febru- ary 2021. URL http:://rxiii org/ abaaabbs///// 2103. 00020.
Li, F-F., Andreeto, M., Ranzato, M., and Perona, P. Caltech 101, Apr 2022.
Recht, B., Roelofs, R., Schmidt, L., and Shankar, Do ImageNet classifiers generalize ImageNet? In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 5389 -480. PMLR, 09-15 Jun 2019. URL https:: httptt:/pprcceeddaaee http://poceeddnnngn// ings www. www.m.........// recht1 2ahht19.hhe html.
Lin, T.-Y., Maire, M., Belongie, S., Bourdev, L., Girshick, R., Hays, J. Perona, P.. Ramanan, D., Zitnick, C. L., and Dollár, P. Microsoft COCO: Common Objects in Context, February 2015. URL abs/1405. 0312.
Loshchilov, I. and Hutter, F. Decoupled Weight De- cay Regularization. arXiv:1711.05100 [cs, math), Jan- uary 2019. URL http: /tpp://aaae 05101. arXiv: 1711.05101.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, 7.,, Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-25,, 2015. doi: 10. 10.1077/11263-005-008
Nilsback, M.-E. and Zisserman, A. Automated flower clas- sification over large number of classes. In Indian Con- ference Computer Vision, Graphics and Imuge Pro- cessing, Dec 2008.
Noroozi, M. and Favaro, P. Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles, August 2017. URL ht //tpiv.////iivva//a org abs/aal3...... 09246.
Saunshi, N., Plevrakis, O., Arora, S., Khodak, M., and Khandeparkar, H. A theoretical analysis of con- trastive unsupervised representation learning. In Chaud- huri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learn- ing, volume 97 of Proceedings of Machine Learn- ing Research, pp. 5628 5637. PMLR, June 2019.
Ogryczak, W. and Tamir, A. Minimizing the sum the largest functions in linear time. Information Processing Letters, 8573):11-1122, 2003.

---

Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
URL htthhtss//prooceddngge/ ptt.sm//...reee/9///
Zhang, R., Isola, P., and Efros, A. A. Colorful Image Col- orization, October 2016. URL httthtt/////riii.orrr abs/1603.085
saunshi1 9a html..
Shah, A., Sra, S., Chellappa, R., and Cherian, A. Max- Margin Contrastive Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8):8220-8230,
Zhao, N., Wu, Z., Lau, R. W. H., and Lin, S. What makes instance discrimination good for transfer learning?, Jan- uary 2021. URL http://t///// /ttp:////avvv.a org/ abs/2006 06606.
June 2022. ISSN 2374-3468, 2159-5399. doi: 10.1609/ 20796.
Sharma, P., Ding, N., Goodman, S., and Soricut, R. Con- ceptual captions: cleaned. hypernymed, image alt-text dataset for automatic image captioning. In Gurevych, I. and Miyao, Y. (eds.), Proceedings of the 56th An- nual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pp. 2556-2565, Mel- bourne, Australia, July 2018. Association for Computa- tional Linguistics. doi: 10.18653/v1/P18- https: http///aaaanttthogco http//lgg...gg.---o1//1 wtt/p/8-11111
Zheng, M., Wang, F,, You, S., Qian, C., Zhang, C., Wang, X., and Xu, C. Weakly Supervised Contrastive Learning. In 2021 IEEE/CVE International Conference on Com- piter Vision (ICCV), pp. 10022-10031, Montreal, QC, Canada, October 2021. IEEE. ISBN 978-1 1--------6--8--- doi: 10.1109//CCV49922222222 000999. URL https:// ieeexplore ieee org/ http://dcumeet//9911
URL
Sowrirajan, H., Yang, J., Ng, A. Y., and Rajpurkar, MoCo- CXR: MoCo Pretraining Improves Representation and Transferability of Chest X-ray Models, May 2021. URL http: /awxiv.vvvvvvv////i//eeeeaaaaava org/ abs/ 2010.000.. 05352.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. Guyon, I., Luxburg, V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Wang, H., Ge, S., Xing, E. P., and Lipton, Z. C. Learning robust global representations by penalizing local predic- tive power, 2019. URL hwtpt:ttp///om /ttpp::///xxii.../ httpxxxxvvvoooo org/ /bs/ 1 1905. 1905.13549. 13549.
Wei, X., Ye, F., Yonay, O., Chen, X., Sun, B., Tao, D., and Yang, T. FastCLIP: Suite of Optimization Techniques to Accelerate CLIP Training with Limited Resources, October 2024.
Wu, Y., Chen, Y., Wang. L., Ye, Y., Liu, Z., Guo, Y., and Fu, Y. Large Scale Incremental Learning, May 2019, URL abs abs/aaas..11 13260.
http:// /ttp///axvvv./ae////e/eeeea.a.la http://aax......abbs...s.ss/
Wu, Z., Xiong, Y., Yu, S., and Lin, D. Unsupervised Feature Learning via Pon-marrmttiic Instance-level Discrimina- tion, May 2018. URL 1805. 01978.
wwwpiiiiiorrraaaeeeee abs/
You, Y. Gitman, I., and Ginsburg, B. Large batch training of convolutional networks, 2017. URL https://t://art org/abs /108 03888.
Yuan, Z., Wu, Y., Qiu, Z.-H., Du, X., Zhang, I.., Zhou, D., and Yang, T. Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance, September 2022. URL http: //a rxiv. wwwaiivvrrg//...eeeee..e..ooooee abgg/bbs/222.. 12387.
12

---

Discovering Global False Negatives On the Fly for Self-supervied Contrastive Learning
A. Proof of Lemma 3.1
Proof. For simplicity, we denote that ni; = | and 8j is the j-th largest value {sim(z, Lw (x)) x E S ie.
$1 2 $2 2 2 $ nn A subgradient (,(A,) of the objective at X, in (2)
1. 8j X
((())= am,
(88 de),
6(s) X1)
C, 8j = X;
1=1
0, 8j
Xi
where [0. 1]. We define k [an, 1. E (A,) only happens when X [sx", si) since k - an; S k, where K' = max sj > $ > k). k" minfk" k + 1}, k" = max 8j < sk, > k}. Thus, is solution to (2), Besides, when om, is an integer (i.e. k = am, = [an, D. any value between [sk, 88+1] is also a solution to (2), which could be different from 8k.
B. More Details on Extension to Bimodal CL
Our approach GL.NFN can be extended to resolve the global false negative discovery in bimodal CL., e.g., CLIP (Radford et al., 2021). Consider a dataset of image-text pairs D = {(x1, t1),.... (Xa, t.)). a collection of image augmentation operators PI, and a collection of text augmentation operators Pr. Suppose that the encoder network E, for images and the encoder network ET for text are parametrized by w. For each (x,, L,) E DD the negative dataset for each anchor image X; is S7. (A) VAT Pr, v(x,t) E D} while the negative dataset for each anchor text t, is ST = {A) | VA, E (xx,t) t) E D}. For the i-th anchor image with representation Zi,i, the threshold 11, [-1, 1] for finding the top a% text neighbors among all negatives S7, can be solved by
min $1,((1), vE(-1.1]
(v, = va + | LES,,
Σ
(sim(2),,,Fr - v)
Similarly, we can obtain the threshold λr, E [[-1, for the i-th anchor text t. Given the thresholds λ Ar, the bimodal contrastive loss can be written as
1 n1 (x.D))D
LBGCI(W,AI,,
Σ Ar.
t:)],
l(w, (ww,d,s,)A,,
t.) 2zi,
+ T log (T, A1.53 X,, S7,1)
+ T log S7,199 AT. ti, ST.)):
gr(w, A1.5 Xi, S7.))
Σ
exp(sim(Z1, ET (t))))/
|
te5
=
(x),
|S xEST,
where S7, = {t It E S7 sim Et() S A1,3. S7, = (x x S7,, sim(E))))) ZT,)) & \T,} are the negative datasets for anchor (x;, t;) excluding the false negatives identified through the learned thresholds A1,5, Ar,-
We extend the GLoFND to the bimodal setting as follows. First, sample mini-batch of image-text pairs B C D, sampled image augmentations A,, and text augmentations Ar, we construct the sampled negative sets B7, (Ar(t)
(x, t) E B (x, t. BT,; = {x)(x) (x, t) E B B)x(x,, t,)}} for each (x, t,) E B. Given the image embedding 11, = (xr( and text embedding žτ, = Pr(Ar(t,)) for anchor (x,, t,), the thresholds X, for images can be
13

---

Discovering Global False Negatives On the Fly for Self-supervise Contrastive Learning
updated by
(r( A1.).
187,1
Ao.. [--1.1]
A4 Aans)
(x,, tz) B,
Ar
X1,ss
(xi, $ B,
Similarly, we can update the thresholds Ar for texts. Given the thresholds A for images and thresholds Ar for texts, construct B {t t E B sim (Zz, Et)) A and BT, {x
BT., sim(Er(x)) zT,)) I Xr,3} by
excluding the false negative images and texts identified via the thresholds Xτ,5 and Xy.
Then, employ the moving-averes average estimators u1 uT, for gr(w, XI, X,, ST.) gr Ar. t, S7,). respectively.
Σ
|B LEB
Gr(w, AT, ti BT,)) | x T.
(x]sim(Er(()),,n)) (T,)/T)
(1 7)u,, + +70 A1, x, B7.))
(x, t4) E B,
01
U1,60
(x;, (;) $ B,
(1-7)ur, 70 AT t,, BT,s)
(xi, t;) E B,
WT
UT,4:
(xi, t;) $ B.
Finally, we can update the parameters w for image-texi encoder networks by the stochastic gradient estimator.
2V si
B
(xi,ta)EB
+
V V191 w. X;; BI,²)
U1
Vigr A7, ti, Br,d)
WT
C. High-level Intuition for a Hyperparameter
The hyperparameter a allows GLoFND to adapt to different definitions of false negatives, which are inherently dependent on the desired level of granularity. For example, in dataset like ImageNet, consider two classification settings: (1) coarse-grained task of classifying between cars and animals, and (2) fine-grained task of classifying dog breeds. Two images of a dog from different breeds might be considered a false negative in the coarse-grained case (1), but not the fine-grained one (2). Consequently, the optimal percentage of false negatives, controlled by a, varies with the chosen granularity. By adjusting a, GLoFND can flexibly align with different levels of semantic resolution, i.e., granularity.
The value of can be set based on prior knowledge (e.g., expected rate of false negatives or desired granularity of learned representations) or tuned like other hyperparameters such as the temperature. If is too low, GLoFND may fail to identify sufficient false negatives, leading to minimal impact on the learned representations, though not degrading performance, as setting a = 0 is equivalent to disabling GLOFND. Conversely, if is too high, GLOFND may identify too many false negatives. If these are filtered out during training, the reduced number of negative pairs can limit contrastive learning, potentially harming performance. For tuning, it is recommended to start with a low a and gradually increase until no further performance gains are observed.
14

---

Discovering Global False Negatives On the Fly for Self-supervied Contrastive Learning
D. More Details on Experiments
All the experiments are implemented using the PyTorch (Paszke et al., 2019) library. The unimodal experiments are run on a single NVIDIA A30 with 24GB memory size, while the bimodal experiments make use of a multi-node setup with 2 nodes, each with 2 NVIDIA A100 GPUs with 40GB each. The estimated amount of time to run single experiment is 1.5 days for ImageNet100, and 14 hours for CC3M.
D.I. Additional Details for Unimodal Experiments
Experiment Setup. Following prior work (Yuan et al., 2022), we pretrain a ResNet-50 (He et al., 2015) with a 2-layer 128 x 128 projection head on top of the backbone encoder. We use square root learning rate scaling (0.075 x /BatchSize) with cosine decay schedule without restart. Additionally, we apply a linear learning rate warm-up for 10 epochs, where the learning rate linearly increases to its maximum value.
We adopt the same augmentation pipeline as in SogCLR (Yuan et al., 2022), utilizing the torchvision implementation. This includes RandomResizedCrop (resizing to 224 x 224), random ColorJitter, RandomGrayscale, random GaussianBlur, RundommHorizontallliipp and normalization using ImageNet statisties.
The network is pretrained for 200 epochs with batch size of 128. We use the LARS optimizer (You et al., 2017) with weight decay of le 6 and momentum of 0.9. The temperature (7) is set to 0.1, and for SogCLR, 7 0.9. For GL.OFND, we set updates using a learning rate of 0.05, B1 = 0.9, and 32 = 0.98. For FNC, 0.01 and the starting epoch is tuned from {10, 30, 50, 70, 90, 110, 130), selecting the value that yields the best semi-supervised average performance.
0.01 and tune the starting epoch from {70, 90, 110), after which we begin updating ); with Adam
Linear Evaluation. We evaluate GL.oFND's s ability to produce better representations through linear evaluation. Specifically, we freeze the encoder's weights at the last iteration of pretraining, remove its projection head, and train linear classifier (a single fully connected layer) top of the encoder's 's output.
Additionally, we employ semi-supervised learning setup, using different fractions of labeled training data during linear evaluation. We train on random subsets of 100% (full dataset), 10%, 1%, and 0. % of the training data. For each fraction, we report the top-1 I accuracy on the validation set and average the performance across the different percentages to obtain the overall semi-supervised performance.
We train for 90, 285, 900, and 900 epochs corresponding to 100%, 10%, 1,, and 0.1% labeled data, respectively, with batch size of 1024 and early stopping if the validation accuracy does not improve for 100 epochs. We use AdamW (Loshchilov& & Hutter, 2019) with weight decay of O, momentum of 0.9, and a learning rate of 0.1. The same augmentation pipeline used in SogCLR is applied for linear evaluation. For training, we use RandomResizedCrop (resizing to 224 x 224), RandomHorizomalFlip and normalization. For testing, we resize the images to 256 x 256, apply CenterCrop to 224 x 224, and normalize.
Transfer Learning Datasets. We additionally examine the transfer learning performance on Food-101 (Bossard et al., 2014), CIFAR- and CIFAR-100 (Krizhevsky, 2009), Stanford Cars (Krause al., 2013), Describable Textures Dataset (DTD) (Cimpoi al., 2014), Oxford-IIIT Pets (Parkhi et al., 2012), Caltech-101 (Li et al., 2022), and Oxford 102 Flowers (Nilsback & Zisserman, 2008). We follow the evaluation protocols in the papers introducing these datasets, i.e., we report top-1 accuracy for F01,-101, CIFAR- 10, CIFAR-100, Stanford Cars, and DTD; and mean per-class accuracy for Oxford- IIIT Pets, Caltech-101, and Oxford 102 Flowers. We report results on the test set and, for DTD, we report results only for the first split. Caltech-101 defines no train/test split, so we randomly select 20% of images per class to create the test set.
Transfer Learning Evaluation. We train an re-ulaulr multinomial logistic regression classifier on features extracted from the frozen pretrained network after removing the projector head. For each method, we select the pretrained network that achieved the highest semi-supervised average performance, used in the remi-supervised results.
We employ L--FGGS and apply the same preprocessing as during validation in the linear evaluation setting: resizing to 256, center-cropping to 224, and normalizing. We report the best test performance across different & regularization parameters, selecting from a range of 10 logarithmically spaced values between 10 6 and 105.
15

---

Discovering Global False Negatives On the Fly for Self-supervied Contrastive Learning
D.2. Additional Details for Bimodal Experiments
Datasets. For bimodal learning, we use the Conceptual Captions 3M (CC3M) (Sharma et al., 2018) dataset. Because some links have expired, our downloaded training set of CC3M contains 2, 723, 840 image-text pairs. We evaluate the performance by leveraging the Datacomp Benchmark (Gadre et al., 2023), which includes 38 zero-shot downstream tasks. We report the average performance, named Datacomp. For each scenario, we select the model with the best Datacomp average and also report its average performance on two subsets of the tasks: zero-shot image classification on ImageNet and its different variants (IN & Variants), and zero-shot cross-modal image-text retrieval. IN & Variants includes ImageNet- Ik (Russakovsky et al., 2015) and 6 ImageNet distribution shift datasets (i.e., ImageNet-Sketch (Wang et al., 2019), ImageNet-V2 (Recht et al., 2019), ImageNet-A (Hendrycks et al., 2021b), ImageNet-O (Hendrycks al., 2021b), ImageNet-R R (Hendrycks et al., 2021a), and ObjectNet (Barbu et al., 2019)). Retrieval tasks consist of Flickr30K (Plummer al., 2017); MSCOCO (Lin et al., 2015), and WinoGAViL (Bitton et al., 2022).
Experiment Setup. Following previous work (Wei et al., 2024), we use 12-layer transformer (Vaswani et al., 2017) as the text encoder and ResNer50 as the vision encoder. All experiments are conducted in a multi-node setting with 2 nodes, each equipped with two A100 40GB GPUs. We pretrain for 37 epochs with a global batch size of 1024, The AdamW (Loshchilov & Hutter, 2019) optimizer is used with (2),8)) = (0.9, 0.999), = le - 8, and learning rate of le - 3.A weight decay of 0.1 is applied, with warm-up period of 10k steps. The learning rate follows a cosine schedule, initially increasing linearly during the warm-up phase and then decreasing according to cosine function. A cosine y schedule is employed, with minimum y of 0.2 and decay epochs set to 18.
For SogCLR, the temperature parameter is set to 0.03. In FastCLIP, we set the initial temperature parameter to 0.07, to 6.d.and the learning rate for r to 2e 4. Additionally, the learning rate of 7 decays to one-third of its original value when r falls below 0.03, The complete set of hyperparameters is summarized Table 4. We tune a E {5e 4, le - 3) and the starting epoch in (15, 20). For SogCLR, we start using FNC/G1.FNN after 15 epochs with a = 5e 4, while for FasCCLIP we start after 20 epochs with a Le 3. For both losses, we initialize X, = 1 and use Adam updates with a learning rate of 0.05.
Table 4: Hyperparameters for FastCLIP Training
Hyperparameter
CC3M
Optimizer
Adam W (0.9, 0.999)
81,82
le-8
Learning rate
lc-3
Weight decay
0.1
Warm-up steps
10k
Cosine min
0.2
Decay epochs Temperature (SogCLR)
18
0.03
Initial temperature (FastCLIP)
0.07
p (FastCLIP)
6.5
Learning rate of (FastCLIP)
2e-4
D.3. Additional Experimental Results
Statistical Significance.
We check for statistical significance between using the false negative approaches against not using them, which we consider the baseline. Thus, we compute p-values via a paired 1-test between SogCLR + FNC/GL.FFD and SogCLR baseline across multiple runs, with the alternative hypothesis testing for performance greater than the baseline.
We report in Tables 5 and the p-values with respect to the baseline for the unimodal semi- superviee and transfer learning experiments respectively, and consider standard significance level of 5%. For the semi-supervised scenario, we can observe GLOFND achieves a p-value below 0.018 on all scenarios, thus achieving statistically significant improvements in all scenarios. Moreover, GLOFND achieves statistical significance below the % level on both the 100% and 1 % scenarios.
16

---

Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
For the transfer learning case, GLOFND achieves statistically significant improvements 6 out of 8 datasets, while FNC only achieves it on 2 of 8.
Table 5: Unimodal semi-supervised linear evaluation p-values WRT the baseline (SogCLR), We color red those above the 0.05 threshold. The p-values are calculated via a paired t-test across multiple runs with the alternative hypothesis testing for performance greater than the baseline.
Method
100.0%
10.0%
1.0%
0.1
SogCLR FNC
0.011
0.035
0.014
0.024
SogCLR GLOFND
0.002
0.011
<0.001
0.018
Table Unimodal transfer learning evaluation p-values WRT the baseline (SogCLR). We color red those above the 0.05 threshold. The p-values calculated via paired t-test across multiple runs with the alternative hypothesis testing for performance greater than the baseline.
Method
CIFARIO
CIFARI00
Food101
Caltech101
Cars
DTD
Pets
Flowers
SogCLR + FNC
0.158
0.056
0,219
0.249
0.235
0.080
0.032
0,036
SogCLR + GLOFND
0.143
0.005
0.021
0.024
0.006
0.123
0.002
0.005
SimCLR Experiment.
We evaluate the performance of GLOFND in conjunction with SimCLR. Unlike SogCLR, SimCLR identifies false negatives only within each mini-batch, necessitating the use of a larger batch size. Table 7 presents the linear evaluation results for SimCLR under the experimental setup described in Appendix D.I, using batch size of 512.
Table 7: Linear evaluation results in unimodal semi-supervised scenario. We train the linear classifiers with different percentages of randomly sampled labeled training data and present their top-1 accuracies (%) on the validation set. We include the overall average and, in parentheses, its improvement WRT SimCLR baseline.
Method
100.0%
10.0%
1.0%
0.1%
Average
SimCLR
76.88
73.38
66.40
33.56
62.56
FNC
76.90
73.10
64.88
34.20
62.27
GloFND
77.14
73.66
66.50
35.58
63.22
CLIP fine-tuning.
To evaluate the effectiveness of GLOFND in fine-tuning large pretrained models to mitigate the impact of false negatives, we fine-tune OpenAl's ResNet-50 CLIP model on CC3M. The experimental setup closely follows Appendix D.2, with the key difference being that we initialize from OpenAl's pretrained weights and train for 15 epochs, using FNC/GLOFND after the first epoch (a= 10-4). Validation image-text retrieval results reported in Table 8.
Table 8: We fine-tune OpenAl's ResNet-50 CLIP model on CC3M and report image-text retrieval results on its validation set.
Method
IR @ I
IR @
IR @ 10
IR Average
TR@
TR@5
TR @ 10
TR Average
Base
27.58
48.17
57.53
44.43
26.30
48.14
57.69
44.04
GloFND
36.07
58.94
67.22
54.08
35.76
59.19
67.44
54.13
+ FNC
33.69
58.01
67.51
53.07
33.61
57.95
67.53
53.03
+ GloFND
36.52
59.44
68.02
54.66
35.71
59.27
67.97
54.32
More examples of false negatives identified by GLOFND.
Figure 7 shows examples of false negatives identified by GLoFND for ImageNer100 with 0.01 during training. We observe that the number of false negatives identified is not constant for all anchors since we are using dynamic threshold for each anchor, as opposed to mini-batch top k approach. Moreover, the false negatives identified by GLOFND are
17

---

Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning
Anchor
False negatives
Anchor
False negatives
Figure 7: Examples of false negatives identified for ImageNet100 GLOFND with a 1%. The left column the anchor image and the rest are identified false negative samples.
semantically similar to the anchor image, which is what we aim to achieve.
18


Reviews:
[{"review_id": "I9LyLgDzY6", "reviewer": "Reviewer_tdJR", "summary": "In this work, authors propose GLOFND, a way to find and automatically threshold false negative samples during self-supervised training with contrastive learning. The proposed method works by determining adaptive thresholds $\\lambda_i$ for each anchor $i$ which, thanks to the optimization-based approach, are global to the entire dataset and not limited to the current minibatch. Contrarily to other existing methods which require to compute similarity across all possible pairs, GLOFND does not introduce significant complexity in the training. \n\nAuthors empirically test their approach on standard vision benchmarks such as ImageNet-100, CIFAR, DTD Caltech and Oxford datasets.\n\n## Update after rebuttal\n\nAfter reading the author's comments and other reviewers' comments, I maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thanks for your review and questions.\n\n**Q1: Experiment on larger dataset than ImageNet**\n\n**A:** We would like to point the reviewer to Table 3, where we tested GloFND on CC3M, which is larger than ImageNet-1k, with 2.7 million image-text pairs.\n\n\n**Q2: GLOFND applied on other baselines (SimCLR, VICReg, Barlow Twins, etc.)**\n\n**A:** We agree that it would be interesting to apply GloFND to other contrastive losses. To the best of our knowledge, VICReg and Barlow Twins do not use negative pairs, so the issue of false negative detection is not directly applicable. Regarding SimCLR, SogCLR has been previously shown [1] to outperform SimCLR, which requires a large batch size. Nevertheless, we have tried SimCLR using a batch size 512 with results shown below. \n\n| Method   | 100%  | 10%   | 1%    | 0.1%  | Average |\n| -------- | ----- | ----- | ----- | ----- | ------- |\n| Baseline | 76.88 | 73.38 | 66.40 | 33.56 | 62.56   |\n| FNC      | 76.90 | 73.10 | 64.88 | 34.20 | 62.27   |\n| GloFND   | **77.14** | **73.66** | **66.50** | **35.58** | **63.22**   |\n\n[1] Yuan, Zhuoning, Yuexin Wu, Zi-Hao Qiu, Xianzhi Du, Lijun Zhang, Denny Zhou, and Tianbao Yang. “Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance.” arXiv, September 20, 2022. http://arxiv.org/abs/2202.12387.\n\n\n**Q3: Fine-tuning large pre-trained model**\n\n**A:** We have fine-tuned OpenAI's CLIP model on CC3M using GloFND. The results on CC3M's validation set are shown below.\n\n| Method   | IR@1    | IR@5      | IR@10        | IR Avg | TR@1       | TR@5            | TR@10         | TR Avg |\n| -------- | ------- | --------- | ------------ | ------ | ---------- | --------------- | ------------- | ------ |\n| Baseline | 36.07   | 58.94     | 67.22        | 54.08  | **35.76**      | 59.19           | 67.44         | 54.13  |\n| FNC      | 33.69 | 58.01 | 67.51 |   53.07     | 33.61 | 57.95 | 67.53 |      53.03  |\n| GloFND   | **36.52**   | **59.44**     | **68.02**        | **54.66**  | 35.71      | **59.27**           | **67.97**         | **54.32**  |\n\n\n\n**Q4: Comparison with finding global thresholds in the entire dataset**\n\n**A:** We agree such a comparison would be beneficial. Kindly note that computing the global threshold in the entire dataset would need to be done every iteration, which is intractable. Instead, we freeze the encoder network and compare GloFND with the (estimated) global thresholds. You can find this analysis in Section 4.3 (iii).\n\n**Q5: Why does the performance decrease after epoch 70?**\n\n**A:** Thanks for this question. We hypothesize the reason is that the total number of training epochs is fixed to 200. That is, there is a trade-off between starting at a later epoch (and having a better \"sufficiently\" trained network), and the amount of training epochs for GloFND to positively impact. Starting at a later epoch entails less training time with GloFND which reduces the potential improvement of removing false negatives. FNC shows a similar pattern, with its performance dropping after 110.\n\n**Q6: Improvements in the bimodal setting are less significant than in the unimodal setting**\n\n**A:** Thanks for pointing this out. We agree with your observation. We hypothesize that this is due to the training time because the bimodal dataset is much larger.  While we train GloFND for 130 epochs in the unimodal setting, training for only 22 epochs in the bimodal setting makes the value of $\\lambda$ less stable.", "claims_and_evidence": "- This work identifies the issue of determining false positive pairs in a global and efficient manner\n\n- The proposed approach is in line with the authors' goal\n\n- The proposed approach can be integrated into to many existing contrastive learning framework", "methods_and_evaluation_criteria": "- The evaluation criteria ideally are okay, my main concern is in the lack of comparison and well-established baselines [see experimental design or analyses]. \n\n- The ablation study is thorough", "theoretical_claims": "- I think the theoretical claims are well motivated, although I would make a stronger connection to meta-learning literature (as essentially the thresholds $\\lambda_i$ will change the main objective function)", "experimental_designs_or_analyses": "I think that the main weakness of this work lies in the experimental setting: \n\n- Larger datasets such as ImageNet-1k are missing (I think experiments on it should be doable)\n\n- The only comparison is with FNC, which selects local false positive samples in a minibatch\n\n- GLOFND is only applied to SogCLR\n\nFor these reasons i think that: \n\n- Some more experiments are required, showcasing GLOFND applied on other baselines (SimCLR, VICReg, Barlow Twins, etc.)\n\n- GLOFND requires the network to be sufficiently trained to work: for me this makes sense, and I think that applying GLOFND for fine-tuning large pre-trained model would be for an excellent use case. I would like to see some experiments in fine-tuning some existing large models to reduce the impact of false-positive pairs (authors only tested with SogCLR and FastCLIP)\n\n- A comparison with finding global thresholds in the entire dataset (even if computationally expensive) should be added", "relation_to_broader_scientific_literature": "This work proposes an adaptive method to find thresholds for filtering out false positive samples. It may represent an interesting contribution to the field.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- The paper is very well written and the objective is clear\n\n- I think Eq. 2 would benefit from a clearer explanation", "other_comments_or_suggestions": "- L190-L191 are not clear", "questions_for_authors": "- In Fig. 5d, authors show the results of GLOFND with varying starting epochs; I wonder why the performance decreases after epoch 70? \n\n- Improvements in the bimodal setting are less significant than in the unimodal setting, what could be the reason for it?", "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": "", "extra_scores": {}}, {"review_id": "n3BhmHSL8p", "reviewer": "Reviewer_UmKd", "summary": "Previous contrastive learning methods may generate negative sample pairs with similar semantics when constructing negative samples. Different from them, this paper introduces a method that automatically learns on the fly the threshold for each anchor data to identify its false negatives during training. Meanwhile, it can globally detect false negative samples rather than locally within the mini-batch. Experiments are done to verify the effectiveness of the method.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thanks for your review and questions.\n\n**Q1: About GloFND limitations to a specific contrastive learning (CL) technique and integration on classical contrastive learning algorithms.** \n\n**A:** Thanks for this question, this is something we could have done a better job explaining. To clarify, the computation of $\\lambda$ in GloFND is independent of the contrastive loss used, as it relies solely on the embedding similarity of negative pairs. This makes it applicable across different contrastive learning methods. In our experiments, we applied GloFND to unimodal SogCLR, bimodal SogCLR and FastCLIP. As you suggested, we have additionally run unimodal GloFND with SimCLR with results shown in Reviewer tdJR's Q2 answer. However, it is worth noting that prior work [1] has shown that SogCLR outperforms SimCLR. Additionally, SimCLR requires a large batch size, and its performance can be more sensitive to the impact of false negatives as batch size increases.\n\n[1] Yuan, Zhuoning, Yuexin Wu, Zi-Hao Qiu, Xianzhi Du, Lijun Zhang, Denny Zhou, and Tianbao Yang. “Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance.” arXiv, September 20, 2022. http://arxiv.org/abs/2202.12387.\n\n\n**Q2: The novelty of this method is insufficient, and its generalizability does not seem to be well demonstrated in the paper.**\n\n**A:**  We appreciate the reviewer’s feedback and would like to clarify the novelty and generalizability of our approach. Formulating false negative discovery as identifying the k-th largest similarity across the **entire dataset** is, to the best of our knowledge, a novel contribution. This formulation enables a simple yet effective algorithm based on stochastic optimization for efficient computation.\n\nWe have conducted experiments to demonstrate its applicability in unimodal CL (semi-supervised and transfer learning) and bimodal CL. Moreover, to further demonstrate generalizability, we have conducted additional experiments with SimCLR, reinforcing its broad applicability (see the previous question). We appreciate the reviewer’s concerns and are open to suggestions that could further strengthen this aspect.\n\n\n**Q3: The experiments in this paper seem to be insufficient. The author focuses on how to find false negative samples, but ignores the generality research in specific comparative learning or self-supervised learning methods.**\n\n**A:** To address your concern, we have conducted additional experiments using SimCLR (see Reviewer tdJR Q2). We have also conducted an experiment fine-tuning OpenAI's CLIP model on CC3M (see Reviewer tdJR Q3).\n\n\n**Q4: The author's focus does not seem to be on downstream task performance.**\n\n**A:** We would like to draw the reviewer’s attention to Tables 2 and 3, which present results on downstream task performance. In Table 2, we pretrain on ImageNet100, after which a logistic regression classifier is trained on top of the frozen embeddings for multiple unimodal downstream datasets. In Table 3, we pretrain on CC3M and evaluate performance on 38 zero-shot downstream tasks using the DataComp benchmark. Notably, GloFND improves downstream performance in most scenarios.\n\n**Q5: Addressing computational overhead of computing cosine similarity across the entire dataset when selecting the most similar negative samples to the anchor.**\n\n**A:** Thank you for the question. While GloFND computes a global threshold for the entire dataset, it does not require computing cosine similarity across all data points in the dataset. Instead, all computation is done in the mini-batch. This is what makes GloFND shine. \n\nGloFND frames the problem as a stochastic optimization task, allowing for efficient computation. Equation 4 details how the $\\lambda_I$ values are obtained, and as shown, GloFND relies only on mini-batch computations to optimize $\\lambda_i$.\n\nImportantly, the pairwise similarities are already computed as part of the contrastive loss, meaning the only additional computational overhead introduced by GloFND is:\n1. Updating the $\\lambda$ values for samples in the mini-batch, which involves a simple gradient computation (Equation 4).\n2. Filtering false negatives, which is also done via matrix operations by comparing similarities against the computed $\\lambda$ values and applying masking.\n\nBoth can run efficiently on GPUs. Overall, our method consists of basic matrix computations and runs in linear time with respect to the number of pairs in a batch $O(B^2)$, where $B$ is the batch size). This overhead is minimal compared to the cost of cosine similarity computations and the forward/backward passes. For the unimodal case, the per-epoch computation time increases by only 2% (from 427s to 435s), demonstrating the efficiency of our approach.", "claims_and_evidence": "The claims made in the opinion are supported by clear and compelling evidence and further validated by experiments.", "methods_and_evaluation_criteria": "Yes, the method proposed in this paper is a good research direction in the field of contrastive learning.", "theoretical_claims": "The false negative sample detection method proposed in this paper has no obvious problems in theory.", "experimental_designs_or_analyses": "This paper has basically no problems in terms of experimental design and analysis, but there is one problem is that the authors claim that GLOFND is not limited to any specific contrastive learning (CL) technique, however, there does not seem to be direct evidence supporting this claim in the experiments.", "relation_to_broader_scientific_literature": "In this paper, the method \"GLOFND\" is proposed from the perspective of detecting false negative samples. However, how to reasonably define false negative samples and eliminate them is an important research direction of contrast learning, which has a certain impact on the improvement of model performance.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths：\n(1)In this paper, a novel method is proposed to automatically find false negative samples, and its view is proved by experiments. The article has clear ideas. The method is simple and effective. \n(2)The structure of this paper is clear.\n(3)The proposed method has better performance and experimental results in some cases\nWeaknesses:\n(1)The authors claim that GLOFND is not limited to any specific contrastive learning (CL) technique. However, they only integrate it with SogCLR and do not demonstrate its effectiveness on classical contrastive learning algorithms, thereby reducing the credibility of their claims.\n(2)The novelty of this method is insufficient, and its generalizability does not seem to be well demonstrated in the paper.\n(3)The experiments in this paper seem to be insufficient. The author focuses on how to find false negative samples, but ignores the generality research in specific comparative learning or self-supervised learning methods.\n(4)The author's focus does not seem to be on downstream task performance, and adding some downstream task evaluations, such as object detection, might be more convincing.", "other_comments_or_suggestions": "(1)The authors mention that previous methods require computing cosine similarity across the entire dataset when selecting the most similar negative samples to the anchor. However, it appears that they have not effectively addressed this computational overhead.\n(2)The authors should apply their method to a broader range of contrastive learning (CL) approaches to further validate its effectiveness and strengthen its credibility.", "questions_for_authors": "There's no question.", "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": "", "extra_scores": {}}, {"review_id": "NoymZpoJMb", "reviewer": "Reviewer_KEsn", "summary": "This paper presents an approach to detect false negative pairs in contrastive learning. Contrary to previous approaches, they work by detecting FN globally on the pretraining dataset, and they are computationally efficient as they apply SGD for each anchor and do not require to compute clustering for the whole dataset. They conduct extensive experiments to compare and validate the approach.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thanks for your review and questions.\n\n**Q1: It would have been nice to see other downstream tasks than classification to validate further the quality of the learned representation.**\n\n**A:** Thanks for pointing this out. We agree that the unimodal performance has only been validated in the context of classification. In the bimodal scenario, please note we use the Datacomp Benchmark. This benchmark includes 38 zero-shot downstream tasks, which also include cross-modal image-text retrieval tasks. As suggested, we will modify the contributions to clarify the tasks used for validation.\n\n\n**Q2: Display computational overhead results in the core of the paper.**\n\n**A:** Thanks for your comment. We will move the computational overhead result to the main paper.\n\n\n**Q3: Introduction, for practical CL training on ImageNet, how many FN do we have on average? Also, it would be good to give an idea of the impact these FN have on final results (results on a particular downstream tasks can be shown in an early figure).**\n\n**A:** During training on ImageNet100, the empirical average of FN is 1%, that's around 20k FN per batch with a batch size of 1024 and 325 with a batch size of 128. Thanks for your suggestion. We agree both of these questions would provide a better idea of the importance of this line of work. We will make changes to the introduction to address both.\n\n\n**Q4: GloFND performance for fine-grained classification downstream tasks?**\n\n**A:** Thanks for the question, this is something we could have done a better job pointing out. Table 2 presents the performance on several fine-grained downstream datasets such as Stanford Cars, Oxford 102 Flowers, Oxford-IIIT Pets, Caltech-101, and Food-101.\n\n\n**Q5: About the top $\\alpha$% assumption. What proportions of detected FN are actually FN in practice?**\n\n**A:** Table 1 presents \"False Negative Identification\" metrics, which evaluate what proportion of detected FN are actually FN in practice. As it can be observed, GloFND achieves much better precision, recall, and f1-score compared to FNC. Answering your question, the last epoch mean for GloFND is 48.40% of predicted FN are true FN, compared to 27.57% for FNC.", "claims_and_evidence": "This paper claims to have a efficient and effective approach for FN detection in contrastive learning. They do not overclaim, and they conduct the necessary experiments to prove their approach works well. \n\nIt would have been nice to see other downstream tasks than classification to validate further the quality of the learned representation. The contributions should state clearly that the findings are only validated in the context of classification and that further experiments are needed to evaluate performance of representation learning for other tasks.", "methods_and_evaluation_criteria": "Proposed datasets and metrics are sufficient and appropriate for evaluation of the method.", "theoretical_claims": "I did not check the proof in the supplementary material in full details, but it seems correct.", "experimental_designs_or_analyses": "Experiments are sufficient to support the claim about the FN detection method being good and efficient. \n\nIt would be good to display computational overhead results compared with other approaches in the core of the paper, since it is part of the claimed advantages of the method.", "relation_to_broader_scientific_literature": "The literature review is very complete, it flows logically and presents a nice introduction to the topic.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "It would be good to provide the reader with a rough idea of the scale of the amount of FN in practical CL scenarios. For example, for practical CL training on ImageNet, how many FN do we have on average? Also, it would be good to give an idea of the impact these FN have on final results (results on a particular downstream tasks can be shown in an early figure). This should be mentioned explicitely in the introduction, as it would help grasping the importance of the proposed line of work.\n\nBy removing examples that are close to each other in the latent space as FN, isn't there a risk of removing hard true negatives, thus making the contrastive learning too simple and thus reducing the performance of the representation learned? --> In other words, could it decrease the performance for fine grained classification downstream tasks? This could be tested in the experiments by including fine grained datasets.\n\n\"Moreover, we assume that the top α% most similar negative data share similar semantics with the anchor data based on their current representations\" --> This is a rather strong assumption. This should be backed up by experiments using the labels. What proportions of detected FN are actually FN in practice?", "other_comments_or_suggestions": "See above", "questions_for_authors": "See above", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a method for learning per anchor similarity thresholds that separate false negatives from true negatives during contrastive learning.  Reviewer opinion is split, with tdJR and KEsn recommending accept, while UmKd recommends reject.  The rebuttal resolves some, but not all reviewer concerns.

Reviewer UmKd notes that "novelty of this method is insufficient, and its generalizability does not seem to be well demonstrated" and asks for experiments on "downstream task evaluations, such as object detection".  The rebuttal does not fully resolve this concern as it points to Tables 2 and 3, which cover only classification and retrieval tasks, rather than tasks such as object detection or segmentation that require more detailed output.

Reviewer KEsn raises concern over a strong assumption made in the paper about the structure of the data: "we assume that the top $\alpha$% most similar negative data share similar semantics with the anchor data based on their current representations."  The rebuttal responds with clarifications about $\alpha$, but does not address the core of this concern.  Specifically, $\alpha$ is a hyper-parameter; if chosen correctly it can yield good results (as demonstrated in experiments), but the paper chooses $\alpha$ in an ad-hoc, heuristic manner.

Overall, limitations in novelty and generality are balanced against experiments that demonstrate the efficiency of the approach and improved results.
Decision: Accept (poster)