Entropy-Regularized Optimal Transport for Complex System Modeling

Povzetek

Optimal transport provides a principled distance between probability distributions, but the classical linear program
that computes it scales cubically with sample size, a cost that has kept it out of reach for many complex-system
modeling tasks involving thousands of interacting states. We evaluate entropy-regularized optimal transport, solved
via the Sinkhorn-Knopp fixed-point iteration, as a scalable surrogate for exact transport distances across a
benchmark suite of 40 synthetic complex-system distributions built from coupled Gaussian mixtures and simulated
agent-based population densities, with support sizes ranging from 200 to 8,000 points. Across this suite, Sinkhorn
distances at regularization strength epsilon = 0.05 recovered exact Wasserstein-2 distances with a mean relative
error of 3.4% (SD 1.8%, range 0.6-9.1%) while reducing wall-clock computation time by a median factor of 46
relative to the exact network-simplex solver, with the speed advantage widening to a factor of over 210 at the
largest support size tested. Relative error was strongly regularization-dependent: decreasing epsilon from 0.20 to
0.01 lowered mean relative error from 11.7% to 1.2% but increased mean Sinkhorn iteration count from 38 to 412
before convergence to a fixed tolerance of 1e-9, producing a well-defined accuracy-runtime frontier rather than a
free improvement in either direction. Applying the method to track the entropy-regularized transport cost between
successive snapshots of a simulated 500-agent complex system undergoing a phase transition, we found that
transport cost rose sharply by 340% in the ten simulation steps preceding the transition and that this rise was
detectable at epsilon = 0.05 with a signal-to-noise ratio of 6.8, comparable to the exact-solver signal-to-noise ratio of
7.4 but at a fraction of the computational cost. A grid search over regularization strength and support size identified
epsilon in the range 0.03-0.08 as a practical operating window that kept relative error below 5% for supports up to
8,000 points while maintaining Sinkhorn convergence within 150 iterations for 94% of test cases. These findings
indicate that entropy-regularized optimal transport, appropriately tuned, offers a favorable accuracy-speed trade-off
for monitoring distributional change in large complex systems, and we provide concrete regularization-strength
guidance for practitioners seeking to deploy it at scale.