Optimal Transport: The Ancient Moving-Earth Problem Now Training Modern AI

Picture a pile of dirt at a construction site and a set of trenches that need filling. Every shovelful you move costs you something — distance, fuel, time. There are a near-infinite number of ways to pair up "this scoop of dirt" with "that trench," and almost all of them are wasteful. Somewhere in that haystack of possibilities is one assignment that costs the least total effort. Finding it, in general, is brutally hard.

That problem — stated almost exactly that way — is 245 years old. It was posed by a French mathematician trying to help the French army move earth more efficiently. Today, the same mathematics sits inside the training loop of some of the most advanced AI image and language models on the planet. The idea that connects an 18th-century fortifications problem to modern generative AI is called optimal transport.

The Concept

In 1781, Gaspard Monge — a mathematician who would later become one of Napoleon's scientific advisors — published a paper called "Mémoire sur la théorie des déblais et des remblais" ("Memoir on the Theory of Cuttings and Fillings"). Translated out of 18th-century engineering jargon, the question was: if you have a pile of excavated soil in one shape and a hole you need to fill in another shape, what is the cheapest way to move every grain of dirt from the pile to the hole, where "cheapest" means minimizing total distance traveled?

This sounds like a narrow civil-engineering question, but it is really a question about comparing two shapes, or more generally, two distributions of stuff. Replace "piles of dirt" with "distributions of probability" and the question becomes universal: given two distributions — a "before" and an "after" — what is the minimum-cost way of morphing one into the other, where you're only allowed to move mass around, never create or destroy it?

Monge's version turned out to be extremely difficult to solve directly, and it sat as a mostly unsolved curiosity for over 150 years. The breakthrough came in 1942 from the Soviet mathematician and economist Leonid Kantorovich, who — initially unaware of Monge's work — reframed the problem. Instead of insisting that each grain of dirt go to exactly one destination, Kantorovich allowed mass to be split: half a shovelful could go one way, half another, as long as the books balanced at both ends. This relaxation turned an intractable combinatorial puzzle into a linear programming problem, which by the 1940s had tractable algorithms. Kantorovich later connected his work explicitly back to Monge's in a short 1948 paper, and the field has carried both of their names ever since: the Monge-Kantorovich transportation problem. Kantorovich went on to share the 1975 Nobel Prize in Economic Sciences (with Tjalling Koopmans) for applying this kind of optimization to the allocation of scarce resources.

The quantity that falls out of solving this problem — the minimum cost of transforming one distribution into another — is called the Wasserstein distance (named after Soviet mathematician Leonid Vaserstein), also known more vividly as the Earth Mover's Distance. It measures not just whether two distributions differ, but how much "work" it would take to reshape one into the other — which turns out to be a far more useful notion of distance than most of the alternatives mathematicians had been using.

Why It Matters

For most of its history, optimal transport was a tool for economists and a plaything for pure mathematicians. That changed dramatically once people realized two things: the Wasserstein distance is a genuinely better way to compare probability distributions than older tools like KL-divergence, and — thanks to a key computational trick — it could actually be calculated fast enough to use at scale.

The first big application outside economics came in computer vision. In 1998, Yossi Rubner, Carlo Tomasi, and Leonidas Guibas introduced the "Earth Mover's Distance" to the image-retrieval world, using it to compare color and texture histograms between images. Unlike simpler distance measures, EMD matched human perceptual judgments of image similarity remarkably well — two photos that "look similar" to a person tended to have low EMD, even when their raw pixel statistics looked quite different.

The real explosion, though, came from deep learning. Training a generative model means teaching a network to produce a distribution of outputs — synthetic images, say — that matches the distribution of some real dataset. That requires a way to measure the "distance" between the fake distribution and the real one, and feed back a useful training signal. Standard measures like KL-divergence have a serious flaw here: when two distributions don't overlap at all (common early in training, when the generator is still producing noise), those measures either blow up or go flat to zero, giving the network nothing useful to learn from.

The Wasserstein distance doesn't have this problem — because it measures the cost of moving mass rather than ratios of overlapping probability, it stays smooth and informative even when two distributions are far apart. In 2017, researchers Martin Arjovsky, Soumith Chintala, and Léon Bottou introduced the Wasserstein GAN, swapping the distance metric inside a generative adversarial network for something derived from optimal transport. The result was dramatically more stable training — one of the notorious pain points of the GAN era largely tamed by borrowing a 175-year-old idea about moving dirt.

Optimal transport now shows up far beyond images. In computational biology, a method called Waddington-OT uses optimal transport to reconstruct how populations of developing or reprogramming cells transition between states over time, matching single-cell gene-expression snapshots from one timepoint to the next as though each cell were a grain of sand finding its cheapest path forward. In natural language processing, it's used to compare word-embedding distributions across languages and documents. In economics — its original home — it still underlies modern matching markets, from school-choice assignment systems to algorithms that price and allocate goods.

The Details

What makes the optimal transport problem hard isn't the concept — it's the scale. If you have a distribution with a thousand points of "mass" on one side and a thousand on the other, the number of possible ways to match them up is staggering, and the honest linear-programming solution, while guaranteed optimal, scales so poorly that it becomes impractical for the sizes of data modern machine learning throws around (images with millions of pixels, embeddings with thousands of dimensions).

The fix that made optimal transport computationally practical for machine learning came from Marco Cuturi in 2013. His insight was to add a small entropic regularization term to the problem — essentially a mathematical nudge that discourages the transport plan from being too "sharp" or deterministic, and rewards it for spreading mass more smoothly. This seemingly small tweak transforms the problem from a rigid linear program into something that can be solved by a much older and far faster algorithm: the Sinkhorn-Knopp matrix scaling method, originally developed in the 1960s for a completely different purpose (balancing matrices so their rows and columns sum to given targets).

The Sinkhorn algorithm works by alternately rescaling the rows and then the columns of a cost matrix until everything balances — a simple, repetitive procedure that converges quickly and, crucially, is built almost entirely out of matrix multiplications. That makes it perfect for GPUs, the same hardware that makes modern neural network training possible. Cuturi showed this approach could compute near-optimal transport distances orders of magnitude faster than classical solvers, which is the difference between "an interesting idea mathematicians discuss" and "a tool you can bolt onto a neural network's loss function and train with every batch."

It helps to have a mental picture. Imagine two piles of sand on a table, each shaped differently, with the same total volume. The optimal transport plan is a complete set of instructions — move this much sand from this exact spot in pile A to that exact spot in pile B — chosen so the total "distance times sand moved" is as small as possible across every grain. The Wasserstein distance is just the final cost of following those instructions. If pile A is a tall, narrow spike and pile B is the same spike shifted three inches to the left, the optimal transport cost is simply "volume times three inches" — intuitively correct, cheap, and small. Compare that to a measure like KL-divergence, which in this same scenario would report something close to "infinitely different," since the two piles barely overlap. That single contrast — one measure that degrades gracefully as distributions drift apart, one that doesn't — is the whole reason optimal transport found a second life in deep learning nearly two centuries after Monge first wrote it down for moving dirt.

Takeaways

Optimal transport began in 1781 as Gaspard Monge's literal dirt-moving problem, and gained its modern, solvable form in 1942 when Leonid Kantorovich allowed mass to be split between destinations — work that later earned him a share of the 1975 Nobel Prize in Economic Sciences.
The resulting "cost of the cheapest transport plan" is called the Wasserstein distance, or informally the Earth Mover's Distance — a way of measuring the difference between two distributions that reflects how much "work" it takes to reshape one into the other.
Earth Mover's Distance proved valuable in computer vision as early as 1998, matching human perceptual judgments of image similarity better than simpler metrics.
The 2013 discovery that entropic regularization lets the Sinkhorn algorithm approximate optimal transport orders of magnitude faster made it practical for machine learning, directly enabling the more stable 2017 Wasserstein GAN.
The same mathematics now reconstructs developmental trajectories of living cells from single-cell sequencing data, showing how a single abstract idea — the cheapest way to move stuff around — keeps resurfacing across fields that otherwise have nothing to do with each other.

Resources: - Rubner, Y., Tomasi, C., & Guibas, L. (2000). "The Earth Mover's Distance as a Metric for Image Retrieval." International Journal of Computer Vision. - Cuturi, M. (2013). "Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances." NeurIPS. - Arjovsky, M., Chintala, S., & Bottou, L. (2017). "Wasserstein GAN." arXiv. - Schiebinger, G. et al. (2019). "Optimal-Transport Analysis of Single-Cell Gene Expression Identifies Developmental Trajectories in Reprogramming."30039-X) Cell.