In semi-supervised learning, self-supervised pre-training, and deep clustering, models face a common fundamental challenge: how do we assign labels to unlabeled data to guide feature learning?
The traditional approach relies on per-sample thresholding. A model computes a softmax probability vector for an unlabeled image, and if its confidence for a specific class exceeds a predefined threshold (e.g., 95%), that class becomes its "pseudo-label."
While intuitive, this greedy strategy suffers from a fatal flaw: confirmation bias. If a model develops a slight initial bias toward a majority class, it will naturally produce more high-confidence predictions for that class. This generates more pseudo-labels for the majority class, which further entrenches the model's bias during the next training iteration. Left unchecked, this feedback loop leads to representation collapse, where the model completely ignores minority "tail" classes or collapses all data into a handful of dominant clusters.
To break this loop, a rapidly growing body of research shifts the perspective from local thresholding to global assignment, framing pseudo-labeling as an Optimal Transport (OT) problem. Instead of asking "Is this specific sample a dog?", the system asks: "Given this entire batch of samples, how do we distribute them across our available categories such that we respect our expected class proportions while minimizing prediction error?"
The Intuition: Pseudo-Labeling as Resource Allocation
To understand why this works, imagine you are managing a warehouse distribution network. You have a collection of items (unlabeled data points) that need to be shipped to various retail stores (target classes or prototypes). Each store has a specific capacity or demand (the expected class distribution), and shipping an item to a store incurs a cost (the distance between the sample's feature representation and the class prototype).
Your goal is to find a transport plan—an assignment matrix—that satisfies the demand of every store while minimizing the total shipping cost.
Unlabeled Samples (Sources) Target Classes / Prototypes (Sinks)
[ Sample 1 ] -------------\ /-------------> [ Class A (Prior: 50%) ]
[ Sample 2 ] --------------X--------------> [ Class B (Prior: 30%) ]
[ Sample 3 ] -------------/ \-------------> [ Class C (Prior: 20%) ]
Global Transport Plan (P)
Enforces Marginal Constraints (q)
Mathematically, let $N$ be the number of samples in a batch and $K$ be the number of classes. We define a cost matrix $C \in \mathbb{R}^{N \times K}$, where $C_{ij}$ represents the dissimilarity (such as the negative log-likelihood or cosine distance) between sample $i$ and class prototype $j$. We seek a transport plan $P \in \mathbb{R}^{N \times K}$ that minimizes the total cost:
$$\min_{P} \sum_{i,j} P_{ij} C_{ij}$$
Crucially, we subject this optimization to two strict marginal constraints:
- Row Constraint: $\sum_{j} P_{ij} = \frac{1}{N}$, ensuring that every sample's probability mass is fully allocated.
- Column Constraint: $\sum_{i} P_{ij} = q_j$, where $q$ is a vector representing the target label distribution (e.g., a uniform distribution for balanced clustering, or a known class prior).
By forcing the columns to sum to a predefined target distribution $q$, the model can no longer collapse into a single majority class. As shown by Rizve et al., integrating these class distribution priors directly into the optimal transport formulation prevents model collapse and stabilizes training on imbalanced datasets. Similarly, Zhang et al. demonstrate that aligning global sample distributions via optimal transport is significantly more robust than making independent sample-level predictions, as it explicitly models the relationships between all samples in a batch simultaneously.
The Mathematical Engine: The Sinkhorn-Knopp Algorithm
Solving the standard linear programming formulation of optimal transport is computationally expensive, scaling at $O(N^3 \log N)$, which is far too slow to run inside the inner loop of a deep neural network.
The breakthrough that makes optimal transport pseudo-labeling practical is entropy regularization. By adding an entropic penalty term to the objective function, the problem becomes strictly convex:
$$\min_{P} \sum_{i,j} P_{ij} C_{ij} + \epsilon \sum_{i,j} P_{ij} \log P_{ij}$$
Where $\epsilon$ controls the smoothness of the assignment. This regularized formulation can be solved incredibly fast using the Sinkhorn-Knopp algorithm. According to Cuturi's theorem, the optimal solution takes the form of a simple matrix scaling:
$$P = \text{diag}(u) \exp(-C / \epsilon) \text{diag}(v)$$
Where $u \in \mathbb{R}^N$ and $v \in \mathbb{R}^K$ are scaling vectors found by iteratively normalizing the rows and columns of the exponentiated cost matrix to match the target marginals.
Because this involves only basic matrix-vector multiplications, it can be executed efficiently on GPUs. As highlighted by Wu et al., the Sinkhorn-Knopp algorithm allows models to dynamically update soft target labels for every batch in real time, making the process computationally feasible for high-speed contrastive learning. Li et al. successfully scaled this mechanism to pixel-level self-labeling for semantic segmentation, proving that fast matrix-scaling approximations can handle high-throughput label updates without increasing inference latency.
Correcting for Imbalance and Noise
The power of optimal transport pseudo-labeling becomes most apparent when dealing with real-world data imperfections, such as long-tailed class distributions and out-of-distribution noise.
The Long-Tail Problem
When a dataset is highly imbalanced, forcing a uniform distribution constraint ($q_j = 1/K$) would be disastrous, forcing rare tail classes to absorb samples that do not belong to them. To fix this, frameworks like SoLar, introduced by Wang et al., use estimated class priors to dynamically adjust the target distribution vector $q$.
When the transport plan is optimized against an imbalanced target, it acts as an implicit adaptive sampler. As explained by Gao et al., the optimization automatically assigns higher transport costs to minority samples, ensuring they are mapped to distinct regions of the latent space despite their low frequency in the training set. This prevents the model from ignoring rare categories, allowing accurate label recovery even in highly skewed environments (Zhu et al.).
Handling Out-of-Distribution Noise
What happens when a batch contains noisy samples or entirely unknown classes that shouldn't be assigned to any of the known prototypes?
Standard optimal transport forces all mass to be distributed, which would pollute the prototypes with noise. To solve this, Zhang et al. proposed a Partial Optimal Transport framework that introduces a "virtual sink."
Samples Prototypes
[ Clean Sample 1 ] --------------------> [ Class Prototype A ]
[ Clean Sample 2 ] --------------------> [ Class Prototype B ]
[ Noisy / OOD Outlier ] ---------------> [ Virtual Sink (Trash Bin) ]
This virtual sink acts as a placeholder category with a fixed, moderate transport cost. If a sample is an outlier and lies far from all valid class centroids, the optimization determines that the cheapest option is to "dump" its probability mass into the virtual sink rather than forcing it into an incorrect cluster.
Applications Across the Lifecycle
Because optimal transport pseudo-labeling is a general mathematical framework for distribution matching, it has been adopted across a wide variety of machine learning paradigms:
- Unsupervised Deep Clustering: In the absence of any labels, models are highly prone to degenerate solutions where all data points map to a single cluster. Single-author works by Lin and Sellars demonstrate that enforcing an equal partition constraint via Sinkhorn-Knopp ensures that data points are partitioned evenly across a set of trainable prototypes, maintaining cluster diversity. Toering et al. leverage this to prevent representation collapse in self-supervised video learning, while Xu applies it to single-cell RNA sequencing data to maintain biologically realistic cluster sizes.
- Domain Adaptation: When deploying a model from a labeled source domain (e.g., synthetic data) to an unlabeled target domain (e.g., real-world images), Zhu et al. show that mapping unlabeled target samples to class prototypes using optimal transport preserves the global structure of the data distribution, preventing majority-class bias.
- Inference-Time Adaptation: Remarkably, this framework can be applied without any model training at all. Shin et al. introduced a training-free adapter that treats zero-shot classification (e.g., using CLIP) as an inference-time optimal transport problem. By mapping raw prediction scores to a cost matrix and solving for a transport plan that satisfies the target dataset's label frequencies, they correct for distribution shift entirely on the fly.
By shifting from isolated, greedy decisions to a global, distribution-aware allocation, optimal transport transforms pseudo-labeling from a noisy heuristic into a mathematically principled, collapse-resistant foundation for unsupervised and semi-supervised learning.