How Can Global False Negatives Be Discovered on the Fly in Contrastive Learning?

Why similar negatives corrupt contrastive representations

Self-supervised contrastive learning builds positive pairs from two augmented views of the same image and negative pairs by sampling other images from the dataset, without checking whether those images share semantics. When a sampled negative is semantically close to the anchor, the loss still pushes the two embeddings apart. The paper calls such a pair a false negative, and notes that this pushes the model to discard semantic information it should keep.

The scale is not trivial. During SogCLR pretraining on ImageNet100, roughly 1% of all negative pairs are false negatives; with a batch size of 1024 that translates to about 20,000 false negatives per batch, and about 325 at a batch size of 128. The paper also reports that a linear classifier trained on representations learned in the presence of such false negatives can reach up to 10% lower accuracy in a semi-supervised setting than representations learned without them.

Local detection misses what the whole dataset contains

Prior false-negative discovery splits into two families. Local methods judge an anchor against other samples inside the same mini-batch, using similarity or adjacency. The paper's objection is structural: the most similar item inside a small mini-batch need not be the most semantically similar item in the full data space, so a local rule can miss the real false negative or flag the wrong one.

The global alternative, IFND, searches the whole dataset for each anchor but does so by clustering the entire dataset at specific epochs. That gives global coverage at the price of computation that grows with dataset size. GloFND is positioned against both: it keeps the dataset-wide definition of a false negative while keeping the per-iteration cost mini-batch-sized.

A threshold that encodes a quantile, not a fixed cutoff

GloFND defines the false negatives of an anchor as the top-α% most similar negative points across the entire dataset, meaning the set above the (1−α)-quantile of similarity scores, with α in [0,1]. Each anchor therefore gets its own threshold λᵢ rather than sharing one global cutoff, because different anchors sit in regions of embedding space with different similarity scales.

The threshold is not set by hand. It is learned by stochastic gradient descent on a convex problem whose target is to filter out exactly the top-α% of a set of scores. The update moves λᵢ in the direction that makes the fraction of negatives scoring above it approach α, and the result is projected back onto [−1,1] because cosine similarity scores live in that interval. In the image experiments α is set to 0.01, and threshold updates begin only after a tuned starting epoch chosen from {70, 90, 110}.

Two alternating updates keep detection inside the batch

The algorithm alternates between two steps. First, for each anchor in the current batch, λᵢ is updated using only the negatives present in that batch, so the threshold estimate is refined incrementally while the definition it targets remains dataset-wide. Second, the encoder is updated with a modified contrastive loss in which negatives scoring above λᵢ are removed from the anchor's negative set, so they no longer push the embeddings apart.

Removing false negatives shrinks the negative set, and the paper compensates with a moving-average estimator: each anchor keeps a scalar uᵢ that accumulates an estimate of its loss term across iterations, following SogCLR. This is what allows the method to work without a large batch size. The added computation is described as basic matrix operations running in O(B²), which the paper argues is negligible next to the cosine similarity and forward/backward passes.

Gains appear in both image and image-text pretraining

For unimodal experiments the paper pretrains a ResNet-50 with a 2-layer projection head for 200 epochs at batch size 128, then evaluates by freezing the encoder and training a linear classifier on top. Evaluation covers 100%, 10%, 1%, and 0.1% of labeled training data, and the reported semi-supervised figure averages top-1 validation accuracy across those fractions. Transfer performance is measured on eight additional datasets with a logistic regression classifier on frozen features.

For bimodal experiments the paper uses CC3M, with a downloaded training set of 2,723,840 image-text pairs after some links expired, and evaluates zero-shot behavior through the Datacomp benchmark's 38 downstream tasks, reporting the average along with subsets for ImageNet and its variants and for cross-modal retrieval. The paper's claim is that GloFND improves existing contrastive learning methods in both settings with minimal computational overhead; the qualitative t-SNE comparison on ImageNet100 shows tighter, more distinct peripheral clusters after false negatives are removed.

The benefit depends on how many false negatives exist

The paper states its own boundary directly: gains from GloFND and similar false-negative techniques on downstream tasks depend on the proportion of false negatives in the pretraining dataset and on how false negatives are defined within the downstream task. That condition matters more than the choice of benchmark, because a dataset with few semantically overlapping negatives gives the threshold little to remove.

Two further limits are stated by the authors. The method addresses false negatives only by filtering them out, which the paper calls straightforward and effective in its settings but not the only option; treating them as extra positives is mentioned as an alternative the paper does not pursue. And α is a single shared value rather than an individualized per-anchor setting, which the authors list as an open question alongside whether GloFND could extend beyond contrastive methods.

Watch the α setting and the starting epoch

The most decision-relevant detail for anyone reusing this method is that GloFND introduces two knobs that must be tuned per setting: α, which fixes what fraction of negatives is declared false, and the epoch at which threshold learning starts. The image experiments use α = 0.01 with a starting epoch tuned over three values; the CC3M experiments tune α over {5e−4, 1e−3} and start after 15 epochs for SogCLR or 20 for FastCLIP. These are not incidental hyperparameters, since α directly defines the quantity the threshold is solving for.

The paper's own framing puts the priority on the global-versus-local distinction rather than on raw accuracy deltas: the contribution is a way to apply a dataset-wide false-negative definition at mini-batch cost, and the reported evidence is that this improves existing contrastive methods in unimodal and bimodal settings. Whether it pays off in a given pretraining corpus should be judged against that corpus's share of semantically overlapping negatives, which the authors identify as the condition governing downstream benefit.

Sources used in this answer