TL;DR
This paper introduces a principled framework for generating "hard" negative samples in contrastive representation learning by leveraging Optimal Transport (OT). By framing negative sampling as a worst-case optimization problem and then regularizing it with OT, they demonstrate a theoretically justified approach that leads to improved representation learning performance on downstream tasks.
What Problem Does This Paper Address?
Contrastive representation learning aims to learn powerful data representations by pulling similar samples (positives) together and pushing dissimilar samples (negatives) apart in an embedding space. A crucial, yet often heuristically designed, component of this process is the selection of negative samples. Choosing "hard" negatives – those that are semantically similar but not identical to the anchor – is known to improve learning, but how to best generate them remains an open question. Previous methods often relied on ad-hoc strategies. This paper addresses the theoretical underpinnings of hard negative sampling, showing that a naive worst-case approach leads to degenerate solutions and proposing a regularized Optimal Transport framework as a principled solution.
Methods
The authors propose a novel min-max framework for hard negative sampling. They define the problem as finding a representation that minimizes the maximum contrastive loss over all possible joint distributions (couplings) between anchor, positive, and negative samples, subject to marginal constraints. They prove that this unregularized min-max formulation leads to degenerate representations (where all samples map to the same point).
To overcome this degeneracy, they re-interpret the problem through the lens of Optimal Transport (OT). Specifically, they use regularized OT, employing entropic regularization (KL divergence) to control the "hardness" of the negative samples. This approach allows for a smooth control over the degree of similarity between the generated negative samples and the anchor. They also explore using a novel ground cost function beyond the standard squared Euclidean distance to further refine negative sample selection.
Datasets
The paper evaluates their method on several standard datasets:
- Image Datasets: STL10, CIFAR10, CIFAR100, and Tiny-ImageNet.
- Graph Datasets: MUTAG, ENZYMES, PTC, IMDB-BINARY, and IMDB-MULTI.
Key Insights and Ideas
- Theoretical Justification for Regularization: The paper provides the first theoretical justification for why regularization is necessary in hard negative sampling. The unregularized min-max approach inherently leads to degenerate representations, meaning the learned embeddings are not discriminative.
- Optimal Transport as a Principled Framework: Re-framing negative sampling as an Optimal Transport problem offers a systematic and theoretically grounded way to design negative sampling distributions.
- Tunable Hardness: Regularized OT, particularly with entropic regularization, allows for fine-grained control over the "hardness" of negative samples by adjusting the regularization parameter ($\epsilon$).
- Beyond Squared Euclidean Distance: The exploration of alternative ground costs in OT suggests that the choice of cost function significantly impacts the quality of learned representations, potentially by better identifying "false negatives" or uninformative samples.
Key Results
- Improved Performance: The proposed method consistently outperforms baseline methods like SimCLR and matches or slightly exceeds the performance of a recent state-of-the-art method (HCL [12]) on various image and graph datasets.
- Image Datasets: Achieved absolute improvements of up to 4.8 percentage points over SimCLR on NCE loss for STL10.
- Graph Datasets: Consistently improved accuracy over the InfoGraph baseline by 1.3-1.4 percentage points on MUTAG and PTC datasets.
- Qualitative Insights: Visualizations (t-SNE) show that after training with their method, images with the same class label become closer in the representation space, and the generated hard negatives are semantically more related to the anchor compared to uniformly sampled negatives.
Limitations and Future Work
- Computational Cost: While the use of entropic regularization and the Sinkhorn algorithm makes the OT approach computationally feasible, it can still be more demanding than simpler sampling strategies.
- Hyperparameter Tuning: The method introduces hyperparameters (e.g., $\epsilon$ for regularization, and potentially parameters for the ground cost) that require tuning.
- Future Work: The authors suggest exploring other regularization mechanisms beyond entropic regularization, different marginal constraints, and novel ground costs within the OT framework to further improve negative sample design. They also hint at investigating the trade-offs between learning representations that are discriminative and those that capture semantic similarity more broadly.
Summary updated