Computational Optimal Transport
summary
Computes that classic discrete OT is cubic (Hungarian / network‑flow), fragile (nonunique P with Jacobian zero or infinite) and statistically cursed in 5–50D or for n~100 samples, so practical use needs regularization. Adds entropic regularization yielding Pγ = diag(u) K diag(v) with K = exp(−C/γ), solved by the Sinkhorn algorithm (iterative row/column scaling). Differentiation options are unrolled automatic differentiation (memory heavy) or implicit differentiation* via the Jacobian of optimality conditions and a linear solve; software (OT tools) implements these routes.
AI-written summary · about
chapters (18)
- 0:00Start
- 2:47Example
- 3:23Singleton Genomics
- 7:44Empirical Risk Minimization
- 15:56Definitions of Optimal Transport
- 21:19The Optimal Assignment Problem
- 21:40The Hungarian Algorithm
- 24:45Controvic Dual Problem
- 29:59Sensitivity Analysis
- 43:37Input Convex Neural Networks
- 44:32Regularize the Primal Optimal Transfer Problem
- 45:54Entropic Regularization
- 46:08Bronier Theorem
- 50:39Optimal Transport Matrix
- 51:42Second Algorithm
- 1:03:02The Implicit Function Theorem
- 1:04:46Implicit Differentiation
- 1:07:49Optimal Matching
related talks
15mGraphical Optimal Transport and Its Applications
29mOptimal Transport in Python: A Practical Introduction with POT
09mA Fast Algorithm for Optimal Transport
11mOptimal Transport for Inverse Problems
48mSketching Techniques for Kernel Density Estimation or for Optimal Transport Computations
01h 18mOptimization I
38mSome Easy Optimization Problems Have the Overlap-Gap Property
34mFast Algorithms for Multivariate ODEs arising in Sampling and Learning