Optimal transport is a branch of mathematics that formalizes the problem of transforming one probability distribution into another with minimal cost. Originating from the work of Gaspard Monge in 1781 and later generalized by Leonid Kantorovich in 1942, the theory provides a rigorous framework for comparing and shifting mass, such as goods, data points, or probabilities. Its core insight is to treat the difference between distributions not as a simple scalar but as a geometric quantity that accounts for the underlying space's structure.
The problem is typically stated in two forms. Monge's formulation seeks a deterministic mapping that pushes one distribution to another, minimizing the total transport cost. Kantorovich's relaxation allows for mass to be split and reassigned, leading to a linear programming problem that always has a solution. This relaxation introduced the concept of a transport plan and the Wasserstein distance, a metric that quantifies the minimal cost of transforming one distribution into another.
Mathematical Foundations
At the heart of optimal transport is the cost function, usually defined as the distance between points raised to a power, such as the squared Euclidean distance. The Wasserstein distance of order p, denoted W_p, is defined as the minimum expected cost over all couplings. For p=1, it is also known as the Earth mover's distance, popular in image retrieval and histogram comparison. The theory connects to partial differential equations through the Monge-Ampere equation, which describes the optimal mapping in continuous settings.
Kantorovich duality is another key result, expressing the primal transportation problem as a supremum over pairs of functions, leading to efficient computational methods. This duality also links optimal transport to concepts in convex analysis and game theory. The existence and uniqueness of optimal solutions under certain conditions were established by mathematicians such as Yann Brenier in 1991, who showed that for quadratic costs, the optimal map is the gradient of a convex function.
Computational Approaches
Computing optimal transport plans exactly is computationally intensive, especially in high dimensions. The introduction of entropic regularization by Marco Cuturi in 2013 transformed the field, allowing the use of the Sinkhorn algorithm, which iteratively scales a matrix to approximate the optimal plan. This approach, known as Sinkhorn distances, scales to large datasets and has become a staple in Machine learning libraries.
Sparse and multiscale methods have further improved scalabilityhet on parallel hardware such as AMD and NVIDIA GPUs. Libraries like Python's POT (Python Optimal Transport) and JAX-based implementations provide efficient solvers. For high-dimensional problems, approximate methods such as sliced optimal transport project distributions onto lower-dimensional spaces, reducing complexity while retaining geometric information.
Applications in Machine Learning
In Machine learning, optimal transport is widely used for domain adaptation, where a model trained on one distribution is adjusted to work on another. The Wasserstein distance serves as a training objective in generative models, notably in Wasserstein generative adversarial networks (WGANs), introduced by Martin Arjovsky and colleagues in 2017, which improve training stability compared to traditional GANs.
Optimal transport also powers Neural network interpretability and model compression. For instance, it is used to align embeddings from different models, enabling transfer learning across Artificial intelligence systems. In Deep learning, it facilitates the alignment of latent spaces in variational autoencoders and helps in clustering with geometric awareness. The theory underpins methods in Generative AI for controlling the output distribution of models, improving diversity and fidelity.
Economics and Other Domains
Beyond AI, optimal transport is foundational in economics, where it models resource allocation, such as shipping goods from factories to markets with minimal cost. It is used in econometrics to measure inequality through the Wasserstein distance between income distributions. In urban planning, it assists in optimizing public transportation networks and facility locations.
In image processing, optimal transport enables color transfer between images and shape morphing. In bioinformatics, it aligns single-cell RNA sequencing data across experimentsley. The theory also appears in meteorology for data assimilation and in finance for risk management and portfolio optimization, where it helps in comparing probability distributions of asset returns.
Recent Developments
Recent research extends optimal transport to unbalanced and partial transport, where total mass may not be conserved, useful in noisy settings. Neural optimal transport uses Deep learning to parameterize transport maps, enabling use in high-dimensional spaces. The field also intersects with Large language model alignment, where it helps in evaluating and improving semantic similarity between text embeddings.
The Sinkhorn algorithm has been adapted for use in Transformer (architecture) architectures, improving attention mechanisms' efficiency. Researchers at Google DeepMind and OpenAI have explored optimal transport for improving training data selection and model robustness. As of 2024, optimal transport remains a vibrant research area, with annual workshops at major AI conferences like NeurIPS and ICML, reflecting its broad utility.
infobox
• Type: Mathematical theory
• Introduced: 1781 (Monge), 1942 (Kantorovich)
• Introduced by: Gaspard Monge, Leonid Kantorovich
• Related: Machine learning, Deep learning, Generative AI
/infobox